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