diff options
Diffstat (limited to 'Source/DirectFB/lib/direct/hash.c')
| -rwxr-xr-x | Source/DirectFB/lib/direct/hash.c | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/Source/DirectFB/lib/direct/hash.c b/Source/DirectFB/lib/direct/hash.c new file mode 100755 index 0000000..729e866 --- /dev/null +++ b/Source/DirectFB/lib/direct/hash.c @@ -0,0 +1,268 @@ +/* + (c) Copyright 2001-2009 The world wide DirectFB Open Source Community (directfb.org) + (c) Copyright 2000-2004 Convergence (integrated media) GmbH + + All rights reserved. + + Written by Denis Oliver Kropp <dok@directfb.org>, + Andreas Hundt <andi@fischlustig.de>, + Sven Neumann <neo@directfb.org>, + Ville Syrjälä <syrjala@sci.fi> and + Claudio Ciccani <klan@users.sf.net>. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the + Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#include <config.h> + +#include <stdlib.h> + +#include <direct/debug.h> +#include <direct/hash.h> +#include <direct/mem.h> +#include <direct/messages.h> + + +D_DEBUG_DOMAIN( Direct_Hash, "Direct/Hash", "Hash table implementation" ); + + +#define REMOVED ((void *) -1) + +typedef struct { + unsigned long key; + void *value; +} Element; + +struct __D_DirectHash { + int magic; + + int size; + + int count; + int removed; + + Element *elements; +}; + +/**************************************************************************************************/ + +static inline int +locate_key( const DirectHash *hash, unsigned long key ) +{ + int pos; + const Element *element; + + pos = key % hash->size; + + element = &hash->elements[pos]; + + while (element->value) { + if (element->value != REMOVED && element->key == key) + return pos; + + if (++pos == hash->size) + pos = 0; + + element = &hash->elements[pos]; + } + + return -1; +} + +/**************************************************************************************************/ + +DirectResult +direct_hash_create( int size, + DirectHash **ret_hash ) +{ + DirectHash *hash; + + if (size < 17) + size = 17; + + D_DEBUG_AT( Direct_Hash, "Creating hash table with initial capacity of %d...\n", size ); + + hash = D_CALLOC( 1, sizeof (DirectHash) ); + if (!hash) { + D_WARN( "out of memory" ); + return DR_NOLOCALMEMORY; + } + + hash->size = size; + hash->elements = D_CALLOC( size, sizeof(Element) ); + + if (!hash->elements) { + D_WARN( "out of memory" ); + D_FREE( hash ); + return DR_NOLOCALMEMORY; + } + + D_MAGIC_SET( hash, DirectHash ); + + *ret_hash = hash; + + return DR_OK; +} + +void +direct_hash_destroy( DirectHash *hash ) +{ + D_MAGIC_ASSERT( hash, DirectHash ); + + D_MAGIC_CLEAR( hash ); + + D_FREE( hash->elements ); + D_FREE( hash ); +} + +DirectResult +direct_hash_insert( DirectHash *hash, + unsigned long key, + void *value ) +{ + int pos; + Element *element; + + D_MAGIC_ASSERT( hash, DirectHash ); + D_ASSERT( value != NULL ); + + /* Need to resize the hash table? */ + if ((hash->count + hash->removed) > hash->size / 4) { + int i, size = hash->size * 3; + Element *elements; + + D_DEBUG_AT( Direct_Hash, "Resizing from %d to %d... (count %d, removed %d)\n", + hash->size, size, hash->count, hash->removed ); + + elements = D_CALLOC( size, sizeof(Element) ); + if (!elements) { + D_WARN( "out of memory" ); + return DR_NOLOCALMEMORY; + } + + for (i=0; i<hash->size; i++) { + Element *element = &hash->elements[i]; + Element *insertElement; + + if (element->value && element->value != REMOVED) { + pos = element->key % size; + + insertElement = &elements[pos]; + while (insertElement->value && insertElement->value != REMOVED) { + if (++pos == size) + pos = 0; + insertElement = &elements[pos]; + } + + elements[pos] = *element; + } + } + + D_FREE( hash->elements ); + + hash->size = size; + hash->elements = elements; + hash->removed = 0; + } + + pos = key % hash->size; + + D_DEBUG_AT( Direct_Hash, "Attempting to insert key 0x%08lx at position %d...\n", key, pos ); + + element = &hash->elements[pos]; + + while (element->value && element->value != REMOVED) { + if (element->key == key) { + D_BUG( "key already exists" ); + return DR_BUG; + } + + if (++pos == hash->size) + pos = 0; + + element = &hash->elements[pos]; + } + + if (element->value == REMOVED) + hash->removed--; + + element->key = key; + element->value = value; + + hash->count++; + + D_DEBUG_AT( Direct_Hash, "...inserted at %d, new count = %d, removed = %d, size = %d, key = 0x%08lx.\n", + pos, hash->count, hash->removed, hash->size, key ); + + return DR_OK; +} + +void +direct_hash_remove( DirectHash *hash, + unsigned long key ) +{ + int pos; + + D_MAGIC_ASSERT( hash, DirectHash ); + + pos = locate_key( hash, key ); + if (pos == -1) { + D_WARN( "key not found" ); + return; + } + + hash->elements[pos].value = REMOVED; + + hash->count--; + hash->removed++; + + D_DEBUG_AT( Direct_Hash, "Removed key 0x%08lx at %d, new count = %d, removed = %d, size = %d.\n", + key, pos, hash->count, hash->removed, hash->size ); +} + +void * +direct_hash_lookup( DirectHash *hash, + unsigned long key ) +{ + int pos; + + D_MAGIC_ASSERT( hash, DirectHash ); + + pos = locate_key( hash, key ); + + return (pos != -1) ? hash->elements[pos].value : NULL; +} + +void +direct_hash_iterate( DirectHash *hash, + DirectHashIteratorFunc func, + void *ctx ) +{ + int i; + + D_MAGIC_ASSERT( hash, DirectHash ); + + for (i=0; i<hash->size; i++) { + Element *element = &hash->elements[i]; + + if (!element->value || element->value == REMOVED) + continue; + + if (!func( hash, element->key, element->value, ctx ) ) + return; + } +} + |