src/gallium/auxiliary/util/u_cache.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 VMware, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /**
  29  * @file
  30  * Simple cache implementation.
  31  *
  32  * We simply have fixed size array, and destroy previous values on collision.
  33  *
  34  * @author Jose Fonseca <jfonseca@vmware.com>
  35  */
  36
  37
  38 #include "pipe/p_compiler.h"
  39 #include "util/u_debug.h"
  40
  41 #include "util/u_math.h"
  42 #include "util/u_memory.h"
  43 #include "util/u_cache.h"
  44
  45
  46 struct util_cache_entry
  47 {
  48    void *key;
  49    void *value;
  50
  51 #ifdef DEBUG
  52    unsigned count;
  53 #endif
  54 };
  55
  56
  57 struct util_cache
  58 {
  59    /** Hash function */
  60    uint32_t (*hash)(const void *key);
  61
  62    /** Compare two keys */
  63    int (*compare)(const void *key1, const void *key2);
  64
  65    /** Destroy a (key, value) pair */
  66    void (*destroy)(void *key, void *value);
  67
  68    uint32_t size;
  69
  70    struct util_cache_entry *entries;
  71
  72 #ifdef DEBUG
  73    unsigned count;
  74 #endif
  75 };
  76
  77
  78 struct util_cache *
  79 util_cache_create(uint32_t (*hash)(const void *key),
  80                   int (*compare)(const void *key1, const void *key2),
  81                   void (*destroy)(void *key, void *value),
  82                   uint32_t size)
  83 {
  84    struct util_cache *cache;
  85
  86    cache = CALLOC_STRUCT(util_cache);
  87    if(!cache)
  88       return NULL;
  89
  90    cache->hash = hash;
  91    cache->compare = compare;
  92    cache->destroy = destroy;
  93    cache->size = size;
  94
  95    cache->entries = CALLOC(size, sizeof(struct util_cache_entry));
  96    if(!cache->entries) {
  97       FREE(cache);
  98       return NULL;
  99    }
 100
 101    return cache;
 102 }
 103
 104
 105 static INLINE struct util_cache_entry *
 106 util_cache_entry_get(struct util_cache *cache,
 107                      const void *key)
 108 {
 109    uint32_t hash;
 110
 111    hash = cache->hash(key);
 112
 113    return &cache->entries[hash % cache->size];
 114 }
 115
 116 static INLINE void
 117 util_cache_entry_destroy(struct util_cache *cache,
 118                          struct util_cache_entry *entry)
 119 {
 120    void *key = entry->key;
 121    void *value = entry->value;
 122
 123    entry->key = NULL;
 124    entry->value = NULL;
 125
 126    if(key || value)
 127       if(cache->destroy)
 128          cache->destroy(key, value);
 129 }
 130
 131
 132 void
 133 util_cache_set(struct util_cache *cache,
 134                void *key,
 135                void *value)
 136 {
 137    struct util_cache_entry *entry;
 138
 139    assert(cache);
 140
 141    entry = util_cache_entry_get(cache, key);
 142    util_cache_entry_destroy(cache, entry);
 143
 144 #ifdef DEBUG
 145    ++entry->count;
 146    ++cache->count;
 147 #endif
 148
 149    entry->key = key;
 150    entry->value = value;
 151 }
 152
 153
 154 void *
 155 util_cache_get(struct util_cache *cache,
 156                const void *key)
 157 {
 158    struct util_cache_entry *entry;
 159
 160    assert(cache);
 161
 162    entry = util_cache_entry_get(cache, key);
 163    if(!entry->key && !entry->value)
 164       return NULL;
 165
 166    if(cache->compare(key, entry->key) != 0)
 167       return NULL;
 168
 169    return entry->value;
 170 }
 171
 172
 173 void
 174 util_cache_clear(struct util_cache *cache)
 175 {
 176    uint32_t i;
 177
 178    assert(cache);
 179
 180    for(i = 0; i < cache->size; ++i)
 181       util_cache_entry_destroy(cache, &cache->entries[i]);
 182 }
 183
 184
 185 void
 186 util_cache_destroy(struct util_cache *cache)
 187 {
 188    assert(cache);
 189
 190 #ifdef DEBUG
 191    if(cache->count >= 20*cache->size) {
 192       /* Normal approximation of the Poisson distribution */
 193       double mean = (double)cache->count/(double)cache->size;
 194       double stddev = sqrt(mean);
 195       unsigned i;
 196       for(i = 0; i < cache->size; ++i) {
 197          double z = fabs(cache->count - mean)/stddev;
 198          /* This assert should not fail 99.9999998027% of the times, unless
 199           * the hash function is a poor one */
 200          assert(z <= 6.0);
 201       }
 202    }
 203 #endif
 204
 205    util_cache_clear(cache);
 206
 207    FREE(cache->entries);
 208    FREE(cache);
 209 }