From df902a57f916c1744c8a8a56d27cf89f7de9b885 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Tue, 12 May 2015 09:28:25 +0100 Subject: [PATCH] Remove old radix code (no functional changes). --- src/libutil/radix.c | 328 +------------------------------------------- src/libutil/radix.h | 134 +++++++----------- 2 files changed, 48 insertions(+), 414 deletions(-) diff --git a/src/libutil/radix.c b/src/libutil/radix.c index 17b73b6cc..605d86668 100644 --- a/src/libutil/radix.c +++ b/src/libutil/radix.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2009-2014, Vsevolod Stakhov + * Copyright (c) 2009-2015, Vsevolod Stakhov * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -28,7 +28,6 @@ #include "main.h" #include "mem_pool.h" - struct radix_compressed_node { union { struct { @@ -52,331 +51,6 @@ struct radix_tree_compressed { size_t size; }; - -#ifdef LEGACY_RADIX -static void * radix_alloc (radix_tree_t * tree); - -#undef RADIX_DEBUG -#ifndef RADIX_DEBUG -#undef msg_debug -#define msg_debug(...) do {} while (0) -#endif - -struct radix_node_s { - radix_node_t *right; - radix_node_t *left; - radix_node_t *parent; - uintptr_t value; - guint32 key; -}; -struct radix_tree_s { - radix_node_t *root; - size_t size; - rspamd_mempool_t *pool; -}; - -radix_tree_t * -radix_tree_create (void) -{ - radix_tree_t *tree; - - tree = g_malloc (sizeof (radix_tree_t)); - if (tree == NULL) { - return NULL; - } - - tree->pool = rspamd_mempool_new (rspamd_mempool_suggest_size ()); - tree->size = 0; - - tree->root = radix_alloc (tree); - if (tree->root == NULL) { - return NULL; - } - - tree->root->right = NULL; - tree->root->left = NULL; - tree->root->parent = NULL; - tree->root->value = RADIX_NO_VALUE; - - return tree; -} - -static uintptr_t -radix32tree_insert_common (radix_tree_t * tree, - guint32 key, - guint32 mask, - uintptr_t value, - enum radix_insert_type type) -{ - guint32 bit; - radix_node_t *node, *next; - - bit = 0x80000000; - - node = tree->root; - next = tree->root; - /* Find a place in trie to insert */ - while (bit & mask) { - if (key & bit) { - next = node->right; - } - else { - next = node->left; - } - - if (next == NULL) { - break; - } - - bit >>= 1; - node = next; - } - - if (next) { - if (node->value != RADIX_NO_VALUE) { - /* Value was found, switch on insert type */ - switch (type) { - case RADIX_INSERT: - return 1; - case RADIX_ADD: - node->value += value; - return value; - case RADIX_REPLACE: - node->value = value; - return 1; - } - } - - node->value = value; - node->key = key; - return 0; - } - /* Inserting value in trie creating all path components */ - while (bit & mask) { - next = radix_alloc (tree); - if (next == NULL) { - return -1; - } - - next->right = NULL; - next->left = NULL; - next->parent = node; - next->value = RADIX_NO_VALUE; - - if (key & bit) { - node->right = next; - - } - else { - node->left = next; - } - - bit >>= 1; - node = next; - } - - node->value = value; - node->key = key; - - return 0; -} - -gint -radix32tree_insert (radix_tree_t *tree, - guint32 key, - guint32 mask, - uintptr_t value) -{ - return (gint)radix32tree_insert_common (tree, key, mask, value, - RADIX_INSERT); -} - -uintptr_t -radix32tree_add (radix_tree_t *tree, guint32 key, guint32 mask, uintptr_t value) -{ - return radix32tree_insert_common (tree, key, mask, value, RADIX_ADD); -} - -gint -radix32tree_replace (radix_tree_t *tree, - guint32 key, - guint32 mask, - uintptr_t value) -{ - return (gint)radix32tree_insert_common (tree, - key, - mask, - value, - RADIX_REPLACE); -} - -/* - * per recursion step: - * ptr + ptr + ptr + gint = 4 words - * result = 1 word - * 5 words total in stack - */ -static gboolean -radix_recurse_nodes (radix_node_t *node, - radix_tree_traverse_func func, - void *user_data, - gint level) -{ - if (node->left) { - if (radix_recurse_nodes (node->left, func, user_data, level + 1)) { - return TRUE; - } - } - - if (node->value != RADIX_NO_VALUE) { - if (func (node->key, level, node->value, user_data)) { - return TRUE; - } - } - - if (node->right) { - if (radix_recurse_nodes (node->right, func, user_data, level + 1)) { - return TRUE; - } - } - - return FALSE; -} - -void -radix32tree_traverse (radix_tree_t *tree, - radix_tree_traverse_func func, - void *user_data) -{ - radix_recurse_nodes (tree->root, func, user_data, 0); -} - - -gint -radix32tree_delete (radix_tree_t * tree, guint32 key, guint32 mask) -{ - guint32 bit; - radix_node_t *node; - - bit = 0x80000000; - node = tree->root; - - while (node && (bit & mask)) { - if (key & bit) { - node = node->right; - - } - else { - node = node->left; - } - - bit >>= 1; - } - - if (node == NULL || node->parent == NULL) { - return -1; - } - - if (node->right || node->left) { - if (node->value != RADIX_NO_VALUE) { - node->value = RADIX_NO_VALUE; - return 0; - } - - return -1; - } - - for (;; ) { - if (node->parent->right == node) { - node->parent->right = NULL; - - } - else { - node->parent->left = NULL; - } - - node = node->parent; - - if (node->right || node->left) { - break; - } - - if (node->value != RADIX_NO_VALUE) { - break; - } - - if (node->parent == NULL) { - break; - } - } - - return 0; -} - - -uintptr_t -radix32tree_find (radix_tree_t * tree, guint32 key) -{ - guint32 bit; - uintptr_t value; - radix_node_t *node; - - bit = 0x80000000; - value = RADIX_NO_VALUE; - node = tree->root; - - while (node) { - if (node->value != RADIX_NO_VALUE) { - value = node->value; - } - - if (key & bit) { - node = node->right; - - } - else { - node = node->left; - } - - bit >>= 1; - } - - return value; -} - - -static void * -radix_alloc (radix_tree_t * tree) -{ - gchar *p; - - p = rspamd_mempool_alloc (tree->pool, sizeof (radix_node_t)); - - tree->size += sizeof (radix_node_t); - - return p; -} - -void -radix_tree_free (radix_tree_t * tree) -{ - - g_return_if_fail (tree != NULL); - rspamd_mempool_delete (tree->pool); - g_free (tree); -} - -uintptr_t -radix32_tree_find_addr (radix_tree_t *tree, rspamd_inet_addr_t *addr) -{ - if (addr == NULL || addr->af != AF_INET) { - return RADIX_NO_VALUE; - } - - return radix32tree_find (tree, ntohl (addr->addr.s4.sin_addr.s_addr)); -} -#endif /* Old radix code */ - static gboolean radix_compare_compressed (struct radix_compressed_node *node, guint8 *key, guint keylen, guint cur_level) diff --git a/src/libutil/radix.h b/src/libutil/radix.h index b17731fd7..84d617305 100644 --- a/src/libutil/radix.h +++ b/src/libutil/radix.h @@ -1,3 +1,27 @@ +/* + * Copyright (c) 2009-2015, Vsevolod Stakhov + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY AUTHOR ''AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + #ifndef RADIX_H #define RADIX_H @@ -10,105 +34,33 @@ typedef struct radix_tree_compressed radix_compressed_t; -#ifdef LEGACY_RADIX -typedef struct radix_node_s radix_node_t; -typedef struct radix_tree_s radix_tree_t; -enum radix_insert_type { - RADIX_INSERT, - RADIX_ADD, - RADIX_REPLACE -}; - -typedef gboolean (*radix_tree_traverse_func)(guint32 key, guint32 mask, - uintptr_t value, void *user_data); - -/** - * Create new radix tree - */ -radix_tree_t * radix_tree_create (void); - -/** - * Insert value to radix tree - * returns: 1 if value already exists - * 0 if operation was successfull - * -1 if there was some error - */ -gint radix32tree_insert (radix_tree_t *tree, - guint32 key, - guint32 mask, - uintptr_t value); - -/** - * Add value to radix tree or insert it if value does not exists - * returns: value if value already exists and was added - * 0 if value was inserted - * -1 if there was some error - */ -uintptr_t radix32tree_add (radix_tree_t *tree, - guint32 key, - guint32 mask, - uintptr_t value); - -/** - * Replace value in radix tree or insert it if value does not exists - * returns: 1 if value already exists and was replaced - * 0 if value was inserted - * -1 if there was some error - */ -gint radix32tree_replace (radix_tree_t *tree, - guint32 key, - guint32 mask, - uintptr_t value); - -/** - * Delete value from radix tree - * returns: 1 if value does not exist - * 0 if value was deleted - * -1 if there was some error - */ -gint radix32tree_delete (radix_tree_t *tree, guint32 key, guint32 mask); - -/** - * Find value in radix tree - * returns: value if value was found - * RADIX_NO_VALUE if value was not found - */ -uintptr_t radix32tree_find (radix_tree_t *tree, guint32 key); - -/** - * Find specified address in tree (works only for ipv4 addresses) - * @param tree - * @param addr - * @return - */ -uintptr_t radix32_tree_find_addr (radix_tree_t *tree, rspamd_inet_addr_t *addr); - - - /** - * Traverse via the whole tree calling specified callback + * Insert new key to the radix trie + * @param tree radix trie + * @param key key to insert (bitstring) + * @param keylen length of the key (in bytes) + * @param masklen lenght of mask that should be applied to the key (in bits) + * @param value opaque value pointer + * @return previous value of the key or `RADIX_NO_VALUE` */ -void radix32tree_traverse (radix_tree_t *tree, - radix_tree_traverse_func func, - void *user_data); - -/** - * Frees radix tree - */ -void radix_tree_free (radix_tree_t *tree); -#endif - uintptr_t radix_insert_compressed (radix_compressed_t * tree, guint8 *key, gsize keylen, gsize masklen, uintptr_t value); +/** + * Find a key in a radix trie + * @param tree radix trie + * @param key key to find (bitstring) + * @param keylen length of a key + * @return opaque pointer or `RADIX_NO_VALUE` if no value has been found + */ uintptr_t radix_find_compressed (radix_compressed_t * tree, guint8 *key, gsize keylen); /** - * Find specified address in tree (works for any address) + * Find specified address in tree (works for IPv4 or IPv6 addresses) * @param tree * @param addr * @return @@ -116,8 +68,16 @@ uintptr_t radix_find_compressed (radix_compressed_t * tree, guint8 *key, uintptr_t radix_find_compressed_addr (radix_compressed_t *tree, rspamd_inet_addr_t *addr); +/** + * Destroy the complete radix trie + * @param tree + */ void radix_destroy_compressed (radix_compressed_t *tree); +/** + * Create new radix trie + * @return + */ radix_compressed_t *radix_create_compressed (void); /** -- 2.39.5