Lines Matching refs:ulist
8 #include "ulist.h"
12 * ulist is a generic data structure to hold a collection of unique u64
20 * ulist = ulist_alloc();
21 * ulist_add(ulist, root);
24 * while ((elem = ulist_next(ulist, &uiter)) {
26 * ulist_add(ulist, n);
29 * ulist_free(ulist);
41 * ulist_init - freshly initialize a ulist
42 * @ulist: the ulist to initialize
44 * Note: don't use this function to init an already used ulist, use
47 void ulist_init(struct ulist *ulist)
49 INIT_LIST_HEAD(&ulist->nodes);
50 ulist->root = RB_ROOT;
51 ulist->nnodes = 0;
55 * ulist_release - free up additionally allocated memory for the ulist
56 * @ulist: the ulist from which to free the additional memory
58 * This is useful in cases where the base 'struct ulist' has been statically
61 void ulist_release(struct ulist *ulist)
66 list_for_each_entry_safe(node, next, &ulist->nodes, list) {
69 ulist->root = RB_ROOT;
70 INIT_LIST_HEAD(&ulist->nodes);
74 * ulist_reinit - prepare a ulist for reuse
75 * @ulist: ulist to be reused
78 * the ulist.
80 void ulist_reinit(struct ulist *ulist)
82 ulist_release(ulist);
83 ulist_init(ulist);
87 * ulist_alloc - dynamically allocate a ulist
90 * The allocated ulist will be returned in an initialized state.
92 struct ulist *ulist_alloc(gfp_t gfp_mask)
94 struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
96 if (!ulist)
99 ulist_init(ulist);
101 return ulist;
105 * ulist_free - free dynamically allocated ulist
106 * @ulist: ulist to free
110 void ulist_free(struct ulist *ulist)
112 if (!ulist)
114 ulist_release(ulist);
115 kfree(ulist);
118 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
120 struct rb_node *n = ulist->root.rb_node;
135 static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node)
137 rb_erase(&node->rb_node, &ulist->root);
140 BUG_ON(ulist->nnodes == 0);
141 ulist->nnodes--;
144 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
146 struct rb_node **p = &ulist->root.rb_node;
162 rb_insert_color(&ins->rb_node, &ulist->root);
167 * ulist_add - add an element to the ulist
168 * @ulist: ulist to add the element to
169 * @val: value to add to ulist
176 * Add an element to a ulist. The @val will only be added if it doesn't
178 * it. In case @val already exists in the ulist, @aux is ignored, even if
181 * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
183 * In case of allocation failure -ENOMEM is returned and the ulist stays
186 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
188 return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
191 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
197 node = ulist_rbtree_search(ulist, val);
210 ret = ulist_rbtree_insert(ulist, node);
212 list_add_tail(&node->list, &ulist->nodes);
213 ulist->nnodes++;
219 * ulist_del - delete one node from ulist
220 * @ulist: ulist to remove node from
228 int ulist_del(struct ulist *ulist, u64 val, u64 aux)
232 node = ulist_rbtree_search(ulist, val);
241 ulist_rbtree_erase(ulist, node);
246 * ulist_next - iterate ulist
247 * @ulist: ulist to iterate
253 * This function is used to iterate an ulist.
254 * It returns the next element from the ulist or %NULL when the
261 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
265 if (list_empty(&ulist->nodes))
267 if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes)
272 uiter->cur_list = ulist->nodes.next;