/**************************************************************************
*
- * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
+ * Copyright 2008 VMware, Inc.
* All Rights Reserved.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* 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 TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR
+ * 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.
* better lookup and cache performance and it appears to be possible to write
* a lock-free implementation of such hash tables .
*
- * @author José Fonseca <jrfonseca@tungstengraphics.com>
+ * @author José Fonseca <jfonseca@vmware.com>
*/
#include "util/u_hash_table.h"
-struct hash_table
+struct util_hash_table
{
struct cso_hash *cso;
};
-struct hash_table_item
+struct util_hash_table_item
{
void *key;
void *value;
};
-static INLINE struct hash_table_item *
-hash_table_item(struct cso_hash_iter iter)
+static inline struct util_hash_table_item *
+util_hash_table_item(struct cso_hash_iter iter)
{
- return (struct hash_table_item *)cso_hash_iter_data(iter);
+ return (struct util_hash_table_item *)cso_hash_iter_data(iter);
}
-struct hash_table *
-hash_table_create(unsigned (*hash)(void *key),
- int (*compare)(void *key1, void *key2))
+struct util_hash_table *
+util_hash_table_create(unsigned (*hash)(void *key),
+ int (*compare)(void *key1, void *key2))
{
- struct hash_table *ht;
+ struct util_hash_table *ht;
- ht = MALLOC_STRUCT(hash_table);
- if(!ht)
+ ht = MALLOC_STRUCT(util_hash_table);
+ if (!ht)
return NULL;
ht->cso = cso_hash_create();
}
-static INLINE struct cso_hash_iter
-hash_table_find_iter(struct hash_table *ht,
- void *key,
- unsigned key_hash)
+static inline struct cso_hash_iter
+util_hash_table_find_iter(struct util_hash_table *ht,
+ void *key,
+ unsigned key_hash)
{
struct cso_hash_iter iter;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
iter = cso_hash_find(ht->cso, key_hash);
while (!cso_hash_iter_is_null(iter)) {
- item = (struct hash_table_item *)cso_hash_iter_data(iter);
+ item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
if (!ht->compare(item->key, key))
break;
iter = cso_hash_iter_next(iter);
}
-static INLINE struct hash_table_item *
-hash_table_find_item(struct hash_table *ht,
- void *key,
- unsigned key_hash)
+static inline struct util_hash_table_item *
+util_hash_table_find_item(struct util_hash_table *ht,
+ void *key,
+ unsigned key_hash)
{
struct cso_hash_iter iter;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
iter = cso_hash_find(ht->cso, key_hash);
while (!cso_hash_iter_is_null(iter)) {
- item = (struct hash_table_item *)cso_hash_iter_data(iter);
+ item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
if (!ht->compare(item->key, key))
return item;
iter = cso_hash_iter_next(iter);
enum pipe_error
-hash_table_set(struct hash_table *ht,
- void *key,
- void *value)
+util_hash_table_set(struct util_hash_table *ht,
+ void *key,
+ void *value)
{
unsigned key_hash;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
struct cso_hash_iter iter;
assert(ht);
+ if (!ht)
+ return PIPE_ERROR_BAD_INPUT;
key_hash = ht->hash(key);
- item = hash_table_find_item(ht, key, key_hash);
- if(item) {
+ item = util_hash_table_find_item(ht, key, key_hash);
+ if (item) {
/* TODO: key/value destruction? */
item->value = value;
return PIPE_OK;
}
- item = MALLOC_STRUCT(hash_table_item);
- if(!item)
+ item = MALLOC_STRUCT(util_hash_table_item);
+ if (!item)
return PIPE_ERROR_OUT_OF_MEMORY;
item->key = key;
void *
-hash_table_get(struct hash_table *ht,
- void *key)
+util_hash_table_get(struct util_hash_table *ht,
+ void *key)
{
unsigned key_hash;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
assert(ht);
+ if (!ht)
+ return NULL;
key_hash = ht->hash(key);
- item = hash_table_find_item(ht, key, key_hash);
- if(!item)
+ item = util_hash_table_find_item(ht, key, key_hash);
+ if (!item)
return NULL;
return item->value;
void
-hash_table_remove(struct hash_table *ht,
- void *key)
+util_hash_table_remove(struct util_hash_table *ht,
+ void *key)
{
unsigned key_hash;
struct cso_hash_iter iter;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
assert(ht);
+ if (!ht)
+ return;
key_hash = ht->hash(key);
- iter = hash_table_find_iter(ht, key, key_hash);
+ iter = util_hash_table_find_iter(ht, key, key_hash);
if(cso_hash_iter_is_null(iter))
return;
- item = hash_table_item(iter);
+ item = util_hash_table_item(iter);
assert(item);
FREE(item);
void
-hash_table_clear(struct hash_table *ht)
+util_hash_table_clear(struct util_hash_table *ht)
{
struct cso_hash_iter iter;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
assert(ht);
-
+ if (!ht)
+ return;
+
iter = cso_hash_first_node(ht->cso);
while (!cso_hash_iter_is_null(iter)) {
- item = (struct hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
+ item = (struct util_hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
FREE(item);
iter = cso_hash_first_node(ht->cso);
}
enum pipe_error
-hash_table_foreach(struct hash_table *ht,
- enum pipe_error (*callback)(void *key, void *value, void *data),
- void *data)
+util_hash_table_foreach(struct util_hash_table *ht,
+ enum pipe_error (*callback)
+ (void *key, void *value, void *data),
+ void *data)
{
struct cso_hash_iter iter;
- struct hash_table_item *item;
+ struct util_hash_table_item *item;
enum pipe_error result;
-
+
assert(ht);
-
+ if (!ht)
+ return PIPE_ERROR_BAD_INPUT;
+
iter = cso_hash_first_node(ht->cso);
while (!cso_hash_iter_is_null(iter)) {
- item = (struct hash_table_item *)cso_hash_iter_data(iter);
+ item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
result = callback(item->key, item->value, data);
if(result != PIPE_OK)
return result;
}
+static enum pipe_error
+util_hash_inc(UNUSED void *k, UNUSED void *v, void *d)
+{
+ ++*(size_t *)d;
+ return PIPE_OK;
+}
+
+
+size_t
+util_hash_table_count(struct util_hash_table *ht)
+{
+ size_t count = 0;
+ util_hash_table_foreach(ht, util_hash_inc, &count);
+ return count;
+}
+
+
void
-hash_table_destroy(struct hash_table *ht)
+util_hash_table_destroy(struct util_hash_table *ht)
{
struct cso_hash_iter iter;
- struct hash_table_item *item;
-
+ struct util_hash_table_item *item;
+
assert(ht);
-
+ if (!ht)
+ return;
+
iter = cso_hash_first_node(ht->cso);
while (!cso_hash_iter_is_null(iter)) {
- item = (struct hash_table_item *)cso_hash_iter_data(iter);
+ item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
FREE(item);
iter = cso_hash_iter_next(iter);
}