X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fgallium%2Fauxiliary%2Futil%2Fu_cache.c;h=26aab2bf1d4380dbdb5ae3a3eff94ebceb977524;hb=8ed6b1400bc8a78f46340f41aaf2e88b24c23267;hp=47c16b1c927f5f70fbd6d1dddeeaea8e0df11e3a;hpb=eeb7e04da64fdae3a40b1afdcde71dcded2481f3;p=mesa.git

diff --git a/src/gallium/auxiliary/util/u_cache.c b/src/gallium/auxiliary/util/u_cache.c
index 47c16b1c927..26aab2bf1d4 100644
--- a/src/gallium/auxiliary/util/u_cache.c
+++ b/src/gallium/auxiliary/util/u_cache.c
@@ -27,9 +27,10 @@
 
 /**
  * @file
- * Simple cache implementation.
+ * Improved cache implementation.
  *
- * We simply have fixed size array, and destroy previous values on collision. 
+ * Fixed size array with linear probing on collision and LRU eviction
+ * on full.
  * 
  * @author Jose Fonseca <jfonseca@vmware.com>
  */
@@ -41,10 +42,17 @@
 #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;
    
@@ -69,11 +77,14 @@ struct util_cache
    
    struct util_cache_entry *entries;
    
-#ifdef DEBUG
    unsigned count;
-#endif
+   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),
@@ -90,6 +101,10 @@ util_cache_create(uint32_t (*hash)(const void *key),
    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));
@@ -98,19 +113,46 @@ util_cache_create(uint32_t (*hash)(const void *key),
       return NULL;
    }
    
+   ensure_sanity(cache);
    return cache;
 }
 
 
-static INLINE struct util_cache_entry *
+static struct util_cache_entry *
 util_cache_entry_get(struct util_cache *cache,
+                     uint32_t hash,
                      const void *key)
 {
-   uint32_t hash;
-   
-   hash = cache->hash(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 &cache->entries[hash % cache->size];
+   return NULL;
 }
 
 static INLINE void
@@ -123,9 +165,15 @@ util_cache_entry_destroy(struct util_cache *cache,
    entry->key = NULL;
    entry->value = NULL;
    
-   if(key || value)
+   if (entry->state == FILLED) {
+      remove_from_list(entry);
+      cache->count--;
+
       if(cache->destroy)
          cache->destroy(key, value);
+
+      entry->state = DELETED;
+   }
 }
 
 
@@ -135,21 +183,33 @@ util_cache_set(struct util_cache *cache,
                void *value)
 {
    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)
+      entry = cache->lru.prev;
+
+   if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)
+      util_cache_entry_destroy(cache, cache->lru.prev);
 
-   entry = util_cache_entry_get(cache, key);
    util_cache_entry_destroy(cache, entry);
    
 #ifdef DEBUG
    ++entry->count;
-   ++cache->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);
 }
 
 
@@ -158,17 +218,18 @@ util_cache_get(struct util_cache *cache,
                const void *key)
 {
    struct util_cache_entry *entry;
+   uint32_t hash;
 
    assert(cache);
    if (!cache)
       return NULL;
-
-   entry = util_cache_entry_get(cache, key);
-   if(!entry->key && !entry->value)
-      return NULL;
-   
-   if(cache->compare(key, entry->key) != 0)
+   hash = cache->hash(key);
+   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;
 }
@@ -183,8 +244,14 @@ util_cache_clear(struct util_cache *cache)
    if (!cache)
       return;
 
-   for(i = 0; i < cache->size; ++i)
+   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);
 }
 
 
@@ -202,7 +269,7 @@ util_cache_destroy(struct util_cache *cache)
       double stddev = sqrt(mean);
       unsigned i;
       for(i = 0; i < cache->size; ++i) {
-         double z = fabs(cache->count - mean)/stddev;
+         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);
@@ -215,3 +282,70 @@ util_cache_destroy(struct util_cache *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;
+}