include/patricia.h

   1 /*
   2  * $Id: patricia.h 22407 2006-05-07 15:39:43Z 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 _PATRICIA_H
  16 #define _PATRICIA_H
  17 #include <stdlib.h>
  18 #include <string.h>
  19 #include <sys/types.h>
  20 #include <netinet/in.h>
  21 #include <arpa/inet.h>
  22 #include <assert.h>
  23 #ifndef TESTING
  24 #include "class.h"
  25 #include "client.h"
  26 #include "common.h"
  27 #include "irc_string.h"
  28 #include "ircd.h"
  29 #include "numeric.h"
  30 #include "send.h"
  31 #include "memory.h"
  32 #include "config.h"
  33 #endif
  34
  35
  36 #ifndef FALSE
  37 #define FALSE 0
  38 #endif
  39 #ifndef TRUE
  40 #define TRUE !(FALSE)
  41 #endif
  42 #ifndef INET6_ADDRSTRLEN
  43 #define INET6_ADDRSTRLEN 46
  44 #endif
  45
  46 /* typedef unsigned int uint; */
  47 typedef void (*void_fn_t) ();
  48 #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
  49 #define MAXLINE 1024
  50 #define BIT_TEST(f, b)  ((f) & (b))
  51
  52 #include <netinet/in.h>
  53 #include <sys/socket.h>
  54
  55 typedef struct _prefix_t
  56 {
  57         u_short family;         /* AF_INET | AF_INET6 */
  58         u_short bitlen;         /* same as mask? */
  59         int ref_count;          /* reference count */
  60         union
  61         {
  62                 struct in_addr sin;
  63 #ifdef IPV6
  64                 struct in6_addr sin6;
  65 #endif                          /* IPV6 */
  66         }
  67         add;
  68 }
  69 prefix_t;
  70
  71
  72 typedef struct _patricia_node_t
  73 {
  74         unsigned int bit;               /* flag if this node used */
  75         prefix_t *prefix;       /* who we are in patricia tree */
  76         struct _patricia_node_t *l, *r; /* left and right children */
  77         struct _patricia_node_t *parent;        /* may be used */
  78         void *data;
  79 }
  80 patricia_node_t;
  81
  82 typedef struct _patricia_tree_t
  83 {
  84         patricia_node_t *head;
  85         unsigned int maxbits;           /* for IP, 32 bit addresses */
  86         int num_active_node;    /* for debug purpose */
  87 }
  88 patricia_tree_t;
  89
  90
  91 patricia_node_t *match_ip(patricia_tree_t * tree, struct sockaddr  *ip);
  92 patricia_node_t *match_string(patricia_tree_t * tree, const char *string);
  93 patricia_node_t *match_exact_string(patricia_tree_t * tree, const char *string);
  94 patricia_node_t *patricia_search_exact(patricia_tree_t * patricia, prefix_t * prefix);
  95 patricia_node_t *patricia_search_best(patricia_tree_t * patricia, prefix_t * prefix);
  96 patricia_node_t *patricia_search_best2(patricia_tree_t * patricia,
  97                                        prefix_t * prefix, int inclusive);
  98 patricia_node_t *patricia_lookup(patricia_tree_t * patricia, prefix_t * prefix);
  99
 100 void patricia_remove(patricia_tree_t * patricia, patricia_node_t * node);
 101 patricia_tree_t *New_Patricia(int maxbits);
 102 void Clear_Patricia(patricia_tree_t * patricia, void_fn_t func);
 103 void Destroy_Patricia(patricia_tree_t * patricia, void_fn_t func);
 104 void patricia_process(patricia_tree_t * patricia, void_fn_t func);
 105 void init_patricia(void);
 106
 107
 108 #if 0
 109 prefix_t *ascii2prefix(int family, char *string);
 110 #endif
 111 patricia_node_t *make_and_lookup(patricia_tree_t * tree, const char *string);
 112 patricia_node_t *make_and_lookup_ip(patricia_tree_t * tree, struct sockaddr *, int bitlen);
 113
 114
 115 #define PATRICIA_MAXBITS 128
 116 #define PATRICIA_NBIT(x)        (0x80 >> ((x) & 0x7f))
 117 #define PATRICIA_NBYTE(x)       ((x) >> 3)
 118
 119 #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
 120 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
 121
 122 #define PATRICIA_WALK(Xhead, Xnode) \
 123     do { \
 124         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 125         patricia_node_t **Xsp = Xstack; \
 126         patricia_node_t *Xrn = (Xhead); \
 127         while ((Xnode = Xrn)) { \
 128             if (Xnode->prefix)
 129
 130 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
 131 do { \
 132         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 133         patricia_node_t **Xsp = Xstack; \
 134         patricia_node_t *Xrn = (Xhead); \
 135         while ((Xnode = Xrn)) { \
 136             if (1)
 137
 138 #define PATRICIA_WALK_BREAK { \
 139             if (Xsp != Xstack) { \
 140                 Xrn = *(--Xsp); \
 141              } else { \
 142                 Xrn = (patricia_node_t *) 0; \
 143             } \
 144             continue; }
 145
 146 #define PATRICIA_WALK_END \
 147             if (Xrn->l) { \
 148                 if (Xrn->r) { \
 149                     *Xsp++ = Xrn->r; \
 150                 } \
 151                 Xrn = Xrn->l; \
 152             } else if (Xrn->r) { \
 153                 Xrn = Xrn->r; \
 154             } else if (Xsp != Xstack) { \
 155                 Xrn = *(--Xsp); \
 156             } else { \
 157                 Xrn = (patricia_node_t *) 0; \
 158             } \
 159         } \
 160     } while (0)
 161
 162 #endif /* _PATRICIA_H */