#ifndef _PATRICIA_H
#define _PATRICIA_H
-#include "irc_ipv6.h"
+#include "../lib/irc_ipv6.h"
typedef unsigned short u_short;
typedef unsigned int u_int;
/* { from defs.h */
#define prefix_touchar(prefix) ((u_char *)&(prefix)->sin)
#define MAXLINE 1024
-#define BIT_TEST(f, b) ((f) & (b))
/* } */
#include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
/* { from mrt.h */
-#define PATRICIA_MAXSLOTS 5
+#define PATRICIA_MAXSLOTS 7
+
typedef struct _prefix_t {
u_short bitlen; /* same as mask? */
struct irc_in_addr sin;
} prefix_t;
+union prefixes {
+ struct _prefix_t prefix;
+ union prefixes *next;
+};
+
/* } */
typedef struct _patricia_node_t {
int num_active_node; /* for debug purpose */
} patricia_tree_t;
+extern patricia_tree_t *iptree;
prefix_t *patricia_new_prefix (struct irc_in_addr *dest, int bitlen);
prefix_t * patricia_ref_prefix (prefix_t * prefix);
void patricia_destroy_tree (patricia_tree_t *patricia, void_fn_t func);
void patricia_process (patricia_tree_t *patricia, void_fn_t func);
+patricia_node_t *patricia_new_node(patricia_tree_t *patricia, unsigned char bit,prefix_t *prefix);
+
+int registernodeext(const char *name);
+int findnodeext(const char *name);
+void releasenodeext(int index);
+
+void node_increment_usercount( patricia_node_t *node);
+void node_decrement_usercount( patricia_node_t *node);
+int is_normalized_ipmask( struct irc_in_addr *sin, unsigned char bitlen );
+
+/* alloc */
+void freeprefix (prefix_t *prefix);
+prefix_t *newprefix();
+patricia_node_t *newnode();
+void freenode (patricia_node_t *node);
+
/* } */
patricia_node_t *refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen);
void derefnode(patricia_tree_t *tree, patricia_node_t *node);
-#define PATRICIA_MAXBITS 128
-#define PATRICIA_NBYTE(x) ((x) >> 3)
+#define get_byte_for_bit(base, nr) (base)[(nr) >> 3]
+#define bigendian_bitfor(nr) (0x80 >> ((nr) & 0x07))
+#define is_bit_set(base, nr) (get_byte_for_bit(base, nr) & bigendian_bitfor(nr))
-/*#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
-#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))*/
+#define PATRICIA_MAXBITS 128
#define PATRICIA_WALK(Xhead, Xnode) \
do { \
} \
} while (0)
+#define PATRICIA_WALK_CLEAR(Xhead, Xnode) \
+ patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
+ patricia_node_t **Xsp = Xstack; \
+ patricia_node_t *Xrn = (Xhead); \
+ while ((Xnode = Xrn)) { \
+ patricia_node_t *l = Xrn->l; \
+ patricia_node_t *r = Xrn->r; \
+
+#define PATRICIA_WALK_CLEAR_END \
+ if (l) { \
+ if (r) { \
+ *Xsp++ = r; \
+ } \
+ Xrn = l; \
+ } else if (r) { \
+ Xrn = r; \
+ } else if (Xsp != Xstack) { \
+ Xrn = *(--Xsp); \
+ } else { \
+ Xrn = (patricia_node_t *) 0; \
+ } \
+ }
+
#endif /* _PATRICIA_H */