X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=364570e81ec9d35dbb589a0e7ab2b1b2821809ac;hb=53f943b0e6c87e60283248a099f70d43ce418116;hp=22ee01cef781e3977ba4884538b66a08697b633a;hpb=1b34283b72f272bffc9258306173b1cfe2e3ce8e;p=userspace-rcu.git

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index 22ee01c..364570e 100644
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -247,6 +247,18 @@ enum ja_recompact {
 	JA_RECOMPACT_DEL,
 };
 
+enum ja_lookup_inequality {
+	JA_LOOKUP_BE,
+	JA_LOOKUP_AE,
+};
+
+enum ja_direction {
+	JA_LEFT,
+	JA_RIGHT,
+	JA_LEFTMOST,
+	JA_RIGHTMOST,
+};
+
 static
 struct cds_ja_inode *_ja_node_mask_ptr(struct cds_ja_inode_flag *node)
 {
@@ -350,18 +362,26 @@ 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_left(const struct cds_ja_type *type,
+struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
-		unsigned int n)
+		int n, uint8_t *result_key,
+		enum ja_direction dir)
 {
 	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;
+	unsigned int i;
+	int match_idx = -1, match_v;
 
 	assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
+	assert(dir == JA_LEFT || dir == JA_RIGHT);
+
+	if (dir == JA_LEFT) {
+		match_v = -1;
+	} else {
+		match_v = JA_ENTRY_PER_NODE;
+	}
 
 	nr_child = ja_linear_node_get_nr_child(type, node);
 	cmm_smp_rmb();	/* read nr_child before values and pointers */
@@ -373,14 +393,25 @@ struct cds_ja_inode_flag *ja_linear_node_get_left(const struct cds_ja_type *type
 		unsigned int v;
 
 		v = CMM_LOAD_SHARED(values[i]);
-		if (v < n && (int) v > match_v) {
-			match_v = v;
-			match_idx = i;
+		if (dir == JA_LEFT) {
+			if ((int) v < n && (int) v > match_v) {
+				match_v = v;
+				match_idx = i;
+			}
+		} else {
+			if ((int) v > n && (int) v < match_v) {
+				match_v = v;
+				match_idx = i;
+			}
 		}
 	}
-	if (match_v < 0) {
+
+	if (match_idx < 0) {
 		return NULL;
 	}
+	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;
@@ -459,15 +490,23 @@ 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_left(const struct cds_ja_type *type,
+struct cds_ja_inode_flag *ja_pool_node_get_direction(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
-		unsigned int n)
+		int n, uint8_t *result_key,
+		enum ja_direction dir)
 {
 	unsigned int pool_nr;
-	int match_v = -1;
+	int match_v;
 	struct cds_ja_inode_flag *match_node_flag = NULL;
 
 	assert(type->type_class == RCU_JA_POOL);
+	assert(dir == JA_LEFT || dir == JA_RIGHT);
+
+	if (dir == JA_LEFT) {
+		match_v = -1;
+	} else {
+		match_v = JA_ENTRY_PER_NODE;
+	}
 
 	for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
 		struct cds_ja_inode *pool =
@@ -485,12 +524,21 @@ struct cds_ja_inode_flag *ja_pool_node_get_left(const struct cds_ja_type *type,
 					j, &v, &iter);
 			if (!iter)
 				continue;
-			if (v < n && (int) v > match_v) {
-				match_v = v;
-				match_node_flag = iter;
+			if (dir == JA_LEFT) {
+				if ((int) v < n && (int) v > match_v) {
+					match_v = v;
+					match_node_flag = iter;
+				}
+			} else {
+				if ((int) v > n && (int) v < match_v) {
+					match_v = v;
+					match_node_flag = iter;
+				}
 			}
 		}
 	}
+	if (match_node_flag)
+		*result_key = (uint8_t) match_v;
 	return match_node_flag;
 }
 
@@ -514,24 +562,41 @@ 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_left(const struct cds_ja_type *type,
+struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
-		unsigned int n)
+		int n, uint8_t *result_key,
+		enum ja_direction dir)
 {
 	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;
+	assert(dir == JA_LEFT || dir == JA_RIGHT);
+
+	if (dir == JA_LEFT) {
+		/* 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);
+				*result_key = (uint8_t) i;
+				return child_node_flag;
+			}
+		}
+	} else {
+		/* n + 1 is first value right of n */
+		for (i = n + 1; i < JA_ENTRY_PER_NODE; 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_right child_node_flag %p\n",
+					child_node_flag);
+				*result_key = (uint8_t) i;
+				return child_node_flag;
+			}
 		}
 	}
 	return NULL;
@@ -580,8 +645,9 @@ 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)
+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;
 	struct cds_ja_inode *node;
@@ -594,11 +660,11 @@ struct cds_ja_inode_flag *ja_node_get_left(struct cds_ja_inode_flag *node_flag,
 
 	switch (type->type_class) {
 	case RCU_JA_LINEAR:
-		return ja_linear_node_get_left(type, node, n);
+		return ja_linear_node_get_direction(type, node, n, result_key, dir);
 	case RCU_JA_POOL:
-		return ja_pool_node_get_left(type, node, n);
+		return ja_pool_node_get_direction(type, node, n, result_key, dir);
 	case RCU_JA_PIGEON:
-		return ja_pigeon_node_get_left(type, node, n);
+		return ja_pigeon_node_get_direction(type, node, n, result_key, dir);
 	default:
 		assert(0);
 		return (void *) -1UL;
@@ -606,9 +672,28 @@ struct cds_ja_inode_flag *ja_node_get_left(struct cds_ja_inode_flag *node_flag,
 }
 
 static
-struct cds_ja_inode_flag *ja_node_get_rightmost(struct cds_ja_inode_flag *node_flag)
+struct cds_ja_inode_flag *ja_node_get_leftright(struct cds_ja_inode_flag *node_flag,
+		unsigned int n, uint8_t *result_key,
+		enum ja_direction dir)
 {
-	return ja_node_get_left(node_flag, JA_ENTRY_PER_NODE);
+	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, result_key, JA_RIGHT);
+	case JA_RIGHTMOST:
+		return ja_node_get_direction(node_flag,
+				JA_ENTRY_PER_NODE, result_key, JA_LEFT);
+	default:
+		assert(0);
+	}
 }
 
 static
@@ -1720,15 +1805,31 @@ struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key)
 	return (struct cds_ja_node *) node_flag;
 }
 
-struct cds_ja_node *cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
+static
+struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key,
+		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;
 
-	if (caa_unlikely(key > ja->key_max || !key))
+	switch (mode) {
+	case JA_LOOKUP_BE:
+		if (caa_unlikely(key > ja->key_max || key == 0))
+			return NULL;
+		break;
+	case JA_LOOKUP_AE:
+		if (caa_unlikely(key >= ja->key_max))
+			return NULL;
+		break;
+	default:
 		return NULL;
+	}
 
 	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;
@@ -1744,37 +1845,51 @@ struct cds_ja_node *cds_ja_lookup_lower_equal(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 iter key lookup %u finds node_flag %p\n",
+		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 (result_key)
+			*result_key = key;
 		return (struct cds_ja_node *) node_flag;
 	}
 
 	/*
-	 * Find highest value left of current node.
+	 * Find highest value left/right 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).
+	 * Start at current level. If we cannot find any key left/right
+	 * of ours, go one level up, seek highest value left/right of
+	 * current (recursively), and when we find one, get the
+	 * rightmost/leftmost child of its rightmost/leftmost child
+	 * (recursively).
 	 */
+	switch (mode) {
+	case JA_LOOKUP_BE:
+		dir = JA_LEFT;
+		break;
+	case JA_LOOKUP_AE:
+		dir = JA_RIGHT;
+		break;
+	default:
+		assert(0);
+	}
 	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. */
+		node_flag = ja_node_get_leftright(cur_node_depth[level - 1],
+				iter_key, &cur_key[level - 1], dir);
+		/* If found left/right sibling, find rightmost/leftmost child. */
 		if (ja_node_ptr(node_flag))
 			break;
 	}
 
 	if (!level) {
-		/* Reached the root and could not find a left sibling. */
+		/* Reached the root and could not find a left/right sibling. */
 		return NULL;
 	}
 
@@ -1782,24 +1897,55 @@ struct cds_ja_node *cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
 
 	/*
 	 * From this point, we are guaranteed to be able to find a
-	 * "lower than" match. ja_attach_node() and ja_detach_node()
-	 * both guarantee that it is not possible for a lookup to reach
-	 * a dead-end.
+	 * "below than"/"above than" match. ja_attach_node() and
+	 * ja_detach_node() both guarantee that it is not possible for a
+	 * lookup to reach a dead-end.
 	 */
 
-	/* Find rightmost child of rightmost child (recursively). */
+	/*
+	 * Find rightmost/leftmost child of rightmost/leftmost child
+	 * (recursively).
+	 */
+	switch (mode) {
+	case JA_LOOKUP_BE:
+		dir = JA_RIGHTMOST;
+		break;
+	case JA_LOOKUP_AE:
+		dir = JA_LEFTMOST;
+		break;
+	default:
+		assert(0);
+	}
 	for (; level < tree_depth; level++) {
-		node_flag = ja_node_get_rightmost(node_flag);
-		/* If found left sibling, find rightmost child. */
+		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, uint64_t *result_key)
+{
+	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, uint64_t *result_key)
+{
+	return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_AE);
+}
+
 /*
  * We reached an unpopulated node. Create it and the children we need,
  * and then attach the entire branch to the current node. This may
@@ -2015,7 +2161,7 @@ end:
 
 static
 int _cds_ja_add(struct cds_ja *ja, uint64_t key,
-		struct cds_ja_node *new_node,
+		struct cds_ja_node *node,
 		struct cds_ja_node **unique_node_ret)
 {
 	unsigned int tree_depth, i;
@@ -2036,7 +2182,7 @@ int _cds_ja_add(struct cds_ja *ja, uint64_t key,
 
 retry:
 	dbg_printf("cds_ja_add attempt: key %" PRIu64 ", node %p\n",
-		key, new_node);
+		key, node);
 	parent2_node_flag = NULL;
 	parent_node_flag =
 		(struct cds_ja_inode_flag *) &ja->root;	/* Use root ptr address as key for mutex */
@@ -2079,7 +2225,7 @@ retry:
 				parent_attach_node_flag,
 				node_flag_ptr,
 				node_flag,
-				key, i, new_node);
+				key, i, node);
 	} else {
 		if (unique_node_ret) {
 			*unique_node_ret = (struct cds_ja_node *) ja_node_ptr(node_flag);
@@ -2097,7 +2243,7 @@ retry:
 			parent_attach_node_flag,
 			attach_node_flag_ptr,
 			attach_node_flag,
-			new_node);
+			node);
 	}
 	if (ret == -EAGAIN || ret == -EEXIST)
 		goto retry;
@@ -2106,22 +2252,22 @@ retry:
 }
 
 int cds_ja_add(struct cds_ja *ja, uint64_t key,
-		struct cds_ja_node *new_node)
+		struct cds_ja_node *node)
 {
-	return _cds_ja_add(ja, key, new_node, NULL);
+	return _cds_ja_add(ja, key, node, NULL);
 }
 
 struct cds_ja_node *cds_ja_add_unique(struct cds_ja *ja, uint64_t key,
-		struct cds_ja_node *new_node)
+		struct cds_ja_node *node)
 {
 	int ret;
 	struct cds_ja_node *ret_node;
 
-	ret = _cds_ja_add(ja, key, new_node, &ret_node);
+	ret = _cds_ja_add(ja, key, node, &ret_node);
 	if (ret == -EEXIST)
 		return ret_node;
 	else
-		return new_node;
+		return node;
 }
 
 /*
@@ -2630,11 +2776,12 @@ int ja_final_checks(struct cds_ja *ja)
 }
 
 /*
- * There should be no more concurrent add to the judy array while it is
- * being destroyed (ensured by the caller).
+ * There should be no more concurrent add, delete, nor look-up performed
+ * on the Judy array while it is being destroyed (ensured by the
+ * caller).
  */
 int cds_ja_destroy(struct cds_ja *ja,
-		void (*rcu_free_node)(struct cds_ja_node *node))
+		void (*free_node_cb)(struct cds_ja_node *node))
 {
 	const struct rcu_flavor_struct *flavor;
 	int ret;
@@ -2642,7 +2789,7 @@ int cds_ja_destroy(struct cds_ja *ja,
 	flavor = cds_lfht_rcu_flavor(ja->ht);
 	rcuja_shadow_prune(ja->ht,
 		RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK,
-		rcu_free_node);
+		free_node_cb);
 	flavor->thread_offline();
 	ret = rcuja_delete_ht(ja->ht);
 	if (ret)