linux/fs/btrfs/ulist.c
<<
>>
Prefs
   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 <linux/module.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 * The implementation is preliminary and can probably be sped up
  18 * significantly. A first step would be to store the values in an rbtree
  19 * as soon as ULIST_SIZE is exceeded.
  20 *
  21 * A sample usage for ulists is the enumeration of directed graphs without
  22 * visiting a node twice. The pseudo-code could look like this:
  23 *
  24 * ulist = ulist_alloc();
  25 * ulist_add(ulist, root);
  26 * ULIST_ITER_INIT(&uiter);
  27 *
  28 * while ((elem = ulist_next(ulist, &uiter)) {
  29 *      for (all child nodes n in elem)
  30 *              ulist_add(ulist, n);
  31 *      do something useful with the node;
  32 * }
  33 * ulist_free(ulist);
  34 *
  35 * This assumes the graph nodes are adressable by u64. This stems from the
  36 * usage for tree enumeration in btrfs, where the logical addresses are
  37 * 64 bit.
  38 *
  39 * It is also useful for tree enumeration which could be done elegantly
  40 * recursively, but is not possible due to kernel stack limitations. The
  41 * loop would be similar to the above.
  42 */
  43
  44/**
  45 * ulist_init - freshly initialize a ulist
  46 * @ulist:      the ulist to initialize
  47 *
  48 * Note: don't use this function to init an already used ulist, use
  49 * ulist_reinit instead.
  50 */
  51void ulist_init(struct ulist *ulist)
  52{
  53        ulist->nnodes = 0;
  54        ulist->nodes = ulist->int_nodes;
  55        ulist->nodes_alloced = ULIST_SIZE;
  56}
  57EXPORT_SYMBOL(ulist_init);
  58
  59/**
  60 * ulist_fini - free up additionally allocated memory for the ulist
  61 * @ulist:      the ulist from which to free the additional memory
  62 *
  63 * This is useful in cases where the base 'struct ulist' has been statically
  64 * allocated.
  65 */
  66void ulist_fini(struct ulist *ulist)
  67{
  68        /*
  69         * The first ULIST_SIZE elements are stored inline in struct ulist.
  70         * Only if more elements are alocated they need to be freed.
  71         */
  72        if (ulist->nodes_alloced > ULIST_SIZE)
  73                kfree(ulist->nodes);
  74        ulist->nodes_alloced = 0;       /* in case ulist_fini is called twice */
  75}
  76EXPORT_SYMBOL(ulist_fini);
  77
  78/**
  79 * ulist_reinit - prepare a ulist for reuse
  80 * @ulist:      ulist to be reused
  81 *
  82 * Free up all additional memory allocated for the list elements and reinit
  83 * the ulist.
  84 */
  85void ulist_reinit(struct ulist *ulist)
  86{
  87        ulist_fini(ulist);
  88        ulist_init(ulist);
  89}
  90EXPORT_SYMBOL(ulist_reinit);
  91
  92/**
  93 * ulist_alloc - dynamically allocate a ulist
  94 * @gfp_mask:   allocation flags to for base allocation
  95 *
  96 * The allocated ulist will be returned in an initialized state.
  97 */
  98struct ulist *ulist_alloc(gfp_t gfp_mask)
  99{
 100        struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
 101
 102        if (!ulist)
 103                return NULL;
 104
 105        ulist_init(ulist);
 106
 107        return ulist;
 108}
 109EXPORT_SYMBOL(ulist_alloc);
 110
 111/**
 112 * ulist_free - free dynamically allocated ulist
 113 * @ulist:      ulist to free
 114 *
 115 * It is not necessary to call ulist_fini before.
 116 */
 117void ulist_free(struct ulist *ulist)
 118{
 119        if (!ulist)
 120                return;
 121        ulist_fini(ulist);
 122        kfree(ulist);
 123}
 124EXPORT_SYMBOL(ulist_free);
 125
 126/**
 127 * ulist_add - add an element to the ulist
 128 * @ulist:      ulist to add the element to
 129 * @val:        value to add to ulist
 130 * @aux:        auxiliary value to store along with val
 131 * @gfp_mask:   flags to use for allocation
 132 *
 133 * Note: locking must be provided by the caller. In case of rwlocks write
 134 *       locking is needed
 135 *
 136 * Add an element to a ulist. The @val will only be added if it doesn't
 137 * already exist. If it is added, the auxiliary value @aux is stored along with
 138 * it. In case @val already exists in the ulist, @aux is ignored, even if
 139 * it differs from the already stored value.
 140 *
 141 * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
 142 * inserted.
 143 * In case of allocation failure -ENOMEM is returned and the ulist stays
 144 * unaltered.
 145 */
 146int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
 147{
 148        return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
 149}
 150
 151int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
 152                    u64 *old_aux, gfp_t gfp_mask)
 153{
 154        int i;
 155
 156        for (i = 0; i < ulist->nnodes; ++i) {
 157                if (ulist->nodes[i].val == val) {
 158                        if (old_aux)
 159                                *old_aux = ulist->nodes[i].aux;
 160                        return 0;
 161                }
 162        }
 163
 164        if (ulist->nnodes >= ulist->nodes_alloced) {
 165                u64 new_alloced = ulist->nodes_alloced + 128;
 166                struct ulist_node *new_nodes;
 167                void *old = NULL;
 168
 169                /*
 170                 * if nodes_alloced == ULIST_SIZE no memory has been allocated
 171                 * yet, so pass NULL to krealloc
 172                 */
 173                if (ulist->nodes_alloced > ULIST_SIZE)
 174                        old = ulist->nodes;
 175
 176                new_nodes = krealloc(old, sizeof(*new_nodes) * new_alloced,
 177                                     gfp_mask);
 178                if (!new_nodes)
 179                        return -ENOMEM;
 180
 181                if (!old)
 182                        memcpy(new_nodes, ulist->int_nodes,
 183                               sizeof(ulist->int_nodes));
 184
 185                ulist->nodes = new_nodes;
 186                ulist->nodes_alloced = new_alloced;
 187        }
 188        ulist->nodes[ulist->nnodes].val = val;
 189        ulist->nodes[ulist->nnodes].aux = aux;
 190        ++ulist->nnodes;
 191
 192        return 1;
 193}
 194EXPORT_SYMBOL(ulist_add);
 195
 196/**
 197 * ulist_next - iterate ulist
 198 * @ulist:      ulist to iterate
 199 * @uiter:      iterator variable, initialized with ULIST_ITER_INIT(&iterator)
 200 *
 201 * Note: locking must be provided by the caller. In case of rwlocks only read
 202 *       locking is needed
 203 *
 204 * This function is used to iterate an ulist.
 205 * It returns the next element from the ulist or %NULL when the
 206 * end is reached. No guarantee is made with respect to the order in which
 207 * the elements are returned. They might neither be returned in order of
 208 * addition nor in ascending order.
 209 * It is allowed to call ulist_add during an enumeration. Newly added items
 210 * are guaranteed to show up in the running enumeration.
 211 */
 212struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
 213{
 214        if (ulist->nnodes == 0)
 215                return NULL;
 216        if (uiter->i < 0 || uiter->i >= ulist->nnodes)
 217                return NULL;
 218
 219        return &ulist->nodes[uiter->i++];
 220}
 221EXPORT_SYMBOL(ulist_next);
 222
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.