fs/btrfs/ulist.h

   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
   8 #ifndef __ULIST__
   9 #define __ULIST__
  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
  22 /*
  23  * number of elements statically allocated inside struct ulist
  24  */
  25 #define ULIST_SIZE 16
  26
  27 struct ulist_iterator {
  28         int i;
  29 };
  30
  31 /*
  32  * element of the list
  33  */
  34 struct ulist_node {
  35         u64 val;                /* value to store */
  36         unsigned long aux;      /* auxiliary value saved along with the val */
  37 };
  38
  39 struct ulist {
  40         /*
  41          * number of elements stored in list
  42          */
  43         unsigned long nnodes;
  44
  45         /*
  46          * number of nodes we already have room for
  47          */
  48         unsigned long nodes_alloced;
  49
  50         /*
  51          * pointer to the array storing the elements. The first ULIST_SIZE
  52          * elements are stored inline. In this case the it points to int_nodes.
  53          * After exceeding ULIST_SIZE, dynamic memory is allocated.
  54          */
  55         struct ulist_node *nodes;
  56
  57         /*
  58          * inline storage space for the first ULIST_SIZE entries
  59          */
  60         struct ulist_node int_nodes[ULIST_SIZE];
  61 };
  62
  63 void ulist_init(struct ulist *ulist);
  64 void ulist_fini(struct ulist *ulist);
  65 void ulist_reinit(struct ulist *ulist);
  66 struct ulist *ulist_alloc(gfp_t gfp_mask);
  67 void ulist_free(struct ulist *ulist);
  68 int ulist_add(struct ulist *ulist, u64 val, unsigned long aux,
  69               gfp_t gfp_mask);
  70 int ulist_add_merge(struct ulist *ulist, u64 val, unsigned long aux,
  71                     unsigned long *old_aux, gfp_t gfp_mask);
  72 struct ulist_node *ulist_next(struct ulist *ulist,
  73                               struct ulist_iterator *uiter);
  74
  75 #define ULIST_ITER_INIT(uiter) ((uiter)->i = 0)
  76
  77 #endif