Merge branch 'urcu/ht-shrink'

[urcu.git] / rculfhash.c

diff --git a/rculfhash.c b/rculfhash.c
index 5220cd5fd804321cf2b9b725c87b9e54d58296f2..94366050bfb00957988730edcae25923e3f39379 100644 (file)
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -779,9 +779,9 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
                         */
                        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
@@ -820,6 +820,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
  */
 static
 void _cds_lfht_add(struct cds_lfht *ht,
+               unsigned long hash,
                cds_lfht_match_fct match,
                const void *key,
                unsigned long size,
@@ -833,7 +834,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
        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;
 
@@ -929,8 +930,7 @@ end:
 
 static
 int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
-               struct cds_lfht_node *node,
-               int bucket_removal)
+               struct cds_lfht_node *node)
 {
        struct cds_lfht_node *bucket, *next;
 
@@ -951,10 +951,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
        next = rcu_dereference(node->next);
        if (caa_unlikely(is_removed(next)))
                return -ENOENT;
-       if (bucket_removal)
-               assert(is_bucket(next));
-       else
-               assert(!is_bucket(next));
+       assert(!is_bucket(next));
        /*
         * We set the REMOVED_FLAG unconditionally. Note that there may
         * be more than one concurrent thread setting this flag.
@@ -1071,7 +1068,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
                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();
 }
@@ -1475,9 +1472,9 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 {
        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);
 }
 
@@ -1490,9 +1487,9 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
        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;
@@ -1507,10 +1504,10 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
        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;
@@ -1521,30 +1518,46 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
        }
 }
 
-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, 0);
+       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)
 {
@@ -1604,11 +1617,10 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
 void cds_lfht_count_nodes(struct cds_lfht *ht,
                long *approx_before,
                unsigned long *count,
-               unsigned long *removed,
                long *approx_after)
 {
        struct cds_lfht_node *node, *next;
-       unsigned long nr_bucket = 0;
+       unsigned long nr_bucket = 0, nr_removed = 0;
 
        *approx_before = 0;
        if (ht->split_count) {
@@ -1621,7 +1633,6 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
        }
 
        *count = 0;
-       *removed = 0;
 
        /* Count non-bucket nodes in the table */
        node = bucket_at(ht, 0);
@@ -1629,7 +1640,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
                next = rcu_dereference(node->next);
                if (is_removed(next)) {
                        if (!is_bucket(next))
-                               (*removed)++;
+                               (nr_removed)++;
                        else
                                (nr_bucket)++;
                } else if (!is_bucket(next))
@@ -1638,6 +1649,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
                        (nr_bucket)++;
                node = clear_flag(next);
        } while (!is_end(node));
+       dbg_printf("number of logically removed nodes: %lu\n", nr_removed);
        dbg_printf("number of bucket nodes: %lu\n", nr_bucket);
        *approx_after = 0;
        if (ht->split_count) {