Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
static
struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type *type,
struct cds_ja_inode *node,
static
struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type *type,
struct cds_ja_inode *node,
+ int n, uint8_t *result_key,
enum ja_direction dir)
{
uint8_t nr_child;
enum ja_direction dir)
{
uint8_t nr_child;
}
assert(match_v >= 0 && match_v < JA_ENTRY_PER_NODE);
}
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;
pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
ptr = rcu_dereference(pointers[match_idx]);
return ptr;
static
struct cds_ja_inode_flag *ja_pool_node_get_direction(const struct cds_ja_type *type,
struct cds_ja_inode *node,
static
struct cds_ja_inode_flag *ja_pool_node_get_direction(const struct cds_ja_type *type,
struct cds_ja_inode *node,
+ int n, uint8_t *result_key,
enum ja_direction dir)
{
unsigned int pool_nr;
enum ja_direction dir)
{
unsigned int pool_nr;
+ if (match_node_flag)
+ *result_key = (uint8_t) match_v;
return match_node_flag;
}
return match_node_flag;
}
static
struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type *type,
struct cds_ja_inode *node,
static
struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type *type,
struct cds_ja_inode *node,
+ int n, uint8_t *result_key,
enum ja_direction dir)
{
struct cds_ja_inode_flag **child_node_flag_ptr;
enum ja_direction dir)
{
struct cds_ja_inode_flag **child_node_flag_ptr;
if (child_node_flag) {
dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n",
child_node_flag);
if (child_node_flag) {
dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n",
child_node_flag);
return child_node_flag;
}
}
return child_node_flag;
}
}
if (child_node_flag) {
dbg_printf("ja_pigeon_node_get_right child_node_flag %p\n",
child_node_flag);
if (child_node_flag) {
dbg_printf("ja_pigeon_node_get_right child_node_flag %p\n",
child_node_flag);
return child_node_flag;
}
}
return child_node_flag;
}
}
static
struct cds_ja_inode_flag *ja_node_get_direction(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, uint8_t *result_key,
enum ja_direction dir)
{
unsigned int type_index;
enum ja_direction dir)
{
unsigned int type_index;
switch (type->type_class) {
case RCU_JA_LINEAR:
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);
- return ja_pool_node_get_direction(type, node, n, dir);
+ return ja_pool_node_get_direction(type, node, n, result_key, dir);
- 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;
default:
assert(0);
return (void *) -1UL;
static
struct cds_ja_inode_flag *ja_node_get_leftright(struct cds_ja_inode_flag *node_flag,
static
struct cds_ja_inode_flag *ja_node_get_leftright(struct cds_ja_inode_flag *node_flag,
+ unsigned int n, uint8_t *result_key,
- 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,
}
static
struct cds_ja_inode_flag *ja_node_get_minmax(struct cds_ja_inode_flag *node_flag,
enum ja_direction dir)
{
switch (dir) {
case JA_LEFTMOST:
return ja_node_get_direction(node_flag,
enum ja_direction dir)
{
switch (dir) {
case JA_LEFTMOST:
return ja_node_get_direction(node_flag,
+ -1, result_key, JA_RIGHT);
case JA_RIGHTMOST:
return ja_node_get_direction(node_flag,
case JA_RIGHTMOST:
return ja_node_get_direction(node_flag,
- JA_ENTRY_PER_NODE, JA_LEFT);
+ JA_ENTRY_PER_NODE, result_key, JA_LEFT);
static
struct cds_ja_node *cds_ja_lookup_inequality(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];
{
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) {
enum ja_direction dir;
switch (mode) {
}
memset(cur_node_depth, 0, sizeof(cur_node_depth));
}
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;
tree_depth = ja->tree_depth;
node_flag = rcu_dereference(ja->root);
cur_node_depth[0] = node_flag;
node_flag = ja_node_get_nth(node_flag, NULL, iter_key);
if (!ja_node_ptr(node_flag))
break;
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);
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);
if (level == tree_depth) {
/* Last level lookup succeded. We got an equal match. */
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;
}
return (struct cds_ja_node *) node_flag;
}
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 = (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;
}
if (ja_node_ptr(node_flag))
break;
}
assert(0);
}
for (; level < tree_depth; level++) {
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 (!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;
}
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);
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
key = ka[i] + ka_test_offset;
rcu_read_lock();
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 (!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();
assert(0);
}
rcu_read_unlock();
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
key = ka[i] - ka_test_offset;
rcu_read_lock();
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 (!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();
assert(0);
}
rcu_read_unlock();
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
key = ka[i]; /* without offset */
rcu_read_lock();
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 (!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);
- 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 (!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();
assert(0);
}
rcu_read_unlock();
- 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();
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct ja_test_node *node = node_alloc();
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
key = ka[i] + ka_test_offset;
rcu_read_lock();
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 (!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();
assert(0);
}
rcu_read_unlock();
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
key = ka[i] - ka_test_offset;
rcu_read_lock();
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 (!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();
assert(0);
}
rcu_read_unlock();
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
struct cds_ja_node *ja_node;
struct ja_test_node *node;
key = ka[i]; /* without offset */
rcu_read_lock();
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 (!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);
- 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 (!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();
assert(0);
}
rcu_read_unlock();
* cds_ja_lookup_below_equal - look up first node with key <= @key.
* @ja: the Judy array.
* @key: key to look up.
* 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.
*
* 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.
* use of its return value.
*/
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_below_equal(struct cds_ja *ja,
+ 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.
/*
* 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.
*
* 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.
* use of its return value.
*/
struct cds_ja_node *cds_ja_lookup_above_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 *result_key);
/*
* cds_ja_add - Add @node at @key, allowing duplicates.
/*
* cds_ja_add - Add @node at @key, allowing duplicates.