projects
/
urcu.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
rculfhash: add c++ ifdef
[urcu.git]
/
rculfhash.c
diff --git
a/rculfhash.c
b/rculfhash.c
index 5baa2d415b34483486ece296cb9c511ae2cf0714..556ec36ddab261625d3c3b412496718c790d0c0b 100644
(file)
--- a/
rculfhash.c
+++ b/
rculfhash.c
@@
-234,13
+234,17
@@
void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
}
static
}
static
-
int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node
,
- int unique)
+
struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t
,
+
struct rcu_ht_node *node,
int unique)
{
struct rcu_ht_node *iter_prev, *dummy, *iter, *next;
{
struct rcu_ht_node *iter_prev, *dummy, *iter, *next;
+ unsigned long hash;
- if (!t->size)
- return 0;
+ if (!t->size) {
+ assert(node->dummy);
+ return node; /* Initial first add (head) */
+ }
+ hash = bit_reverse_ulong(node->reverse_hash);
for (;;) {
uint32_t chain_len = 0;
for (;;) {
uint32_t chain_len = 0;
@@
-248,7
+252,7
@@
int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
* iter_prev points to the non-removed node prior to the
* insert location.
*/
* iter_prev points to the non-removed node prior to the
* insert location.
*/
- iter_prev = rcu_dereference(t->tbl[
node->
hash & (t->size - 1)]);
+ iter_prev = rcu_dereference(t->tbl[hash & (t->size - 1)]);
/* We can always skip the dummy node initially */
iter = rcu_dereference(iter_prev->next);
assert(iter_prev->reverse_hash <= node->reverse_hash);
/* We can always skip the dummy node initially */
iter = rcu_dereference(iter_prev->next);
assert(iter_prev->reverse_hash <= node->reverse_hash);
@@
-259,7
+263,13
@@
int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
goto insert;
next = rcu_dereference(clear_flag(iter)->next);
if (is_removed(next))
goto insert;
next = rcu_dereference(clear_flag(iter)->next);
if (is_removed(next))
- goto gc;
+ goto gc_node;
+ if (unique
+ && !clear_flag(iter)->dummy
+ && !ht->compare_fct(node->key, node->key_len,
+ clear_flag(iter)->key,
+ clear_flag(iter)->key_len))
+ return clear_flag(iter);
/* Only account for identical reverse hash once */
if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash)
check_resize(ht, t, ++chain_len);
/* Only account for identical reverse hash once */
if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash)
check_resize(ht, t, ++chain_len);
@@
-276,17
+286,16
@@
int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
continue; /* retry */
else
goto gc_end;
continue; /* retry */
else
goto gc_end;
- gc:
- /* Garbage collect logically removed nodes in the bucket */
- dummy = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
- _ht_gc_bucket(dummy, node);
+ gc_node:
+ assert(!is_removed(iter));
+ (void) uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next));
/* retry */
}
gc_end:
/* Garbage collect logically removed nodes in the bucket */
/* retry */
}
gc_end:
/* Garbage collect logically removed nodes in the bucket */
- dummy = rcu_dereference(t->tbl[
node->
hash & (t->size - 1)]);
+ dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
_ht_gc_bucket(dummy, node);
_ht_gc_bucket(dummy, node);
- return
0
;
+ return
node
;
}
static
}
static
@@
-294,6
+303,7
@@
int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
{
struct rcu_ht_node *dummy, *next, *old;
int flagged = 0;
{
struct rcu_ht_node *dummy, *next, *old;
int flagged = 0;
+ unsigned long hash;
/* logically delete the node */
old = rcu_dereference(node->next);
/* logically delete the node */
old = rcu_dereference(node->next);
@@
-314,7
+324,8
@@
int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
* the node, and remove it (along with any other logically removed node)
* if found.
*/
* the node, and remove it (along with any other logically removed node)
* if found.
*/
- dummy = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
+ hash = bit_reverse_ulong(node->reverse_hash);
+ dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
_ht_gc_bucket(dummy, node);
end:
/*
_ht_gc_bucket(dummy, node);
end:
/*
@@
-341,7
+352,6
@@
void init_table(struct rcu_ht *ht, struct rcu_table *t,
t->size = i;
t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
t->tbl[i]->dummy = 1;
t->size = i;
t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
t->tbl[i]->dummy = 1;
- t->tbl[i]->hash = i;
t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
(void) _ht_add(ht, t, t->tbl[i], 0);
}
t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
(void) _ht_add(ht, t, t->tbl[i], 0);
}
@@
-392,9
+402,9
@@
struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
node = NULL;
break;
}
node = NULL;
break;
}
- if (
!ht->compare_fct(node->key, node->key_len, key, key_len)) {
- if (likely(!is_removed(rcu_dereference(node->next)))
- && likely(!node->dummy))
+ if (
likely(!is_removed(rcu_dereference(node->next)))
+ && !node->dummy
+ && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
break;
}
node = clear_flag(rcu_dereference(node->next));
break;
}
node = clear_flag(rcu_dereference(node->next));
@@
-406,20
+416,22
@@
struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
{
struct rcu_table *t;
void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
{
struct rcu_table *t;
+ unsigned long hash;
-
node->
hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
- node->reverse_hash = bit_reverse_ulong((unsigned long)
node->
hash);
+ hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
+ node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
t = rcu_dereference(ht->t);
(void) _ht_add(ht, t, node, 0);
}
t = rcu_dereference(ht->t);
(void) _ht_add(ht, t, node, 0);
}
-
int
ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
+
struct rcu_ht_node *
ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
{
struct rcu_table *t;
{
struct rcu_table *t;
+ unsigned long hash;
-
node->
hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
- node->reverse_hash = bit_reverse_ulong((unsigned long)
node->
hash);
+ hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
+ node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
t = rcu_dereference(ht->t);
return _ht_add(ht, t, node, 1);
t = rcu_dereference(ht->t);
return _ht_add(ht, t, node, 1);
This page took
0.024316 seconds
and
4
git commands to generate.