1 /* 2 * Copyright (C) 2018 Alexander Borisov 3 * 4 * Author: Alexander Borisov <borisov@lexbor.com> 5 */ 6 7 #ifndef LEXBOR_AVL_H 8 #define LEXBOR_AVL_H 9 10 #ifdef __cplusplus 11 extern "C" { 12 #endif 13 14 #include "lexbor/core/base.h" 15 #include "lexbor/core/dobject.h" 16 17 18 typedef struct lexbor_avl lexbor_avl_t; 19 typedef struct lexbor_avl_node lexbor_avl_node_t; 20 21 typedef lxb_status_t 22 (*lexbor_avl_node_f)(lexbor_avl_t *avl, lexbor_avl_node_t **root, 23 lexbor_avl_node_t *node, void *ctx); 24 25 struct lexbor_avl_node { 26 size_t type; 27 short height; 28 void *value; 29 30 lexbor_avl_node_t *left; 31 lexbor_avl_node_t *right; 32 lexbor_avl_node_t *parent; 33 }; 34 35 struct lexbor_avl { 36 lexbor_dobject_t *nodes; 37 lexbor_avl_node_t *last_right; 38 }; 39 40 41 LXB_API lexbor_avl_t * 42 lexbor_avl_create(void); 43 44 LXB_API lxb_status_t 45 lexbor_avl_init(lexbor_avl_t *avl, size_t chunk_len, size_t struct_size); 46 47 LXB_API void 48 lexbor_avl_clean(lexbor_avl_t *avl); 49 50 LXB_API lexbor_avl_t * 51 lexbor_avl_destroy(lexbor_avl_t *avl, bool self_destroy); 52 53 54 LXB_API lexbor_avl_node_t * 55 lexbor_avl_node_make(lexbor_avl_t *avl, size_t type, void *value); 56 57 LXB_API void 58 lexbor_avl_node_clean(lexbor_avl_node_t *node); 59 60 LXB_API lexbor_avl_node_t * 61 lexbor_avl_node_destroy(lexbor_avl_t *avl, lexbor_avl_node_t *node, 62 bool self_destroy); 63 64 65 LXB_API lexbor_avl_node_t * 66 lexbor_avl_insert(lexbor_avl_t *avl, lexbor_avl_node_t **scope, 67 size_t type, void *value); 68 69 LXB_API lexbor_avl_node_t * 70 lexbor_avl_search(lexbor_avl_t *avl, lexbor_avl_node_t *scope, size_t type); 71 72 LXB_API void * 73 lexbor_avl_remove(lexbor_avl_t *avl, lexbor_avl_node_t **scope, size_t type); 74 75 LXB_API void 76 lexbor_avl_remove_by_node(lexbor_avl_t *avl, lexbor_avl_node_t **root, 77 lexbor_avl_node_t *node); 78 79 LXB_API lxb_status_t 80 lexbor_avl_foreach(lexbor_avl_t *avl, lexbor_avl_node_t **scope, 81 lexbor_avl_node_f cb, void *ctx); 82 83 LXB_API void 84 lexbor_avl_foreach_recursion(lexbor_avl_t *avl, lexbor_avl_node_t *scope, 85 lexbor_avl_node_f callback, void *ctx); 86 87 88 #ifdef __cplusplus 89 } /* extern "C" */ 90 #endif 91 92 #endif /* LEXBOR_AVL_H */ 93
