src/xt_critbit.h

   1 /*
   2  * Lightweight Autonomic Network Architecture
   3  *
   4  * Copyright 2011 Daniel Borkmann <dborkma@tik.ee.ethz.ch>,
   5  * Swiss federal institute of technology (ETH Zurich)
   6  * Subject to the GPL.
   7  */
   8
   9 #ifndef CRITBIT_H
  10 #define CRITBIT_H
  11
  12 #include <linux/spinlock.h>
  13
  14 /*
  15  * Note that 'myname' is null-terminated and must be power of two aligned,
  16  * otherwise you trap into unspecified behaviour. To retrive a struct you
  17  * can do the following:
  18  *
  19  * struct mystruct {
  20  *      char myname[IFNAMSIZ];
  21  *      int myflag;
  22  *      ...
  23  * } ____cacheline_aligned;
  24  *
  25  * Here, myname is at the start of the struct and cacheline aligned. Then,
  26  * instantiate such a struct with i.e. name "foobar" and add it to your tree
  27  * with critbit_insert(&mytree, foo->name).
  28  *
  29  * Later on, if your are about to retrive your struct, do a lookup like
  30  * struct mystruct *bar = struct_of(critbit_get(&mytree, "foobar"), struct mystruct);
  31  * and there you go. Not that bar points to the same location as foo.
  32  */
  33
  34 struct critbit_tree {
  35         void *root;
  36         spinlock_t wr_lock;
  37 };
  38
  39 #define struct_of(ptr, type)  ((type *)(ptr))
  40
  41 /* Lock holding variants. */
  42 extern int critbit_insert(struct critbit_tree *tree, char *elem);
  43 extern char *critbit_get(struct critbit_tree *tree, const char *elem);
  44 extern int critbit_delete(struct critbit_tree *tree, const char *elem);
  45 extern int critbit_contains(struct critbit_tree *tree, const char *elem);
  46
  47 /* Non-lock holding variants. */
  48 extern int __critbit_insert(struct critbit_tree *tree, char *elem);
  49 extern char *__critbit_get(struct critbit_tree *tree, const char *elem);
  50 extern int __critbit_delete(struct critbit_tree *tree, const char *elem);
  51 extern int __critbit_contains(struct critbit_tree *tree, const char *elem);
  52
  53 /*
  54  * If your module needs the critbit cache, call get_critbit_cache() on
  55  * module init and put_critbit_cache() on module unload!
  56  */
  57 extern void get_critbit_cache(void);
  58 extern void put_critbit_cache(void);
  59
  60 static inline void critbit_init_tree(struct critbit_tree *tree)
  61 {
  62         tree->wr_lock = __SPIN_LOCK_UNLOCKED(wr_lock);
  63 }
  64
  65 #endif  /* CRITBIT_H */