From ce4a5fe02aec3606740195e334f3dd3a34d7857d Mon Sep 17 00:00:00 2001
From: Peter Johnson <peter@tortall.net>
Date: Mon, 26 Nov 2001 17:37:09 +0000
Subject: [PATCH] Switch from using ternary tree to Hash Array Mapped Trie
 (HAMT), which has *much* less overhead. XXX: current implementation of HAMT
 is *not* portable due to pointer alignment restrictions (it uses the LSB of a
 pointer to store a flag).  Need to write a portable (if not so
 space-efficient) equivalent.

svn path=/trunk/yasm/; revision=363
---
 libyasm/hamt.c    | 354 ++++++++++++++++++++++++++++++++++++++++++++++
 libyasm/hamt.h    |  62 ++++++++
 libyasm/linemgr.c |  34 +++--
 libyasm/symrec.c  |  83 ++++++-----
 splint.sh         |   2 +-
 src/Makefile.am   |   4 +-
 src/globals.c     |  34 +++--
 src/hamt.c        | 354 ++++++++++++++++++++++++++++++++++++++++++++++
 src/hamt.h        |  62 ++++++++
 src/lclint.sh     |   2 +-
 src/linemgr.c     |  34 +++--
 src/symrec.c      |  83 ++++++-----
 src/ternary.c     | 191 -------------------------
 src/ternary.h     |  60 --------
 14 files changed, 981 insertions(+), 378 deletions(-)
 create mode 100644 libyasm/hamt.c
 create mode 100644 libyasm/hamt.h
 create mode 100644 src/hamt.c
 create mode 100644 src/hamt.h
 delete mode 100644 src/ternary.c
 delete mode 100644 src/ternary.h

diff --git a/libyasm/hamt.c b/libyasm/hamt.c
new file mode 100644
index 00000000..eb4df1f3
--- /dev/null
+++ b/libyasm/hamt.c
@@ -0,0 +1,354 @@
+/*
+ * Hash Array Mapped Trie (HAMT) implementation
+ *
+ *  Copyright (C) 2001  Peter Johnson
+ *
+ *  Based on the paper "Ideal Hash Tries" by Phil Bagwell [2000].
+ *  One algorithmic change from that described in the paper: we use the LSB's
+ *  of the key to index the root table and move upward in the key rather than
+ *  use the MSBs as described in the paper.  The LSBs have more entropy.
+ *
+ *  This file is part of YASM.
+ *
+ *  YASM is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  YASM is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+#include "util.h"
+/*@unused@*/ RCSID("$IdPath$");
+
+#include "errwarn.h"
+#include "hamt.h"
+
+typedef struct HAMTEntry {
+    SLIST_ENTRY(HAMTEntry) next;	/* next hash table entry */
+    /*@dependent@*/ const char *str;	/* string being hashed */
+    /*@owned@*/ void *data;		/* data pointer being stored */
+} HAMTEntry;
+
+typedef struct HAMTNode {
+    unsigned long BitMapKey;		/* 32 bits, bitmap or hash key */
+    void *BaseValue;			/* Base of HAMTNode list or value */
+} HAMTNode;
+
+struct HAMT {
+    SLIST_HEAD(HAMTEntryHead, HAMTEntry) entries;
+    HAMTNode *root;
+};
+
+/* XXX make a portable version of this.  This depends on the pointer being
+ * 4 or 2-byte aligned (as it uses the LSB of the pointer variable to store
+ * the subtrie flag!
+ */
+#define IsSubTrie(n)		((unsigned long)((n)->BaseValue) & 1)
+#define SetSubTrie(n, v)	do {				\
+	if ((unsigned long)(v) & 1)				\
+	    InternalError(_("Subtrie is seen as subtrie before flag is set (misaligned?)"));	\
+	(n)->BaseValue = (void *)((unsigned long)(v) | 1);	\
+    } while (0)
+#define GetSubTrie(n)		(HAMTNode *)((unsigned long)((n)->BaseValue)&~1UL)
+
+/* Bit-counting */
+#define SK5	0x55555555
+#define SK3	0x33333333
+#define SKF0	0x0F0F0F0F
+#define BitCount(d, s)		do {		\
+	d = s;					\
+	d -= (d>>1) & SK5;			\
+	d = (d & SK3) + ((d>>2) & SK3);		\
+	d = (d & SKF0) + ((d>>4) & SKF0);	\
+	d += d>>16;				\
+	d += d>>8;				\
+    } while (0)
+
+static unsigned long
+HashKey(const char *key)
+{
+    unsigned long a=31415, b=27183, vHash;
+    for (vHash=0; *key; key++, a*=b)
+	vHash = a*vHash + *key;
+    return vHash;
+}
+
+static unsigned long
+ReHashKey(const char *key, int Level)
+{
+    unsigned long a=31415, b=27183, vHash;
+    for (vHash=0; *key; key++, a*=b)
+	vHash = a*vHash*(unsigned long)Level + *key;
+    return vHash;
+}
+
+/*@-compdef -nullret@*/
+HAMT *
+HAMT_new(void)
+{
+    HAMT *hamt;
+    int i;
+
+    hamt = xmalloc(sizeof(HAMT));
+    SLIST_INIT(&hamt->entries);
+    hamt->root = xmalloc(32*sizeof(HAMTNode));
+
+    for (i=0; i<32; i++)
+	hamt->root[i].BaseValue = NULL;
+
+    return hamt;
+}
+/*@=compdef =nullret@*/
+
+static void
+HAMT_delete_trie(HAMTNode *node)
+{
+    if (IsSubTrie(node)) {
+	unsigned long i, Size;
+
+	/* Count total number of bits in bitmap to determine size */
+	BitCount(Size, node->BitMapKey);
+	Size &= 0x1F;	/* Clamp to <32 */
+
+	for (i=0; i<Size; i++)
+	    HAMT_delete_trie(&(GetSubTrie(node))[i]);
+	xfree(GetSubTrie(node));
+    }
+}
+
+void
+HAMT_delete(HAMT *hamt, void (*deletefunc) (/*@keep@*/ void *data))
+{
+    int i;
+
+    /* delete entries */
+    while (!SLIST_EMPTY(&hamt->entries)) {
+	HAMTEntry *entry;
+	entry = SLIST_FIRST(&hamt->entries);
+	SLIST_REMOVE_HEAD(&hamt->entries, next);
+	deletefunc(entry->data);
+	xfree(entry);
+    }
+
+    /* delete trie */
+    for (i=0; i<32; i++)
+	HAMT_delete_trie(&hamt->root[i]);
+
+    xfree(hamt->root);
+    xfree(hamt);
+}
+
+int
+HAMT_traverse(HAMT *hamt, void *d,
+	      int (*func) (/*@dependent@*/ /*@null@*/ void *node,
+			    /*@null@*/ void *d))
+{
+    HAMTEntry *entry;
+    SLIST_FOREACH(entry, &hamt->entries, next)
+	if (func(entry->data, d) == 0)
+	    return 0;
+    return 1;
+}
+
+/*@-temptrans -kepttrans -mustfree@*/
+void *
+HAMT_insert(HAMT *hamt, const char *str, void *data, int *replace,
+	    void (*deletefunc) (/*@only@*/ void *data))
+{
+    HAMTNode *node, *newnodes;
+    HAMTEntry *entry;
+    unsigned long key, keypart, Map;
+    int keypartbits = 0;
+    int level = 0;
+
+    key = HashKey(str);
+    keypart = key & 0x1F;
+    node = &hamt->root[keypart];
+
+    if (!node->BaseValue) {
+	node->BitMapKey = key;
+	entry = xmalloc(sizeof(HAMTEntry));
+	entry->str = str;
+	entry->data = data;
+	SLIST_INSERT_HEAD(&hamt->entries, entry, next);
+	node->BaseValue = entry;
+	if (IsSubTrie(node))
+	    InternalError(_("Data is seen as subtrie (misaligned?)"));
+	*replace = 1;
+	return data;
+    }
+
+    for (;;) {
+	if (!(IsSubTrie(node))) {
+	    if (node->BitMapKey == key) {
+		/*@-branchstate@*/
+		if (*replace) {
+		    deletefunc(((HAMTEntry *)(node->BaseValue))->data);
+		    ((HAMTEntry *)(node->BaseValue))->str = str;
+		    ((HAMTEntry *)(node->BaseValue))->data = data;
+		} else
+		    deletefunc(data);
+		/*@=branchstate@*/
+		return ((HAMTEntry *)(node->BaseValue))->data;
+	    } else {
+		unsigned long key2 = node->BitMapKey;
+		/* build tree downward until keys differ */
+		for (;;) {
+		    unsigned long keypart2;
+
+		    /* replace node with subtrie */
+		    keypartbits += 5;
+		    if (keypartbits > 30) {
+			/* Exceeded 32 bits: rehash */
+			key = ReHashKey(str, level);
+			key2 = ReHashKey(((HAMTEntry *)(node->BaseValue))->str,
+					 level);
+			keypartbits = 0;
+		    }
+		    keypart = (key >> keypartbits) & 0x1F;
+		    keypart2 = (key2 >> keypartbits) & 0x1F;
+
+		    if (keypart == keypart2) {
+			/* Still equal, build one-node subtrie and continue
+			 * downward.
+			 */
+			newnodes = xmalloc(sizeof(HAMTNode));
+			newnodes[0] = *node;	/* structure copy */
+			node->BitMapKey = 1<<keypart;
+			SetSubTrie(node, newnodes);
+			node = &newnodes[0];
+			level++;
+		    } else {
+			/* partitioned: allocate two-node subtrie */
+			newnodes = xmalloc(2*sizeof(HAMTNode));
+
+			entry = xmalloc(sizeof(HAMTEntry));
+			entry->str = str;
+			entry->data = data;
+			SLIST_INSERT_HEAD(&hamt->entries, entry, next);
+
+			/* Copy nodes into subtrie based on order */
+			if (keypart2 < keypart) {
+			    newnodes[0] = *node;    /* structure copy */
+			    newnodes[1].BitMapKey = key;
+			    newnodes[1].BaseValue = entry;
+			} else {
+			    newnodes[0].BitMapKey = key;
+			    newnodes[0].BaseValue = entry;
+			    newnodes[1] = *node;    /* structure copy */
+			}
+
+			/* Set bits in bitmap corresponding to keys */
+			node->BitMapKey = (1UL<<keypart) | (1UL<<keypart2);
+			SetSubTrie(node, newnodes);
+			*replace = 1;
+			return data;
+		    }
+		}
+	    }
+	}
+
+	/* Subtrie: look up in bitmap */
+	keypartbits += 5;
+	if (keypartbits > 30) {
+	    /* Exceeded 32 bits of current key: rehash */
+	    key = ReHashKey(str, level);
+	    keypartbits = 0;
+	}
+	keypart = (key >> keypartbits) & 0x1F;
+	if (!(node->BitMapKey & (1<<keypart))) {
+	    /* bit is 0 in bitmap -> add node to table */
+	    unsigned long Size;
+
+	    /* set bit to 1 */
+	    node->BitMapKey |= 1<<keypart;
+
+	    /* Count total number of bits in bitmap to determine new size */
+	    BitCount(Size, node->BitMapKey);
+	    Size &= 0x1F;	/* Clamp to <32 */
+	    newnodes = xmalloc(Size*sizeof(HAMTNode));
+
+	    /* Count bits below to find where to insert new node at */
+	    BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
+	    Map &= 0x1F;	/* Clamp to <32 */
+	    /* Copy existing nodes leaving gap for new node */
+	    memcpy(newnodes, GetSubTrie(node), Map*sizeof(HAMTNode));
+	    memcpy(&newnodes[Map+1], &(GetSubTrie(node))[Map],
+		   (Size-Map-1)*sizeof(HAMTNode));
+	    /* Delete old subtrie */
+	    xfree(GetSubTrie(node));
+	    /* Set up new node */
+	    newnodes[Map].BitMapKey = key;
+	    entry = xmalloc(sizeof(HAMTEntry));
+	    entry->str = str;
+	    entry->data = data;
+	    SLIST_INSERT_HEAD(&hamt->entries, entry, next);
+	    newnodes[Map].BaseValue = entry;
+	    SetSubTrie(node, newnodes);
+
+	    *replace = 1;
+	    return data;
+	}
+
+	/* Count bits below */
+	BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
+	Map &= 0x1F;	/* Clamp to <32 */
+
+	/* Go down a level */
+	level++;
+	node = &(GetSubTrie(node))[Map];
+    }
+}
+/*@=temptrans =kepttrans =mustfree@*/
+
+void *
+HAMT_search(HAMT *hamt, const char *str)
+{
+    HAMTNode *node;
+    unsigned long key, keypart, Map;
+    int keypartbits = 0;
+    int level = 0;
+    
+    key = HashKey(str);
+    keypart = key & 0x1F;
+    node = &hamt->root[keypart];
+
+    if (!node->BaseValue)
+	return NULL;
+
+    for (;;) {
+	if (!(IsSubTrie(node))) {
+	    if (node->BitMapKey == key)
+		return ((HAMTEntry *)(node->BaseValue))->data;
+	    else
+		return NULL;
+	}
+
+	/* Subtree: look up in bitmap */
+	keypartbits += 5;
+	if (keypartbits > 30) {
+	    /* Exceeded 32 bits of current key: rehash */
+	    key = ReHashKey(str, level);
+	    keypartbits = 0;
+	}
+	keypart = (key >> keypartbits) & 0x1F;
+	if (!(node->BitMapKey & (1<<keypart)))
+	    return NULL;	/* bit is 0 in bitmap -> no match */
+
+	/* Count bits below */
+	BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
+	Map &= 0x1F;	/* Clamp to <32 */
+
+	/* Go down a level */
+	level++;
+	node = &(GetSubTrie(node))[Map];
+    }
+}
+
diff --git a/libyasm/hamt.h b/libyasm/hamt.h
new file mode 100644
index 00000000..d74eb2a6
--- /dev/null
+++ b/libyasm/hamt.h
@@ -0,0 +1,62 @@
+/* $IdPath$
+ * Hash Array Mapped Trie (HAMT) header file.
+ *
+ *  Copyright (C) 2001  Peter Johnson
+ *
+ *  This file is part of YASM.
+ *
+ *  YASM is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  YASM is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+#ifndef YASM_HAMT_H
+#define YASM_HAMT_H
+
+typedef struct HAMT HAMT;
+
+/* Creates new, empty, HAMT. */
+HAMT *HAMT_new(void);
+
+/* Deletes HAMT and all data associated with it using deletefunc() on each data
+ * item.
+ */
+void HAMT_delete(/*@only@*/ HAMT *hamt,
+		 void (*deletefunc) (/*@only@*/ void *data));
+
+/* Inserts key into HAMT, associating it with data. 
+ * If the key is not present in the HAMT, inserts it, sets *replace to 1, and
+ *  returns the data passed in.
+ * If the key is already present and *replace is 0, deletes the data passed
+ *  in using deletefunc() and returns the data currently associated with the
+ *  key.
+ * If the key is already present and *replace is 1, deletes the data currently
+ *  associated with the key using deletefunc() and replaces it with the data
+ *  passed in.
+ */
+/*@dependent@*/ void *HAMT_insert(HAMT *hamt, /*@dependent@*/ const char *str,
+				  /*@only@*/ void *data, int *replace,
+				  void (*deletefunc) (/*@only@*/ void *data));
+
+/* Searches for the data associated with a key in the HAMT.  If the key is not
+ * present, returns NULL.
+ */
+/*@dependent@*/ /*@null@*/ void *HAMT_search(HAMT *hamt, const char *str);
+
+/* Traverse over all keys in HAMT, calling func() for each data item. 
+ * Stops early if func returns 0.
+ */
+int HAMT_traverse(HAMT *hamt, /*@null@*/ void *d,
+		  int (*func) (/*@dependent@*/ /*@null@*/ void *node,
+			       /*@null@*/ void *d));
+
+#endif
diff --git a/libyasm/linemgr.c b/libyasm/linemgr.c
index dd618c6b..10d87f5f 100644
--- a/libyasm/linemgr.c
+++ b/libyasm/linemgr.c
@@ -22,7 +22,7 @@
 #include "util.h"
 /*@unused@*/ RCSID("$IdPath$");
 
-#include "ternary.h"
+#include "hamt.h"
 
 #include "globals.h"
 
@@ -39,18 +39,7 @@ unsigned int asm_options = 0;
 
 int indent_level = 0;
 
-static /*@only@*/ /*@null@*/ ternary_tree filename_table = (ternary_tree)NULL;
-
-void
-switch_filename(const char *filename)
-{
-    char *copy = xstrdup(filename);
-    in_filename = ternary_insert(&filename_table, filename, copy, 0);
-    /*@-branchstate@*/
-    if (in_filename != copy)
-	xfree(copy);
-    /*@=branchstate@*/
-}
+static /*@only@*/ /*@null@*/ HAMT *filename_table = NULL;
 
 static void
 filename_delete_one(/*@only@*/ void *d)
@@ -58,10 +47,25 @@ filename_delete_one(/*@only@*/ void *d)
     xfree(d);
 }
 
+void
+switch_filename(const char *filename)
+{
+    char *copy = xstrdup(filename);
+    int replace = 0;
+    if (!filename_table)
+	filename_table = HAMT_new();
+    /*@-aliasunique@*/
+    in_filename = HAMT_insert(filename_table, copy, copy, &replace,
+			      filename_delete_one);
+    /*@=aliasunique@*/
+}
+
 void
 filename_delete_all(void)
 {
     in_filename = NULL;
-    ternary_cleanup(filename_table, filename_delete_one);
-    filename_table = NULL;
+    if (filename_table) {
+	HAMT_delete(filename_table, filename_delete_one);
+	filename_table = NULL;
+    }
 }
diff --git a/libyasm/symrec.c b/libyasm/symrec.c
index c265fa88..76ba18d6 100644
--- a/libyasm/symrec.c
+++ b/libyasm/symrec.c
@@ -27,7 +27,7 @@
 # include <limits.h>
 #endif
 
-#include "ternary.h"
+#include "hamt.h"
 
 #include "globals.h"
 #include "errwarn.h"
@@ -78,27 +78,38 @@ struct symrec {
 };
 
 /* The symbol table: a ternary tree. */
-static /*@only@*/ /*@null@*/ ternary_tree sym_table = (ternary_tree)NULL;
+static /*@only@*/ /*@null@*/ HAMT *sym_table = NULL;
+
+static void
+symrec_delete_one(/*@only@*/ void *d)
+{
+    symrec *sym = d;
+    xfree(sym->name);
+    if (sym->type == SYM_EQU)
+	expr_delete(sym->value.expn);
+    assert(cur_objfmt != NULL);
+    if (sym->of_data_vis_g && (sym->visibility & SYM_GLOBAL))
+	cur_objfmt->declare_data_delete(SYM_GLOBAL, sym->of_data_vis_g);
+    if (sym->of_data_vis_ce && (sym->visibility & SYM_COMMON)) {
+	cur_objfmt->declare_data_delete(SYM_COMMON, sym->of_data_vis_ce);
+	sym->of_data_vis_ce = NULL;
+    }
+    if (sym->of_data_vis_ce && (sym->visibility & SYM_EXTERN))
+	cur_objfmt->declare_data_delete(SYM_EXTERN, sym->of_data_vis_ce);
+    xfree(sym);
+}
 
 /* create a new symrec */
+/*@-freshtrans -mustfree@*/
 static /*@partial@*/ /*@dependent@*/ symrec *
 symrec_get_or_new(const char *name, int in_table)
 {
-    symrec *rec, *rec2;
+    symrec *rec;
+    int replace = 0;
+    char *symname = xstrdup(name);
 
     rec = xmalloc(sizeof(symrec));
-    if (in_table) {
-	rec2 = ternary_insert(&sym_table, name, rec, 0);
-
-	if (rec2 != rec) {
-	    xfree(rec);
-	    return rec2;
-	}
-	rec->status = SYM_NOSTATUS;
-    } else
-	rec->status = SYM_NOTINTABLE;
-
-    rec->name = xstrdup(name);
+    rec->name = symname;
     rec->type = SYM_UNKNOWN;
     rec->filename = in_filename;
     rec->line = line_number;
@@ -106,17 +117,28 @@ symrec_get_or_new(const char *name, int in_table)
     rec->of_data_vis_ce = NULL;
     rec->of_data_vis_g = NULL;
 
-    /*@-freshtrans -mustfree@*/
+    if (in_table) {
+	rec->status = SYM_NOSTATUS;
+	if (!sym_table)
+	    sym_table = HAMT_new();
+	return HAMT_insert(sym_table, symname, rec, &replace,
+			   symrec_delete_one);
+    }
+
+    rec->status = SYM_NOTINTABLE;
     return rec;
-    /*@=freshtrans =mustfree@*/
 }
+/*@=freshtrans =mustfree@*/
 
 /* Call a function with each symrec.  Stops early if 0 returned by func.
    Returns 0 if stopped early. */
 int
 symrec_traverse(void *d, int (*func) (symrec *sym, void *d))
 {
-    return ternary_traverse(sym_table, d, (int (*) (void *, void *))func);
+    if (sym_table)
+	return HAMT_traverse(sym_table, d, (int (*) (void *, void *))func);
+    else
+	return 1;
 }
 
 symrec *
@@ -289,30 +311,13 @@ symrec_parser_finalize(void)
 		_(" (Each undefined symbol is reported only once.)"));
 }
 
-static void
-symrec_delete_one(/*@only@*/ void *d)
-{
-    symrec *sym = d;
-    xfree(sym->name);
-    if (sym->type == SYM_EQU)
-	expr_delete(sym->value.expn);
-    assert(cur_objfmt != NULL);
-    if (sym->of_data_vis_g && (sym->visibility & SYM_GLOBAL))
-	cur_objfmt->declare_data_delete(SYM_GLOBAL, sym->of_data_vis_g);
-    if (sym->of_data_vis_ce && (sym->visibility & SYM_COMMON)) {
-	cur_objfmt->declare_data_delete(SYM_COMMON, sym->of_data_vis_ce);
-	sym->of_data_vis_ce = NULL;
-    }
-    if (sym->of_data_vis_ce && (sym->visibility & SYM_EXTERN))
-	cur_objfmt->declare_data_delete(SYM_EXTERN, sym->of_data_vis_ce);
-    xfree(sym);
-}
-
 void
 symrec_delete_all(void)
 {
-    ternary_cleanup(sym_table, symrec_delete_one);
-    sym_table = NULL;
+    if (sym_table) {
+	HAMT_delete(sym_table, symrec_delete_one);
+	sym_table = NULL;
+    }
 }
 
 void
diff --git a/splint.sh b/splint.sh
index 607bdf75..559fdf3e 100755
--- a/splint.sh
+++ b/splint.sh
@@ -1,2 +1,2 @@
 #!/bin/sh
-lclint -exportlocal -predbool -boolops +boolint +charint -retvalint -retvalother +ansilimits -I/usr/local/include -I.. -Iarch/x86 -I. -DHAVE_CONFIG_H -DHAVE_BOGUS_SYS_QUEUE_H -Dlint main.c options.c arch.c bytecode.c errwarn.c expr.c file.c floatnum.c globals.c intnum.c parser.c section.c arch/x86/arch.c arch/x86/bytecode.c arch/x86/expr.c objfmts/dbg/objfmt.c parsers/nasm/parser.c preprocs/raw/preproc.c parsers/nasm/bison.c symrec.c ternary.c
+lclint -exportlocal -predbool -boolops +boolint +charint -retvalint -retvalother +ansilimits -I/usr/local/include -I.. -Iarch/x86 -I. -DHAVE_CONFIG_H -DHAVE_BOGUS_SYS_QUEUE_H -Dlint main.c options.c arch.c bytecode.c errwarn.c expr.c file.c floatnum.c globals.c intnum.c parser.c section.c arch/x86/arch.c arch/x86/bytecode.c arch/x86/expr.c objfmts/dbg/objfmt.c parsers/nasm/parser.c preprocs/raw/preproc.c parsers/nasm/bison.c symrec.c hamt.c
diff --git a/src/Makefile.am b/src/Makefile.am
index 5650b0f3..f7908803 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -54,8 +54,8 @@ libyasm_a_SOURCES = \
 	intnum.h		\
 	floatnum.c		\
 	floatnum.h		\
-	ternary.c		\
-	ternary.h		\
+	hamt.c			\
+	hamt.h			\
 	bitvect.c		\
 	bitvect.h		\
 	valparam.c		\
diff --git a/src/globals.c b/src/globals.c
index dd618c6b..10d87f5f 100644
--- a/src/globals.c
+++ b/src/globals.c
@@ -22,7 +22,7 @@
 #include "util.h"
 /*@unused@*/ RCSID("$IdPath$");
 
-#include "ternary.h"
+#include "hamt.h"
 
 #include "globals.h"
 
@@ -39,18 +39,7 @@ unsigned int asm_options = 0;
 
 int indent_level = 0;
 
-static /*@only@*/ /*@null@*/ ternary_tree filename_table = (ternary_tree)NULL;
-
-void
-switch_filename(const char *filename)
-{
-    char *copy = xstrdup(filename);
-    in_filename = ternary_insert(&filename_table, filename, copy, 0);
-    /*@-branchstate@*/
-    if (in_filename != copy)
-	xfree(copy);
-    /*@=branchstate@*/
-}
+static /*@only@*/ /*@null@*/ HAMT *filename_table = NULL;
 
 static void
 filename_delete_one(/*@only@*/ void *d)
@@ -58,10 +47,25 @@ filename_delete_one(/*@only@*/ void *d)
     xfree(d);
 }
 
+void
+switch_filename(const char *filename)
+{
+    char *copy = xstrdup(filename);
+    int replace = 0;
+    if (!filename_table)
+	filename_table = HAMT_new();
+    /*@-aliasunique@*/
+    in_filename = HAMT_insert(filename_table, copy, copy, &replace,
+			      filename_delete_one);
+    /*@=aliasunique@*/
+}
+
 void
 filename_delete_all(void)
 {
     in_filename = NULL;
-    ternary_cleanup(filename_table, filename_delete_one);
-    filename_table = NULL;
+    if (filename_table) {
+	HAMT_delete(filename_table, filename_delete_one);
+	filename_table = NULL;
+    }
 }
diff --git a/src/hamt.c b/src/hamt.c
new file mode 100644
index 00000000..eb4df1f3
--- /dev/null
+++ b/src/hamt.c
@@ -0,0 +1,354 @@
+/*
+ * Hash Array Mapped Trie (HAMT) implementation
+ *
+ *  Copyright (C) 2001  Peter Johnson
+ *
+ *  Based on the paper "Ideal Hash Tries" by Phil Bagwell [2000].
+ *  One algorithmic change from that described in the paper: we use the LSB's
+ *  of the key to index the root table and move upward in the key rather than
+ *  use the MSBs as described in the paper.  The LSBs have more entropy.
+ *
+ *  This file is part of YASM.
+ *
+ *  YASM is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  YASM is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+#include "util.h"
+/*@unused@*/ RCSID("$IdPath$");
+
+#include "errwarn.h"
+#include "hamt.h"
+
+typedef struct HAMTEntry {
+    SLIST_ENTRY(HAMTEntry) next;	/* next hash table entry */
+    /*@dependent@*/ const char *str;	/* string being hashed */
+    /*@owned@*/ void *data;		/* data pointer being stored */
+} HAMTEntry;
+
+typedef struct HAMTNode {
+    unsigned long BitMapKey;		/* 32 bits, bitmap or hash key */
+    void *BaseValue;			/* Base of HAMTNode list or value */
+} HAMTNode;
+
+struct HAMT {
+    SLIST_HEAD(HAMTEntryHead, HAMTEntry) entries;
+    HAMTNode *root;
+};
+
+/* XXX make a portable version of this.  This depends on the pointer being
+ * 4 or 2-byte aligned (as it uses the LSB of the pointer variable to store
+ * the subtrie flag!
+ */
+#define IsSubTrie(n)		((unsigned long)((n)->BaseValue) & 1)
+#define SetSubTrie(n, v)	do {				\
+	if ((unsigned long)(v) & 1)				\
+	    InternalError(_("Subtrie is seen as subtrie before flag is set (misaligned?)"));	\
+	(n)->BaseValue = (void *)((unsigned long)(v) | 1);	\
+    } while (0)
+#define GetSubTrie(n)		(HAMTNode *)((unsigned long)((n)->BaseValue)&~1UL)
+
+/* Bit-counting */
+#define SK5	0x55555555
+#define SK3	0x33333333
+#define SKF0	0x0F0F0F0F
+#define BitCount(d, s)		do {		\
+	d = s;					\
+	d -= (d>>1) & SK5;			\
+	d = (d & SK3) + ((d>>2) & SK3);		\
+	d = (d & SKF0) + ((d>>4) & SKF0);	\
+	d += d>>16;				\
+	d += d>>8;				\
+    } while (0)
+
+static unsigned long
+HashKey(const char *key)
+{
+    unsigned long a=31415, b=27183, vHash;
+    for (vHash=0; *key; key++, a*=b)
+	vHash = a*vHash + *key;
+    return vHash;
+}
+
+static unsigned long
+ReHashKey(const char *key, int Level)
+{
+    unsigned long a=31415, b=27183, vHash;
+    for (vHash=0; *key; key++, a*=b)
+	vHash = a*vHash*(unsigned long)Level + *key;
+    return vHash;
+}
+
+/*@-compdef -nullret@*/
+HAMT *
+HAMT_new(void)
+{
+    HAMT *hamt;
+    int i;
+
+    hamt = xmalloc(sizeof(HAMT));
+    SLIST_INIT(&hamt->entries);
+    hamt->root = xmalloc(32*sizeof(HAMTNode));
+
+    for (i=0; i<32; i++)
+	hamt->root[i].BaseValue = NULL;
+
+    return hamt;
+}
+/*@=compdef =nullret@*/
+
+static void
+HAMT_delete_trie(HAMTNode *node)
+{
+    if (IsSubTrie(node)) {
+	unsigned long i, Size;
+
+	/* Count total number of bits in bitmap to determine size */
+	BitCount(Size, node->BitMapKey);
+	Size &= 0x1F;	/* Clamp to <32 */
+
+	for (i=0; i<Size; i++)
+	    HAMT_delete_trie(&(GetSubTrie(node))[i]);
+	xfree(GetSubTrie(node));
+    }
+}
+
+void
+HAMT_delete(HAMT *hamt, void (*deletefunc) (/*@keep@*/ void *data))
+{
+    int i;
+
+    /* delete entries */
+    while (!SLIST_EMPTY(&hamt->entries)) {
+	HAMTEntry *entry;
+	entry = SLIST_FIRST(&hamt->entries);
+	SLIST_REMOVE_HEAD(&hamt->entries, next);
+	deletefunc(entry->data);
+	xfree(entry);
+    }
+
+    /* delete trie */
+    for (i=0; i<32; i++)
+	HAMT_delete_trie(&hamt->root[i]);
+
+    xfree(hamt->root);
+    xfree(hamt);
+}
+
+int
+HAMT_traverse(HAMT *hamt, void *d,
+	      int (*func) (/*@dependent@*/ /*@null@*/ void *node,
+			    /*@null@*/ void *d))
+{
+    HAMTEntry *entry;
+    SLIST_FOREACH(entry, &hamt->entries, next)
+	if (func(entry->data, d) == 0)
+	    return 0;
+    return 1;
+}
+
+/*@-temptrans -kepttrans -mustfree@*/
+void *
+HAMT_insert(HAMT *hamt, const char *str, void *data, int *replace,
+	    void (*deletefunc) (/*@only@*/ void *data))
+{
+    HAMTNode *node, *newnodes;
+    HAMTEntry *entry;
+    unsigned long key, keypart, Map;
+    int keypartbits = 0;
+    int level = 0;
+
+    key = HashKey(str);
+    keypart = key & 0x1F;
+    node = &hamt->root[keypart];
+
+    if (!node->BaseValue) {
+	node->BitMapKey = key;
+	entry = xmalloc(sizeof(HAMTEntry));
+	entry->str = str;
+	entry->data = data;
+	SLIST_INSERT_HEAD(&hamt->entries, entry, next);
+	node->BaseValue = entry;
+	if (IsSubTrie(node))
+	    InternalError(_("Data is seen as subtrie (misaligned?)"));
+	*replace = 1;
+	return data;
+    }
+
+    for (;;) {
+	if (!(IsSubTrie(node))) {
+	    if (node->BitMapKey == key) {
+		/*@-branchstate@*/
+		if (*replace) {
+		    deletefunc(((HAMTEntry *)(node->BaseValue))->data);
+		    ((HAMTEntry *)(node->BaseValue))->str = str;
+		    ((HAMTEntry *)(node->BaseValue))->data = data;
+		} else
+		    deletefunc(data);
+		/*@=branchstate@*/
+		return ((HAMTEntry *)(node->BaseValue))->data;
+	    } else {
+		unsigned long key2 = node->BitMapKey;
+		/* build tree downward until keys differ */
+		for (;;) {
+		    unsigned long keypart2;
+
+		    /* replace node with subtrie */
+		    keypartbits += 5;
+		    if (keypartbits > 30) {
+			/* Exceeded 32 bits: rehash */
+			key = ReHashKey(str, level);
+			key2 = ReHashKey(((HAMTEntry *)(node->BaseValue))->str,
+					 level);
+			keypartbits = 0;
+		    }
+		    keypart = (key >> keypartbits) & 0x1F;
+		    keypart2 = (key2 >> keypartbits) & 0x1F;
+
+		    if (keypart == keypart2) {
+			/* Still equal, build one-node subtrie and continue
+			 * downward.
+			 */
+			newnodes = xmalloc(sizeof(HAMTNode));
+			newnodes[0] = *node;	/* structure copy */
+			node->BitMapKey = 1<<keypart;
+			SetSubTrie(node, newnodes);
+			node = &newnodes[0];
+			level++;
+		    } else {
+			/* partitioned: allocate two-node subtrie */
+			newnodes = xmalloc(2*sizeof(HAMTNode));
+
+			entry = xmalloc(sizeof(HAMTEntry));
+			entry->str = str;
+			entry->data = data;
+			SLIST_INSERT_HEAD(&hamt->entries, entry, next);
+
+			/* Copy nodes into subtrie based on order */
+			if (keypart2 < keypart) {
+			    newnodes[0] = *node;    /* structure copy */
+			    newnodes[1].BitMapKey = key;
+			    newnodes[1].BaseValue = entry;
+			} else {
+			    newnodes[0].BitMapKey = key;
+			    newnodes[0].BaseValue = entry;
+			    newnodes[1] = *node;    /* structure copy */
+			}
+
+			/* Set bits in bitmap corresponding to keys */
+			node->BitMapKey = (1UL<<keypart) | (1UL<<keypart2);
+			SetSubTrie(node, newnodes);
+			*replace = 1;
+			return data;
+		    }
+		}
+	    }
+	}
+
+	/* Subtrie: look up in bitmap */
+	keypartbits += 5;
+	if (keypartbits > 30) {
+	    /* Exceeded 32 bits of current key: rehash */
+	    key = ReHashKey(str, level);
+	    keypartbits = 0;
+	}
+	keypart = (key >> keypartbits) & 0x1F;
+	if (!(node->BitMapKey & (1<<keypart))) {
+	    /* bit is 0 in bitmap -> add node to table */
+	    unsigned long Size;
+
+	    /* set bit to 1 */
+	    node->BitMapKey |= 1<<keypart;
+
+	    /* Count total number of bits in bitmap to determine new size */
+	    BitCount(Size, node->BitMapKey);
+	    Size &= 0x1F;	/* Clamp to <32 */
+	    newnodes = xmalloc(Size*sizeof(HAMTNode));
+
+	    /* Count bits below to find where to insert new node at */
+	    BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
+	    Map &= 0x1F;	/* Clamp to <32 */
+	    /* Copy existing nodes leaving gap for new node */
+	    memcpy(newnodes, GetSubTrie(node), Map*sizeof(HAMTNode));
+	    memcpy(&newnodes[Map+1], &(GetSubTrie(node))[Map],
+		   (Size-Map-1)*sizeof(HAMTNode));
+	    /* Delete old subtrie */
+	    xfree(GetSubTrie(node));
+	    /* Set up new node */
+	    newnodes[Map].BitMapKey = key;
+	    entry = xmalloc(sizeof(HAMTEntry));
+	    entry->str = str;
+	    entry->data = data;
+	    SLIST_INSERT_HEAD(&hamt->entries, entry, next);
+	    newnodes[Map].BaseValue = entry;
+	    SetSubTrie(node, newnodes);
+
+	    *replace = 1;
+	    return data;
+	}
+
+	/* Count bits below */
+	BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
+	Map &= 0x1F;	/* Clamp to <32 */
+
+	/* Go down a level */
+	level++;
+	node = &(GetSubTrie(node))[Map];
+    }
+}
+/*@=temptrans =kepttrans =mustfree@*/
+
+void *
+HAMT_search(HAMT *hamt, const char *str)
+{
+    HAMTNode *node;
+    unsigned long key, keypart, Map;
+    int keypartbits = 0;
+    int level = 0;
+    
+    key = HashKey(str);
+    keypart = key & 0x1F;
+    node = &hamt->root[keypart];
+
+    if (!node->BaseValue)
+	return NULL;
+
+    for (;;) {
+	if (!(IsSubTrie(node))) {
+	    if (node->BitMapKey == key)
+		return ((HAMTEntry *)(node->BaseValue))->data;
+	    else
+		return NULL;
+	}
+
+	/* Subtree: look up in bitmap */
+	keypartbits += 5;
+	if (keypartbits > 30) {
+	    /* Exceeded 32 bits of current key: rehash */
+	    key = ReHashKey(str, level);
+	    keypartbits = 0;
+	}
+	keypart = (key >> keypartbits) & 0x1F;
+	if (!(node->BitMapKey & (1<<keypart)))
+	    return NULL;	/* bit is 0 in bitmap -> no match */
+
+	/* Count bits below */
+	BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
+	Map &= 0x1F;	/* Clamp to <32 */
+
+	/* Go down a level */
+	level++;
+	node = &(GetSubTrie(node))[Map];
+    }
+}
+
diff --git a/src/hamt.h b/src/hamt.h
new file mode 100644
index 00000000..d74eb2a6
--- /dev/null
+++ b/src/hamt.h
@@ -0,0 +1,62 @@
+/* $IdPath$
+ * Hash Array Mapped Trie (HAMT) header file.
+ *
+ *  Copyright (C) 2001  Peter Johnson
+ *
+ *  This file is part of YASM.
+ *
+ *  YASM is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  YASM is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+#ifndef YASM_HAMT_H
+#define YASM_HAMT_H
+
+typedef struct HAMT HAMT;
+
+/* Creates new, empty, HAMT. */
+HAMT *HAMT_new(void);
+
+/* Deletes HAMT and all data associated with it using deletefunc() on each data
+ * item.
+ */
+void HAMT_delete(/*@only@*/ HAMT *hamt,
+		 void (*deletefunc) (/*@only@*/ void *data));
+
+/* Inserts key into HAMT, associating it with data. 
+ * If the key is not present in the HAMT, inserts it, sets *replace to 1, and
+ *  returns the data passed in.
+ * If the key is already present and *replace is 0, deletes the data passed
+ *  in using deletefunc() and returns the data currently associated with the
+ *  key.
+ * If the key is already present and *replace is 1, deletes the data currently
+ *  associated with the key using deletefunc() and replaces it with the data
+ *  passed in.
+ */
+/*@dependent@*/ void *HAMT_insert(HAMT *hamt, /*@dependent@*/ const char *str,
+				  /*@only@*/ void *data, int *replace,
+				  void (*deletefunc) (/*@only@*/ void *data));
+
+/* Searches for the data associated with a key in the HAMT.  If the key is not
+ * present, returns NULL.
+ */
+/*@dependent@*/ /*@null@*/ void *HAMT_search(HAMT *hamt, const char *str);
+
+/* Traverse over all keys in HAMT, calling func() for each data item. 
+ * Stops early if func returns 0.
+ */
+int HAMT_traverse(HAMT *hamt, /*@null@*/ void *d,
+		  int (*func) (/*@dependent@*/ /*@null@*/ void *node,
+			       /*@null@*/ void *d));
+
+#endif
diff --git a/src/lclint.sh b/src/lclint.sh
index 607bdf75..559fdf3e 100755
--- a/src/lclint.sh
+++ b/src/lclint.sh
@@ -1,2 +1,2 @@
 #!/bin/sh
-lclint -exportlocal -predbool -boolops +boolint +charint -retvalint -retvalother +ansilimits -I/usr/local/include -I.. -Iarch/x86 -I. -DHAVE_CONFIG_H -DHAVE_BOGUS_SYS_QUEUE_H -Dlint main.c options.c arch.c bytecode.c errwarn.c expr.c file.c floatnum.c globals.c intnum.c parser.c section.c arch/x86/arch.c arch/x86/bytecode.c arch/x86/expr.c objfmts/dbg/objfmt.c parsers/nasm/parser.c preprocs/raw/preproc.c parsers/nasm/bison.c symrec.c ternary.c
+lclint -exportlocal -predbool -boolops +boolint +charint -retvalint -retvalother +ansilimits -I/usr/local/include -I.. -Iarch/x86 -I. -DHAVE_CONFIG_H -DHAVE_BOGUS_SYS_QUEUE_H -Dlint main.c options.c arch.c bytecode.c errwarn.c expr.c file.c floatnum.c globals.c intnum.c parser.c section.c arch/x86/arch.c arch/x86/bytecode.c arch/x86/expr.c objfmts/dbg/objfmt.c parsers/nasm/parser.c preprocs/raw/preproc.c parsers/nasm/bison.c symrec.c hamt.c
diff --git a/src/linemgr.c b/src/linemgr.c
index dd618c6b..10d87f5f 100644
--- a/src/linemgr.c
+++ b/src/linemgr.c
@@ -22,7 +22,7 @@
 #include "util.h"
 /*@unused@*/ RCSID("$IdPath$");
 
-#include "ternary.h"
+#include "hamt.h"
 
 #include "globals.h"
 
@@ -39,18 +39,7 @@ unsigned int asm_options = 0;
 
 int indent_level = 0;
 
-static /*@only@*/ /*@null@*/ ternary_tree filename_table = (ternary_tree)NULL;
-
-void
-switch_filename(const char *filename)
-{
-    char *copy = xstrdup(filename);
-    in_filename = ternary_insert(&filename_table, filename, copy, 0);
-    /*@-branchstate@*/
-    if (in_filename != copy)
-	xfree(copy);
-    /*@=branchstate@*/
-}
+static /*@only@*/ /*@null@*/ HAMT *filename_table = NULL;
 
 static void
 filename_delete_one(/*@only@*/ void *d)
@@ -58,10 +47,25 @@ filename_delete_one(/*@only@*/ void *d)
     xfree(d);
 }
 
+void
+switch_filename(const char *filename)
+{
+    char *copy = xstrdup(filename);
+    int replace = 0;
+    if (!filename_table)
+	filename_table = HAMT_new();
+    /*@-aliasunique@*/
+    in_filename = HAMT_insert(filename_table, copy, copy, &replace,
+			      filename_delete_one);
+    /*@=aliasunique@*/
+}
+
 void
 filename_delete_all(void)
 {
     in_filename = NULL;
-    ternary_cleanup(filename_table, filename_delete_one);
-    filename_table = NULL;
+    if (filename_table) {
+	HAMT_delete(filename_table, filename_delete_one);
+	filename_table = NULL;
+    }
 }
diff --git a/src/symrec.c b/src/symrec.c
index c265fa88..76ba18d6 100644
--- a/src/symrec.c
+++ b/src/symrec.c
@@ -27,7 +27,7 @@
 # include <limits.h>
 #endif
 
-#include "ternary.h"
+#include "hamt.h"
 
 #include "globals.h"
 #include "errwarn.h"
@@ -78,27 +78,38 @@ struct symrec {
 };
 
 /* The symbol table: a ternary tree. */
-static /*@only@*/ /*@null@*/ ternary_tree sym_table = (ternary_tree)NULL;
+static /*@only@*/ /*@null@*/ HAMT *sym_table = NULL;
+
+static void
+symrec_delete_one(/*@only@*/ void *d)
+{
+    symrec *sym = d;
+    xfree(sym->name);
+    if (sym->type == SYM_EQU)
+	expr_delete(sym->value.expn);
+    assert(cur_objfmt != NULL);
+    if (sym->of_data_vis_g && (sym->visibility & SYM_GLOBAL))
+	cur_objfmt->declare_data_delete(SYM_GLOBAL, sym->of_data_vis_g);
+    if (sym->of_data_vis_ce && (sym->visibility & SYM_COMMON)) {
+	cur_objfmt->declare_data_delete(SYM_COMMON, sym->of_data_vis_ce);
+	sym->of_data_vis_ce = NULL;
+    }
+    if (sym->of_data_vis_ce && (sym->visibility & SYM_EXTERN))
+	cur_objfmt->declare_data_delete(SYM_EXTERN, sym->of_data_vis_ce);
+    xfree(sym);
+}
 
 /* create a new symrec */
+/*@-freshtrans -mustfree@*/
 static /*@partial@*/ /*@dependent@*/ symrec *
 symrec_get_or_new(const char *name, int in_table)
 {
-    symrec *rec, *rec2;
+    symrec *rec;
+    int replace = 0;
+    char *symname = xstrdup(name);
 
     rec = xmalloc(sizeof(symrec));
-    if (in_table) {
-	rec2 = ternary_insert(&sym_table, name, rec, 0);
-
-	if (rec2 != rec) {
-	    xfree(rec);
-	    return rec2;
-	}
-	rec->status = SYM_NOSTATUS;
-    } else
-	rec->status = SYM_NOTINTABLE;
-
-    rec->name = xstrdup(name);
+    rec->name = symname;
     rec->type = SYM_UNKNOWN;
     rec->filename = in_filename;
     rec->line = line_number;
@@ -106,17 +117,28 @@ symrec_get_or_new(const char *name, int in_table)
     rec->of_data_vis_ce = NULL;
     rec->of_data_vis_g = NULL;
 
-    /*@-freshtrans -mustfree@*/
+    if (in_table) {
+	rec->status = SYM_NOSTATUS;
+	if (!sym_table)
+	    sym_table = HAMT_new();
+	return HAMT_insert(sym_table, symname, rec, &replace,
+			   symrec_delete_one);
+    }
+
+    rec->status = SYM_NOTINTABLE;
     return rec;
-    /*@=freshtrans =mustfree@*/
 }
+/*@=freshtrans =mustfree@*/
 
 /* Call a function with each symrec.  Stops early if 0 returned by func.
    Returns 0 if stopped early. */
 int
 symrec_traverse(void *d, int (*func) (symrec *sym, void *d))
 {
-    return ternary_traverse(sym_table, d, (int (*) (void *, void *))func);
+    if (sym_table)
+	return HAMT_traverse(sym_table, d, (int (*) (void *, void *))func);
+    else
+	return 1;
 }
 
 symrec *
@@ -289,30 +311,13 @@ symrec_parser_finalize(void)
 		_(" (Each undefined symbol is reported only once.)"));
 }
 
-static void
-symrec_delete_one(/*@only@*/ void *d)
-{
-    symrec *sym = d;
-    xfree(sym->name);
-    if (sym->type == SYM_EQU)
-	expr_delete(sym->value.expn);
-    assert(cur_objfmt != NULL);
-    if (sym->of_data_vis_g && (sym->visibility & SYM_GLOBAL))
-	cur_objfmt->declare_data_delete(SYM_GLOBAL, sym->of_data_vis_g);
-    if (sym->of_data_vis_ce && (sym->visibility & SYM_COMMON)) {
-	cur_objfmt->declare_data_delete(SYM_COMMON, sym->of_data_vis_ce);
-	sym->of_data_vis_ce = NULL;
-    }
-    if (sym->of_data_vis_ce && (sym->visibility & SYM_EXTERN))
-	cur_objfmt->declare_data_delete(SYM_EXTERN, sym->of_data_vis_ce);
-    xfree(sym);
-}
-
 void
 symrec_delete_all(void)
 {
-    ternary_cleanup(sym_table, symrec_delete_one);
-    sym_table = NULL;
+    if (sym_table) {
+	HAMT_delete(sym_table, symrec_delete_one);
+	sym_table = NULL;
+    }
 }
 
 void
diff --git a/src/ternary.c b/src/ternary.c
deleted file mode 100644
index 07ba7b4d..00000000
--- a/src/ternary.c
+++ /dev/null
@@ -1,191 +0,0 @@
-/* ternary.c - Ternary Search Trees
-   Copyright (C) 2001 Free Software Foundation, Inc.
-
-   Contributed by Daniel Berlin (dan@cgsoftware.com)
-
-   ternary_traverse by Peter Johnson (adapted from code by Jon Bentley and
-   Robert Sedgewick).
-
-   This program is free software; you can redistribute it and/or modify it
-   under the terms of the GNU General Public License as published by the
-   Free Software Foundation; either version 2, or (at your option) any
-   later version.
-
-   This program is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-   GNU General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-   USA.  */
-#include "util.h"
-/*@unused@*/ RCSID("$IdPath$");
-
-#ifdef STDC_HEADERS
-# include <assert.h>
-#endif
-
-#include "errwarn.h"
-
-#include "ternary.h"
-
-
-/* Non-recursive so we don't waste stack space/time on large
-   insertions. */
-/*@-compmempass@*/
-void *
-ternary_insert (ternary_tree * root, const char *s, void *data, int replace)
-{
-  int diff;
-  ternary_tree curr, *pcurr;
-
-  /* Start at the root. */
-  pcurr = root;
-  /* Loop until we find the right position */
-  while ((curr = *pcurr))
-    {
-      /* Calculate the difference */
-      diff = *s - curr->splitchar;
-      /* Handle current char equal to node splitchar */
-      if (diff == 0)
-	{
-	  /* Handle the case of a string we already have */
-	  if (*s++ == 0)
-	    {
-	      if (replace)
-	        {
-		  xfree(curr->eqkid);
-		  /*@-temptrans@*/
-		  curr->eqkid = (ternary_tree) data;
-		  /*@=temptrans@*/
-	        }
-	      return (void *) curr->eqkid;
-	    }
-	  pcurr = &(curr->eqkid);
-	}
-      /* Handle current char less than node splitchar */
-      else if (diff < 0)
-	{
-	  pcurr = &(curr->lokid);
-	}
-      /* Handle current char greater than node splitchar */
-      else
-	{
-	  pcurr = &(curr->hikid);
-	}
-    }
-  /* It's not a duplicate string, and we should insert what's left of
-     the string, into the tree rooted at curr */
-  for (;;)
-    {
-      /* Allocate the memory for the node, and fill it in */
-      *pcurr = (ternary_tree) xmalloc (sizeof (ternary_node));
-      curr = *pcurr;
-      curr->splitchar = *s;
-      curr->lokid = curr->hikid = curr->eqkid = 0;
-
-      /* Place nodes until we hit the end of the string.
-         When we hit it, place the data in the right place, and
-         return.
-       */
-      if (*s++ == 0)
-	{
-	  curr->eqkid = (ternary_tree) data;
-	  return data;
-	}
-      pcurr = &(curr->eqkid);
-    }
-}
-/*@=compmempass@*/
-
-/* Free the ternary search tree rooted at p. */
-void
-ternary_cleanup (ternary_tree p, void (*data_cleanup)(/*@dependent@*/
-						      /*@null@*/ void *d))
-{
-  if (p)
-    {
-      ternary_cleanup (p->lokid, data_cleanup);
-      if (p->splitchar)
-	ternary_cleanup (p->eqkid, data_cleanup);
-      else
-	data_cleanup (p->eqkid);
-      ternary_cleanup (p->hikid, data_cleanup);
-      xfree (p);
-    }
-}
-
-/* Non-recursive find of a string in the ternary tree */
-void *
-ternary_search (ternary_tree p, const char *s)
-{
-  /*@null@*/ ternary_tree curr;
-  int diff, spchar;
-  spchar = *s;
-  curr = p;
-  /* Loop while we haven't hit a NULL node or returned */
-  while (curr)
-    {
-      assert(curr != NULL);
-      /* Calculate the difference */
-      diff = spchar - curr->splitchar;
-      /* Handle the equal case */
-      if (diff == 0)
-	{
-	  if (spchar == 0)
-	    return (void *) curr->eqkid;
-	  spchar = *++s;
-	  curr = curr->eqkid;
-	}
-      /* Handle the less than case */
-      else if (diff < 0)
-	curr = curr->lokid;
-      /* All that's left is greater than */
-      else
-	curr = curr->hikid;
-    }
-  return NULL;
-}
-
-/* For those who care, the recursive version of the search. Useful if
-   you want a starting point for pmsearch or nearsearch. */
-static /*@dependent@*/ /*@null@*/ void *
-ternary_recursivesearch (ternary_tree p, const char *s)
-{
-  if (!p)
-    return 0;
-  if (*s < p->splitchar)
-    return ternary_recursivesearch (p->lokid, s);
-  else if (*s > p->splitchar)
-    return ternary_recursivesearch (p->hikid, s);
-  else
-    {
-      if (*s == 0)
-	return (void *) p->eqkid;
-      return ternary_recursivesearch (p->eqkid, ++s);
-    }
-}
-
-/* Traverse over tree, calling callback function for each leaf. 
-   Stops early if func returns 0. */
-int
-ternary_traverse (ternary_tree p, void *d,
-		  int (*func) (/*@dependent@*/ /*@null@*/ void *node,
-			       /*@null@*/ void *d))
-{
-  if (!p)
-    return 1;
-  if (ternary_traverse (p->lokid, d, func) == 0)
-    return 0;
-  if (p->splitchar)
-    {
-      if (ternary_traverse (p->eqkid, d, func) == 0)
-	return 0;
-    }
-  else
-    if (func (p->eqkid, d) == 0)
-      return 0;
-  return ternary_traverse (p->hikid, d, func);
-}
diff --git a/src/ternary.h b/src/ternary.h
deleted file mode 100644
index dd5fb37d..00000000
--- a/src/ternary.h
+++ /dev/null
@@ -1,60 +0,0 @@
-/* ternary.h - Ternary Search Trees
-   Copyright 2001 Free Software Foundation, Inc.
-
-   Contributed by Daniel Berlin (dan@cgsoftware.com)
-
-
-   This program is free software; you can redistribute it and/or modify it
-   under the terms of the GNU General Public License as published by the
-   Free Software Foundation; either version 2, or (at your option) any
-   later version.
-
-   This program is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-   GNU General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-   USA.  */
-#ifndef YASM_TERNARY_H
-#define YASM_TERNARY_H
-/* Ternary search trees */
-
-typedef /*@null@*/ struct ternary_node_def *ternary_tree;
-
-typedef struct ternary_node_def
-{
-  char splitchar;
-  /*@null@*/ ternary_tree lokid;
-  /*@owned@*/ /*@null@*/ ternary_tree eqkid;
-  /*@null@*/ ternary_tree hikid;
-}
-ternary_node;
-
-/* Insert string S into tree P, associating it with DATA. 
-   Return the data in the tree associated with the string if it's
-   already there, and replace is 0.
-   Otherwise, replaces if it it exists, inserts if it doesn't, and
-   returns the data you passed in. */
-/*@dependent@*/ void *ternary_insert (ternary_tree *p, const char *s,
-				      void *data, int replace);
-
-/* Delete the ternary search tree rooted at P. 
-   Does NOT delete the data you associated with the strings. */
-void ternary_cleanup (/*@only@*/ ternary_tree p,
-		      void (*data_cleanup)(/*@dependent@*/ /*@null@*/
-					   void *d));
-
-/* Search the ternary tree for string S, returning the data associated
-   with it if found. */
-/*@dependent@*/ /*@null@*/ void *ternary_search (ternary_tree p,
-						 const char *s);
-
-/* Traverse over tree, calling callback function for each leaf. 
-   Stops early if func returns 0. */
-int ternary_traverse (ternary_tree p, /*@null@*/ void *d,
-		      int (*func) (/*@dependent@*/ /*@null@*/ void *node,
-				   /*@null@*/ void *d));
-#endif
-- 
2.40.0