1 /* 2 * Copyright (C) 2011 STRATO AG 3 * written by Arne Jansen <sensille@gmx.net> 4 * Distributed under the GNU GPL license version 2. 5 */ 6 7 #include <linux/slab.h> 8 #include "ulist.h" 9 #include "ctree.h" 10 11 /* 12 * ulist is a generic data structure to hold a collection of unique u64 13 * values. The only operations it supports is adding to the list and 14 * enumerating it. 15 * It is possible to store an auxiliary value along with the key. 16 * 17 * A sample usage for ulists is the enumeration of directed graphs without 18 * visiting a node twice. The pseudo-code could look like this: 19 * 20 * ulist = ulist_alloc(); 21 * ulist_add(ulist, root); 22 * ULIST_ITER_INIT(&uiter); 23 * 24 * while ((elem = ulist_next(ulist, &uiter)) { 25 * for (all child nodes n in elem) 26 * ulist_add(ulist, n); 27 * do something useful with the node; 28 * } 29 * ulist_free(ulist); 30 * 31 * This assumes the graph nodes are adressable by u64. This stems from the 32 * usage for tree enumeration in btrfs, where the logical addresses are 33 * 64 bit. 34 * 35 * It is also useful for tree enumeration which could be done elegantly 36 * recursively, but is not possible due to kernel stack limitations. The 37 * loop would be similar to the above. 38 */ 39 40 /** 41 * ulist_init - freshly initialize a ulist 42 * @ulist: the ulist to initialize 43 * 44 * Note: don't use this function to init an already used ulist, use 45 * ulist_reinit instead. 46 */ 47 void ulist_init(struct ulist *ulist) 48 { 49 INIT_LIST_HEAD(&ulist->nodes); 50 ulist->root = RB_ROOT; 51 ulist->nnodes = 0; 52 } 53 54 /** 55 * ulist_fini - free up additionally allocated memory for the ulist 56 * @ulist: the ulist from which to free the additional memory 57 * 58 * This is useful in cases where the base 'struct ulist' has been statically 59 * allocated. 60 */ 61 static void ulist_fini(struct ulist *ulist) 62 { 63 struct ulist_node *node; 64 struct ulist_node *next; 65 66 list_for_each_entry_safe(node, next, &ulist->nodes, list) { 67 kfree(node); 68 } 69 ulist->root = RB_ROOT; 70 INIT_LIST_HEAD(&ulist->nodes); 71 } 72 73 /** 74 * ulist_reinit - prepare a ulist for reuse 75 * @ulist: ulist to be reused 76 * 77 * Free up all additional memory allocated for the list elements and reinit 78 * the ulist. 79 */ 80 void ulist_reinit(struct ulist *ulist) 81 { 82 ulist_fini(ulist); 83 ulist_init(ulist); 84 } 85 86 /** 87 * ulist_alloc - dynamically allocate a ulist 88 * @gfp_mask: allocation flags to for base allocation 89 * 90 * The allocated ulist will be returned in an initialized state. 91 */ 92 struct ulist *ulist_alloc(gfp_t gfp_mask) 93 { 94 struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask); 95 96 if (!ulist) 97 return NULL; 98 99 ulist_init(ulist); 100 101 return ulist; 102 } 103 104 /** 105 * ulist_free - free dynamically allocated ulist 106 * @ulist: ulist to free 107 * 108 * It is not necessary to call ulist_fini before. 109 */ 110 void ulist_free(struct ulist *ulist) 111 { 112 if (!ulist) 113 return; 114 ulist_fini(ulist); 115 kfree(ulist); 116 } 117 118 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val) 119 { 120 struct rb_node *n = ulist->root.rb_node; 121 struct ulist_node *u = NULL; 122 123 while (n) { 124 u = rb_entry(n, struct ulist_node, rb_node); 125 if (u->val < val) 126 n = n->rb_right; 127 else if (u->val > val) 128 n = n->rb_left; 129 else 130 return u; 131 } 132 return NULL; 133 } 134 135 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins) 136 { 137 struct rb_node **p = &ulist->root.rb_node; 138 struct rb_node *parent = NULL; 139 struct ulist_node *cur = NULL; 140 141 while (*p) { 142 parent = *p; 143 cur = rb_entry(parent, struct ulist_node, rb_node); 144 145 if (cur->val < ins->val) 146 p = &(*p)->rb_right; 147 else if (cur->val > ins->val) 148 p = &(*p)->rb_left; 149 else 150 return -EEXIST; 151 } 152 rb_link_node(&ins->rb_node, parent, p); 153 rb_insert_color(&ins->rb_node, &ulist->root); 154 return 0; 155 } 156 157 /** 158 * ulist_add - add an element to the ulist 159 * @ulist: ulist to add the element to 160 * @val: value to add to ulist 161 * @aux: auxiliary value to store along with val 162 * @gfp_mask: flags to use for allocation 163 * 164 * Note: locking must be provided by the caller. In case of rwlocks write 165 * locking is needed 166 * 167 * Add an element to a ulist. The @val will only be added if it doesn't 168 * already exist. If it is added, the auxiliary value @aux is stored along with 169 * it. In case @val already exists in the ulist, @aux is ignored, even if 170 * it differs from the already stored value. 171 * 172 * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been 173 * inserted. 174 * In case of allocation failure -ENOMEM is returned and the ulist stays 175 * unaltered. 176 */ 177 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask) 178 { 179 return ulist_add_merge(ulist, val, aux, NULL, gfp_mask); 180 } 181 182 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, 183 u64 *old_aux, gfp_t gfp_mask) 184 { 185 int ret; 186 struct ulist_node *node; 187 188 node = ulist_rbtree_search(ulist, val); 189 if (node) { 190 if (old_aux) 191 *old_aux = node->aux; 192 return 0; 193 } 194 node = kmalloc(sizeof(*node), gfp_mask); 195 if (!node) 196 return -ENOMEM; 197 198 node->val = val; 199 node->aux = aux; 200 #ifdef CONFIG_BTRFS_DEBUG 201 node->seqnum = ulist->nnodes; 202 #endif 203 204 ret = ulist_rbtree_insert(ulist, node); 205 ASSERT(!ret); 206 list_add_tail(&node->list, &ulist->nodes); 207 ulist->nnodes++; 208 209 return 1; 210 } 211 212 /** 213 * ulist_next - iterate ulist 214 * @ulist: ulist to iterate 215 * @uiter: iterator variable, initialized with ULIST_ITER_INIT(&iterator) 216 * 217 * Note: locking must be provided by the caller. In case of rwlocks only read 218 * locking is needed 219 * 220 * This function is used to iterate an ulist. 221 * It returns the next element from the ulist or %NULL when the 222 * end is reached. No guarantee is made with respect to the order in which 223 * the elements are returned. They might neither be returned in order of 224 * addition nor in ascending order. 225 * It is allowed to call ulist_add during an enumeration. Newly added items 226 * are guaranteed to show up in the running enumeration. 227 */ 228 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter) 229 { 230 struct ulist_node *node; 231 232 if (list_empty(&ulist->nodes)) 233 return NULL; 234 if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes) 235 return NULL; 236 if (uiter->cur_list) { 237 uiter->cur_list = uiter->cur_list->next; 238 } else { 239 uiter->cur_list = ulist->nodes.next; 240 #ifdef CONFIG_BTRFS_DEBUG 241 uiter->i = 0; 242 #endif 243 } 244 node = list_entry(uiter->cur_list, struct ulist_node, list); 245 #ifdef CONFIG_BTRFS_DEBUG 246 ASSERT(node->seqnum == uiter->i); 247 ASSERT(uiter->i >= 0 && uiter->i < ulist->nnodes); 248 uiter->i++; 249 #endif 250 return node; 251 } 252