strlist: use a hash table

Use a hash table to enforce uniqueness in a string list. It is still
an ordered list, however, and can be walked in insertion order.

Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>

7 files changed, 106 insertions, 160 deletions

diff --git a/asm/nasm.c b/asm/nasm.c
index 545a81b1..ce62b39a 100644
--- a/asm/nasm.c
+++ b/asm/nasm.c
@@ -75,7 +75,7 @@ struct forwrefinfo {            /* info held on forward refs. */
 };
 
 static void parse_cmdline(int, char **, int);
-static void assemble_file(const char *, StrList **);
+static void assemble_file(const char *, StrList *);
 static bool is_suppressed_warning(int severity);
 static bool skip_this_pass(int severity);
 static void nasm_verror_gnu(int severity, const char *fmt, va_list args);
@@ -309,9 +309,12 @@ static void emit_dependencies(StrList *list)
 {
     FILE *deps;
     int linepos, len;
-    StrList *l, *nl;
     bool wmake = (quote_for_make == quote_for_wmake);
     const char *wrapstr, *nulltarget;
+    struct strlist_entry *l;
+
+    if (!list)
+        return;
 
     wrapstr = wmake ? " &\n " : " \\\n ";
     nulltarget = wmake ? "\t%null\n" : "";
@@ -328,7 +331,7 @@ static void emit_dependencies(StrList *list)
     }
 
     linepos = fprintf(deps, "%s :", depend_target);
-    list_for_each(l, list) {
+    list_for_each(l, list->head) {
         char *file = quote_for_make(l->str);
         len = strlen(file);
         if (linepos + len > 62 && linepos > 1) {
@@ -341,15 +344,16 @@ static void emit_dependencies(StrList *list)
     }
     fprintf(deps, "\n\n");
 
-    list_for_each_safe(l, nl, list) {
+    list_for_each(l, list->head) {
         if (depend_emit_phony) {
             char *file = quote_for_make(l->str);
             fprintf(deps, "%s :\n%s\n", file, nulltarget);
             nasm_free(file);
         }
-        nasm_free(l);
     }
 
+    strlist_free(list);
+
     if (deps != stdout)
         fclose(deps);
 }
@@ -409,8 +413,6 @@ static void timestamp(void)
 
 int main(int argc, char **argv)
 {
-    StrList **depend_ptr;
-
     timestamp();
 
     iflag_set_default_cpu(&cpu);
@@ -494,7 +496,8 @@ int main(int argc, char **argv)
     /* define some macros dependent of command-line */
     define_macros_late();
 
-    depend_ptr = (depend_file || (operating_mode & OP_DEPEND)) ? &depend_list : NULL;
+    if (depend_file || (operating_mode & OP_DEPEND))
+        depend_list = strlist_allocate();
 
     if (!depend_target)
         depend_target = quote_for_make(outname);
@@ -505,7 +508,7 @@ int main(int argc, char **argv)
             if (depend_missing_ok)
                 preproc->include_path(NULL);    /* "assume generated" */
 
-            preproc->reset(inname, 0, depend_ptr);
+            preproc->reset(inname, 0, depend_list);
             ofile = NULL;
             while ((line = preproc->getline()))
                 nasm_free(line);
@@ -528,7 +531,7 @@ int main(int argc, char **argv)
             location.known = false;
 
             /* pass = 1; */
-            preproc->reset(inname, 3, depend_ptr);
+            preproc->reset(inname, 3, depend_list);
 
 	    /* Revert all warnings to the default state */
 	    memcpy(warning_state, warning_state_init, sizeof warning_state);
@@ -570,7 +573,7 @@ int main(int argc, char **argv)
         ofmt->init();
         dfmt->init();
 
-        assemble_file(inname, depend_ptr);
+        assemble_file(inname, depend_list);
 
         if (!terminate_after_phase) {
             ofmt->cleanup();
@@ -1379,7 +1382,7 @@ static void parse_cmdline(int argc, char **argv, int pass)
     }
 }
 
-static void assemble_file(const char *fname, StrList **depend_ptr)
+static void assemble_file(const char *fname, StrList *depend_list)
 {
     char *line;
     insn output_ins;
@@ -1431,7 +1434,7 @@ static void assemble_file(const char *fname, StrList **depend_ptr)
             location.known = true;
         ofmt->reset();
         switch_segment(ofmt->section(NULL, pass2, &globalbits));
-        preproc->reset(fname, pass1, pass1 == 2 ? depend_ptr : NULL);
+        preproc->reset(fname, pass1, pass1 == 2 ? depend_list : NULL);
 
 	/* Revert all warnings to the default state */
 	memcpy(warning_state, warning_state_init, sizeof warning_state);
diff --git a/asm/preproc-nop.c b/asm/preproc-nop.c
index ee690063..94614dd1 100644
--- a/asm/preproc-nop.c
+++ b/asm/preproc-nop.c
@@ -63,7 +63,7 @@ static void nop_init(void)
     /* Nothing to do */
 }
 
-static void nop_reset(const char *file, int pass, StrList **deplist)
+static void nop_reset(const char *file, int pass, StrList *deplist)
 {
     src_set(0, file);
     nop_lineinc = 1;
@@ -73,7 +73,7 @@ static void nop_reset(const char *file, int pass, StrList **deplist)
 	nasm_fatal_fl(ERR_NOFILE, "unable to open input file `%s'", file);
     (void)pass;                 /* placate compilers */
 
-    nasm_add_string_to_strlist(deplist, file);
+    strlist_add_string(deplist, file);
 }
 
 static char *nop_getline(void)
@@ -170,7 +170,7 @@ static void nop_pre_command(const char *what, char *string)
     (void)string;
 }
 
-static void nop_include_path(char *path)
+static void nop_include_path(const char *path)
 {
     (void)path;
 }
diff --git a/asm/preproc.c b/asm/preproc.c
index 6cae4a7a..0ae712a9 100644
--- a/asm/preproc.c
+++ b/asm/preproc.c
@@ -91,7 +91,6 @@ typedef struct Blocks Blocks;
 typedef struct Line Line;
 typedef struct Include Include;
 typedef struct Cond Cond;
-typedef struct IncPath IncPath;
 
 /*
  * Note on the storage of both SMacro and MMacros: the hash table
@@ -277,16 +276,6 @@ struct Include {
 };
 
 /*
- * Include search path. This is simply a list of strings which get
- * prepended, in turn, to the name of an include file, in an
- * attempt to find the file if it's not in the current directory.
- */
-struct IncPath {
-    IncPath *next;
-    char *path;
-};
-
-/*
  * File real name hash, so we don't have to re-search the include
  * path for every pass (and potentially more than that if a file
  * is used more than once.)
@@ -397,10 +386,10 @@ static int LocalOffset = 0;
 
 static Context *cstk;
 static Include *istk;
-static IncPath *ipath = NULL;
+static StrList *ipath;
 
 static int pass;            /* HACK: pass 0 = generate dependencies only */
-static StrList **dephead;
+static StrList *deplist;
 
 static uint64_t unique;     /* unique identifier numbers */
 
@@ -1509,43 +1498,37 @@ enum incopen_mode {
 };
 
 /* This is conducts a full pathname search */
-static FILE *inc_fopen_search(const char *file, StrList **slpath,
+static FILE *inc_fopen_search(const char *file, char **slpath,
                               enum incopen_mode omode, enum file_flags fmode)
 {
     FILE *fp;
-    char *prefix = "";
-    const IncPath *ip = ipath;
-    int len;
-    StrList *sl;
+    const char *prefix = "";
+    const struct strlist_entry *ip = ipath->head;
     char *sp;
     bool found;
 
     while (1) {
         sp = nasm_catfile(prefix, file);
-        len = strlen(sp) + 1;
-        sl = nasm_malloc(len + sizeof sl->next);
-        memcpy(sl->str, sp, len);
-        sl->next = NULL;
-        nasm_free(sp);
-
         if (omode == INC_PROBE) {
             fp = NULL;
-            found = nasm_file_exists(sl->str);
+            found = nasm_file_exists(sp);
         } else {
-            fp = nasm_open_read(sl->str, fmode);
+            fp = nasm_open_read(sp, fmode);
             found = (fp != NULL);
         }
         if (found) {
-            *slpath = sl;
+            *slpath = sp;
             return fp;
         }
 
-        nasm_free(sl);
+        nasm_free(sp);
 
-        if (!ip)
+        if (!ip) {
+            *slpath = NULL;
             return NULL;
+        }
 
-        prefix = ip->path;
+        prefix = ip->str;
         ip = ip->next;
     }
 }
@@ -1555,12 +1538,11 @@ static FILE *inc_fopen_search(const char *file, StrList **slpath,
  * considering the include path.
  */
 static FILE *inc_fopen(const char *file,
-                       StrList **dhead,
+                       StrList *dhead,
                        const char **found_path,
                        enum incopen_mode omode,
                        enum file_flags fmode)
 {
-    StrList *sl;
     struct hash_insert hi;
     void **hp;
     char *path;
@@ -1570,52 +1552,30 @@ static FILE *inc_fopen(const char *file,
     if (hp) {
         path = *hp;
         if (path || omode != INC_NEEDED) {
-            nasm_add_string_to_strlist(dhead, path ? path : file);
+            strlist_add_string(dhead, path ? path : file);
         }
     } else {
         /* Need to do the actual path search */
-        size_t file_len;
-
-        sl = NULL;
-        fp = inc_fopen_search(file, &sl, omode, fmode);
-
-        file_len = strlen(file);
-
-        if (!sl) {
-            /* Store negative result for this file */
-            sl = nasm_malloc(file_len + 1 + sizeof sl->next);
-            memcpy(sl->str, file, file_len+1);
-            sl->next = NULL;
-            file = sl->str;
-            path = NULL;
-        } else  {
-            path = sl->str;
-            file = strchr(path, '\0') - file_len;
-        }
+        fp = inc_fopen_search(file, &path, omode, fmode);
 
-        hash_add(&hi, file, path); /* Positive or negative result */
+        /* Positive or negative result */
+        hash_add(&hi, nasm_strdup(file), path);
 
         /*
-         * Add file to dependency path. The in_list() is needed
-         * in case the file was already added with %depend.
+         * Add file to dependency path.
          */
         if (path || omode != INC_NEEDED)
-            nasm_add_to_strlist(dhead, sl);
+            strlist_add_string(dhead, file);
     }
 
     if (!path) {
         if (omode == INC_NEEDED)
             nasm_fatal("unable to open include file `%s'", file);
-
-        if (found_path)
-            *found_path = NULL;
-
-        return NULL;
+    } else {
+        if (!fp && omode != INC_PROBE)
+            fp = nasm_open_read(path, fmode);
     }
 
-    if (!fp && omode != INC_PROBE)
-        fp = nasm_open_read(path, fmode);
-
     if (found_path)
         *found_path = path;
 
@@ -2598,7 +2558,7 @@ static int do_directive(Token *tline, char **output)
         p = t->text;
         if (t->type != TOK_INTERNAL_STRING)
             nasm_unquote_cstr(p, i);
-        nasm_add_string_to_strlist(dephead, p);
+        strlist_add_string(deplist, p);
         free_tlist(origline);
         return DIRECTIVE_FOUND;
 
@@ -2622,7 +2582,7 @@ static int do_directive(Token *tline, char **output)
         inc->next = istk;
         inc->conds = NULL;
         found_path = NULL;
-        inc->fp = inc_fopen(p, dephead, &found_path,
+        inc->fp = inc_fopen(p, deplist, &found_path,
                             pass == 0 ? INC_OPTIONAL : INC_NEEDED, NF_TEXT);
         if (!inc->fp) {
             /* -MG given but file not found */
@@ -4972,7 +4932,7 @@ static void pp_verror(int severity, const char *fmt, va_list arg)
 }
 
 static void
-pp_reset(const char *file, int apass, StrList **deplist)
+pp_reset(const char *file, int apass, StrList *dep_list)
 {
     Token *t;
 
@@ -4993,6 +4953,7 @@ pp_reset(const char *file, int apass, StrList **deplist)
     nested_rep_count = 0;
     init_macros();
     unique = 0;
+    deplist = dep_list;
 
     if (tasm_compatible_mode)
         pp_add_stdmac(nasm_stdmac_tasm);
@@ -5015,9 +4976,8 @@ pp_reset(const char *file, int apass, StrList **deplist)
      */
     pass = apass > 2 ? 2 : apass;
 
-    dephead = deplist;
-    nasm_add_string_to_strlist(dephead, file);
-    
+    strlist_add_string(deplist, file);
+
     /*
      * Define the __PASS__ macro.  This is defined here unlike
      * all the other builtins, because it is special -- it varies between
@@ -5033,6 +4993,7 @@ pp_reset(const char *file, int apass, StrList **deplist)
 static void pp_init(void)
 {
     hash_init(&FileHash, HASH_MEDIUM);
+    ipath = strlist_allocate();
 }
 
 static char *pp_getline(void)
@@ -5296,36 +5257,20 @@ static void pp_cleanup(int pass)
         ctx_pop();
     src_set_fname(NULL);
     if (pass == 0) {
-        IncPath *i;
         free_llist(predef);
         predef = NULL;
         delete_Blocks();
         freeTokens = NULL;
-        while ((i = ipath)) {
-            ipath = i->next;
-            if (i->path)
-                nasm_free(i->path);
-            nasm_free(i);
-        }
+        strlist_free(ipath);
     }
 }
 
-static void pp_include_path(char *path)
+static void pp_include_path(const char *path)
 {
-    IncPath *i;
-
-    i = nasm_malloc(sizeof(IncPath));
-    i->path = path ? nasm_strdup(path) : NULL;
-    i->next = NULL;
+    if (!path)
+        path = "";
 
-    if (ipath) {
-        IncPath *j = ipath;
-        while (j->next)
-            j = j->next;
-        j->next = i;
-    } else {
-        ipath = i;
-    }
+    strlist_add_string(ipath, path);
 }
 
 static void pp_pre_include(char *fname)
diff --git a/include/nasm.h b/include/nasm.h
index fc56c3e3..463b91bf 100644
--- a/include/nasm.h
+++ b/include/nasm.h
@@ -336,7 +336,7 @@ struct preproc_ops {
      * of the pass, an error reporting function, an evaluator
      * function, and a listing generator to talk to.
      */
-    void (*reset)(const char *file, int pass, StrList **deplist);
+    void (*reset)(const char *file, int pass, StrList *deplist);
 
     /*
      * Called to fetch a line of preprocessed source. The line
@@ -362,7 +362,7 @@ struct preproc_ops {
     void (*pre_command)(const char *what, char *str);
 
     /* Include path from command line */
-    void (*include_path)(char *path);
+    void (*include_path)(const char *path);
 
     /* Unwind the macro stack when printing an error message */
     void (*error_list_macros)(int severity);
diff --git a/include/strlist.h b/include/strlist.h
index e00fc1f6..caf11e18 100644
--- a/include/strlist.h
+++ b/include/strlist.h
@@ -1,6 +1,6 @@
 /* ----------------------------------------------------------------------- *
  *
- *   Copyright 1996-2016 The NASM Authors - All Rights Reserved
+ *   Copyright 1996-2018 The NASM Authors - All Rights Reserved
  *   See the file AUTHORS included with the NASM distribution for
  *   the specific copyright holders.
  *
@@ -39,17 +39,22 @@
 #define NASM_STRLIST_H
 
 #include "compiler.h"
-
-#include <string.h>
-
 #include "nasmlib.h"
+#include "hashtbl.h"
+
+struct strlist_entry {
+    struct strlist_entry *next;
+    size_t len;
+    char str[1];
+};
 
 typedef struct string_list {
-    struct string_list  *next;
-    char                str[1];
+    struct hash_table hash;
+    struct strlist_entry *head, **tailp;
 } StrList;
 
-bool nasm_add_to_strlist(StrList **head, StrList *entry);
-bool nasm_add_string_to_strlist(StrList **head, const char *str);
+StrList safe_alloc *strlist_allocate(void);
+bool strlist_add_string(StrList *list, const char *str);
+void strlist_free(StrList *list);
 
 #endif /* NASM_STRLIST_H */
diff --git a/nasmlib/strlist.c b/nasmlib/strlist.c
index cf475278..8a8213ae 100644
--- a/nasmlib/strlist.c
+++ b/nasmlib/strlist.c
@@ -1,6 +1,6 @@
 /* ----------------------------------------------------------------------- *
  *
- *   Copyright 1996-2016 The NASM Authors - All Rights Reserved
+ *   Copyright 1996-2018 The NASM Authors - All Rights Reserved
  *   See the file AUTHORS included with the NASM distribution for
  *   the specific copyright holders.
  *
@@ -32,69 +32,62 @@
  * ----------------------------------------------------------------------- */
 
 /*
- * strlist.c - simple linked list of strings
+ * strlist.c - list of unique, ordered strings
  */
 
-#include "compiler.h"
-
-#include <string.h>
-
 #include "strlist.h"
 
-static inline StrList *nasm_str_to_strlist(const char *str)
+/*
+ * Create a string list
+ */
+StrList *strlist_allocate(void)
 {
-    size_t l = strlen(str) + 1;
-    StrList *sl = nasm_malloc(l + sizeof sl->next);
+    StrList *list;
 
-    memcpy(sl->str, str, l);
-    sl->next = NULL;
+    nasm_new(list);
+    hash_init(&list->hash, HASH_MEDIUM);
+    list->tailp = &list->head;
 
-    return sl;
+    return list;
 }
 
 /*
- * Append a string list entry to a string list if and only if it isn't
+ * Append a string to a string list if and only if it isn't
  * already there.  Return true if it was added.
  */
-bool nasm_add_to_strlist(StrList **head, StrList *entry)
+bool strlist_add_string(StrList *list, const char *str)
 {
-    StrList *list;
+    struct hash_insert hi;
+    struct strlist_entry *sl;
+    size_t l;
 
-    if (!head)
+    if (!list)
         return false;
 
-    list = *head;
-    while (list) {
-        if (!strcmp(list->str, entry->str))
-            return false;
-        head = &list->next;
-        list = list->next;
-    }
+    if (hash_find(&list->hash, str, &hi))
+        return false;           /* Already present */
+
+    l = strlen(str);
 
-    *head = entry;
-    entry->next = NULL;
+    sl = nasm_malloc(sizeof(struct strlist_entry) + l);
+    sl->len = l;
+    memcpy(sl->str, str, l+1);
+    sl->next = NULL;
+    *list->tailp = sl;
+    list->tailp = &sl->next;
+
+    hash_add(&hi, sl->str, (void *)sl);
     return true;
 }
 
 /*
- * Append a string to a string list if and only if it isn't
- * already there.  Return true if it was added.
+ * Free a string list
  */
-bool nasm_add_string_to_strlist(StrList **head, const char *str)
+void strlist_free(StrList *list)
 {
-    StrList *list;
+    if (!list)
+        return;
 
-    if (!head)
-        return false;
-
-    list = *head;
-    while (list) {
-        if (!strcmp(list->str, str))
-            return false;
-        head = &list->next;
-        list = list->next;
-    }
-
-    *head = nasm_str_to_strlist(str);
-    return true;
+    hash_free_all(&list->hash, false);
+    nasm_free(list);
 }
diff --git a/output/outobj.c b/output/outobj.c
index f3880a4b..35938823 100644
--- a/output/outobj.c
+++ b/output/outobj.c
@@ -1965,7 +1965,7 @@ static void obj_write_file(void)
     struct ExpDef *export;
     int lname_idx;
     ObjRecord *orp;
-    const StrList *depfile;
+    const struct strlist_entry *depfile;
     const bool debuginfo = (dfmt == &borland_debug_form);
 
     /*
@@ -1988,7 +1988,7 @@ static void obj_write_file(void)
      * Output file dependency information
      */
     if (!obj_nodepend) {
-        list_for_each(depfile, depend_list) {
+        list_for_each(depfile, depend_list->head) {
             uint32_t ts;
 
             ts = obj_file_timestamp(depfile->str);