From 38e70330ee6c6b8ddc805ed2a0eb45531166b658 Mon Sep 17 00:00:00 2001 From: Phil Sutter Date: Fri, 27 Sep 2019 14:24:40 +0200 Subject: set: Export nftnl_set_list_lookup_byname() Rename and optimize internal function nftnl_set_lookup() for external use. Just like with nftnl_chain_list, use a hash table for fast set name lookups. Signed-off-by: Phil Sutter Acked-by: Pablo Neira Ayuso --- src/libnftnl.map | 4 ++++ src/set.c | 53 ++++++++++++++++++++++++++++++++++------------------- 2 files changed, 38 insertions(+), 19 deletions(-) (limited to 'src') diff --git a/src/libnftnl.map b/src/libnftnl.map index 3c6f863..3ddb946 100644 --- a/src/libnftnl.map +++ b/src/libnftnl.map @@ -351,3 +351,7 @@ LIBNFTNL_12 { nftnl_chain_list_lookup_byname; nftnl_rule_lookup_byindex; } LIBNFTNL_11; + +LIBNFTNL_13 { + nftnl_set_list_lookup_byname; +} LIBNFTNL_12; diff --git a/src/set.c b/src/set.c index d1bdb16..e6db725 100644 --- a/src/set.c +++ b/src/set.c @@ -715,20 +715,26 @@ void nftnl_set_elem_add(struct nftnl_set *s, struct nftnl_set_elem *elem) list_add_tail(&elem->head, &s->element_list); } +#define SET_NAME_HSIZE 512 + struct nftnl_set_list { struct list_head list; + struct hlist_head name_hash[SET_NAME_HSIZE]; }; EXPORT_SYMBOL(nftnl_set_list_alloc); struct nftnl_set_list *nftnl_set_list_alloc(void) { struct nftnl_set_list *list; + int i; list = calloc(1, sizeof(struct nftnl_set_list)); if (list == NULL) return NULL; INIT_LIST_HEAD(&list->list); + for (i = 0; i < SET_NAME_HSIZE; i++) + INIT_HLIST_HEAD(&list->name_hash[i]); return list; } @@ -740,6 +746,7 @@ void nftnl_set_list_free(struct nftnl_set_list *list) list_for_each_entry_safe(s, tmp, &list->list, head) { list_del(&s->head); + hlist_del(&s->hnode); nftnl_set_free(s); } xfree(list); @@ -751,15 +758,31 @@ int nftnl_set_list_is_empty(const struct nftnl_set_list *list) return list_empty(&list->list); } +static uint32_t djb_hash(const char *key) +{ + uint32_t i, hash = 5381; + + for (i = 0; i < strlen(key); i++) + hash = ((hash << 5) + hash) + key[i]; + + return hash; +} + EXPORT_SYMBOL(nftnl_set_list_add); void nftnl_set_list_add(struct nftnl_set *s, struct nftnl_set_list *list) { + int key = djb_hash(s->name) % SET_NAME_HSIZE; + + hlist_add_head(&s->hnode, &list->name_hash[key]); list_add(&s->head, &list->list); } EXPORT_SYMBOL(nftnl_set_list_add_tail); void nftnl_set_list_add_tail(struct nftnl_set *s, struct nftnl_set_list *list) { + int key = djb_hash(s->name) % SET_NAME_HSIZE; + + hlist_add_head(&s->hnode, &list->name_hash[key]); list_add_tail(&s->head, &list->list); } @@ -767,6 +790,7 @@ EXPORT_SYMBOL(nftnl_set_list_del); void nftnl_set_list_del(struct nftnl_set *s) { list_del(&s->head); + hlist_del(&s->hnode); } EXPORT_SYMBOL(nftnl_set_list_foreach); @@ -837,28 +861,19 @@ void nftnl_set_list_iter_destroy(const struct nftnl_set_list_iter *iter) xfree(iter); } -static struct nftnl_set *nftnl_set_lookup(const char *this_set_name, - struct nftnl_set_list *set_list) +EXPORT_SYMBOL(nftnl_set_list_lookup_byname); +struct nftnl_set * +nftnl_set_list_lookup_byname(struct nftnl_set_list *set_list, const char *set) { - struct nftnl_set_list_iter *iter; + int key = djb_hash(set) % SET_NAME_HSIZE; + struct hlist_node *n; struct nftnl_set *s; - const char *set_name; - - iter = nftnl_set_list_iter_create(set_list); - if (iter == NULL) - return NULL; - s = nftnl_set_list_iter_cur(iter); - while (s != NULL) { - set_name = nftnl_set_get_str(s, NFTNL_SET_NAME); - if (strcmp(this_set_name, set_name) == 0) - break; - - s = nftnl_set_list_iter_next(iter); + hlist_for_each_entry(s, n, &set_list->name_hash[key], hnode) { + if (!strcmp(set, s->name)) + return s; } - nftnl_set_list_iter_destroy(iter); - - return s; + return NULL; } int nftnl_set_lookup_id(struct nftnl_expr *e, @@ -871,7 +886,7 @@ int nftnl_set_lookup_id(struct nftnl_expr *e, if (set_name == NULL) return 0; - s = nftnl_set_lookup(set_name, set_list); + s = nftnl_set_list_lookup_byname(set_list, set_name); if (s == NULL) return 0; -- cgit v1.2.3