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 /*
  28  * element of the list
  29  */
  30 struct ulist_node {
  31         u64 val;                /* value to store */
  32         unsigned long aux;      /* auxiliary value saved along with the val */
  33 };
  34
  35 struct ulist {
  36         /*
  37          * number of elements stored in list
  38          */
  39         unsigned long nnodes;
  40
  41         /*
  42          * number of nodes we already have room for
  43          */
  44         unsigned long nodes_alloced;
  45
  46         /*
  47          * pointer to the array storing the elements. The first ULIST_SIZE
  48          * elements are stored inline. In this case the it points to int_nodes.
  49          * After exceeding ULIST_SIZE, dynamic memory is allocated.
  50          */
  51         struct ulist_node *nodes;
  52
  53         /*
  54          * inline storage space for the first ULIST_SIZE entries
  55          */
  56         struct ulist_node int_nodes[ULIST_SIZE];
  57 };
  58
  59 void ulist_init(struct ulist *ulist);
  60 void ulist_fini(struct ulist *ulist);
  61 void ulist_reinit(struct ulist *ulist);
  62 struct ulist *ulist_alloc(unsigned long gfp_mask);
  63 void ulist_free(struct ulist *ulist);
  64 int ulist_add(struct ulist *ulist, u64 val, unsigned long aux,
  65               unsigned long gfp_mask);
  66 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_node *prev);
  67
  68 #endif