X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=7a61817135c8c558e26c6da1c9350534e279f058;hb=78ed159afe62f81fb2db3ffa42b3b33d4871f372;hp=525267246e9b2b0abfd2254638942ae7db5ed36e;hpb=b023ba9fb95fbcfbedd3e499556959ad6706ce79;p=userspace-rcu.git

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index 5252672..7a61817 100644
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -3,6 +3,7 @@
  *
  * Userspace RCU library - RCU Judy Array
  *
+ * Copyright (C) 2000 - 2002 Hewlett-Packard Company
  * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  *
  * This library is free software; you can redistribute it and/or
@@ -364,13 +365,13 @@ 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;
 	uint8_t *values;
 	struct cds_ja_inode_flag **pointers;
-	struct cds_ja_inode_flag *ptr;
+	struct cds_ja_inode_flag *ptr = NULL;
 	unsigned int i;
 	int match_idx = -1, match_v;
 
@@ -389,10 +390,14 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type
 	assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 
 	values = &node->u.data[1];
+	pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
 	for (i = 0; i < nr_child; i++) {
 		unsigned int v;
 
 		v = CMM_LOAD_SHARED(values[i]);
+		ptr = CMM_LOAD_SHARED(pointers[i]);
+		if (!ptr)
+			continue;
 		if (dir == JA_LEFT) {
 			if ((int) v < n && (int) v > match_v) {
 				match_v = v;
@@ -411,7 +416,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);
 
-	pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
+	*result_key = (uint8_t) match_v;
 	ptr = rcu_dereference(pointers[match_idx]);
 	return ptr;
 }
@@ -491,7 +496,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 +541,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 +568,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 +586,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 = (uint8_t) i;
 				return child_node_flag;
 			}
 		}
@@ -590,6 +598,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 = (uint8_t) i;
 				return child_node_flag;
 			}
 		}
@@ -641,7 +650,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 +664,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 +677,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 +1811,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 +1833,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 +1849,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 +1857,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 +1886,11 @@ 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);
+		dbg_printf("cds_ja_lookup_inequality find sibling from %u at %u finds node_flag %p\n",
+				(unsigned int) iter_key, (unsigned int) cur_key[level - 1],
+				node_flag);
+		/* If found left/right sibling, find rightmost/leftmost child. */
 		if (ja_node_ptr(node_flag))
 			break;
 	}
@@ -1905,24 +1924,38 @@ 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);
+		dbg_printf("cds_ja_lookup_inequality find minmax at %u finds node_flag %p\n",
+				(unsigned int) cur_key[level - 1],
+				node_flag);
 		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);
+	dbg_printf("cds_ja_lookup_below_equal key %" PRIu64 "\n", 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)
+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);
+	dbg_printf("cds_ja_lookup_above_equal key %" PRIu64 "\n", key);
+	return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_AE);
 }
 
 /*
@@ -2625,91 +2658,6 @@ ja_error:
 	return NULL;
 }
 
-/*
- * Called from RCU read-side CS.
- */
-__attribute__((visibility("protected")))
-void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node,
-		struct cds_ja_inode_flag *node_flag,
-		void (*rcu_free_node)(struct cds_ja_node *node))
-{
-	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:
-	{
-		uint8_t nr_child =
-			ja_linear_node_get_nr_child(type, node);
-		unsigned int i;
-
-		for (i = 0; i < nr_child; i++) {
-			struct cds_ja_inode_flag *iter;
-			struct cds_ja_node *node_iter, *n;
-			uint8_t v;
-
-			ja_linear_node_get_ith_pos(type, node, i, &v, &iter);
-			node_iter = (struct cds_ja_node *) iter;
-			cds_ja_for_each_duplicate_safe(node_iter, n) {
-				rcu_free_node(node_iter);
-			}
-		}
-		break;
-	}
-	case RCU_JA_POOL:
-	{
-		unsigned int pool_nr;
-
-		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;
-				struct cds_ja_node *node_iter, *n;
-				uint8_t v;
-
-				ja_linear_node_get_ith_pos(type, pool, j, &v, &iter);
-				node_iter = (struct cds_ja_node *) iter;
-				cds_ja_for_each_duplicate_safe(node_iter, n) {
-					rcu_free_node(node_iter);
-				}
-			}
-		}
-		break;
-	}
-	case RCU_JA_NULL:
-		break;
-	case RCU_JA_PIGEON:
-	{
-		unsigned int i;
-
-		for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
-			struct cds_ja_inode_flag *iter;
-			struct cds_ja_node *node_iter, *n;
-
-			iter = ja_pigeon_node_get_ith_pos(type, node, i);
-			node_iter = (struct cds_ja_node *) iter;
-			cds_ja_for_each_duplicate_safe(node_iter, n) {
-				rcu_free_node(node_iter);
-			}
-		}
-		break;
-	}
-	default:
-		assert(0);
-	}
-}
-
 static
 void print_debug_fallback_distribution(struct cds_ja *ja)
 {
@@ -2759,16 +2707,14 @@ int ja_final_checks(struct cds_ja *ja)
  * on the Judy array while it is being destroyed (ensured by the
  * caller).
  */
-int cds_ja_destroy(struct cds_ja *ja,
-		void (*free_node_cb)(struct cds_ja_node *node))
+int cds_ja_destroy(struct cds_ja *ja)
 {
 	const struct rcu_flavor_struct *flavor;
 	int ret;
 
 	flavor = cds_lfht_rcu_flavor(ja->ht);
 	rcuja_shadow_prune(ja->ht,
-		RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK,
-		free_node_cb);
+		RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK);
 	flavor->thread_offline();
 	ret = rcuja_delete_ht(ja->ht);
 	if (ret)