Trying with a hashtable instead of a dumb structure.

1 files changed, 31 insertions, 94 deletions

diff --git a/mpq-fs.c b/mpq-fs.c
index ae9ed02..3a2a4b3 100644
--- a/mpq-fs.c
+++ b/mpq-fs.c
@@ -1,90 +1,50 @@
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
+#include "lookupa.h"
+#include "hashtab.h"
 #include "mpq-fs.h"
+#include "mpq-misc.h"
 
 #define MAX_FNAME 2048
 
-typedef struct directory_list_t {
-    struct directory_list_t * child;
-    char * name;
+#define INITIAL_HASH_SIZE 10
+
+typedef struct hash_entry_t {
     struct mpq_archive_t * mpq_a;
     int entry;
-    struct directory_list_t * next;
-} directory_list;
-
-static directory_list root_dir = {
-    NULL, "", NULL, -1, NULL
-};
-
-static directory_list * root = &root_dir;
+} hash_entry;
 
-static char * strtoupper(char * _str) {
+static char * strnormalize(char * _str) {
     char * str = _str;
     while (*str) {
         *str = toupper(*str);
+        if (*str == '/')
+            *str = '\\';
         str++;
     }
     return _str;
 }
 
-/*
- * The 'new' keyword is abusive: the function returns an existing entry if it matches, allowing overrites.
- */
-static directory_list * new_directory_list(directory_list * parent, struct mpq_archive_t * mpq_a, const char * name) {
-    directory_list * r;
-    
-    for (r = parent->child; r; r = r->next) {
-        if (!strcasecmp(r->name, name))
-            break;
-    }
-    
-    if (!r) {
-        r = (directory_list *) malloc(sizeof(directory_list));
-        r->child = NULL;
-        r->next = parent->child;
-        parent->child = r;
-        r->name = strtoupper(strdup(name));
-    }
-    r->mpq_a = mpq_a;
-    r->entry = -1;
-    
-    return r;
-}
+htab * hash_table = 0;
 
-/*
- * Recursively adds a new entry into our directory structure.
- */
-static directory_list * add_file_r(directory_list * parent, struct mpq_archive_t * mpq_a, char * fname, int entry) {
-    char * bs;
-    directory_list * r;
-    int tail = 0;
-    
-    bs = strchr(fname, '\\');
-    
-    if (bs) {
-        *bs = 0;
-    } else {
-        tail = 1;
-    }
-    if (!(r = new_directory_list(parent, mpq_a, fname)))
-        return NULL;
-    
-    if (tail) {
-        r->entry = entry;
-        return r;
-    }
-    
-    return add_file_r(r, mpq_a, bs + 1, entry);
-}
-
-static directory_list * add_file(struct mpq_archive_t * mpq_a, char * fname) {
+static void add_file(struct mpq_archive_t * mpq_a, char * fname) {
     int entry;
-    
+    char * nfname;
+
     if ((entry = mpqlib_find_hash_entry_by_name(mpq_a, fname, 0, 0)) < 0)
-        return NULL;
+        return;
     
-    return add_file_r(root, mpq_a, fname, entry);
+    if (!hash_table)
+        hash_table = hcreate(INITIAL_HASH_SIZE);
+
+    nfname = strnormalize(strdup(fname));    
+    hadd(hash_table, (uint8_t *) nfname, strlen(nfname), NULL);
+    if (!hstuff(hash_table)) {
+        hstuff(hash_table) = malloc(sizeof(hash_entry));
+    }
+    ((hash_entry *) hstuff(hash_table))->mpq_a = mpq_a;
+    ((hash_entry *) hstuff(hash_table))->entry = entry;
 }
 
 /*
@@ -143,39 +103,16 @@ void mpqlib_fs_attach_listfile(struct mpq_archive_t * mpq_a, const char * listfi
 /*
  * Recursively find a file.
  */
-static directory_list * find_file_r(directory_list * parent, char * fname) {
-    char * bs;
-    directory_list * r;
-    int tail = 0;
-    
-    bs = strchr(fname, '\\');
-    
-    if (bs) {
-        *bs = 0;
-    } else {
-        tail = 1;
-    }
-    
-    for (r = parent->child; r; r = r->next) {
-        if (!strcmp(fname, r->name)) {
-            if (tail) {
-                return r;
-            } else {
-                return find_file_r(r, bs + 1);
-            }
-        }
-    }
+static hash_entry * find_file(char * fname) {
+    if (!hfind(hash_table, (uint8_t *) fname, strlen(fname)))
+        return NULL;
     
-    return NULL;
-}
-
-static directory_list * find_file(char * fname) {
-    return find_file_r(root, fname);
+    return (hash_entry *) hstuff(hash_table);
 }
 
 struct mpq_file_t * mpqlib_fs_open(const char * _fname) {
-    char * fname = strtoupper(strdup(_fname));
-    directory_list * entry;
+    char * fname = strnormalize(strdup(_fname));
+    hash_entry * entry;
     
     entry = find_file(fname);