--- a/ucx/avl.h Tue May 19 14:04:48 2015 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,188 +0,0 @@
-/*
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
- *
- * Copyright 2015 Olaf Wintermann. 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 HOLDER 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.
- */
-
-
-/**
- * @file avl.h
- *
- * AVL tree implementation.
- *
- * This binary search tree implementation allows average O(1) insertion and
- * removal of elements.
- *
- * @author Mike Becker
- * @author Olaf Wintermann
- */
-
-#ifndef UCX_AVL_H
-#define UCX_AVL_H
-
-#include "ucx.h"
-#include "allocator.h"
-#include <stdint.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- * UCX AVL Node type.
- *
- * @see UcxAVLNode
- */
-typedef struct UcxAVLNode UcxAVLNode;
-
-/**
- * UCX AVL Node.
- */
-struct UcxAVLNode {
- /**
- * The key for this node.
- */
- intptr_t key;
- /**
- * Data contained by this node.
- */
- void *value;
- /**
- * The height of this (sub)-tree.
- */
- size_t height;
- /**
- * Parent node.
- */
- UcxAVLNode *parent;
- /**
- * Root node of left subtree.
- */
- UcxAVLNode *left;
- /**
- * Root node of right subtree.
- */
- UcxAVLNode *right;
-};
-
-/**
- * UCX AVL Tree.
- */
-typedef struct {
- /**
- * The UcxAllocator that shall be used to manage the memory for node data.
- */
- UcxAllocator *allocator;
- /**
- * Root node of the tree.
- */
- UcxAVLNode *root;
- /**
- * Compare function that shall be used to compare the UcxAVLNode keys.
- * @see UcxAVLNode.key
- */
- cmp_func cmpfunc;
- /**
- * Custom user data.
- * This data will also be provided to the cmpfunc.
- */
- void *userdata;
-} UcxAVLTree;
-
-/**
- * Initializes a new UcxAVLTree with a default allocator.
- *
- * @param cmpfunc the compare function that shall be used
- * @return a new UcxAVLTree object
- * @see ucx_avl_new_a()
- */
-UcxAVLTree *ucx_avl_new(cmp_func cmpfunc);
-
-/**
- * Initializes a new UcxAVLTree with the specified allocator.
- *
- * The cmpfunc should be capable of comparing two keys within this AVL tree.
- * So if you want to use null terminated strings as keys, you could use the
- * ucx_strcmp() function here.
- *
- * @param cmpfunc the compare function that shall be used
- * @param allocator the UcxAllocator that shall be used
- * @return a new UcxAVLTree object
- */
-UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
-
-/**
- * Destroys an UcxAVLTree.
- * @param tree the tree to destroy
- */
-void ucx_avl_free(UcxAVLTree *tree);
-
-/**
- * Macro for initializing a new UcxAVLTree with the default allocator and a
- * ucx_ptrcmp() compare function.
- *
- * @return a new default UcxAVLTree object
- */
-#define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
-
-/**
- * Gets the value from the tree, that is associated with the specified key.
- * @param tree the UcxAVLTree
- * @param key the key
- * @return the value (or <code>NULL</code>, if the key is not present)
- */
-void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
-
-/**
- * Puts a key/value pair into the tree.
- * @param tree the UcxAVLTree
- * @param key the key
- * @param value the new value
- * @return the replaced value (or <code>NULL</code>, if the key is new to the
- * tree)
- */
-void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
-
-/**
- * Removes an element from the AVL tree.
- * @param tree the UcxAVLTree
- * @param key the key
- * @return the removed value (or <code>NULL</code>, if the key was not present)
- */
-void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
-
-/**
- * Counts the nodes in the specified UcxAVLTree.
- * @param tree the AVL tree
- * @return the node count
- */
-size_t ucx_avl_count(UcxAVLTree *tree);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* UCX_AVL_H */
-