1 | #pragma once |
2 | |
3 | #if defined (__cplusplus) |
4 | extern "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 | |
23 | typedef struct btrie_node_s btrie_node_t; |
24 | |
25 | struct 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 | |
33 | typedef 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 | |
57 | btrie_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 | */ |
66 | int btrie_destroy(btrie_t *tree); |
67 | |
68 | /** |
69 | * Count the nodes in the radix tree. |
70 | */ |
71 | size_t btrie_count(btrie_t *tree); |
72 | |
73 | /** |
74 | * Return the allocated number of bytes. |
75 | */ |
76 | size_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 | */ |
91 | int 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 | */ |
104 | int 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 | */ |
117 | uintptr_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 | */ |
132 | int 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 | */ |
144 | int 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 | */ |
156 | uintptr_t btrie_find_a6(btrie_t *tree, const uint8_t *key); |
157 | |
158 | #if defined (__cplusplus) |
159 | } |
160 | #endif |