From 980c9e198f1c5563380bed2a2672e592edf9efaa Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sat, 3 Feb 2024 00:58:23 +0900 Subject: kconfig: convert linked list of files to hash table Currently, a linked list is used to keep track of all the Kconfig files that have ever been parsed. Every time the "source" statement is encountered, the linked list is traversed to check if the file has been opened before. This prevents the same file from being recorded in include/config/auto.conf.cmd again. Given 1500+ Kconfig files parsed, a hashtable is now a more optimal data structure. By the way, you may wonder why we check this in the first place. It matters only when the same file is included multiple times. In old days, such a use case was forbidden, but commit f094f8a1b273 ("kconfig: allow multiple inclusion of the same file") provided a bit more flexibility. Of course, it is almost hypothetical... Signed-off-by: Masahiro Yamada --- scripts/kconfig/util.c | 20 +++++++++++--------- 1 file changed, 11 insertions(+), 9 deletions(-) (limited to 'scripts') diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index d6172f2f64c9..439c131b424e 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -7,6 +7,8 @@ #include #include #include + +#include "hashtable.h" #include "lkc.h" unsigned int strhash(const char *s) @@ -19,32 +21,32 @@ unsigned int strhash(const char *s) return hash; } +/* hash table of all parsed Kconfig files */ +static HASHTABLE_DEFINE(file_hashtable, 1U << 11); + struct file { - struct file *next; + struct hlist_node node; char name[]; }; -static struct file *file_list; - /* file already present in list? If not add it */ const char *file_lookup(const char *name) { struct file *file; size_t len; + int hash = strhash(name); - for (file = file_list; file; file = file->next) { - if (!strcmp(name, file->name)) { + hash_for_each_possible(file_hashtable, file, node, hash) + if (!strcmp(name, file->name)) return file->name; - } - } len = strlen(name); file = xmalloc(sizeof(*file) + len + 1); memset(file, 0, sizeof(*file)); memcpy(file->name, name, len); file->name[len] = '\0'; - file->next = file_list; - file_list = file; + + hash_add(file_hashtable, &file->node, hash); str_printf(&autoconf_cmd, "\t%s \\\n", name); -- cgit v1.2.3