projects
/
urcu.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
rculfhash: Add parenthesis around macro arg use in iterator macro
[urcu.git]
/
rculfhash.c
diff --git
a/rculfhash.c
b/rculfhash.c
index 600feecfa8f4f8230eede1683cf79cff14a0333f..41b774adfdd3257f53e7acb548f147d43fe0dc10 100644
(file)
--- a/
rculfhash.c
+++ b/
rculfhash.c
@@
-45,7
+45,7
@@
* - The resize operation executes concurrently with add/remove/lookup.
* - Hash table nodes are contained within a split-ordered list. This
* list is ordered by incrementing reversed-bits-hash value.
* - The resize operation executes concurrently with add/remove/lookup.
* - Hash table nodes are contained within a split-ordered list. This
* list is ordered by incrementing reversed-bits-hash value.
- * - An index of
dummy nodes is kept. These dummy
nodes are the hash
+ * - An index of
bucket nodes is kept. These bucket
nodes are the hash
* table "buckets", and they are also chained together in the
* split-ordered list, which allows recursive expansion.
* - The resize operation for small tables only allows expanding the hash table.
* table "buckets", and they are also chained together in the
* split-ordered list, which allows recursive expansion.
* - The resize operation for small tables only allows expanding the hash table.
@@
-74,7
+74,7
@@
* successfully set the "removed" flag (with a cmpxchg) into a node's
* next pointer is considered to have succeeded its removal (and thus
* owns the node to reclaim). Because we garbage-collect starting from
* successfully set the "removed" flag (with a cmpxchg) into a node's
* next pointer is considered to have succeeded its removal (and thus
* owns the node to reclaim). Because we garbage-collect starting from
- * an invariant node (the start-of-bucket
dummy
node) up to the
+ * an invariant node (the start-of-bucket
bucket
node) up to the
* "removed" node (or find a reverse-hash that is higher), we are sure
* that a successful traversal of the chain leads to a chain that is
* present in the linked-list (the start node is never removed) and
* "removed" node (or find a reverse-hash that is higher), we are sure
* that a successful traversal of the chain leads to a chain that is
* present in the linked-list (the start node is never removed) and
@@
-88,19
+88,19
@@
* for it do to so.
* - A RCU "order table" indexed by log2(hash index) is copied and
* expanded by the resize operation. This order table allows finding
* for it do to so.
* - A RCU "order table" indexed by log2(hash index) is copied and
* expanded by the resize operation. This order table allows finding
- * the "
dummy
node" tables.
- * - There is one
dummy
node table per hash index order. The size of
- * each
dummy
node table is half the number of hashes contained in
+ * the "
bucket
node" tables.
+ * - There is one
bucket
node table per hash index order. The size of
+ * each
bucket
node table is half the number of hashes contained in
* this order (except for order 0).
* this order (except for order 0).
- * - synchronzie_rcu is used to garbage-collect the old
dummy
node table.
- * - The per-order
dummy
node tables contain a compact version of the
+ * - synchronzie_rcu is used to garbage-collect the old
bucket
node table.
+ * - The per-order
bucket
node tables contain a compact version of the
* hash table nodes. These tables are invariant after they are
* populated into the hash table.
*
* hash table nodes. These tables are invariant after they are
* populated into the hash table.
*
- *
Dummy
node tables:
+ *
Bucket
node tables:
*
*
- * hash table hash table the last all
dummy
node tables
- * order size
dummy node
0 1 2 3 4 5 6(index)
+ * hash table hash table the last all
bucket
node tables
+ * order size
bucket node
0 1 2 3 4 5 6(index)
* table size
* 0 1 1 1
* 1 2 1 1 1
* table size
* 0 1 1 1
* 1 2 1 1 1
@@
-110,12
+110,12
@@
* 5 32 16 1 1 2 4 8 16
* 6 64 32 1 1 2 4 8 16 32
*
* 5 32 16 1 1 2 4 8 16
* 6 64 32 1 1 2 4 8 16 32
*
- * When growing/shrinking, we only focus on the last
dummy
node table
+ * When growing/shrinking, we only focus on the last
bucket
node table
* which size is (!order ? 1 : (1 << (order -1))).
*
* Example for growing/shrinking:
* which size is (!order ? 1 : (1 << (order -1))).
*
* Example for growing/shrinking:
- * grow hash table from order 5 to 6: init the index=6
dummy
node table
- * shrink hash table from order 6 to 5: fini the index=6
dummy
node table
+ * grow hash table from order 5 to 6: init the index=6
bucket
node table
+ * shrink hash table from order 6 to 5: fini the index=6
bucket
node table
*
* A bit of ascii art explanation:
*
*
* A bit of ascii art explanation:
*
@@
-195,7
+195,7
@@
#endif
/*
#endif
/*
- * Minimum number of
dummy
nodes to touch per thread to parallelize grow/shrink.
+ * Minimum number of
bucket
nodes to touch per thread to parallelize grow/shrink.
*/
#define MIN_PARTITION_PER_THREAD_ORDER 12
#define MIN_PARTITION_PER_THREAD (1UL << MIN_PARTITION_PER_THREAD_ORDER)
*/
#define MIN_PARTITION_PER_THREAD_ORDER 12
#define MIN_PARTITION_PER_THREAD (1UL << MIN_PARTITION_PER_THREAD_ORDER)
@@
-212,11
+212,11
@@
* The removed flag needs to be updated atomically with the pointer.
* It indicates that no node must attach to the node scheduled for
* removal, and that node garbage collection must be performed.
* The removed flag needs to be updated atomically with the pointer.
* It indicates that no node must attach to the node scheduled for
* removal, and that node garbage collection must be performed.
- * The
dummy
flag does not require to be updated atomically with the
+ * The
bucket
flag does not require to be updated atomically with the
* pointer, but it is added as a pointer low bit flag to save space.
*/
#define REMOVED_FLAG (1UL << 0)
* pointer, but it is added as a pointer low bit flag to save space.
*/
#define REMOVED_FLAG (1UL << 0)
-#define
DUMMY_FLAG
(1UL << 1)
+#define
BUCKET_FLAG
(1UL << 1)
#define FLAGS_MASK ((1UL << 2) - 1)
/* Value of the end pointer. Should not interact with flags. */
#define FLAGS_MASK ((1UL << 2) - 1)
/* Value of the end pointer. Should not interact with flags. */
@@
-237,15
+237,15
@@
struct ht_items_count {
} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
/*
} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
/*
- * rcu_level: Contains the per order-index-level
dummy
node table. The
- * size of each
dummy
node table is half the number of hashes contained
+ * rcu_level: Contains the per order-index-level
bucket
node table. The
+ * size of each
bucket
node table is half the number of hashes contained
* in this order (except for order 0). The minimum allocation size
* in this order (except for order 0). The minimum allocation size
- * parameter allows combining the
dummy
node arrays of the lowermost
+ * parameter allows combining the
bucket
node arrays of the lowermost
* levels to improve cache locality for small index orders.
*/
struct rcu_level {
/* Note: manually update allocation length when adding a field */
* levels to improve cache locality for small index orders.
*/
struct rcu_level {
/* Note: manually update allocation length when adding a field */
- struct
_
cds_lfht_node nodes[0];
+ struct cds_lfht_node nodes[0];
};
/*
};
/*
@@
-267,11
+267,8
@@
struct rcu_table {
*/
struct cds_lfht {
struct rcu_table t;
*/
struct cds_lfht {
struct rcu_table t;
- cds_lfht_hash_fct hash_fct;
- cds_lfht_compare_fct compare_fct;
unsigned long min_alloc_order;
unsigned long min_alloc_size;
unsigned long min_alloc_order;
unsigned long min_alloc_size;
- unsigned long hash_seed;
int flags;
/*
* We need to put the work threads offline (QSBR) when taking this
int flags;
/*
* We need to put the work threads offline (QSBR) when taking this
@@
-320,10
+317,12
@@
struct partition_resize_work {
static
void _cds_lfht_add(struct cds_lfht *ht,
static
void _cds_lfht_add(struct cds_lfht *ht,
+ cds_lfht_match_fct match,
+ void *key,
unsigned long size,
struct cds_lfht_node *node,
struct cds_lfht_iter *unique_ret,
unsigned long size,
struct cds_lfht_node *node,
struct cds_lfht_iter *unique_ret,
- int
dummy
);
+ int
bucket
);
/*
* Algorithm to reverse bits in a word by lookup table, extended to
/*
* Algorithm to reverse bits in a word by lookup table, extended to
@@
-718,15
+717,15
@@
struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
}
static
}
static
-int is_
dummy
(struct cds_lfht_node *node)
+int is_
bucket
(struct cds_lfht_node *node)
{
{
- return ((unsigned long) node) &
DUMMY
_FLAG;
+ return ((unsigned long) node) &
BUCKET
_FLAG;
}
static
}
static
-struct cds_lfht_node *flag_
dummy
(struct cds_lfht_node *node)
+struct cds_lfht_node *flag_
bucket
(struct cds_lfht_node *node)
{
{
- return (struct cds_lfht_node *) (((unsigned long) node) |
DUMMY
_FLAG);
+ return (struct cds_lfht_node *) (((unsigned long) node) |
BUCKET
_FLAG);
}
static
}
static
@@
-757,7
+756,7
@@
unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
}
static
}
static
-struct
_
cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
+struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
unsigned long hash)
{
unsigned long index, order;
unsigned long hash)
{
unsigned long index, order;
@@
-785,44
+784,44
@@
struct _cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
* Remove all logically deleted nodes from a bucket up to a certain node key.
*/
static
* Remove all logically deleted nodes from a bucket up to a certain node key.
*/
static
-void _cds_lfht_gc_bucket(struct cds_lfht_node *
dummy
, struct cds_lfht_node *node)
+void _cds_lfht_gc_bucket(struct cds_lfht_node *
bucket
, struct cds_lfht_node *node)
{
struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
{
struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
- assert(!is_
dummy(dummy
));
- assert(!is_removed(
dummy
));
- assert(!is_
dummy
(node));
+ assert(!is_
bucket(bucket
));
+ assert(!is_removed(
bucket
));
+ assert(!is_
bucket
(node));
assert(!is_removed(node));
for (;;) {
assert(!is_removed(node));
for (;;) {
- iter_prev =
dummy
;
- /* We can always skip the
dummy
node initially */
- iter = rcu_dereference(iter_prev->
p.
next);
+ iter_prev =
bucket
;
+ /* We can always skip the
bucket
node initially */
+ iter = rcu_dereference(iter_prev->next);
assert(!is_removed(iter));
assert(!is_removed(iter));
- assert(iter_prev->
p.reverse_hash <= node->p.
reverse_hash);
+ assert(iter_prev->
reverse_hash <= node->
reverse_hash);
/*
/*
- * We should never be called with
dummy
(start of chain)
+ * We should never be called with
bucket
(start of chain)
* and logically removed node (end of path compression
* marker) being the actual same node. This would be a
* bug in the algorithm implementation.
*/
* and logically removed node (end of path compression
* marker) being the actual same node. This would be a
* bug in the algorithm implementation.
*/
- assert(
dummy
!= node);
+ assert(
bucket
!= node);
for (;;) {
if (caa_unlikely(is_end(iter)))
return;
for (;;) {
if (caa_unlikely(is_end(iter)))
return;
- if (caa_likely(clear_flag(iter)->
p.reverse_hash > node->p.
reverse_hash))
+ if (caa_likely(clear_flag(iter)->
reverse_hash > node->
reverse_hash))
return;
return;
- next = rcu_dereference(clear_flag(iter)->
p.
next);
+ next = rcu_dereference(clear_flag(iter)->next);
if (caa_likely(is_removed(next)))
break;
iter_prev = clear_flag(iter);
iter = next;
}
assert(!is_removed(iter));
if (caa_likely(is_removed(next)))
break;
iter_prev = clear_flag(iter);
iter = next;
}
assert(!is_removed(iter));
- if (is_
dummy
(iter))
- new_next = flag_
dummy
(clear_flag(next));
+ if (is_
bucket
(iter))
+ new_next = flag_
bucket
(clear_flag(next));
else
new_next = clear_flag(next);
else
new_next = clear_flag(next);
- (void) uatomic_cmpxchg(&iter_prev->
p.
next, iter, new_next);
+ (void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
}
return;
}
}
return;
}
@@
-833,16
+832,15
@@
int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
struct cds_lfht_node *old_next,
struct cds_lfht_node *new_node)
{
struct cds_lfht_node *old_next,
struct cds_lfht_node *new_node)
{
- struct cds_lfht_node *dummy, *ret_next;
- struct _cds_lfht_node *lookup;
+ struct cds_lfht_node *bucket, *ret_next;
if (!old_node) /* Return -ENOENT if asked to replace NULL node */
return -ENOENT;
assert(!is_removed(old_node));
if (!old_node) /* Return -ENOENT if asked to replace NULL node */
return -ENOENT;
assert(!is_removed(old_node));
- assert(!is_
dummy
(old_node));
+ assert(!is_
bucket
(old_node));
assert(!is_removed(new_node));
assert(!is_removed(new_node));
- assert(!is_
dummy
(new_node));
+ assert(!is_
bucket
(new_node));
assert(new_node != old_node);
for (;;) {
/* Insert after node to be replaced */
assert(new_node != old_node);
for (;;) {
/* Insert after node to be replaced */
@@
-853,9
+851,9
@@
int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
*/
return -ENOENT;
}
*/
return -ENOENT;
}
- assert(!is_
dummy
(old_next));
+ assert(!is_
bucket
(old_next));
assert(new_node != clear_flag(old_next));
assert(new_node != clear_flag(old_next));
- new_node->
p.
next = clear_flag(old_next);
+ new_node->next = clear_flag(old_next);
/*
* Here is the whole trick for lock-free replace: we add
* the replacement node _after_ the node we want to
/*
* Here is the whole trick for lock-free replace: we add
* the replacement node _after_ the node we want to
@@
-866,7
+864,7
@@
int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
* to the removal flag and see the new node, or use
* the old node, but will not see the new one.
*/
* to the removal flag and see the new node, or use
* the old node, but will not see the new one.
*/
- ret_next = uatomic_cmpxchg(&old_node->
p.
next,
+ ret_next = uatomic_cmpxchg(&old_node->next,
old_next, flag_removed(new_node));
if (ret_next == old_next)
break; /* We performed the replacement. */
old_next, flag_removed(new_node));
if (ret_next == old_next)
break; /* We performed the replacement. */
@@
-878,11
+876,10
@@
int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
* lookup for the node, and remove it (along with any other
* logically removed node) if found.
*/
* lookup for the node, and remove it (along with any other
* logically removed node) if found.
*/
- lookup = lookup_bucket(ht, size, bit_reverse_ulong(old_node->p.reverse_hash));
- dummy = (struct cds_lfht_node *) lookup;
- _cds_lfht_gc_bucket(dummy, new_node);
+ bucket = lookup_bucket(ht, size, bit_reverse_ulong(old_node->reverse_hash));
+ _cds_lfht_gc_bucket(bucket, new_node);
- assert(is_removed(rcu_dereference(old_node->
p.
next)));
+ assert(is_removed(rcu_dereference(old_node->next)));
return 0;
}
return 0;
}
@@
-892,18
+889,20
@@
int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
*/
static
void _cds_lfht_add(struct cds_lfht *ht,
*/
static
void _cds_lfht_add(struct cds_lfht *ht,
+ cds_lfht_match_fct match,
+ void *key,
unsigned long size,
struct cds_lfht_node *node,
struct cds_lfht_iter *unique_ret,
unsigned long size,
struct cds_lfht_node *node,
struct cds_lfht_iter *unique_ret,
- int
dummy
)
+ int
bucket_flag
)
{
struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
*return_node;
{
struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
*return_node;
- struct
_cds_lfht_node *lookup
;
+ struct
cds_lfht_node *bucket
;
- assert(!is_
dummy
(node));
+ assert(!is_
bucket
(node));
assert(!is_removed(node));
assert(!is_removed(node));
-
lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.
reverse_hash));
+
bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->
reverse_hash));
for (;;) {
uint32_t chain_len = 0;
for (;;) {
uint32_t chain_len = 0;
@@
-911,28
+910,28
@@
void _cds_lfht_add(struct cds_lfht *ht,
* 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 =
(struct cds_lfht_node *) lookup
;
- /* We can always skip the
dummy
node initially */
- iter = rcu_dereference(iter_prev->
p.
next);
- assert(iter_prev->
p.reverse_hash <= node->p.
reverse_hash);
+ iter_prev =
bucket
;
+ /* We can always skip the
bucket
node initially */
+ iter = rcu_dereference(iter_prev->next);
+ assert(iter_prev->
reverse_hash <= node->
reverse_hash);
for (;;) {
if (caa_unlikely(is_end(iter)))
goto insert;
for (;;) {
if (caa_unlikely(is_end(iter)))
goto insert;
- if (caa_likely(clear_flag(iter)->
p.reverse_hash > node->p.
reverse_hash))
+ if (caa_likely(clear_flag(iter)->
reverse_hash > node->
reverse_hash))
goto insert;
goto insert;
- /*
dummy
node is the first node of the identical-hash-value chain */
- if (
dummy && clear_flag(iter)->p.reverse_hash == node->p.
reverse_hash)
+ /*
bucket
node is the first node of the identical-hash-value chain */
+ if (
bucket_flag && clear_flag(iter)->reverse_hash == node->
reverse_hash)
goto insert;
goto insert;
- next = rcu_dereference(clear_flag(iter)->
p.
next);
+ next = rcu_dereference(clear_flag(iter)->next);
if (caa_unlikely(is_removed(next)))
goto gc_node;
/* uniquely add */
if (unique_ret
if (caa_unlikely(is_removed(next)))
goto gc_node;
/* uniquely add */
if (unique_ret
- && !is_
dummy
(next)
- && clear_flag(iter)->
p.reverse_hash == node->p.
reverse_hash) {
+ && !is_
bucket
(next)
+ && clear_flag(iter)->
reverse_hash == node->
reverse_hash) {
struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
/*
struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
/*
@@
-944,7
+943,7
@@
void _cds_lfht_add(struct cds_lfht *ht,
* (including observe one node by one node
* by forward iterations)
*/
* (including observe one node by one node
* by forward iterations)
*/
- cds_lfht_next_duplicate(ht, &d_iter);
+ cds_lfht_next_duplicate(ht,
match, key,
&d_iter);
if (!d_iter.node)
goto insert;
if (!d_iter.node)
goto insert;
@@
-953,8
+952,8
@@
void _cds_lfht_add(struct cds_lfht *ht,
}
/* Only account for identical reverse hash once */
}
/* Only account for identical reverse hash once */
- if (iter_prev->
p.reverse_hash != clear_flag(iter)->p.
reverse_hash
- && !is_
dummy
(next))
+ if (iter_prev->
reverse_hash != clear_flag(iter)->
reverse_hash
+ && !is_
bucket
(next))
check_resize(ht, size, ++chain_len);
iter_prev = clear_flag(iter);
iter = next;
check_resize(ht, size, ++chain_len);
iter_prev = clear_flag(iter);
iter = next;
@@
-965,15
+964,15
@@
void _cds_lfht_add(struct cds_lfht *ht,
assert(!is_removed(iter_prev));
assert(!is_removed(iter));
assert(iter_prev != node);
assert(!is_removed(iter_prev));
assert(!is_removed(iter));
assert(iter_prev != node);
- if (!
dummy
)
- node->
p.
next = clear_flag(iter);
+ if (!
bucket_flag
)
+ node->next = clear_flag(iter);
else
else
- node->
p.next = flag_dummy
(clear_flag(iter));
- if (is_
dummy
(iter))
- new_node = flag_
dummy
(node);
+ node->
next = flag_bucket
(clear_flag(iter));
+ if (is_
bucket
(iter))
+ new_node = flag_
bucket
(node);
else
new_node = node;
else
new_node = node;
- if (uatomic_cmpxchg(&iter_prev->
p.
next, iter,
+ if (uatomic_cmpxchg(&iter_prev->next, iter,
new_node) != iter) {
continue; /* retry */
} else {
new_node) != iter) {
continue; /* retry */
} else {
@@
-983,11
+982,11
@@
void _cds_lfht_add(struct cds_lfht *ht,
gc_node:
assert(!is_removed(iter));
gc_node:
assert(!is_removed(iter));
- if (is_
dummy
(iter))
- new_next = flag_
dummy
(clear_flag(next));
+ if (is_
bucket
(iter))
+ new_next = flag_
bucket
(clear_flag(next));
else
new_next = clear_flag(next);
else
new_next = clear_flag(next);
- (void) uatomic_cmpxchg(&iter_prev->
p.
next, iter, new_next);
+ (void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
/* retry */
}
end:
/* retry */
}
end:
@@
-1000,30
+999,29
@@
end:
static
int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
struct cds_lfht_node *node,
static
int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
struct cds_lfht_node *node,
- int
dummy
_removal)
+ int
bucket
_removal)
{
{
- struct cds_lfht_node *dummy, *next, *old;
- struct _cds_lfht_node *lookup;
+ struct cds_lfht_node *bucket, *next, *old;
if (!node) /* Return -ENOENT if asked to delete NULL node */
return -ENOENT;
/* logically delete the node */
if (!node) /* Return -ENOENT if asked to delete NULL node */
return -ENOENT;
/* logically delete the node */
- assert(!is_
dummy
(node));
+ assert(!is_
bucket
(node));
assert(!is_removed(node));
assert(!is_removed(node));
- old = rcu_dereference(node->
p.
next);
+ old = rcu_dereference(node->next);
do {
struct cds_lfht_node *new_next;
next = old;
if (caa_unlikely(is_removed(next)))
return -ENOENT;
do {
struct cds_lfht_node *new_next;
next = old;
if (caa_unlikely(is_removed(next)))
return -ENOENT;
- if (
dummy
_removal)
- assert(is_
dummy
(next));
+ if (
bucket
_removal)
+ assert(is_
bucket
(next));
else
else
- assert(!is_
dummy
(next));
+ assert(!is_
bucket
(next));
new_next = flag_removed(next);
new_next = flag_removed(next);
- old = uatomic_cmpxchg(&node->
p.
next, next, new_next);
+ old = uatomic_cmpxchg(&node->next, next, new_next);
} while (old != next);
/* We performed the (logical) deletion. */
} while (old != next);
/* We performed the (logical) deletion. */
@@
-1032,11
+1030,10
@@
int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
* 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.
*/
- lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash));
- dummy = (struct cds_lfht_node *) lookup;
- _cds_lfht_gc_bucket(dummy, node);
+ bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
+ _cds_lfht_gc_bucket(bucket, node);
- assert(is_removed(rcu_dereference(node->
p.
next)));
+ assert(is_removed(rcu_dereference(node->next)));
return 0;
}
return 0;
}
@@
-1102,7
+1099,7
@@
void partition_resize_helper(struct cds_lfht *ht, unsigned long i,
* many worker threads, based on the number of CPUs available in the system.
* This should therefore take care of not having the expand lagging behind too
* many concurrent insertion threads by using the scheduler's ability to
* many worker threads, based on the number of CPUs available in the system.
* This should therefore take care of not having the expand lagging behind too
* many concurrent insertion threads by using the scheduler's ability to
- * schedule
dummy
node population fairly with insertions.
+ * schedule
bucket
node population fairly with insertions.
*/
static
void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
*/
static
void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
@@
-1113,14
+1110,13
@@
void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
assert(i > ht->min_alloc_order);
ht->cds_lfht_rcu_read_lock();
for (j = start; j < start + len; j++) {
assert(i > ht->min_alloc_order);
ht->cds_lfht_rcu_read_lock();
for (j = start; j < start + len; j++) {
- struct cds_lfht_node *new_node =
- (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
+ struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j];
dbg_printf("init populate: i %lu j %lu hash %lu\n",
i, j, (1UL << (i - 1)) + j);
dbg_printf("init populate: i %lu j %lu hash %lu\n",
i, j, (1UL << (i - 1)) + j);
- new_node->
p.
reverse_hash =
+ new_node->reverse_hash =
bit_reverse_ulong((1UL << (i - 1)) + j);
bit_reverse_ulong((1UL << (i - 1)) + j);
- _cds_lfht_add(ht, 1UL << (i - 1),
+ _cds_lfht_add(ht,
NULL, NULL,
1UL << (i - 1),
new_node, NULL, 1);
}
ht->cds_lfht_rcu_read_unlock();
new_node, NULL, 1);
}
ht->cds_lfht_rcu_read_unlock();
@@
-1159,12
+1155,12
@@
void init_table(struct cds_lfht *ht,
if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
break;
if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
break;
- ht->t.tbl[i] = calloc(1, len * sizeof(struct
_
cds_lfht_node));
+ ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
assert(ht->t.tbl[i]);
/*
assert(ht->t.tbl[i]);
/*
- * Set all
dummy
nodes reverse hash values for a level and
- * link all
dummy
nodes into the table.
+ * Set all
bucket
nodes reverse hash values for a level and
+ * link all
bucket
nodes into the table.
*/
init_table_populate(ht, i, len);
*/
init_table_populate(ht, i, len);
@@
-1195,7
+1191,7
@@
void init_table(struct cds_lfht *ht,
* Concurrent removal and add operations are helping us perform garbage
* collection of logically removed nodes. We guarantee that all logically
* removed nodes have been garbage-collected (unlinked) before call_rcu is
* Concurrent removal and add operations are helping us perform garbage
* collection of logically removed nodes. We guarantee that all logically
* removed nodes have been garbage-collected (unlinked) before call_rcu is
- * invoked to free a hole level of
dummy
nodes (after a grace period).
+ * invoked to free a hole level of
bucket
nodes (after a grace period).
*
* Logical removal and garbage collection can therefore be done in batch or on a
* node-per-node basis, as long as the guarantee above holds.
*
* Logical removal and garbage collection can therefore be done in batch or on a
* node-per-node basis, as long as the guarantee above holds.
@@
-1214,12
+1210,11
@@
void remove_table_partition(struct cds_lfht *ht, unsigned long i,
assert(i > ht->min_alloc_order);
ht->cds_lfht_rcu_read_lock();
for (j = start; j < start + len; j++) {
assert(i > ht->min_alloc_order);
ht->cds_lfht_rcu_read_lock();
for (j = start; j < start + len; j++) {
- struct cds_lfht_node *fini_node =
- (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
+ struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j];
dbg_printf("remove entry: i %lu j %lu hash %lu\n",
i, j, (1UL << (i - 1)) + j);
dbg_printf("remove entry: i %lu j %lu hash %lu\n",
i, j, (1UL << (i - 1)) + j);
- fini_node->
p.
reverse_hash =
+ fini_node->reverse_hash =
bit_reverse_ulong((1UL << (i - 1)) + j);
(void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
}
bit_reverse_ulong((1UL << (i - 1)) + j);
(void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
}
@@
-1266,7
+1261,7
@@
void fini_table(struct cds_lfht *ht,
/*
* We need to wait for all add operations to reach Q.S. (and
* thus use the new table for lookups) before we can start
/*
* We need to wait for all add operations to reach Q.S. (and
* thus use the new table for lookups) before we can start
- * releasing the old
dummy
nodes. Otherwise their lookup will
+ * releasing the old
bucket
nodes. Otherwise their lookup will
* return a logically removed node as insert position.
*/
ht->cds_lfht_synchronize_rcu();
* return a logically removed node as insert position.
*/
ht->cds_lfht_synchronize_rcu();
@@
-1274,8
+1269,8
@@
void fini_table(struct cds_lfht *ht,
free(free_by_rcu);
/*
free(free_by_rcu);
/*
- * Set "removed" flag in
dummy
nodes about to be removed.
- * Unlink all now-logically-removed
dummy
node pointers.
+ * Set "removed" flag in
bucket
nodes about to be removed.
+ * Unlink all now-logically-removed
bucket
node pointers.
* Concurrent add/remove operation are helping us doing
* the gc.
*/
* Concurrent add/remove operation are helping us doing
* the gc.
*/
@@
-1295,16
+1290,16
@@
void fini_table(struct cds_lfht *ht,
}
static
}
static
-void cds_lfht_create_
dummy
(struct cds_lfht *ht, unsigned long size)
+void cds_lfht_create_
bucket
(struct cds_lfht *ht, unsigned long size)
{
{
- struct
_
cds_lfht_node *prev, *node;
+ struct cds_lfht_node *prev, *node;
unsigned long order, len, i, j;
unsigned long order, len, i, j;
- ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct
_
cds_lfht_node));
+ ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
assert(ht->t.tbl[0]);
assert(ht->t.tbl[0]);
- dbg_printf("create
dummy
: order %lu index %lu hash %lu\n", 0, 0, 0);
- ht->t.tbl[0]->nodes[0].next = flag_
dummy
(get_end());
+ dbg_printf("create
bucket
: order %lu index %lu hash %lu\n", 0, 0, 0);
+ ht->t.tbl[0]->nodes[0].next = flag_
bucket
(get_end());
ht->t.tbl[0]->nodes[0].reverse_hash = 0;
for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
ht->t.tbl[0]->nodes[0].reverse_hash = 0;
for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
@@
-1312,7
+1307,7
@@
void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
if (order <= ht->min_alloc_order) {
ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
} else {
if (order <= ht->min_alloc_order) {
ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
} else {
- ht->t.tbl[order] = calloc(1, len * sizeof(struct
_
cds_lfht_node));
+ ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
assert(ht->t.tbl[order]);
}
assert(ht->t.tbl[order]);
}
@@
-1327,20
+1322,17
@@
void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
}
node = &ht->t.tbl[order]->nodes[j];
}
node = &ht->t.tbl[order]->nodes[j];
- dbg_printf("create
dummy
: order %lu index %lu hash %lu\n",
+ dbg_printf("create
bucket
: order %lu index %lu hash %lu\n",
order, j, j + len);
node->next = prev->next;
order, j, j + len);
node->next = prev->next;
- assert(is_
dummy
(node->next));
+ assert(is_
bucket
(node->next));
node->reverse_hash = bit_reverse_ulong(j + len);
node->reverse_hash = bit_reverse_ulong(j + len);
- prev->next = flag_
dummy((struct cds_lfht_node *)
node);
+ prev->next = flag_
bucket(
node);
}
}
}
}
}
}
-struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
- cds_lfht_compare_fct compare_fct,
- unsigned long hash_seed,
- unsigned long init_size,
+struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_alloc_size,
int flags,
void (*cds_lfht_call_rcu)(struct rcu_head *head,
unsigned long min_alloc_size,
int flags,
void (*cds_lfht_call_rcu)(struct rcu_head *head,
@@
-1368,9
+1360,6
@@
struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
ht->flags = flags;
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
ht->flags = flags;
- ht->hash_fct = hash_fct;
- ht->compare_fct = compare_fct;
- ht->hash_seed = hash_seed;
ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
@@
-1387,62
+1376,56
@@
struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
ht->t.resize_target = 1UL << order;
ht->min_alloc_size = min_alloc_size;
ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
ht->t.resize_target = 1UL << order;
ht->min_alloc_size = min_alloc_size;
ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
- cds_lfht_create_
dummy
(ht, 1UL << order);
+ cds_lfht_create_
bucket
(ht, 1UL << order);
ht->t.size = 1UL << order;
return ht;
}
ht->t.size = 1UL << order;
return ht;
}
-void cds_lfht_lookup(struct cds_lfht *ht,
void *key, size_t key_len
,
- struct cds_lfht_iter *iter)
+void cds_lfht_lookup(struct cds_lfht *ht,
cds_lfht_match_fct match
,
+
unsigned long hash, void *key,
struct cds_lfht_iter *iter)
{
{
- struct cds_lfht_node *node, *next, *dummy_node;
- struct _cds_lfht_node *lookup;
- unsigned long hash, reverse_hash, size;
+ struct cds_lfht_node *node, *next, *bucket;
+ unsigned long reverse_hash, size;
- hash = ht->hash_fct(key, key_len, ht->hash_seed);
reverse_hash = bit_reverse_ulong(hash);
size = rcu_dereference(ht->t.size);
reverse_hash = bit_reverse_ulong(hash);
size = rcu_dereference(ht->t.size);
- lookup = lookup_bucket(ht, size, hash);
- dummy_node = (struct cds_lfht_node *) lookup;
- /* We can always skip the dummy node initially */
- node = rcu_dereference(dummy_node->p.next);
+ bucket = lookup_bucket(ht, size, hash);
+ /* We can always skip the bucket node initially */
+ node = rcu_dereference(bucket->next);
node = clear_flag(node);
for (;;) {
if (caa_unlikely(is_end(node))) {
node = next = NULL;
break;
}
node = clear_flag(node);
for (;;) {
if (caa_unlikely(is_end(node))) {
node = next = NULL;
break;
}
- if (caa_unlikely(node->
p.
reverse_hash > reverse_hash)) {
+ if (caa_unlikely(node->reverse_hash > reverse_hash)) {
node = next = NULL;
break;
}
node = next = NULL;
break;
}
- next = rcu_dereference(node->
p.
next);
+ next = rcu_dereference(node->next);
assert(node == clear_flag(node));
if (caa_likely(!is_removed(next))
assert(node == clear_flag(node));
if (caa_likely(!is_removed(next))
- && !is_
dummy
(next)
- && node->
p.
reverse_hash == reverse_hash
- && caa_likely(
!ht->compare_fct(node->key, node->key_len, key, key_len
))) {
+ && !is_
bucket
(next)
+ && node->reverse_hash == reverse_hash
+ && caa_likely(
match(node, key
))) {
break;
}
node = clear_flag(next);
}
break;
}
node = clear_flag(next);
}
- assert(!node || !is_
dummy(rcu_dereference(node->p.
next)));
+ assert(!node || !is_
bucket(rcu_dereference(node->
next)));
iter->node = node;
iter->next = next;
}
iter->node = node;
iter->next = next;
}
-void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
+void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
+ void *key, struct cds_lfht_iter *iter)
{
struct cds_lfht_node *node, *next;
unsigned long reverse_hash;
{
struct cds_lfht_node *node, *next;
unsigned long reverse_hash;
- void *key;
- size_t key_len;
node = iter->node;
node = iter->node;
- reverse_hash = node->p.reverse_hash;
- key = node->key;
- key_len = node->key_len;
+ reverse_hash = node->reverse_hash;
next = iter->next;
node = clear_flag(next);
next = iter->next;
node = clear_flag(next);
@@
-1451,19
+1434,19
@@
void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
node = next = NULL;
break;
}
node = next = NULL;
break;
}
- if (caa_unlikely(node->
p.
reverse_hash > reverse_hash)) {
+ if (caa_unlikely(node->reverse_hash > reverse_hash)) {
node = next = NULL;
break;
}
node = next = NULL;
break;
}
- next = rcu_dereference(node->
p.
next);
+ next = rcu_dereference(node->next);
if (caa_likely(!is_removed(next))
if (caa_likely(!is_removed(next))
- && !is_
dummy
(next)
- && caa_likely(
!ht->compare_fct(node->key, node->key_len, key, key_len
))) {
+ && !is_
bucket
(next)
+ && caa_likely(
match(node, key
))) {
break;
}
node = clear_flag(next);
}
break;
}
node = clear_flag(next);
}
- assert(!node || !is_
dummy(rcu_dereference(node->p.
next)));
+ assert(!node || !is_
bucket(rcu_dereference(node->
next)));
iter->node = node;
iter->next = next;
}
iter->node = node;
iter->next = next;
}
@@
-1478,24
+1461,24
@@
void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
node = next = NULL;
break;
}
node = next = NULL;
break;
}
- next = rcu_dereference(node->
p.
next);
+ next = rcu_dereference(node->next);
if (caa_likely(!is_removed(next))
if (caa_likely(!is_removed(next))
- && !is_
dummy
(next)) {
+ && !is_
bucket
(next)) {
break;
}
node = clear_flag(next);
}
break;
}
node = clear_flag(next);
}
- assert(!node || !is_
dummy(rcu_dereference(node->p.
next)));
+ assert(!node || !is_
bucket(rcu_dereference(node->
next)));
iter->node = node;
iter->next = next;
}
void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
{
iter->node = node;
iter->next = next;
}
void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
{
- struct
_
cds_lfht_node *lookup;
+ struct cds_lfht_node *lookup;
/*
/*
- * Get next after first
dummy node. The first dummy
node is the
+ * Get next after first
bucket node. The first bucket
node is the
* first node of the linked list.
*/
lookup = &ht->t.tbl[0]->nodes[0];
* first node of the linked list.
*/
lookup = &ht->t.tbl[0]->nodes[0];
@@
-1503,46
+1486,47
@@
void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
cds_lfht_next(ht, iter);
}
cds_lfht_next(ht, iter);
}
-void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
+void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
+ struct cds_lfht_node *node)
{
{
- unsigned long hash, size;
-
- hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
- node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+ unsigned long size;
+ node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
size = rcu_dereference(ht->t.size);
size = rcu_dereference(ht->t.size);
- _cds_lfht_add(ht, size, node, NULL, 0);
+ _cds_lfht_add(ht,
NULL, NULL,
size, node, NULL, 0);
ht_count_add(ht, size, hash);
}
struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
ht_count_add(ht, size, hash);
}
struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
+ cds_lfht_match_fct match,
+ void *key,
+ unsigned long hash,
struct cds_lfht_node *node)
{
struct cds_lfht_node *node)
{
- unsigned long
hash,
size;
+ unsigned long size;
struct cds_lfht_iter iter;
struct cds_lfht_iter iter;
- hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
- node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
-
+ node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
size = rcu_dereference(ht->t.size);
size = rcu_dereference(ht->t.size);
- _cds_lfht_add(ht, size, node, &iter, 0);
+ _cds_lfht_add(ht,
match, key,
size, node, &iter, 0);
if (iter.node == node)
ht_count_add(ht, size, hash);
return iter.node;
}
struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
if (iter.node == node)
ht_count_add(ht, size, hash);
return iter.node;
}
struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
+ cds_lfht_match_fct match,
+ void *key,
+ unsigned long hash,
struct cds_lfht_node *node)
{
struct cds_lfht_node *node)
{
- unsigned long
hash,
size;
+ unsigned long size;
struct cds_lfht_iter iter;
struct cds_lfht_iter iter;
- hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
- node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
-
+ node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
size = rcu_dereference(ht->t.size);
for (;;) {
size = rcu_dereference(ht->t.size);
for (;;) {
- _cds_lfht_add(ht, size, node, &iter, 0);
+ _cds_lfht_add(ht,
match, key,
size, node, &iter, 0);
if (iter.node == node) {
ht_count_add(ht, size, hash);
return NULL;
if (iter.node == node) {
ht_count_add(ht, size, hash);
return NULL;
@@
-1571,25
+1555,23
@@
int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
size = rcu_dereference(ht->t.size);
ret = _cds_lfht_del(ht, size, iter->node, 0);
if (!ret) {
size = rcu_dereference(ht->t.size);
ret = _cds_lfht_del(ht, size, iter->node, 0);
if (!ret) {
- hash = bit_reverse_ulong(iter->node->
p.
reverse_hash);
+ hash = bit_reverse_ulong(iter->node->reverse_hash);
ht_count_del(ht, size, hash);
}
return ret;
}
static
ht_count_del(ht, size, hash);
}
return ret;
}
static
-int cds_lfht_delete_
dummy
(struct cds_lfht *ht)
+int cds_lfht_delete_
bucket
(struct cds_lfht *ht)
{
struct cds_lfht_node *node;
{
struct cds_lfht_node *node;
- struct _cds_lfht_node *lookup;
unsigned long order, i, size;
/* Check that the table is empty */
unsigned long order, i, size;
/* Check that the table is empty */
- lookup = &ht->t.tbl[0]->nodes[0];
- node = (struct cds_lfht_node *) lookup;
+ node = &ht->t.tbl[0]->nodes[0];
do {
do {
- node = clear_flag(node)->
p.
next;
- if (!is_
dummy
(node))
+ node = clear_flag(node)->next;
+ if (!is_
bucket
(node))
return -EPERM;
assert(!is_removed(node));
} while (!is_end(node));
return -EPERM;
assert(!is_removed(node));
} while (!is_end(node));
@@
-1598,7
+1580,7
@@
int cds_lfht_delete_dummy(struct cds_lfht *ht)
* being destroyed.
*/
size = ht->t.size;
* being destroyed.
*/
size = ht->t.size;
- /* Internal sanity check: all nodes left should be
dummy
*/
+ /* Internal sanity check: all nodes left should be
bucket
*/
for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
unsigned long len;
for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
unsigned long len;
@@
-1607,7
+1589,7
@@
int cds_lfht_delete_dummy(struct cds_lfht *ht)
dbg_printf("delete order %lu i %lu hash %lu\n",
order, i,
bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
dbg_printf("delete order %lu i %lu hash %lu\n",
order, i,
bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
- assert(is_
dummy
(ht->t.tbl[order]->nodes[i].next));
+ assert(is_
bucket
(ht->t.tbl[order]->nodes[i].next));
}
if (order == ht->min_alloc_order)
}
if (order == ht->min_alloc_order)
@@
-1632,7
+1614,7
@@
int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
cmm_smp_mb(); /* Store destroy before load resize */
while (uatomic_read(&ht->in_progress_resize))
poll(NULL, 0, 100); /* wait for 100ms */
cmm_smp_mb(); /* Store destroy before load resize */
while (uatomic_read(&ht->in_progress_resize))
poll(NULL, 0, 100); /* wait for 100ms */
- ret = cds_lfht_delete_
dummy
(ht);
+ ret = cds_lfht_delete_
bucket
(ht);
if (ret)
return ret;
free_split_items_count(ht);
if (ret)
return ret;
free_split_items_count(ht);
@@
-1649,8
+1631,7
@@
void cds_lfht_count_nodes(struct cds_lfht *ht,
long *approx_after)
{
struct cds_lfht_node *node, *next;
long *approx_after)
{
struct cds_lfht_node *node, *next;
- struct _cds_lfht_node *lookup;
- unsigned long nr_dummy = 0;
+ unsigned long nr_bucket = 0;
*approx_before = 0;
if (ht->split_count) {
*approx_before = 0;
if (ht->split_count) {
@@
-1665,23
+1646,22
@@
void cds_lfht_count_nodes(struct cds_lfht *ht,
*count = 0;
*removed = 0;
*count = 0;
*removed = 0;
- /* Count non-dummy nodes in the table */
- lookup = &ht->t.tbl[0]->nodes[0];
- node = (struct cds_lfht_node *) lookup;
+ /* Count non-bucket nodes in the table */
+ node = &ht->t.tbl[0]->nodes[0];
do {
do {
- next = rcu_dereference(node->
p.
next);
+ next = rcu_dereference(node->next);
if (is_removed(next)) {
if (is_removed(next)) {
- if (!is_
dummy
(next))
+ if (!is_
bucket
(next))
(*removed)++;
else
(*removed)++;
else
- (nr_
dummy
)++;
- } else if (!is_
dummy
(next))
+ (nr_
bucket
)++;
+ } else if (!is_
bucket
(next))
(*count)++;
else
(*count)++;
else
- (nr_
dummy
)++;
+ (nr_
bucket
)++;
node = clear_flag(next);
} while (!is_end(node));
node = clear_flag(next);
} while (!is_end(node));
- dbg_printf("number of
dummy nodes: %lu\n", nr_dummy
);
+ dbg_printf("number of
bucket nodes: %lu\n", nr_bucket
);
*approx_after = 0;
if (ht->split_count) {
int i;
*approx_after = 0;
if (ht->split_count) {
int i;
@@
-1722,7
+1702,7
@@
void _do_cds_lfht_shrink(struct cds_lfht *ht,
old_size, old_order, new_size, new_order);
assert(new_size < old_size);
old_size, old_order, new_size, new_order);
assert(new_size < old_size);
- /* Remove and unlink all
dummy
nodes to remove. */
+ /* Remove and unlink all
bucket
nodes to remove. */
fini_table(ht, new_order + 1, old_order);
}
fini_table(ht, new_order + 1, old_order);
}
This page took
0.049553 seconds
and
4
git commands to generate.