1 /* 2 * Copyright (C) 2018 Alexander Borisov 3 * 4 * Author: Alexander Borisov <borisov@lexbor.com> 5 */ 6 7 #ifndef LEXBOR_BST_H 8 #define LEXBOR_BST_H 9 10 #ifdef __cplusplus 11 extern "C" { 12 #endif 13 14 #include <string.h> 15 16 #include "lexbor/core/base.h" 17 #include "lexbor/core/dobject.h" 18 19 20 #define lexbor_bst_root(bst) (bst)->root 21 #define lexbor_bst_root_ref(bst) &((bst)->root) 22 23 24 typedef struct lexbor_bst_entry lexbor_bst_entry_t; 25 typedef struct lexbor_bst lexbor_bst_t; 26 27 typedef bool (*lexbor_bst_entry_f)(lexbor_bst_t *bst, 28 lexbor_bst_entry_t *entry, void *ctx); 29 30 struct lexbor_bst_entry { 31 void *value; 32 33 lexbor_bst_entry_t *right; 34 lexbor_bst_entry_t *left; 35 lexbor_bst_entry_t *next; 36 lexbor_bst_entry_t *parent; 37 38 size_t size; 39 }; 40 41 struct lexbor_bst { 42 lexbor_dobject_t *dobject; 43 lexbor_bst_entry_t *root; 44 45 size_t tree_length; 46 }; 47 48 49 LXB_API lexbor_bst_t * 50 lexbor_bst_create(void); 51 52 LXB_API lxb_status_t 53 lexbor_bst_init(lexbor_bst_t *bst, size_t size); 54 55 LXB_API void 56 lexbor_bst_clean(lexbor_bst_t *bst); 57 58 LXB_API lexbor_bst_t * 59 lexbor_bst_destroy(lexbor_bst_t *bst, bool self_destroy); 60 61 LXB_API lexbor_bst_entry_t * 62 lexbor_bst_entry_make(lexbor_bst_t *bst, size_t size); 63 64 LXB_API lexbor_bst_entry_t * 65 lexbor_bst_insert(lexbor_bst_t *bst, lexbor_bst_entry_t **scope, 66 size_t size, void *value); 67 68 LXB_API lexbor_bst_entry_t * 69 lexbor_bst_insert_not_exists(lexbor_bst_t *bst, lexbor_bst_entry_t **scope, 70 size_t size); 71 72 73 LXB_API lexbor_bst_entry_t * 74 lexbor_bst_search(lexbor_bst_t *bst, lexbor_bst_entry_t *scope, size_t size); 75 76 LXB_API lexbor_bst_entry_t * 77 lexbor_bst_search_close(lexbor_bst_t *bst, lexbor_bst_entry_t *scope, 78 size_t size); 79 80 81 LXB_API void * 82 lexbor_bst_remove(lexbor_bst_t *bst, lexbor_bst_entry_t **root, size_t size); 83 84 LXB_API void * 85 lexbor_bst_remove_close(lexbor_bst_t *bst, lexbor_bst_entry_t **root, 86 size_t size, size_t *found_size); 87 88 LXB_API void * 89 lexbor_bst_remove_by_pointer(lexbor_bst_t *bst, lexbor_bst_entry_t *entry, 90 lexbor_bst_entry_t **root); 91 92 93 LXB_API void 94 lexbor_bst_serialize(lexbor_bst_t *bst, lexbor_callback_f callback, void *ctx); 95 96 LXB_API void 97 lexbor_bst_serialize_entry(lexbor_bst_entry_t *entry, 98 lexbor_callback_f callback, void *ctx, size_t tabs); 99 100 101 #ifdef __cplusplus 102 } /* extern "C" */ 103 #endif 104 105 #endif /* LEXBOR_BST_H */ 106 107 108 109
