aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@linux.intel.com>2009-04-21 16:25:49 -0700
committerH. Peter Anvin <hpa@linux.intel.com>2009-04-21 16:25:49 -0700
commitd842a813847fbb5cce3c152779a279395f33410f (patch)
treebec841f501902277193bb99e5ec5b1b0f4d1b23b
parent31937531087fb47aa4a3a218e8114b32176f8683 (diff)
downloadsyslinux-hashtbl.tar.gz
syslinux-hashtbl.tar.xz
syslinux-hashtbl.zip
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>
-rw-r--r--com32/menu/crc64.c41
-rw-r--r--com32/menu/hashtbl.c145
-rw-r--r--com32/menu/hashtbl.h49
-rw-r--r--com32/menu/menu.h16
-rw-r--r--com32/menu/readconfig.c162
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"));