fs/btrfs/ulist.c

9 #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  * Freshly initialize a ulist.
43  * @ulist:	the ulist to initialize
45  * Note: don't use this function to init an already used ulist, use
48 void ulist_init(struct ulist *ulist)
50 	INIT_LIST_HEAD(&ulist->nodes);
51 	ulist->root = RB_ROOT;
52 	ulist->nnodes = 0;
56  * Free up additionally allocated memory for the ulist.
58  * @ulist:	the ulist from which to free the additional memory
60  * This is useful in cases where the base 'struct ulist' has been statically
63 void ulist_release(struct ulist *ulist)
68 	list_for_each_entry_safe(node, next, &ulist->nodes, list) {
71 	ulist->root = RB_ROOT;
72 	INIT_LIST_HEAD(&ulist->nodes);
76  * Prepare a ulist for reuse.
78  * @ulist:	ulist to be reused
81  * the ulist.
83 void ulist_reinit(struct ulist *ulist)
85 	ulist_release(ulist);
86 	ulist_init(ulist);
90  * Dynamically allocate a ulist.
94  * The allocated ulist will be returned in an initialized state.
96 struct ulist *ulist_alloc(gfp_t gfp_mask)
98 	struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
100 	if (!ulist)
103 	ulist_init(ulist);
105 	return ulist;
109  * Free dynamically allocated ulist.
111  * @ulist:	ulist to free
115 void ulist_free(struct ulist *ulist)
117 	if (!ulist)
119 	ulist_release(ulist);
120 	kfree(ulist);
123 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
125 	struct rb_node *n = ulist->root.rb_node;
140 static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node)
142 	rb_erase(&node->rb_node, &ulist->root);
145 	BUG_ON(ulist->nnodes == 0);
146 	ulist->nnodes--;
149 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
151 	struct rb_node **p = &ulist->root.rb_node;
167 	rb_insert_color(&ins->rb_node, &ulist->root);
172  * Add an element to the ulist.
174  * @ulist:	ulist to add the element to
175  * @val:	value to add to ulist
182  * Add an element to a ulist. The @val will only be added if it doesn't
184  * it. In case @val already exists in the ulist, @aux is ignored, even if
187  * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
189  * In case of allocation failure -ENOMEM is returned and the ulist stays
192 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
194 	return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
197 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
203 	node = ulist_rbtree_search(ulist, val);
216 	ret = ulist_rbtree_insert(ulist, node);
218 	list_add_tail(&node->list, &ulist->nodes);
219 	ulist->nnodes++;
225  * 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;