X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fgallium%2Fauxiliary%2Futil%2Fu_cache.c;h=c748cb99dd0c468f4342411ef784b688b1e67256;hb=e9cf8c1d3010e9eada5a7921239ad7895f249b5c;hp=0a1a64259f1e74d0c70686f4f50b81f8509ce7c2;hpb=ae7e75d6108e8621878083b35a13edc1aca893df;p=mesa.git

diff --git a/src/gallium/auxiliary/util/u_cache.c b/src/gallium/auxiliary/util/u_cache.c
index 0a1a64259f1..c748cb99dd0 100644
--- a/src/gallium/auxiliary/util/u_cache.c
+++ b/src/gallium/auxiliary/util/u_cache.c
@@ -27,24 +27,32 @@
 
 /**
  * @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>
  */
 
 
 #include "pipe/p_compiler.h"
-#include "pipe/p_debug.h"
+#include "util/u_debug.h"
 
 #include "util/u_math.h"
 #include "util/u_memory.h"
 #include "util/u_cache.h"
+#include "util/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;
    
@@ -65,16 +73,29 @@ struct util_cache
    /** Destroy a (key, value) pair */
    void (*destroy)(void *key, void *value);
 
+   /** Max entries in the cache */
    uint32_t size;
    
+   /** Array [size] of entries */
    struct util_cache_entry *entries;
    
-#ifdef DEBUG
+   /** Number of entries in the cache */
    unsigned count;
-#endif
+
+   /** Head of list, sorted from Least-recently used to Most-recently used */
+   struct util_cache_entry lru;
 };
 
 
+static void
+ensure_sanity(const struct util_cache *cache);
+
+#define CACHE_DEFAULT_ALPHA 2
+
+/**
+ * Create a new cache with 'size' entries.  Also provide functions for
+ * hashing keys, comparing keys and destroying (key,value) pairs.
+ */
 struct util_cache *
 util_cache_create(uint32_t (*hash)(const void *key),
                   int (*compare)(const void *key1, const void *key2),
@@ -84,36 +105,70 @@ util_cache_create(uint32_t (*hash)(const void *key),
    struct util_cache *cache;
    
    cache = CALLOC_STRUCT(util_cache);
-   if(!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) {
+   if (!cache->entries) {
       FREE(cache);
       return NULL;
    }
    
+   ensure_sanity(cache);
    return cache;
 }
 
 
-static INLINE struct util_cache_entry *
+/**
+ * Try to find a cache entry, given the key and hash of the key.
+ */
+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];
 
-   return &cache->entries[hash % cache->size];
+      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
+static inline void
 util_cache_entry_destroy(struct util_cache *cache,
                          struct util_cache_entry *entry)
 {
@@ -123,78 +178,125 @@ util_cache_entry_destroy(struct util_cache *cache,
    entry->key = NULL;
    entry->value = NULL;
    
-   if(key || value)
-      if(cache->destroy)
+   if (entry->state == FILLED) {
+      remove_from_list(entry);
+      cache->count--;
+
+      if (cache->destroy)
          cache->destroy(key, value);
+
+      entry->state = DELETED;
+   }
 }
 
 
+/**
+ * Insert an entry in the cache, given the key and value.
+ */
 void
 util_cache_set(struct util_cache *cache,
                void *key,
                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);
 }
 
 
+/**
+ * Search the cache for an entry with the given key.  Return the corresponding
+ * value or NULL if not found.
+ */
 void *
 util_cache_get(struct util_cache *cache, 
                const void *key)
 {
    struct util_cache_entry *entry;
+   uint32_t hash;
 
    assert(cache);
-
-   entry = util_cache_entry_get(cache, key);
-   if(!entry->key && !entry->value)
+   if (!cache)
       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;
 }
 
 
+/**
+ * Remove all entries from the cache.  The 'destroy' function will be called
+ * for each entry's (key, value).
+ */
 void 
 util_cache_clear(struct util_cache *cache)
 {
    uint32_t i;
 
    assert(cache);
-   
-   for(i = 0; i < cache->size; ++i)
+   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);
 }
 
 
+/**
+ * Destroy the cache and all entries.
+ */
 void
 util_cache_destroy(struct util_cache *cache)
 {
    assert(cache);
+   if (!cache)
+      return;
 
 #ifdef DEBUG
-   if(cache->count >= 20*cache->size) {
+   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->count - mean)/stddev;
+      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);
@@ -207,3 +309,73 @@ util_cache_destroy(struct util_cache *cache)
    FREE(cache->entries);
    FREE(cache);
 }
+
+
+/**
+ * Remove the cache entry which matches the given key.
+ */
+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;
+}