libfrog/radix-tree.h

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2001 Momchil Velikov
   4  * Portions Copyright (C) 2001 Christoph Hellwig
   5  */
   6 #ifndef __LIBFROG_RADIX_TREE_H__
   7 #define __LIBFROG_RADIX_TREE_H__
   8
   9 #define RADIX_TREE_TAGS
  10
  11 struct radix_tree_root {
  12         unsigned int            height;
  13         struct radix_tree_node  *rnode;
  14 };
  15
  16 #define RADIX_TREE_INIT(mask)   {                                       \
  17         .height = 0,                                                    \
  18         .rnode = NULL,                                                  \
  19 }
  20
  21 #define RADIX_TREE(name, mask) \
  22         struct radix_tree_root name = RADIX_TREE_INIT(mask)
  23
  24 #define INIT_RADIX_TREE(root, mask)                                     \
  25 do {                                                                    \
  26         (root)->height = 0;                                             \
  27         (root)->rnode = NULL;                                           \
  28 } while (0)
  29
  30 #ifdef RADIX_TREE_TAGS
  31 #define RADIX_TREE_MAX_TAGS 2
  32 #endif
  33
  34 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
  35 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
  36 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
  37 void *radix_tree_lookup_first(struct radix_tree_root *, unsigned long *);
  38 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
  39 unsigned int
  40 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
  41                         unsigned long first_index, unsigned int max_items);
  42 unsigned int
  43 radix_tree_gang_lookup_ex(struct radix_tree_root *root, void **results,
  44                         unsigned long first_index, unsigned long last_index,
  45                         unsigned int max_items);
  46
  47 void radix_tree_init(void);
  48
  49 #ifdef RADIX_TREE_TAGS
  50 void *radix_tree_tag_set(struct radix_tree_root *root,
  51                         unsigned long index, unsigned int tag);
  52 void *radix_tree_tag_clear(struct radix_tree_root *root,
  53                         unsigned long index, unsigned int tag);
  54 int radix_tree_tag_get(struct radix_tree_root *root,
  55                         unsigned long index, unsigned int tag);
  56 unsigned int
  57 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
  58                         unsigned long first_index, unsigned int max_items,
  59                         unsigned int tag);
  60 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
  61 #endif
  62
  63 #endif /* __LIBFROG_RADIX_TREE_H__ */