1 #ifdef __cplusplus
2 extern "C" {
3 #endif
4 #include "EXTERN.h"
5 #include "perl.h"
6 #include "XSUB.h"
7 #ifdef __cplusplus
8 }
9 #endif
10
11 #include <sys/types.h>
12 #include <stdint.h>
13 #include <netinet/in.h>
14 #include "libpatricia/patricia.h"
15
16 /* frozen stuff is frozen in network byte order */
17 struct frozen_node
18 {
19 int32_t l_index;
20 int32_t r_index;
21 int32_t d_index;
22 uint16_t bitlen; /* bit 0x8000 indicates presence of prefix */
23 uint16_t family;
24 uint8_t address[16];
25 } __attribute__((__packed__));
26
27 struct frozen_header
28 {
29 uint32_t magic;
30 #define FROZEN_MAGIC 0x4E655061 /* NePa */
31 uint8_t major;
32 #define FROZEN_MAJOR 0
33 uint8_t minor;
34 #define FROZEN_MINOR 0
35 uint16_t maxbits;
36 int32_t num_total_node;
37 int32_t num_active_node;
38 } __attribute__((__packed__));
39
40 struct frozen_patricia
41 {
42 struct frozen_header header;
43 struct frozen_node node[1];
44 } __attribute__((__packed__));
45
46 static int
not_here(s)47 not_here(s)
48 char *s;
49 {
50 croak("%s not implemented on this architecture", s);
51 return -1;
52 }
53
54 static double
constant(name,arg)55 constant(name, arg)
56 char *name;
57 int arg;
58 {
59 errno = 0;
60 switch (*name) {
61 case 'A':
62 break;
63 case 'B':
64 break;
65 case 'C':
66 break;
67 case 'D':
68 break;
69 case 'E':
70 break;
71 case 'F':
72 break;
73 case 'G':
74 break;
75 case 'H':
76 break;
77 case 'I':
78 break;
79 case 'J':
80 break;
81 case 'K':
82 break;
83 case 'L':
84 break;
85 case 'M':
86 break;
87 case 'N':
88 break;
89 case 'O':
90 break;
91 case 'P':
92 break;
93 case 'Q':
94 break;
95 case 'R':
96 break;
97 case 'S':
98 break;
99 case 'T':
100 break;
101 case 'U':
102 break;
103 case 'V':
104 break;
105 case 'W':
106 break;
107 case 'X':
108 break;
109 case 'Y':
110 break;
111 case 'Z':
112 break;
113 case 'a':
114 break;
115 case 'b':
116 break;
117 case 'c':
118 break;
119 case 'd':
120 break;
121 case 'e':
122 break;
123 case 'f':
124 break;
125 case 'g':
126 break;
127 case 'h':
128 break;
129 case 'i':
130 break;
131 case 'j':
132 break;
133 case 'k':
134 break;
135 case 'l':
136 break;
137 case 'm':
138 break;
139 case 'n':
140 break;
141 case 'o':
142 break;
143 case 'p':
144 break;
145 case 'q':
146 break;
147 case 'r':
148 break;
149 case 's':
150 break;
151 case 't':
152 break;
153 case 'u':
154 break;
155 case 'v':
156 break;
157 case 'w':
158 break;
159 case 'x':
160 break;
161 case 'y':
162 break;
163 case 'z':
164 break;
165 }
166 errno = EINVAL;
167 return 0;
168
169 not_there:
170 errno = ENOENT;
171 return 0;
172 }
173
174 #define Fill_Prefix(p,f,a,b,mb) \
175 do { \
176 if (b < 0 || b > mb) \
177 croak("invalid key"); \
178 memcpy(&p.add.sin, a, (mb+7)/8); \
179 p.family = f; \
180 p.bitlen = b; \
181 p.ref_count = 0; \
182 } while (0)
183
deref_data(SV * data)184 static void deref_data(SV *data) {
185 SvREFCNT_dec(data);
186 data = NULL;
187 }
188
189 static size_t
patricia_walk_inorder_perl(patricia_node_t * node,SV * coderef)190 patricia_walk_inorder_perl(patricia_node_t *node, SV *coderef) {
191 dSP;
192 size_t n = 0;
193
194 if (node->l) {
195 n += patricia_walk_inorder_perl(node->l, coderef);
196 }
197
198 if (node->prefix) {
199 if (NULL != coderef) {
200 PUSHMARK(SP);
201 XPUSHs(sv_mortalcopy((SV *)node->data));
202 PUTBACK;
203 perl_call_sv(coderef, G_VOID|G_DISCARD);
204 SPAGAIN;
205 }
206 n++;
207 }
208
209 if (node->r) {
210 n += patricia_walk_inorder_perl(node->r, coderef);
211 }
212
213 return n;
214 }
215
216 typedef patricia_tree_t *Net__Patricia;
217 typedef patricia_node_t *Net__PatriciaNode;
218
219 MODULE = Net::Patricia PACKAGE = Net::Patricia
220
221 PROTOTYPES: ENABLE
222
223 double
224 constant(name,arg)
225 char * name
226 int arg
227
228 Net::Patricia
229 _new(size)
230 int size
231 CODE:
232 RETVAL = New_Patricia(size);
233 OUTPUT:
234 RETVAL
235
236 void
237 _add(tree, family, addr, bits, data)
238 Net::Patricia tree
239 int family
240 char * addr
241 int bits
242 SV * data
243 PROTOTYPE: $$$$$
244 PREINIT:
245 prefix_t prefix;
246 Net__PatriciaNode node;
247 PPCODE:
248 Fill_Prefix(prefix, family, addr, bits, tree->maxbits);
249 node = patricia_lookup(tree, &prefix);
250 if (NULL != node) {
251 /* { */
252 if (node->data) {
253 deref_data(node->data);
254 }
255 node->data = newSVsv(data);
256 /* } */
257 PUSHs(data);
258 } else {
259 XSRETURN_UNDEF;
260 }
261
262 void
263 _match(tree, family, addr, bits)
264 Net::Patricia tree
265 int family
266 char * addr
267 int bits
268 PROTOTYPE: $$$$
269 PREINIT:
270 prefix_t prefix;
271 Net__PatriciaNode node;
272 PPCODE:
273 Fill_Prefix(prefix, family, addr, bits, tree->maxbits);
274 node = patricia_search_best(tree, &prefix);
275 if (NULL != node) {
276 XPUSHs((SV *)node->data);
277 } else {
278 XSRETURN_UNDEF;
279 }
280
281 void
282 _exact(tree, family, addr, bits)
283 Net::Patricia tree
284 int family
285 char * addr
286 int bits
287 PROTOTYPE: $$$$
288 PREINIT:
289 prefix_t prefix;
290 Net__PatriciaNode node;
291 PPCODE:
292 Fill_Prefix(prefix, family, addr, bits, tree->maxbits);
293 node = patricia_search_exact(tree, &prefix);
294 if (NULL != node) {
295 XPUSHs((SV *)node->data);
296 } else {
297 XSRETURN_UNDEF;
298 }
299
300
301 void
302 _remove(tree, family, addr, bits)
303 Net::Patricia tree
304 int family
305 char * addr
306 int bits
307 PROTOTYPE: $$$$
308 PREINIT:
309 prefix_t prefix;
310 Net__PatriciaNode node;
311 PPCODE:
312 Fill_Prefix(prefix, family, addr, bits, tree->maxbits);
313 node = patricia_search_exact(tree, &prefix);
314 if (NULL != node) {
315 XPUSHs(sv_mortalcopy((SV *)node->data));
316 deref_data(node->data);
317 patricia_remove(tree, node);
318 } else {
319 XSRETURN_UNDEF;
320 }
321
322 size_t
323 climb(tree, ...)
324 Net::Patricia tree
325 PREINIT:
326 patricia_node_t *node = NULL;
327 size_t n = 0;
328 SV *func = NULL;
329 CODE:
330 if (2 == items) {
331 func = ST(1);
332 } else if (2 < items) {
333 croak("Usage: Net::Patricia::climb(tree[,CODEREF])");
334 }
335 PATRICIA_WALK (tree->head, node) {
336 if (NULL != func) {
337 PUSHMARK(SP);
338 XPUSHs(sv_mortalcopy((SV *)node->data));
339 PUTBACK;
340 perl_call_sv(func, G_VOID|G_DISCARD);
341 SPAGAIN;
342 }
343 n++;
344 } PATRICIA_WALK_END;
345 RETVAL = n;
346 OUTPUT:
347 RETVAL
348
349 size_t
350 climb_inorder(tree, ...)
351 Net::Patricia tree
352 PREINIT:
353 size_t n = 0;
354 SV *func = NULL;
355 CODE:
356 func = NULL;
357 if (2 == items) {
358 func = ST(1);
359 } else if (2 < items) {
360 croak("Usage: Net::Patricia::climb_inorder(tree[,CODEREF])");
361 }
362 n = patricia_walk_inorder_perl(tree->head, func);
363 RETVAL = n;
364 OUTPUT:
365 RETVAL
366
367 void
368 STORABLE_freeze(tree, cloning)
369 Net::Patricia tree
370 SV * cloning
371 PREINIT:
372 patricia_node_t *node = NULL;
373 struct frozen_header frozen_header;
374 struct frozen_node *frozen_nodes, *frozen_node;
375 size_t n = 0, i = 0, nd = 0;
376 SV *frozen_patricia;
377 PPCODE:
378 if (SvTRUE(cloning))
379 XSRETURN_UNDEF;
380
381 /* I do not know enough of patricia.c to
382 * decide whether inactive nodes can
383 * be present in a tree, and whether such
384 * nodes can be skipped while copying,
385 * so we copy everything and do not use
386 * num_active_node here. */
387 PATRICIA_WALK_ALL (tree->head, node) {
388 n++;
389 } PATRICIA_WALK_END;
390
391 if (n > 2147483646)
392 croak("Net::Patricia::STORABLE_freeze: too many nodes");
393
394 frozen_header.magic = htonl(FROZEN_MAGIC);
395 frozen_header.major = FROZEN_MAJOR;
396 frozen_header.minor = FROZEN_MINOR;
397 frozen_header.maxbits = htons((uint16_t)tree->maxbits);
398 frozen_header.num_total_node = htonl(n);
399 frozen_header.num_active_node = htonl(tree->num_active_node);
400
401 frozen_patricia = newSVpv((char *)&frozen_header, sizeof(frozen_header));
402 XPUSHs(frozen_patricia);
403
404 frozen_nodes = calloc(n, sizeof(struct frozen_node));
405
406 /* We use user1 field to store the index of each node
407 * in the frozen_node array; it is okay since Net::Patricia
408 * is not using it for anything anywhere else */
409 PATRICIA_WALK_ALL (tree->head, node) {
410 node->user1 = (void *)(IV)i;
411
412 frozen_node = &frozen_nodes[i];
413 frozen_node->l_index = htonl(-1);
414 frozen_node->r_index = htonl(-1);
415 frozen_node->bitlen = node->bit;
416 if (node->prefix) {
417 frozen_node->bitlen |= 0x8000;
418 frozen_node->family = htons(node->prefix->family);
419 if (tree->maxbits == 32)
420 memcpy(&frozen_node->address, &node->prefix->add, 4);
421 else
422 memcpy(&frozen_node->address, &node->prefix->add, 16);
423 }
424 frozen_node->bitlen = htons(frozen_node->bitlen);
425
426 if (node->data) {
427 frozen_node->d_index = htonl(nd);
428 nd++;
429 XPUSHs(sv_2mortal(newRV_inc((SV *)node->data)));
430 } else {
431 frozen_node->d_index = htonl(-1);
432 }
433 if (node->parent && node->parent->l == node) {
434 frozen_nodes[(IV)node->parent->user1].l_index = htonl(i);
435 } else if (node->parent && node->parent->r == node) {
436 frozen_nodes[(IV)node->parent->user1].r_index = htonl(i);
437 }
438 i++;
439 } PATRICIA_WALK_END;
440
441 sv_catpvn(frozen_patricia, (char*)frozen_nodes, n*sizeof(struct frozen_node));
442 free(frozen_nodes);
443
444 void
445 STORABLE_thaw(tobj, cloning, serialized, ...)
446 SV * tobj
447 SV * cloning
448 SV * serialized;
449 PREINIT:
450 struct frozen_patricia *frozen_patricia;
451 struct frozen_node *frozen_node;
452 struct _patricia_tree_t *tree;
453 patricia_node_t *node = NULL, *child, **fixup;
454 int n, n_calculated, i, d_index, l_index, r_index;
455 STRLEN len;
456 PPCODE:
457 if (SvTRUE(cloning))
458 XSRETURN_UNDEF;
459
460 tree = calloc(1, sizeof(*tree));
461 frozen_patricia = (struct frozen_patricia*)SvPV(serialized, len);
462
463 if (ntohl(frozen_patricia->header.magic) != FROZEN_MAGIC)
464 croak("Net::Patricia::STORABLE_thaw: magic mismatch");
465 if (frozen_patricia->header.major != FROZEN_MAJOR)
466 croak("Net::Patricia::STORABLE_thaw: major mismatch");
467 if (frozen_patricia->header.minor != FROZEN_MINOR)
468 croak("Net::Patricia::STORABLE_thaw: minor mismatch");
469
470 tree->maxbits = ntohs(frozen_patricia->header.maxbits);
471 tree->num_active_node = ntohl(frozen_patricia->header.num_active_node);
472 tree->head = NULL;
473
474 n = ntohl(frozen_patricia->header.num_total_node);
475 n_calculated = (len - sizeof(frozen_patricia->header)) / sizeof(struct frozen_node);
476 if (n_calculated < n)
477 croak("Net::Patricia::STORABLE_thaw: size mismatch");
478 fixup = calloc(n, sizeof(patricia_node_t *));
479
480 for (i = 0; i < n; i++) {
481 node = calloc(1, sizeof(*node));
482 memset(node, 0, sizeof(*node));
483 frozen_node = &frozen_patricia->node[i];
484
485 node->bit = ntohs(frozen_node->bitlen) & ~0x8000;
486 d_index = ntohl(frozen_node->d_index);
487 if (d_index >= 0)
488 node->data = newSVsv(SvRV(ST(3+d_index)));
489
490 if (ntohs(frozen_node->bitlen) & 0x8000) {
491 node->prefix = calloc(1, sizeof(*node->prefix));
492 node->prefix->bitlen = node->bit;
493 node->prefix->family = ntohs(frozen_node->family);
494 #ifndef HAVE_IPV6
495 if (tree->maxbits > 32)
496 croak("Net::Patricia::STORABLE_thaw: IPv6 is not supported by Net::Patricia on this machine");
497 #endif
498 if (tree->maxbits == 32) {
499 memcpy(&node->prefix->add, &frozen_node->address, 4);
500 } else
501 memcpy(&node->prefix->add, &frozen_node->address, 16);
502 node->prefix->ref_count = 1;
503 }
504 fixup[i] = node;
505 }
506
507 /* Fix pointers up. */
508 if (n)
509 tree->head = fixup[0];
510 for (i = 0; i < n; i++) {
511 frozen_node = &frozen_patricia->node[i];
512 node = fixup[i];
513
514 l_index = ntohl(frozen_node->l_index);
515 if (l_index >= 0) {
516 child = fixup[l_index];
517 child->parent = node;
518 node->l = child;
519 }
520
521 r_index = ntohl(frozen_node->r_index);
522 if (r_index >= 0) {
523 child = fixup[r_index];
524 child->parent = node;
525 node->r = child;
526 }
527 }
528
529 free(fixup);
530 sv_setiv((SV*)SvRV(tobj), PTR2IV(tree));
531 XSRETURN_EMPTY;
532
533 void
534 DESTROY(tree)
535 Net::Patricia tree
536 CODE:
537 Destroy_Patricia(tree, deref_data);
538