u_cache.c File Reference

Simple cache implementation. More...

Include dependency graph for u_cache.c:

Go to the source code of this file.

Data Structures
struct	util_cache_entry
struct	util_cache
Functions
struct util_cache *	util_cache_create (uint32_t(*hash)(const void *key), int(*compare)(const void *key1, const void *key2), void(*destroy)(void *key, void *value), uint32_t size)
	Create a cache.
static struct util_cache_entry *	util_cache_entry_get (struct util_cache *cache, const void *key)
static void	util_cache_entry_destroy (struct util_cache *cache, struct util_cache_entry *entry)
void	util_cache_set (struct util_cache *cache, void *key, void *value)
void *	util_cache_get (struct util_cache *cache, const void *key)
void	util_cache_clear (struct util_cache *cache)
void	util_cache_destroy (struct util_cache *cache)

---

Detailed Description

Simple cache implementation.

We simply have fixed size array, and destroy previous values on collision.

Author:

Jose Fonseca <jfonseca@vmware.com>

Definition in file u_cache.c.

---

Function Documentation

void util_cache_clear

(

struct util_cache *

cache

)

Definition at line 174 of file u_cache.c.

References assert, util_cache::entries, util_cache::size, and util_cache_entry_destroy().

{
   uint32_t i;

   assert(cache);
   
   for(i = 0; i < cache->size; ++i)
      util_cache_entry_destroy(cache, &cache->entries[i]);
}

struct util_cache* util_cache_create	(	uint32_t(*)(const void *key)	hash,
		int(*)(const void *key1, const void *key2)	compare,
		void(*)(void *key, void *value)	destroy,
		uint32_t	size
	)			[read]

Create a cache.

Parameters:

	hash	hash function
	compare	should return 0 for two equal keys
	destroy	destruction callback (optional)
	size	maximum number of entries

Definition at line 79 of file u_cache.c.

References CALLOC, CALLOC_STRUCT, util_cache::compare, util_cache::destroy, util_cache::entries, FREE, util_cache::hash, and util_cache::size.

{
   struct util_cache *cache;
   
   cache = CALLOC_STRUCT(util_cache);
   if(!cache)
      return NULL;
   
   cache->hash = hash;
   cache->compare = compare;
   cache->destroy = destroy;
   cache->size = size;
   
   cache->entries = CALLOC(size, sizeof(struct util_cache_entry));
   if(!cache->entries) {
      FREE(cache);
      return NULL;
   }
   
   return cache;
}

void util_cache_destroy

(

struct util_cache *

cache

)

Definition at line 186 of file u_cache.c.

References assert, util_cache::entries, FREE, util_cache::size, and util_cache_clear().

{
   assert(cache);

#ifdef DEBUG
   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;
         /* This assert should not fail 99.9999998027% of the times, unless 
          * the hash function is a poor one */
         assert(z <= 6.0);
      }
   }
#endif
      
   util_cache_clear(cache);
   
   FREE(cache->entries);
   FREE(cache);
}

static void util_cache_entry_destroy	(	struct util_cache *	cache,
		struct util_cache_entry *	entry
	)			[static]

Definition at line 117 of file u_cache.c.

References util_cache::destroy, util_cache_entry::key, and util_cache_entry::value.

{
   void *key = entry->key;
   void *value = entry->value;
   
   entry->key = NULL;
   entry->value = NULL;
   
   if(key || value)
      if(cache->destroy)
         cache->destroy(key, value);
}

static struct util_cache_entry* util_cache_entry_get	(	struct util_cache *	cache,
		const void *	key
	)			[static, read]

Definition at line 106 of file u_cache.c.

References util_cache::entries, util_cache::hash, and util_cache::size.

{
   uint32_t hash;
   
   hash = cache->hash(key);

   return &cache->entries[hash % cache->size];
}

void* util_cache_get	(	struct util_cache *	cache,
		const void *	key
	)

Definition at line 155 of file u_cache.c.

References assert, util_cache::compare, util_cache_entry::key, util_cache_entry_get(), and util_cache_entry::value.

{
   struct util_cache_entry *entry;

   assert(cache);

   entry = util_cache_entry_get(cache, key);
   if(!entry->key && !entry->value)
      return NULL;
   
   if(cache->compare(key, entry->key) != 0)
      return NULL;
   
   return entry->value;
}

void util_cache_set	(	struct util_cache *	cache,
		void *	key,
		void *	value
	)

Definition at line 133 of file u_cache.c.

References assert, util_cache_entry::key, util_cache_entry_destroy(), util_cache_entry_get(), and util_cache_entry::value.

{
   struct util_cache_entry *entry;

   assert(cache);

   entry = util_cache_entry_get(cache, key);
   util_cache_entry_destroy(cache, entry);
   
#ifdef DEBUG
   ++entry->count;
   ++cache->count;
#endif
   
   entry->key = key;
   entry->value = value;
}

---