linux-imx

// SPDX-License-Identifier: GPL-2.0

/*

 * Copyright (C) 2011 STRATO AG

 * written by Arne Jansen <sensille@gmx.net>

 */

​

#include <linux/slab.h>

#include "ulist.h"

#include "ctree.h"

​

/*

 * ulist is a generic data structure to hold a collection of unique u64

 * values. The only operations it supports is adding to the list and

 * enumerating it.

 * It is possible to store an auxiliary value along with the key.

 *

 * A sample usage for ulists is the enumeration of directed graphs without

 * visiting a node twice. The pseudo-code could look like this:

 *

 * ulist = ulist_alloc();

 * ulist_add(ulist, root);

 * ULIST_ITER_INIT(&uiter);

 *

 * while ((elem = ulist_next(ulist, &uiter)) {

 *  for (all child nodes n in elem)

 *      ulist_add(ulist, n);

 *  do something useful with the node;

 * }

 * ulist_free(ulist);

 *

 * This assumes the graph nodes are addressable by u64. This stems from the

 * usage for tree enumeration in btrfs, where the logical addresses are

 * 64 bit.

 *

 * It is also useful for tree enumeration which could be done elegantly

 * recursively, but is not possible due to kernel stack limitations. The

 * loop would be similar to the above.

 */

​

/**

 * ulist_init - freshly initialize a ulist

 * @ulist:  the ulist to initialize

 *

 * Note: don't use this function to init an already used ulist, use

 * ulist_reinit instead.

 */

void ulist_init(struct ulist *ulist)

{

    INIT_LIST_HEAD(&ulist->nodes);

    ulist->root = RB_ROOT;

    ulist->nnodes = 0;

}

​

/**

 * ulist_release - free up additionally allocated memory for the ulist

 * @ulist:  the ulist from which to free the additional memory

 *

 * This is useful in cases where the base 'struct ulist' has been statically

 * allocated.

 */

void ulist_release(struct ulist *ulist)

{

    struct ulist_node *node;