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