Message ID | 20200731092323.763-2-anton.ivanov@cambridgegreys.com |
---|---|
State | Changes Requested |
Headers | show |
Series | [ovs-dev,1/3] Optimise shash disposal | expand |
On 7/31/20 11:23 AM, anton.ivanov@cambridgegreys.com wrote: > From: Anton Ivanov <anton.ivanov@cambridgegreys.com> > > SHASH as written at present relies on HMAP and iterator macros > to dispose of all of its elements. > > This results in a lot of unnecessary hash comparisons and walk > attempts which simply return the next item. > > This patch switches this to direct removal where the whole shash > is cleared at once in O(N) without any hash recomputations and > comparisons. > > Signed-off-by: Anton Ivanov <anton.ivanov@cambridgegreys.com> > --- > lib/shash.c | 48 +++++++++++++++++++++++++++++++++++++----------- > 1 file changed, 37 insertions(+), 11 deletions(-) > > diff --git a/lib/shash.c b/lib/shash.c > index a8433629a..09505b73d 100644 > --- a/lib/shash.c > +++ b/lib/shash.c > @@ -68,27 +68,53 @@ shash_moved(struct shash *sh) > void > shash_clear(struct shash *sh) > { > - struct shash_node *node, *next; > + struct shash_node *node; > + struct hmap_node *hn; > + > + int i; > > - SHASH_FOR_EACH_SAFE (node, next, sh) { > - hmap_remove(&sh->map, &node->node); > - free(node->name); > - free(node); > + if (sh->map.n == 0) { > + return; > + } > + > + for (i = 0; i <= sh->map.mask; i++) { > + hn = sh->map.buckets[i]; > + while (hn != NULL) { > + node = CONTAINER_OF(hn, struct shash_node, node); > + hn = hn->next; > + free(node->name); > + free(node); > + } > + sh->map.buckets[i] = NULL; > } > + sh->map.n = 0; > } > > /* Like shash_clear(), but also free() each node's 'data'. */ > void > shash_clear_free_data(struct shash *sh) > { > - struct shash_node *node, *next; > + struct shash_node *node; > + struct hmap_node *hn; > + > + int i; > > - SHASH_FOR_EACH_SAFE (node, next, sh) { > - hmap_remove(&sh->map, &node->node); > - free(node->data); > - free(node->name); > - free(node); > + if (sh->map.n == 0) { > + return; > + } > + > + for (i = 0; i <= sh->map.mask; i++) { > + hn = sh->map.buckets[i]; > + while (hn != NULL) { > + node = CONTAINER_OF(hn, struct shash_node, node); > + hn = hn->next; > + free(node->data); > + free(node->name); > + free(node); > + } > + sh->map.buckets[i] = NULL; > } > + sh->map.n = 0; > } > > bool > Hi Anton, With this we're now using hmap internals in shash.c. Wouldn't it be better for hmap to expose an API to clear (maybe with a handler per node)? Thanks, Dumitru
diff --git a/lib/shash.c b/lib/shash.c index a8433629a..09505b73d 100644 --- a/lib/shash.c +++ b/lib/shash.c @@ -68,27 +68,53 @@ shash_moved(struct shash *sh) void shash_clear(struct shash *sh) { - struct shash_node *node, *next; + struct shash_node *node; + struct hmap_node *hn; + + int i; - SHASH_FOR_EACH_SAFE (node, next, sh) { - hmap_remove(&sh->map, &node->node); - free(node->name); - free(node); + if (sh->map.n == 0) { + return; + } + + for (i = 0; i <= sh->map.mask; i++) { + hn = sh->map.buckets[i]; + while (hn != NULL) { + node = CONTAINER_OF(hn, struct shash_node, node); + hn = hn->next; + free(node->name); + free(node); + } + sh->map.buckets[i] = NULL; } + sh->map.n = 0; } /* Like shash_clear(), but also free() each node's 'data'. */ void shash_clear_free_data(struct shash *sh) { - struct shash_node *node, *next; + struct shash_node *node; + struct hmap_node *hn; + + int i; - SHASH_FOR_EACH_SAFE (node, next, sh) { - hmap_remove(&sh->map, &node->node); - free(node->data); - free(node->name); - free(node); + if (sh->map.n == 0) { + return; + } + + for (i = 0; i <= sh->map.mask; i++) { + hn = sh->map.buckets[i]; + while (hn != NULL) { + node = CONTAINER_OF(hn, struct shash_node, node); + hn = hn->next; + free(node->data); + free(node->name); + free(node); + } + sh->map.buckets[i] = NULL; } + sh->map.n = 0; } bool