Cleanup: harmless mistake in rangetree
[blender.git] / extern / rangetree / intern / range_tree.c
1 /*
2  * Copyright (c) 2016, Campbell Barton.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "Apache License")
5  * with the following modification; you may not use this file except in
6  * compliance with the Apache License and the following modification to it:
7  * Section 6. Trademarks. is deleted and replaced with:
8  *
9  * 6. Trademarks. This License does not grant permission to use the trade
10  *   names, trademarks, service marks, or product names of the Licensor
11  *   and its affiliates, except as required to comply with Section 4(c) of
12  *   the License and to reproduce the content of the NOTICE file.
13  *
14  * You may obtain a copy of the Apache License at
15  *
16  *    http://www.apache.org/licenses/LICENSE-2.0
17  *
18  * Unless required by applicable law or agreed to in writing, software
19  * distributed under the Apache License with the above modification is
20  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21  * KIND, either express or implied. See the Apache License for the specific
22  * language governing permissions and limitations under the Apache License.
23  */
24
25 #include <stdlib.h>
26 #include <stdbool.h>
27 #include <string.h>
28
29 #include <assert.h>
30
31 #include "range_tree.h"
32
33 typedef unsigned int uint;
34
35 /* Use binary-tree for lookups, else fallback to full search */
36 #define USE_BTREE
37 /* Use memory pool for nodes, else do individual allocations */
38 #define USE_TPOOL
39
40 /* Node representing a range in the RangeTreeUInt. */
41 typedef struct Node {
42         struct Node *next, *prev;
43
44         /* range (inclusive) */
45         uint min, max;
46
47 #ifdef USE_BTREE
48         /* Left leaning red-black tree, for reference implementation see:
49          * https://gitlab.com/ideasman42/btree-mini-py */
50         struct Node *left, *right;
51         /* RED/BLACK */
52         bool color;
53 #endif
54 } Node;
55
56 #ifdef USE_TPOOL
57 /* rt_pool_* pool allocator */
58 #define TPOOL_IMPL_PREFIX  rt_node
59 #define TPOOL_ALLOC_TYPE   Node
60 #define TPOOL_STRUCT       ElemPool_Node
61 #include "generic_alloc_impl.h"
62 #undef TPOOL_IMPL_PREFIX
63 #undef TPOOL_ALLOC_TYPE
64 #undef TPOOL_STRUCT
65 #endif  /* USE_TPOOL */
66
67 typedef struct LinkedList {
68         Node *first, *last;
69 } LinkedList;
70
71 typedef struct RangeTreeUInt {
72         uint range[2];
73         LinkedList list;
74 #ifdef USE_BTREE
75         Node *root;
76 #endif
77 #ifdef USE_TPOOL
78         struct ElemPool_Node epool;
79 #endif
80 } RangeTreeUInt;
81
82 /* ------------------------------------------------------------------------- */
83 /* List API */
84
85 static void list_push_front(LinkedList *list, Node *node)
86 {
87         if (list->first != NULL) {
88                 node->next = list->first;
89                 node->next->prev = node;
90                 node->prev = NULL;
91         }
92         else {
93                 list->last = node;
94         }
95         list->first = node;
96 }
97
98 static void list_push_back(LinkedList *list, Node *node)
99 {
100         if (list->first != NULL) {
101                 node->prev = list->last;
102                 node->prev->next = node;
103                 node->next = NULL;
104         }
105         else {
106                 list->first = node;
107         }
108         list->last = node;
109 }
110
111 static void list_push_after(LinkedList *list, Node *node_prev, Node *node_new)
112 {
113         /* node_new before node_next */
114
115         /* empty list */
116         if (list->first == NULL) {
117                 list->first = node_new;
118                 list->last = node_new;
119                 return;
120         }
121
122         /* insert at head of list */
123         if (node_prev == NULL) {
124                 node_new->prev = NULL;
125                 node_new->next = list->first;
126                 node_new->next->prev = node_new;
127                 list->first = node_new;
128                 return;
129         }
130
131         /* at end of list */
132         if (list->last == node_prev) {
133                 list->last = node_new;
134         }
135
136         node_new->next = node_prev->next;
137         node_new->prev = node_prev;
138         node_prev->next = node_new;
139         if (node_new->next) {
140                 node_new->next->prev = node_new;
141         }
142 }
143
144 static void list_push_before(LinkedList *list, Node *node_next, Node *node_new)
145 {
146         /* node_new before node_next */
147
148         /* empty list */
149         if (list->first == NULL) {
150                 list->first = node_new;
151                 list->last = node_new;
152                 return;
153         }
154
155         /* insert at end of list */
156         if (node_next == NULL) {
157                 node_new->prev = list->last;
158                 node_new->next = NULL;
159                 list->last->next = node_new;
160                 list->last = node_new;
161                 return;
162         }
163
164         /* at beginning of list */
165         if (list->first == node_next) {
166                 list->first = node_new;
167         }
168
169         node_new->next = node_next;
170         node_new->prev = node_next->prev;
171         node_next->prev = node_new;
172         if (node_new->prev) {
173                 node_new->prev->next = node_new;
174         }
175 }
176
177 static void list_remove(LinkedList *list, Node *node)
178 {
179         if (node->next != NULL) {
180                 node->next->prev = node->prev;
181         }
182         if (node->prev != NULL) {
183                 node->prev->next = node->next;
184         }
185
186         if (list->last == node) {
187                 list->last = node->prev;
188         }
189         if (list->first == node) {
190                 list->first = node->next;
191         }
192 }
193
194 static void list_clear(LinkedList *list)
195 {
196         list->first = NULL;
197         list->last = NULL;
198 }
199
200 /* end list API */
201
202
203 /* forward declarations */
204 static void rt_node_free(RangeTreeUInt *rt, Node *node);
205
206
207 #ifdef USE_BTREE
208
209 #ifdef DEBUG
210 static bool rb_is_balanced_root(const Node *root);
211 #endif
212
213 /* ------------------------------------------------------------------------- */
214 /* Internal BTree API
215  *
216  * Left-leaning red-black tree.
217  */
218
219 /* use minimum, could use max too since nodes never overlap */
220 #define KEY(n) ((n)->min)
221
222 enum {
223         RED = 0,
224         BLACK = 1,
225 };
226
227
228 static bool is_red(const Node *node)
229 {
230         return (node && (node->color == RED));
231 }
232
233 static int key_cmp(uint key1, uint key2)
234 {
235         return (key1 == key2) ? 0 : ((key1 < key2) ? -1 : 1);
236 }
237
238 /* removed from the tree */
239 static void rb_node_invalidate(Node *node)
240 {
241 #ifdef DEBUG
242         node->left = NULL;
243         node->right = NULL;
244         node->color = false;
245 #else
246         (void)node;
247 #endif
248 }
249
250 static void rb_flip_color(Node *node)
251 {
252         node->color ^= 1;
253         node->left->color ^= 1;
254         node->right->color ^= 1;
255 }
256
257 static Node *rb_rotate_left(Node *left)
258 {
259         /* Make a right-leaning 3-node lean to the left. */
260         Node *right = left->right;
261         left->right = right->left;
262         right->left = left;
263         right->color = left->color;
264         left->color = RED;
265         return right;
266 }
267
268 static Node *rb_rotate_right(Node *right)
269 {
270         /* Make a left-leaning 3-node lean to the right. */
271         Node *left = right->left;
272         right->left = left->right;
273         left->right = right;
274         left->color = right->color;
275         right->color = RED;
276         return left;
277 }
278
279 /* Fixup colors when insert happened */
280 static Node *rb_fixup_insert(Node *node)
281 {
282         if (is_red(node->right) && !is_red(node->left)) {
283                 node = rb_rotate_left(node);
284         }
285         if (is_red(node->left) && is_red(node->left->left)) {
286                 node = rb_rotate_right(node);
287         }
288
289         if (is_red(node->left) && is_red(node->right)) {
290                 rb_flip_color(node);
291         }
292
293         return node;
294 }
295
296 static Node *rb_insert_recursive(Node *node, Node *node_to_insert)
297 {
298         if (node == NULL) {
299                 return node_to_insert;
300         }
301
302         const int cmp = key_cmp(KEY(node_to_insert), KEY(node));
303         if (cmp == 0) {
304                 /* caller ensures no collisions */
305                 assert(0);
306         }
307         else if (cmp == -1) {
308                 node->left = rb_insert_recursive(node->left, node_to_insert);
309         }
310         else {
311                 node->right = rb_insert_recursive(node->right, node_to_insert);
312         }
313
314         return rb_fixup_insert(node);
315 }
316
317 static Node *rb_insert_root(Node *root, Node *node_to_insert)
318 {
319         root = rb_insert_recursive(root, node_to_insert);
320         root->color = BLACK;
321         return root;
322 }
323
324 static Node *rb_move_red_to_left(Node *node)
325 {
326         /* Assuming that h is red and both h->left and h->left->left
327          * are black, make h->left or one of its children red.
328          */
329         rb_flip_color(node);
330         if (node->right && is_red(node->right->left)) {
331                 node->right = rb_rotate_right(node->right);
332                 node = rb_rotate_left(node);
333                 rb_flip_color(node);
334         }
335         return node;
336 }
337
338 static Node *rb_move_red_to_right(Node *node)
339 {
340         /* Assuming that h is red and both h->right and h->right->left
341          * are black, make h->right or one of its children red.
342          */
343         rb_flip_color(node);
344         if (node->left && is_red(node->left->left)) {
345                 node = rb_rotate_right(node);
346                 rb_flip_color(node);
347         }
348         return node;
349 }
350
351 /* Fixup colors when remove happened */
352 static Node *rb_fixup_remove(Node *node)
353 {
354         if (is_red(node->right)) {
355                 node = rb_rotate_left(node);
356         }
357         if (is_red(node->left) && is_red(node->left->left)) {
358                 node = rb_rotate_right(node);
359         }
360         if (is_red(node->left) && is_red(node->right)) {
361                 rb_flip_color(node);
362         }
363         return node;
364 }
365
366 static Node *rb_pop_min_recursive(Node *node, Node **r_node_pop)
367 {
368         if (node == NULL) {
369                 return NULL;
370         }
371         if (node->left == NULL) {
372                 rb_node_invalidate(node);
373                 *r_node_pop = node;
374                 return NULL;
375         }
376         if ((!is_red(node->left)) && (!is_red(node->left->left))) {
377                 node = rb_move_red_to_left(node);
378         }
379         node->left = rb_pop_min_recursive(node->left, r_node_pop);
380         return rb_fixup_remove(node);
381 }
382
383 static Node *rb_remove_recursive(Node *node, const Node *node_to_remove)
384 {
385         if (node == NULL) {
386                 return NULL;
387         }
388         if (key_cmp(KEY(node_to_remove), KEY(node)) == -1) {
389                 if (node->left != NULL) {
390                         if ((!is_red(node->left)) && (!is_red(node->left->left))) {
391                                 node = rb_move_red_to_left(node);
392                         }
393                 }
394                 node->left = rb_remove_recursive(node->left, node_to_remove);
395         }
396         else {
397                 if (is_red(node->left)) {
398                         node = rb_rotate_right(node);
399                 }
400                 if ((node == node_to_remove) && (node->right == NULL)) {
401                         rb_node_invalidate(node);
402                         return NULL;
403                 }
404                 assert(node->right != NULL);
405                 if ((!is_red(node->right)) && (!is_red(node->right->left))) {
406                         node = rb_move_red_to_right(node);
407                 }
408
409                 if (node == node_to_remove) {
410                         /* minor improvement over original method:
411                          * no need to double lookup min */
412                         Node *node_free;  /* will always be set */
413                         node->right = rb_pop_min_recursive(node->right, &node_free);
414
415                         node_free->left = node->left;
416                         node_free->right = node->right;
417                         node_free->color = node->color;
418
419                         rb_node_invalidate(node);
420                         node = node_free;
421                 }
422                 else {
423                         node->right = rb_remove_recursive(node->right, node_to_remove);
424                 }
425         }
426         return rb_fixup_remove(node);
427 }
428
429 static Node *rb_btree_remove(Node *root, const Node *node_to_remove)
430 {
431         root = rb_remove_recursive(root, node_to_remove);
432         if (root != NULL) {
433                 root->color = BLACK;
434         }
435         return root;
436 }
437
438 /*
439  * Returns the node closest to and including 'key',
440  * excluding anything below.
441  */
442 static Node *rb_get_or_upper_recursive(Node *n, const uint key)
443 {
444         if (n == NULL) {
445                 return NULL;
446         }
447         const int cmp_upper = key_cmp(KEY(n), key);
448         if (cmp_upper == 0) {
449                 return n;  // exact match
450         }
451         else if (cmp_upper == 1) {
452                 assert(KEY(n) >= key);
453                 Node *n_test = rb_get_or_upper_recursive(n->left, key);
454                 return n_test ? n_test : n;
455         }
456         else {  // cmp_upper == -1
457                 return rb_get_or_upper_recursive(n->right, key);
458         }
459 }
460
461 /*
462  * Returns the node closest to and including 'key',
463  * excluding anything above.
464  */
465 static Node *rb_get_or_lower_recursive(Node *n, const uint key)
466 {
467         if (n == NULL) {
468                 return NULL;
469         }
470         const int cmp_lower = key_cmp(KEY(n), key);
471         if (cmp_lower == 0) {
472                 return n;  // exact match
473         }
474         else if (cmp_lower == -1) {
475                 assert(KEY(n) <= key);
476                 Node *n_test = rb_get_or_lower_recursive(n->right, key);
477                 return n_test ? n_test : n;
478         }
479         else {  // cmp_lower == 1
480                 return rb_get_or_lower_recursive(n->left, key);
481         }
482 }
483
484 #ifdef DEBUG
485
486 static bool rb_is_balanced_recursive(const Node *node, int black)
487 {
488         // Does every path from the root to a leaf have the given number
489         // of black links?
490         if (node == NULL) {
491                 return black == 0;
492         }
493         if (!is_red(node)) {
494                 black--;
495         }
496         return rb_is_balanced_recursive(node->left, black) &&
497                rb_is_balanced_recursive(node->right, black);
498 }
499
500 static bool rb_is_balanced_root(const Node *root)
501 {
502         // Do all paths from root to leaf have same number of black edges?
503         int black = 0;     // number of black links on path from root to min
504         const Node *node = root;
505         while (node != NULL) {
506                 if (!is_red(node)) {
507                         black++;
508                 }
509                 node = node->left;
510         }
511         return rb_is_balanced_recursive(root, black);
512 }
513
514 #endif  // DEBUG
515
516
517 /* End BTree API */
518 #endif  // USE_BTREE
519
520
521 /* ------------------------------------------------------------------------- */
522 /* Internal RangeTreeUInt API */
523
524 #ifdef _WIN32
525 #define inline __inline
526 #endif
527
528 static inline Node *rt_node_alloc(RangeTreeUInt *rt)
529 {
530 #ifdef USE_TPOOL
531         return rt_node_pool_elem_alloc(&rt->epool);
532 #else
533         (void)rt;
534         return malloc(sizeof(Node));
535 #endif
536 }
537
538 static Node *rt_node_new(RangeTreeUInt *rt, uint min, uint max)
539 {
540         Node *node = rt_node_alloc(rt);
541
542         assert(min <= max);
543         node->prev = NULL;
544         node->next = NULL;
545         node->min = min;
546         node->max = max;
547 #ifdef USE_BTREE
548         node->left = NULL;
549         node->right = NULL;
550 #endif
551         return node;
552 }
553
554 static void rt_node_free(RangeTreeUInt *rt, Node *node)
555 {
556 #ifdef USE_TPOOL
557         rt_node_pool_elem_free(&rt->epool, node);
558 #else
559         (void)rt;
560         free(node);
561 #endif
562 }
563
564 #ifdef USE_BTREE
565 static void rt_btree_insert(RangeTreeUInt *rt, Node *node)
566 {
567         node->color = RED;
568         node->left = NULL;
569         node->right = NULL;
570         rt->root = rb_insert_root(rt->root, node);
571 }
572 #endif
573
574 static void rt_node_add_back(RangeTreeUInt *rt, Node *node)
575 {
576         list_push_back(&rt->list, node);
577 #ifdef USE_BTREE
578         rt_btree_insert(rt, node);
579 #endif
580 }
581 static void rt_node_add_front(RangeTreeUInt *rt, Node *node)
582 {
583         list_push_front(&rt->list, node);
584 #ifdef USE_BTREE
585         rt_btree_insert(rt, node);
586 #endif
587 }
588 static void rt_node_add_before(RangeTreeUInt *rt, Node *node_next, Node *node)
589 {
590         list_push_before(&rt->list, node_next, node);
591 #ifdef USE_BTREE
592         rt_btree_insert(rt, node);
593 #endif
594 }
595 static void rt_node_add_after(RangeTreeUInt *rt, Node *node_prev, Node *node)
596 {
597         list_push_after(&rt->list, node_prev, node);
598 #ifdef USE_BTREE
599         rt_btree_insert(rt, node);
600 #endif
601 }
602
603 static void rt_node_remove(RangeTreeUInt *rt, Node *node)
604 {
605         list_remove(&rt->list, node);
606 #ifdef USE_BTREE
607         rt->root = rb_btree_remove(rt->root, node);
608 #endif
609         rt_node_free(rt, node);
610 }
611
612 static Node *rt_find_node_from_value(RangeTreeUInt *rt, const uint value)
613 {
614 #ifdef USE_BTREE
615         Node *node = rb_get_or_lower_recursive(rt->root, value);
616         if (node != NULL) {
617                 if ((value >= node->min) && (value <= node->max)) {
618                         return node;
619                 }
620         }
621         return NULL;
622 #else
623         for (Node *node = rt->list.first; node; node = node->next) {
624                 if ((value >= node->min) && (value <= node->max)) {
625                         return node;
626                 }
627         }
628         return NULL;
629 #endif // USE_BTREE
630 }
631
632 static void rt_find_node_pair_around_value(RangeTreeUInt *rt, const uint value,
633                                            Node **r_node_prev, Node **r_node_next)
634 {
635         if (value < rt->list.first->min) {
636                 *r_node_prev = NULL;
637                 *r_node_next = rt->list.first;
638                 return;
639         }
640         else if (value > rt->list.last->max) {
641                 *r_node_prev = rt->list.last;
642                 *r_node_next = NULL;
643                 return;
644         }
645         else {
646 #ifdef USE_BTREE
647                 Node *node_next = rb_get_or_upper_recursive(rt->root, value);
648                 if (node_next != NULL) {
649                         Node *node_prev = node_next->prev;
650                         if ((node_prev->max < value) && (value < node_next->min)) {
651                                 *r_node_prev = node_prev;
652                                 *r_node_next = node_next;
653                                 return;
654                         }
655                 }
656 #else
657                 Node *node_prev = rt->list.first;
658                 Node *node_next;
659                 while ((node_next = node_prev->next)) {
660                         if ((node_prev->max < value) && (value < node_next->min)) {
661                                 *r_node_prev = node_prev;
662                                 *r_node_next = node_next;
663                                 return;
664                         }
665                         node_prev = node_next;
666                 }
667 #endif // USE_BTREE
668         }
669         *r_node_prev = NULL;
670         *r_node_next = NULL;
671 }
672
673
674 /* ------------------------------------------------------------------------- */
675 /* Public API */
676
677 static RangeTreeUInt *rt_create_empty(uint min, uint max)
678 {
679         RangeTreeUInt *rt = malloc(sizeof(*rt));
680         rt->range[0] = min;
681         rt->range[1] = max;
682
683         list_clear(&rt->list);
684
685 #ifdef USE_BTREE
686         rt->root = NULL;
687 #endif
688 #ifdef USE_TPOOL
689         rt_node_pool_create(&rt->epool, 512);
690 #endif
691
692         return rt;
693 }
694
695 RangeTreeUInt *range_tree_uint_alloc(uint min, uint max)
696 {
697         RangeTreeUInt *rt = rt_create_empty(min, max);
698
699         Node *node = rt_node_new(rt, min, max);
700         rt_node_add_front(rt, node);
701         return rt;
702 }
703
704 void range_tree_uint_free(RangeTreeUInt *rt)
705 {
706 #ifdef DEBUG
707 #ifdef USE_BTREE
708         assert(rb_is_balanced_root(rt->root));
709 #endif
710 #endif
711
712 #ifdef USE_TPOOL
713
714         rt_node_pool_destroy(&rt->epool);
715 #else
716         for (Node *node = rt->list.first, *node_next; node; node = node_next) {
717                 node_next = node->next;
718                 rt_node_free(rt, node);
719         }
720 #endif
721
722         free(rt);
723 }
724
725 #ifdef USE_BTREE
726 static Node *rt_copy_recursive(RangeTreeUInt *rt_dst, const Node *node_src)
727 {
728         if (node_src == NULL) {
729                 return NULL;
730         }
731
732         Node *node_dst = rt_node_alloc(rt_dst);
733
734         *node_dst = *node_src;
735         node_dst->left = rt_copy_recursive(rt_dst, node_dst->left);
736         list_push_back(&rt_dst->list, node_dst);
737         node_dst->right = rt_copy_recursive(rt_dst, node_dst->right);
738
739         return node_dst;
740 }
741 #endif  // USE_BTREE
742
743 RangeTreeUInt *range_tree_uint_copy(const RangeTreeUInt *rt_src)
744 {
745         RangeTreeUInt *rt_dst = rt_create_empty(rt_src->range[0], rt_src->range[1]);
746 #ifdef USE_BTREE
747         rt_dst->root = rt_copy_recursive(rt_dst, rt_src->root);
748 #else
749         for (Node *node_src = rt_src->list.first; node_src; node_src = node_src->next) {
750                 Node *node_dst = rt_node_alloc(rt_dst);
751                 *node_dst = *node_src;
752                 list_push_back(&rt_dst->list, node_dst);
753         }
754 #endif
755         return rt_dst;
756 }
757
758 /**
759  * Return true if the tree has the value (not taken).
760  */
761 bool range_tree_uint_has(RangeTreeUInt *rt, const uint value)
762 {
763         assert(value >= rt->range[0] && value <= rt->range[1]);
764         Node *node = rt_find_node_from_value(rt, value);
765         return (node != NULL);
766 }
767
768 static void range_tree_uint_take_impl(RangeTreeUInt *rt, const uint value, Node *node)
769 {
770         assert(node == rt_find_node_from_value(rt, value));
771         if (node->min == value) {
772                 if (node->max != value) {
773                         node->min += 1;
774                 }
775                 else {
776                         assert(node->min == node->max);
777                         rt_node_remove(rt, node);
778                 }
779         }
780         else if (node->max == value) {
781                 node->max -= 1;
782         }
783         else {
784                 Node *node_next = rt_node_new(rt, value + 1, node->max);
785                 node->max = value - 1;
786                 rt_node_add_after(rt, node, node_next);
787         }
788 }
789
790 void range_tree_uint_take(RangeTreeUInt *rt, const uint value)
791 {
792         Node *node = rt_find_node_from_value(rt, value);
793         assert(node != NULL);
794         range_tree_uint_take_impl(rt, value, node);
795 }
796
797 bool range_tree_uint_retake(RangeTreeUInt *rt, const uint value)
798 {
799         Node *node = rt_find_node_from_value(rt, value);
800         if (node != NULL) {
801                 range_tree_uint_take_impl(rt, value, node);
802                 return true;
803         }
804         else {
805                 return false;
806         }
807 }
808
809 uint range_tree_uint_take_any(RangeTreeUInt *rt)
810 {
811         Node *node = rt->list.first;
812         uint value = node->min;
813         if (value == node->max) {
814                 rt_node_remove(rt, node);
815         }
816         else {
817                 node->min += 1;
818         }
819         return value;
820 }
821
822 void range_tree_uint_release(RangeTreeUInt *rt, const uint value)
823 {
824         bool touch_prev, touch_next;
825         Node *node_prev, *node_next;
826
827         if (rt->list.first != NULL) {
828                 rt_find_node_pair_around_value(rt, value, &node_prev, &node_next);
829                 /* the value must have been already taken */
830                 assert(node_prev || node_next);
831
832                 /* Cases:
833                  * 1) fill the gap between prev & next (two spans into one span).
834                  * 2) touching prev, (grow node_prev->max up one).
835                  * 3) touching next, (grow node_next->min down one).
836                  * 4) touching neither, add a new segment. */
837                 touch_prev = (node_prev != NULL && node_prev->max + 1 == value);
838                 touch_next = (node_next != NULL && node_next->min - 1 == value);
839         }
840         else {
841                 // we could handle this case (4) inline,
842                 // since its not a common case - use regular logic.
843                 node_prev = node_next = NULL;
844                 touch_prev = false;
845                 touch_next = false;
846         }
847
848         if (touch_prev && touch_next) {  // 1)
849                 node_prev->max = node_next->max;
850                 rt_node_remove(rt, node_next);
851         }
852         else if (touch_prev) {  // 2)
853                 assert(node_prev->max + 1 == value);
854                 node_prev->max = value;
855         }
856         else if (touch_next) {  // 3)
857                 assert(node_next->min - 1 == value);
858                 node_next->min = value;
859         }
860         else {  // 4)
861                 Node *node_new = rt_node_new(rt, value, value);
862                 if (node_prev != NULL) {
863                         rt_node_add_after(rt, node_prev, node_new);
864                 }
865                 else if (node_next != NULL) {
866                         rt_node_add_before(rt, node_next, node_new);
867                 }
868                 else {
869                         assert(rt->list.first == NULL);
870                         rt_node_add_back(rt, node_new);
871                 }
872         }
873 }