Added extra needed files

1 files changed, 351 insertions, 0 deletions

diff --git a/mesalib/src/gallium/auxiliary/util/u_cache.c b/mesalib/src/gallium/auxiliary/util/u_cache.c
new file mode 100644
index 000000000..215236818
--- /dev/null
+++ b/mesalib/src/gallium/auxiliary/util/u_cache.c
@@ -0,0 +1,351 @@
+/**************************************************************************

+ *

+ * Copyright 2008 VMware, Inc.

+ * All Rights Reserved.

+ *

+ * Permission is hereby granted, free of charge, to any person obtaining a

+ * copy of this software and associated documentation files (the

+ * "Software"), to deal in the Software without restriction, including

+ * without limitation the rights to use, copy, modify, merge, publish,

+ * distribute, sub license, and/or sell copies of the Software, and to

+ * permit persons to whom the Software is furnished to do so, subject to

+ * the following conditions:

+ *

+ * The above copyright notice and this permission notice (including the

+ * next paragraph) shall be included in all copies or substantial portions

+ * of the Software.

+ *

+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS

+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.

+ * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR

+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,

+ * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE

+ * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

+ *

+ **************************************************************************/

+

+/**

+ * @file

+ * Improved cache implementation.

+ *

+ * Fixed size array with linear probing on collision and LRU eviction

+ * on full.

+ * 

+ * @author Jose Fonseca <jfonseca@vmware.com>

+ */

+

+

+#include "pipe/p_compiler.h"

+#include "util/u_debug.h"

+

+#include "util/u_math.h"

+#include "util/u_memory.h"

+#include "util/u_cache.h"

+#include "util/u_simple_list.h"

+

+

+struct util_cache_entry

+{

+   enum { EMPTY = 0, FILLED, DELETED } state;

+   uint32_t hash;

+

+   struct util_cache_entry *next;

+   struct util_cache_entry *prev;

+

+   void *key;

+   void *value;

+   

+#ifdef DEBUG

+   unsigned count;

+#endif

+};

+

+

+struct util_cache

+{

+   /** Hash function */

+   uint32_t (*hash)(const void *key);

+   

+   /** Compare two keys */

+   int (*compare)(const void *key1, const void *key2);

+

+   /** Destroy a (key, value) pair */

+   void (*destroy)(void *key, void *value);

+

+   uint32_t size;

+   

+   struct util_cache_entry *entries;

+   

+   unsigned count;

+   struct util_cache_entry lru;

+};

+

+static void

+ensure_sanity(const struct util_cache *cache);

+

+#define CACHE_DEFAULT_ALPHA 2

+

+struct util_cache *

+util_cache_create(uint32_t (*hash)(const void *key),

+                  int (*compare)(const void *key1, const void *key2),

+                  void (*destroy)(void *key, void *value),

+                  uint32_t size)

+{

+   struct util_cache *cache;

+   

+   cache = CALLOC_STRUCT(util_cache);

+   if(!cache)

+      return NULL;

+   

+   cache->hash = hash;

+   cache->compare = compare;

+   cache->destroy = destroy;

+

+   make_empty_list(&cache->lru);

+

+   size *= CACHE_DEFAULT_ALPHA;

+   cache->size = size;

+   

+   cache->entries = CALLOC(size, sizeof(struct util_cache_entry));

+   if(!cache->entries) {

+      FREE(cache);

+      return NULL;

+   }

+   

+   ensure_sanity(cache);

+   return cache;

+}

+

+

+static struct util_cache_entry *

+util_cache_entry_get(struct util_cache *cache,

+                     uint32_t hash,

+                     const void *key)

+{

+   struct util_cache_entry *first_unfilled = NULL;

+   uint32_t index = hash % cache->size;

+   uint32_t probe;

+

+   /* Probe until we find either a matching FILLED entry or an EMPTY

+    * slot (which has never been occupied).

+    *

+    * Deleted or non-matching slots are not indicative of completion

+    * as a previous linear probe for the same key could have continued

+    * past this point.

+    */

+   for (probe = 0; probe < cache->size; probe++) {

+      uint32_t i = (index + probe) % cache->size;

+      struct util_cache_entry *current = &cache->entries[i];

+

+      if (current->state == FILLED) {

+         if (current->hash == hash &&

+             cache->compare(key, current->key) == 0)

+            return current;

+      }

+      else {

+         if (!first_unfilled)

+            first_unfilled = current;

+

+         if (current->state == EMPTY)

+            return first_unfilled;

+      }

+   }

+

+   return NULL;

+}

+

+static INLINE void

+util_cache_entry_destroy(struct util_cache *cache,

+                         struct util_cache_entry *entry)

+{

+   void *key = entry->key;

+   void *value = entry->value;

+   

+   entry->key = NULL;

+   entry->value = NULL;

+   

+   if (entry->state == FILLED) {

+      remove_from_list(entry);

+      cache->count--;

+

+      if(cache->destroy)

+         cache->destroy(key, value);

+

+      entry->state = DELETED;

+   }

+}

+

+

+void

+util_cache_set(struct util_cache *cache,

+               void *key,

+               void *value)

+{

+   struct util_cache_entry *entry;

+   uint32_t hash = cache->hash(key);

+

+   assert(cache);

+   if (!cache)

+      return;

+

+   entry = util_cache_entry_get(cache, hash, key);

+   if (!entry)

+      entry = cache->lru.prev;

+

+   if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)

+      util_cache_entry_destroy(cache, cache->lru.prev);

+

+   util_cache_entry_destroy(cache, entry);

+   

+#ifdef DEBUG

+   ++entry->count;

+#endif

+   

+   entry->key = key;

+   entry->hash = hash;

+   entry->value = value;

+   entry->state = FILLED;

+   insert_at_head(&cache->lru, entry);

+   cache->count++;

+

+   ensure_sanity(cache);

+}

+

+

+void *

+util_cache_get(struct util_cache *cache, 

+               const void *key)

+{

+   struct util_cache_entry *entry;

+   uint32_t hash = cache->hash(key);

+

+   assert(cache);

+   if (!cache)

+      return NULL;

+

+   entry = util_cache_entry_get(cache, hash, key);

+   if (!entry)

+      return NULL;

+

+   if (entry->state == FILLED)

+      move_to_head(&cache->lru, entry);

+   

+   return entry->value;

+}

+

+

+void 

+util_cache_clear(struct util_cache *cache)

+{

+   uint32_t i;

+

+   assert(cache);

+   if (!cache)

+      return;

+

+   for(i = 0; i < cache->size; ++i) {

+      util_cache_entry_destroy(cache, &cache->entries[i]);

+      cache->entries[i].state = EMPTY;

+   }

+

+   assert(cache->count == 0);

+   assert(is_empty_list(&cache->lru));

+   ensure_sanity(cache);

+}

+

+

+void

+util_cache_destroy(struct util_cache *cache)

+{

+   assert(cache);

+   if (!cache)

+      return;

+

+#ifdef DEBUG

+   if(cache->count >= 20*cache->size) {

+      /* Normal approximation of the Poisson distribution */

+      double mean = (double)cache->count/(double)cache->size;

+      double stddev = sqrt(mean);

+      unsigned i;

+      for(i = 0; i < cache->size; ++i) {

+         double z = fabs(cache->entries[i].count - mean)/stddev;

+         /* This assert should not fail 99.9999998027% of the times, unless 

+          * the hash function is a poor one */

+         assert(z <= 6.0);

+      }

+   }

+#endif

+      

+   util_cache_clear(cache);

+   

+   FREE(cache->entries);

+   FREE(cache);

+}

+

+

+void

+util_cache_remove(struct util_cache *cache,

+                  const void *key)

+{

+   struct util_cache_entry *entry;

+   uint32_t hash;

+

+   assert(cache);

+   if (!cache)

+      return;

+

+   hash = cache->hash(key);

+

+   entry = util_cache_entry_get(cache, hash, key);

+   if (!entry)

+      return;

+

+   if (entry->state == FILLED)

+      util_cache_entry_destroy(cache, entry);

+

+   ensure_sanity(cache);

+}

+

+

+static void

+ensure_sanity(const struct util_cache *cache)

+{

+#ifdef DEBUG

+   unsigned i, cnt = 0;

+

+   assert(cache);

+   for (i = 0; i < cache->size; i++) {

+      struct util_cache_entry *header = &cache->entries[i];

+

+      assert(header);

+      assert(header->state == FILLED ||

+             header->state == EMPTY ||

+             header->state == DELETED);

+      if (header->state == FILLED) {

+         cnt++;

+         assert(header->hash == cache->hash(header->key));

+      }

+   }

+

+   assert(cnt == cache->count);

+   assert(cache->size >= cnt);

+

+   if (cache->count == 0) {

+      assert (is_empty_list(&cache->lru));

+   }

+   else {

+      struct util_cache_entry *header = cache->lru.next;

+

+      assert (header);

+      assert (!is_empty_list(&cache->lru));

+

+      for (i = 0; i < cache->count; i++)

+         header = header->next;

+

+      assert(header == &cache->lru);

+   }

+#endif

+

+   (void)cache;

+}