*/
#define _LGPL_SOURCE
+#define _GNU_SOURCE
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
+#include <sched.h>
#include "config.h"
#include <urcu.h>
*/
return -ENOENT;
}
- assert(!is_bucket(old_next));
- assert(new_node != clear_flag(old_next));
- new_node->next = clear_flag(old_next);
+ assert(old_next == clear_flag(old_next));
+ assert(new_node != old_next);
+ new_node->next = old_next;
/*
* Here is the whole trick for lock-free replace: we add
* the replacement node _after_ the node we want to
*/
static
void _cds_lfht_add(struct cds_lfht *ht,
+ unsigned long hash,
cds_lfht_match_fct match,
const void *key,
unsigned long size,
assert(!is_bucket(node));
assert(!is_removed(node));
- bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
+ bucket = lookup_bucket(ht, size, hash);
for (;;) {
uint32_t chain_len = 0;
dbg_printf("init populate: order %lu index %lu hash %lu\n",
i, j, j);
new_node->reverse_hash = bit_reverse_ulong(j);
- _cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1);
+ _cds_lfht_add(ht, j, NULL, NULL, size, new_node, NULL, 1);
}
ht->flavor->read_unlock();
}
{
unsigned long size;
- node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
+ node->reverse_hash = bit_reverse_ulong(hash);
size = rcu_dereference(ht->size);
- _cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
+ _cds_lfht_add(ht, hash, NULL, NULL, size, node, NULL, 0);
ht_count_add(ht, size, hash);
}
unsigned long size;
struct cds_lfht_iter iter;
- node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
+ node->reverse_hash = bit_reverse_ulong(hash);
size = rcu_dereference(ht->size);
- _cds_lfht_add(ht, match, key, size, node, &iter, 0);
+ _cds_lfht_add(ht, hash, match, key, size, node, &iter, 0);
if (iter.node == node)
ht_count_add(ht, size, hash);
return iter.node;
unsigned long size;
struct cds_lfht_iter iter;
- node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
+ node->reverse_hash = bit_reverse_ulong(hash);
size = rcu_dereference(ht->size);
for (;;) {
- _cds_lfht_add(ht, match, key, size, node, &iter, 0);
+ _cds_lfht_add(ht, hash, match, key, size, node, &iter, 0);
if (iter.node == node) {
ht_count_add(ht, size, hash);
return NULL;
}
}
-int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
+int cds_lfht_replace(struct cds_lfht *ht,
+ struct cds_lfht_iter *old_iter,
+ unsigned long hash,
+ cds_lfht_match_fct match,
+ const void *key,
struct cds_lfht_node *new_node)
{
unsigned long size;
+ new_node->reverse_hash = bit_reverse_ulong(hash);
+ if (!old_iter->node)
+ return -ENOENT;
+ if (caa_unlikely(old_iter->node->reverse_hash != new_node->reverse_hash))
+ return -EINVAL;
+ if (caa_unlikely(!match(old_iter->node, key)))
+ return -EINVAL;
size = rcu_dereference(ht->size);
return _cds_lfht_replace(ht, size, old_iter->node, old_iter->next,
new_node);
}
-int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
+int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node)
{
unsigned long size, hash;
int ret;
size = rcu_dereference(ht->size);
- ret = _cds_lfht_del(ht, size, iter->node);
+ ret = _cds_lfht_del(ht, size, node);
if (!ret) {
- hash = bit_reverse_ulong(iter->node->reverse_hash);
+ hash = bit_reverse_ulong(node->reverse_hash);
ht_count_del(ht, size, hash);
}
return ret;
}
+int cds_lfht_is_node_deleted(struct cds_lfht_node *node)
+{
+ return is_removed(rcu_dereference(node->next));
+}
+
static
int cds_lfht_delete_bucket(struct cds_lfht *ht)
{