1 /*
2 * Copyright (C) 2018 Alexander Borisov
3 *
4 * Author: Alexander Borisov <borisov@lexbor.com>
5 */
6
7 #include "lexbor/core/bst_map.h"
8 #include "lexbor/core/utils.h"
9
10
11 lexbor_bst_map_t *
lexbor_bst_map_create(void)12 lexbor_bst_map_create(void)
13 {
14 return lexbor_calloc(1, sizeof(lexbor_bst_map_t));
15 }
16
17 lxb_status_t
lexbor_bst_map_init(lexbor_bst_map_t * bst_map,size_t size)18 lexbor_bst_map_init(lexbor_bst_map_t *bst_map, size_t size)
19 {
20 lxb_status_t status;
21
22 if (bst_map == NULL) {
23 return LXB_STATUS_ERROR_OBJECT_IS_NULL;
24 }
25
26 if (size == 0) {
27 return LXB_STATUS_ERROR_WRONG_ARGS;
28 }
29
30 /* bst */
31 bst_map->bst = lexbor_bst_create();
32 status = lexbor_bst_init(bst_map->bst, size);
33 if (status) {
34 return status;
35 }
36
37 /* dobject */
38 bst_map->entries = lexbor_dobject_create();
39 status = lexbor_dobject_init(bst_map->entries, size,
40 sizeof(lexbor_bst_map_entry_t));
41 if (status) {
42 return status;
43 }
44
45 /* mraw */
46 bst_map->mraw = lexbor_mraw_create();
47 status = lexbor_mraw_init(bst_map->mraw, (size * 6));
48 if (status) {
49 return status;
50 }
51
52 return LXB_STATUS_OK;
53 }
54
55 void
lexbor_bst_map_clean(lexbor_bst_map_t * bst_map)56 lexbor_bst_map_clean(lexbor_bst_map_t *bst_map)
57 {
58 lexbor_bst_clean(bst_map->bst);
59 lexbor_mraw_clean(bst_map->mraw);
60 lexbor_dobject_clean(bst_map->entries);
61 }
62
63 lexbor_bst_map_t *
lexbor_bst_map_destroy(lexbor_bst_map_t * bst_map,bool self_destroy)64 lexbor_bst_map_destroy(lexbor_bst_map_t *bst_map, bool self_destroy)
65 {
66 if (bst_map == NULL) {
67 return NULL;
68 }
69
70 bst_map->bst = lexbor_bst_destroy(bst_map->bst, true);
71 bst_map->mraw = lexbor_mraw_destroy(bst_map->mraw, true);
72 bst_map->entries = lexbor_dobject_destroy(bst_map->entries, true);
73
74 if (self_destroy) {
75 return lexbor_free(bst_map);
76 }
77
78 return bst_map;
79 }
80
81 lexbor_bst_map_entry_t *
lexbor_bst_map_search(lexbor_bst_map_t * bst_map,lexbor_bst_entry_t * scope,const lxb_char_t * key,size_t key_len)82 lexbor_bst_map_search(lexbor_bst_map_t *bst_map, lexbor_bst_entry_t *scope,
83 const lxb_char_t *key, size_t key_len)
84 {
85 lexbor_bst_map_entry_t *entry;
86 lexbor_bst_entry_t *bst_entry;
87
88 size_t hash_id = lexbor_utils_hash_hash(key, key_len);
89
90 bst_entry = lexbor_bst_search(bst_map->bst, scope, hash_id);
91 if (bst_entry == NULL) {
92 return NULL;
93 }
94
95 do {
96 entry = bst_entry->value;
97
98 if (entry->str.length == key_len &&
99 lexbor_str_data_cmp(entry->str.data, key))
100 {
101 return entry;
102 }
103
104 bst_entry = bst_entry->next;
105 }
106 while (bst_entry != NULL);
107
108 return NULL;
109 }
110
111 lexbor_bst_map_entry_t *
lexbor_bst_map_insert(lexbor_bst_map_t * bst_map,lexbor_bst_entry_t ** scope,const lxb_char_t * key,size_t key_len,void * value)112 lexbor_bst_map_insert(lexbor_bst_map_t *bst_map,
113 lexbor_bst_entry_t **scope,
114 const lxb_char_t *key, size_t key_len, void *value)
115 {
116 lexbor_bst_map_entry_t *entry;
117
118 entry = lexbor_bst_map_insert_not_exists(bst_map, scope, key, key_len);
119 if (entry == NULL) {
120 return NULL;
121 }
122
123 entry->value = value;
124
125 return entry;
126 }
127
128 lexbor_bst_map_entry_t *
lexbor_bst_map_insert_not_exists(lexbor_bst_map_t * bst_map,lexbor_bst_entry_t ** scope,const lxb_char_t * key,size_t key_len)129 lexbor_bst_map_insert_not_exists(lexbor_bst_map_t *bst_map,
130 lexbor_bst_entry_t **scope,
131 const lxb_char_t *key, size_t key_len)
132 {
133 lexbor_bst_map_entry_t *entry;
134 lexbor_bst_entry_t *bst_entry;
135
136 size_t hash_id = lexbor_utils_hash_hash(key, key_len);
137
138 bst_entry = lexbor_bst_insert_not_exists(bst_map->bst, scope, hash_id);
139 if (bst_entry == NULL) {
140 return NULL;
141 }
142
143 if (bst_entry->value == NULL) {
144 goto new_entry;
145 }
146
147 do {
148 entry = bst_entry->value;
149
150 if (entry->str.length == key_len &&
151 lexbor_str_data_cmp(entry->str.data, key))
152 {
153 return entry;
154 }
155
156 if (bst_entry->next == NULL) {
157 bst_entry->next = lexbor_bst_entry_make(bst_map->bst, hash_id);
158 bst_entry = bst_entry->next;
159
160 if (bst_entry == NULL) {
161 return NULL;
162 }
163
164 goto new_entry;
165 }
166
167 bst_entry = bst_entry->next;
168 }
169 while (1);
170
171 return NULL;
172
173 new_entry:
174
175 entry = lexbor_dobject_calloc(bst_map->entries);
176 if (entry == NULL) {
177 return NULL;
178 }
179
180 lexbor_str_init(&entry->str, bst_map->mraw, key_len);
181 if (entry->str.data == NULL) {
182 lexbor_dobject_free(bst_map->entries, entry);
183
184 return NULL;
185 }
186
187 lexbor_str_append(&entry->str, bst_map->mraw, key, key_len);
188
189 bst_entry->value = entry;
190
191 return entry;
192 }
193
194 void *
lexbor_bst_map_remove(lexbor_bst_map_t * bst_map,lexbor_bst_entry_t ** scope,const lxb_char_t * key,size_t key_len)195 lexbor_bst_map_remove(lexbor_bst_map_t *bst_map, lexbor_bst_entry_t **scope,
196 const lxb_char_t *key, size_t key_len)
197 {
198 lexbor_bst_map_entry_t *entry;
199 lexbor_bst_entry_t *bst_entry;
200
201 size_t hash_id = lexbor_utils_hash_hash(key, key_len);
202
203 bst_entry = lexbor_bst_search(bst_map->bst, *scope, hash_id);
204 if (bst_entry == NULL) {
205 return NULL;
206 }
207
208 do {
209 entry = bst_entry->value;
210
211 if (entry->str.length == key_len &&
212 lexbor_str_data_cmp(entry->str.data, key))
213 {
214 void *value = entry->value;
215
216 lexbor_bst_remove_by_pointer(bst_map->bst, bst_entry, scope);
217
218 lexbor_str_destroy(&entry->str, bst_map->mraw, false);
219 lexbor_dobject_free(bst_map->entries, entry);
220
221 return value;
222 }
223
224 bst_entry = bst_entry->next;
225 }
226 while (bst_entry != NULL);
227
228 return NULL;
229 }
230
231 /*
232 * No inline functions.
233 */
234 lexbor_mraw_t *
lexbor_bst_map_mraw_noi(lexbor_bst_map_t * bst_map)235 lexbor_bst_map_mraw_noi(lexbor_bst_map_t *bst_map)
236 {
237 return lexbor_bst_map_mraw(bst_map);
238 }
239
