comparison: ucx/avl.h
ucx/avl.h
- changeset 193
- fb05d315a0ba
- parent 192
- 1e51558b9d09
- child 194
- 0c1b7676e74c
equal
deleted
inserted
replaced
| 192:1e51558b9d09 | 193:fb05d315a0ba |
|---|---|
| 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" | |
| 46 | |
| 47 | |
| 45 #ifdef __cplusplus | 48 #ifdef __cplusplus |
| 46 extern "C" { | 49 extern "C" { |
| 47 #endif | 50 #endif |
| 48 | 51 |
| 52 /** | |
| 53 * UCX AVL Node type. | |
| 54 * | |
| 55 * @see UcxAVLNode | |
| 56 */ | |
| 57 typedef struct UcxAVLNode UcxAVLNode; | |
| 58 | |
| 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 }; | |
| 88 | |
| 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; | |
| 108 | |
| 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); | |
| 116 | |
| 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); | |
| 126 | |
| 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); | |
| 49 | 134 |
| 50 | 135 |
| 51 | 136 |
| 52 #ifdef __cplusplus | 137 #ifdef __cplusplus |
| 53 } | 138 } |
