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    if (!cache)
 141       return;
 142
 143    entry = util_cache_entry_get(cache, key);
 144    util_cache_entry_destroy(cache, entry);
 145
 146 #ifdef DEBUG
 147    ++entry->count;
 148    ++cache->count;
 149 #endif
 150
 151    entry->key = key;
 152    entry->value = value;
 153 }
 154
 155
 156 void *
 157 util_cache_get(struct util_cache *cache,
 158                const void *key)
 159 {
 160    struct util_cache_entry *entry;
 161
 162    assert(cache);
 163    if (!cache)
 164       return NULL;
 165
 166    entry = util_cache_entry_get(cache, key);
 167    if(!entry->key && !entry->value)
 168       return NULL;
 169
 170    if(cache->compare(key, entry->key) != 0)
 171       return NULL;
 172
 173    return entry->value;
 174 }
 175
 176
 177 void
 178 util_cache_clear(struct util_cache *cache)
 179 {
 180    uint32_t i;
 181
 182    assert(cache);
 183    if (!cache)
 184       return;
 185
 186    for(i = 0; i < cache->size; ++i)
 187       util_cache_entry_destroy(cache, &cache->entries[i]);
 188 }
 189
 190
 191 void
 192 util_cache_destroy(struct util_cache *cache)
 193 {
 194    assert(cache);
 195    if (!cache)
 196       return;
 197
 198 #ifdef DEBUG
 199    if(cache->count >= 20*cache->size) {
 200       /* Normal approximation of the Poisson distribution */
 201       double mean = (double)cache->count/(double)cache->size;
 202       double stddev = sqrt(mean);
 203       unsigned i;
 204       for(i = 0; i < cache->size; ++i) {
 205          double z = fabs(cache->entries[i].count - mean)/stddev;
 206          /* This assert should not fail 99.9999998027% of the times, unless
 207           * the hash function is a poor one */
 208          assert(z <= 6.0);
 209       }
 210    }
 211 #endif
 212
 213    util_cache_clear(cache);
 214
 215    FREE(cache->entries);
 216    FREE(cache);
 217 }