1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2011 STRATO AG 4 * written by Arne Jansen <sensille@gmx.net> 5 */ 6 7 #include <linux/slab.h> 8 #include "messages.h" 9 #include "ulist.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 addressable 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 * Freshly initialize a ulist. 42 * 43 * @ulist: the ulist to initialize 44 * 45 * Note: don't use this function to init an already used ulist, use 46 * ulist_reinit instead. 47 */ 48 void ulist_init(struct ulist *ulist) 49 { 50 INIT_LIST_HEAD(&ulist->nodes); 51 ulist->root = RB_ROOT; 52 ulist->nnodes = 0; 53 } 54 55 /* 56 * Free up additionally allocated memory for the ulist. 57 * 58 * @ulist: the ulist from which to free the additional memory 59 * 60 * This is useful in cases where the base 'struct ulist' has been statically 61 * allocated. 62 */ 63 void ulist_release(struct ulist *ulist) 64 { 65 struct ulist_node *node; 66 struct ulist_node *next; 67 68 list_for_each_entry_safe(node, next, &ulist->nodes, list) { 69 kfree(node); 70 } 71 ulist->root = RB_ROOT; 72 INIT_LIST_HEAD(&ulist->nodes); 73 } 74 75 /* 76 * Prepare a ulist for reuse. 77 * 78 * @ulist: ulist to be reused 79 * 80 * Free up all additional memory allocated for the list elements and reinit 81 * the ulist. 82 */ 83 void ulist_reinit(struct ulist *ulist) 84 { 85 ulist_release(ulist); 86 ulist_init(ulist); 87 } 88 89 /* 90 * Dynamically allocate a ulist. 91 * 92 * @gfp_mask: allocation flags to for base allocation 93 * 94 * The allocated ulist will be returned in an initialized state. 95 */ 96 struct ulist *ulist_alloc(gfp_t gfp_mask) 97 { 98 struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask); 99 100 if (!ulist) 101 return NULL; 102 103 ulist_init(ulist); 104 105 return ulist; 106 } 107 108 /* 109 * Free dynamically allocated ulist. 110 * 111 * @ulist: ulist to free 112 * 113 * It is not necessary to call ulist_release before. 114 */ 115 void ulist_free(struct ulist *ulist) 116 { 117 if (!ulist) 118 return; 119 ulist_release(ulist); 120 kfree(ulist); 121 } 122 123 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val) 124 { 125 struct rb_node *n = ulist->root.rb_node; 126 struct ulist_node *u = NULL; 127 128 while (n) { 129 u = rb_entry(n, struct ulist_node, rb_node); 130 if (u->val < val) 131 n = n->rb_right; 132 else if (u->val > val) 133 n = n->rb_left; 134 else 135 return u; 136 } 137 return NULL; 138 } 139 140 static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node) 141 { 142 rb_erase(&node->rb_node, &ulist->root); 143 list_del(&node->list); 144 kfree(node); 145 BUG_ON(ulist->nnodes == 0); 146 ulist->nnodes--; 147 } 148 149 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins) 150 { 151 struct rb_node **p = &ulist->root.rb_node; 152 struct rb_node *parent = NULL; 153 struct ulist_node *cur = NULL; 154 155 while (*p) { 156 parent = *p; 157 cur = rb_entry(parent, struct ulist_node, rb_node); 158 159 if (cur->val < ins->val) 160 p = &(*p)->rb_right; 161 else if (cur->val > ins->val) 162 p = &(*p)->rb_left; 163 else 164 return -EEXIST; 165 } 166 rb_link_node(&ins->rb_node, parent, p); 167 rb_insert_color(&ins->rb_node, &ulist->root); 168 return 0; 169 } 170 171 /* 172 * Add an element to the ulist. 173 * 174 * @ulist: ulist to add the element to 175 * @val: value to add to ulist 176 * @aux: auxiliary value to store along with val 177 * @gfp_mask: flags to use for allocation 178 * 179 * Note: locking must be provided by the caller. In case of rwlocks write 180 * locking is needed 181 * 182 * Add an element to a ulist. The @val will only be added if it doesn't 183 * already exist. If it is added, the auxiliary value @aux is stored along with 184 * it. In case @val already exists in the ulist, @aux is ignored, even if 185 * it differs from the already stored value. 186 * 187 * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been 188 * inserted. 189 * In case of allocation failure -ENOMEM is returned and the ulist stays 190 * unaltered. 191 */ 192 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask) 193 { 194 return ulist_add_merge(ulist, val, aux, NULL, gfp_mask); 195 } 196 197 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, 198 u64 *old_aux, gfp_t gfp_mask) 199 { 200 int ret; 201 struct ulist_node *node; 202 203 node = ulist_rbtree_search(ulist, val); 204 if (node) { 205 if (old_aux) 206 *old_aux = node->aux; 207 return 0; 208 } 209 node = kmalloc(sizeof(*node), gfp_mask); 210 if (!node) 211 return -ENOMEM; 212 213 node->val = val; 214 node->aux = aux; 215 216 ret = ulist_rbtree_insert(ulist, node); 217 ASSERT(!ret); 218 list_add_tail(&node->list, &ulist->nodes); 219 ulist->nnodes++; 220 221 return 1; 222 } 223 224 /* 225 * Delete one node from ulist. 226 * 227 * @ulist: ulist to remove node from 228 * @val: value to delete 229 * @aux: aux to delete 230 * 231 * The deletion will only be done when *BOTH* val and aux matches. 232 * Return 0 for successful delete. 233 * Return > 0 for not found. 234 */ 235 int ulist_del(struct ulist *ulist, u64 val, u64 aux) 236 { 237 struct ulist_node *node; 238 239 node = ulist_rbtree_search(ulist, val); 240 /* Not found */ 241 if (!node) 242 return 1; 243 244 if (node->aux != aux) 245 return 1; 246 247 /* Found and delete */ 248 ulist_rbtree_erase(ulist, node); 249 return 0; 250 } 251 252 /* 253 * Iterate ulist. 254 * 255 * @ulist: ulist to iterate 256 * @uiter: iterator variable, initialized with ULIST_ITER_INIT(&iterator) 257 * 258 * Note: locking must be provided by the caller. In case of rwlocks only read 259 * locking is needed 260 * 261 * This function is used to iterate an ulist. 262 * It returns the next element from the ulist or %NULL when the 263 * end is reached. No guarantee is made with respect to the order in which 264 * the elements are returned. They might neither be returned in order of 265 * addition nor in ascending order. 266 * It is allowed to call ulist_add during an enumeration. Newly added items 267 * are guaranteed to show up in the running enumeration. 268 */ 269 struct ulist_node *ulist_next(const struct ulist *ulist, struct ulist_iterator *uiter) 270 { 271 struct ulist_node *node; 272 273 if (list_empty(&ulist->nodes)) 274 return NULL; 275 if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes) 276 return NULL; 277 if (uiter->cur_list) { 278 uiter->cur_list = uiter->cur_list->next; 279 } else { 280 uiter->cur_list = ulist->nodes.next; 281 } 282 node = list_entry(uiter->cur_list, struct ulist_node, list); 283 return node; 284 } 285