lib/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 "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 #define BIT_TEST(f, b)  ((f) & (b))
  30 /* } */
  31
  32 #include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
  33
  34 #include <errno.h> /* for EAFNOSUPPORT */
  35 #ifndef EAFNOSUPPORT
  36 #  defined EAFNOSUPPORT WSAEAFNOSUPPORT
  37 #  include <winsock.h>
  38 #else
  39 #  include <netinet/in.h> /* for struct in_addr */
  40 #endif
  41
  42 #include <sys/socket.h> /* for AF_INET */
  43
  44 /* { from mrt.h */
  45
  46 #define PATRICIA_MAXSLOTS 5
  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 /* } */
  55
  56 typedef struct _patricia_node_t {
  57    unsigned char bit;           /* flag if this node used */
  58    prefix_t *prefix;            /* who we are in patricia tree */
  59    struct _patricia_node_t *l, *r;      /* left and right children */
  60    struct _patricia_node_t *parent;/* may be used */
  61     void **slots;
  62 } patricia_node_t;
  63
  64 typedef struct _patricia_tree_t {
  65    patricia_node_t      *head;
  66    u_int                maxbits;        /* for IPv6, 128 bit addresses */
  67    int num_active_node;         /* for debug purpose */
  68 } patricia_tree_t;
  69
  70
  71 prefix_t *patricia_new_prefix (struct irc_in_addr *dest, int bitlen);
  72 prefix_t * patricia_ref_prefix (prefix_t * prefix);
  73 void patricia_deref_prefix (prefix_t * prefix);
  74
  75 patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen);
  76 patricia_node_t *patricia_search_best (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen);
  77 patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen,
  78                                    int inclusive);
  79 patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
  80 void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
  81 patricia_tree_t *patricia_new_tree (int maxbits);
  82 void patricia_clear_tree (patricia_tree_t *patricia, void_fn_t func);
  83 void patricia_destroy_tree (patricia_tree_t *patricia, void_fn_t func);
  84 void patricia_process (patricia_tree_t *patricia, void_fn_t func);
  85
  86 /* } */
  87
  88 patricia_node_t *refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen);
  89 void derefnode(patricia_tree_t *tree, patricia_node_t *node);
  90
  91 #define PATRICIA_MAXBITS 128
  92 #define PATRICIA_NBIT(x)        (0x80 >> ((x) & 0x7f))
  93 #define PATRICIA_NBYTE(x)       ((x) >> 3)
  94
  95 /*#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
  96 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))*/
  97
  98 #define PATRICIA_WALK(Xhead, Xnode) \
  99     do { \
 100         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 101         patricia_node_t **Xsp = Xstack; \
 102         patricia_node_t *Xrn = (Xhead); \
 103         while ((Xnode = Xrn)) { \
 104             if (Xnode->prefix)
 105
 106 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
 107 do { \
 108         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 109         patricia_node_t **Xsp = Xstack; \
 110         patricia_node_t *Xrn = (Xhead); \
 111         while ((Xnode = Xrn)) { \
 112             if (1)
 113
 114 #define PATRICIA_WALK_BREAK { \
 115             if (Xsp != Xstack) { \
 116                 Xrn = *(--Xsp); \
 117              } else { \
 118                 Xrn = (patricia_node_t *) 0; \
 119             } \
 120             continue; }
 121
 122 #define PATRICIA_WALK_END \
 123             if (Xrn->l) { \
 124                 if (Xrn->r) { \
 125                     *Xsp++ = Xrn->r; \
 126                 } \
 127                 Xrn = Xrn->l; \
 128             } else if (Xrn->r) { \
 129                 Xrn = Xrn->r; \
 130             } else if (Xsp != Xstack) { \
 131                 Xrn = *(--Xsp); \
 132             } else { \
 133                 Xrn = (patricia_node_t *) 0; \
 134             } \
 135         } \
 136     } while (0)
 137
 138 #endif /* _PATRICIA_H */