Lines Matching refs:ulist
9 #include "ulist.h"
13 * ulist is a generic data structure to hold a collection of unique u64
21 * ulist = ulist_alloc();
22 * ulist_add(ulist, root);
25 * while ((elem = ulist_next(ulist, &uiter)) {
27 * ulist_add(ulist, n);
30 * ulist_free(ulist);
42 * Freshly initialize a ulist.
44 * @ulist: the ulist to initialize
46 * Note: don't use this function to init an already used ulist, use
49 void ulist_init(struct ulist *ulist)
51 INIT_LIST_HEAD(&ulist->nodes);
52 ulist->root = RB_ROOT;
53 ulist->nnodes = 0;
57 * Free up additionally allocated memory for the ulist.
59 * @ulist: the ulist from which to free the additional memory
61 * This is useful in cases where the base 'struct ulist' has been statically
64 void ulist_release(struct ulist *ulist)
69 list_for_each_entry_safe(node, next, &ulist->nodes, list) {
72 ulist->root = RB_ROOT;
73 INIT_LIST_HEAD(&ulist->nodes);
77 * Prepare a ulist for reuse.
79 * @ulist: ulist to be reused
82 * the ulist.
84 void ulist_reinit(struct ulist *ulist)
86 ulist_release(ulist);
87 ulist_init(ulist);
91 * Dynamically allocate a ulist.
95 * The allocated ulist will be returned in an initialized state.
97 struct ulist *ulist_alloc(gfp_t gfp_mask)
99 struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
101 if (!ulist)
104 ulist_init(ulist);
106 return ulist;
110 * Free dynamically allocated ulist.
112 * @ulist: ulist to free
116 void ulist_free(struct ulist *ulist)
118 if (!ulist)
120 ulist_release(ulist);
121 kfree(ulist);
124 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
126 struct rb_node *n = ulist->root.rb_node;
141 static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node)
143 rb_erase(&node->rb_node, &ulist->root);
146 BUG_ON(ulist->nnodes == 0);
147 ulist->nnodes--;
150 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
152 struct rb_node **p = &ulist->root.rb_node;
168 rb_insert_color(&ins->rb_node, &ulist->root);
173 * Add an element to the ulist.
175 * @ulist: ulist to add the element to
176 * @val: value to add to ulist
183 * Add an element to a ulist. The @val will only be added if it doesn't
185 * it. In case @val already exists in the ulist, @aux is ignored, even if
188 * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
190 * In case of allocation failure -ENOMEM is returned and the ulist stays
193 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
195 return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
198 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
204 node = ulist_rbtree_search(ulist, val);
217 ret = ulist_rbtree_insert(ulist, node);
219 list_add_tail(&node->list, &ulist->nodes);
220 ulist->nnodes++;
226 * ulist_del - delete one node from ulist
227 * @ulist: ulist to remove node from
235 int ulist_del(struct ulist *ulist, u64 val, u64 aux)
239 node = ulist_rbtree_search(ulist, val);
248 ulist_rbtree_erase(ulist, node);
253 * Iterate ulist.
255 * @ulist: ulist to iterate
261 * This function is used to iterate an ulist.
262 * It returns the next element from the ulist or %NULL when the
269 struct ulist_node *ulist_next(const struct ulist *ulist, struct ulist_iterator *uiter)
273 if (list_empty(&ulist->nodes))
275 if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes)
280 uiter->cur_list = ulist->nodes.next;