* Lai Jiangshan ([email protected]) wrote: > Fast path is not changed. > It will slow down very little for slow path.
it cleans up the code, so it's generally fine with me. There is just one part that I don't understand, see below, > > Signed-off-by: Lai Jiangshan <[email protected]> > --- > rculfhash.c | 100 +++++++++++++++++++++++++++------------------------------- > 1 files changed, 47 insertions(+), 53 deletions(-) > > diff --git a/rculfhash.c b/rculfhash.c > index bda3bd6..b0c7de5 100644 > --- a/rculfhash.c > +++ b/rculfhash.c > @@ -755,18 +755,14 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned > long *ptr, > return old2; > } > > -static > -struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size, > - unsigned long hash) > +static inline > +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) > { > - unsigned long index, order; > - > - assert(size > 0); > - index = hash & (size - 1); > + unsigned long order; > > - if (index < ht->min_alloc_size) { > - dbg_printf("lookup hash %lu index %lu order 0 aridx 0\n", > - hash, index); > + if ((__builtin_constant_p(index) && index == 0) > + || index < ht->min_alloc_size) { > + dbg_printf("bucket index %lu order 0 aridx 0\n", index); > return &ht->t.tbl[0]->nodes[index]; > } > /* > @@ -775,11 +771,19 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht > *ht, unsigned long size, > * get_count_order_ulong. > */ > order = fls_ulong(index); > - dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n", > - hash, index, order, index & ((1UL << (order - 1)) - 1)); > + dbg_printf("bucket index %lu order %lu aridx %lu\n", > + index, order, index & ((1UL << (order - 1)) - 1)); > return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)]; > } > > +static inline > +struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size, > + unsigned long hash) > +{ > + assert(size > 0); > + return bucket_at(ht, hash & (size - 1)); > +} > + > /* > * Remove all logically deleted nodes from a bucket up to a certain node key. > */ > @@ -1105,19 +1109,18 @@ static > void init_table_populate_partition(struct cds_lfht *ht, unsigned long i, > unsigned long start, unsigned long len) > { > - unsigned long j; > + unsigned long j, size = 1UL << (i - 1); > > 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 = &ht->t.tbl[i]->nodes[j]; > - > - dbg_printf("init populate: i %lu j %lu hash %lu\n", > - i, j, (1UL << (i - 1)) + j); > - new_node->reverse_hash = > - bit_reverse_ulong((1UL << (i - 1)) + j); > - _cds_lfht_add(ht, NULL, NULL, 1UL << (i - 1), > - new_node, NULL, 1); > + for (j = start + size; j < size + start + len; j++) { Please use "j = size + start; j < size + start + len;" > + struct cds_lfht_node *new_node = bucket_at(ht, j); > + > + assert(j >= size && j < (size << 1)); > + 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); > } > ht->cds_lfht_rcu_read_unlock(); > } > @@ -1205,18 +1208,18 @@ static > void remove_table_partition(struct cds_lfht *ht, unsigned long i, > unsigned long start, unsigned long len) > { > - unsigned long j; > + unsigned long j, size = 1UL << (i - 1); > > 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 = &ht->t.tbl[i]->nodes[j]; > - > - dbg_printf("remove entry: i %lu j %lu hash %lu\n", > - i, j, (1UL << (i - 1)) + j); > - fini_node->reverse_hash = > - bit_reverse_ulong((1UL << (i - 1)) + j); > - (void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1); > + for (j = size + start; j < size + start + len; j++) { > + struct cds_lfht_node *fini_node = bucket_at(ht, j); > + > + assert(j >= size && j < (size << 1)); > + dbg_printf("remove entry: order %lu index %lu hash %lu\n", > + i, j, j); > + fini_node->reverse_hash = bit_reverse_ulong(j); > + (void) _cds_lfht_del(ht, size, fini_node, 1); > } > ht->cds_lfht_rcu_read_unlock(); > } > @@ -1293,14 +1296,15 @@ static > void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size) > { > struct cds_lfht_node *prev, *node; > - unsigned long order, len, i, j; > + unsigned long order, len, i; > > ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct > cds_lfht_node)); > assert(ht->t.tbl[0]); > > - 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; > + dbg_printf("create bucket: order 0 index 0 hash 0\n"); > + node = bucket_at(ht, 0); > + node->next = flag_bucket(get_end()); > + node->reverse_hash = 0; > > for (order = 1; order < get_count_order_ulong(size) + 1; order++) { > len = 1UL << (order - 1); > @@ -1311,22 +1315,15 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, > unsigned long size) > assert(ht->t.tbl[order]); > } > below is the change I fail to understand. I think I'd need to be walked through this change with an explanation, which could be added as a comment telling what this function is doing. > - i = 0; > - prev = ht->t.tbl[i]->nodes; > - for (j = 0; j < len; j++) { > - if (j & (j - 1)) { /* Between power of 2 */ > - prev++; > - } else if (j) { /* At each power of 2 */ > - i++; > - prev = ht->t.tbl[i]->nodes; > - } > + for (i = 0; i < len; i++) { > + prev = bucket_at(ht, i); > + node = bucket_at(ht, i + len); Using "len + i" would help us follow the code, as i changes, but not len. I usually try to put the iterators that change the most (innermost indexes) at the right. > > - node = &ht->t.tbl[order]->nodes[j]; > dbg_printf("create bucket: order %lu index %lu hash > %lu\n", > - order, j, j + len); > + order, i + len, i + len); Same here, > node->next = prev->next; > assert(is_bucket(node->next)); > - node->reverse_hash = bit_reverse_ulong(j + len); > + node->reverse_hash = bit_reverse_ulong(i + len); Same here, Thanks! Mathieu > prev->next = flag_bucket(node); > } > } > @@ -1476,14 +1473,11 @@ void cds_lfht_next(struct cds_lfht *ht, struct > cds_lfht_iter *iter) > > void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter) > { > - struct cds_lfht_node *lookup; > - > /* > * 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]; > - iter->next = lookup->next; > + iter->next = bucket_at(ht, 0)->next; > cds_lfht_next(ht, iter); > } > > @@ -1569,7 +1563,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht) > unsigned long order, i, size; > > /* Check that the table is empty */ > - node = &ht->t.tbl[0]->nodes[0]; > + node = bucket_at(ht, 0); > do { > node = clear_flag(node)->next; > if (!is_bucket(node)) > @@ -1648,7 +1642,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, > *removed = 0; > > /* Count non-bucket nodes in the table */ > - node = &ht->t.tbl[0]->nodes[0]; > + node = bucket_at(ht, 0); > do { > next = rcu_dereference(node->next); > if (is_removed(next)) { > -- > 1.7.4.4 > -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com _______________________________________________ ltt-dev mailing list [email protected] http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
