Add linux kernel interval tree

1 files changed, 143 insertions, 263 deletions

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