We get a lot of entries there, and lookups are done many, many times. This gives a significant performance improvement.
Signed-off-by: Timo Teräs <[email protected]> --- modutils/modprobe.c | 13 ++++++++++--- 1 files changed, 10 insertions(+), 3 deletions(-) diff --git a/modutils/modprobe.c b/modutils/modprobe.c index 678f4be..b3767ac 100644 --- a/modutils/modprobe.c +++ b/modutils/modprobe.c @@ -157,8 +157,10 @@ struct module_entry { /* I'll call it ME. */ llist_t *deps; /* strings. modules we depend on */ }; +#define DB_HASH_SIZE 256 + struct globals { - llist_t *db; /* MEs of all modules ever seen (caching for speed) */ + llist_t *db[DB_HASH_SIZE]; /* MEs of all modules ever seen (caching for speed) */ llist_t *probes; /* MEs of module(s) requested on cmdline */ char *cmdline_mopts; /* module options from cmdline */ int num_unresolved_deps; @@ -195,9 +197,14 @@ static struct module_entry *helper_get_module(const char *module, int create) char modname[MODULE_NAME_LEN]; struct module_entry *e; llist_t *l; + unsigned int hash = 5381, i; filename2modname(module, modname); - for (l = G.db; l != NULL; l = l->link) { + for (i = 0; modname[i]; i++) + hash = ((hash << 5) + hash) + modname[i]; + hash %= DB_HASH_SIZE; + + for (l = G.db[hash]; l != NULL; l = l->link) { e = (struct module_entry *) l->data; if (strcmp(e->modname, modname) == 0) return e; @@ -207,7 +214,7 @@ static struct module_entry *helper_get_module(const char *module, int create) e = xzalloc(sizeof(*e)); e->modname = xstrdup(modname); - llist_add_to(&G.db, e); + llist_add_to(&G.db[hash], e); return e; } -- 1.7.1 _______________________________________________ busybox mailing list [email protected] http://lists.busybox.net/mailman/listinfo/busybox
