| Subject: | Function to return all matching records |
I've attached a patch to add match_all and match_all_string functions to
Net::Patricia. These work identically to match and match_string, only
they return all matching records.
If there's any interest in applying this upstream, I'm willing to finish
it off (it needs POD and IPv4 tests).
| Subject: | match_all.patch |
diff -Naur Net-Patricia-1.19-orig/libpatricia/patricia.c Net-Patricia-1.19/libpatricia/patricia.c
--- Net-Patricia-1.19-orig/libpatricia/patricia.c 2011-03-05 15:03:56.000000000 +0000
+++ Net-Patricia-1.19/libpatricia/patricia.c 2011-03-07 14:25:11.000000000 +0000
@@ -523,14 +523,17 @@
/* if inclusive != 0, "best" may be the given prefix itself */
+/* optional out argument 'parents' will be an array of parent node objects */
patricia_node_t *
-patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
+patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, patricia_node_t ***parents, int *num_parents,
+ int inclusive)
{
patricia_node_t *node;
patricia_node_t *stack[PATRICIA_MAXBITS + 1];
u_char *addr;
u_int bitlen;
int cnt = 0;
+ int i;
assert (patricia);
assert (prefix);
@@ -609,6 +612,16 @@
fprintf (stderr, "patricia_search_best: found %s/%d\n",
prefix_toa (node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
+ if (num_parents != NULL)
+ *num_parents = cnt;
+ if (parents != NULL && cnt > 0) {
+ *parents = malloc(sizeof(patricia_node_t *) * (cnt));
+ if (*parents != NULL) {
+ for (i = 0; i < cnt; i++) {
+ (*parents)[i] = stack[i];
+ }
+ }
+ }
return (node);
}
}
@@ -619,9 +632,14 @@
patricia_node_t *
patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix)
{
- return (patricia_search_best2 (patricia, prefix, 1));
+ return (patricia_search_best2 (patricia, prefix, NULL, NULL, 1));
}
+patricia_node_t *
+patricia_search_parents (patricia_tree_t *patricia, prefix_t *prefix, patricia_node_t ***parents, int *num_parents)
+{
+ return patricia_search_best2 (patricia, prefix, parents, num_parents, 1);
+}
patricia_node_t *
patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
diff -Naur Net-Patricia-1.19-orig/libpatricia/patricia.h Net-Patricia-1.19/libpatricia/patricia.h
--- Net-Patricia-1.19-orig/libpatricia/patricia.h 2011-03-05 15:03:56.000000000 +0000
+++ Net-Patricia-1.19/libpatricia/patricia.h 2011-03-07 14:26:23.000000000 +0000
@@ -80,8 +80,10 @@
patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix);
patricia_node_t *patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix);
-patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix,
- int inclusive);
+patricia_node_t * patricia_search_parents (patricia_tree_t *patricia, prefix_t *prefix,
+ patricia_node_t ***parents, int *num_parents);
+patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix,
+ patricia_node_t ***parents, int *num_parents, int inclusive);
patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
patricia_tree_t *New_Patricia (int maxbits);
diff -Naur Net-Patricia-1.19-orig/Patricia.pm Net-Patricia-1.19/Patricia.pm
--- Net-Patricia-1.19-orig/Patricia.pm 2011-03-05 15:03:56.000000000 +0000
+++ Net-Patricia-1.19/Patricia.pm 2011-03-05 15:50:07.000000000 +0000
@@ -87,6 +87,12 @@
$self->match($self->_ip_bits($str))
}
+sub match_all_string {
+ croak "match_string: wrong number of args" if (@_ != 2);
+ my ($self,$str) = @_;
+ $self->match_all($self->_ip_bits($str))
+}
+
sub match_exact_string {
croak "match_exact_string: wrong number of args" if (@_ != 2);
my ($self,$str) = @_;
@@ -198,6 +204,15 @@
$self->SUPER::_match(AF_INET, $packed, $bits);
}
+sub match_all {
+ croak "match: wrong number of args" if (@_ < 2 || @_ > 3);
+ my ($self, $ip, $bits) = @_;
+ my $packed = inet_aton($ip);
+ croak("invalid key") unless (defined $packed);
+ $bits = 32 if (@_ < 3);
+ $self->SUPER::_match_all(AF_INET, $packed, $bits);
+}
+
sub exact {
croak "exact: wrong number of args" if (@_ < 2 || @_ > 3);
my ($self, $ip, $bits) = @_;
@@ -285,6 +300,15 @@
$self->SUPER::_match(AF_INET6, $packed, $bits);
}
+sub match_all {
+ croak "match: wrong number of args" if (@_ < 2 || @_ > 3);
+ my ($self, $ip, $bits) = @_;
+ my $packed = inet_pton(AF_INET6, $ip);
+ croak("invalid key") unless (defined $packed);
+ $bits = 128 if (@_ < 3);
+ $self->SUPER::_match_all(AF_INET6, $packed, $bits);
+}
+
sub exact {
croak "exact: wrong number of args" if (@_ < 2 || @_ > 3);
my ($self, $ip, $bits) = @_;
diff -Naur Net-Patricia-1.19-orig/Patricia.xs Net-Patricia-1.19/Patricia.xs
--- Net-Patricia-1.19-orig/Patricia.xs 2011-03-05 15:03:56.000000000 +0000
+++ Net-Patricia-1.19/Patricia.xs 2011-03-07 14:38:25.000000000 +0000
@@ -246,6 +246,34 @@
}
void
+_match_all(tree, family, addr, bits)
+ Net::Patricia tree
+ int family
+ char * addr
+ int bits
+ PROTOTYPE: $$$$
+ PREINIT:
+ prefix_t prefix;
+ Net__PatriciaNode node;
+ Net__PatriciaNode *parents;
+ int num_parents;
+ int i;
+ PPCODE:
+ Fill_Prefix(prefix, family, addr, bits, tree->maxbits);
+ node = patricia_search_parents(tree, &prefix, &parents, &num_parents);
+ if (NULL != node) {
+ if (parents == NULL)
+ croak("out of memory, could not allocate storage for parents");
+
+ if (num_parents > 0) {
+ for (i = 0; i < num_parents; i++)
+ XPUSHs((SV *)parents[i]->data);
+ free(parents);
+ }
+ XPUSHs((SV *)node->data);
+ }
+
+void
_exact(tree, family, addr, bits)
Net::Patricia tree
int family
diff -Naur Net-Patricia-1.19-orig/t/02match_all.t Net-Patricia-1.19/t/02match_all.t
--- Net-Patricia-1.19-orig/t/02match_all.t 1970-01-01 01:00:00.000000000 +0100
+++ Net-Patricia-1.19/t/02match_all.t 2011-03-07 13:08:50.000000000 +0000
@@ -0,0 +1,45 @@
+use strict;
+use warnings;
+use Test::More tests => 8;
+use Net::Patricia;
+use Socket;
+
+my $tree = Net::Patricia->new(AF_INET6);
+can_ok($tree, 'match_all_string')
+ or BAIL_OUT('No method match_all_string');
+
+sub test {
+ my ($query, $expected_result, $message) = @_;
+ my @result = $tree->match_all_string($query);
+ is_deeply(\@result, $expected_result, $message);
+}
+
+test('::', [], 'lookup against no data');
+
+$tree->add_string('::/0', 'root');
+test('::', ['root'], 'lookup against root zone');
+
+$tree->add_string('2001::/16', '/16');
+$tree->add_string('2001:51a:ff::/48', '/48');
+
+test('::', ['root'], 'root lookup');
+test('2001:51a:ff::1', ['root', '/16', '/48'], 'general lookup');
+test('2001:b::', ['root', '/16'], 'less general lookup');
+
+$tree->add_string('2001:51a:ff::1');
+test('2001:51a:ff::1', ['root', '/16', '/48', '2001:51a:ff::1'], 'exact IP match');
+
+# Reset and try a more complex example
+$tree = Net::Patricia->new(AF_INET6);
+
+$tree->add_string('::/0');
+$tree->add_string('2800::/12');
+$tree->add_string('2a00::/12');
+$tree->add_string('2a00::/22');
+$tree->add_string('2a00:1000::/32');
+$tree->add_string('2a00:1400::/48');
+$tree->add_string('2a00:1440::/32');
+$tree->add_string('2a00:1450::/32');
+
+test('2a00:1450:8002::6a', ['::/0', '2a00::/12', '2a00:1450::/32']);
+