menu: initial work on hash table for labelshashtbl

Initial work on a proper hash table for labels and menu tags.  This
doesn't compile just yet.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>

5 files changed, 350 insertions, 63 deletions

diff --git a/com32/menu/crc64.c b/com32/menu/crc64.c
new file mode 100644
index 00000000..e3baaa42
--- /dev/null
+++ b/com32/menu/crc64.c
@@ -0,0 +1,41 @@
+#include <klibc/compiler.h>
+#include <inttypes.h>
+#include <ctype.h>
+
+static uint64_t crc64_tab[256];
+
+static void __constructor build_crc64_table(void)
+{
+	int i, j;
+	uint64_t c;
+	const uint64_t poly = UINT64_C(0x95ac9329ac4bc9b5);
+
+	for (i = 0; i < 256; i++) {
+		c = i;
+		for (j = 0; j < 8; j++) {
+			if (c & 1)
+				c = (c >> 1) & poly;
+			else
+				c = (c >> 1);
+		}
+		crc64_tab[i] = c;
+	}
+}
+
+uint64_t crc64(uint64_t crc, const char *str)
+{
+	uint8_t c;
+
+	while ((c = *str++) != 0)
+		crc = crc64_tab[(uint8_t)crc ^ c] ^ (crc >> 8);
+	return crc;
+}
+
+uint64_t crc64i(uint64_t crc, const char *str)
+{
+	uint8_t c;
+	
+	while ((c = *str++) != 0)
+		crc = crc64_tab[(uint8_t)crc ^ tolower(c)] ^ (crc >> 8);
+	return crc;
+}
diff --git a/com32/menu/hashtbl.c b/com32/menu/hashtbl.c
new file mode 100644
index 00000000..960425c5
--- /dev/null
+++ b/com32/menu/hashtbl.c
@@ -0,0 +1,145 @@
+/*
+ * hashtbl.c
+ *
+ * Efficient symbol hash table class.
+ */
+
+#include <inttypes.h>
+#include <string.h>
+#include <stdlib.h>
+#include "hashtbl.h"
+
+#define HASH_MAX_LOAD		2 /* Higher = more memory-efficient, slower */
+
+static struct hash_symbol **alloc_table(size_t newsize)
+{
+	return calloc(sizeof(struct hash_symbol *), newsize);
+}
+
+void hash_init(struct hash_table *head, size_t size)
+{
+	head->table    = alloc_table(size);
+	head->load     = 0;
+	head->size     = size;
+	head->max_load = size*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
+}
+
+/*
+ * Find an entry in a hash table.
+ *
+ * On failure, if "insert" is non-NULL, store data in that structure
+ * which can be used to insert that node using hash_add().
+ *
+ * WARNING: this data is only valid until the very next call of
+ * hash_add(); it cannot be "saved" to a later date.
+ *
+ * On success, return the hash_symbol pointer.
+ */
+struct hash_symbol *hash_find(struct hash_table *head, const char *key,
+			      struct hash_insert *insert)
+{
+	struct hash_symbol *np;
+	uint64_t hash = crc64(CRC64_INIT, key);
+	struct hash_symbol **tbl = head->table;
+	size_t mask = head->size-1;
+	size_t pos  = hash & mask;
+	size_t inc  = ((hash >> 32) & mask) | 1;	/* Always odd */
+
+	while ((np = tbl[pos])) {
+		if (hash == np->hash && !strcmp(key, np->key))
+			return np;
+		pos = (pos+inc) & mask;
+	}
+
+	/* Not found.  Store info for insert if requested. */
+	if (insert) {
+		insert->head  = head;
+		insert->hash  = hash;
+		insert->where = &tbl[pos];
+	}
+	return NULL;
+}
+
+/*
+ * Same as hash_find, but for case-insensitive hashing.
+ */
+struct hash_symbol *hash_findi(struct hash_table *head, const char *key,
+			       struct hash_insert *insert)
+{
+	struct hash_symbol *np;
+	uint64_t hash = crc64i(CRC64_INIT, key);
+	struct hash_symbol **tbl = head->table;
+	size_t mask = head->size-1;
+	size_t pos  = hash & mask;
+	size_t inc  = ((hash >> 32) & mask) | 1;	/* Always odd */
+
+	while ((np = tbl[pos])) {
+		if (hash == np->hash && !strcasecmp(key, np->key))
+			return np;
+		pos = (pos+inc) & mask;
+	}
+
+	/* Not found.  Store info for insert if requested. */
+	if (insert) {
+		insert->head  = head;
+		insert->hash  = hash;
+		insert->where = &tbl[pos];
+	}
+	return NULL;
+}
+
+/*
+ * Insert node.
+ */
+void hash_add(struct hash_insert *insert, struct hash_symbol *sym)
+{
+	struct hash_table *head = insert->head;
+	struct hash_symbol **np = insert->where;
+
+	/* Insert node.  We can always do this, even if we need to
+	   rebalance immediately after. */
+	sym->hash = insert->hash;
+	*np = sym;
+
+	if (++head->load > head->max_load) {
+		/* Need to expand the table */
+		size_t newsize = head->size << 1;
+		struct hash_symbol **newtbl = alloc_table(newsize);
+		size_t mask = newsize-1;
+		
+		if (head->table) {
+			struct hash_symbol **op, **xp;
+			size_t i, pos, inc;
+			uint64_t hash;
+			
+			/* Rebalance all the entries */
+			for (i = 0, op = head->table; i < head->size;
+			     i++, op++) {
+				if (*op) {
+					hash = (*op)->hash;
+					pos = hash & mask;
+					inc = ((hash >> 32) & mask) | 1;
+
+					while (*(xp = &newtbl[pos]))
+						pos = (pos+inc) & mask;
+					*xp = *op;
+				}
+			}
+			free(head->table);
+		}
+		head->table    = newtbl;
+		head->size     = newsize;
+		head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
+	}
+}
+
+/*
+ * Free the hash itself.  Doesn't free the data elements; use
+ * hash_iterate() to do that first, if needed.
+ */
+void hash_free(struct hash_table *head)
+{
+    void *p = head->table;
+    memset(head, 0, sizeof *head);
+    free(p);
+}
diff --git a/com32/menu/hashtbl.h b/com32/menu/hashtbl.h
new file mode 100644
index 00000000..7de892f5
--- /dev/null
+++ b/com32/menu/hashtbl.h
@@ -0,0 +1,49 @@
+/*
+ * hashtbl.h
+ *
+ * Efficient dictionary hash table class.
+ */
+
+#ifndef MENU_HASHTBL_H
+#define MENU_HASHTBL_H
+
+#include <inttypes.h>
+#include <stddef.h>
+
+/* This is expected to be embedded in a larger structure */
+struct hash_symbol {
+    uint64_t hash;
+    const char *key;
+};
+
+struct hash_table {
+	struct hash_symbol **table;
+	size_t load;
+	size_t size;
+	size_t max_load;
+};
+
+struct hash_insert {
+	uint64_t hash;
+	struct hash_table  *head;
+	struct hash_symbol **where;
+};
+
+uint64_t crc64(uint64_t crc, const char *string);
+uint64_t crc64i(uint64_t crc, const char *string);
+#define CRC64_INIT UINT64_C(0xffffffffffffffff)
+
+/* Some reasonable initial sizes... */
+#define HASH_SMALL	4
+#define HASH_MEDIUM	16
+#define HASH_LARGE	256
+
+void hash_init(struct hash_table *head, size_t size);
+struct hash_symbol *hash_find(struct hash_table *head, const char *string,
+			      struct hash_insert *insert);
+struct hash_symbol *hash_findi(struct hash_table *head, const char *string,
+			       struct hash_insert *insert);
+void hash_add(struct hash_insert *insert, struct hash_symbol *sym);
+void hash_free(struct hash_table *head);
+
+#endif /* MENU_HASHTBL_H */
diff --git a/com32/menu/menu.h b/com32/menu/menu.h
index 98b6fa9b..1cd70d5b 100644
--- a/com32/menu/menu.h
+++ b/com32/menu/menu.h
@@ -27,6 +27,7 @@
 #include <colortbl.h>
 #include <stdbool.h>
 #include "refstr.h"
+#include "hashtbl.h"
 
 #ifndef CLK_TCK
 # define CLK_TCK sysconf(_SC_CLK_TCK)
@@ -34,30 +35,27 @@
 
 struct menu;
 
-/* Note: the _UNRES variants must always be immediately after their
-   "normal" versions. */
 enum menu_action {
-  MA_NONE,			/* Undefined value */
+  MA_UNDEF,			/* Unresolved entry */
   MA_CMD,			/* Execute a command */
   MA_DISABLED,			/* Disabled menu entry */
   MA_SUBMENU,			/* This is a submenu entry */
   MA_GOTO,			/* Go to another menu */
-  MA_GOTO_UNRES,		/* Unresolved go to */
   MA_QUIT,			/* Quit to CLI */
   MA_EXIT,			/* Exit to higher-level menu */
-  MA_EXIT_UNRES,		/* Unresolved exit */
 };
 
 struct menu_entry {
+  struct hash_symbol l;		/* Label and hash entry */
   struct menu *menu;		/* Parent menu */
   const char *displayname;
-  const char *label;
   const char *passwd;
   char *helptext;
   const char *cmdline;
   struct menu *submenu;
-  struct menu_entry *next;	/* Linked list of all labels across menus */
+  struct menu_entry *menuref;	/* Reference for GOTO or EXIT */
   int entry;			/* Entry number inside menu */
+  int collision;		/* Collision counter (for synthetic labels) */
   enum menu_action action;
   unsigned char hotkey;
   bool save;			/* Save this entry if selected */
@@ -136,8 +134,7 @@ struct fkey_help {
 };
 
 struct menu {
-  struct menu *next;		/* Linked list of all menus */
-  const char *label;		/* Goto label for this menu */
+  struct hash_symbol l;		/* Label and hash table entry */
   struct menu *parent;
   struct menu_entry *parent_entry; /* Entry for self in parent */
 
@@ -152,6 +149,7 @@ struct menu {
   int defentry;
   int timeout;
 
+  bool defined;			/* This menu is actually defined... */
   bool allowedit;
   bool save;			/* MENU SAVE default for this menu */
 
diff --git a/com32/menu/readconfig.c b/com32/menu/readconfig.c
index 376d8181..db80285d 100644
--- a/com32/menu/readconfig.c
+++ b/com32/menu/readconfig.c
@@ -24,6 +24,7 @@
 #include <syslinux/config.h>
 
 #include "menu.h"
+#include "hashtbl.h"
 
 /* Empty refstring */
 const char *empty_string;
@@ -74,20 +75,67 @@ const char * const kernel_types[] = {
   NULL
 };
 
+static struct hash_table label_hash;
+static struct hash_table menu_hash;
+
 /*
- * Search the list of all menus for a specific label
+ * Set up or return a reference to a specific label.
+ * Consumes a reference count.
  */
-static struct menu *
-find_menu(const char *label)
+static struct menu_entry *label_ref(const char *label)
+{
+  struct hash_symbol *hs;
+  struct menu_entry *me;
+  struct hash_insert hi;
+
+  hs = hash_find(&label_hash, label, &hi);
+  if (hs) {
+    refstr_put(label);
+    return container_of(hs, struct menu_entry, l);
+  }
+
+  /* Unresolved reference; create a placeholder entry. */
+  me = zalloc(sizeof *me);
+  me->l.key = label;		/* Retains the reference */
+
+  hash_add(&hi, me);
+  return me;
+}
+
+/*
+ * Set up or return a reference to a specific menu.
+ * Consumes a reference count.
+ */
+static struct menu *menu_ref(const char *label)
 {
+  struct hash_symbol *hs;
   struct menu *m;
+  struct hash_insert hi;
 
-  for (m = menu_list; m; m = m->next) {
-    if (!strcmp(label, m->label))
-      return m;
+  hs = hash_find(&menu_hash, label, &hi);
+  if (hs) {
+    refstr_put(label);
+    return container_of(hs, struct menu, l);
   }
 
-  return NULL;
+  /* Unresolved reference; create a placeholder entry. */
+  m = zalloc(sizeof *m);
+  m->l.key = label;		/* Retains the reference */
+
+  hash_add(&hi, m);
+  return m;
+}
+
+/*
+ * Search the list of all menus for a specific label
+ */
+static struct menu *
+find_menu(const char *label)
+{
+  struct menu **mp;
+
+  mp = (struct menu **)hash_find(&menu_hash, label, NULL);
+  return mp ? *mp : NULL;
 }
 
 #define MAX_LINE 4096
@@ -156,17 +204,23 @@ static struct menu * new_menu(struct menu *parent,
 {
   struct menu *m = calloc(1, sizeof(struct menu));
   int i;
+  struct hash_insert hi;
 
   m->label = label;
   m->title = refstr_get(empty_string);
+  
+  if (!hash_find(&menu_hash, label, &hi))
+    hash_add(&hi, label, m);
+
+  /* We always have a parent entry for bookkeeping purposes */
+  m->parent_entry = parent_entry;
+  parent_entry->action = MA_SUBMENU;
+  parent_entry->submenu = m;
 
   if (parent) {
-    /* Submenu */
+    /* An actual submenu */
     m->parent = parent;
-    m->parent_entry = parent_entry;
-    parent_entry->action = MA_SUBMENU;
-    parent_entry->submenu = m;
-
+  
     for (i = 0; i < MSG_COUNT; i++)
       m->messages[i] = refstr_get(parent->messages[i]);
 
@@ -221,7 +275,7 @@ struct labeldata {
   unsigned int menuindent;
   enum menu_action action;
   int save;
-  struct menu *submenu;
+  struct menu_entry *menuref;
 };
 
 /* Menu currently being parsed */
@@ -240,9 +294,10 @@ clear_label_data(struct labeldata *ld)
   memset(ld, 0, sizeof *ld);
 }
 
-static struct menu_entry *new_entry(struct menu *m)
+static struct menu_entry *new_entry(struct menu *m, const char *label)
 {
   struct menu_entry *me;
+  const char *nl;
 
   if (m->nentries >= m->nentries_space) {
     if (!m->nentries_space)
@@ -254,9 +309,17 @@ static struct menu_entry *new_entry(struct menu *m)
 			      sizeof(struct menu_entry *));
   }
 
-  me = calloc(1, sizeof(struct menu_entry));
+  refstr_get(label);
+  while (me = label_ref(label), me->action != MA_UNDEF) {
+    /* Duplicate label, generate synthetic name that can't collide */
+    rsprintf(&nl, "%s\n%d", label, ++me->collision);
+    refstr_put(label);
+    label = nl;
+  }
+
   me->menu = m;
   me->entry = m->nentries;
+  me->label = label;
   m->menu_entries[m->nentries++] = me;
   *all_entries_end = me;
   all_entries_end = &me->next;
@@ -298,7 +361,7 @@ record(struct menu *m, struct labeldata *ld, const char *append)
     const char *a;
     char *s;
 
-    me = new_entry(m);
+    me = new_entry(m, ld->label);
 
     me->displayname = ld->menulabel
       ? refstr_get(ld->menulabel) : refstr_get(ld->label);
@@ -364,14 +427,9 @@ record(struct menu *m, struct labeldata *ld, const char *append)
       }
       break;
 
-    case MA_GOTO_UNRES:
-    case MA_EXIT_UNRES:
-      me->cmdline = refstr_get(ld->kernel);
-      break;
-
     case MA_GOTO:
     case MA_EXIT:
-      me->submenu = ld->submenu;
+      me->menuref = ld->menuref;
       break;
 
     default:
@@ -404,8 +462,9 @@ static struct menu *end_submenu(void)
 
 static struct menu_entry *find_label(const char *str)
 {
-  const char *p;
+  const char *p, op;
   struct menu_entry *me;
+  struct menu_entry **lrp;
   int pos;
 
   p = str;
@@ -413,14 +472,12 @@ static struct menu_entry *find_label(const char *str)
     p++;
 
   /* p now points to the first byte beyond the kernel name */
-  pos = p-str;
-
-  for (me = all_entries; me; me = me->next) {
-    if (!strncmp(str, me->label, pos) && !me->label[pos])
-      return me;
-  }
+  op = *p;
+  *(char *)p = '\0';		/* Ugly, but works in our environment */
+  lrp = hash_find(&label_hash, str, NULL);
+  *(char *)p = op;
 
-  return NULL;
+  return lrp ? *lrp : NULL;
 }
 
 static const char *unlabel(const char *str)
@@ -429,25 +486,19 @@ static const char *unlabel(const char *str)
   const char *p;
   const char *q;
   struct menu_entry *me;
-  int pos;
+  
+  me = find_label(str);
+  if (!me)
+    return str;
 
+  /* Found matching label */
   p = str;
   while ( *p && !my_isspace(*p) )
     p++;
 
-  /* p now points to the first byte beyond the kernel name */
-  pos = p-str;
-
-  for (me = all_entries; me; me = me->next) {
-    if (!strncmp(str, me->label, pos) && !me->label[pos]) {
-      /* Found matching label */
-      rsprintf(&q, "%s%s", me->cmdline, p);
-      refstr_put(str);
-      return q;
-    }
-  }
-
-  return str;
+  rsprintf(&q, "%s%s", me->cmdline, p);
+  refstr_put(str);
+  return q;
 }
 
 static const char *
@@ -812,21 +863,21 @@ static void parse_config_file(FILE *f)
 	  ld.action = MA_QUIT;
       } else if ( looking_at(p, "goto") ) {
 	if (ld.label) {
-	  ld.action = MA_GOTO_UNRES;
-	  refstr_put(ld.kernel);
-	  ld.kernel = refstrdup(skipspace(p+4));
+	  ld.action = MA_GOTO;
+	  if (*p) {
+	    ld.menuref = label_ref(skipspace(p+4));
+	  }
 	}
       } else if ( looking_at(p, "exit") ) {
 	p = skipspace(p+4);
-	if (ld.label && m->parent) {
+	if (ld.label) {
+	  ld.action = MA_EXIT;
 	  if (*p) {
 	    /* This is really just a goto, except for the marker */
-	    ld.action = MA_EXIT_UNRES;
-	    refstr_put(ld.kernel);
-	    ld.kernel = refstrdup(p);
-	  } else {
-	    ld.action = MA_EXIT;
-	    ld.submenu = m->parent;
+	    ld.menuref = label_ref(p);
+	  } else if (m->parent) {
+	    /* True exit */
+	    ld.menuref = m->parent->parententry;
 	  }
 	}
       } else if ( looking_at(p, "start") ) {
@@ -1011,6 +1062,9 @@ void parse_configs(char **argv)
 
   empty_string = refstrdup("");
 
+  hash_init(&label_hash, HASH_MEDIUM);
+  hash_init(&menu_hash,  HASH_SMALL);
+
   /* Initialize defaults for the root and hidden menus */
   hide_menu = new_menu(NULL, NULL, refstrdup(".hidden"));
   root_menu = new_menu(NULL, NULL, refstrdup(".top"));