kern/include/radix.h

   1 /* Copyright (c) 2010 The Regents of the University of California
   2  * Barret Rhoden <brho@cs.berkeley.edu>
   3  * See LICENSE for details.
   4  *
   5  * Radix Tree, modeled after Linux's (described here:
   6  * http://lwn.net/Articles/175432/).
   7  *
   8  * It maps unsigned longs to void*s, growing the depth of the tree as needed to
   9  * handle more items.  It won't allow the insertion of existing keys, and it
  10  * can fail due to lack of memory.
  11  *
  12  * There are some utility functions, probably unimplemented til we need them,
  13  * that will make the tree have enough memory for future calls.
  14  *
  15  * You can also store a tag along with the void* for a given item, and do
  16  * lookups based on those tags.  Or you will be able to, once it is
  17  * implemented. */
  18
  19 #ifndef ROS_KERN_RADIX_H
  20 #define ROS_KERN_RADIX_H
  21
  22 #define LOG_RNODE_SLOTS 6
  23 #define NR_RNODE_SLOTS (1 << LOG_RNODE_SLOTS)
  24
  25 #include <ros/common.h>
  26
  27 struct radix_node {
  28         void                                            *items[NR_RNODE_SLOTS];
  29         unsigned int                            num_items;
  30         bool                                            leaf;
  31         struct radix_node                       *parent;
  32         struct radix_node                       **my_slot;
  33 };
  34
  35 /* Defines the whole tree. */
  36 struct radix_tree {
  37         struct radix_node                       *root;
  38         unsigned int                            depth;
  39         unsigned long                           upper_bound;
  40 };
  41
  42 void radix_init(void);          /* initializes the whole radix system */
  43 #define RADIX_INITIALIZER {0, 0, 0}
  44 void radix_tree_init(struct radix_tree *tree);  /* inits one tree */
  45 void radix_tree_destroy(struct radix_tree *tree);
  46
  47 /* Item management */
  48 int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
  49                  void ***slot_p);
  50 void *radix_delete(struct radix_tree *tree, unsigned long key);
  51 void *radix_lookup(struct radix_tree *tree, unsigned long key);
  52 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key);
  53 int radix_gang_lookup(struct radix_tree *tree, void **results,
  54                       unsigned long first, unsigned int max_items);
  55
  56 /* Memory management */
  57 int radix_grow(struct radix_tree *tree, unsigned long max);
  58 int radix_preload(struct radix_tree *tree, int flags);
  59
  60 /* Tag management */
  61 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag);
  62 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag);
  63 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag);
  64 int radix_tree_tagged(struct radix_tree *tree, int tag);
  65 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
  66                           unsigned long first, unsigned int max_items, int tag);
  67
  68 /* Debugging */
  69 void print_radix_tree(struct radix_tree *tree);
  70
  71 #endif /* !ROS_KERN_RADIX_H */