From: Anton Ivanov <[email protected]> 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 <[email protected]> --- 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 -- 2.20.1 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
