comparison: ucx/avl.h
ucx/avl.h
- changeset 194
- 0c1b7676e74c
- parent 193
- fb05d315a0ba
- child 196
- 1b4cdafef2eb
equal
deleted
inserted
replaced
| 193:fb05d315a0ba | 194:0c1b7676e74c |
|---|---|
| 38 * @author Mike Becker | 38 * @author Mike Becker |
| 39 * @author Olaf Wintermann | 39 * @author Olaf Wintermann |
| 40 */ | 40 */ |
| 41 | 41 |
| 42 #ifndef UCX_AVL_H | 42 #ifndef UCX_AVL_H |
| 43 #define UCX_AVL_H | 43 #define UCX_AVL_H |
| 44 | 44 |
| 45 #include "ucx.h" | 45 #include "ucx.h" |
| 46 | 46 #include "allocator.h" |
| 47 #include <stdint.h> | |
| 47 | 48 |
| 48 #ifdef __cplusplus | 49 #ifdef __cplusplus |
| 49 extern "C" { | 50 extern "C" { |
| 50 #endif | 51 #endif |
| 51 | 52 |
| 61 */ | 62 */ |
| 62 struct UcxAVLNode { | 63 struct UcxAVLNode { |
| 63 /** | 64 /** |
| 64 * The key for this node. | 65 * The key for this node. |
| 65 */ | 66 */ |
| 66 void *key; | 67 intptr_t key; |
| 67 /** | 68 /** |
| 68 * Data contained by this node. | 69 * Data contained by this node. |
| 69 */ | 70 */ |
| 70 void *value; | 71 void *value; |
| 71 /** | 72 /** |
| 89 /** | 90 /** |
| 90 * UCX AVL Tree. | 91 * UCX AVL Tree. |
| 91 */ | 92 */ |
| 92 typedef struct { | 93 typedef struct { |
| 93 /** | 94 /** |
| 95 * The UcxAllocator that shall be used to manage the memory for node data. | |
| 96 */ | |
| 97 UcxAllocator *allocator; | |
| 98 /** | |
| 94 * Root node of the tree. | 99 * Root node of the tree. |
| 95 */ | 100 */ |
| 96 UcxAVLNode *root; | 101 UcxAVLNode *root; |
| 97 /** | 102 /** |
| 98 * Compare function that shall be used to compare the UcxAVLNode keys. | 103 * Compare function that shall be used to compare the UcxAVLNode keys. |
| 105 */ | 110 */ |
| 106 void *userdata; | 111 void *userdata; |
| 107 } UcxAVLTree; | 112 } UcxAVLTree; |
| 108 | 113 |
| 109 /** | 114 /** |
| 115 * Initializes a new UcxAVLTree with a default allocator. | |
| 116 * | |
| 117 * @param cmpfunc the compare function that shall be used | |
| 118 * @return a new UcxAVLTree object | |
| 119 * @see ucx_avl_new_a() | |
| 120 */ | |
| 121 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc); | |
| 122 | |
| 123 /** | |
| 124 * Initializes a new UcxAVLTree with the specified allocator. | |
| 125 * | |
| 126 * The cmpfunc should be capable of comparing two keys within this AVL tree. | |
| 127 * So if you want to use null terminated strings as keys, you could use the | |
| 128 * ucx_strcmp() function here. | |
| 129 * | |
| 130 * @param cmpfunc the compare function that shall be used | |
| 131 * @param allocator the UcxAllocator that shall be used | |
| 132 * @return a new UcxAVLTree object | |
| 133 */ | |
| 134 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator); | |
| 135 | |
| 136 /** | |
| 137 * Macro for initializing a new UcxAVLTree with the default allocator and a | |
| 138 * ucx_ptrcmp() compare function. | |
| 139 * | |
| 140 * @return a new default UcxAVLTree object | |
| 141 */ | |
| 142 #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator()) | |
| 143 | |
| 144 /** | |
| 110 * Gets the value from the tree, that is associated with the specified key. | 145 * Gets the value from the tree, that is associated with the specified key. |
| 111 * @param tree the UcxAVLTree | 146 * @param tree the UcxAVLTree |
| 112 * @param key the key | 147 * @param key the key |
| 113 * @return the value (or <code>NULL</code>, if the key is not present) | 148 * @return the value (or <code>NULL</code>, if the key is not present) |
| 114 */ | 149 */ |
| 115 void *ucx_avl_get(UcxAVLTree *tree, void *key); | 150 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); |
| 116 | 151 |
| 117 /** | 152 /** |
| 118 * Puts a key/value pair into the tree. | 153 * Puts a key/value pair into the tree. |
| 119 * @param tree the UcxAVLTree | 154 * @param tree the UcxAVLTree |
| 120 * @param key the key | 155 * @param key the key |
| 121 * @param value the new value | 156 * @param value the new value |
| 122 * @return the replaced value (or <code>NULL</code>, if the key is new to the | 157 * @return the replaced value (or <code>NULL</code>, if the key is new to the |
| 123 * tree) | 158 * tree) |
| 124 */ | 159 */ |
| 125 void* ucx_avl_put(UcxAVLTree *tree, void *key, void *value); | 160 void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value); |
| 126 | 161 |
| 127 /** | 162 /** |
| 128 * Removes an element from the AVL tree. | 163 * Removes an element from the AVL tree. |
| 129 * @param tree the UcxAVLTree | 164 * @param tree the UcxAVLTree |
| 130 * @param key the key | 165 * @param key the key |
| 131 * @return the removed value (or <code>NULL</code>, if the key was not present) | 166 * @return the removed value (or <code>NULL</code>, if the key was not present) |
| 132 */ | 167 */ |
| 133 void* ucx_avl_remove(UcxAVLTree *tree, void *key); | 168 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key); |
| 134 | 169 |
| 135 | 170 |
| 136 | 171 |
| 137 #ifdef __cplusplus | 172 #ifdef __cplusplus |
| 138 } | 173 } |
