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    int usercount;               /* number of users on a given node */
  59    prefix_t *prefix;            /* who we are in patricia tree */
  60    struct _patricia_node_t *l, *r;      /* left and right children */
  61    struct _patricia_node_t *parent;/* may be used */
  62    void *exts[PATRICIA_MAXSLOTS];
  63 } patricia_node_t;
  64
  65 typedef struct _patricia_tree_t {
  66    patricia_node_t      *head;
  67    u_int                maxbits;        /* for IPv6, 128 bit addresses */
  68    int num_active_node;         /* for debug purpose */
  69 } patricia_tree_t;
  70
  71
  72 prefix_t *patricia_new_prefix (struct irc_in_addr *dest, int bitlen);
  73 prefix_t * patricia_ref_prefix (prefix_t * prefix);
  74 void patricia_deref_prefix (prefix_t * prefix);
  75
  76 patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen);
  77 patricia_node_t *patricia_search_best (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen);
  78 patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen,
  79                                    int inclusive);
  80 patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
  81 void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
  82 patricia_tree_t *patricia_new_tree (int maxbits);
  83 void patricia_clear_tree (patricia_tree_t *patricia, void_fn_t func);
  84 void patricia_destroy_tree (patricia_tree_t *patricia, void_fn_t func);
  85 void patricia_process (patricia_tree_t *patricia, void_fn_t func);
  86
  87 /* } */
  88
  89 patricia_node_t *refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen);
  90 void derefnode(patricia_tree_t *tree, patricia_node_t *node);
  91
  92 #define PATRICIA_MAXBITS 128
  93 #define PATRICIA_NBIT(x)        (0x80 >> ((x) & 0x7f))
  94 #define PATRICIA_NBYTE(x)       ((x) >> 3)
  95
  96 /*#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
  97 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))*/
  98
  99 #define PATRICIA_WALK(Xhead, Xnode) \
 100     do { \
 101         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 102         patricia_node_t **Xsp = Xstack; \
 103         patricia_node_t *Xrn = (Xhead); \
 104         while ((Xnode = Xrn)) { \
 105             if (Xnode->prefix)
 106
 107 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
 108 do { \
 109         patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
 110         patricia_node_t **Xsp = Xstack; \
 111         patricia_node_t *Xrn = (Xhead); \
 112         while ((Xnode = Xrn)) { \
 113             if (1)
 114
 115 #define PATRICIA_WALK_BREAK { \
 116             if (Xsp != Xstack) { \
 117                 Xrn = *(--Xsp); \
 118              } else { \
 119                 Xrn = (patricia_node_t *) 0; \
 120             } \
 121             continue; }
 122
 123 #define PATRICIA_WALK_END \
 124             if (Xrn->l) { \
 125                 if (Xrn->r) { \
 126                     *Xsp++ = Xrn->r; \
 127                 } \
 128                 Xrn = Xrn->l; \
 129             } else if (Xrn->r) { \
 130                 Xrn = Xrn->r; \
 131             } else if (Xsp != Xstack) { \
 132                 Xrn = *(--Xsp); \
 133             } else { \
 134                 Xrn = (patricia_node_t *) 0; \
 135             } \
 136         } \
 137     } while (0)
 138
 139 #endif /* _PATRICIA_H */