Added dynamic perfect hash for opcodes

ok marco@

3 files changed, 33 insertions, 10 deletions

diff --git a/sys/dev/acpi/acpi.c b/sys/dev/acpi/acpi.c
index 579e87c52a1..5dd86499ec4 100644
--- a/sys/dev/acpi/acpi.c
+++ b/sys/dev/acpi/acpi.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: acpi.c,v 1.80 2007/02/18 01:37:49 marco Exp $	*/
+/*	$OpenBSD: acpi.c,v 1.81 2007/02/18 02:25:05 jordan Exp $	*/
 /*
  * Copyright (c) 2005 Thorsten Lockert <tholo@sigmasoft.com>
  * Copyright (c) 2005 Jordan Hargrave <jordan@openbsd.org>
@@ -350,6 +350,7 @@ acpi_attach(struct device *parent, struct device *self, void *aux)
 	sc->sc_iot = aaa->aaa_iot;
 	sc->sc_memt = aaa->aaa_memt;
 
+
 	if (acpi_map(aaa->aaa_pbase, sizeof(struct acpi_rsdp), &handle)) {
 		printf(": can't map memory\n");
 		return;
@@ -407,6 +408,9 @@ acpi_attach(struct device *parent, struct device *self, void *aux)
 	}
 #endif
 
+	/* Create opcode hashtable */
+	aml_hashopcodes();
+
 	acpi_enabled=1;
 
 	/* Create Default AML objects */
diff --git a/sys/dev/acpi/dsdt.c b/sys/dev/acpi/dsdt.c
index 7ef26704a29..c1b3973933d 100644
--- a/sys/dev/acpi/dsdt.c
+++ b/sys/dev/acpi/dsdt.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: dsdt.c,v 1.79 2007/02/13 04:40:00 jordan Exp $ */
+/* $OpenBSD: dsdt.c,v 1.80 2007/02/18 02:25:05 jordan Exp $ */
 /*
  * Copyright (c) 2005 Jordan Hargrave <jordan@openbsd.org>
  *
@@ -95,6 +95,9 @@ void			aml_gasio(struct acpi_softc *, int, uint64_t, uint64_t,
 
 struct aml_opcode	*aml_findopcode(int);
 
+#define acpi_os_malloc(sz) _acpi_os_malloc(sz, __FUNCTION__, __LINE__)
+#define acpi_os_free(ptr)  _acpi_os_free(ptr, __FUNCTION__, __LINE__)
+
 void			*_acpi_os_malloc(size_t, const char *, int);
 void			_acpi_os_free(void *, const char *, int);
 void			acpi_sleep(int);
@@ -136,10 +139,16 @@ struct aml_value *aml_parsematch(struct aml_scope *, int, struct aml_value *);
 struct aml_value *aml_parseref(struct aml_scope *, int, struct aml_value *);
 struct aml_value *aml_parsestring(struct aml_scope *, int, struct aml_value *);
 
+/* Perfect Hash key */
+#define HASH_OFF		6904
+#define HASH_SIZE		179
+#define HASH_KEY(k)		(((k) ^ HASH_OFF) % HASH_SIZE)
+
 /*
  * XXX this array should be sorted, and then aml_findopcode() should
  * do a binary search
  */
+struct aml_opcode **aml_ophash;
 struct aml_opcode aml_table[] = {
 	/* Simple types */
 	{ AMLOP_ZERO,		"Zero",		"c",	aml_parsesimple },
@@ -314,14 +323,25 @@ void _aml_die(const char *fn, int line, const char *fmt, ...)
 	panic("aml_die %s:%d", fn, line);
 }
 
-struct aml_opcode *
-aml_findopcode(int opcode)
+void
+aml_hashopcodes(void)
 {
 	int i;
 
+	/* Dynamically allocate hash table */
+	aml_ophash = (struct aml_opcode **)acpi_os_malloc(HASH_SIZE*sizeof(struct aml_opcode *));
 	for (i = 0; i < sizeof(aml_table) / sizeof(aml_table[0]); i++)
-		if (aml_table[i].opcode == opcode)
-			return &aml_table[i];
+		aml_ophash[HASH_KEY(aml_table[i].opcode)] = &aml_table[i];
+}
+
+struct aml_opcode *
+aml_findopcode(int opcode)
+{
+	struct aml_opcode *hop;
+
+	hop = aml_ophash[HASH_KEY(opcode)];
+	if (hop && hop->opcode == opcode)
+		return hop;
 	return NULL;
 }
 
@@ -388,9 +408,6 @@ struct aml_notify_head aml_notify_list =
  *  @@@: Memory management functions
  */
 
-#define acpi_os_malloc(sz) _acpi_os_malloc(sz, __FUNCTION__, __LINE__)
-#define acpi_os_free(ptr)  _acpi_os_free(ptr, __FUNCTION__, __LINE__)
-
 long acpi_nalloc;
 
 struct acpi_memblock {
diff --git a/sys/dev/acpi/dsdt.h b/sys/dev/acpi/dsdt.h
index 9b5e0641fbc..89c76138b15 100644
--- a/sys/dev/acpi/dsdt.h
+++ b/sys/dev/acpi/dsdt.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: dsdt.h,v 1.25 2007/02/06 18:56:31 jordan Exp $ */
+/* $OpenBSD: dsdt.h,v 1.26 2007/02/18 02:25:05 jordan Exp $ */
 /*
  * Copyright (c) 2005 Marco Peereboom <marco@openbsd.org>
  *
@@ -196,4 +196,6 @@ void			aml_walknodes(struct aml_node *, int,
 void			aml_postparse(void);
 void			acpi_poll_notify(void);
 
+void			aml_hashopcodes(void);
+
 #endif /* __DEV_ACPI_DSDT_H__ */