patricia/patricia.h

   1 /*
   2  * $Id: patricia.h,v 1.6 2005/12/07 20:53:01 dplonka Exp $
   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
  18 #include "../lib/irc_ipv6.h"
  19
  20 typedef unsigned short u_short;
  21 typedef unsigned int u_int;
  22 typedef unsigned char u_char;
  23
  24 /* typedef unsigned int u_int; */
  25 typedef void (*void_fn_t)();
  26 /* { from defs.h */
  27 #define prefix_touchar(prefix) ((u_char *)&(prefix)->sin)
  28 #define MAXLINE 1024
  29 /* } */
  30
  31 #include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
  32
  33 #include <errno.h> /* for EAFNOSUPPORT */
  34 #ifndef EAFNOSUPPORT
  35 #  defined EAFNOSUPPORT WSAEAFNOSUPPORT
  36 #  include <winsock.h>
  37 #else
  38 #  include <netinet/in.h> /* for struct in_addr */
  39 #endif
  40
  41 #include <sys/socket.h> /* for AF_INET */
  42
  43 /* { from mrt.h */
  44
  45 #define PATRICIA_MAXSLOTS 5
  46
  47
  48 typedef struct _prefix_t {
  49     u_short bitlen;             /* same as mask? */
  50     int ref_count;              /* reference count */
  51     struct irc_in_addr sin;
  52 } prefix_t;
  53
  54 union prefixes {
  55   struct _prefix_t prefix;
  56   union prefixes *next;
  57 };
  58
  59 /* } */
  60
  61 typedef struct _patricia_node_t {
  62    unsigned char bit;           /* flag if this node used */
  63    int usercount;               /* number of users on a given node */
  64    prefix_t *prefix;            /* who we are in patricia tree */
  65    struct _patricia_node_t *l, *r;      /* left and right children */
  66    struct _patricia_node_t *parent;/* may be used */
  67    void *exts[PATRICIA_MAXSLOTS];
  68 } patricia_node_t;
  69
  70 typedef struct _patricia_tree_t {
  71    patricia_node_t      *head;
  72    u_int                maxbits;        /* for IPv6, 128 bit addresses */
  73    int num_active_node;         /* for debug purpose */
  74 } patricia_tree_t;
  75
  76 extern patricia_tree_t *iptree;
  77
  78 prefix_t *patricia_new_prefix (struct irc_in_addr *dest, int bitlen);
  79 prefix_t * patricia_ref_prefix (prefix_t * prefix);
  80 void patricia_deref_prefix (prefix_t * prefix);
  81
  82 patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen);
  83 patricia_node_t *patricia_search_best (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen);
  84 patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen,
  85                                    int inclusive);
  86 patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
  87 void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
  88 patricia_tree_t *patricia_new_tree (int maxbits);
  89 void patricia_clear_tree (patricia_tree_t *patricia, void_fn_t func);
  90 void patricia_destroy_tree (patricia_tree_t *patricia, void_fn_t func);
  91 void patricia_process (patricia_tree_t *patricia, void_fn_t func);
  92
  93 patricia_node_t *patricia_new_node(patricia_tree_t *patricia, unsigned char bit,prefix_t *prefix);
  94
  95 int registernodeext(const char *name);
  96 int findnodeext(const char *name);
  97 void releasenodeext(int index);
  98
  99 /* alloc */
 100 void freeprefix (prefix_t *prefix);
 101 prefix_t *newprefix();
 102 patricia_node_t *newnode();
 103 void freenode (patricia_node_t *node);
 104
 105 /* } */
 106
 107 patricia_node_t *refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen);
 108 void derefnode(patricia_tree_t *tree, patricia_node_t *node);
 109
 110 #define get_byte_for_bit(base, nr) (base)[(nr) >> 3]
 111 #define bigendian_bitfor(nr) (0x80 >> ((nr) & 0x07))
 112 #define is_bit_set(base, nr) (get_byte_for_bit(base, nr) & bigendian_bitfor(nr))
 113
 114 #define PATRICIA_MAXBITS 128
 115
 116 #define PATRICIA_WALK(Xhead, Xnode) \
 117     do { \
 118         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 119         patricia_node_t **Xsp = Xstack; \
 120         patricia_node_t *Xrn = (Xhead); \
 121         while ((Xnode = Xrn)) { \
 122             if (Xnode->prefix)
 123
 124 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
 125 do { \
 126         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 127         patricia_node_t **Xsp = Xstack; \
 128         patricia_node_t *Xrn = (Xhead); \
 129         while ((Xnode = Xrn)) { \
 130             if (1)
 131
 132 #define PATRICIA_WALK_BREAK { \
 133             if (Xsp != Xstack) { \
 134                 Xrn = *(--Xsp); \
 135              } else { \
 136                 Xrn = (patricia_node_t *) 0; \
 137             } \
 138             continue; }
 139
 140 #define PATRICIA_WALK_END \
 141             if (Xrn->l) { \
 142                 if (Xrn->r) { \
 143                     *Xsp++ = Xrn->r; \
 144                 } \
 145                 Xrn = Xrn->l; \
 146             } else if (Xrn->r) { \
 147                 Xrn = Xrn->r; \
 148             } else if (Xsp != Xstack) { \
 149                 Xrn = *(--Xsp); \
 150             } else { \
 151                 Xrn = (patricia_node_t *) 0; \
 152             } \
 153         } \
 154     } while (0)
 155
 156 #endif /* _PATRICIA_H */