librb/include/rb_patricia.h

   1 /*
   2  * Dave Plonka <plonka@doit.wisc.edu>
   3  *
   4  * This product includes software developed by the University of Michigan,
   5  * Merit Network, Inc., and their contributors.
   6  *
   7  * This file had been called "radix.h" in the MRT sources.
   8  *
   9  * I renamed it to "patricia.h" since it's not an implementation of a general
  10  * radix trie.  Also, pulled in various requirements from "mrt.h" and added
  11  * some other things it could be used as a standalone API.
  12  */
  13
  14 #ifndef _RB_PATRICIA_H
  15 #define _RB_PATRICIA_H
  16
  17 #ifndef FALSE
  18 #define FALSE 0
  19 #endif
  20 #ifndef TRUE
  21 #define TRUE !(FALSE)
  22 #endif
  23 #ifndef INET6_ADDRSTRLEN
  24 #define INET6_ADDRSTRLEN 46
  25 #endif
  26
  27 #define rb_prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
  28 #define MAXLINE 1024
  29 #define BIT_TEST(f, b)  ((f) & (b))
  30
  31 typedef struct _rb_prefix_t
  32 {
  33         unsigned short family;  /* AF_INET | AF_INET6 */
  34         unsigned short bitlen;  /* same as mask? */
  35         int ref_count;          /* reference count */
  36         union
  37         {
  38                 struct in_addr sin;
  39 #ifdef RB_IPV6
  40                 struct in6_addr sin6;
  41 #endif                          /* RB_IPV6 */
  42         }
  43         add;
  44 }
  45 rb_prefix_t;
  46
  47
  48 typedef struct _rb_patricia_node_t
  49 {
  50         unsigned int bit;       /* flag if this node used */
  51         rb_prefix_t *prefix;    /* who we are in patricia tree */
  52         struct _rb_patricia_node_t *l, *r;      /* left and right children */
  53         struct _rb_patricia_node_t *parent;     /* may be used */
  54         void *data;
  55 }
  56 rb_patricia_node_t;
  57
  58 typedef struct _rb_patricia_tree_t
  59 {
  60         rb_patricia_node_t *head;
  61         unsigned int maxbits;   /* for IP, 32 bit addresses */
  62         int num_active_node;    /* for debug purpose */
  63 }
  64 rb_patricia_tree_t;
  65
  66
  67 rb_patricia_node_t *rb_match_ip(rb_patricia_tree_t *tree, struct sockaddr *ip);
  68 rb_patricia_node_t *rb_match_ip_exact(rb_patricia_tree_t *tree, struct sockaddr *ip,
  69                                       unsigned int len);
  70 rb_patricia_node_t *rb_match_string(rb_patricia_tree_t *tree, const char *string);
  71 rb_patricia_node_t *rb_match_exact_string(rb_patricia_tree_t *tree, const char *string);
  72 rb_patricia_node_t *rb_patricia_search_exact(rb_patricia_tree_t *patricia, rb_prefix_t *prefix);
  73 rb_patricia_node_t *rb_patricia_search_best(rb_patricia_tree_t *patricia, rb_prefix_t *prefix);
  74 rb_patricia_node_t *rb_patricia_search_best2(rb_patricia_tree_t *patricia,
  75                                              rb_prefix_t *prefix, int inclusive);
  76 rb_patricia_node_t *rb_patricia_lookup(rb_patricia_tree_t *patricia, rb_prefix_t *prefix);
  77
  78 void rb_patricia_remove(rb_patricia_tree_t *patricia, rb_patricia_node_t *node);
  79 rb_patricia_tree_t *rb_new_patricia(int maxbits);
  80 void rb_clear_patricia(rb_patricia_tree_t *patricia, void (*func) (void *));
  81 void rb_destroy_patricia(rb_patricia_tree_t *patricia, void (*func) (void *));
  82 void rb_patricia_process(rb_patricia_tree_t *patricia, void (*func) (rb_prefix_t *, void *));
  83 void rb_init_patricia(void);
  84
  85
  86 #if 0
  87 rb_prefix_t *ascii2prefix(int family, char *string);
  88 #endif
  89 rb_patricia_node_t *make_and_lookup(rb_patricia_tree_t *tree, const char *string);
  90 rb_patricia_node_t *make_and_lookup_ip(rb_patricia_tree_t *tree, struct sockaddr *, int bitlen);
  91
  92
  93 #define RB_PATRICIA_MAXBITS 128
  94 #define RB_PATRICIA_NBIT(x)        (0x80 >> ((x) & 0x7f))
  95 #define RB_PATRICIA_NBYTE(x)       ((x) >> 3)
  96
  97 #define RB_PATRICIA_DATA_GET(node, type) (type *)((node)->data)
  98 #define RB_PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
  99
 100 #define RB_PATRICIA_WALK(Xhead, Xnode) \
 101     do { \
 102         rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \
 103         rb_patricia_node_t **Xsp = Xstack; \
 104         rb_patricia_node_t *Xrn = (Xhead); \
 105         while ((Xnode = Xrn)) { \
 106             if (Xnode->prefix)
 107
 108 #define RB_PATRICIA_WALK_ALL(Xhead, Xnode) \
 109 do { \
 110         rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \
 111         rb_patricia_node_t **Xsp = Xstack; \
 112         rb_patricia_node_t *Xrn = (Xhead); \
 113         while ((Xnode = Xrn)) { \
 114             if (1)
 115
 116 #define RB_PATRICIA_WALK_BREAK { \
 117             if (Xsp != Xstack) { \
 118                 Xrn = *(--Xsp); \
 119              } else { \
 120                 Xrn = (rb_patricia_node_t *) 0; \
 121             } \
 122             continue; }
 123
 124 #define RB_PATRICIA_WALK_END \
 125             if (Xrn->l) { \
 126                 if (Xrn->r) { \
 127                     *Xsp++ = Xrn->r; \
 128                 } \
 129                 Xrn = Xrn->l; \
 130             } else if (Xrn->r) { \
 131                 Xrn = Xrn->r; \
 132             } else if (Xsp != Xstack) { \
 133                 Xrn = *(--Xsp); \
 134             } else { \
 135                 Xrn = (rb_patricia_node_t *) 0; \
 136             } \
 137         } \
 138     } while (0)
 139
 140 #endif /* _RB_PATRICIA_H */