From 36305a3db8c572e25a6335c9384a5112bdfd8148 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 7 Jun 2013 09:29:30 -0400 Subject: [PATCH] rcuja: below/equal result key Signed-off-by: Mathieu Desnoyers --- rcuja/rcuja.c | 59 ++++++++++++++++++++++++------------ tests/test_urcu_ja.c | 72 ++++++++++++++++++++++++-------------------- urcu/rcuja.h | 6 ++-- 3 files changed, 83 insertions(+), 54 deletions(-) diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 5252672..ef7619b 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -364,7 +364,7 @@ struct cds_ja_inode_flag *ja_linear_node_get_nth(const struct cds_ja_type *type, static struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type *type, struct cds_ja_inode *node, - int n, + int n, uint8_t *result_key, enum ja_direction dir) { uint8_t nr_child; @@ -411,6 +411,7 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type } assert(match_v >= 0 && match_v < JA_ENTRY_PER_NODE); + *result_key = (uint8_t) match_v; pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]); ptr = rcu_dereference(pointers[match_idx]); return ptr; @@ -491,7 +492,7 @@ struct cds_ja_inode *ja_pool_node_get_ith_pool(const struct cds_ja_type *type, static struct cds_ja_inode_flag *ja_pool_node_get_direction(const struct cds_ja_type *type, struct cds_ja_inode *node, - int n, + int n, uint8_t *result_key, enum ja_direction dir) { unsigned int pool_nr; @@ -536,6 +537,8 @@ struct cds_ja_inode_flag *ja_pool_node_get_direction(const struct cds_ja_type *t } } } + if (match_node_flag) + *result_key = (uint8_t) match_v; return match_node_flag; } @@ -561,7 +564,7 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type, static struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type *type, struct cds_ja_inode *node, - int n, + int n, uint8_t *result_key, enum ja_direction dir) { struct cds_ja_inode_flag **child_node_flag_ptr; @@ -579,6 +582,7 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type if (child_node_flag) { dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n", child_node_flag); + *result_key = i; return child_node_flag; } } @@ -590,6 +594,7 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type if (child_node_flag) { dbg_printf("ja_pigeon_node_get_right child_node_flag %p\n", child_node_flag); + *result_key = i; return child_node_flag; } } @@ -641,7 +646,7 @@ struct cds_ja_inode_flag *ja_node_get_nth(struct cds_ja_inode_flag *node_flag, static struct cds_ja_inode_flag *ja_node_get_direction(struct cds_ja_inode_flag *node_flag, - int n, + int n, uint8_t *result_key, enum ja_direction dir) { unsigned int type_index; @@ -655,11 +660,11 @@ struct cds_ja_inode_flag *ja_node_get_direction(struct cds_ja_inode_flag *node_f switch (type->type_class) { case RCU_JA_LINEAR: - return ja_linear_node_get_direction(type, node, n, dir); + return ja_linear_node_get_direction(type, node, n, result_key, dir); case RCU_JA_POOL: - return ja_pool_node_get_direction(type, node, n, dir); + return ja_pool_node_get_direction(type, node, n, result_key, dir); case RCU_JA_PIGEON: - return ja_pigeon_node_get_direction(type, node, n, dir); + return ja_pigeon_node_get_direction(type, node, n, result_key, dir); default: assert(0); return (void *) -1UL; @@ -668,23 +673,24 @@ struct cds_ja_inode_flag *ja_node_get_direction(struct cds_ja_inode_flag *node_f static struct cds_ja_inode_flag *ja_node_get_leftright(struct cds_ja_inode_flag *node_flag, - unsigned int n, + unsigned int n, uint8_t *result_key, enum ja_direction dir) { - return ja_node_get_direction(node_flag, n, dir); + return ja_node_get_direction(node_flag, n, result_key, dir); } static struct cds_ja_inode_flag *ja_node_get_minmax(struct cds_ja_inode_flag *node_flag, + uint8_t *result_key, enum ja_direction dir) { switch (dir) { case JA_LEFTMOST: return ja_node_get_direction(node_flag, - -1, JA_RIGHT); + -1, result_key, JA_RIGHT); case JA_RIGHTMOST: return ja_node_get_direction(node_flag, - JA_ENTRY_PER_NODE, JA_LEFT); + JA_ENTRY_PER_NODE, result_key, JA_LEFT); default: assert(0); } @@ -1801,10 +1807,12 @@ struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key) static struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, - enum ja_lookup_inequality mode) + uint64_t *result_key, enum ja_lookup_inequality mode) { int tree_depth, level; struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH]; + uint8_t cur_key[JA_MAX_DEPTH]; + uint64_t _result_key = 0; enum ja_direction dir; switch (mode) { @@ -1821,6 +1829,7 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, } memset(cur_node_depth, 0, sizeof(cur_node_depth)); + memset(cur_key, 0, sizeof(cur_key)); tree_depth = ja->tree_depth; node_flag = rcu_dereference(ja->root); cur_node_depth[0] = node_flag; @@ -1836,6 +1845,7 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, node_flag = ja_node_get_nth(node_flag, NULL, iter_key); if (!ja_node_ptr(node_flag)) break; + cur_key[level - 1] = iter_key; cur_node_depth[level] = node_flag; dbg_printf("cds_ja_lookup_inequality iter key lookup %u finds node_flag %p\n", (unsigned int) iter_key, node_flag); @@ -1843,6 +1853,8 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, if (level == tree_depth) { /* Last level lookup succeded. We got an equal match. */ + if (result_key) + *result_key = key; return (struct cds_ja_node *) node_flag; } @@ -1870,8 +1882,8 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1))); node_flag = ja_node_get_leftright(cur_node_depth[level - 1], - iter_key, dir); - /* If found left sibling, find rightmost/leftmost child. */ + iter_key, &cur_key[level - 1], dir); + /* If found left/right sibling, find rightmost/leftmost child. */ if (ja_node_ptr(node_flag)) break; } @@ -1905,24 +1917,33 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, assert(0); } for (; level < tree_depth; level++) { - node_flag = ja_node_get_minmax(node_flag, dir); + node_flag = ja_node_get_minmax(node_flag, &cur_key[level - 1], dir); if (!ja_node_ptr(node_flag)) break; } assert(level == tree_depth); + if (result_key) { + for (level = 1; level < tree_depth; level++) { + _result_key |= ((uint64_t) cur_key[level - 1]) + << (JA_BITS_PER_BYTE * (tree_depth - level - 1)); + } + *result_key = _result_key; + } return (struct cds_ja_node *) node_flag; } -struct cds_ja_node *cds_ja_lookup_below_equal(struct cds_ja *ja, uint64_t key) +struct cds_ja_node *cds_ja_lookup_below_equal(struct cds_ja *ja, + uint64_t key, uint64_t *result_key) { - return cds_ja_lookup_inequality(ja, key, JA_LOOKUP_BE); + return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_BE); } -struct cds_ja_node *cds_ja_lookup_above_equal(struct cds_ja *ja, uint64_t key) +struct cds_ja_node *cds_ja_lookup_above_equal(struct cds_ja *ja, + uint64_t key, uint64_t *result_key) { - return cds_ja_lookup_inequality(ja, key, JA_LOOKUP_AE); + return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_AE); } /* diff --git a/tests/test_urcu_ja.c b/tests/test_urcu_ja.c index 001d631..a552db1 100644 --- a/tests/test_urcu_ja.c +++ b/tests/test_urcu_ja.c @@ -330,19 +330,20 @@ int test_8bit_key(void) for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i] + ka_test_offset; rcu_read_lock(); - ja_node = cds_ja_lookup_below_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -351,19 +352,20 @@ int test_8bit_key(void) for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i] - ka_test_offset; rcu_read_lock(); - ja_node = cds_ja_lookup_above_equal(test_ja, key); + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -372,32 +374,33 @@ int test_8bit_key(void) for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i]; /* without offset */ rcu_read_lock(); - ja_node = cds_ja_lookup_below_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } - ja_node = cds_ja_lookup_above_equal(test_ja, key); + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -503,7 +506,7 @@ int test_16bit_key(void) } printf("OK\n"); - printf("Test #5: lookup below equal (16-bit).\n"); + printf("Test #5: lookup below/above equal (16-bit).\n"); for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct ja_test_node *node = node_alloc(); @@ -523,19 +526,20 @@ int test_16bit_key(void) for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i] + ka_test_offset; rcu_read_lock(); - ja_node = cds_ja_lookup_below_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -544,19 +548,20 @@ int test_16bit_key(void) for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i] - ka_test_offset; rcu_read_lock(); - ja_node = cds_ja_lookup_above_equal(test_ja, key); + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -565,32 +570,33 @@ int test_16bit_key(void) for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i]; /* without offset */ rcu_read_lock(); - ja_node = cds_ja_lookup_below_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } - ja_node = cds_ja_lookup_above_equal(test_ja, key); + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); if (!ja_node) { fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); diff --git a/urcu/rcuja.h b/urcu/rcuja.h index 5dd7baf..eb38494 100644 --- a/urcu/rcuja.h +++ b/urcu/rcuja.h @@ -74,6 +74,7 @@ struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key); * cds_ja_lookup_below_equal - look up first node with key <= @key. * @ja: the Judy array. * @key: key to look up. + * @result_key: key found. * * Returns the first node of a duplicate chain if a node is present in * the tree which has a key below or equal to @key, else returns NULL. @@ -81,12 +82,13 @@ struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key); * use of its return value. */ struct cds_ja_node *cds_ja_lookup_below_equal(struct cds_ja *ja, - uint64_t key); + uint64_t key, uint64_t *result_key); /* * cds_ja_lookup_above_equal - look up first node with key >= @key. * @ja: the Judy array. * @key: key to look up. + * @result_key: key found. * * Returns the first node of a duplicate chain if a node is present in * the tree which has a key above or equal to @key, else returns NULL. @@ -94,7 +96,7 @@ struct cds_ja_node *cds_ja_lookup_below_equal(struct cds_ja *ja, * use of its return value. */ struct cds_ja_node *cds_ja_lookup_above_equal(struct cds_ja *ja, - uint64_t key); + uint64_t key, uint64_t *result_key); /* * cds_ja_add - Add @node at @key, allowing duplicates. -- 2.34.1