mojoshader_common.c
changeset 858 d51537335896
parent 735 78c882b8c813
child 859 824d67791db0
--- a/mojoshader_common.c	Tue Feb 23 17:38:00 2010 -0500
+++ b/mojoshader_common.c	Wed Feb 24 01:21:21 2010 -0500
@@ -136,13 +136,22 @@
 
 
 // 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)
@@ -150,5 +159,146 @@
     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 ...