path: root/third-party/tommyds/tommytrie.c

/*
 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. 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 THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 THE COPYRIGHT OWNER OR CONTRIBUTORS 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.
 */

#include "tommytrie.h"
#include "tommylist.h"

#include <assert.h> /* for assert */

/******************************************************************************/
/* trie */

/**
 * Mask for the inner branches.
 */
#define TOMMY_TRIE_TREE_MASK (TOMMY_TRIE_TREE_MAX - 1)

/**
 * Shift for the first level of branches.
 */
#define TOMMY_TRIE_BUCKET_SHIFT (TOMMY_KEY_BIT - TOMMY_TRIE_BUCKET_BIT)

/**
 * Max number of levels.
 */
#define TOMMY_TRIE_LEVEL_MAX ((TOMMY_KEY_BIT - TOMMY_TRIE_BUCKET_BIT) / TOMMY_TRIE_TREE_BIT)

/**
 * Hashtrie tree.
 * A tree contains TOMMY_TRIE_TREE_MAX ordered pointers to <null/node/tree>.
 *
 * Each tree level uses exactly TOMMY_TRIE_TREE_BIT bits from the key.
 */
struct tommy_trie_tree_struct {
	tommy_trie_node* map[TOMMY_TRIE_TREE_MAX];
};
typedef struct tommy_trie_tree_struct tommy_trie_tree;

/**
 * Kinds of an trie node.
 */
#define TOMMY_TRIE_TYPE_NODE 0 /**< The node is of type ::tommy_trie_node. */
#define TOMMY_TRIE_TYPE_TREE 1 /**< The node is of type ::tommy_trie_tree. */

/**
 * Get and set pointer of trie nodes.
 *
 * The pointer type is stored in the lower bit.
 */
#define trie_get_type(ptr) (((tommy_uintptr_t)(ptr)) & 1)
#define trie_get_tree(ptr) ((tommy_trie_tree*)(((tommy_uintptr_t)(ptr)) - TOMMY_TRIE_TYPE_TREE))
#define trie_set_tree(ptr) (void*)(((tommy_uintptr_t)(ptr)) + TOMMY_TRIE_TYPE_TREE)

void tommy_trie_init(tommy_trie* trie, tommy_allocator* alloc)
{
	tommy_uint_t i;

	for (i = 0; i < TOMMY_TRIE_BUCKET_MAX; ++i)
		trie->bucket[i] = 0;

	trie->count = 0;
	trie->node_count = 0;

	trie->alloc = alloc;
}

static void trie_bucket_insert(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* insert, tommy_key_t key)
{
	tommy_trie_tree* tree;
	tommy_trie_node* node;
	void* ptr;
	tommy_uint_t i;
	tommy_uint_t j;

recurse:
	ptr = *let_ptr;

	/* if null, just insert the node */
	if (!ptr) {
		/* setup the node as a list */
		tommy_list_insert_first(let_ptr, insert);
		return;
	}

	if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
		/* repeat the process one level down */
		let_ptr = &trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
		shift -= TOMMY_TRIE_TREE_BIT;
		goto recurse;
	}

	node = tommy_cast(tommy_trie_node*, ptr);

	/* if it's the same key, insert in the list */
	if (node->key == key) {
		tommy_list_insert_tail_not_empty(node, insert);
		return;
	}

expand:
	/* convert to a tree */
	tree = tommy_cast(tommy_trie_tree*, tommy_allocator_alloc(trie->alloc));
	++trie->node_count;
	*let_ptr = tommy_cast(tommy_trie_node*, trie_set_tree(tree));

	/* initialize it */
	for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i)
		tree->map[i] = 0;

	/* get the position of the two elements */
	i = (node->key >> shift) & TOMMY_TRIE_TREE_MASK;
	j = (key >> shift) & TOMMY_TRIE_TREE_MASK;

	/* if they don't collide */
	if (i != j) {
		/* insert the already existing element */
		tree->map[i] = node;

		/* insert the new node */
		tommy_list_insert_first(&tree->map[j], insert);
		return;
	}

	/* expand one more level */
	let_ptr = &tree->map[i];
	shift -= TOMMY_TRIE_TREE_BIT;
	goto expand;
}

void tommy_trie_insert(tommy_trie* trie, tommy_trie_node* node, void* data, tommy_key_t key)
{
	tommy_trie_node** let_ptr;

	node->data = data;
	node->key = key;

	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];

	trie_bucket_insert(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);

	++trie->count;
}

static tommy_trie_node* trie_bucket_remove_existing(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* remove, tommy_key_t key)
{
	tommy_trie_node* node;
	tommy_trie_tree* tree;
	void* ptr;
	tommy_trie_node** let_back[TOMMY_TRIE_LEVEL_MAX + 1];
	tommy_uint_t level;
	tommy_uint_t i;
	tommy_uint_t count;
	tommy_uint_t last;

	level = 0;
recurse:
	ptr = *let_ptr;

	if (!ptr)
		return 0;

	if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
		tree = trie_get_tree(ptr);

		/* save the path */
		let_back[level++] = let_ptr;

		/* go down one level */
		let_ptr = &tree->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
		shift -= TOMMY_TRIE_TREE_BIT;

		goto recurse;
	}

	node = tommy_cast(tommy_trie_node*, ptr);

	/* if the node to remove is not specified */
	if (!remove) {
		/* remove the first */
		remove = node;

		/* check if it's really the element to remove */
		if (remove->key != key)
			return 0;
	}

	tommy_list_remove_existing(let_ptr, remove);

	/* if the list is not empty, try to reduce */
	if (*let_ptr || !level)
		return remove;

reduce:
	/* go one level up */
	let_ptr = let_back[--level];

	tree = trie_get_tree(*let_ptr);

	/* check if there is only one child node */
	count = 0;
	last = 0;
	for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i) {
		if (tree->map[i]) {
			/* if we have a sub tree, we cannot reduce */
			if (trie_get_type(tree->map[i]) != TOMMY_TRIE_TYPE_NODE)
				return remove;
			/* if more than one node, we cannot reduce */
			if (++count > 1)
				return remove;
			last = i;
		}
	}

	/* here count is never 0, as we cannot have a tree with only one sub node */
	assert(count == 1);

	*let_ptr = tree->map[last];

	tommy_allocator_free(trie->alloc, tree);
	--trie->node_count;

	/* repeat until more level */
	if (level)
		goto reduce;

	return remove;
}

void* tommy_trie_remove(tommy_trie* trie, tommy_key_t key)
{
	tommy_trie_node* ret;
	tommy_trie_node** let_ptr;

	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];

	ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, 0, key);

	if (!ret)
		return 0;

	--trie->count;

	return ret->data;
}

void* tommy_trie_remove_existing(tommy_trie* trie, tommy_trie_node* node)
{
	tommy_trie_node* ret;
	tommy_key_t key = node->key;
	tommy_trie_node** let_ptr;

	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];

	ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);

	/* the element removed must match the one passed */
	assert(ret == node);

	--trie->count;

	return ret->data;
}

tommy_trie_node* tommy_trie_bucket(tommy_trie* trie, tommy_key_t key)
{
	tommy_trie_node* node;
	void* ptr;
	tommy_uint_t type;
	tommy_uint_t shift;

	ptr = trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];

	shift = TOMMY_TRIE_BUCKET_SHIFT;

recurse:
	if (!ptr)
		return 0;

	type = trie_get_type(ptr);

	switch (type) {
	case TOMMY_TRIE_TYPE_NODE :
		node = tommy_cast(tommy_trie_node*, ptr);
		if (node->key != key)
			return 0;
		return node;
	default :
	case TOMMY_TRIE_TYPE_TREE :
		ptr = trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
		shift -= TOMMY_TRIE_TREE_BIT;
		goto recurse;
	}
}

tommy_size_t tommy_trie_memory_usage(tommy_trie* trie)
{
	return tommy_trie_count(trie) * (tommy_size_t)sizeof(tommy_trie_node)
	       + trie->node_count * (tommy_size_t)TOMMY_TRIE_BLOCK_SIZE;
}