Importing rbtree changes from nJScript.

6 files changed, 59 insertions, 169 deletions

diff --git a/src/nxt_event_timer.c b/src/nxt_event_timer.c
index e9615f92..56514683 100644
--- a/src/nxt_event_timer.c
+++ b/src/nxt_event_timer.c
@@ -22,7 +22,7 @@
  * the changes array and should be used only if the timer memory must be freed.
  */
 
-static nxt_int_t nxt_event_timer_rbtree_compare(nxt_rbtree_node_t *node1,
+static intptr_t nxt_event_timer_rbtree_compare(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2);
 static void nxt_event_timer_change(nxt_event_timers_t *timers,
     nxt_event_timer_t *ev, nxt_msec_t time);
@@ -34,7 +34,7 @@ static void nxt_event_timer_drop_changes(nxt_event_timers_t *timers,
 nxt_int_t
 nxt_event_timers_init(nxt_event_timers_t *timers, nxt_uint_t mchanges)
 {
-    nxt_rbtree_init(&timers->tree, nxt_event_timer_rbtree_compare, NULL);
+    nxt_rbtree_init(&timers->tree, nxt_event_timer_rbtree_compare);
 
     timers->mchanges = mchanges;
 
@@ -48,7 +48,7 @@ nxt_event_timers_init(nxt_event_timers_t *timers, nxt_uint_t mchanges)
 }
 
 
-static nxt_int_t
+static intptr_t
 nxt_event_timer_rbtree_compare(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2)
 {
diff --git a/src/nxt_mem_cache_pool.c b/src/nxt_mem_cache_pool.c
index e949dff9..4f4502e0 100644
--- a/src/nxt_mem_cache_pool.c
+++ b/src/nxt_mem_cache_pool.c
@@ -123,7 +123,7 @@ static nxt_mem_cache_block_t *
     nxt_mem_cache_alloc_cluster(nxt_mem_cache_pool_t *pool);
 static void *nxt_mem_cache_alloc_large(nxt_mem_cache_pool_t *pool,
     size_t alignment, size_t size);
-static nxt_int_t nxt_mem_cache_rbtree_compare(nxt_rbtree_node_t *node1,
+static intptr_t nxt_mem_cache_rbtree_compare(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2);
 static nxt_mem_cache_block_t *nxt_mem_cache_find_block(nxt_rbtree_t *tree,
     u_char *p);
@@ -202,7 +202,7 @@ nxt_mem_cache_pool_fast_create(size_t cluster_size, size_t page_alignment,
         pool->chunk_size_shift = nxt_mem_cache_shift(min_chunk_size);
         pool->page_size_shift = nxt_mem_cache_shift(page_size);
 
-        nxt_rbtree_init(&pool->pages, nxt_mem_cache_rbtree_compare, NULL);
+        nxt_rbtree_init(&pool->pages, nxt_mem_cache_rbtree_compare);
 
         nxt_queue_init(&pool->free_pages);
     }
@@ -572,7 +572,7 @@ nxt_mem_cache_alloc_large(nxt_mem_cache_pool_t *pool, size_t alignment,
 }
 
 
-static nxt_int_t
+static intptr_t
 nxt_mem_cache_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
 {
     nxt_mem_cache_block_t  *block1, *block2;
diff --git a/src/nxt_mem_zone.c b/src/nxt_mem_zone.c
index 02dd4328..eacb455d 100644
--- a/src/nxt_mem_zone.c
+++ b/src/nxt_mem_zone.c
@@ -138,7 +138,7 @@ static void *nxt_mem_zone_slots_init(nxt_mem_zone_t *zone,
     nxt_uint_t page_size);
 static void nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot,
     nxt_uint_t page_size);
-static nxt_int_t nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1,
+static intptr_t nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2);
 static void *nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone,
     nxt_mem_zone_slot_t *slot, size_t size);
@@ -204,7 +204,7 @@ nxt_mem_zone_init(u_char *start, size_t zone_size, nxt_uint_t page_size)
 
     /* rbtree of free pages. */
 
-    nxt_rbtree_init(&zone->free_pages, nxt_mem_zone_rbtree_compare, NULL);
+    nxt_rbtree_init(&zone->free_pages, nxt_mem_zone_rbtree_compare);
 
     block = (nxt_mem_zone_free_block_t *) zone->start;
     block->size = pages;
@@ -391,7 +391,7 @@ nxt_next_highest_power_of_two(uint32_t n)
 }
 
 
-static nxt_int_t
+static intptr_t
 nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
 {
     u_char                     *start1, *end1, *start2, *end2;
diff --git a/src/nxt_rbtree.c b/src/nxt_rbtree.c
index ff043d59..3fa5287d 100644
--- a/src/nxt_rbtree.c
+++ b/src/nxt_rbtree.c
@@ -26,23 +26,13 @@ nxt_inline void nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst,
 #define NXT_RBTREE_RED    1
 
 
-#define nxt_rbtree_set_callback_type(tree, type)                              \
-    (tree)->sentinel.spare = type
-
-#define nxt_rbtree_has_insertion_callback(tree)                               \
-    ((tree)->sentinel.spare != 0)
-
 #define nxt_rbtree_comparison_callback(tree)                                  \
     ((nxt_rbtree_compare_t) (tree)->sentinel.right)
 
 
 void
-nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare,
-    nxt_rbtree_insert_t insert)
+nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare)
 {
-    void        *callback;
-    nxt_bool_t  insertion;
-
     /*
      * The sentinel is used as a leaf node sentinel and as a tree root
      * sentinel: it is a parent of a root node and the root node is
@@ -56,13 +46,10 @@ nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare,
     tree->sentinel.left = &tree->sentinel;
 
     /*
-     * The sentinel's right child is never used so either insertion
-     * or comparison callback can be safely stored here.
+     * The sentinel's right child is never used so
+     * comparison callback can be safely stored here.
      */
-    insertion = (insert != NULL);
-    nxt_rbtree_set_callback_type(tree, insertion);
-    callback = insertion ? (void *) insert : (void *) compare;
-    tree->sentinel.right = callback;
+    tree->sentinel.right = (void *) compare;
 
     /* The root and leaf sentinel must be black. */
     tree->sentinel.color = NXT_RBTREE_BLACK;
@@ -72,9 +59,7 @@ nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare,
 void
 nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 {
-    void                  *callback;
     nxt_rbtree_node_t     *node, *new_node, *sentinel, **child;
-    nxt_rbtree_insert_t   insert;
     nxt_rbtree_compare_t  compare;
 
     new_node = (nxt_rbtree_node_t *) part;
@@ -86,32 +71,21 @@ nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
     new_node->right = sentinel;
     new_node->color = NXT_RBTREE_RED;
 
-    callback = tree->sentinel.right;
-
-    if (nxt_rbtree_has_insertion_callback(tree)) {
-        insert = (nxt_rbtree_insert_t) callback;
-
-        insert(node, new_node, sentinel);
-
-    } else {
-        compare = (nxt_rbtree_compare_t) callback;
-
-        child = &nxt_rbtree_root(tree);
+    compare = (nxt_rbtree_compare_t) tree->sentinel.right;
+    child = &nxt_rbtree_root(tree);
 
-        while (*child != sentinel) {
-            node = *child;
+    while (*child != sentinel) {
+        node = *child;
 
-            nxt_prefetch(node->left);
-            nxt_prefetch(node->right);
+        nxt_prefetch(node->left);
+        nxt_prefetch(node->right);
 
-            child = (compare(new_node, node) < 0) ? &node->left : &node->right;
-        }
-
-        *child = new_node;
-
-        new_node->parent = node;
+        child = (compare(new_node, node) < 0) ? &node->left : &node->right;
     }
 
+    *child = new_node;
+    new_node->parent = node;
+
     nxt_rbtree_insert_fixup(new_node);
 
     node = nxt_rbtree_root(tree);
@@ -158,8 +132,12 @@ nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
                 grandparent = parent->parent;
                 grandparent->color = NXT_RBTREE_RED;
                 nxt_rbtree_right_rotate(grandparent);
-
-                continue;
+                /*
+                 * nxt_rbtree_right_rotate() does not change node->parent
+                 * color which is now black, so testing color is not required
+                 * to return from function.
+                 */
+                return;
             }
 
         } else {
@@ -179,7 +157,8 @@ nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
                 grandparent->color = NXT_RBTREE_RED;
                 nxt_rbtree_left_rotate(grandparent);
 
-                continue;
+                /* See the comment in the symmetric branch above. */
+                return;
             }
         }
 
@@ -195,7 +174,7 @@ nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
 nxt_rbtree_node_t *
 nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 {
-    nxt_int_t             n;
+    intptr_t              n;
     nxt_rbtree_node_t     *node, *next, *sentinel;
     nxt_rbtree_compare_t  compare;
 
@@ -229,7 +208,7 @@ nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 nxt_rbtree_node_t *
 nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 {
-    nxt_int_t             n;
+    intptr_t              n;
     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
     nxt_rbtree_compare_t  compare;
 
@@ -266,7 +245,7 @@ nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 nxt_rbtree_node_t *
 nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 {
-    nxt_int_t             n;
+    intptr_t              n;
     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
     nxt_rbtree_compare_t  compare;
 
@@ -303,7 +282,7 @@ nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 void
 nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
 {
-    nxt_uint_t         color;
+    uint8_t            color;
     nxt_rbtree_node_t  *node, *sentinel, *subst, *child;
 
     node = (nxt_rbtree_node_t *) part;
diff --git a/src/nxt_rbtree.h b/src/nxt_rbtree.h
index 63b759fb..0f2e2fb1 100644
--- a/src/nxt_rbtree.h
+++ b/src/nxt_rbtree.h
@@ -11,44 +11,44 @@
 typedef struct nxt_rbtree_node_s  nxt_rbtree_node_t;
 
 struct nxt_rbtree_node_s {
-    nxt_rbtree_node_t  *left;
-    nxt_rbtree_node_t  *right;
-    nxt_rbtree_node_t  *parent;
+    nxt_rbtree_node_t         *left;
+    nxt_rbtree_node_t         *right;
+    nxt_rbtree_node_t         *parent;
 
-    uint8_t            color;
-    uint8_t            spare;
+    uint8_t                   color;
 };
 
 
 typedef struct {
-    nxt_rbtree_node_t  *left;
-    nxt_rbtree_node_t  *right;
-    nxt_rbtree_node_t  *parent;
+    nxt_rbtree_node_t         *left;
+    nxt_rbtree_node_t         *right;
+    nxt_rbtree_node_t         *parent;
 } nxt_rbtree_part_t;
 
 
 #define NXT_RBTREE_NODE(node)                                                 \
-    nxt_rbtree_part_t  node;                                                  \
-    uint8_t            color
+    nxt_rbtree_part_t         node;                                           \
+    uint8_t                   node##_color
 
 
 #define NXT_RBTREE_NODE_INIT  { NULL, NULL, NULL }, 0
 
 
 typedef struct {
-    nxt_rbtree_node_t  sentinel;
+    nxt_rbtree_node_t         sentinel;
 } nxt_rbtree_t;
 
 
-typedef void (*nxt_rbtree_insert_t)(nxt_rbtree_node_t *root,
-    nxt_rbtree_node_t *node, nxt_rbtree_node_t *sentinel);
-
-typedef nxt_int_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1,
+/*
+ * A comparison function should return intptr_t result because
+ * this eliminates overhead required to implement correct addresses
+ * comparison without result truncation.
+ */
+typedef intptr_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2);
 
 
-#define                                                                       \
-nxt_rbtree_root(tree)                                                         \
+#define nxt_rbtree_root(tree)                                                 \
     ((tree)->sentinel.left)
 
 
@@ -105,14 +105,14 @@ nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
 
 
 NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree,
-    nxt_rbtree_compare_t compare, nxt_rbtree_insert_t insert);
+    nxt_rbtree_compare_t compare);
 NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
 NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree,
     nxt_rbtree_part_t *node);
 NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree,
     nxt_rbtree_part_t *node);
-NXT_EXPORT nxt_rbtree_node_t *
-    nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree,
+NXT_EXPORT nxt_rbtree_node_t
+    *nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree,
     nxt_rbtree_part_t *node);
 NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
 
diff --git a/test/nxt_rbtree_unit_test.c b/test/nxt_rbtree_unit_test.c
index d5122e2a..9f38d2c3 100644
--- a/test/nxt_rbtree_unit_test.c
+++ b/test/nxt_rbtree_unit_test.c
@@ -7,24 +7,14 @@
 #include <nxt_main.h>
 
 
-#define NXT_RBTREE_COMPARISON  1
-
-
 typedef struct {
     NXT_RBTREE_NODE  (node);
     uint32_t         key;
 } nxt_rbtree_test_t;
 
 
-#if (NXT_RBTREE_COMPARISON)
-static nxt_int_t nxt_rbtree_unit_test_comparison(nxt_rbtree_node_t *node1,
+static intptr_t nxt_rbtree_unit_test_comparison(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2);
-#else
-static void nxt_rbtree_unit_test_insertion(nxt_rbtree_node_t *node,
-    nxt_rbtree_node_t *new_node, nxt_rbtree_node_t *sentinel);
-static nxt_rbtree_test_t *nxt_rbtree_unit_test_find(nxt_rbtree_t *tree,
-    uint32_t key);
-#endif
 static nxt_int_t nxt_rbtree_unit_test_compare(uint32_t key1, uint32_t key2);
 static int nxt_cdecl nxt_rbtree_unit_test_sort_cmp(const void *one,
     const void *two);
@@ -45,11 +35,7 @@ nxt_rbtree_unit_test(nxt_thread_t *thr, nxt_uint_t n)
 
     nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree unit test started: %ui", n);
 
-#if (NXT_RBTREE_COMPARISON)
-    nxt_rbtree_init(&tree, nxt_rbtree_unit_test_comparison, NULL);
-#else
-    nxt_rbtree_init(&tree, NULL, nxt_rbtree_unit_test_insertion);
-#endif
+    nxt_rbtree_init(&tree, nxt_rbtree_unit_test_comparison);
 
     mark = tree.sentinel.right;
 
@@ -83,13 +69,9 @@ nxt_rbtree_unit_test(nxt_thread_t *thr, nxt_uint_t n)
     }
 
     for (i = 0; i < n; i++) {
-#if (NXT_RBTREE_COMPARISON)
         node = nxt_rbtree_find(&tree, &items[i].node);
 
         if (node != (nxt_rbtree_node_t *) &items[i].node) {
-#else
-        if (nxt_rbtree_unit_test_find(&tree, items[i].key) != &items[i]) {
-#endif
             nxt_log_alert(thr->log, "rbtree unit test failed: %08XD not found",
                           items[i].key);
             goto fail;
@@ -155,9 +137,7 @@ fail:
 }
 
 
-#if (NXT_RBTREE_COMPARISON)
-
-static nxt_int_t
+static intptr_t
 nxt_rbtree_unit_test_comparison(nxt_rbtree_node_t *node1,
     nxt_rbtree_node_t *node2)
 {
@@ -169,71 +149,6 @@ nxt_rbtree_unit_test_comparison(nxt_rbtree_node_t *node1,
     return nxt_rbtree_unit_test_compare(item1->key, item2->key);
 }
 
-#else
-
-static void
-nxt_rbtree_unit_test_insertion(nxt_rbtree_node_t *node,
-    nxt_rbtree_node_t *new_node, nxt_rbtree_node_t *sentinel)
-{
-    nxt_int_t          n;
-    nxt_rbtree_node_t  **child;
-    nxt_rbtree_test_t  *item, *new_item;
-
-    new_item = (nxt_rbtree_test_t *) new_node;
-    child = &node;
-
-    while (*child != sentinel) {
-        node = *child;
-
-        nxt_prefetch(node->left);
-        nxt_prefetch(node->right);
-
-        item = (nxt_rbtree_test_t *) node;
-
-        n = nxt_rbtree_unit_test_compare(new_item->key, item->key);
-        child = (n < 0) ? &node->left : &node->right;
-    }
-
-    *child = new_node;
-
-    new_node->parent = node;
-}
-
-
-static nxt_rbtree_test_t *
-nxt_rbtree_unit_test_find(nxt_rbtree_t *tree, uint32_t key)
-{
-    nxt_int_t          n;
-    nxt_rbtree_node_t  *next, *sentinel;
-    nxt_rbtree_test_t  *item;
-
-    next = nxt_rbtree_root(tree);
-    sentinel = nxt_rbtree_sentinel(tree);
-
-    while (next != sentinel) {
-        nxt_prefetch(next->left);
-        nxt_prefetch(next->right);
-
-        item = (nxt_rbtree_test_t *) next;
-
-        n = nxt_rbtree_unit_test_compare(key, item->key);
-
-        if (n < 0) {
-            next = next->left;
-
-        } else if (n > 0) {
-            next = next->right;
-
-        } else {
-            return (nxt_rbtree_test_t *) next;
-        }
-    }
-
-    return NULL;
-}
-
-#endif
-
 
 /*
  * Subtraction cannot be used in these comparison functions because
@@ -298,11 +213,7 @@ nxt_rbtree_mb_start(nxt_thread_t *thr)
         return NXT_ERROR;
     }
 
-#if (NXT_RBTREE_COMPARISON)
-    nxt_rbtree_init(&mb_tree, nxt_rbtree_unit_test_comparison, NULL);
-#else
-    nxt_rbtree_init(&mb_tree, NULL, nxt_rbtree_unit_test_insertion);
-#endif
+    nxt_rbtree_init(&mb_tree, nxt_rbtree_unit_test_comparison);
 
     key = 0;