1 /*
2 * Copyright (C) 2018-2022 Alexander Borisov
3 *
4 * Author: Alexander Borisov <borisov@lexbor.com>
5 */
6
7 #include "lexbor/core/avl.h"
8
9
10 lxb_inline short
11 lexbor_avl_node_height(lexbor_avl_node_t *node);
12
13 lxb_inline short
14 lexbor_avl_node_balance_factor(lexbor_avl_node_t *node);
15
16 lxb_inline void
17 lexbor_avl_node_set_height(lexbor_avl_node_t *node);
18
19 static lexbor_avl_node_t *
20 lexbor_avl_node_rotate_right(lexbor_avl_node_t *pos);
21
22 static lexbor_avl_node_t *
23 lexbor_avl_node_rotate_left(lexbor_avl_node_t *pos);
24
25 static lexbor_avl_node_t *
26 lexbor_avl_node_balance(lexbor_avl_node_t *node,
27 lexbor_avl_node_t **scope);
28
29 lxb_inline lexbor_avl_node_t *
30 lexbor_avl_find_min(lexbor_avl_node_t *node);
31
32 lxb_inline void
33 lexbor_avl_rotate_for_delete(lexbor_avl_node_t *delete_node,
34 lexbor_avl_node_t *node,
35 lexbor_avl_node_t **root);
36
37
38 lexbor_avl_t *
lexbor_avl_create(void)39 lexbor_avl_create(void)
40 {
41 return lexbor_calloc(1, sizeof(lexbor_avl_t));
42 }
43
44 lxb_status_t
lexbor_avl_init(lexbor_avl_t * avl,size_t chunk_len,size_t struct_size)45 lexbor_avl_init(lexbor_avl_t *avl, size_t chunk_len, size_t struct_size)
46 {
47 if (avl == NULL) {
48 return LXB_STATUS_ERROR_OBJECT_IS_NULL;
49 }
50
51 if (chunk_len == 0
52 || (struct_size != 0 && struct_size < sizeof(lexbor_avl_node_t)))
53 {
54 return LXB_STATUS_ERROR_WRONG_ARGS;
55 }
56
57 if (struct_size == 0) {
58 struct_size = sizeof(lexbor_avl_node_t);
59 }
60
61 avl->last_right = NULL;
62
63 avl->nodes = lexbor_dobject_create();
64 return lexbor_dobject_init(avl->nodes, chunk_len, struct_size);
65 }
66
67 void
lexbor_avl_clean(lexbor_avl_t * avl)68 lexbor_avl_clean(lexbor_avl_t *avl)
69 {
70 avl->last_right = NULL;
71
72 lexbor_dobject_clean(avl->nodes);
73 }
74
75 lexbor_avl_t *
lexbor_avl_destroy(lexbor_avl_t * avl,bool self_destroy)76 lexbor_avl_destroy(lexbor_avl_t *avl, bool self_destroy)
77 {
78 if (avl == NULL)
79 return NULL;
80
81 avl->nodes = lexbor_dobject_destroy(avl->nodes, true);
82
83 if (self_destroy) {
84 return lexbor_free(avl);
85 }
86
87 return avl;
88 }
89
90 lexbor_avl_node_t *
lexbor_avl_node_make(lexbor_avl_t * avl,size_t type,void * value)91 lexbor_avl_node_make(lexbor_avl_t *avl, size_t type, void *value)
92 {
93 lexbor_avl_node_t *node = lexbor_dobject_calloc(avl->nodes);
94 if (node == NULL) {
95 return NULL;
96 }
97
98 node->type = type;
99 node->value = value;
100
101 return node;
102 }
103
104 void
lexbor_avl_node_clean(lexbor_avl_node_t * node)105 lexbor_avl_node_clean(lexbor_avl_node_t *node)
106 {
107 memset(node, 0, sizeof(lexbor_avl_node_t));
108 }
109
110 lexbor_avl_node_t *
lexbor_avl_node_destroy(lexbor_avl_t * avl,lexbor_avl_node_t * node,bool self_destroy)111 lexbor_avl_node_destroy(lexbor_avl_t *avl,
112 lexbor_avl_node_t *node, bool self_destroy)
113 {
114 if (node == NULL) {
115 return NULL;
116 }
117
118 if (self_destroy) {
119 return lexbor_dobject_free(avl->nodes, node);
120 }
121
122 return node;
123 }
124
125 lxb_inline short
lexbor_avl_node_height(lexbor_avl_node_t * node)126 lexbor_avl_node_height(lexbor_avl_node_t *node)
127 {
128 return (node) ? node->height : 0;
129 }
130
131 lxb_inline short
lexbor_avl_node_balance_factor(lexbor_avl_node_t * node)132 lexbor_avl_node_balance_factor(lexbor_avl_node_t *node)
133 {
134 return (lexbor_avl_node_height(node->right)
135 - lexbor_avl_node_height(node->left));
136 }
137
138 lxb_inline void
lexbor_avl_node_set_height(lexbor_avl_node_t * node)139 lexbor_avl_node_set_height(lexbor_avl_node_t *node)
140 {
141 short left_height = lexbor_avl_node_height(node->left);
142 short right_height = lexbor_avl_node_height(node->right);
143
144 node->height = ((left_height > right_height)
145 ? left_height : right_height) + 1;
146 }
147
148 static lexbor_avl_node_t *
lexbor_avl_node_rotate_right(lexbor_avl_node_t * pos)149 lexbor_avl_node_rotate_right(lexbor_avl_node_t *pos)
150 {
151 lexbor_avl_node_t *node = pos->left;
152
153 node->parent = pos->parent;
154
155 if (node->right) {
156 node->right->parent = pos;
157 }
158
159 pos->left = node->right;
160 pos->parent = node;
161
162 node->right = pos;
163
164 lexbor_avl_node_set_height(pos);
165 lexbor_avl_node_set_height(node);
166
167 return node;
168 }
169
170 static lexbor_avl_node_t *
lexbor_avl_node_rotate_left(lexbor_avl_node_t * pos)171 lexbor_avl_node_rotate_left(lexbor_avl_node_t *pos)
172 {
173 lexbor_avl_node_t *node = pos->right;
174
175 node->parent = pos->parent;
176
177 if (node->left) {
178 node->left->parent = pos;
179 }
180
181 pos->right = node->left;
182 pos->parent = node;
183
184 node->left = pos;
185
186 lexbor_avl_node_set_height(pos);
187 lexbor_avl_node_set_height(node);
188
189 return node;
190 }
191
192 static lexbor_avl_node_t *
lexbor_avl_node_balance(lexbor_avl_node_t * node,lexbor_avl_node_t ** scope)193 lexbor_avl_node_balance(lexbor_avl_node_t *node, lexbor_avl_node_t **scope)
194 {
195 /* Set height */
196 lexbor_avl_node_t *parent;
197
198 short left_height = lexbor_avl_node_height(node->left);
199 short right_height = lexbor_avl_node_height(node->right);
200
201 node->height = ((left_height > right_height)
202 ? left_height : right_height) + 1;
203
204 /* Check balance */
205 switch ((right_height - left_height)) {
206 case 2: {
207 if (lexbor_avl_node_balance_factor(node->right) < 0) {
208 node->right = lexbor_avl_node_rotate_right(node->right);
209 }
210
211 parent = node->parent;
212
213 if (parent != NULL) {
214 if (parent->right == node) {
215 parent->right = lexbor_avl_node_rotate_left(node);
216 return parent->right;
217 }
218 else {
219 parent->left = lexbor_avl_node_rotate_left(node);
220 return parent->left;
221 }
222 }
223
224 return lexbor_avl_node_rotate_left(node);
225 }
226 case -2: {
227 if (lexbor_avl_node_balance_factor(node->left) > 0) {
228 node->left = lexbor_avl_node_rotate_left(node->left);
229 }
230
231 parent = node->parent;
232
233 if (parent != NULL) {
234 if (parent->right == node) {
235 parent->right = lexbor_avl_node_rotate_right(node);
236 return parent->right;
237 }
238 else {
239 parent->left = lexbor_avl_node_rotate_right(node);
240 return parent->left;
241 }
242 }
243
244 return lexbor_avl_node_rotate_right(node);
245 }
246 default:
247 break;
248 }
249
250 if (node->parent == NULL) {
251 *scope = node;
252 }
253
254 return node->parent;
255 }
256
257 lexbor_avl_node_t *
lexbor_avl_insert(lexbor_avl_t * avl,lexbor_avl_node_t ** scope,size_t type,void * value)258 lexbor_avl_insert(lexbor_avl_t *avl, lexbor_avl_node_t **scope,
259 size_t type, void *value)
260 {
261 lexbor_avl_node_t *node, *new_node;
262
263 if (*scope == NULL) {
264 *scope = lexbor_avl_node_make(avl, type, value);
265 return *scope;
266 }
267
268 node = *scope;
269 new_node = lexbor_dobject_calloc(avl->nodes);
270
271 for (;;) {
272 if (type == node->type) {
273 node->value = value;
274 return node;
275 }
276 else if (type < node->type) {
277 if (node->left == NULL) {
278 node->left = new_node;
279
280 new_node->parent = node;
281 new_node->type = type;
282 new_node->value = value;
283
284 node = new_node;
285 break;
286 }
287
288 node = node->left;
289 }
290 else {
291 if (node->right == NULL) {
292 node->right = new_node;
293
294 new_node->parent = node;
295 new_node->type = type;
296 new_node->value = value;
297
298 node = new_node;
299 break;
300 }
301
302 node = node->right;
303 }
304 }
305
306 while (node != NULL) {
307 node = lexbor_avl_node_balance(node, scope);
308 }
309
310 return new_node;
311 }
312
313 lxb_inline lexbor_avl_node_t *
lexbor_avl_find_min(lexbor_avl_node_t * node)314 lexbor_avl_find_min(lexbor_avl_node_t *node)
315 {
316 if (node == NULL) {
317 return NULL;
318 }
319
320 while (node->right != NULL) {
321 node = node->right;
322 }
323
324 return node;
325 }
326
327 lxb_inline void
lexbor_avl_rotate_for_delete(lexbor_avl_node_t * delete_node,lexbor_avl_node_t * node,lexbor_avl_node_t ** scope)328 lexbor_avl_rotate_for_delete(lexbor_avl_node_t *delete_node,
329 lexbor_avl_node_t *node, lexbor_avl_node_t **scope)
330 {
331 lexbor_avl_node_t *balance_node;
332
333 if (node) {
334 if (delete_node->left == node) {
335 balance_node = (node->left) ? node->left : node;
336
337 node->parent = delete_node->parent;
338 node->right = delete_node->right;
339
340 if (delete_node->right)
341 delete_node->right->parent = node;
342 }
343 else {
344 balance_node = node;
345
346 node->parent->right = NULL;
347
348 node->parent = delete_node->parent;
349 node->right = delete_node->right;
350 node->left = delete_node->left;
351
352 if (delete_node->left != NULL) {
353 delete_node->left->parent = node;
354 }
355
356 if (delete_node->right != NULL) {
357 delete_node->right->parent = node;
358 }
359 }
360
361 if (delete_node->parent != NULL) {
362 if (delete_node->parent->left == delete_node) {
363 delete_node->parent->left = node;
364 }
365 else {
366 delete_node->parent->right = node;
367 }
368 }
369 else {
370 *scope = node;
371 }
372 }
373 else {
374 balance_node = delete_node->parent;
375
376 if (balance_node != NULL) {
377 if (balance_node->left == delete_node) {
378 balance_node->left = delete_node->right;
379 }
380 else {
381 balance_node->right = delete_node->right;
382 }
383 }
384 else {
385 *scope = delete_node->right;
386 }
387
388 if (delete_node->right != NULL) {
389 delete_node->right->parent = balance_node;
390 }
391 }
392
393 while (balance_node != NULL) {
394 balance_node = lexbor_avl_node_balance(balance_node, scope);
395 }
396 }
397
398 void *
lexbor_avl_remove(lexbor_avl_t * avl,lexbor_avl_node_t ** scope,size_t type)399 lexbor_avl_remove(lexbor_avl_t *avl, lexbor_avl_node_t **scope, size_t type)
400 {
401 void *value;
402 lexbor_avl_node_t *node = *scope;
403
404 while (node != NULL) {
405 if (type == node->type) {
406 avl->last_right = lexbor_avl_find_min(node->left);
407 lexbor_avl_rotate_for_delete(node, avl->last_right, scope);
408
409 value = node->value;
410 lexbor_dobject_free(avl->nodes, node);
411
412 return value;
413 }
414 else if (type < node->type) {
415 node = node->left;
416 }
417 else {
418 node = node->right;
419 }
420 }
421
422 return NULL;
423 }
424
425 void
lexbor_avl_remove_by_node(lexbor_avl_t * avl,lexbor_avl_node_t ** root,lexbor_avl_node_t * node)426 lexbor_avl_remove_by_node(lexbor_avl_t *avl, lexbor_avl_node_t **root,
427 lexbor_avl_node_t *node)
428 {
429 avl->last_right = lexbor_avl_find_min(node->left);
430
431 lexbor_avl_rotate_for_delete(node, avl->last_right, root);
432
433 (void) lexbor_dobject_free(avl->nodes, node);
434 }
435
436 lexbor_avl_node_t *
lexbor_avl_search(lexbor_avl_t * avl,lexbor_avl_node_t * node,size_t type)437 lexbor_avl_search(lexbor_avl_t *avl, lexbor_avl_node_t *node, size_t type)
438 {
439 while (node != NULL) {
440 if (type == node->type) {
441 return node;
442 }
443 else if (type < node->type) {
444 node = node->left;
445 }
446 else {
447 node = node->right;
448 }
449 }
450
451 return NULL;
452 }
453
454 lxb_status_t
lexbor_avl_foreach(lexbor_avl_t * avl,lexbor_avl_node_t ** scope,lexbor_avl_node_f cb,void * ctx)455 lexbor_avl_foreach(lexbor_avl_t *avl, lexbor_avl_node_t **scope,
456 lexbor_avl_node_f cb, void *ctx)
457 {
458 lxb_status_t status;
459 int state = 0;
460 bool from_right = false;
461 lexbor_avl_node_t *node, *parent, *root;
462
463 if (scope == NULL || *scope == NULL) {
464 return LXB_STATUS_ERROR_WRONG_ARGS;
465 }
466
467 node = *scope;
468 root = node;
469
470 while (node->left != NULL) {
471 node = node->left;
472 }
473
474 do {
475 parent = node->parent;
476
477 if (!from_right) {
478 if (node == root) {
479 state = 2;
480 }
481 else {
482 state = parent->left == node;
483 }
484
485 status = cb(avl, scope, node, ctx);
486 if (status != LXB_STATUS_OK) {
487 return status;
488 }
489
490 if (state == 2) {
491 if (*scope != root) {
492 root = *scope;
493
494 if (root == NULL) {
495 return LXB_STATUS_OK;
496 }
497 else if (avl->last_right == root) {
498 node = root;
499 }
500 else {
501 node = root;
502 continue;
503 }
504 }
505 }
506 else if (parent->left != node && parent->right != node) {
507 if (state) {
508 if (parent->left != NULL && parent->left->right != NULL) {
509 node = parent->left;
510 }
511 else {
512 node = parent;
513 continue;
514 }
515 }
516 else {
517 if (parent->right != NULL) {
518 node = parent->right;
519
520 if (node != avl->last_right) {
521 continue;
522 }
523 }
524 else {
525 node = parent;
526 }
527 }
528 }
529 }
530
531 if (node->right != NULL && !from_right) {
532 node = node->right;
533
534 while (node->left != NULL) {
535 node = node->left;
536 }
537
538 continue;
539 }
540
541 if (parent == root->parent) {
542 return LXB_STATUS_OK;
543 }
544 else if (node == parent->left) {
545 from_right = false;
546 }
547 else {
548 from_right = true;
549 }
550
551 node = parent;
552 }
553 while (true);
554 }
555
556 void
lexbor_avl_foreach_recursion(lexbor_avl_t * avl,lexbor_avl_node_t * scope,lexbor_avl_node_f callback,void * ctx)557 lexbor_avl_foreach_recursion(lexbor_avl_t *avl, lexbor_avl_node_t *scope,
558 lexbor_avl_node_f callback, void *ctx)
559 {
560 if (scope == NULL) {
561 return;
562 }
563
564 callback(avl, NULL, scope, ctx);
565
566 lexbor_avl_foreach_recursion(avl, scope->left, callback, ctx);
567 lexbor_avl_foreach_recursion(avl, scope->right, callback, ctx);
568 }
569