1 /*
2 * Copyright (C) 2018 Alexander Borisov
3 *
4 * Author: Alexander Borisov <borisov@lexbor.com>
5 */
6
7 #include "lexbor/core/bst.h"
8 #include "lexbor/core/conv.h"
9
10
11 lexbor_bst_t *
lexbor_bst_create(void)12 lexbor_bst_create(void)
13 {
14 return lexbor_calloc(1, sizeof(lexbor_bst_t));
15 }
16
17 lxb_status_t
lexbor_bst_init(lexbor_bst_t * bst,size_t size)18 lexbor_bst_init(lexbor_bst_t *bst, size_t size)
19 {
20 lxb_status_t status;
21
22 if (bst == 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->dobject = lexbor_dobject_create();
31 status = lexbor_dobject_init(bst->dobject, size,
32 sizeof(lexbor_bst_entry_t));
33 if (status != LXB_STATUS_OK) {
34 return status;
35 }
36
37 bst->root = 0;
38 bst->tree_length = 0;
39
40 return LXB_STATUS_OK;
41 }
42
43 void
lexbor_bst_clean(lexbor_bst_t * bst)44 lexbor_bst_clean(lexbor_bst_t *bst)
45 {
46 if (bst != NULL) {
47 lexbor_dobject_clean(bst->dobject);
48
49 bst->root = 0;
50 bst->tree_length = 0;
51 }
52 }
53
54 lexbor_bst_t *
lexbor_bst_destroy(lexbor_bst_t * bst,bool self_destroy)55 lexbor_bst_destroy(lexbor_bst_t *bst, bool self_destroy)
56 {
57 if (bst == NULL) {
58 return NULL;
59 }
60
61 bst->dobject = lexbor_dobject_destroy(bst->dobject, true);
62
63 if (self_destroy) {
64 return lexbor_free(bst);
65 }
66
67 return bst;
68 }
69
70 lexbor_bst_entry_t *
lexbor_bst_entry_make(lexbor_bst_t * bst,size_t size)71 lexbor_bst_entry_make(lexbor_bst_t *bst, size_t size)
72 {
73 lexbor_bst_entry_t *new_entry = lexbor_dobject_calloc(bst->dobject);
74 if (new_entry == NULL) {
75 return NULL;
76 }
77
78 new_entry->size = size;
79
80 bst->tree_length++;
81
82 return new_entry;
83 }
84
85 lexbor_bst_entry_t *
lexbor_bst_insert(lexbor_bst_t * bst,lexbor_bst_entry_t ** scope,size_t size,void * value)86 lexbor_bst_insert(lexbor_bst_t *bst, lexbor_bst_entry_t **scope,
87 size_t size, void *value)
88 {
89 lexbor_bst_entry_t *new_entry, *entry;
90
91 new_entry = lexbor_dobject_calloc(bst->dobject);
92 if (new_entry == NULL) {
93 return NULL;
94 }
95
96 new_entry->size = size;
97 new_entry->value = value;
98
99 bst->tree_length++;
100
101 if (*scope == NULL) {
102 *scope = new_entry;
103 return new_entry;
104 }
105
106 entry = *scope;
107
108 while (entry != NULL) {
109 if (size == entry->size) {
110 if (entry->next) {
111 new_entry->next = entry->next;
112 }
113
114 entry->next = new_entry;
115 new_entry->parent = entry->parent;
116
117 return new_entry;
118 }
119 else if (size > entry->size) {
120 if (entry->right == NULL) {
121 entry->right = new_entry;
122 new_entry->parent = entry;
123
124 return new_entry;
125 }
126
127 entry = entry->right;
128 }
129 else {
130 if (entry->left == NULL) {
131 entry->left = new_entry;
132 new_entry->parent = entry;
133
134 return new_entry;
135 }
136
137 entry = entry->left;
138 }
139 }
140
141 return NULL;
142 }
143
144 lexbor_bst_entry_t *
lexbor_bst_insert_not_exists(lexbor_bst_t * bst,lexbor_bst_entry_t ** scope,size_t size)145 lexbor_bst_insert_not_exists(lexbor_bst_t *bst, lexbor_bst_entry_t **scope,
146 size_t size)
147 {
148 lexbor_bst_entry_t *entry;
149
150 if (*scope == NULL) {
151 *scope = lexbor_bst_entry_make(bst, size);
152
153 return *scope;
154 }
155
156 entry = *scope;
157
158 while (entry != NULL) {
159 if (size == entry->size) {
160 return entry;
161 }
162 else if (size > entry->size) {
163 if (entry->right == NULL) {
164 entry->right = lexbor_bst_entry_make(bst, size);
165 entry->right->parent = entry;
166
167 return entry->right;
168 }
169
170 entry = entry->right;
171 }
172 else {
173 if (entry->left == NULL) {
174 entry->left = lexbor_bst_entry_make(bst, size);
175 entry->left->parent = entry;
176
177 return entry->left;
178 }
179
180 entry = entry->left;
181 }
182 }
183
184 return NULL;
185 }
186
187 lexbor_bst_entry_t *
lexbor_bst_search(lexbor_bst_t * bst,lexbor_bst_entry_t * scope,size_t size)188 lexbor_bst_search(lexbor_bst_t *bst, lexbor_bst_entry_t *scope, size_t size)
189 {
190 while (scope != NULL) {
191 if (scope->size == size) {
192 return scope;
193 }
194 else if (size > scope->size) {
195 scope = scope->right;
196 }
197 else {
198 scope = scope->left;
199 }
200 }
201
202 return NULL;
203 }
204
205 lexbor_bst_entry_t *
lexbor_bst_search_close(lexbor_bst_t * bst,lexbor_bst_entry_t * scope,size_t size)206 lexbor_bst_search_close(lexbor_bst_t *bst, lexbor_bst_entry_t *scope,
207 size_t size)
208 {
209 lexbor_bst_entry_t *max = NULL;
210
211 while (scope != NULL) {
212 if (scope->size == size) {
213 return scope;
214 }
215 else if (size > scope->size) {
216 scope = scope->right;
217 }
218 else {
219 max = scope;
220 scope = scope->left;
221 }
222 }
223
224 return max;
225 }
226
227 void *
lexbor_bst_remove(lexbor_bst_t * bst,lexbor_bst_entry_t ** scope,size_t size)228 lexbor_bst_remove(lexbor_bst_t *bst, lexbor_bst_entry_t **scope, size_t size)
229 {
230 lexbor_bst_entry_t *entry = *scope;
231
232 while (entry != NULL) {
233 if (entry->size == size) {
234 return lexbor_bst_remove_by_pointer(bst, entry, scope);
235 }
236 else if (size > entry->size) {
237 entry = entry->right;
238 }
239 else {
240 entry = entry->left;
241 }
242 }
243
244 return NULL;
245 }
246
247 void *
lexbor_bst_remove_close(lexbor_bst_t * bst,lexbor_bst_entry_t ** scope,size_t size,size_t * found_size)248 lexbor_bst_remove_close(lexbor_bst_t *bst, lexbor_bst_entry_t **scope,
249 size_t size, size_t *found_size)
250 {
251 lexbor_bst_entry_t *entry = *scope;
252 lexbor_bst_entry_t *max = NULL;
253
254 while (entry != NULL) {
255 if (entry->size == size) {
256 if (found_size) {
257 *found_size = entry->size;
258 }
259
260 return lexbor_bst_remove_by_pointer(bst, entry, scope);
261 }
262 else if (size > entry->size) {
263 entry = entry->right;
264 }
265 else {
266 max = entry;
267 entry = entry->left;
268 }
269 }
270
271 if (max != NULL) {
272 if (found_size != NULL) {
273 *found_size = max->size;
274 }
275
276 return lexbor_bst_remove_by_pointer(bst, max, scope);
277 }
278
279 if (found_size != NULL) {
280 *found_size = 0;
281 }
282
283 return NULL;
284 }
285
286 void *
lexbor_bst_remove_by_pointer(lexbor_bst_t * bst,lexbor_bst_entry_t * entry,lexbor_bst_entry_t ** root)287 lexbor_bst_remove_by_pointer(lexbor_bst_t *bst, lexbor_bst_entry_t *entry,
288 lexbor_bst_entry_t **root)
289 {
290 void *value;
291 lexbor_bst_entry_t *next, *right, *left;
292
293 bst->tree_length--;
294
295 if (entry->next != NULL) {
296 next = entry->next;
297 entry->next = entry->next->next;
298
299 value = next->value;
300
301 lexbor_dobject_free(bst->dobject, next);
302
303 return value;
304 }
305
306 value = entry->value;
307
308 if (entry->left == NULL && entry->right == NULL) {
309 if (entry->parent != NULL) {
310 if (entry->parent->left == entry) entry->parent->left = NULL;
311 if (entry->parent->right == entry) entry->parent->right = NULL;
312 }
313 else {
314 *root = NULL;
315 }
316
317 lexbor_dobject_free(bst->dobject, entry);
318 }
319 else if (entry->left == NULL) {
320 if (entry->parent == NULL) {
321 entry->right->parent = NULL;
322
323 *root = entry->right;
324
325 lexbor_dobject_free(bst->dobject, entry);
326
327 entry = *root;
328 }
329 else {
330 right = entry->right;
331 right->parent = entry->parent;
332
333 memcpy(entry, right, sizeof(lexbor_bst_entry_t));
334
335 lexbor_dobject_free(bst->dobject, right);
336 }
337
338 if (entry->right != NULL) {
339 entry->right->parent = entry;
340 }
341
342 if (entry->left != NULL) {
343 entry->left->parent = entry;
344 }
345 }
346 else if (entry->right == NULL) {
347 if (entry->parent == NULL) {
348 entry->left->parent = NULL;
349
350 *root = entry->left;
351
352 lexbor_dobject_free(bst->dobject, entry);
353
354 entry = *root;
355 }
356 else {
357 left = entry->left;
358 left->parent = entry->parent;
359
360 memcpy(entry, left, sizeof(lexbor_bst_entry_t));
361
362 lexbor_dobject_free(bst->dobject, left);
363 }
364
365 if (entry->right != NULL) {
366 entry->right->parent = entry;
367 }
368
369 if (entry->left != NULL) {
370 entry->left->parent = entry;
371 }
372 }
373 else {
374 left = entry->right;
375
376 while (left->left != NULL) {
377 left = left->left;
378 }
379
380 /* Swap */
381 entry->size = left->size;
382 entry->next = left->next;
383 entry->value = left->value;
384
385 /* Change parrent */
386 if (entry->right == left) {
387 entry->right = left->right;
388
389 if (entry->right != NULL) {
390 left->right->parent = entry;
391 }
392 }
393 else {
394 left->parent->left = left->right;
395
396 if (left->right != NULL) {
397 left->right->parent = left->parent;
398 }
399 }
400
401 lexbor_dobject_free(bst->dobject, left);
402 }
403
404 return value;
405 }
406
407 void
lexbor_bst_serialize(lexbor_bst_t * bst,lexbor_callback_f callback,void * ctx)408 lexbor_bst_serialize(lexbor_bst_t *bst, lexbor_callback_f callback, void *ctx)
409 {
410 lexbor_bst_serialize_entry(bst->root, callback, ctx, 0);
411 }
412
413 void
lexbor_bst_serialize_entry(lexbor_bst_entry_t * entry,lexbor_callback_f callback,void * ctx,size_t tabs)414 lexbor_bst_serialize_entry(lexbor_bst_entry_t *entry,
415 lexbor_callback_f callback, void *ctx, size_t tabs)
416 {
417 size_t len;
418 lxb_char_t buff[1024];
419
420 if (entry == NULL) {
421 return;
422 }
423
424 /* Left */
425 for (size_t i = 0; i < tabs; i++) {
426 callback((lxb_char_t *) "\t", 1, ctx);
427 }
428 callback((lxb_char_t *) "<left ", 6, ctx);
429
430 if (entry->left) {
431 len = lexbor_conv_int64_to_data((int64_t) entry->left->size,
432 buff, sizeof(buff));
433 callback(buff, len, ctx);
434
435 callback((lxb_char_t *) ">\n", 2, ctx);
436 lexbor_bst_serialize_entry(entry->left, callback, ctx, (tabs + 1));
437
438 for (size_t i = 0; i < tabs; i++) {
439 callback((lxb_char_t *) "\t", 1, ctx);
440 }
441 }
442 else {
443 callback((lxb_char_t *) "NULL>", 5, ctx);
444 }
445
446 callback((lxb_char_t *) "</left>\n", 8, ctx);
447
448 /* Right */
449 for (size_t i = 0; i < tabs; i++) {
450 callback((lxb_char_t *) "\t", 1, ctx);
451 }
452 callback((lxb_char_t *) "<right ", 7, ctx);
453
454 if (entry->right) {
455 len = lexbor_conv_int64_to_data((int64_t) entry->right->size,
456 buff, sizeof(buff));
457 callback(buff, len, ctx);
458
459 callback((lxb_char_t *) ">\n", 2, ctx);
460 lexbor_bst_serialize_entry(entry->right, callback, ctx, (tabs + 1));
461
462 for (size_t i = 0; i < tabs; i++) {
463 callback((lxb_char_t *) "\t", 1, ctx);
464 }
465 }
466 else {
467 callback((lxb_char_t *) "NULL>", 5, ctx);
468 }
469
470 callback((lxb_char_t *) "</right>\n", 9, ctx);
471 }
472
