git.sesse.net Git - bcachefs-tools-debian/blob - include/linux/generic-radix-tree.h

   1 #ifndef _LINUX_GENERIC_RADIX_TREE_H
   2 #define _LINUX_GENERIC_RADIX_TREE_H
   3
   4 /*
   5  * Generic radix trees/sparse arrays:
   6  *
   7  * A generic radix tree has all nodes of size PAGE_SIZE - both leaves and
   8  * interior nodes.
   9  */
  10
  11 #include <linux/page.h>
  12 #include <linux/bug.h>
  13 #include <linux/kernel.h>
  14 #include <linux/log2.h>
  15
  16 struct genradix_node;
  17
  18 struct __genradix {
  19         struct genradix_node            *root;
  20         size_t                          depth;
  21 };
  22
  23 /*
  24  * NOTE: currently, sizeof(_type) must be a power of two and not larger than
  25  * PAGE_SIZE:
  26  */
  27
  28 #define __GENRADIX_INITIALIZER                                  \
  29         {                                                       \
  30                 .tree = {                                       \
  31                         .root = NULL,                           \
  32                         .depth = 0,                             \
  33                 }                                               \
  34         }
  35
  36 /*
  37  * We use a 0 size array to stash the type we're storing without taking any
  38  * space at runtime - then the various accessor macros can use typeof() to get
  39  * to it for casts/sizeof - we also force the alignment so that storing a type
  40  * with a ridiculous alignment doesn't blow up the alignment or size of the
  41  * genradix.
  42  */
  43
  44 #define DECLARE_GENRADIX_TYPE(_name, _type)                     \
  45 struct _name {                                                  \
  46         struct __genradix       tree;                           \
  47         _type                   type[0] __aligned(1);           \
  48 }
  49
  50 #define DECLARE_GENRADIX(_name, _type)                          \
  51 struct {                                                        \
  52         struct __genradix       tree;                           \
  53         _type                   type[0] __aligned(1);           \
  54 } _name
  55
  56 #define DEFINE_GENRADIX(_name, _type)                           \
  57         DECLARE_GENRADIX(_name, _type) = __GENRADIX_INITIALIZER
  58
  59 #define genradix_init(_radix)                                   \
  60 do {                                                            \
  61         *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER;   \
  62 } while (0)
  63
  64 void __genradix_free(struct __genradix *);
  65
  66 #define genradix_free(_radix)   __genradix_free(&(_radix)->tree)
  67
  68 static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
  69 {
  70         BUILD_BUG_ON(obj_size > PAGE_SIZE);
  71
  72         if (!is_power_of_2(obj_size)) {
  73                 size_t objs_per_page = PAGE_SIZE / obj_size;
  74
  75                 return (idx / objs_per_page) * PAGE_SIZE +
  76                         (idx % objs_per_page) * obj_size;
  77         } else {
  78                 return idx * obj_size;
  79         }
  80 }
  81
  82 #define __genradix_cast(_radix)         (typeof((_radix)->type[0]) *)
  83 #define __genradix_obj_size(_radix)     sizeof((_radix)->type[0])
  84 #define __genradix_idx_to_offset(_radix, _idx)                  \
  85         __idx_to_offset(_idx, __genradix_obj_size(_radix))
  86
  87 void *__genradix_ptr(struct __genradix *, size_t);
  88
  89 /* Returns a pointer to element at @_idx */
  90 #define genradix_ptr(_radix, _idx)                              \
  91         (__genradix_cast(_radix)                                \
  92          __genradix_ptr(&(_radix)->tree,                        \
  93                         __genradix_idx_to_offset(_radix, _idx)))
  94
  95 void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
  96
  97 /* Returns a pointer to element at @_idx, allocating it if necessary */
  98 #define genradix_ptr_alloc(_radix, _idx, _gfp)                  \
  99         (__genradix_cast(_radix)                                \
 100          __genradix_ptr_alloc(&(_radix)->tree,                  \
 101                         __genradix_idx_to_offset(_radix, _idx), \
 102                         _gfp))
 103
 104 struct genradix_iter {
 105         size_t                  offset;
 106         size_t                  pos;
 107 };
 108
 109 static inline void genradix_iter_init(struct genradix_iter *iter)
 110 {
 111         iter->offset    = 0;
 112         iter->pos       = 0;
 113 }
 114
 115 void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
 116
 117 #define genradix_iter_peek(_iter, _radix)                       \
 118         (__genradix_cast(_radix)                                \
 119          __genradix_iter_peek(_iter, &(_radix)->tree,           \
 120                               PAGE_SIZE / __genradix_obj_size(_radix)))
 121
 122 static inline void __genradix_iter_advance(struct genradix_iter *iter,
 123                                            size_t obj_size)
 124 {
 125         iter->offset += obj_size;
 126
 127         if (!is_power_of_2(obj_size) &&
 128             (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
 129                 iter->offset = round_up(iter->offset, PAGE_SIZE);
 130
 131         iter->pos++;
 132 }
 133
 134 #define genradix_iter_advance(_iter, _radix)                    \
 135         __genradix_iter_advance(_iter, __genradix_obj_size(_radix))
 136
 137 #endif /* _LINUX_GENERIC_RADIX_TREE_H */