src/gallium/auxiliary/util/u_hash_table.c

/**************************************************************************
 *
 * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
 * 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 TUNGSTEN GRAPHICS 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
 * General purpose hash table implementation.
 * 
 * Just uses the cso_hash for now, but it might be better switch to a linear 
 * probing hash table implementation at some point -- as it is said they have 
 * 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>
 */


#include "pipe/p_compiler.h"
#include "util/u_debug.h"

#include "cso_cache/cso_hash.h"

#include "util/u_memory.h"
#include "util/u_hash_table.h"


struct util_hash_table
{
   struct cso_hash *cso;   
   
   /** Hash function */
   unsigned (*hash)(void *key);
   
   /** Compare two keys */
   int (*compare)(void *key1, void *key2);
   
   /* TODO: key, value destructors? */
};


struct util_hash_table_item
{
   void *key;
   void *value;
};


static INLINE struct util_hash_table_item *
util_hash_table_item(struct cso_hash_iter iter)
{
   return (struct util_hash_table_item *)cso_hash_iter_data(iter);
}


struct util_hash_table *
util_hash_table_create(unsigned (*hash)(void *key),
                       int (*compare)(void *key1, void *key2))
{
   struct util_hash_table *ht;
   
   ht = MALLOC_STRUCT(util_hash_table);
   if(!ht)
      return NULL;
   
   ht->cso = cso_hash_create();
   if(!ht->cso) {
      FREE(ht);
      return NULL;
   }
   
   ht->hash = hash;
   ht->compare = compare;
   
   return ht;
}


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 util_hash_table_item *item;
   
   iter = cso_hash_find(ht->cso, key_hash);
   while (!cso_hash_iter_is_null(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);
   }
   
   return iter;
}


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 util_hash_table_item *item;
   
   iter = cso_hash_find(ht->cso, key_hash);
   while (!cso_hash_iter_is_null(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);
   }
   
   return NULL;
}


enum pipe_error
util_hash_table_set(struct util_hash_table *ht,
                    void *key,
                    void *value)
{
   unsigned key_hash;
   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 = util_hash_table_find_item(ht, key, key_hash);
   if(item) {
      /* TODO: key/value destruction? */
      item->value = value;
      return PIPE_OK;
   }
   
   item = MALLOC_STRUCT(util_hash_table_item);
   if(!item)
      return PIPE_ERROR_OUT_OF_MEMORY;
   
   item->key = key;
   item->value = value;
   
   iter = cso_hash_insert(ht->cso, key_hash, item);
   if(cso_hash_iter_is_null(iter)) {
      FREE(item);
      return PIPE_ERROR_OUT_OF_MEMORY;
   }

   return PIPE_OK;
}


void *
util_hash_table_get(struct util_hash_table *ht,
                    void *key)
{
   unsigned key_hash;
   struct util_hash_table_item *item;

   assert(ht);
   if (!ht)
      return NULL;

   key_hash = ht->hash(key);

   item = util_hash_table_find_item(ht, key, key_hash);
   if(!item)
      return NULL;
   
   return item->value;
}


void
util_hash_table_remove(struct util_hash_table *ht,
                       void *key)
{
   unsigned key_hash;
   struct cso_hash_iter iter;
   struct util_hash_table_item *item;

   assert(ht);
   if (!ht)
      return;

   key_hash = ht->hash(key);

   iter = util_hash_table_find_iter(ht, key, key_hash);
   if(cso_hash_iter_is_null(iter))
      return;
   
   item = util_hash_table_item(iter);
   assert(item);
   FREE(item);
   
   cso_hash_erase(ht->cso, iter);
}


void 
util_hash_table_clear(struct util_hash_table *ht)
{
   struct cso_hash_iter iter;
   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 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
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 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 util_hash_table_item *)cso_hash_iter_data(iter);
      result = callback(item->key, item->value, data);
      if(result != PIPE_OK)
	 return result;
      iter = cso_hash_iter_next(iter);
   }

   return PIPE_OK;
}


void
util_hash_table_destroy(struct util_hash_table *ht)
{
   struct cso_hash_iter iter;
   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 util_hash_table_item *)cso_hash_iter_data(iter);
      FREE(item);
      iter = cso_hash_iter_next(iter);
   }

   cso_hash_delete(ht->cso);
   
   FREE(ht);
}