patricia, trie: minor: do some cleanups
authorDaniel Borkmann <dborkman@redhat.com>
Mon, 28 Jan 2013 16:35:51 +0000 (28 17:35 +0100)
committerDaniel Borkmann <dborkman@redhat.com>
Mon, 28 Jan 2013 16:35:51 +0000 (28 17:35 +0100)
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
patricia.c
patricia.h
trie.c

index c56cea7..b58fa63 100644 (file)
 #include "built_in.h"
 #include "xmalloc.h"
 
-static unsigned char mbit[] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
+static const unsigned char mbit[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
 
 static inline int testbit(char *str, size_t slen, int bitplace)
 {
        int maskptr;
+
        if ((maskptr = bitplace >> 3) > slen)
                return 0;
+
        return (str[maskptr] & mbit[bitplace & 7]);
 }
 
@@ -31,46 +33,53 @@ static inline int testbit_max(char *str, int bitplace, int maxbitplace)
 {
        if (bitplace >= maxbitplace)
                return 0;
+
        return (str[bitplace >> 3] & mbit[bitplace & 7]);
 }
 
 static int where_the_bit_differ(char *str1, size_t l1, char *str2, size_t l2)
 {
        int p = 0, bitloc;
+
        while (str1[p] == str2[p])
                p++;
+
        bitloc = p * 8;
-       while (testbit(str1, l1, bitloc) ==
-              testbit(str2, l2, bitloc))
+
+       while (testbit(str1, l1, bitloc) == testbit(str2, l2, bitloc))
                bitloc++;
+
        return bitloc;
 }
 
 static struct patricia_node *new_node(void)
 {
        struct patricia_node *n = xzmalloc(sizeof(*n));
+
        n->l = n->r = NULL;
+
        return n;
 }
 
 static void free_node(struct patricia_node *n)
 {
-       if (n->key)
-               xfree(n->key);
-       if (n->addr)
-               xfree(n->addr);
+       free(n->key);
+       free(n->addr);
        xfree(n);
 }
 
 void ptree_display(struct patricia_node *node, int level)
 {
        int i;
+
        for (i = 0; i < level; ++i)
                printf("-");
+
        if (node->l == NULL && node->r == NULL)
                printf("leaf: (%s -> %d)\n", (char *) node->key, node->value.data);
        else {
                printf("thres: %d\n", node->value.thres_bit);
+
                if (node->l != NULL)
                        ptree_display(node->l, level + 1);
                if (node->r != NULL)
@@ -83,6 +92,7 @@ void ptree_get_key(int data, struct patricia_node *node,
 {
        if (!node)
                return;
+
        if (node->l == NULL && node->r == NULL) {
                if (node->value.data == data)
                        (*wanted) = node;
@@ -99,6 +109,7 @@ void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen,
 {
        if (!node)
                return;
+
        if (node->l == NULL && node->r == NULL) {
                if (!memcmp(node->addr, addr, node->alen))
                        (*wanted) = node;
@@ -110,22 +121,22 @@ void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen,
        }
 }
 
-static int ptree_search_data_r(struct patricia_node *node, char *str,
-                              size_t slen, struct sockaddr_storage *addr,
-                              size_t *alen, int maxbitplace)
+static int ptree_search_data_r(struct patricia_node *node, char *str, size_t slen,
+                              struct sockaddr_storage *addr, size_t *alen, int maxbitplace)
 {
        if (node->l == NULL && node->r == NULL) {
                if (node->addr && addr)
                        memcpy(addr, node->addr, node->alen);
+
                (*alen) = node->alen;
+
                return node->value.data;
        }
+
        if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0)
-               return ptree_search_data_r(node->r, str, slen, addr,
-                                          alen, maxbitplace);
+               return ptree_search_data_r(node->r, str, slen, addr, alen, maxbitplace);
        else
-               return ptree_search_data_r(node->l, str, slen, addr,
-                                          alen, maxbitplace);
+               return ptree_search_data_r(node->l, str, slen, addr, alen, maxbitplace);
 }
 
 static int *ptree_search_data_r_p(struct patricia_node *node, char *str,
@@ -133,6 +144,7 @@ static int *ptree_search_data_r_p(struct patricia_node *node, char *str,
 {
        if (node->l == NULL && node->r == NULL)
                return &(node->value.data);
+
        if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0)
                return ptree_search_data_r_p(node->r, str, slen, maxbitplace);
        else
@@ -147,17 +159,18 @@ static int ptree_search_data_r_x(struct patricia_node *node, char *str,
                if (node->klen == slen && !memcmp(str, node->key, node->klen)) {
                        if (node->addr && addr)
                                memcpy(addr, node->addr, node->alen);
+
                        (*alen) = node->alen;
+
                        return node->value.data;
                } else
                        return -ENOENT;
        }
+
        if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0)
-               return ptree_search_data_r_x(node->r, str, slen, addr,
-                                            alen, maxbitplace);
+               return ptree_search_data_r_x(node->r, str, slen, addr, alen, maxbitplace);
        else
-               return ptree_search_data_r_x(node->l, str, slen, addr,
-                                            alen, maxbitplace);
+               return ptree_search_data_r_x(node->l, str, slen, addr, alen, maxbitplace);
 }
 
 int ptree_search_data_nearest(void *str, size_t sstr, struct sockaddr_storage *addr,
@@ -165,6 +178,7 @@ int ptree_search_data_nearest(void *str, size_t sstr, struct sockaddr_storage *a
 {
        if (!root)
                return -ENOENT;
+
        return ptree_search_data_r(root, str, sstr, addr, alen, sstr * 8);
 }
 
@@ -179,6 +193,7 @@ int ptree_search_data_exact(void *str, size_t sstr, struct sockaddr_storage *add
 {
        if (!root)
                return -ENOENT;
+
        return ptree_search_data_r_x(root, str, sstr, addr, alen, sstr * 8);
 }
 
@@ -187,6 +202,7 @@ static struct patricia_node *ptree_make_root_node(char *str, size_t sstr,
                                                  size_t alen)
 {
        struct patricia_node *n = new_node();
+
        n->value.data = data;
        n->key = xmemdupz(str, sstr);
        n->klen = sstr;
@@ -195,6 +211,7 @@ static struct patricia_node *ptree_make_root_node(char *str, size_t sstr,
        else
                n->addr = NULL;
        n->alen = alen;
+
        return n;
 }
 
@@ -203,14 +220,15 @@ static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data,
                               struct patricia_node **parentlink)
 {
        struct patricia_node *node = (*parentlink);
-       if (node->value.thres_bit > bitloc ||
-           (node->l == NULL && node->r == NULL)) {
+
+       if (node->value.thres_bit > bitloc || (node->l == NULL && node->r == NULL)) {
                struct patricia_node *newleaf, *newbranch;
 
                newleaf = new_node();
                newleaf->value.data = data;
                newleaf->key = xmemdupz(str, slen);
                newleaf->klen = slen;
+
                if (addr)
                        newleaf->addr = xmemdupz(addr, alen);
                else
@@ -220,6 +238,7 @@ static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data,
                newbranch = new_node();
                newbranch->value.thres_bit = bitloc;
                (*parentlink) = newbranch;
+
                if (testbit(str, slen, bitloc) ==0) {
                        newbranch->l = newleaf;
                        newbranch->r = node;
@@ -227,14 +246,11 @@ static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data,
                        newbranch->l = node;
                        newbranch->r = newleaf;
                }
-               return;
        } else {
                if (testbit(str, slen, node->value.thres_bit) != 0)
-                       ptree_add_entry_at(str, slen, bitloc, data,
-                                          addr, alen, &(node->r));
+                       ptree_add_entry_at(str, slen, bitloc, data, addr, alen, &(node->r));
                else
-                       ptree_add_entry_at(str, slen, bitloc, data,
-                                          addr, alen, &(node->l));
+                       ptree_add_entry_at(str, slen, bitloc, data, addr, alen, &(node->l));
        }
 }
 
@@ -249,6 +265,7 @@ int ptree_add_entry(void *str, size_t sstr, int data, struct sockaddr_storage *a
        else {
                ptr = ptree_search_data_nearest_ptr(str, sstr, (*root));
                n = container_of(ptr, struct patricia_node, value.data);
+
                if (n->klen == sstr && !memcmp(str, n->key, n->klen)) {
                        /* Make sure if entry exists, that we also have the
                         * same data, otherwise, we drop the packet */
@@ -262,8 +279,10 @@ int ptree_add_entry(void *str, size_t sstr, int data, struct sockaddr_storage *a
                                if (memcmp(n->addr, addr, alen))
                                        malicious = 1;
                        }
+
                        return malicious;
                }
+
                bitloc = where_the_bit_differ(str, sstr, n->key, n->klen);
                ptree_add_entry_at(str, sstr, bitloc, data, addr, alen, root);
        }
@@ -289,7 +308,9 @@ static void ptree_remove_entry_r(struct patricia_node *now,
                        free_node(now);
                        return;
                }
+
                b = (up->r == now) ? up->l : up->r;
+
                if (up2 == NULL) {
                        *root = b;
                        free_node(now);
@@ -300,16 +321,14 @@ static void ptree_remove_entry_r(struct patricia_node *now,
                        up2->l = b;
                else
                        up2->r = b;
+
                free_node(now);
                free_node(up);
-               return;
        } else {
                if (testbit_max(str, now->value.thres_bit, maxbitplace) != 0)
-                       ptree_remove_entry_r(now->r, now, up, str, slen,
-                                            maxbitplace, root);
+                       ptree_remove_entry_r(now->r, now, up, str, slen, maxbitplace, root);
                else
-                       ptree_remove_entry_r(now->l, now, up, str, slen,
-                                            maxbitplace, root);
+                       ptree_remove_entry_r(now->l, now, up, str, slen, maxbitplace, root);
        }
 }
 
@@ -317,6 +336,7 @@ void ptree_del_entry(void *str, size_t sstr, struct patricia_node **root)
 {
        if (!(*root))
                return;
+
        ptree_remove_entry_r(*root, NULL, NULL, str, sstr, sstr * 8, root);
 }
 
@@ -324,10 +344,11 @@ void ptree_free(struct patricia_node *node)
 {
        if (!node)
                return;
+
        if (node->l)
                ptree_free(node->l);
        if (node->r)
                ptree_free(node->r);
+
        free_node(node);
 }
-
index 0e3bc5f..d568547 100644 (file)
@@ -47,6 +47,4 @@ extern void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen,
 extern void ptree_display(struct patricia_node *node, int level);
 extern void ptree_free(struct patricia_node *root);
 
-#define ptree_maybe_add_entry ptree_add_entry
-
 #endif /* PATRICIA_H */
diff --git a/trie.c b/trie.c
index 85277a8..a74d710 100644 (file)
--- a/trie.c
+++ b/trie.c
@@ -38,7 +38,6 @@ void trie_addr_lookup(char *buff, size_t len, int ipv4, int *fd,
                return;
        }
 
-       /* Always happens on the dst address */
        rwlock_rd_lock(&tree_lock);
        (*fd) = ptree_search_data_exact(data, dlen, addr, alen, tree);
        rwlock_unlock(&tree_lock);
@@ -60,9 +59,8 @@ int trie_addr_maybe_update(char *buff, size_t len, int ipv4, int fd,
                     (!ipv4 && ((struct ipv6hdr *) buff)->version  != 6)))
                return -1;
 
-       /* Always happens on the src address */
        rwlock_wr_lock(&tree_lock);
-       ret = ptree_maybe_add_entry(data, dlen, fd, addr, alen, &tree);
+       ret = ptree_add_entry(data, dlen, fd, addr, alen, &tree);
        rwlock_unlock(&tree_lock);
 
        return ret;
@@ -116,6 +114,5 @@ void trie_cleanup(void)
        rwlock_wr_lock(&tree_lock);
        ptree_free(tree);
        rwlock_unlock(&tree_lock);
-
        rwlock_destroy(&tree_lock);
 }