X-Git-Url: https://git.xonotic.org/?p=xonotic%2Fgmqcc.git;a=blobdiff_plain;f=util.c;h=92a99f76e463fb1e1d6289d53c629aa04cabfb21;hp=b2b092d13828a7be9609fc08b68b380c46071f86;hb=d97e032fcfe6e1c1a080aa66f435426330e8585e;hpb=35ba2dcaf99f4352869ad8519c35fefb1c53dd93

diff --git a/util.c b/util.c
index b2b092d..92a99f7 100644
--- a/util.c
+++ b/util.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012
+ * Copyright (C) 2012, 2013
  *     Dale Weiler
  *     Wolfgang Bumiller
  *
@@ -54,20 +54,18 @@ void *util_memory_a(size_t byte, unsigned int line, const char *file) {
         mem_start->prev = info;
     mem_start = info;
 
-    util_debug("MEM", "allocation:   % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
     mem_at++;
     mem_ab += info->byte;
 
     return data;
 }
 
-void util_memory_d(void *ptrn, unsigned int line, const char *file) {
+void util_memory_d(void *ptrn) {
     struct memblock_t *info = NULL;
 
     if (!ptrn) return;
     info = ((struct memblock_t*)ptrn - 1);
 
-    util_debug("MEM", "released:     % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
     mem_db += info->byte;
     mem_dt++;
 
@@ -89,18 +87,16 @@ void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file
     if (!ptrn)
         return util_memory_a(byte, line, file);
     if (!byte) {
-        util_memory_d(ptrn, line, file);
+        util_memory_d(ptrn);
         return NULL;
     }
 
     oldinfo = ((struct memblock_t*)ptrn - 1);
     newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
 
-    util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
-
     /* new data */
     if (!newinfo) {
-        util_memory_d(oldinfo+1, line, file);
+        util_memory_d(oldinfo+1);
         return NULL;
     }
 
@@ -573,6 +569,220 @@ void util_htdel(hash_table_t *ht) {
     mem_d(ht);
 }
 
+/*
+ * A basic implementation of a hash-set.  Unlike a hashtable, a hash
+ * set doesn't maintain key-value pairs.  It simply maintains a key
+ * that can be set, removed, and checked for.
+ *
+ * See EXPOSED interface comment below 
+ */
+#define GMQCC_HASHSET_PRIME0 0x0049
+#define GMQCC_HASHSET_PRIME1 0x1391
+
+static int util_hsput(hash_set_t *set, void *item) {
+    size_t hash = (size_t)item; /* shouldn't drop the bits */
+    size_t iter;
+
+    /* a == 0 || a == 1 */
+    if (hash >> 1)
+        return -1;
+
+    iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash);
+
+    /* while (set->items[iter] != 0 && set->items[iter] != 1) */
+    while  (!(set->items[iter] >> 1)) {
+        if (set->items[iter] == hash)
+            return 0;
+
+        iter = set->mask & (iter + GMQCC_HASHSET_PRIME1);
+    }
+
+    set->total ++;
+    set->items[iter] = hash;
+
+    return 1;
+}
+
+static void util_hsupdate(hash_set_t *set) {
+    size_t *old;
+    size_t  end;
+    size_t  itr;
+
+    /* time to rehash? */
+    if ((float)set->total >= (size_t)((double)set->capacity * 0.85)) {
+        old = set->items;
+        end = set->capacity;
+
+        set->bits ++;
+        set->capacity = (size_t)(1 << set->bits);
+        set->mask     = set->capacity - 1;
+        set->items    = mem_a(set->capacity * sizeof(size_t));
+        set->total    = 0;
+
+        /*assert(set->items);*/
+
+        /*
+         * this shouldn't be slow?  if so unroll it a little perhaps
+         * (shouldn't be though)
+         */
+        for (itr = 0; itr < end; itr++)
+            util_hsput(set, (void*)old[itr]);
+
+        mem_d(old);
+    }
+}
+
+/*
+ * EXPOSED interface: all of these functions are exposed to the outside
+ * for use. The stuff above is static because it's the "internal" mechanics
+ * for syncronizing the set for updating, and putting data into the set.
+ */   
+int util_hsadd(hash_set_t *set, void *item) {
+    int run = util_hsput(set, item); /* inlined */
+    util_hsupdate(set);
+
+    return run;
+}
+
+/* remove item in set */
+int util_hsrem(hash_set_t *set, void *item) {
+    size_t hash = (size_t)item;
+    size_t iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash);
+
+    while  (set->items[iter]) {
+        if (set->items[iter] == hash) {
+            set->items[iter] =  1;
+            set->total       --;
+
+            return 1;
+        }
+        iter = set->mask & (iter + GMQCC_HASHSET_PRIME1);
+    }
+
+    return 0;
+}
+
+/* check if item is set */
+int util_hshas(hash_set_t *set, void *item) {
+    size_t hash = (size_t)item;
+    size_t iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash);
+
+    while  (set->items[iter]) {
+        if (set->items[iter] == hash)
+            return 1;
+
+        iter = set->mask & (iter + GMQCC_HASHSET_PRIME1);
+    }
+
+    return 0;
+}
+
+hash_set_t *util_hsnew(void) {
+    hash_set_t *set;
+
+    if (!(set = mem_a(sizeof(hash_set_t))))
+        return NULL;
+
+    set->bits     = 3;
+    set->total    = 0;
+    set->capacity = (size_t)(1 << set->bits);
+    set->mask     = set->capacity - 1;
+    set->items    = mem_a(set->capacity * sizeof(size_t));
+
+    if (!set->items) {
+        util_hsdel(set);
+        return NULL;
+    }
+
+    return set;
+}
+
+void util_hsdel(hash_set_t *set) {
+    if (!set) return;
+
+    if (set->items)
+        mem_d(set->items);
+
+    mem_d(set);
+}
+#undef GMQCC_HASHSET_PRIME0
+#undef GMQCC_HASHSET_PRIME1
+
+
+/*
+ * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
+ * exists, otherwise compiler error.
+ *
+ * TODO: fix for MSVC ....  
+ */
+int util_vasprintf(char **dat, const char *fmt, va_list args) {
+    int   ret;
+    int   len;
+    char *tmp = NULL;
+
+    /*
+     * For visuals tido _vsnprintf doesn't tell you the length of a
+     * formatted string if it overflows. However there is a MSVC
+     * intrinsic (which is documented wrong) called _vcsprintf which
+     * will return the required amount to allocate.
+     */     
+    #ifdef _MSC_VER
+        char *str;
+        if ((len = _vscprintf(fmt, args)) < 0) {
+            *dat = NULL;
+            return -1;
+        }
+
+        tmp = mem_a(len + 1);
+        if ((ret = _vsnprintf(tmp, len+1, fmt, args)) != len) {
+            mem_d(tmp);
+            *dat = NULL;
+            return -1;
+        }
+        *dat = tmp;
+        return len;
+    #else
+        /*
+         * For everything else we have a decent conformint vsnprintf that
+         * returns the number of bytes needed.  We give it a try though on
+         * a short buffer, since efficently speaking, it could be nice to
+         * above a second vsnprintf call.
+         */
+        char    buf[128];
+        va_list cpy;
+        va_copy(cpy, args);
+        len = vsnprintf(buf, sizeof(buf), fmt, cpy);
+        va_end (cpy);
+
+        if (len < (int)sizeof(buf)) {
+            *dat = util_strdup(buf);
+            return len;
+        }
+
+        /* not large enough ... */
+        tmp = mem_a(len + 1);
+        if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
+            mem_d(tmp);
+            *dat = NULL;
+            return -1;
+        }
+
+        *dat = tmp;
+        return len;
+    #endif
+    /* never reached ... */
+    return -1;
+}
+int util_asprintf(char **ret, const char *fmt, ...) {
+    va_list  args;
+    int      read;
+    va_start(args, fmt);
+    read = util_vasprintf(ret, fmt, args);
+    va_end  (args);
+
+    return read;
+}
+
 /*
  * Implementation of the Mersenne twister PRNG (pseudo random numer
  * generator).  Implementation of MT19937.  Has a period of 2^19937-1