diff options
| -rw-r--r-- | src/nxt_event_timer.c | 6 | ||||
| -rw-r--r-- | src/nxt_mem_cache_pool.c | 6 | ||||
| -rw-r--r-- | src/nxt_mem_zone.c | 6 | ||||
| -rw-r--r-- | src/nxt_rbtree.c | 73 | ||||
| -rw-r--r-- | src/nxt_rbtree.h | 40 | ||||
| -rw-r--r-- | test/nxt_rbtree_unit_test.c | 97 |
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; |