fs/btrfs/ulist.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2011 STRATO AG
0004  * written by Arne Jansen <sensille@gmx.net>
0005  */
0006
0007 #include <linux/slab.h>
0008 #include "ulist.h"
0009 #include "ctree.h"
0010
0011 /*
0012  * ulist is a generic data structure to hold a collection of unique u64
0013  * values. The only operations it supports is adding to the list and
0014  * enumerating it.
0015  * It is possible to store an auxiliary value along with the key.
0016  *
0017  * A sample usage for ulists is the enumeration of directed graphs without
0018  * visiting a node twice. The pseudo-code could look like this:
0019  *
0020  * ulist = ulist_alloc();
0021  * ulist_add(ulist, root);
0022  * ULIST_ITER_INIT(&uiter);
0023  *
0024  * while ((elem = ulist_next(ulist, &uiter)) {
0025  *  for (all child nodes n in elem)
0026  *      ulist_add(ulist, n);
0027  *  do something useful with the node;
0028  * }
0029  * ulist_free(ulist);
0030  *
0031  * This assumes the graph nodes are addressable by u64. This stems from the
0032  * usage for tree enumeration in btrfs, where the logical addresses are
0033  * 64 bit.
0034  *
0035  * It is also useful for tree enumeration which could be done elegantly
0036  * recursively, but is not possible due to kernel stack limitations. The
0037  * loop would be similar to the above.
0038  */
0039
0040 /**
0041  * ulist_init - freshly initialize a ulist
0042  * @ulist:  the ulist to initialize
0043  *
0044  * Note: don't use this function to init an already used ulist, use
0045  * ulist_reinit instead.
0046  */
0047 void ulist_init(struct ulist *ulist)
0048 {
0049     INIT_LIST_HEAD(&ulist->nodes);
0050     ulist->root = RB_ROOT;
0051     ulist->nnodes = 0;
0052 }
0053
0054 /**
0055  * ulist_release - free up additionally allocated memory for the ulist
0056  * @ulist:  the ulist from which to free the additional memory
0057  *
0058  * This is useful in cases where the base 'struct ulist' has been statically
0059  * allocated.
0060  */
0061 void ulist_release(struct ulist *ulist)
0062 {
0063     struct ulist_node *node;
0064     struct ulist_node *next;
0065
0066     list_for_each_entry_safe(node, next, &ulist->nodes, list) {
0067         kfree(node);
0068     }
0069     ulist->root = RB_ROOT;
0070     INIT_LIST_HEAD(&ulist->nodes);
0071 }
0072
0073 /**
0074  * ulist_reinit - prepare a ulist for reuse
0075  * @ulist:  ulist to be reused
0076  *
0077  * Free up all additional memory allocated for the list elements and reinit
0078  * the ulist.
0079  */
0080 void ulist_reinit(struct ulist *ulist)
0081 {
0082     ulist_release(ulist);
0083     ulist_init(ulist);
0084 }
0085
0086 /**
0087  * ulist_alloc - dynamically allocate a ulist
0088  * @gfp_mask:   allocation flags to for base allocation
0089  *
0090  * The allocated ulist will be returned in an initialized state.
0091  */
0092 struct ulist *ulist_alloc(gfp_t gfp_mask)
0093 {
0094     struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
0095
0096     if (!ulist)
0097         return NULL;
0098
0099     ulist_init(ulist);
0100
0101     return ulist;
0102 }
0103
0104 /**
0105  * ulist_free - free dynamically allocated ulist
0106  * @ulist:  ulist to free
0107  *
0108  * It is not necessary to call ulist_release before.
0109  */
0110 void ulist_free(struct ulist *ulist)
0111 {
0112     if (!ulist)
0113         return;
0114     ulist_release(ulist);
0115     kfree(ulist);
0116 }
0117
0118 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
0119 {
0120     struct rb_node *n = ulist->root.rb_node;
0121     struct ulist_node *u = NULL;
0122
0123     while (n) {
0124         u = rb_entry(n, struct ulist_node, rb_node);
0125         if (u->val < val)
0126             n = n->rb_right;
0127         else if (u->val > val)
0128             n = n->rb_left;
0129         else
0130             return u;
0131     }
0132     return NULL;
0133 }
0134
0135 static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node)
0136 {
0137     rb_erase(&node->rb_node, &ulist->root);
0138     list_del(&node->list);
0139     kfree(node);
0140     BUG_ON(ulist->nnodes == 0);
0141     ulist->nnodes--;
0142 }
0143
0144 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
0145 {
0146     struct rb_node **p = &ulist->root.rb_node;
0147     struct rb_node *parent = NULL;
0148     struct ulist_node *cur = NULL;
0149
0150     while (*p) {
0151         parent = *p;
0152         cur = rb_entry(parent, struct ulist_node, rb_node);
0153
0154         if (cur->val < ins->val)
0155             p = &(*p)->rb_right;
0156         else if (cur->val > ins->val)
0157             p = &(*p)->rb_left;
0158         else
0159             return -EEXIST;
0160     }
0161     rb_link_node(&ins->rb_node, parent, p);
0162     rb_insert_color(&ins->rb_node, &ulist->root);
0163     return 0;
0164 }
0165
0166 /**
0167  * ulist_add - add an element to the ulist
0168  * @ulist:  ulist to add the element to
0169  * @val:    value to add to ulist
0170  * @aux:    auxiliary value to store along with val
0171  * @gfp_mask:   flags to use for allocation
0172  *
0173  * Note: locking must be provided by the caller. In case of rwlocks write
0174  *       locking is needed
0175  *
0176  * Add an element to a ulist. The @val will only be added if it doesn't
0177  * already exist. If it is added, the auxiliary value @aux is stored along with
0178  * it. In case @val already exists in the ulist, @aux is ignored, even if
0179  * it differs from the already stored value.
0180  *
0181  * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
0182  * inserted.
0183  * In case of allocation failure -ENOMEM is returned and the ulist stays
0184  * unaltered.
0185  */
0186 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
0187 {
0188     return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
0189 }
0190
0191 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
0192             u64 *old_aux, gfp_t gfp_mask)
0193 {
0194     int ret;
0195     struct ulist_node *node;
0196
0197     node = ulist_rbtree_search(ulist, val);
0198     if (node) {
0199         if (old_aux)
0200             *old_aux = node->aux;
0201         return 0;
0202     }
0203     node = kmalloc(sizeof(*node), gfp_mask);
0204     if (!node)
0205         return -ENOMEM;
0206
0207     node->val = val;
0208     node->aux = aux;
0209
0210     ret = ulist_rbtree_insert(ulist, node);
0211     ASSERT(!ret);
0212     list_add_tail(&node->list, &ulist->nodes);
0213     ulist->nnodes++;
0214
0215     return 1;
0216 }
0217
0218 /*
0219  * ulist_del - delete one node from ulist
0220  * @ulist:  ulist to remove node from
0221  * @val:    value to delete
0222  * @aux:    aux to delete
0223  *
0224  * The deletion will only be done when *BOTH* val and aux matches.
0225  * Return 0 for successful delete.
0226  * Return > 0 for not found.
0227  */
0228 int ulist_del(struct ulist *ulist, u64 val, u64 aux)
0229 {
0230     struct ulist_node *node;
0231
0232     node = ulist_rbtree_search(ulist, val);
0233     /* Not found */
0234     if (!node)
0235         return 1;
0236
0237     if (node->aux != aux)
0238         return 1;
0239
0240     /* Found and delete */
0241     ulist_rbtree_erase(ulist, node);
0242     return 0;
0243 }
0244
0245 /**
0246  * ulist_next - iterate ulist
0247  * @ulist:  ulist to iterate
0248  * @uiter:  iterator variable, initialized with ULIST_ITER_INIT(&iterator)
0249  *
0250  * Note: locking must be provided by the caller. In case of rwlocks only read
0251  *       locking is needed
0252  *
0253  * This function is used to iterate an ulist.
0254  * It returns the next element from the ulist or %NULL when the
0255  * end is reached. No guarantee is made with respect to the order in which
0256  * the elements are returned. They might neither be returned in order of
0257  * addition nor in ascending order.
0258  * It is allowed to call ulist_add during an enumeration. Newly added items
0259  * are guaranteed to show up in the running enumeration.
0260  */
0261 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
0262 {
0263     struct ulist_node *node;
0264
0265     if (list_empty(&ulist->nodes))
0266         return NULL;
0267     if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes)
0268         return NULL;
0269     if (uiter->cur_list) {
0270         uiter->cur_list = uiter->cur_list->next;
0271     } else {
0272         uiter->cur_list = ulist->nodes.next;
0273     }
0274     node = list_entry(uiter->cur_list, struct ulist_node, list);
0275     return node;
0276 }