From 990bc3f015a4f8fce2eb918375defcd44980a845 Mon Sep 17 00:00:00 2001 From: marha Date: Fri, 8 Jun 2012 09:33:13 +0200 Subject: Used synchronise script to update files --- mesalib/src/gallium/auxiliary/util/u_cache.c | 702 +++++++++++++-------------- 1 file changed, 351 insertions(+), 351 deletions(-) (limited to 'mesalib/src/gallium/auxiliary/util/u_cache.c') diff --git a/mesalib/src/gallium/auxiliary/util/u_cache.c b/mesalib/src/gallium/auxiliary/util/u_cache.c index 215236818..df08ec302 100644 --- a/mesalib/src/gallium/auxiliary/util/u_cache.c +++ b/mesalib/src/gallium/auxiliary/util/u_cache.c @@ -1,351 +1,351 @@ -/************************************************************************** - * - * Copyright 2008 VMware, Inc. - * All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sub license, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice (including the - * next paragraph) shall be included in all copies or substantial portions - * of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. - * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR - * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - **************************************************************************/ - -/** - * @file - * Improved cache implementation. - * - * Fixed size array with linear probing on collision and LRU eviction - * on full. - * - * @author Jose Fonseca - */ - - -#include "pipe/p_compiler.h" -#include "util/u_debug.h" - -#include "util/u_math.h" -#include "util/u_memory.h" -#include "util/u_cache.h" -#include "util/u_simple_list.h" - - -struct util_cache_entry -{ - enum { EMPTY = 0, FILLED, DELETED } state; - uint32_t hash; - - struct util_cache_entry *next; - struct util_cache_entry *prev; - - void *key; - void *value; - -#ifdef DEBUG - unsigned count; -#endif -}; - - -struct util_cache -{ - /** Hash function */ - uint32_t (*hash)(const void *key); - - /** Compare two keys */ - int (*compare)(const void *key1, const void *key2); - - /** Destroy a (key, value) pair */ - void (*destroy)(void *key, void *value); - - uint32_t size; - - struct util_cache_entry *entries; - - unsigned count; - struct util_cache_entry lru; -}; - -static void -ensure_sanity(const struct util_cache *cache); - -#define CACHE_DEFAULT_ALPHA 2 - -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) -{ - struct util_cache *cache; - - cache = CALLOC_STRUCT(util_cache); - if(!cache) - return NULL; - - cache->hash = hash; - cache->compare = compare; - cache->destroy = destroy; - - make_empty_list(&cache->lru); - - size *= CACHE_DEFAULT_ALPHA; - cache->size = size; - - cache->entries = CALLOC(size, sizeof(struct util_cache_entry)); - if(!cache->entries) { - FREE(cache); - return NULL; - } - - ensure_sanity(cache); - return cache; -} - - -static struct util_cache_entry * -util_cache_entry_get(struct util_cache *cache, - uint32_t hash, - const void *key) -{ - struct util_cache_entry *first_unfilled = NULL; - uint32_t index = hash % cache->size; - uint32_t probe; - - /* Probe until we find either a matching FILLED entry or an EMPTY - * slot (which has never been occupied). - * - * Deleted or non-matching slots are not indicative of completion - * as a previous linear probe for the same key could have continued - * past this point. - */ - for (probe = 0; probe < cache->size; probe++) { - uint32_t i = (index + probe) % cache->size; - struct util_cache_entry *current = &cache->entries[i]; - - if (current->state == FILLED) { - if (current->hash == hash && - cache->compare(key, current->key) == 0) - return current; - } - else { - if (!first_unfilled) - first_unfilled = current; - - if (current->state == EMPTY) - return first_unfilled; - } - } - - return NULL; -} - -static INLINE void -util_cache_entry_destroy(struct util_cache *cache, - struct util_cache_entry *entry) -{ - void *key = entry->key; - void *value = entry->value; - - entry->key = NULL; - entry->value = NULL; - - if (entry->state == FILLED) { - remove_from_list(entry); - cache->count--; - - if(cache->destroy) - cache->destroy(key, value); - - entry->state = DELETED; - } -} - - -void -util_cache_set(struct util_cache *cache, - void *key, - void *value) -{ - struct util_cache_entry *entry; - uint32_t hash = cache->hash(key); - - assert(cache); - if (!cache) - return; - - entry = util_cache_entry_get(cache, hash, key); - if (!entry) - entry = cache->lru.prev; - - if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA) - util_cache_entry_destroy(cache, cache->lru.prev); - - util_cache_entry_destroy(cache, entry); - -#ifdef DEBUG - ++entry->count; -#endif - - entry->key = key; - entry->hash = hash; - entry->value = value; - entry->state = FILLED; - insert_at_head(&cache->lru, entry); - cache->count++; - - ensure_sanity(cache); -} - - -void * -util_cache_get(struct util_cache *cache, - const void *key) -{ - struct util_cache_entry *entry; - uint32_t hash = cache->hash(key); - - assert(cache); - if (!cache) - return NULL; - - entry = util_cache_entry_get(cache, hash, key); - if (!entry) - return NULL; - - if (entry->state == FILLED) - move_to_head(&cache->lru, entry); - - return entry->value; -} - - -void -util_cache_clear(struct util_cache *cache) -{ - uint32_t i; - - assert(cache); - if (!cache) - return; - - for(i = 0; i < cache->size; ++i) { - util_cache_entry_destroy(cache, &cache->entries[i]); - cache->entries[i].state = EMPTY; - } - - assert(cache->count == 0); - assert(is_empty_list(&cache->lru)); - ensure_sanity(cache); -} - - -void -util_cache_destroy(struct util_cache *cache) -{ - assert(cache); - if (!cache) - return; - -#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->entries[i].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); -} - - -void -util_cache_remove(struct util_cache *cache, - const void *key) -{ - struct util_cache_entry *entry; - uint32_t hash; - - assert(cache); - if (!cache) - return; - - hash = cache->hash(key); - - entry = util_cache_entry_get(cache, hash, key); - if (!entry) - return; - - if (entry->state == FILLED) - util_cache_entry_destroy(cache, entry); - - ensure_sanity(cache); -} - - -static void -ensure_sanity(const struct util_cache *cache) -{ -#ifdef DEBUG - unsigned i, cnt = 0; - - assert(cache); - for (i = 0; i < cache->size; i++) { - struct util_cache_entry *header = &cache->entries[i]; - - assert(header); - assert(header->state == FILLED || - header->state == EMPTY || - header->state == DELETED); - if (header->state == FILLED) { - cnt++; - assert(header->hash == cache->hash(header->key)); - } - } - - assert(cnt == cache->count); - assert(cache->size >= cnt); - - if (cache->count == 0) { - assert (is_empty_list(&cache->lru)); - } - else { - struct util_cache_entry *header = cache->lru.next; - - assert (header); - assert (!is_empty_list(&cache->lru)); - - for (i = 0; i < cache->count; i++) - header = header->next; - - assert(header == &cache->lru); - } -#endif - - (void)cache; -} +/************************************************************************** + * + * Copyright 2008 VMware, Inc. + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sub license, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice (including the + * next paragraph) shall be included in all copies or substantial portions + * of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. + * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + **************************************************************************/ + +/** + * @file + * Improved cache implementation. + * + * Fixed size array with linear probing on collision and LRU eviction + * on full. + * + * @author Jose Fonseca + */ + + +#include "pipe/p_compiler.h" +#include "util/u_debug.h" + +#include "util/u_math.h" +#include "util/u_memory.h" +#include "util/u_cache.h" +#include "util/u_simple_list.h" + + +struct util_cache_entry +{ + enum { EMPTY = 0, FILLED, DELETED } state; + uint32_t hash; + + struct util_cache_entry *next; + struct util_cache_entry *prev; + + void *key; + void *value; + +#ifdef DEBUG + unsigned count; +#endif +}; + + +struct util_cache +{ + /** Hash function */ + uint32_t (*hash)(const void *key); + + /** Compare two keys */ + int (*compare)(const void *key1, const void *key2); + + /** Destroy a (key, value) pair */ + void (*destroy)(void *key, void *value); + + uint32_t size; + + struct util_cache_entry *entries; + + unsigned count; + struct util_cache_entry lru; +}; + +static void +ensure_sanity(const struct util_cache *cache); + +#define CACHE_DEFAULT_ALPHA 2 + +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) +{ + struct util_cache *cache; + + cache = CALLOC_STRUCT(util_cache); + if(!cache) + return NULL; + + cache->hash = hash; + cache->compare = compare; + cache->destroy = destroy; + + make_empty_list(&cache->lru); + + size *= CACHE_DEFAULT_ALPHA; + cache->size = size; + + cache->entries = CALLOC(size, sizeof(struct util_cache_entry)); + if(!cache->entries) { + FREE(cache); + return NULL; + } + + ensure_sanity(cache); + return cache; +} + + +static struct util_cache_entry * +util_cache_entry_get(struct util_cache *cache, + uint32_t hash, + const void *key) +{ + struct util_cache_entry *first_unfilled = NULL; + uint32_t index = hash % cache->size; + uint32_t probe; + + /* Probe until we find either a matching FILLED entry or an EMPTY + * slot (which has never been occupied). + * + * Deleted or non-matching slots are not indicative of completion + * as a previous linear probe for the same key could have continued + * past this point. + */ + for (probe = 0; probe < cache->size; probe++) { + uint32_t i = (index + probe) % cache->size; + struct util_cache_entry *current = &cache->entries[i]; + + if (current->state == FILLED) { + if (current->hash == hash && + cache->compare(key, current->key) == 0) + return current; + } + else { + if (!first_unfilled) + first_unfilled = current; + + if (current->state == EMPTY) + return first_unfilled; + } + } + + return NULL; +} + +static INLINE void +util_cache_entry_destroy(struct util_cache *cache, + struct util_cache_entry *entry) +{ + void *key = entry->key; + void *value = entry->value; + + entry->key = NULL; + entry->value = NULL; + + if (entry->state == FILLED) { + remove_from_list(entry); + cache->count--; + + if(cache->destroy) + cache->destroy(key, value); + + entry->state = DELETED; + } +} + + +void +util_cache_set(struct util_cache *cache, + void *key, + void *value) +{ + struct util_cache_entry *entry; + uint32_t hash = cache->hash(key); + + assert(cache); + if (!cache) + return; + + entry = util_cache_entry_get(cache, hash, key); + if (!entry) + entry = cache->lru.prev; + + if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA) + util_cache_entry_destroy(cache, cache->lru.prev); + + util_cache_entry_destroy(cache, entry); + +#ifdef DEBUG + ++entry->count; +#endif + + entry->key = key; + entry->hash = hash; + entry->value = value; + entry->state = FILLED; + insert_at_head(&cache->lru, entry); + cache->count++; + + ensure_sanity(cache); +} + + +void * +util_cache_get(struct util_cache *cache, + const void *key) +{ + struct util_cache_entry *entry; + uint32_t hash = cache->hash(key); + + assert(cache); + if (!cache) + return NULL; + + entry = util_cache_entry_get(cache, hash, key); + if (!entry) + return NULL; + + if (entry->state == FILLED) + move_to_head(&cache->lru, entry); + + return entry->value; +} + + +void +util_cache_clear(struct util_cache *cache) +{ + uint32_t i; + + assert(cache); + if (!cache) + return; + + for(i = 0; i < cache->size; ++i) { + util_cache_entry_destroy(cache, &cache->entries[i]); + cache->entries[i].state = EMPTY; + } + + assert(cache->count == 0); + assert(is_empty_list(&cache->lru)); + ensure_sanity(cache); +} + + +void +util_cache_destroy(struct util_cache *cache) +{ + assert(cache); + if (!cache) + return; + +#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->entries[i].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); +} + + +void +util_cache_remove(struct util_cache *cache, + const void *key) +{ + struct util_cache_entry *entry; + uint32_t hash; + + assert(cache); + if (!cache) + return; + + hash = cache->hash(key); + + entry = util_cache_entry_get(cache, hash, key); + if (!entry) + return; + + if (entry->state == FILLED) + util_cache_entry_destroy(cache, entry); + + ensure_sanity(cache); +} + + +static void +ensure_sanity(const struct util_cache *cache) +{ +#ifdef DEBUG + unsigned i, cnt = 0; + + assert(cache); + for (i = 0; i < cache->size; i++) { + struct util_cache_entry *header = &cache->entries[i]; + + assert(header); + assert(header->state == FILLED || + header->state == EMPTY || + header->state == DELETED); + if (header->state == FILLED) { + cnt++; + assert(header->hash == cache->hash(header->key)); + } + } + + assert(cnt == cache->count); + assert(cache->size >= cnt); + + if (cache->count == 0) { + assert (is_empty_list(&cache->lru)); + } + else { + struct util_cache_entry *header = cache->lru.next; + + assert (header); + assert (!is_empty_list(&cache->lru)); + + for (i = 0; i < cache->count; i++) + header = header->next; + + assert(header == &cache->lru); + } +#endif + + (void)cache; +} -- cgit v1.2.3