Sun, 17 May 2015 17:59:07 +0200
defined AVL tree functional interface
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2015 Olaf Wintermann. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
30 /**
31 * @file avl.h
32 *
33 * AVL tree implementation.
34 *
35 * This binary search tree implementation allows average O(1) insertion and
36 * removal of elements.
37 *
38 * @author Mike Becker
39 * @author Olaf Wintermann
40 */
42 #ifndef UCX_AVL_H
43 #define UCX_AVL_H
45 #include "ucx.h"
48 #ifdef __cplusplus
49 extern "C" {
50 #endif
52 /**
53 * UCX AVL Node type.
54 *
55 * @see UcxAVLNode
56 */
57 typedef struct UcxAVLNode UcxAVLNode;
59 /**
60 * UCX AVL Node.
61 */
62 struct UcxAVLNode {
63 /**
64 * The key for this node.
65 */
66 void *key;
67 /**
68 * Data contained by this node.
69 */
70 void *value;
71 /**
72 * The height of this (sub)-tree.
73 */
74 size_t height;
75 /**
76 * Parent node.
77 */
78 UcxAVLNode *parent;
79 /**
80 * Root node of left subtree.
81 */
82 UcxAVLNode *left;
83 /**
84 * Root node of right subtree.
85 */
86 UcxAVLNode *right;
87 };
89 /**
90 * UCX AVL Tree.
91 */
92 typedef struct {
93 /**
94 * Root node of the tree.
95 */
96 UcxAVLNode *root;
97 /**
98 * Compare function that shall be used to compare the UcxAVLNode keys.
99 * @see UcxAVLNode.key
100 */
101 cmp_func cmpfunc;
102 /**
103 * Custom user data.
104 * This data will also be provided to the cmpfunc.
105 */
106 void *userdata;
107 } UcxAVLTree;
109 /**
110 * Gets the value from the tree, that is associated with the specified key.
111 * @param tree the UcxAVLTree
112 * @param key the key
113 * @return the value (or <code>NULL</code>, if the key is not present)
114 */
115 void *ucx_avl_get(UcxAVLTree *tree, void *key);
117 /**
118 * Puts a key/value pair into the tree.
119 * @param tree the UcxAVLTree
120 * @param key the key
121 * @param value the new value
122 * @return the replaced value (or <code>NULL</code>, if the key is new to the
123 * tree)
124 */
125 void* ucx_avl_put(UcxAVLTree *tree, void *key, void *value);
127 /**
128 * Removes an element from the AVL tree.
129 * @param tree the UcxAVLTree
130 * @param key the key
131 * @return the removed value (or <code>NULL</code>, if the key was not present)
132 */
133 void* ucx_avl_remove(UcxAVLTree *tree, void *key);
137 #ifdef __cplusplus
138 }
139 #endif
141 #endif /* UCX_AVL_H */