mkavl.h
Go to the documentation of this file.
00001 00104 #ifndef __MKAVL_H__ 00105 #define __MKAVL_H__ 00106 00107 #include <stdlib.h> 00108 #include <stdint.h> 00109 #include <stdbool.h> 00110 #include <string.h> 00111 #include <assert.h> 00112 00114 typedef struct mkavl_tree_st_ *mkavl_tree_handle; 00115 00117 typedef struct mkavl_iterator_st_ *mkavl_iterator_handle; 00118 00122 typedef enum mkavl_rc_e_ { 00124 MKAVL_RC_E_INVALID, 00126 MKAVL_RC_E_SUCCESS, 00128 MKAVL_RC_E_EINVAL, 00130 MKAVL_RC_E_ENOMEM, 00132 MKAVL_RC_E_EOOSYNC, 00134 MKAVL_RC_E_MAX, 00135 } mkavl_rc_e; 00136 00140 typedef enum mkavl_find_type_e_ { 00142 MKAVL_FIND_TYPE_E_INVALID, 00144 MKAVL_FIND_TYPE_E_EQUAL, 00146 MKAVL_FIND_TYPE_E_FIRST = MKAVL_FIND_TYPE_E_EQUAL, 00148 MKAVL_FIND_TYPE_E_GT, 00150 MKAVL_FIND_TYPE_E_LT, 00152 MKAVL_FIND_TYPE_E_GE, 00154 MKAVL_FIND_TYPE_E_LE, 00156 MKAVL_FIND_TYPE_E_MAX, 00157 } mkavl_find_type_e; 00158 00162 typedef void * 00163 (*mkavl_malloc_fn)(size_t size, void *context); 00164 00168 typedef void 00169 (*mkavl_free_fn)(void *ptr, void *context); 00170 00174 typedef struct mkavl_allocator_st_ { 00176 mkavl_malloc_fn malloc_fn; 00178 mkavl_free_fn free_fn; 00179 } mkavl_allocator_st; 00180 00188 typedef int32_t 00189 (*mkavl_compare_fn)(const void *item1, const void *item2, 00190 void *context); 00191 00200 typedef mkavl_rc_e 00201 (*mkavl_item_fn)(void *item, void *context); 00202 00210 typedef mkavl_rc_e 00211 (*mkavl_delete_context_fn)(void *context); 00212 00221 typedef void * 00222 (*mkavl_copy_fn)(void *item, void *context); 00223 00233 typedef mkavl_rc_e 00234 (*mkavl_walk_cb_fn)(void *item, void *tree_context, void *walk_context, 00235 bool *stop_walk); 00236 00237 /* APIs below are documented in their implementation file */ 00238 00239 /* Utility functions */ 00240 00241 extern bool 00242 mkavl_rc_e_is_notok(mkavl_rc_e rc); 00243 00244 extern bool 00245 mkavl_rc_e_is_ok(mkavl_rc_e rc); 00246 00247 extern bool 00248 mkavl_rc_e_is_valid(mkavl_rc_e rc); 00249 00250 extern const char * 00251 mkavl_rc_e_get_string(mkavl_rc_e rc); 00252 00253 extern bool 00254 mkavl_find_type_e_is_valid(mkavl_find_type_e type); 00255 00256 extern const char * 00257 mkavl_find_type_e_get_string(mkavl_find_type_e type); 00258 00259 /* AVL APIs */ 00260 00261 extern mkavl_rc_e 00262 mkavl_new(mkavl_tree_handle *tree_h, 00263 mkavl_compare_fn *compare_fn_array, 00264 size_t compare_fn_array_count, 00265 void *context, mkavl_allocator_st *allocator); 00266 00267 extern void * 00268 mkavl_get_tree_context(mkavl_tree_handle tree_h); 00269 00270 extern mkavl_rc_e 00271 mkavl_delete(mkavl_tree_handle *tree_h, mkavl_item_fn item_fn, 00272 mkavl_delete_context_fn delete_context_fn); 00273 00274 extern mkavl_rc_e 00275 mkavl_copy(const mkavl_tree_handle source_tree_h, 00276 mkavl_tree_handle *new_tree_h, 00277 mkavl_copy_fn copy_fn, mkavl_item_fn item_fn, 00278 bool use_source_context, void *new_context, 00279 mkavl_delete_context_fn delete_context_fn, 00280 mkavl_allocator_st *allocator); 00281 00282 extern mkavl_rc_e 00283 mkavl_add(mkavl_tree_handle tree_h, void *item_to_add, 00284 void **existing_item); 00285 00286 extern mkavl_rc_e 00287 mkavl_find(mkavl_tree_handle tree_h, mkavl_find_type_e type, 00288 size_t key_idx, const void *lookup_item, void **found_item); 00289 00290 extern mkavl_rc_e 00291 mkavl_remove(mkavl_tree_handle tree_h, const void *item_to_remove, 00292 void **found_item); 00293 00294 extern mkavl_rc_e 00295 mkavl_add_key_idx(mkavl_tree_handle tree_h, size_t key_idx, 00296 void *item_to_add, void **existing_item); 00297 00298 extern mkavl_rc_e 00299 mkavl_remove_key_idx(mkavl_tree_handle tree_h, size_t key_idx, 00300 const void *item_to_remove, void **found_item); 00301 00302 /* AVL utility functions */ 00303 00304 extern uint32_t 00305 mkavl_count(mkavl_tree_handle tree_h); 00306 00307 extern mkavl_rc_e 00308 mkavl_walk(mkavl_tree_handle tree_h, mkavl_walk_cb_fn cb_fn, 00309 void *walk_context); 00310 00311 // TODO: selective delete walk function? 00312 00313 /* AVL iterator functions. */ 00314 00315 extern mkavl_rc_e 00316 mkavl_iter_new(mkavl_iterator_handle *iterator_h, mkavl_tree_handle tree_h, 00317 size_t key_idx); 00318 00319 extern mkavl_rc_e 00320 mkavl_iter_delete(mkavl_iterator_handle *iterator_h); 00321 00322 extern mkavl_rc_e 00323 mkavl_iter_first(mkavl_iterator_handle iterator_h, void **item); 00324 00325 extern mkavl_rc_e 00326 mkavl_iter_last(mkavl_iterator_handle iterator_h, void **item); 00327 00328 extern mkavl_rc_e 00329 mkavl_iter_find(mkavl_iterator_handle iterator_h, void *lookup_item, 00330 void **found_item); 00331 00332 extern mkavl_rc_e 00333 mkavl_iter_next(mkavl_iterator_handle iterator_h, void **item); 00334 00335 extern mkavl_rc_e 00336 mkavl_iter_prev(mkavl_iterator_handle iterator_h, void **item); 00337 00338 extern mkavl_rc_e 00339 mkavl_iter_cur(mkavl_iterator_handle iterator_h, void **item); 00340 00341 #endif
