From 291b254376625f7cf3b11c0aa7ab257b9354b2db Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 3 Jun 2013 00:42:44 -0400 Subject: [PATCH] rcuja: implement lookup_lower_equal Signed-off-by: Mathieu Desnoyers --- rcuja/rcuja.c | 208 ++++++++++++++++++++++++++++++++++++++++++++++++++ urcu/rcuja.h | 2 + 2 files changed, 210 insertions(+) diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 41ac70c..b9ece1a 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -370,6 +370,43 @@ struct cds_ja_inode_flag *ja_linear_node_get_nth(const struct cds_ja_type *type, return ptr; } +static +struct cds_ja_inode_flag *ja_linear_node_get_left(const struct cds_ja_type *type, + struct cds_ja_inode *node, + unsigned int n) +{ + uint8_t nr_child; + uint8_t *values; + struct cds_ja_inode_flag **pointers; + struct cds_ja_inode_flag *ptr; + unsigned int i, match_idx; + int match_v = -1; + + assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL); + + nr_child = ja_linear_node_get_nr_child(type, node); + cmm_smp_rmb(); /* read nr_child before values and pointers */ + assert(nr_child <= type->max_linear_child); + assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child); + + values = &node->u.data[1]; + for (i = 0; i < nr_child; i++) { + unsigned int v; + + v = CMM_LOAD_SHARED(values[i]); + if (v < n && (int) v > match_v) { + match_v = v; + match_idx = i; + } + } + if (match_v < 0) { + return NULL; + } + pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]); + ptr = rcu_dereference(pointers[match_idx]); + return ptr; +} + static void ja_linear_node_get_ith_pos(const struct cds_ja_type *type, struct cds_ja_inode *node, @@ -442,6 +479,42 @@ struct cds_ja_inode *ja_pool_node_get_ith_pool(const struct cds_ja_type *type, &node->u.data[(unsigned int) i << type->pool_size_order]; } +static +struct cds_ja_inode_flag *ja_pool_node_get_left(const struct cds_ja_type *type, + struct cds_ja_inode *node, + unsigned int n) +{ + unsigned int pool_nr; + int match_v = -1; + struct cds_ja_inode_flag *match_node_flag = NULL; + + assert(type->type_class == RCU_JA_POOL); + + for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) { + struct cds_ja_inode *pool = + ja_pool_node_get_ith_pool(type, + node, pool_nr); + uint8_t nr_child = + ja_linear_node_get_nr_child(type, pool); + unsigned int j; + + for (j = 0; j < nr_child; j++) { + struct cds_ja_inode_flag *iter; + uint8_t v; + + ja_linear_node_get_ith_pos(type, pool, + j, &v, &iter); + if (!iter) + continue; + if (v < n && (int) v > match_v) { + match_v = v; + match_node_flag = iter; + } + } + } + return match_node_flag; +} + static struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type, struct cds_ja_inode *node, @@ -461,6 +534,30 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type, return child_node_flag; } +static +struct cds_ja_inode_flag *ja_pigeon_node_get_left(const struct cds_ja_type *type, + struct cds_ja_inode *node, + unsigned int n) +{ + struct cds_ja_inode_flag **child_node_flag_ptr; + struct cds_ja_inode_flag *child_node_flag; + int i; + + assert(type->type_class == RCU_JA_PIGEON); + + /* n - 1 is first value left of n */ + for (i = n - 1; i >= 0; i--) { + child_node_flag_ptr = &((struct cds_ja_inode_flag **) node->u.data)[i]; + child_node_flag = rcu_dereference(*child_node_flag_ptr); + if (child_node_flag) { + dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n", + child_node_flag); + return child_node_flag; + } + } + return NULL; +} + static struct cds_ja_inode_flag *ja_pigeon_node_get_ith_pos(const struct cds_ja_type *type, struct cds_ja_inode *node, @@ -503,6 +600,38 @@ 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_left(struct cds_ja_inode_flag *node_flag, + unsigned int n) +{ + unsigned int type_index; + struct cds_ja_inode *node; + const struct cds_ja_type *type; + + node = ja_node_ptr(node_flag); + assert(node != NULL); + type_index = ja_node_type(node_flag); + type = &ja_types[type_index]; + + switch (type->type_class) { + case RCU_JA_LINEAR: + return ja_linear_node_get_left(type, node, n); + case RCU_JA_POOL: + return ja_pool_node_get_left(type, node, n); + case RCU_JA_PIGEON: + return ja_pigeon_node_get_left(type, node, n); + default: + assert(0); + return (void *) -1UL; + } +} + +static +struct cds_ja_inode_flag *ja_node_get_rightmost(struct cds_ja_inode_flag *node_flag) +{ + return ja_node_get_left(node_flag, JA_ENTRY_PER_NODE); +} + static int ja_linear_node_set_nth(const struct cds_ja_type *type, struct cds_ja_inode *node, @@ -1610,6 +1739,85 @@ struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key) return head; } +struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) +{ + int tree_depth, level; + struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH]; + struct cds_hlist_head head = { NULL }; + + if (caa_unlikely(key > ja->key_max || !key)) + return head; + + memset(cur_node_depth, 0, sizeof(cur_node_depth)); + tree_depth = ja->tree_depth; + node_flag = rcu_dereference(ja->root); + cur_node_depth[0] = node_flag; + + /* level 0: root node */ + if (!ja_node_ptr(node_flag)) + return head; + + for (level = 1; level < tree_depth; level++) { + uint8_t iter_key; + + iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1))); + node_flag = ja_node_get_nth(node_flag, NULL, iter_key); + if (!ja_node_ptr(node_flag)) + break; + cur_node_depth[level] = node_flag; + dbg_printf("cds_ja_lookup 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. */ + head.next = (struct cds_hlist_node *) node_flag; + return head; + } + + /* + * Find highest value left of current node. + * Current node is cur_node_depth[level]. + * Start at current level. If we cannot find any key left of + * ours, go one level up, seek highest value left of current + * (recursively), and when we find one, get the rightmost child + * of its rightmost child (recursively). + */ + for (; level > 0; level--) { + uint8_t iter_key; + + iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1))); + node_flag = ja_node_get_left(cur_node_depth[level - 1], + iter_key); + /* If found left sibling, find rightmost child. */ + if (ja_node_ptr(node_flag)) + break; + } + + if (!level) { + /* Reached the root and could not find a left sibling. */ + return head; + } + + level++; + /* Find rightmost child of rightmost child (recursively). */ + for (; level < tree_depth; level++) { + node_flag = ja_node_get_rightmost(node_flag); + /* If found left sibling, find rightmost child. */ + if (!ja_node_ptr(node_flag)) + break; + } + + if (level == tree_depth) { + /* Last level lookup succeded. We got a "lower than" match. */ + head.next = (struct cds_hlist_node *) node_flag; + return head; + } + + /* No match */ + return head; +} + /* * We reached an unpopulated node. Create it and the children we need, * and then attach the entire branch to the current node. This may diff --git a/urcu/rcuja.h b/urcu/rcuja.h index 0ab0518..e66ce7e 100644 --- a/urcu/rcuja.h +++ b/urcu/rcuja.h @@ -58,6 +58,8 @@ void cds_ja_node_init(struct cds_ja_node *node) } struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key); +struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, + uint64_t key); int cds_ja_add(struct cds_ja *ja, uint64_t key, struct cds_ja_node *new_node); -- 2.34.1