[ovs-dev] [PATCH 1/3] Optimise shash disposal
anton.ivanov at cambridgegreys.com
anton.ivanov at cambridgegreys.com
Fri Jul 31 09:23:21 UTC 2020
From: Anton Ivanov <anton.ivanov at 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 at 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
--
2.20.1
More information about the dev
mailing list