Improve kconfig symbol hashing

Commit Message

Andi Kleen Jan. 13, 2010, 4:02 p.m. UTC

None

Patch

Index: linux-2.6.33-rc3-ak/scripts/kconfig/symbol.c
===================================================================
--- linux-2.6.33-rc3-ak.orig/scripts/kconfig/symbol.c
+++ linux-2.6.33-rc3-ak/scripts/kconfig/symbol.c
@@ -651,12 +651,20 @@  bool sym_is_changable(struct symbol *sym
 	return sym->visible > sym->rev_dep.tri;
 }
 
+static unsigned strhash(const char *s)
+{
+	/* fnv32 hash */
+	unsigned hash = 2166136261U;
+	for (; *s; s++)
+		hash = (hash ^ *s) * 0x01000193;
+	return hash;
+}
+
 struct symbol *sym_lookup(const char *name, int flags)
 {
 	struct symbol *symbol;
-	const char *ptr;
 	char *new_name;
-	int hash = 0;
+	int hash;
 
 	if (name) {
 		if (name[0] && !name[1]) {
@@ -666,12 +674,11 @@  struct symbol *sym_lookup(const char *na
 			case 'n': return &symbol_no;
 			}
 		}
-		for (ptr = name; *ptr; ptr++)
-			hash += *ptr;
-		hash &= 0xff;
+		hash = strhash(name) % SYMBOL_HASHSIZE;
 
 		for (symbol = symbol_hash[hash]; symbol; symbol = symbol->next) {
-			if (!strcmp(symbol->name, name) &&
+			if (symbol->name &&
+			    !strcmp(symbol->name, name) &&
 			    (flags ? symbol->flags & flags
 				   : !(symbol->flags & (SYMBOL_CONST|SYMBOL_CHOICE))))
 				return symbol;
@@ -679,7 +686,7 @@  struct symbol *sym_lookup(const char *na
 		new_name = strdup(name);
 	} else {
 		new_name = NULL;
-		hash = 256;
+		hash = 0;
 	}
 
 	symbol = malloc(sizeof(*symbol));
@@ -703,7 +710,6 @@  struct symbol *sym_lookup(const char *na
 struct symbol *sym_find(const char *name)
 {
 	struct symbol *symbol = NULL;
-	const char *ptr;
 	int hash = 0;
 
 	if (!name)
@@ -716,12 +722,11 @@  struct symbol *sym_find(const char *name
 		case 'n': return &symbol_no;
 		}
 	}
-	for (ptr = name; *ptr; ptr++)
-		hash += *ptr;
-	hash &= 0xff;
+	hash = strhash(name) % SYMBOL_HASHSIZE;
 
 	for (symbol = symbol_hash[hash]; symbol; symbol = symbol->next) {
-		if (!strcmp(symbol->name, name) &&
+		if (symbol->name &&
+		    !strcmp(symbol->name, name) &&
 		    !(symbol->flags & SYMBOL_CONST))
 				break;
 	}
Index: linux-2.6.33-rc3-ak/scripts/kconfig/zconf.tab.c_shipped
===================================================================
--- linux-2.6.33-rc3-ak.orig/scripts/kconfig/zconf.tab.c_shipped
+++ linux-2.6.33-rc3-ak/scripts/kconfig/zconf.tab.c_shipped
@@ -104,7 +104,7 @@  static void zconf_error(const char *err,
 static void zconferror(const char *err);
 static bool zconf_endtoken(struct kconf_id *id, int starttoken, int endtoken);
 
-struct symbol *symbol_hash[257];
+struct symbol *symbol_hash[SYMBOL_HASHSIZE];
 
 static struct menu *current_menu, *current_entry;
 
Index: linux-2.6.33-rc3-ak/scripts/kconfig/zconf.y
===================================================================
--- linux-2.6.33-rc3-ak.orig/scripts/kconfig/zconf.y
+++ linux-2.6.33-rc3-ak/scripts/kconfig/zconf.y
@@ -27,7 +27,7 @@  static void zconf_error(const char *err,
 static void zconferror(const char *err);
 static bool zconf_endtoken(struct kconf_id *id, int starttoken, int endtoken);
 
-struct symbol *symbol_hash[257];
+struct symbol *symbol_hash[SYMBOL_HASHSIZE];
 
 static struct menu *current_menu, *current_entry;
 
Index: linux-2.6.33-rc3-ak/scripts/kconfig/expr.h
===================================================================
--- linux-2.6.33-rc3-ak.orig/scripts/kconfig/expr.h
+++ linux-2.6.33-rc3-ak/scripts/kconfig/expr.h
@@ -86,7 +86,7 @@  struct symbol {
 	struct expr_value rev_dep;
 };
 
-#define for_all_symbols(i, sym) for (i = 0; i < 257; i++) for (sym = symbol_hash[i]; sym; sym = sym->next) if (sym->type != S_OTHER)
+#define for_all_symbols(i, sym) for (i = 0; i < SYMBOL_HASHSIZE; i++) for (sym = symbol_hash[i]; sym; sym = sym->next) if (sym->type != S_OTHER)
 
 #define SYMBOL_CONST      0x0001  /* symbol is const */
 #define SYMBOL_CHECK      0x0008  /* used during dependency checking */
@@ -108,8 +108,7 @@  struct symbol {
 #define SYMBOL_DEF4       0x80000  /* symbol.def[S_DEF_4] is valid */
 
 #define SYMBOL_MAXLENGTH	256
-#define SYMBOL_HASHSIZE		257
-#define SYMBOL_HASHMASK		0xff
+#define SYMBOL_HASHSIZE		9973
 
 /* A property represent the config options that can be associated
  * with a config "symbol".