diff options
| author | luwenpeng <[email protected]> | 2024-03-27 17:11:38 +0800 |
|---|---|---|
| committer | luwenpeng <[email protected]> | 2024-03-27 17:16:59 +0800 |
| commit | 814a0d739f566c064828a695edcdb1be78c523de (patch) | |
| tree | ee4789958f3fec3842ad762518e416f708dd60e7 /deps | |
| parent | eb281ab7897d2181a2740163d00d55728da968d3 (diff) | |
Add linux kernel interval tree
Diffstat (limited to 'deps')
| -rw-r--r-- | deps/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | deps/interval_tree/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | deps/interval_tree/interval.cpp | 71 | ||||
| -rw-r--r-- | deps/interval_tree/interval.h | 59 | ||||
| -rw-r--r-- | deps/interval_tree/interval_list.cpp | 277 | ||||
| -rw-r--r-- | deps/interval_tree/interval_list.h | 57 | ||||
| -rw-r--r-- | deps/interval_tree/interval_tree.cpp | 10 | ||||
| -rw-r--r-- | deps/interval_tree/interval_tree.h | 33 | ||||
| -rw-r--r-- | deps/interval_tree/interval_tree_generic.h | 197 | ||||
| -rw-r--r-- | deps/interval_tree/itree.cpp | 628 | ||||
| -rw-r--r-- | deps/interval_tree/itree.h | 75 | ||||
| -rw-r--r-- | deps/interval_tree/test/gtest_interval_tree.cpp | 406 | ||||
| -rw-r--r-- | deps/list/list.h | 356 | ||||
| -rw-r--r-- | deps/rbtree/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | deps/rbtree/rbtree.cpp | 624 | ||||
| -rw-r--r-- | deps/rbtree/rbtree.h | 383 | ||||
| -rw-r--r-- | deps/rbtree/rbtree_augmented.h | 320 |
17 files changed, 2072 insertions, 1431 deletions
diff --git a/deps/CMakeLists.txt b/deps/CMakeLists.txt index d703aef..3c9947a 100644 --- a/deps/CMakeLists.txt +++ b/deps/CMakeLists.txt @@ -1,4 +1,5 @@ add_subdirectory(timeout) add_subdirectory(dablooms) add_subdirectory(toml) +add_subdirectory(rbtree) add_subdirectory(interval_tree)
\ No newline at end of file diff --git a/deps/interval_tree/CMakeLists.txt b/deps/interval_tree/CMakeLists.txt index 7a6de00..2b297fa 100644 --- a/deps/interval_tree/CMakeLists.txt +++ b/deps/interval_tree/CMakeLists.txt @@ -1,4 +1,6 @@ -add_library(interval_tree STATIC interval.cpp interval_list.cpp itree.cpp) +add_library(interval_tree STATIC interval_tree.cpp) target_include_directories(interval_tree PUBLIC ${CMAKE_CURRENT_LIST_DIR}) +target_include_directories(interval_tree PUBLIC ${CMAKE_SOURCE_DIR}/deps/rbtree) +target_link_libraries(interval_tree rbtree) add_subdirectory(test)
\ No newline at end of file diff --git a/deps/interval_tree/interval.cpp b/deps/interval_tree/interval.cpp deleted file mode 100644 index 4fc7ddf..0000000 --- a/deps/interval_tree/interval.cpp +++ /dev/null @@ -1,71 +0,0 @@ -/* - * Libitree: an interval tree library in C - * - * Copyright (C) 2018 Alessandro Vullo - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#include "interval.h" - -#include <stdlib.h> - -interval_t *interval_new(uint64_t low, uint64_t high, void *data, dup_f dup, rel_f rel) -{ - interval_t *ri = (interval_t *)malloc(sizeof *ri); - if (ri == NULL) - { - return NULL; - } - - ri->low = low; - ri->high = high; - ri->dup = dup; - ri->rel = rel; - ri->data = ri->dup(data); - - return ri; -} - -interval_t *interval_copy(const interval_t *i) -{ - return interval_new(i->low, i->high, i->data, i->dup, i->rel); -} - -void interval_delete(interval_t *i) -{ - if (i != NULL) - { - if (i->data) - { - i->rel(i->data); - } - free(i); - } -} - -int interval_overlap(const interval_t *i1, const interval_t *i2) -{ - return i1->low <= i2->high && i2->low <= i1->high; -} - -int interval_equal(const interval_t *i1, const interval_t *i2) -{ - return i1->low == i2->low && i1->high == i2->high && i1->data == i2->data; -} diff --git a/deps/interval_tree/interval.h b/deps/interval_tree/interval.h deleted file mode 100644 index 4504c7c..0000000 --- a/deps/interval_tree/interval.h +++ /dev/null @@ -1,59 +0,0 @@ -/* - * Libitree: an interval tree library in C - * - * Copyright (C) 2018 Alessandro Vullo - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#ifndef _INTERVAL_H_ -#define _INTERVAL_H_ - -#ifdef __cplusplus -extern "C" -{ -#endif - -#include <stddef.h> -#include <stdint.h> - -/* User-defined item handling */ -typedef void *(*dup_f)(void *p); -typedef void (*rel_f)(void *p); - -typedef struct interval -{ - uint64_t low, high; /* Interval boundaries, inclusive */ - void *data; /* User-defined content */ - dup_f dup; /* Clone an interval data item */ - rel_f rel; /* Destroy an interval data item */ -} interval_t; - -/* Interval functions */ -interval_t *interval_new(uint64_t low, uint64_t high, void *data, dup_f dup, rel_f rel); -interval_t *interval_copy(const interval_t *i); -void interval_delete(interval_t *i); -int interval_overlap(const interval_t *i1, const interval_t *i2); -int interval_equal(const interval_t *i1, const interval_t *i2); - -#ifdef __cplusplus -} -#endif - -#endif /* _INTERVAL_H_ */ diff --git a/deps/interval_tree/interval_list.cpp b/deps/interval_tree/interval_list.cpp deleted file mode 100644 index 6700564..0000000 --- a/deps/interval_tree/interval_list.cpp +++ /dev/null @@ -1,277 +0,0 @@ -/* - * Libitree: an interval tree library in C - * - * Copyright (C) 2018 Alessandro Vullo - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#include "interval_list.h" - -#include <stdlib.h> -#include <stdio.h> - -#ifndef HEIGHT_LIMIT -#define HEIGHT_LIMIT 64 -#endif - -/* Note: doesn't own the interval, comes from the tree - which is responsible for deallocating the interval. */ -typedef struct ilistnode -{ - const interval_t *interval; - struct ilistnode *next; -} ilistnode_t; - -struct ilist -{ - ilistnode_t *head, *tail; /* Dummy nodes */ - size_t size; -}; - -struct ilisttrav -{ - ilist_t *list; /* Paired list */ - ilistnode_t *it; /* Current node */ -}; - -static ilistnode_t *ilistnode_new(const interval_t *i, ilistnode_t *next) -{ - ilistnode_t *node = (ilistnode_t *)malloc(sizeof *node); - if (node != NULL) - { - node->interval = i; /* NOTE: doesn't own the interval, pointer aliasing */ - node->next = next; - } - - return node; -} - -/* - Destroy a single node, assuming it's been unlinked. - Returns the next node specified by the link. -*/ -ilistnode_t *ilistnode_delete(ilistnode_t *node) -{ - ilistnode_t *next = NULL; - if (node != NULL) - { - /* Save a reference to the next node - since we're about to destroy this one */ - next = node->next; - free(node); - } - - return next; -} - -ilist_t *ilist_new() -{ - ilist_t *list = (ilist_t *)malloc(sizeof *list); - if (list != NULL) - { - ilistnode_t *tail = ilistnode_new(NULL, NULL); - if (tail == NULL) - { - free(list); - list = NULL; - } - else - { - list->tail = tail; - list->head = ilistnode_new(NULL, list->tail); - - if (list->head == NULL) - { - free(list); - list = NULL; - } - list->size = 0; - } - } - - return list; -} - -void ilist_delete(ilist_t *list) -{ - if (list == NULL) - { - return; - } - - ilistnode_t *it = list->head; - while (it != list->tail) - { - it = ilistnode_delete(it); - } - - ilistnode_delete(it); /* Delete tail */ - free(list); -} - -size_t ilist_size(ilist_t *list) -{ - return list->size; -} - -static ilistnode_t *insert_before(ilist_t *, ilistnode_t *, interval_t *); -static ilistnode_t *insert_after(ilist_t *list, ilistnode_t *pos, interval_t *i) -{ - ilistnode_t *node = NULL; - if (list != NULL && pos != NULL) - { - if (pos != list->tail) - { - node = ilistnode_new(i, pos->next); - if (node != NULL) - { - pos->next = node; - ++list->size; - } - } - else - { - node = insert_before(list, pos, i); - } - } - - return node; -} - -static ilistnode_t *insert_before(ilist_t *list, ilistnode_t *pos, interval_t *i) -{ - ilistnode_t *node = NULL; - if (list != NULL && pos != NULL) - { - if (pos != list->head) - { - /* Find the previous node */ - ilistnode_t *it = list->head; - while (it->next != pos) - { - it = it->next; - } - - /* Create a new node and set the new link */ - node = ilistnode_new(i, it->next); - if (node != NULL) - { - it->next = node; - ++list->size; - } - } - else - { - node = insert_after(list, pos, i); - } - } - - return node; -} - -int ilist_append(ilist_t *list, interval_t *i) -{ - - ilistnode_t *node = insert_before(list, list->tail, i); - if (node != NULL) - { - return 1; - } - - return 0; -} - -ilisttrav_t *ilisttrav_new(ilist_t *list) -{ - if (list == NULL) - { - return NULL; - } - - ilisttrav_t *trav = (ilisttrav_t *)malloc(sizeof(ilisttrav_t)); - if (trav != NULL) - { - trav->list = list; - } - - return trav; -} - -void ilisttrav_delete(ilisttrav_t *trav) -{ - free(trav); -} - -const interval_t *ilisttrav_first(ilisttrav_t *trav) -{ - if (trav->list == NULL) - { - return NULL; - } - - trav->it = trav->list->head->next; - - return trav->it == NULL || trav->it == trav->list->tail ? NULL : trav->it->interval; -} - -const interval_t *ilisttrav_last(ilisttrav_t *trav) -{ - if (trav->list == NULL) - { - return NULL; - } - - trav->it = trav->list->head; - while (trav->it->next != trav->list->tail) - { - trav->it = trav->it->next; - } - - return trav->it == trav->list->head || trav->it == NULL ? NULL : trav->it->interval; -} - -const interval_t *ilisttrav_next(ilisttrav_t *trav) -{ - if (trav == NULL) - { - return NULL; - } - - trav->it = trav->it->next; - return trav->it == NULL || trav->it == trav->list->tail ? NULL : trav->it->interval; -} - -/* Very inefficient, need a doubly linked list to properly support this */ -const interval_t *ilisttrav_prev(ilisttrav_t *trav) -{ - if (trav == NULL) - { - return NULL; - } - - ilistnode_t *it = trav->list->head; - while (it->next != trav->it) - { - it = it->next; - } - - trav->it = it; - return trav->it == trav->list->head || trav->it == NULL ? NULL : trav->it->interval; -} diff --git a/deps/interval_tree/interval_list.h b/deps/interval_tree/interval_list.h deleted file mode 100644 index 7333419..0000000 --- a/deps/interval_tree/interval_list.h +++ /dev/null @@ -1,57 +0,0 @@ -/* - * Libitree: an interval tree library in C - * - * Copyright (C) 2018 Alessandro Vullo - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#ifndef _INTERVAL_LIST_H_ -#define _INTERVAL_LIST_H_ - -#ifdef __cplusplus -extern "C" -{ -#endif - -#include "interval.h" - -/* Declarations for an interval list, opaque types */ -typedef struct ilist ilist_t; -typedef struct ilisttrav ilisttrav_t; - -/* Interval list functions */ -ilist_t *ilist_new(); -void ilist_delete(ilist_t *list); -size_t ilist_size(ilist_t *list); -int ilist_append(ilist_t *list, interval_t *i); - -/* Interval list traversal functions */ -ilisttrav_t *ilisttrav_new(ilist_t *list); -void ilisttrav_delete(ilisttrav_t *trav); -const interval_t *ilisttrav_first(ilisttrav_t *trav); -const interval_t *ilisttrav_last(ilisttrav_t *trav); -const interval_t *ilisttrav_next(ilisttrav_t *trav); -const interval_t *ilisttrav_prev(ilisttrav_t *trav); - -#ifdef __cplusplus -} -#endif - -#endif /* _INTERVAL_LIST_H_ */ diff --git a/deps/interval_tree/interval_tree.cpp b/deps/interval_tree/interval_tree.cpp new file mode 100644 index 0000000..da6d2c5 --- /dev/null +++ b/deps/interval_tree/interval_tree.cpp @@ -0,0 +1,10 @@ +// SPDX-License-Identifier: GPL-2.0-only +#include "interval_tree.h" +#include "interval_tree_generic.h" + +#define START(node) ((node)->start) +#define LAST(node) ((node)->last) + +INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, + uint64_t, __subtree_last, + START, LAST, , interval_tree) diff --git a/deps/interval_tree/interval_tree.h b/deps/interval_tree/interval_tree.h new file mode 100644 index 0000000..0b3d169 --- /dev/null +++ b/deps/interval_tree/interval_tree.h @@ -0,0 +1,33 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_INTERVAL_TREE_H +#define _LINUX_INTERVAL_TREE_H + +#include "rbtree.h" +#include <stdint.h> + +struct interval_tree_node +{ + struct rb_node rb; + uint64_t start; /* Start of interval */ + uint64_t last; /* Last location _in_ interval */ + uint64_t __subtree_last; + void *user_data; +}; + +extern void +interval_tree_insert(struct interval_tree_node *node, + struct rb_root_cached *root); + +extern void +interval_tree_remove(struct interval_tree_node *node, + struct rb_root_cached *root); + +extern struct interval_tree_node * +interval_tree_iter_first(struct rb_root_cached *root, + uint64_t start, uint64_t last); + +extern struct interval_tree_node * +interval_tree_iter_next(struct interval_tree_node *node, + uint64_t start, uint64_t last); + +#endif /* _LINUX_INTERVAL_TREE_H */ diff --git a/deps/interval_tree/interval_tree_generic.h b/deps/interval_tree/interval_tree_generic.h new file mode 100644 index 0000000..872c264 --- /dev/null +++ b/deps/interval_tree/interval_tree_generic.h @@ -0,0 +1,197 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* + Interval Trees + (C) 2012 Michel Lespinasse <[email protected]> + + + include/linux/interval_tree_generic.h +*/ + +#include "rbtree_augmented.h" + +/* + * Template for implementing interval trees + * + * ITSTRUCT: struct type of the interval tree nodes + * ITRB: name of struct rb_node field within ITSTRUCT + * ITTYPE: type of the interval endpoints + * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree + * ITSTART(n): start endpoint of ITSTRUCT node n + * ITLAST(n): last endpoint of ITSTRUCT node n + * ITSTATIC: 'static' or empty + * ITPREFIX: prefix to use for the inline tree definitions + * + * Note - before using this, please consider if generic version + * (interval_tree.h) would work for you... + */ + +#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \ + ITSTART, ITLAST, ITSTATIC, ITPREFIX) \ + \ + /* Callbacks for augmented rbtree insert and remove */ \ + \ + RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX##_augment, \ + ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \ + \ + /* Insert / remove interval nodes from the tree */ \ + \ + ITSTATIC void ITPREFIX##_insert(ITSTRUCT *node, \ + struct rb_root_cached *root) \ + { \ + struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \ + ITTYPE start = ITSTART(node), last = ITLAST(node); \ + ITSTRUCT *parent; \ + bool leftmost = true; \ + \ + while (*link) \ + { \ + rb_parent = *link; \ + parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \ + if (parent->ITSUBTREE < last) \ + parent->ITSUBTREE = last; \ + if (start < ITSTART(parent)) \ + link = &parent->ITRB.rb_left; \ + else \ + { \ + link = &parent->ITRB.rb_right; \ + leftmost = false; \ + } \ + } \ + \ + node->ITSUBTREE = last; \ + rb_link_node(&node->ITRB, rb_parent, link); \ + rb_insert_augmented_cached(&node->ITRB, root, \ + leftmost, &ITPREFIX##_augment); \ + } \ + \ + ITSTATIC void ITPREFIX##_remove(ITSTRUCT *node, \ + struct rb_root_cached *root) \ + { \ + rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX##_augment); \ + } \ + \ + /* \ + * Iterate over intervals intersecting [start;last] \ + * \ + * Note that a node's interval intersects [start;last] iff: \ + * Cond1: ITSTART(node) <= last \ + * and \ + * Cond2: start <= ITLAST(node) \ + */ \ + \ + static ITSTRUCT * \ + ITPREFIX##_subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ + { \ + while (true) \ + { \ + /* \ + * Loop invariant: start <= node->ITSUBTREE \ + * (Cond2 is satisfied by one of the subtree nodes) \ + */ \ + if (node->ITRB.rb_left) \ + { \ + ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \ + ITSTRUCT, ITRB); \ + if (start <= left->ITSUBTREE) \ + { \ + /* \ + * Some nodes in left subtree satisfy Cond2. \ + * Iterate to find the leftmost such node N. \ + * If it also satisfies Cond1, that's the \ + * match we are looking for. Otherwise, there \ + * is no matching interval as nodes to the \ + * right of N can't satisfy Cond1 either. \ + */ \ + node = left; \ + continue; \ + } \ + } \ + if (ITSTART(node) <= last) \ + { /* Cond1 */ \ + if (start <= ITLAST(node)) /* Cond2 */ \ + return node; /* node is leftmost match */ \ + if (node->ITRB.rb_right) \ + { \ + node = rb_entry(node->ITRB.rb_right, \ + ITSTRUCT, ITRB); \ + if (start <= node->ITSUBTREE) \ + continue; \ + } \ + } \ + return NULL; /* No match */ \ + } \ + } \ + \ + ITSTATIC ITSTRUCT * \ + ITPREFIX##_iter_first(struct rb_root_cached *root, \ + ITTYPE start, ITTYPE last) \ + { \ + ITSTRUCT *node, *leftmost; \ + \ + if (!root->rb_root.rb_node) \ + return NULL; \ + \ + /* \ + * Fastpath range intersection/overlap between A: [a0, a1] and \ + * B: [b0, b1] is given by: \ + * \ + * a0 <= b1 && b0 <= a1 \ + * \ + * ... where A holds the lock range and B holds the smallest \ + * 'start' and largest 'last' in the tree. For the later, we \ + * rely on the root node, which by augmented interval tree \ + * property, holds the largest value in its last-in-subtree. \ + * This allows mitigating some of the tree walk overhead for \ + * for non-intersecting ranges, maintained and consulted in O(1). \ + */ \ + node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \ + if (node->ITSUBTREE < start) \ + return NULL; \ + \ + leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \ + if (ITSTART(leftmost) > last) \ + return NULL; \ + \ + return ITPREFIX##_subtree_search(node, start, last); \ + } \ + \ + ITSTATIC ITSTRUCT * \ + ITPREFIX##_iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ + { \ + struct rb_node *rb = node->ITRB.rb_right, *prev; \ + \ + while (true) \ + { \ + /* \ + * Loop invariants: \ + * Cond1: ITSTART(node) <= last \ + * rb == node->ITRB.rb_right \ + * \ + * First, search right subtree if suitable \ + */ \ + if (rb) \ + { \ + ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \ + if (start <= right->ITSUBTREE) \ + return ITPREFIX##_subtree_search(right, \ + start, last); \ + } \ + \ + /* Move up the tree until we come from a node's left child */ \ + do \ + { \ + rb = rb_parent(&node->ITRB); \ + if (!rb) \ + return NULL; \ + prev = &node->ITRB; \ + node = rb_entry(rb, ITSTRUCT, ITRB); \ + rb = node->ITRB.rb_right; \ + } while (prev == rb); \ + \ + /* Check if the node intersects [start;last] */ \ + if (last < ITSTART(node)) /* !Cond1 */ \ + return NULL; \ + else if (start <= ITLAST(node)) /* Cond2 */ \ + return node; \ + } \ + } diff --git a/deps/interval_tree/itree.cpp b/deps/interval_tree/itree.cpp deleted file mode 100644 index 9d7bf74..0000000 --- a/deps/interval_tree/itree.cpp +++ /dev/null @@ -1,628 +0,0 @@ -/* - * Libitree: an interval tree library in C - * - * Copyright (C) 2018 Alessandro Vullo - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -/* - Interval Tree library - - This is an adaptation of the AVL balanced tree C library - created by Julienne Walker which can be found here: - - http://www.eternallyconfuzzled.com/Libraries.aspx - -*/ - -#include "itree.h" - -#include <stdlib.h> - -#ifndef HEIGHT_LIMIT -#define HEIGHT_LIMIT 64 /* Tallest allowable tree */ -#endif - -typedef struct itreenode -{ - int balance; /* Balance factor */ - uint64_t max; /* Maximum high value in the subtree rooted at this node */ - interval_t *interval; /* The interval the node represents */ - struct itreenode *link[2]; /* Left (0) and right (1) links */ -} itreenode_t; - -struct itree -{ - itreenode_t *root; /* Top of the tree */ - dup_f dup; /* Clone an interval data item (user-defined) */ - rel_f rel; /* Destroy an interval data item (user-defined) */ - size_t size; /* Number of items (user-defined) */ -}; - -struct itreetrav -{ - itree_t *tree; /* Paired tree */ - itreenode_t *it; /* Current node */ - itreenode_t *path[HEIGHT_LIMIT]; /* Traversal path */ - size_t top; /* Top of stack */ -}; - -/* Two way single rotation */ -#define single(root, dir) \ - do \ - { \ - itreenode_t *save = root->link[!dir]; \ - root->link[!dir] = save->link[dir]; \ - save->link[dir] = root; \ - root = save; \ - } while (0) - -/* Two way double rotation */ -#define double(root, dir) \ - do \ - { \ - itreenode_t *save = root->link[!dir]->link[dir]; \ - root->link[!dir]->link[dir] = save->link[!dir]; \ - save->link[!dir] = root->link[!dir]; \ - root->link[!dir] = save; \ - save = root->link[!dir]; \ - root->link[!dir] = save->link[dir]; \ - save->link[dir] = root; \ - root = save; \ - } while (0) - -/* Adjust balance before double rotation */ -#define adjust_balance(root, dir, bal) \ - do \ - { \ - itreenode_t *n = root->link[dir]; \ - itreenode_t *nn = n->link[!dir]; \ - if (nn->balance == 0) \ - { \ - root->balance = n->balance = 0; \ - } \ - else if (nn->balance == bal) \ - { \ - root->balance = -bal; \ - n->balance = 0; \ - } \ - else \ - { /* nn->balance == -bal */ \ - root->balance = 0; \ - n->balance = bal; \ - } \ - nn->balance = 0; \ - } while (0) - -/* Rebalance after insertion */ -#define insert_balance(root, dir) \ - do \ - { \ - itreenode_t *n = root->link[dir]; \ - int bal = dir == 0 ? -1 : +1; \ - if (n->balance == bal) \ - { \ - root->balance = n->balance = 0; \ - single(root, !dir); \ - } \ - else \ - { /* n->balance == -bal */ \ - adjust_balance(root, dir, bal); \ - double(root, !dir); \ - } \ - } while (0) - -/* Rebalance after deletion */ -#define remove_balance(root, dir, done) \ - do \ - { \ - itreenode_t *n = root->link[!dir]; \ - int bal = dir == 0 ? -1 : +1; \ - if (n->balance == -bal) \ - { \ - root->balance = n->balance = 0; \ - single(root, dir); \ - } \ - else if (n->balance == bal) \ - { \ - adjust_balance(root, !dir, -bal); \ - double(root, dir); \ - } \ - else \ - { /* n->balance == 0 */ \ - root->balance = -bal; \ - n->balance = bal; \ - single(root, dir); \ - done = 1; \ - } \ - } while (0) - -static itreenode_t *new_node(itree_t *tree, interval_t *i) -{ - itreenode_t *rn = (itreenode_t *)malloc(sizeof *rn); - if (rn == NULL) - { - return NULL; - } - - rn->interval = (interval_t *)malloc(sizeof(interval_t)); - if (rn->interval == NULL) - { - return NULL; - } - - rn->interval->low = i->low; - rn->interval->high = i->high; - rn->interval->data = tree->dup(i->data); - - rn->balance = 0; - rn->max = i->high; - rn->link[0] = rn->link[1] = NULL; - - return rn; -} - -itree_t *itree_new(dup_f dup, rel_f rel) -{ - itree_t *rt = (itree_t *)malloc(sizeof *rt); - if (rt == NULL) - { - return NULL; - } - - rt->root = NULL; - rt->dup = dup; - rt->rel = rel; - rt->size = 0; - - return rt; -} - -void itree_delete(itree_t *tree) -{ - itreenode_t *it = tree->root; - itreenode_t *save; - - /* Destruction by rotation */ - while (it != NULL) - { - if (it->link[0] == NULL) - { - /* Remove node */ - save = it->link[1]; - tree->rel(it->interval->data); - free(it->interval); - free(it); - } - else - { - /* Rotate right */ - save = it->link[0]; - it->link[0] = save->link[1]; - save->link[1] = it; - } - - it = save; - } - - free(tree); -} - -interval_t *itree_find(itree_t *tree, interval_t *interval) -{ - itreenode_t *it = tree->root; - while (it != NULL) - { - /* int cmp = tree->cmp ( it->data, data ); */ - - /* if ( cmp == 0 ) */ - /* break; */ - - /* it = it->link[cmp < 0]; */ - - if (interval_overlap(it->interval, interval)) - { - break; - } - - it = it->link[it->link[0] == NULL || it->link[0]->max < interval->low]; - } - - return it == NULL ? NULL : it->interval; -} - -void search(itreenode_t *node, interval_t *interval, ilist_t *results) -{ - /* - * If interval is to the right of the rightmost point of any interval - * in this node and all its children, there won't be any matches - */ - if (node == NULL || interval->low > node->max) - { - return; - } - - /* search the left subtree */ - if (node->link[0] != NULL && node->link[0]->max >= interval->low) - { - search(node->link[0], interval, results); - } - - /* search this node */ - if (interval_overlap(node->interval, interval)) - { - ilist_append(results, node->interval); - } - - /* - * if interval is to the left of the start of this interval - * it can't be in any child to the right - */ - if (interval->high < node->interval->low) - { - return; - } - - /* search the right subtree */ - search(node->link[1], interval, results); -} - -ilist_t *itree_findall(itree_t *tree, interval_t *interval) -{ - ilist_t *results = ilist_new(); - if (results != NULL) - { - /* empty tree case */ - if (tree->root == NULL) - { - return results; - } - - search(tree->root, interval, results); - } - - return results; -} - -int itree_insert(itree_t *tree, interval_t *interval) -{ - /* Empty tree case */ - if (tree->root == NULL) - { - tree->root = new_node(tree, interval); - if (tree->root == NULL) - { - return 0; - } - } - else - { - itreenode_t head = {0}; /* Temporary tree root */ - itreenode_t *s, *t; /* Place to rebalance and parent */ - itreenode_t *p, *q; /* Iterator and save pointer to the newly inserted node */ - int dir; - - /* Set up false root to ease maintenance */ - t = &head; - t->link[1] = tree->root; - - /* Search down the tree, saving rebalance points */ - for (s = p = t->link[1];; p = q) - { - /* Duplicates admitted, placed in the right subtree */ - dir = p->interval->low <= interval->low; /* tree->cmp ( p->data, data ) < 0; */ - q = p->link[dir]; - - p->max = p->max < interval->high ? interval->high : p->max; /* Update ancestor's max if needed */ - - if (q == NULL) - { - break; - } - - if (q->balance != 0) - { - t = p; - s = q; - } - } - - p->link[dir] = q = new_node(tree, interval); - if (q == NULL) - { - return 0; /* TODO: should rollback to previous ancestors' max values */ - } - - /* Update balance factors */ - for (p = s; p != q; p = p->link[dir]) - { - dir = p->interval->low <= interval->low; /* tree->cmp ( p->data, data ) < 0; */ - p->balance += dir == 0 ? -1 : +1; - } - - q = s; /* Save rebalance point for parent fix */ - - /* Rebalance if necessary */ - if (abs(s->balance) > 1) - { - dir = s->interval->low <= interval->low; /* tree->cmp ( s->data, data ) < 0; */ - insert_balance(s, dir); - } - - /* Fix parent */ - if (q == head.link[1]) - { - tree->root = s; - } - else - { - t->link[q == t->link[1]] = s; - } - } - - ++tree->size; - - return 1; -} - -int itree_remove(itree_t *tree, interval_t *interval) -{ - if (tree->root != NULL) - { - itreenode_t *it, *up[HEIGHT_LIMIT]; - int upd[HEIGHT_LIMIT], top = 0, top_max; - int done = 0; - - it = tree->root; - - /* Search down tree and save path */ - for (;;) - { - if (it == NULL) - { - return 0; - } - else if (interval_equal(it->interval, interval)) - { - break; - } - - /* Push direction and node onto stack */ - upd[top] = it->interval->low <= interval->low; /* tree->cmp ( it->data, data ) < 0; */ - up[top++] = it; - - it = it->link[upd[top - 1]]; - } - - /* Remove the node */ - if (it->link[0] == NULL || it->link[1] == NULL) - { - /* Which child is not null? */ - int dir = it->link[0] == NULL; - - /* Fix parent */ - if (top != 0) - { - up[top - 1]->link[upd[top - 1]] = it->link[dir]; - } - else - { - tree->root = it->link[dir]; - } - - tree->rel(it->interval->data); - free(it->interval); - free(it); - } - else - { - /* Find the inorder successor */ - itreenode_t *heir = it->link[1]; - void *save; - - /* Save this path too */ - upd[top] = 1; - up[top++] = it; - - while (heir->link[0] != NULL) - { - upd[top] = 0; - up[top++] = heir; - heir = heir->link[0]; - } - - /* Swap data */ - save = it->interval; - it->interval = heir->interval; - heir->interval = (interval_t *)save; - - /* Unlink successor and fix parent */ - up[top - 1]->link[up[top - 1] == it] = heir->link[1]; - - tree->rel(heir->interval->data); - free(heir->interval); - free(heir); - } - - /* Update max: walk back up the search path and bubbles up to root */ - top_max = top; - - while (--top_max >= 0) - { - itreenode_t *left = up[top_max]->link[0], *right = up[top_max]->link[1]; - if (left != NULL && right != NULL) - { - uint64_t left_right_max = left->max < right->max ? right->max : left->max; - up[top_max]->max = up[top_max]->interval->high < left_right_max ? left_right_max : up[top_max]->interval->high; - } - else if (left != NULL && right == NULL) - { - up[top_max]->max = up[top_max]->interval->high < left->max ? left->max : up[top_max]->interval->high; - } - else if (left == NULL && right != NULL) - { - up[top_max]->max = up[top_max]->interval->high < right->max ? right->max : up[top_max]->interval->high; - } - else - { - up[top_max]->max = up[top_max]->interval->high; - } - } - - /* Walk back up the search path */ - while (--top >= 0 && !done) - { - /* Update balance factors */ - up[top]->balance += upd[top] != 0 ? -1 : +1; - - /* Terminate or rebalance as necessary */ - if (abs(up[top]->balance) == 1) - { - break; - } - else if (abs(up[top]->balance) > 1) - { - remove_balance(up[top], upd[top], done); - - /* Fix parent */ - if (top != 0) - { - up[top - 1]->link[upd[top - 1]] = up[top]; - } - else - { - tree->root = up[0]; - } - } - } - - --tree->size; - } - - return 1; -} - -size_t itree_size(itree_t *tree) -{ - return tree->size; -} - -itreetrav_t *itreetnew(void) -{ - return (itreetrav_t *)malloc(sizeof(itreetrav_t)); -} - -void itreetdelete(itreetrav_t *trav) -{ - free(trav); -} - -/* - First step in traversal, - handles min and max -*/ -static interval_t *start(itreetrav_t *trav, itree_t *tree, int dir) -{ - trav->tree = tree; - trav->it = tree->root; - trav->top = 0; - - /* Build a path to work with */ - if (trav->it != NULL) - { - while (trav->it->link[dir] != NULL) - { - trav->path[trav->top++] = trav->it; - trav->it = trav->it->link[dir]; - } - } - -#ifdef DEBUG - if (trav->it) - printf("[%.1f, %.1f] (%d) (%.1f)\n", trav->it->interval->low, trav->it->interval->high, *(int *)trav->it->interval->data, trav->it->max); -#endif - - return trav->it == NULL ? NULL : trav->it->interval; -} - -/* - Subsequent traversal steps, - handles ascending and descending -*/ -static interval_t *move(itreetrav_t *trav, int dir) -{ - if (trav->it->link[dir] != NULL) - { - /* Continue down this branch */ - trav->path[trav->top++] = trav->it; - trav->it = trav->it->link[dir]; - - while (trav->it->link[!dir] != NULL) - { - trav->path[trav->top++] = trav->it; - trav->it = trav->it->link[!dir]; - } - } - else - { - /* Move to the next branch */ - itreenode_t *last; - do - { - if (trav->top == 0) - { - trav->it = NULL; - { - break; - } - } - - last = trav->it; - trav->it = trav->path[--trav->top]; - } while (last == trav->it->link[dir]); - } - -#ifdef DEBUG - if (trav->it) - printf("[%.1f, %.1f] (%d) (%.1f)\n", trav->it->interval->low, trav->it->interval->high, *(int *)trav->it->interval->data, trav->it->max); -#endif - - return trav->it == NULL ? NULL : trav->it->interval; -} - -interval_t *itreetfirst(itreetrav_t *trav, itree_t *tree) -{ - return start(trav, tree, 0); /* Min value */ -} - -interval_t *itreetlast(itreetrav_t *trav, itree_t *tree) -{ - return start(trav, tree, 1); /* Max value */ -} - -interval_t *itreetnext(itreetrav_t *trav) -{ - return move(trav, 1); /* Toward larger items */ -} - -interval_t *itreetprev(itreetrav_t *trav) -{ - return move(trav, 0); /* Toward smaller items */ -} diff --git a/deps/interval_tree/itree.h b/deps/interval_tree/itree.h deleted file mode 100644 index d9abbe1..0000000 --- a/deps/interval_tree/itree.h +++ /dev/null @@ -1,75 +0,0 @@ -/* - * Libitree: an interval tree library in C - * - * Copyright (C) 2018 Alessandro Vullo - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#ifndef _INTERVAL_TREE_H_ -#define _INTERVAL_TREE_H_ - -/* - Interval Tree library - - This is an adaptation of the AVL balanced tree C library - created by Julienne Walker which can be found here: - - http://www.eternallyconfuzzled.com/Libraries.aspx - -*/ - -#ifdef __cplusplus -extern "C" -{ -#endif - -#include "interval.h" -#include "interval_list.h" - -/* Opaque types */ -typedef struct itree itree_t; -typedef struct itreetrav itreetrav_t; - -/* User-defined interval data item handling */ -typedef void *(*dup_f)(void *p); -typedef void (*rel_f)(void *p); - -/* Interval tree functions */ -itree_t *itree_new(dup_f dup, rel_f rel); -void itree_delete(itree_t *tree); -interval_t *itree_find(itree_t *tree, interval_t *interval); -ilist_t *itree_findall(itree_t *tree, interval_t *interval); -int itree_insert(itree_t *tree, interval_t *interval); -int itree_remove(itree_t *tree, interval_t *interval); -size_t itree_size(itree_t *tree); - -/* Tree traversal functions */ -itreetrav_t *itreetnew(void); -void itreetdelete(itreetrav_t *trav); -interval_t *itreetfirst(itreetrav_t *trav, itree_t *tree); -interval_t *itreetlast(itreetrav_t *trav, itree_t *tree); -interval_t *itreetnext(itreetrav_t *trav); -interval_t *itreetprev(itreetrav_t *trav); - -#ifdef __cplusplus -} -#endif - -#endif /* _INTERVAL_TREE_H_ */ diff --git a/deps/interval_tree/test/gtest_interval_tree.cpp b/deps/interval_tree/test/gtest_interval_tree.cpp index 7fe0fbc..d8b7a7b 100644 --- a/deps/interval_tree/test/gtest_interval_tree.cpp +++ b/deps/interval_tree/test/gtest_interval_tree.cpp @@ -1,298 +1,178 @@ #include <gtest/gtest.h> -#include "itree.h" +#include "interval_tree.h" -void *my_dup(void *p) +struct interval_tree_node *node_new(uint64_t start, uint64_t last, void *user_data) { - return p; + uint64_t size = last - start + 1; + struct interval_tree_node *node = (struct interval_tree_node *)calloc(1, sizeof(struct interval_tree_node) + size); + if (node == nullptr) + { + return nullptr; + } + node->start = start; + node->last = last; + node->user_data = (char *)node + sizeof(struct interval_tree_node); + memcpy(node->user_data, user_data, size); + printf("new node: %p, start: %lu, last: %lu, user_data: %s\n", node, node->start, node->last, (char *)node->user_data); + + return node; } -void my_rel(void *p) +void node_free(struct interval_tree_node *node) { + if (node) + { + printf("free node: %p, start: %lu, last: %lu, user_data: %s\n", node, node->start, node->last, (char *)node->user_data); + free(node); + node = NULL; + } } -// find overlap +struct range +{ + uint64_t start; + uint64_t last; +}; + #if 1 TEST(INTERVAL_TREE, FIND) { - itree_t *tree; - interval_t *result; - interval_t query; - interval_t segment; - void *data = (void *)"Hello"; - - // new - tree = itree_new(my_dup, my_rel); - EXPECT_TRUE(tree != nullptr); - EXPECT_TRUE(itree_size(tree) == 0); + struct rb_root_cached root = RB_ROOT_CACHED; + struct interval_tree_node *node; // insert - segment = { - .low = 5, - .high = 9, - .data = data, - }; - EXPECT_TRUE(itree_insert(tree, &segment) == 1); - EXPECT_TRUE(itree_size(tree) == 1); - - // find - query = { - .low = 5, - .high = 5, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); - - // find - query = { - .low = 6, - .high = 8, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); - - // find - query = { - .low = 5, - .high = 9, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); - - // find - query = { - .low = 9, - .high = 9, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); - - // find - query = { - .low = 1, - .high = 14, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); + node = node_new(5, 10, (void *)"Hello"); + interval_tree_insert(node, &root); // not found - query = { - .low = 1, - .high = 4, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result == nullptr); + struct range ranges_not_found[] = { + {0, 4}, + {11, 15}, + }; + for (size_t i = 0; i < sizeof(ranges_not_found) / sizeof(ranges_not_found[0]); i++) + { + node = interval_tree_iter_first(&root, ranges_not_found[i].start, ranges_not_found[i].last); + EXPECT_TRUE(node == nullptr); + } + + // found + struct range ranges_found[] = { + // overlap interval + {0, 5}, + {1, 6}, + {2, 7}, + {3, 8}, + {4, 9}, + {5, 10}, + {6, 11}, + {7, 12}, + {8, 13}, + {9, 14}, + {10, 15}, + // overlap point + {5, 5}, + {6, 6}, + {7, 7}, + {8, 8}, + {9, 9}, + {10, 10}, + // overlap interval + {5, 10}, + {4, 11}, + }; + for (size_t i = 0; i < sizeof(ranges_found) / sizeof(ranges_found[0]); i++) + { + node = interval_tree_iter_first(&root, ranges_found[i].start, ranges_found[i].last); + EXPECT_TRUE(node != nullptr); + EXPECT_TRUE(node->start == 5); + EXPECT_TRUE(node->last == 10); + EXPECT_STREQ((const char *)node->user_data, "Hello"); + } - // not found - query = { - .low = 10, - .high = 14, - }; - result = itree_find(tree, &query); + // remove + interval_tree_remove(node, &root); + node_free(node); - itree_delete(tree); + // find + node = interval_tree_iter_first(&root, 5, 10); + EXPECT_TRUE(node == nullptr); } #endif #if 1 -TEST(INTERVAL_TREE, DELETE) +TEST(INTERVAL_TREE, REPEAT) { - itree_t *tree; - interval_t query; - interval_t segment; - void *data = (void *)"Hello"; - - // new - tree = itree_new(my_dup, my_rel); - EXPECT_TRUE(tree != nullptr); - EXPECT_TRUE(itree_size(tree) == 0); + struct rb_root_cached root = RB_ROOT_CACHED; + struct interval_tree_node *node; // insert - segment = { - .low = 5, - .high = 9, - .data = data, - }; - EXPECT_TRUE(itree_insert(tree, &segment) == 1); - EXPECT_TRUE(itree_size(tree) == 1); - - // delete - query = { - .low = 5, - .high = 5, - }; - EXPECT_TRUE(itree_remove(tree, &query) == 0); - EXPECT_TRUE(itree_size(tree) == 1); - - // delete - query = { - .low = 9, - .high = 9, - .data = data, - }; - EXPECT_TRUE(itree_remove(tree, &query) == 0); - EXPECT_TRUE(itree_size(tree) == 1); - - // delete - query = { - .low = 1, - .high = 20, - .data = data, - }; - EXPECT_TRUE(itree_remove(tree, &query) == 0); - EXPECT_TRUE(itree_size(tree) == 1); - - // delete - query = { - .low = 5, - .high = 9, - .data = data, - }; - EXPECT_TRUE(itree_remove(tree, &query) == 1); - EXPECT_TRUE(itree_size(tree) == 0); - - itree_delete(tree); + node = node_new(5, 10, (void *)"Hello"); + interval_tree_insert(node, &root); + + // insert repeat + node = node_new(5, 10, (void *)"World"); + interval_tree_insert(node, &root); + + node = interval_tree_iter_first(&root, 5, 10); + EXPECT_TRUE(node != nullptr); + EXPECT_TRUE(node->start == 5); + EXPECT_TRUE(node->last == 10); + EXPECT_STREQ((const char *)node->user_data, "Hello"); + + node = interval_tree_iter_next(node, 5, 10); + EXPECT_TRUE(node != nullptr); + EXPECT_TRUE(node->start == 5); + EXPECT_TRUE(node->last == 10); + EXPECT_STREQ((const char *)node->user_data, "World"); + + node = interval_tree_iter_next(node, 5, 10); + EXPECT_TRUE(node == nullptr); + + // remove all + while ((node = interval_tree_iter_first(&root, 5, 10)) != nullptr) + { + interval_tree_remove(node, &root); + node_free(node); + } } #endif #if 1 -TEST(INTERVAL_TREE, REPEAT1) -{ - itree_t *tree; - interval_t segment; - interval_t query; - void *data1 = (void *)"Hello"; - void *data2 = (void *)"World"; - - // new - tree = itree_new(my_dup, my_rel); - EXPECT_TRUE(tree != nullptr); - EXPECT_TRUE(itree_size(tree) == 0); - - // insert - segment = { - .low = 5, - .high = 9, - .data = data1, - }; - EXPECT_TRUE(itree_insert(tree, &segment) == 1); - EXPECT_TRUE(itree_size(tree) == 1); - - // insert - segment = { - .low = 5, - .high = 9, - .data = data2, - }; - EXPECT_TRUE(itree_insert(tree, &segment) == 1); - EXPECT_TRUE(itree_size(tree) == 2); - - // remove - query = { - .low = 5, - .high = 9, - .data = data1, - }; - EXPECT_TRUE(itree_remove(tree, &query) == 1); - EXPECT_TRUE(itree_size(tree) == 1); - query = { - .low = 5, - .high = 9, - .data = data2, - }; - EXPECT_TRUE(itree_remove(tree, &query) == 1); - EXPECT_TRUE(itree_size(tree) == 0); - - itree_delete(tree); -} -#endif - -#if 1 // repeat, return the fist one -TEST(INTERVAL_TREE, REPEAT2) +TEST(INTERVAL_TREE, OVERLAP) { - itree_t *tree; - ilist_t *list; - ilisttrav_t *trav; - interval_t *result; - interval_t query; - interval_t segment; - - // new - tree = itree_new(my_dup, my_rel); - EXPECT_TRUE(tree != nullptr); - EXPECT_TRUE(itree_size(tree) == 0); - - // insert - segment = { - .low = 5, - .high = 9, - .data = (void *)"Hello", - }; - EXPECT_TRUE(itree_insert(tree, &segment) == 1); - EXPECT_TRUE(itree_size(tree) == 1); + struct rb_root_cached root = RB_ROOT_CACHED; + struct interval_tree_node *node; // insert - segment = { - .low = 5, - .high = 9, - .data = (void *)"World", - }; - EXPECT_TRUE(itree_insert(tree, &segment) == 1); - EXPECT_TRUE(itree_size(tree) == 2); - - // find - query = { - .low = 5, - .high = 9, - }; - result = itree_find(tree, &query); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); - - // find all, free the repeat - query = { - .low = 5, - .high = 9, - }; - list = itree_findall(tree, &query); - EXPECT_TRUE(list != nullptr); - EXPECT_TRUE(ilist_size(list) == 2); - trav = ilisttrav_new(list); - EXPECT_TRUE(trav != nullptr); - - result = (interval_t *)ilisttrav_first(trav); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "Hello"); - - result = (interval_t *)ilisttrav_next(trav); - EXPECT_TRUE(result != nullptr); - EXPECT_TRUE(result->low == 5); - EXPECT_TRUE(result->high == 9); - EXPECT_STREQ((const char *)result->data, "World"); - - ilisttrav_delete(trav); - ilist_delete(list); - - itree_delete(tree); + node = node_new(5, 10, (void *)"Hello"); + interval_tree_insert(node, &root); + + // insert repeat + node = node_new(7, 12, (void *)"World"); + interval_tree_insert(node, &root); + + node = interval_tree_iter_first(&root, 5, 10); + EXPECT_TRUE(node != nullptr); + EXPECT_TRUE(node->start == 5); + EXPECT_TRUE(node->last == 10); + EXPECT_STREQ((const char *)node->user_data, "Hello"); + + node = interval_tree_iter_next(node, 5, 10); + EXPECT_TRUE(node != nullptr); + EXPECT_TRUE(node->start == 7); + EXPECT_TRUE(node->last == 12); + EXPECT_STREQ((const char *)node->user_data, "World"); + + node = interval_tree_iter_next(node, 5, 10); + EXPECT_TRUE(node == nullptr); + + // remove all + while ((node = interval_tree_iter_first(&root, 5, 10)) != nullptr) + { + interval_tree_remove(node, &root); + node_free(node); + } } #endif diff --git a/deps/list/list.h b/deps/list/list.h new file mode 100644 index 0000000..f728300 --- /dev/null +++ b/deps/list/list.h @@ -0,0 +1,356 @@ +/* + * Copyright © 2010 Intel Corporation + * Copyright © 2010 Francisco Jerez <[email protected]> + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + */ + +/* Modified by Ben Skeggs <[email protected]> to match kernel list APIs */ + +#ifndef _XORG_LIST_H_ +#define _XORG_LIST_H_ + +/** + * @file Classic doubly-link circular list implementation. + * For real usage examples of the linked list, see the file test/list.c + * + * Example: + * We need to keep a list of struct foo in the parent struct bar, i.e. what + * we want is something like this. + * + * struct bar { + * ... + * struct foo *list_of_foos; -----> struct foo {}, struct foo {}, struct foo{} + * ... + * } + * + * We need one list head in bar and a list element in all list_of_foos (both are of + * data type 'struct list_head'). + * + * struct bar { + * ... + * struct list_head list_of_foos; + * ... + * } + * + * struct foo { + * ... + * struct list_head entry; + * ... + * } + * + * Now we initialize the list head: + * + * struct bar bar; + * ... + * INIT_LIST_HEAD(&bar.list_of_foos); + * + * Then we create the first element and add it to this list: + * + * struct foo *foo = malloc(...); + * .... + * list_add(&foo->entry, &bar.list_of_foos); + * + * Repeat the above for each element you want to add to the list. Deleting + * works with the element itself. + * list_del(&foo->entry); + * free(foo); + * + * Note: calling list_del(&bar.list_of_foos) will set bar.list_of_foos to an empty + * list again. + * + * Looping through the list requires a 'struct foo' as iterator and the + * name of the field the subnodes use. + * + * struct foo *iterator; + * list_for_each_entry(iterator, &bar.list_of_foos, entry) { + * if (iterator->something == ...) + * ... + * } + * + * Note: You must not call list_del() on the iterator if you continue the + * loop. You need to run the safe for-each loop instead: + * + * struct foo *iterator, *next; + * list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) { + * if (...) + * list_del(&iterator->entry); + * } + * + */ + +/** + * The linkage struct for list nodes. This struct must be part of your + * to-be-linked struct. struct list_head is required for both the head of the + * list and for each list node. + * + * Position and name of the struct list_head field is irrelevant. + * There are no requirements that elements of a list are of the same type. + * There are no requirements for a list head, any struct list_head can be a list + * head. + */ +struct list_head +{ + struct list_head *next, *prev; +}; + +/** + * Initialize the list as an empty list. + * + * Example: + * INIT_LIST_HEAD(&bar->list_of_foos); + * + * @param The list to initialized. + */ +#define LIST_HEAD_INIT(name) \ + { \ + &(name), &(name) \ + } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +static inline void +INIT_LIST_HEAD(struct list_head *list) +{ + list->next = list->prev = list; +} + +static inline void +__list_add(struct list_head *entry, + struct list_head *prev, struct list_head *next) +{ + next->prev = entry; + entry->next = next; + entry->prev = prev; + prev->next = entry; +} + +/** + * Insert a new element after the given list head. The new element does not + * need to be initialised as empty list. + * The list changes from: + * head → some element → ... + * to + * head → new element → older element → ... + * + * Example: + * struct foo *newfoo = malloc(...); + * list_add(&newfoo->entry, &bar->list_of_foos); + * + * @param entry The new element to prepend to the list. + * @param head The existing list. + */ +static inline void +list_add(struct list_head *entry, struct list_head *head) +{ + __list_add(entry, head, head->next); +} + +/** + * Append a new element to the end of the list given with this list head. + * + * The list changes from: + * head → some element → ... → lastelement + * to + * head → some element → ... → lastelement → new element + * + * Example: + * struct foo *newfoo = malloc(...); + * list_add_tail(&newfoo->entry, &bar->list_of_foos); + * + * @param entry The new element to prepend to the list. + * @param head The existing list. + */ +static inline void +list_add_tail(struct list_head *entry, struct list_head *head) +{ + __list_add(entry, head->prev, head); +} + +static inline void +__list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * Remove the element from the list it is in. Using this function will reset + * the pointers to/from this element so it is removed from the list. It does + * NOT free the element itself or manipulate it otherwise. + * + * Using list_del on a pure list head (like in the example at the top of + * this file) will NOT remove the first element from + * the list but rather reset the list as empty list. + * + * Example: + * list_del(&foo->entry); + * + * @param entry The element to remove. + */ +static inline void +list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); +} + +static inline void +list_del_init(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +static inline void list_move_tail(struct list_head *list, + struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * Check if the list is empty. + * + * Example: + * list_empty(&bar->list_of_foos); + * + * @return True if the list contains one or more elements or False otherwise. + */ +static inline bool +list_empty(struct list_head *head) +{ + return head->next == head; +} + +/** + * Returns a pointer to the container of this list element. + * + * Example: + * struct foo* f; + * f = container_of(&foo->entry, struct foo, entry); + * assert(f == foo); + * + * @param ptr Pointer to the struct list_head. + * @param type Data type of the list element. + * @param member Member name of the struct list_head field in the list element. + * @return A pointer to the data struct containing the list head. + */ +#ifndef container_of +#define container_of(ptr, type, member) \ + (type *)((char *)(ptr) - (char *)&((type *)0)->member) +#endif + +/** + * Alias of container_of + */ +#define list_entry(ptr, type, member) \ + container_of(ptr, type, member) + +/** + * Retrieve the first list entry for the given list pointer. + * + * Example: + * struct foo *first; + * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos); + * + * @param ptr The list head + * @param type Data type of the list element to retrieve + * @param member Member name of the struct list_head field in the list element. + * @return A pointer to the first list element. + */ +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +/** + * Retrieve the last list entry for the given listpointer. + * + * Example: + * struct foo *first; + * first = list_last_entry(&bar->list_of_foos, struct foo, list_of_foos); + * + * @param ptr The list head + * @param type Data type of the list element to retrieve + * @param member Member name of the struct list_head field in the list element. + * @return A pointer to the last list element. + */ +#define list_last_entry(ptr, type, member) \ + list_entry((ptr)->prev, type, member) + +#define __container_of(ptr, sample, member) \ + (void *)container_of((ptr), typeof(*(sample)), member) + +/** + * Loop through the list given by head and set pos to struct in the list. + * + * Example: + * struct foo *iterator; + * list_for_each_entry(iterator, &bar->list_of_foos, entry) { + * [modify iterator] + * } + * + * This macro is not safe for node deletion. Use list_for_each_entry_safe + * instead. + * + * @param pos Iterator variable of the type of the list elements. + * @param head List head + * @param member Member name of the struct list_head in the list elements. + * + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = __container_of((head)->next, pos, member); \ + &pos->member != (head); \ + pos = __container_of(pos->member.next, pos, member)) + +/** + * Loop through the list, keeping a backup pointer to the element. This + * macro allows for the deletion of a list element while looping through the + * list. + * + * See list_for_each_entry for more details. + */ +#define list_for_each_entry_safe(pos, tmp, head, member) \ + for (pos = __container_of((head)->next, pos, member), \ + tmp = __container_of(pos->member.next, pos, member); \ + &pos->member != (head); \ + pos = tmp, tmp = __container_of(pos->member.next, tmp, member)) + +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = __container_of((head)->prev, pos, member); \ + &pos->member != (head); \ + pos = __container_of(pos->member.prev, pos, member)) + +#define list_for_each_entry_continue(pos, head, member) \ + for (pos = __container_of(pos->member.next, pos, member); \ + &pos->member != (head); \ + pos = __container_of(pos->member.next, pos, member)) + +#define list_for_each_entry_continue_reverse(pos, head, member) \ + for (pos = __container_of(pos->member.prev, pos, member); \ + &pos->member != (head); \ + pos = __container_of(pos->member.prev, pos, member)) + +#define list_for_each_entry_from(pos, head, member) \ + for (; \ + &pos->member != (head); \ + pos = __container_of(pos->member.next, pos, member)) + +#endif diff --git a/deps/rbtree/CMakeLists.txt b/deps/rbtree/CMakeLists.txt new file mode 100644 index 0000000..c7debda --- /dev/null +++ b/deps/rbtree/CMakeLists.txt @@ -0,0 +1,2 @@ +add_library(rbtree STATIC rbtree.cpp) +target_include_directories(rbtree PUBLIC ${CMAKE_CURRENT_LIST_DIR})
\ No newline at end of file diff --git a/deps/rbtree/rbtree.cpp b/deps/rbtree/rbtree.cpp new file mode 100644 index 0000000..d648a94 --- /dev/null +++ b/deps/rbtree/rbtree.cpp @@ -0,0 +1,624 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <[email protected]> + (C) 2002 David Woodhouse <[email protected]> + (C) 2012 Michel Lespinasse <[email protected]> + + + linux/lib/rbtree.c +*/ + +#include "rbtree_augmented.h" + +/* + * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree + * + * 1) A node is either red or black + * 2) The root is black + * 3) All leaves (NULL) are black + * 4) Both children of every red node are black + * 5) Every simple path from root to leaves contains the same number + * of black nodes. + * + * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two + * consecutive red nodes in a path and every red node is therefore followed by + * a black. So if B is the number of black nodes on every simple path (as per + * 5), then the longest possible path due to 4 is 2B. + * + * We shall indicate color with case, where black nodes are uppercase and red + * nodes will be lowercase. Unknown color nodes shall be drawn as red within + * parentheses and have some accompanying text comment. + */ + +/* + * Notes on lockless lookups: + * + * All stores to the tree structure (rb_left and rb_right) must be done using + * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the + * tree structure as seen in program order. + * + * These two requirements will allow lockless iteration of the tree -- not + * correct iteration mind you, tree rotations are not atomic so a lookup might + * miss entire subtrees. + * + * But they do guarantee that any such traversal will only see valid elements + * and that it will indeed complete -- does not get stuck in a loop. + * + * It also guarantees that if the lookup returns an element it is the 'correct' + * one. But not returning an element does _NOT_ mean it's not present. + * + * NOTE: + * + * Stores to __rb_parent_color are not important for simple lookups so those + * are left undone as of now. Nor did I check for loops involving parent + * pointers. + */ + +#define likely(expr) __builtin_expect((expr), 1) +#define unlikely(expr) __builtin_expect((expr), 0) + +static inline void rb_set_black(struct rb_node *rb) +{ + rb->__rb_parent_color |= RB_BLACK; +} + +static inline struct rb_node *rb_red_parent(struct rb_node *red) +{ + return (struct rb_node *)red->__rb_parent_color; +} + +/* + * Helper function for rotations: + * - old's parent and color get assigned to new + * - old gets assigned new as a parent and 'color' as a color. + */ +static inline void +__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new_node, + struct rb_root *root, int color) +{ + struct rb_node *parent = rb_parent(old); + new_node->__rb_parent_color = old->__rb_parent_color; + rb_set_parent_color(old, new_node, color); + __rb_change_child(old, new_node, parent, root); +} + +static inline void +__rb_insert(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new_node)) +{ + struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; + + while (true) + { + /* + * Loop invariant: node is red. + */ + if (unlikely(!parent)) + { + /* + * The inserted node is root. Either this is the + * first node, or we recursed at Case 1 below and + * are no longer violating 4). + */ + rb_set_parent_color(node, NULL, RB_BLACK); + break; + } + + /* + * If there is a black parent, we are done. + * Otherwise, take some corrective action as, + * per 4), we don't want a red root or two + * consecutive red nodes. + */ + if (rb_is_black(parent)) + break; + + gparent = rb_red_parent(parent); + + tmp = gparent->rb_right; + if (parent != tmp) + { /* parent == gparent->rb_left */ + if (tmp && rb_is_red(tmp)) + { + /* + * Case 1 - node's uncle is red (color flips). + * + * G g + * / \ / \ + * p u --> P U + * / / + * n n + * + * However, since g's parent might be red, and + * 4) does not allow this, we need to recurse + * at g. + */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; + } + + tmp = parent->rb_right; + if (node == tmp) + { + /* + * Case 2 - node's uncle is black and node is + * the parent's right child (left rotate at parent). + * + * G G + * / \ / \ + * p U --> n U + * \ / + * n p + * + * This still leaves us in violation of 4), the + * continuation into Case 3 will fix that. + */ + tmp = node->rb_left; + parent->rb_right = tmp; + node->rb_left = parent; + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); + parent = node; + tmp = node->rb_right; + } + + /* + * Case 3 - node's uncle is black and node is + * the parent's left child (right rotate at gparent). + * + * G P + * / \ / \ + * p U --> n g + * / \ + * n U + */ + gparent->rb_left = tmp; /* == parent->rb_right */ + parent->rb_right = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); + break; + } + else + { + tmp = gparent->rb_left; + if (tmp && rb_is_red(tmp)) + { + /* Case 1 - color flips */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; + } + + tmp = parent->rb_left; + if (node == tmp) + { + /* Case 2 - right rotate at parent */ + tmp = node->rb_right; + parent->rb_left = tmp; + node->rb_right = parent; + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); + parent = node; + tmp = node->rb_left; + } + + /* Case 3 - left rotate at gparent */ + gparent->rb_right = tmp; /* == parent->rb_left */ + parent->rb_left = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); + break; + } + } +} + +/* + * Inline version for rb_erase() use - we want to be able to inline + * and eliminate the dummy_rotate callback there + */ +static inline void +____rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new_node)) +{ + struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; + + while (true) + { + /* + * Loop invariants: + * - node is black (or NULL on first iteration) + * - node is not the root (parent is not NULL) + * - All leaf paths going through parent and node have a + * black node count that is 1 lower than other leaf paths. + */ + sibling = parent->rb_right; + if (node != sibling) + { /* node == parent->rb_left */ + if (rb_is_red(sibling)) + { + /* + * Case 1 - left rotate at parent + * + * P S + * / \ / \ + * N s --> p Sr + * / \ / \ + * Sl Sr N Sl + */ + tmp1 = sibling->rb_left; + parent->rb_right = tmp1; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_right; + if (!tmp1 || rb_is_black(tmp1)) + { + tmp2 = sibling->rb_left; + if (!tmp2 || rb_is_black(tmp2)) + { + /* + * Case 2 - sibling color flip + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N s + * / \ / \ + * Sl Sr Sl Sr + * + * This leaves us violating 5) which + * can be fixed by flipping p to black + * if it was red, or by recursing at p. + * p is red when coming from Case 1. + */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else + { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; + } + /* + * Case 3 - right rotate at sibling + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N sl + * / \ \ + * sl Sr S + * \ + * Sr + * + * Note: p might be red, and then both + * p and sl are red after rotation(which + * breaks property 4). This is fixed in + * Case 4 (in __rb_rotate_set_parents() + * which set sl the color of p + * and set p RB_BLACK) + * + * (p) (sl) + * / \ / \ + * N sl --> P S + * \ / \ + * S N Sr + * \ + * Sr + */ + tmp1 = tmp2->rb_right; + sibling->rb_left = tmp1; + tmp2->rb_right = sibling; + parent->rb_right = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; + } + /* + * Case 4 - left rotate at parent + color flips + * (p and sl could be either color here. + * After rotation, p becomes black, s acquires + * p's color, and sl keeps its color) + * + * (p) (s) + * / \ / \ + * N S --> P Sr + * / \ / \ + * (sl) sr N (sl) + */ + tmp2 = sibling->rb_left; + parent->rb_right = tmp2; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); + break; + } + else + { + sibling = parent->rb_left; + if (rb_is_red(sibling)) + { + /* Case 1 - right rotate at parent */ + tmp1 = sibling->rb_right; + parent->rb_left = tmp1; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_left; + if (!tmp1 || rb_is_black(tmp1)) + { + tmp2 = sibling->rb_right; + if (!tmp2 || rb_is_black(tmp2)) + { + /* Case 2 - sibling color flip */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else + { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; + } + /* Case 3 - left rotate at sibling */ + tmp1 = tmp2->rb_left; + sibling->rb_right = tmp1; + tmp2->rb_left = sibling; + parent->rb_left = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; + } + /* Case 4 - right rotate at parent + color flips */ + tmp2 = sibling->rb_right; + parent->rb_left = tmp2; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); + break; + } + } +} + +/* Non-inline version for rb_erase_augmented() use */ +void __rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new_node)) +{ + ____rb_erase_color(parent, root, augment_rotate); +} + +/* + * Non-augmented rbtree manipulation functions. + * + * We use dummy augmented callbacks here, and have the compiler optimize them + * out of the rb_insert_color() and rb_erase() function definitions. + */ + +static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} +static inline void dummy_copy(struct rb_node *old, struct rb_node *new_node) {} +static inline void dummy_rotate(struct rb_node *old, struct rb_node *new_node) {} + +static const struct rb_augment_callbacks dummy_callbacks = { + .propagate = dummy_propagate, + .copy = dummy_copy, + .rotate = dummy_rotate}; + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + __rb_insert(node, root, dummy_rotate); +} + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *rebalance; + rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); + if (rebalance) + ____rb_erase_color(rebalance, root, dummy_rotate); +} + +/* + * Augmented rbtree manipulation functions. + * + * This instantiates the same inline functions as in the non-augmented + * case, but this time with user-defined callbacks. + */ + +void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new_node)) +{ + __rb_insert(node, root, augment_rotate); +} + +/* + * This function returns the first node (in sort order) of the tree. + */ +struct rb_node *rb_first(const struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_left) + n = n->rb_left; + return n; +} + +struct rb_node *rb_last(const struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_right) + n = n->rb_right; + return n; +} + +struct rb_node *rb_next(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return NULL; + + /* + * If we have a right-hand child, go down and then left as far + * as we can. + */ + if (node->rb_right) + { + node = node->rb_right; + while (node->rb_left) + node = node->rb_left; + return (struct rb_node *)node; + } + + /* + * No right-hand children. Everything down and left is smaller than us, + * so any 'next' node must be in the general direction of our parent. + * Go up the tree; any time the ancestor is a right-hand child of its + * parent, keep going up. First time it's a left-hand child of its + * parent, said parent is our 'next' node. + */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; +} + +struct rb_node *rb_prev(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return NULL; + + /* + * If we have a left-hand child, go down and then right as far + * as we can. + */ + if (node->rb_left) + { + node = node->rb_left; + while (node->rb_right) + node = node->rb_right; + return (struct rb_node *)node; + } + + /* + * No left-hand children. Go up till we find an ancestor which + * is a right-hand child of its parent. + */ + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; + + return parent; +} + +void rb_replace_node(struct rb_node *victim, struct rb_node *new_node, + struct rb_root *root) +{ + struct rb_node *parent = rb_parent(victim); + + /* Copy the pointers/colour from the victim to the replacement */ + *new_node = *victim; + + /* Set the surrounding nodes to point to the replacement */ + if (victim->rb_left) + rb_set_parent(victim->rb_left, new_node); + if (victim->rb_right) + rb_set_parent(victim->rb_right, new_node); + __rb_change_child(victim, new_node, parent, root); +} + +static struct rb_node *rb_left_deepest_node(const struct rb_node *node) +{ + for (;;) + { + if (node->rb_left) + node = node->rb_left; + else if (node->rb_right) + node = node->rb_right; + else + return (struct rb_node *)node; + } +} + +struct rb_node *rb_next_postorder(const struct rb_node *node) +{ + const struct rb_node *parent; + if (!node) + return NULL; + parent = rb_parent(node); + + /* If we're sitting on node, we've already seen our children */ + if (parent && node == parent->rb_left && parent->rb_right) + { + /* If we are the parent's left node, go to the parent's right + * node then all the way down to the left */ + return rb_left_deepest_node(parent->rb_right); + } + else + /* Otherwise we are the parent's right node, and the parent + * should be next */ + return (struct rb_node *)parent; +} + +struct rb_node *rb_first_postorder(const struct rb_root *root) +{ + if (!root->rb_node) + return NULL; + + return rb_left_deepest_node(root->rb_node); +} diff --git a/deps/rbtree/rbtree.h b/deps/rbtree/rbtree.h new file mode 100644 index 0000000..25bd4da --- /dev/null +++ b/deps/rbtree/rbtree.h @@ -0,0 +1,383 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <[email protected]> + + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + See Documentation/core-api/rbtree.rst for documentation and samples. +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H + +#include <stdlib.h> + +struct rb_node +{ + unsigned long __rb_parent_color; + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); +/* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root +{ + struct rb_node *rb_node; +}; + +/* + * Leftmost-cached rbtrees. + * + * We do not cache the rightmost node based on footprint + * size vs number of potential users that could benefit + * from O(1) rb_last(). Just not worth it, users that want + * this feature can always implement the logic explicitly. + * Furthermore, users that want to cache both pointers may + * find it a bit asymmetric, but that's ok. + */ +struct rb_root_cached +{ + struct rb_root rb_root; + struct rb_node *rb_leftmost; +}; + +#define RB_ROOT \ + (struct rb_root) { NULL, } +#define RB_ROOT_CACHED \ + (struct rb_root_cached) { { \ + NULL, \ + }, \ + NULL } + +/** + * Returns a pointer to the container of this list element. + * + * Example: + * struct foo* f; + * f = container_of(&foo->entry, struct foo, entry); + * assert(f == foo); + * + * @param ptr Pointer to the struct list_head. + * @param type Data type of the list element. + * @param member Member name of the struct list_head field in the list element. + * @return A pointer to the data struct containing the list head. + */ +#ifndef container_of +#define container_of(ptr, type, member) \ + (type *)((char *)(ptr) - (char *)&((type *)0)->member) +#endif + +#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) + +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) + +/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */ +#define RB_EMPTY_NODE(node) \ + ((node)->__rb_parent_color == (unsigned long)(node)) +#define RB_CLEAR_NODE(node) \ + ((node)->__rb_parent_color = (unsigned long)(node)) + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(const struct rb_node *); +extern struct rb_node *rb_prev(const struct rb_node *); +extern struct rb_node *rb_first(const struct rb_root *); +extern struct rb_node *rb_last(const struct rb_root *); + +/* Postorder iteration - always visit the parent after its children */ +extern struct rb_node *rb_first_postorder(const struct rb_root *); +extern struct rb_node *rb_next_postorder(const struct rb_node *); + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new_node, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, + struct rb_node **rb_link) +{ + node->__rb_parent_color = (unsigned long)parent; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#define rb_entry_safe(ptr, type, member) \ + ({ \ + typeof(ptr) ____ptr = (ptr); \ + ____ptr ? rb_entry(____ptr, type, member) : NULL; \ + }) + +/** + * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of + * given type allowing the backing memory of @pos to be invalidated + * + * @pos: the 'type *' to use as a loop cursor. + * @n: another 'type *' to use as temporary storage + * @root: 'rb_root *' of the rbtree. + * @field: the name of the rb_node field within 'type'. + * + * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as + * list_for_each_entry_safe() and allows the iteration to continue independent + * of changes to @pos by the body of the loop. + * + * Note, however, that it cannot handle other modifications that re-order the + * rbtree it is iterating over. This includes calling rb_erase() on @pos, as + * rb_erase() may rebalance the tree, causing us to miss some nodes. + */ +#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ + for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \ + pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ + typeof(*pos), field); 1; }); \ + pos = n) + +/* Same as rb_first(), but O(1) */ +#define rb_first_cached(root) (root)->rb_leftmost + +static inline void rb_insert_color_cached(struct rb_node *node, + struct rb_root_cached *root, + bool leftmost) +{ + if (leftmost) + root->rb_leftmost = node; + rb_insert_color(node, &root->rb_root); +} + +static inline struct rb_node * +rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) +{ + struct rb_node *leftmost = NULL; + + if (root->rb_leftmost == node) + leftmost = root->rb_leftmost = rb_next(node); + + rb_erase(node, &root->rb_root); + + return leftmost; +} + +static inline void rb_replace_node_cached(struct rb_node *victim, + struct rb_node *new_node, + struct rb_root_cached *root) +{ + if (root->rb_leftmost == victim) + root->rb_leftmost = new_node; + rb_replace_node(victim, new_node, &root->rb_root); +} + +/* + * The below helper functions use 2 operators with 3 different + * calling conventions. The operators are related like: + * + * comp(a->key,b) < 0 := less(a,b) + * comp(a->key,b) > 0 := less(b,a) + * comp(a->key,b) == 0 := !less(a,b) && !less(b,a) + * + * If these operators define a partial order on the elements we make no + * guarantee on which of the elements matching the key is found. See + * rb_find(). + * + * The reason for this is to allow the find() interface without requiring an + * on-stack dummy object, which might not be feasible due to object size. + */ + +/** + * rb_add_cached() - insert @node into the leftmost cached tree @tree + * @node: node to insert + * @tree: leftmost cached tree to insert @node into + * @less: operator defining the (partial) node order + * + * Returns @node when it is the new leftmost, or NULL. + */ +static inline struct rb_node * +rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, + bool (*less)(struct rb_node *, const struct rb_node *)) +{ + struct rb_node **link = &tree->rb_root.rb_node; + struct rb_node *parent = NULL; + bool leftmost = true; + + while (*link) + { + parent = *link; + if (less(node, parent)) + { + link = &parent->rb_left; + } + else + { + link = &parent->rb_right; + leftmost = false; + } + } + + rb_link_node(node, parent, link); + rb_insert_color_cached(node, tree, leftmost); + + return leftmost ? node : NULL; +} + +/** + * rb_add() - insert @node into @tree + * @node: node to insert + * @tree: tree to insert @node into + * @less: operator defining the (partial) node order + */ +static inline void +rb_add(struct rb_node *node, struct rb_root *tree, + bool (*less)(struct rb_node *, const struct rb_node *)) +{ + struct rb_node **link = &tree->rb_node; + struct rb_node *parent = NULL; + + while (*link) + { + parent = *link; + if (less(node, parent)) + link = &parent->rb_left; + else + link = &parent->rb_right; + } + + rb_link_node(node, parent, link); + rb_insert_color(node, tree); +} + +/** + * rb_find_add() - find equivalent @node in @tree, or add @node + * @node: node to look-for / insert + * @tree: tree to search / modify + * @cmp: operator defining the node order + * + * Returns the rb_node matching @node, or NULL when no match is found and @node + * is inserted. + */ +static inline struct rb_node * +rb_find_add(struct rb_node *node, struct rb_root *tree, + int (*cmp)(struct rb_node *, const struct rb_node *)) +{ + struct rb_node **link = &tree->rb_node; + struct rb_node *parent = NULL; + int c; + + while (*link) + { + parent = *link; + c = cmp(node, parent); + + if (c < 0) + link = &parent->rb_left; + else if (c > 0) + link = &parent->rb_right; + else + return parent; + } + + rb_link_node(node, parent, link); + rb_insert_color(node, tree); + return NULL; +} + +/** + * rb_find() - find @key in tree @tree + * @key: key to match + * @tree: tree to search + * @cmp: operator defining the node order + * + * Returns the rb_node matching @key or NULL. + */ +static inline struct rb_node * +rb_find(const void *key, const struct rb_root *tree, + int (*cmp)(const void *key, const struct rb_node *)) +{ + struct rb_node *node = tree->rb_node; + + while (node) + { + int c = cmp(key, node); + + if (c < 0) + node = node->rb_left; + else if (c > 0) + node = node->rb_right; + else + return node; + } + + return NULL; +} + +/** + * rb_find_first() - find the first @key in @tree + * @key: key to match + * @tree: tree to search + * @cmp: operator defining node order + * + * Returns the leftmost node matching @key, or NULL. + */ +static inline struct rb_node * +rb_find_first(const void *key, const struct rb_root *tree, + int (*cmp)(const void *key, const struct rb_node *)) +{ + struct rb_node *node = tree->rb_node; + struct rb_node *match = NULL; + + while (node) + { + int c = cmp(key, node); + + if (c <= 0) + { + if (!c) + match = node; + node = node->rb_left; + } + else if (c > 0) + { + node = node->rb_right; + } + } + + return match; +} + +/** + * rb_next_match() - find the next @key in @tree + * @key: key to match + * @tree: tree to search + * @cmp: operator defining node order + * + * Returns the next node matching @key, or NULL. + */ +static inline struct rb_node * +rb_next_match(const void *key, struct rb_node *node, + int (*cmp)(const void *key, const struct rb_node *)) +{ + node = rb_next(node); + if (node && cmp(key, node)) + node = NULL; + return node; +} + +/** + * rb_for_each() - iterates a subtree matching @key + * @node: iterator + * @key: key to match + * @tree: tree to search + * @cmp: operator defining node order + */ +#define rb_for_each(node, key, tree, cmp) \ + for ((node) = rb_find_first((key), (tree), (cmp)); \ + (node); (node) = rb_next_match((key), (node), (cmp))) + +#endif /* _LINUX_RBTREE_H */ diff --git a/deps/rbtree/rbtree_augmented.h b/deps/rbtree/rbtree_augmented.h new file mode 100644 index 0000000..add1ee5 --- /dev/null +++ b/deps/rbtree/rbtree_augmented.h @@ -0,0 +1,320 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <[email protected]> + (C) 2002 David Woodhouse <[email protected]> + (C) 2012 Michel Lespinasse <[email protected]> + + + linux/include/linux/rbtree_augmented.h +*/ + +#ifndef _LINUX_RBTREE_AUGMENTED_H +#define _LINUX_RBTREE_AUGMENTED_H + +#include "rbtree.h" + +/* + * Please note - only struct rb_augment_callbacks and the prototypes for + * rb_insert_augmented() and rb_erase_augmented() are intended to be public. + * The rest are implementation details you are not expected to depend on. + * + * See Documentation/core-api/rbtree.rst for documentation and samples. + */ + +struct rb_augment_callbacks +{ + void (*propagate)(struct rb_node *node, struct rb_node *stop); + void (*copy)(struct rb_node *old, struct rb_node *new_node); + void (*rotate)(struct rb_node *old, struct rb_node *new_node); +}; + +extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new_node)); + +/* + * Fixup the rbtree and update the augmented information when rebalancing. + * + * On insertion, the user must update the augmented information on the path + * leading to the inserted node, then call rb_link_node() as usual and + * rb_insert_augmented() instead of the usual rb_insert_color() call. + * If rb_insert_augmented() rebalances the rbtree, it will callback into + * a user provided function to update the augmented information on the + * affected subtrees. + */ +static inline void +rb_insert_augmented(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) +{ + __rb_insert_augmented(node, root, augment->rotate); +} + +static inline void +rb_insert_augmented_cached(struct rb_node *node, + struct rb_root_cached *root, bool newleft, + const struct rb_augment_callbacks *augment) +{ + if (newleft) + root->rb_leftmost = node; + rb_insert_augmented(node, &root->rb_root, augment); +} + +/* + * Template for declaring augmented rbtree callbacks (generic case) + * + * RBSTATIC: 'static' or empty + * RBNAME: name of the rb_augment_callbacks structure + * RBSTRUCT: struct type of the tree nodes + * RBFIELD: name of struct rb_node field within RBSTRUCT + * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree + * RBCOMPUTE: name of function that recomputes the RBAUGMENTED data + */ + +#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \ + RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \ + static inline void \ + RBNAME##_propagate(struct rb_node *rb, struct rb_node *stop) \ + { \ + while (rb != stop) \ + { \ + RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \ + if (RBCOMPUTE(node, true)) \ + break; \ + rb = rb_parent(&node->RBFIELD); \ + } \ + } \ + static inline void \ + RBNAME##_copy(struct rb_node *rb_old, struct rb_node *rb_new) \ + { \ + RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \ + RBSTRUCT *new_node = rb_entry(rb_new, RBSTRUCT, RBFIELD); \ + new_node->RBAUGMENTED = old->RBAUGMENTED; \ + } \ + static void \ + RBNAME##_rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ + { \ + RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \ + RBSTRUCT *new_node = rb_entry(rb_new, RBSTRUCT, RBFIELD); \ + new_node->RBAUGMENTED = old->RBAUGMENTED; \ + RBCOMPUTE(old, false); \ + } \ + RBSTATIC const struct rb_augment_callbacks RBNAME = { \ + .propagate = RBNAME##_propagate, \ + .copy = RBNAME##_copy, \ + .rotate = RBNAME##_rotate}; + +/* + * Template for declaring augmented rbtree callbacks, + * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes. + * + * RBSTATIC: 'static' or empty + * RBNAME: name of the rb_augment_callbacks structure + * RBSTRUCT: struct type of the tree nodes + * RBFIELD: name of struct rb_node field within RBSTRUCT + * RBTYPE: type of the RBAUGMENTED field + * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree + * RBCOMPUTE: name of function that returns the per-node RBTYPE scalar + */ + +#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \ + RBTYPE, RBAUGMENTED, RBCOMPUTE) \ + static inline bool RBNAME##_compute_max(RBSTRUCT *node, bool exit) \ + { \ + RBSTRUCT *child; \ + RBTYPE max = RBCOMPUTE(node); \ + if (node->RBFIELD.rb_left) \ + { \ + child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \ + if (child->RBAUGMENTED > max) \ + max = child->RBAUGMENTED; \ + } \ + if (node->RBFIELD.rb_right) \ + { \ + child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \ + if (child->RBAUGMENTED > max) \ + max = child->RBAUGMENTED; \ + } \ + if (exit && node->RBAUGMENTED == max) \ + return true; \ + node->RBAUGMENTED = max; \ + return false; \ + } \ + RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \ + RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME##_compute_max) + +#define RB_RED 0 +#define RB_BLACK 1 + +#define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) + +#define __rb_color(pc) ((pc) & 1) +#define __rb_is_black(pc) __rb_color(pc) +#define __rb_is_red(pc) (!__rb_color(pc)) +#define rb_color(rb) __rb_color((rb)->__rb_parent_color) +#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) +#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; +} + +static inline void rb_set_parent_color(struct rb_node *rb, + struct rb_node *p, int color) +{ + rb->__rb_parent_color = (unsigned long)p | color; +} + +static inline void +__rb_change_child(struct rb_node *old, struct rb_node *new_node, + struct rb_node *parent, struct rb_root *root) +{ + if (parent) + { + if (parent->rb_left == old) + parent->rb_left = new_node; + else + parent->rb_right = new_node; + } + else + root->rb_node = new_node; +} + +extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new_node)); + +static inline struct rb_node * +__rb_erase_augmented(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) +{ + struct rb_node *child = node->rb_right; + struct rb_node *tmp = node->rb_left; + struct rb_node *parent, *rebalance; + unsigned long pc; + + if (!tmp) + { + /* + * Case 1: node to erase has no more than 1 child (easy!) + * + * Note that if there is one child it must be red due to 5) + * and node must be black due to 4). We adjust colors locally + * so as to bypass __rb_erase_color() later on. + */ + pc = node->__rb_parent_color; + parent = __rb_parent(pc); + __rb_change_child(node, child, parent, root); + if (child) + { + child->__rb_parent_color = pc; + rebalance = NULL; + } + else + rebalance = __rb_is_black(pc) ? parent : NULL; + tmp = parent; + } + else if (!child) + { + /* Still case 1, but this time the child is node->rb_left */ + tmp->__rb_parent_color = pc = node->__rb_parent_color; + parent = __rb_parent(pc); + __rb_change_child(node, tmp, parent, root); + rebalance = NULL; + tmp = parent; + } + else + { + struct rb_node *successor = child, *child2; + + tmp = child->rb_left; + if (!tmp) + { + /* + * Case 2: node's successor is its right child + * + * (n) (s) + * / \ / \ + * (x) (s) -> (x) (c) + * \ + * (c) + */ + parent = successor; + child2 = successor->rb_right; + + augment->copy(node, successor); + } + else + { + /* + * Case 3: node's successor is leftmost under + * node's right child subtree + * + * (n) (s) + * / \ / \ + * (x) (y) -> (x) (y) + * / / + * (p) (p) + * / / + * (s) (c) + * \ + * (c) + */ + do + { + parent = successor; + successor = tmp; + tmp = tmp->rb_left; + } while (tmp); + child2 = successor->rb_right; + parent->rb_left = child2; + successor->rb_right = child; + rb_set_parent(child, successor); + + augment->copy(node, successor); + augment->propagate(parent, successor); + } + + tmp = node->rb_left; + successor->rb_left = tmp; + rb_set_parent(tmp, successor); + + pc = node->__rb_parent_color; + tmp = __rb_parent(pc); + __rb_change_child(node, successor, tmp, root); + + if (child2) + { + rb_set_parent_color(child2, parent, RB_BLACK); + rebalance = NULL; + } + else + { + rebalance = rb_is_black(successor) ? parent : NULL; + } + successor->__rb_parent_color = pc; + tmp = successor; + } + + augment->propagate(tmp, NULL); + return rebalance; +} + +static inline void +rb_erase_augmented(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) +{ + struct rb_node *rebalance = __rb_erase_augmented(node, root, augment); + if (rebalance) + __rb_erase_color(rebalance, root, augment->rotate); +} + +static inline void +rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root, + const struct rb_augment_callbacks *augment) +{ + if (root->rb_leftmost == node) + root->rb_leftmost = rb_next(node); + rb_erase_augmented(node, &root->rb_root, augment); +} + +#endif /* _LINUX_RBTREE_AUGMENTED_H */ |