1#pragma once
2
3#if defined (__cplusplus)
4extern "C" {
5#endif
6
7#include <stdlib.h>
8#include <stdint.h>
9
10/**
11 * In btrie, each leaf means one bit in ip tree.
12 * Left means 0, and right means 1.
13 */
14
15#define BTRIE_NULL (uintptr_t) -1
16
17#if !defined(BTRIE_MAX_PAGES)
18/// 54 ip per page. 8 bytes memory per page when empty
19#define BTRIE_MAX_PAGES 1024 * 2048 /// 128m ips , ~16mb ram when empty
20// #define BTRIE_MAX_PAGES 1024 * 65535 /// 4g ips (whole ipv4), ~512mb ram when empty
21#endif
22
23typedef struct btrie_node_s btrie_node_t;
24
25struct btrie_node_s {
26 btrie_node_t *right;
27 btrie_node_t *left;
28 btrie_node_t *parent;
29 uintptr_t value;
30};
31
32
33typedef struct btrie_s {
34 btrie_node_t *root;
35
36 btrie_node_t *free; /* free list of btrie */
37 char *start;
38 size_t size;
39
40 /*
41 * memory pool.
42 * memory management(esp free) will be so easy by using this facility.
43 */
44 char *pools[BTRIE_MAX_PAGES];
45 size_t len;
46} btrie_t;
47
48
49/**
50 * Create an empty btrie
51 *
52 * @Return:
53 * An ip radix_tree created.
54 * NULL if creation failed.
55 */
56
57btrie_t *btrie_create();
58
59/**
60 * Destroy the ip radix_tree
61 *
62 * @Return:
63 * OK if deletion succeed.
64 * ERROR if error occurs while deleting.
65 */
66int btrie_destroy(btrie_t *tree);
67
68/**
69 * Count the nodes in the radix tree.
70 */
71size_t btrie_count(btrie_t *tree);
72
73/**
74 * Return the allocated number of bytes.
75 */
76size_t btrie_allocated(btrie_t *tree);
77
78
79/**
80 * Add an ipv4 into btrie
81 *
82 * @Args:
83 * key: ip address
84 * mask: key's mask
85 * value: value of this IP, may be NULL.
86 *
87 * @Return:
88 * OK for success.
89 * ERROR for failure.
90 */
91int btrie_insert(btrie_t *tree, uint32_t key, uint32_t mask,
92 uintptr_t value);
93
94
95/**
96 * Delete an ipv4 from btrie
97 *
98 * @Args:
99 *
100 * @Return:
101 * OK for success.
102 * ERROR for failure.
103 */
104int btrie_delete(btrie_t *tree, uint32_t key, uint32_t mask);
105
106
107/**
108 * Find an ipv4 from btrie
109 *
110
111 * @Args:
112 *
113 * @Return:
114 * Value if succeed.
115 * NULL if failed.
116 */
117uintptr_t btrie_find(btrie_t *tree, uint32_t key);
118
119
120/**
121 * Add an ipv6 into btrie
122 *
123 * @Args:
124 * key: ip address
125 * mask: key's mask
126 * value: value of this IP, may be NULL.
127 *
128 * @Return:
129 * OK for success.
130 * ERROR for failure.
131 */
132int btrie_insert_a6(btrie_t *tree, const uint8_t *key, const uint8_t *mask,
133 uintptr_t value);
134
135/**
136 * Delete an ipv6 from btrie
137 *
138 * @Args:
139 *
140 * @Return:
141 * OK for success.
142 * ERROR for failure.
143 */
144int btrie_delete_a6(btrie_t *tree, const uint8_t *key, const uint8_t *mask);
145
146/**
147 * Find an ipv6 from btrie
148 *
149
150 * @Args:
151 *
152 * @Return:
153 * Value if succeed.
154 * NULL if failed.
155 */
156uintptr_t btrie_find_a6(btrie_t *tree, const uint8_t *key);
157
158#if defined (__cplusplus)
159}
160#endif