From: Dale Weiler <killfieldengine@gmail.com>
Date: Wed, 17 Apr 2013 10:51:33 +0000 (+0000)
Subject: Use hashtable for macro definitions in the preprocessor, this speeds up the search... 
X-Git-Tag: before-library~48
X-Git-Url: https://git.xonotic.org/?p=xonotic%2Fgmqcc.git;a=commitdiff_plain;h=0b0b6423bae15eae22685f9efc41d6efe70e8ae4;hp=4d394494b6fcbf144975acd3f1d311b63aba598f

Use hashtable for macro definitions in the preprocessor, this speeds up the search for them, and the removal of them making it O(1) instead of O(n). This also makes my 30 second xonotic compiles take only 13 seconds
---

diff --git a/ftepp.c b/ftepp.c
index a9500c4..320afc8 100644
--- a/ftepp.c
+++ b/ftepp.c
@@ -25,6 +25,7 @@
 #include "gmqcc.h"
 #include "lexer.h"
 
+#define HT_MACROS 1024
 typedef struct {
     bool on;
     bool was_on;
@@ -62,7 +63,8 @@ typedef struct ftepp_s {
 
     bool         output_on;
     ppcondition *conditions;
-    ppmacro    **macros;
+    /*ppmacro    **macros;*/
+    ht           macros; /* hashtable<string, ppmacro*> */
 
     char        *output_string;
 
@@ -261,6 +263,7 @@ static ftepp_t* ftepp_new()
     ftepp = (ftepp_t*)mem_a(sizeof(*ftepp));
     memset(ftepp, 0, sizeof(*ftepp));
 
+    ftepp->macros    = util_htnew(HT_MACROS);
     ftepp->output_on = true;
 
     return ftepp;
@@ -273,15 +276,21 @@ static void ftepp_flush_do(ftepp_t *self)
 
 static void ftepp_delete(ftepp_t *self)
 {
-    size_t i;
     ftepp_flush_do(self);
     if (self->itemname)
         mem_d(self->itemname);
     if (self->includename)
         vec_free(self->includename);
+
+    /*
     for (i = 0; i < vec_size(self->macros); ++i)
         ppmacro_delete(self->macros[i]);
+
     vec_free(self->macros);
+*/
+
+    util_htrem(self->macros, (void (*)(void*))&ppmacro_delete);
+
     vec_free(self->conditions);
     if (self->lex)
         lex_close(self->lex);
@@ -310,23 +319,12 @@ static void ftepp_update_output_condition(ftepp_t *ftepp)
 
 static ppmacro* ftepp_macro_find(ftepp_t *ftepp, const char *name)
 {
-    size_t i;
-    for (i = 0; i < vec_size(ftepp->macros); ++i) {
-        if (!strcmp(name, ftepp->macros[i]->name))
-            return ftepp->macros[i];
-    }
-    return NULL;
+    return util_htget(ftepp->macros, name);
 }
 
 static void ftepp_macro_delete(ftepp_t *ftepp, const char *name)
 {
-    size_t i;
-    for (i = 0; i < vec_size(ftepp->macros); ++i) {
-        if (!strcmp(name, ftepp->macros[i]->name)) {
-            vec_remove(ftepp->macros, i, 1);
-            return;
-        }
-    }
+    util_htrm(ftepp->macros, name, NULL);
 }
 
 static GMQCC_INLINE int ftepp_next(ftepp_t *ftepp)
@@ -516,8 +514,12 @@ static bool ftepp_define(ftepp_t *ftepp)
         return false;
     }
 
+#if 0
     if (ftepp->output_on)
         vec_push(ftepp->macros, macro);
+#endif
+    if (ftepp->output_on)
+        util_htset(ftepp->macros, macro->name, (void*)macro);
     else {
         ppmacro_delete(macro);
     }
@@ -1832,7 +1834,8 @@ void ftepp_add_define(ftepp_t *ftepp, const char *source, const char *name)
     lex_ctx ctx = { "__builtin__", 0 };
     ctx.file = source;
     macro = ppmacro_new(ctx, name);
-    vec_push(ftepp->macros, macro);
+    /*vec_push(ftepp->macros, macro);*/
+    util_htset(ftepp->macros, name, macro);
 }
 
 const char *ftepp_get(ftepp_t *ftepp)
diff --git a/gmqcc.h b/gmqcc.h
index 297f735..42e7714 100644
--- a/gmqcc.h
+++ b/gmqcc.h
@@ -417,10 +417,13 @@ typedef struct hash_set_t {
  * util_htdel(foo);
  */
 hash_table_t *util_htnew (size_t size);
+void          util_htrem (hash_table_t *ht, void (*callback)(void *data));
 void          util_htset (hash_table_t *ht, const char *key, void *value);
 void          util_htdel (hash_table_t *ht);
 size_t        util_hthash(hash_table_t *ht, const char *key);
 void          util_htseth(hash_table_t *ht, const char *key, size_t hash, void *value);
+void          util_htrmh (hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*));
+void          util_htrm  (hash_table_t *ht, const char *key, void (*cb)(void*));
 
 void         *util_htget (hash_table_t *ht, const char *key);
 void         *util_htgeth(hash_table_t *ht, const char *key, size_t hash);
diff --git a/util.c b/util.c
index 59be9bf..712a9ea 100644
--- a/util.c
+++ b/util.c
@@ -601,7 +601,7 @@ void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
  * Free all allocated data in a hashtable, this is quite the amount
  * of work.
  */
-void util_htdel(hash_table_t *ht) {
+void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
     size_t i = 0;
     for (; i < ht->size; i++) {
         hash_node_t *n = ht->table[i];
@@ -611,6 +611,8 @@ void util_htdel(hash_table_t *ht) {
         while (n) {
             if (n->key)
                 mem_d(n->key);
+            if (callback)
+                callback(n->value);
             p = n;
             n = n->next;
             mem_d(p);
@@ -622,6 +624,33 @@ void util_htdel(hash_table_t *ht) {
     mem_d(ht);
 }
 
+void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
+    hash_node_t **pair = &ht->table[bin];
+    hash_node_t *tmp;
+
+    while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
+        pair = &(*pair)->next;
+
+    tmp = *pair;
+    if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
+        return;
+
+    if (cb)
+        (*cb)(tmp->value);
+
+    *pair = tmp->next;
+    mem_d(tmp->key);
+    mem_d(tmp);
+}
+
+void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
+    util_htrmh(ht, key, util_hthash(ht, key), cb);
+}
+
+void util_htdel(hash_table_t *ht) {
+    util_htrem(ht, NULL);
+}
+
 /*
  * A basic implementation of a hash-set.  Unlike a hashtable, a hash
  * set doesn't maintain key-value pairs.  It simply maintains a key