u_cache.c revision d00cbf46cde0edee6d8f2c08e14458ef92ff0fbe 
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
46struct util_cache_entry
47{
48   void *key;
49   void *value;
50
51#ifdef DEBUG
52   unsigned count;
53#endif
54};
55
56
57struct 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
78struct util_cache *
79util_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
105static INLINE struct util_cache_entry *
106util_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
116static INLINE void
117util_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
132void
133util_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
156void *
157util_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
177void
178util_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
191void
192util_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}
218
219
220void
221util_cache_remove(struct util_cache *cache,
222                  const void *key)
223{
224   struct util_cache_entry *entry;
225   uint32_t hash;
226
227   assert(cache);
228   if (!cache)
229      return;
230
231   hash = cache->hash(key);
232
233   entry = util_cache_entry_get(cache, hash, key);
234   if (!entry)
235      return;
236
237   if (entry->state == FILLED)
238      util_cache_entry_destroy(cache, entry);
239}
240