u_cache.c

Go to the documentation of this file.
00001 /**************************************************************************
00002  *
00003  * Copyright 2008 VMware, Inc.
00004  * All Rights Reserved.
00005  *
00006  * Permission is hereby granted, free of charge, to any person obtaining a
00007  * copy of this software and associated documentation files (the
00008  * "Software"), to deal in the Software without restriction, including
00009  * without limitation the rights to use, copy, modify, merge, publish,
00010  * distribute, sub license, and/or sell copies of the Software, and to
00011  * permit persons to whom the Software is furnished to do so, subject to
00012  * the following conditions:
00013  *
00014  * The above copyright notice and this permission notice (including the
00015  * next paragraph) shall be included in all copies or substantial portions
00016  * of the Software.
00017  *
00018  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
00019  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00020  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
00021  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
00022  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
00023  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
00024  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00025  *
00026  **************************************************************************/
00027 
00038 #include "pipe/p_compiler.h"
00039 #include "pipe/p_debug.h"
00040 
00041 #include "util/u_math.h"
00042 #include "util/u_memory.h"
00043 #include "util/u_cache.h"
00044 
00045 
00046 struct util_cache_entry
00047 {
00048    void *key;
00049    void *value;
00050    
00051 #ifdef DEBUG
00052    unsigned count;
00053 #endif
00054 };
00055 
00056 
00057 struct util_cache
00058 {
00060    uint32_t (*hash)(const void *key);
00061    
00063    int (*compare)(const void *key1, const void *key2);
00064 
00066    void (*destroy)(void *key, void *value);
00067 
00068    uint32_t size;
00069    
00070    struct util_cache_entry *entries;
00071    
00072 #ifdef DEBUG
00073    unsigned count;
00074 #endif
00075 };
00076 
00077 
00078 struct util_cache *
00079 util_cache_create(uint32_t (*hash)(const void *key),
00080                   int (*compare)(const void *key1, const void *key2),
00081                   void (*destroy)(void *key, void *value),
00082                   uint32_t size)
00083 {
00084    struct util_cache *cache;
00085    
00086    cache = CALLOC_STRUCT(util_cache);
00087    if(!cache)
00088       return NULL;
00089    
00090    cache->hash = hash;
00091    cache->compare = compare;
00092    cache->destroy = destroy;
00093    cache->size = size;
00094    
00095    cache->entries = CALLOC(size, sizeof(struct util_cache_entry));
00096    if(!cache->entries) {
00097       FREE(cache);
00098       return NULL;
00099    }
00100    
00101    return cache;
00102 }
00103 
00104 
00105 static INLINE struct util_cache_entry *
00106 util_cache_entry_get(struct util_cache *cache,
00107                      const void *key)
00108 {
00109    uint32_t hash;
00110    
00111    hash = cache->hash(key);
00112 
00113    return &cache->entries[hash % cache->size];
00114 }
00115 
00116 static INLINE void
00117 util_cache_entry_destroy(struct util_cache *cache,
00118                          struct util_cache_entry *entry)
00119 {
00120    void *key = entry->key;
00121    void *value = entry->value;
00122    
00123    entry->key = NULL;
00124    entry->value = NULL;
00125    
00126    if(key || value)
00127       if(cache->destroy)
00128          cache->destroy(key, value);
00129 }
00130 
00131 
00132 void
00133 util_cache_set(struct util_cache *cache,
00134                void *key,
00135                void *value)
00136 {
00137    struct util_cache_entry *entry;
00138 
00139    assert(cache);
00140 
00141    entry = util_cache_entry_get(cache, key);
00142    util_cache_entry_destroy(cache, entry);
00143    
00144 #ifdef DEBUG
00145    ++entry->count;
00146    ++cache->count;
00147 #endif
00148    
00149    entry->key = key;
00150    entry->value = value;
00151 }
00152 
00153 
00154 void *
00155 util_cache_get(struct util_cache *cache, 
00156                const void *key)
00157 {
00158    struct util_cache_entry *entry;
00159 
00160    assert(cache);
00161 
00162    entry = util_cache_entry_get(cache, key);
00163    if(!entry->key && !entry->value)
00164       return NULL;
00165    
00166    if(cache->compare(key, entry->key) != 0)
00167       return NULL;
00168    
00169    return entry->value;
00170 }
00171 
00172 
00173 void 
00174 util_cache_clear(struct util_cache *cache)
00175 {
00176    uint32_t i;
00177 
00178    assert(cache);
00179    
00180    for(i = 0; i < cache->size; ++i)
00181       util_cache_entry_destroy(cache, &cache->entries[i]);
00182 }
00183 
00184 
00185 void
00186 util_cache_destroy(struct util_cache *cache)
00187 {
00188    assert(cache);
00189 
00190 #ifdef DEBUG
00191    if(cache->count >= 20*cache->size) {
00192       /* Normal approximation of the Poisson distribution */
00193       double mean = (double)cache->count/(double)cache->size;
00194       double stddev = sqrt(mean);
00195       unsigned i;
00196       for(i = 0; i < cache->size; ++i) {
00197          double z = fabs(cache->count - mean)/stddev;
00198          /* This assert should not fail 99.9999998027% of the times, unless 
00199           * the hash function is a poor one */
00200          assert(z <= 6.0);
00201       }
00202    }
00203 #endif
00204       
00205    util_cache_clear(cache);
00206    
00207    FREE(cache->entries);
00208    FREE(cache);
00209 }

Generated on Tue Sep 29 06:25:15 2009 for Gallium3D by  doxygen 1.5.4