libratbox/include/rb_patricia.h

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