Formalized the compiler's string cache into a real API.

Moved the compiler and preprocessor to use it, and dumped their separate implementations of the same thing.
icculus · Feb 24, 2010 · 7fa864c · 7fa864c
1 parent e67427a
commit 7fa864c
Show file tree

Hide file tree

Showing 5 changed files with 216 additions and 206 deletions.
diff --git a/mojoshader_common.c b/mojoshader_common.c
@@ -136,19 +136,169 @@ int hash_remove(HashTable *table, const void *key)
 
 
 // this is djb's xor hashing function.
-uint32 hash_hash_string(const void *_sym)
+static inline uint32 hash_string_djbxor(const char *str, size_t len)
 {
-    register const char *sym = (const char *) _sym;
     register uint32 hash = 5381;
-    while (*sym)
-        hash = ((hash << 5) + hash) ^ *(sym++);
+    while (len--)
+        hash = ((hash << 5) + hash) ^ *(str++);
     return hash;
+} // hash_string_djbxor
+
+static inline uint32 hash_string(const char *str, size_t len)
+{
+    return hash_string_djbxor(str, len);
+} // hash_string
+
+uint32 hash_hash_string(const void *sym)
+{
+    return hash_string(sym, strlen(sym));
 } // hash_hash_string
 
 int hash_keymatch_string(const void *a, const void *b)
 {
     return (strcmp((const char *) a, (const char *) b) == 0);
 } // hash_keymatch_string
 
+
+// The string cache...
+
+typedef struct StringBucket
+{
+    char *string;
+    struct StringBucket *next;
+} StringBucket;
+
+struct StringCache
+{
+    StringBucket **hashtable;
+    uint32 table_size;
+    MOJOSHADER_malloc m;
+    MOJOSHADER_free f;
+    void *d;
+};
+
+const char *stringcache(StringCache *cache, const char *str)
+{
+    return stringcache_len(cache, str, strlen(str));
+} // stringcache
+
+const char *stringcache_len(StringCache *cache, const char *str,
+                             const unsigned int len)
+{
+    const uint8 hash = hash_string(str, len) & (cache->table_size-1);
+    StringBucket *bucket = cache->hashtable[hash];
+    StringBucket *prev = NULL;
+    while (bucket)
+    {
+        const char *bstr = bucket->string;
+        if ((strncmp(bstr, str, len) == 0) && (bstr[len] == 0))
+        {
+            // Matched! Move this to the front of the list.
+            if (prev != NULL)
+            {
+                assert(prev->next == bucket);
+                prev->next = bucket->next;
+                bucket->next = cache->hashtable[hash];
+                cache->hashtable[hash] = bucket;
+            } // if
+            return bstr; // already cached
+        } // if
+        prev = bucket;
+        bucket = bucket->next;
+    } // while
+
+    // no match, add to the table.
+    bucket = (StringBucket *) cache->m(sizeof (StringBucket), cache->d);
+    if (bucket == NULL)
+        return NULL;
+    bucket->string = (char *) cache->m(len + 1, cache->d);
+    if (bucket->string == NULL)
+    {
+        cache->f(bucket, cache->d);
+        return NULL;
+    } // if
+    memcpy(bucket->string, str, len);
+    bucket->string[len] = '\0';
+    bucket->next = cache->hashtable[hash];
+    cache->hashtable[hash] = bucket;
+    return bucket->string;
+} // stringcache_len
+
+const char *stringcache_fmt(StringCache *cache, const char *fmt, ...)
+{
+    char buf[128];  // use the stack if reasonable.
+    char *ptr = NULL;
+    int len = 0;  // number of chars, NOT counting null-terminator!
+    va_list ap;
+
+    va_start(ap, fmt);
+    len = vsnprintf(buf, sizeof (buf), fmt, ap);
+    va_end(ap);
+
+    if (len > sizeof (buf))
+    {
+        ptr = (char *) cache->m(len, cache->d);
+        if (ptr == NULL)
+            return NULL;
+
+        va_start(ap, fmt);
+        vsnprintf(ptr, len, fmt, ap);
+        va_end(ap);
+    } // if
+
+    const char *retval = stringcache_len(cache, ptr ? ptr : buf, len);
+    if (ptr != NULL)
+        cache->f(ptr, cache->d);
+
+    return retval;
+} // stringcache_fmt
+
+StringCache *stringcache_create(MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
+{
+    const uint32 initial_table_size = 256;
+    const size_t tablelen = sizeof (StringBucket *) * initial_table_size;
+    StringCache *cache = (StringCache *) m(sizeof (StringCache), d);
+    if (!cache)
+        return NULL;
+    memset(cache, '\0', sizeof (StringCache));
+
+    cache->hashtable = (StringBucket **) m(tablelen, d);
+    if (!cache->hashtable)
+    {
+        f(cache, d);
+        return NULL;
+    } // if
+    memset(cache->hashtable, '\0', tablelen);
+
+    cache->table_size = initial_table_size;
+    cache->m = m;
+    cache->f = f;
+    cache->d = d;
+    return cache;
+} // stringcache_create
+
+void stringcache_destroy(StringCache *cache)
+{
+    MOJOSHADER_free f = cache->f;
+    void *d = cache->d;
+    size_t i;
+
+    for (i = 0; i < cache->table_size; i++)
+    {
+        StringBucket *bucket = cache->hashtable[i];
+        cache->hashtable[i] = NULL;
+        while (bucket)
+        {
+            StringBucket *next = bucket->next;
+            f(bucket->string, d);
+            f(bucket, d);
+            bucket = next;
+        } // while
+    } // for
+
+    f(cache->hashtable, d);
+    f(cache, d);
+} // stringcache_destroy
+
 // end of mojoshader_common.c ...
 
diff --git a/mojoshader_compiler.c b/mojoshader_compiler.c
@@ -35,12 +35,6 @@ typedef union TokenData
     const char *string;
 } TokenData;
 
-typedef struct StringBucket
-{
-    char *string;
-    struct StringBucket *next;
-} StringBucket;
-
 
 // Structures that make up the parse tree...
 
@@ -547,7 +541,7 @@ typedef struct Context
     void *malloc_data;
     int error_count;
     ErrorList *errors;
-    StringBucket *string_hashtable[256];
+    StringCache *strcache;
     const char *sourcefile;  // current source file that we're parsing.
     unsigned int sourceline; // current line in sourcefile that we're parsing.
     UserTypeMap usertypes;
@@ -1430,93 +1424,6 @@ static int is_usertype(const Context *ctx, const char *token)
 } // is_usertype
 
 
-// !!! FIXME: sort of cut-and-paste from the preprocessor...
-
-// this is djb's xor hashing function.
-static inline uint32 hash_string_djbxor(const char *str, unsigned int len)
-{
-    register uint32 hash = 5381;
-    while (len--)
-        hash = ((hash << 5) + hash) ^ *(str++);
-    return hash;
-} // hash_string_djbxor
-
-static inline uint8 hash_string(const char *str, const unsigned int len)
-{
-    return (uint8) hash_string_djbxor(str, len);
-} // hash_string
-
-static const char *cache_string(Context *ctx, const char *str,
-                                const unsigned int len)
-{
-    const uint8 hash = hash_string(str, len);
-    StringBucket *bucket = ctx->string_hashtable[hash];
-    StringBucket *prev = NULL;
-    while (bucket)
-    {
-        const char *bstr = bucket->string;
-        if ((strncmp(bstr, str, len) == 0) && (bstr[len] == 0))
-        {
-            // Matched! Move this to the front of the list.
-            if (prev != NULL)
-            {
-                assert(prev->next == bucket);
-                prev->next = bucket->next;
-                bucket->next = ctx->string_hashtable[hash];
-                ctx->string_hashtable[hash] = bucket;
-            } // if
-            return bstr; // already cached
-        } // if
-        prev = bucket;
-        bucket = bucket->next;
-    } // while
-
-    // no match, add to the table.
-    bucket = (StringBucket *) Malloc(ctx, sizeof (StringBucket));
-    if (bucket == NULL)
-        return NULL;
-    bucket->string = (char *) Malloc(ctx, len + 1);
-    if (bucket->string == NULL)
-    {
-        Free(ctx, bucket);
-        return NULL;
-    } // if
-    memcpy(bucket->string, str, len);
-    bucket->string[len] = '\0';
-    bucket->next = ctx->string_hashtable[hash];
-    ctx->string_hashtable[hash] = bucket;
-    return bucket->string;
-} // cache_string
-
-static const char *cache_string_fmt(Context *ctx, const char *fmt, ...)
-{
-    char buf[128];  // use the stack if reasonable.
-    char *ptr = NULL;
-    int len = 0;  // number of chars, NOT counting null-terminator!
-    va_list ap;
-
-    va_start(ap, fmt);
-    len = vsnprintf(buf, sizeof (buf), fmt, ap);
-    va_end(ap);
-
-    if (len > sizeof (buf))
-    {
-        ptr = (char *) Malloc(ctx, len);
-        if (ptr == NULL)
-            return NULL;
-
-        va_start(ap, fmt);
-        vsnprintf(ptr, len, fmt, ap);
-        va_end(ap);
-    } // if
-
-    const char *retval = cache_string(ctx, ptr ? ptr : buf, len);
-    if (ptr != NULL)
-        Free(ctx, ptr);
-
-    return retval;
-} // cache_string_fmt
-
 // This is where the actual parsing happens. It's Lemon-generated!
 #define __MOJOSHADER_HLSL_COMPILER__ 1
 #include "mojoshader_parser_hlsl.h"
@@ -2434,7 +2341,7 @@ static int convert_to_lemon_token(Context *ctx, const char *token,
             #undef tokencmp
 
             // get a canonical copy of the string now, as we'll need it.
-            token = cache_string(ctx, token, tokenlen);
+            token = stringcache_len(ctx->strcache, token, tokenlen);
             if (is_usertype(ctx, token))
                 return TOKEN_HLSL_USERTYPE;
             return TOKEN_HLSL_IDENTIFIER;
@@ -2446,24 +2353,6 @@ static int convert_to_lemon_token(Context *ctx, const char *token,
     return 0;
 } // convert_to_lemon_token
 
-// !!! FIXME: unify this code with the string cache in the preprocessor.
-static void free_string_cache(Context *ctx)
-{
-    size_t i;
-    for (i = 0; i < STATICARRAYLEN(ctx->string_hashtable); i++)
-    {
-        StringBucket *bucket = ctx->string_hashtable[i];
-        ctx->string_hashtable[i] = NULL;
-        while (bucket)
-        {
-            StringBucket *next = bucket->next;
-            Free(ctx, bucket->string);
-            Free(ctx, bucket);
-            bucket = next;
-        } // while
-    } // for
-} // free_string_cache
-
 static void destroy_context(Context *ctx)
 {
     if (ctx != NULL)
@@ -2474,7 +2363,10 @@ static void destroy_context(Context *ctx)
         // !!! FIXME: free ctx->errors
         delete_compilation_unit(ctx, ctx->ast);
         destroy_usertypemap(ctx);
-        free_string_cache(ctx);
+
+        if (ctx->strcache)
+            stringcache_destroy(ctx->strcache);
+
         f(ctx, d);
     } // if
 } // destroy_context
@@ -2494,6 +2386,8 @@ static Context *build_context(MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
     ctx->malloc_data = d;
     //ctx->parse_phase = MOJOSHADER_PARSEPHASE_NOTSTARTED;
     create_usertypemap(ctx);  // !!! FIXME: check for failure.
+    ctx->strcache = stringcache_create(m, f, d);  // !!! FIXME: check for failure.
+
     return ctx;
 } // build_context
 
@@ -2541,13 +2435,15 @@ static void parse_source(Context *ctx, const char *filename,
         int j;
         for (j = 1; j <= 4; j++)
         {
+            // "float2"
             int len = snprintf(buf, sizeof (buf), "%s%d", types[i], j);
-            add_usertype(ctx, cache_string(ctx, buf, len));  // "float2"
+            add_usertype(ctx, stringcache_len(ctx->strcache, buf, len));
             int k;
             for (k = 1; k <= 4; k++)
             {
+                // "float2x2"
                 len = snprintf(buf, sizeof (buf), "%s%dx%d", types[i], j, k);
-                add_usertype(ctx, cache_string(ctx, buf, len));  // "float2x2"
+                add_usertype(ctx, stringcache_len(ctx->strcache, buf, len));
             } // for
         } // for
     } // for
@@ -2563,7 +2459,7 @@ static void parse_source(Context *ctx, const char *filename,
         } // if
 
         fname = preprocessor_sourcepos(pp, &ctx->sourceline);
-        ctx->sourcefile = fname ? cache_string(ctx, fname, strlen(fname)) : 0;
+        ctx->sourcefile = fname ? stringcache(ctx->strcache, fname) : 0;
 
         if (tokenval == TOKEN_BAD_CHARS)
         {
@@ -2591,7 +2487,7 @@ static void parse_source(Context *ctx, const char *filename,
             case TOKEN_HLSL_USERTYPE:
             case TOKEN_HLSL_STRING_LITERAL:
             case TOKEN_HLSL_IDENTIFIER:
-                data.string = cache_string(ctx, token, tokenlen);
+                data.string = stringcache_len(ctx->strcache, token, tokenlen);
                 break;
 
             default:

diff --git a/mojoshader_internal.h b/mojoshader_internal.h
@@ -172,6 +172,18 @@ int hash_find(const HashTable *table, const void *key, const void **_value);
 uint32 hash_hash_string(const void *sym);
 int hash_keymatch_string(const void *a, const void *b);
 
+
+// String caching...
+
+typedef struct StringCache StringCache;
+StringCache *stringcache_create(MOJOSHADER_malloc m,MOJOSHADER_free f,void *d);
+const char *stringcache(StringCache *cache, const char *str);
+const char *stringcache_len(StringCache *cache, const char *str,
+                            const unsigned int len);
+const char *stringcache_fmt(StringCache *cache, const char *fmt, ...);
+void stringcache_destroy(StringCache *cache);
+
+
 // This is the ID for a D3DXSHADER_CONSTANTTABLE in the bytecode comments.
 #define CTAB_ID 0x42415443  // 0x42415443 == 'CTAB'
 #define CTAB_SIZE 28  // sizeof (D3DXSHADER_CONSTANTTABLE).