diff options
Diffstat (limited to 'Source/DirectFB/lib/fusion/hash.h')
| -rwxr-xr-x | Source/DirectFB/lib/fusion/hash.h | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/Source/DirectFB/lib/fusion/hash.h b/Source/DirectFB/lib/fusion/hash.h new file mode 100755 index 0000000..8c8b459 --- /dev/null +++ b/Source/DirectFB/lib/fusion/hash.h @@ -0,0 +1,179 @@ +/* + GLIB - Library of useful routines for C programming + Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald + (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>, + Claudio Ciccani <klan@users.sf.net> and + Michael Emmel <memmel@gmail.com>. + + 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. +*/ + +/* + * Modified by the GLib Team and others 1997-2000. See the AUTHORS + * file for a list of people on the GLib Team. See the ChangeLog + * files for a list of changes. These files are distributed with + * GLib at ftp://ftp.gtk.org/pub/gtk/. + */ + +#ifndef __FUSION_HASH_H__ +#define __FUSION_HASH_H__ + +#include <fusion/types.h> +#include <fusion/shmalloc.h> +#include <string.h> + +#define FUSION_HASH_MIN_SIZE 11 +#define FUSION_HASH_MAX_SIZE 13845163 + +#define HASH_STR(h,p) \ +{\ + h = *p;\ + if (h)\ + for (p += 1; *p != '\0'; p++)\ + h = (h << 5) - h + *p;\ +}\ + +typedef enum { +HASH_PTR, +HASH_STRING, +HASH_INT +} +FusionHashType; + +typedef struct _FusionHashNode FusionHashNode; + +struct _FusionHashNode +{ + void *key; + void *value; + FusionHashNode *next; +}; + +struct __Fusion_FusionHash +{ + int magic; + bool local; + FusionHashType key_type; + FusionHashType value_type; + int size; + int nnodes; + FusionHashNode **nodes; + FusionSHMPoolShared *pool; + + bool free_keys; + bool free_values; +}; + +typedef bool (*FusionHashIteratorFunc)( FusionHash *hash, + void *key, + void *value, + void *ctx ); + + +DirectResult +fusion_hash_resize (FusionHash *hash); + +DirectResult +fusion_hash_create (FusionSHMPoolShared *pool, + FusionHashType key_type, + FusionHashType value_type, + int size, FusionHash **ret_hash ); + +DirectResult +fusion_hash_create_local (FusionHashType key_type, FusionHashType value_type, + int size, FusionHash **ret_hash ); + +DirectResult +fusion_hash_remove (FusionHash *hash, + const void * key, + void **old_key, + void **old_value); + +DirectResult +fusion_hash_insert( FusionHash *hash, void *key, void *value ); + +DirectResult +fusion_hash_replace (FusionHash *hash, + void * key, + void * value, + void **old_key, + void **old_value); +void +fusion_hash_destroy( FusionHash *hash ); + +void +fusion_hash_set_autofree( FusionHash *hash, bool free_keys, bool free_values ); + +void * +fusion_hash_lookup (FusionHash *hash, const void * key); + +void +fusion_hash_iterate( FusionHash *hash, + FusionHashIteratorFunc func, + void *ctx ); + +unsigned int +fusion_hash_size (FusionHash *hash); + +bool fusion_hash_should_resize ( FusionHash *hash); + + +static inline FusionHashNode** +fusion_hash_lookup_node (FusionHash *hash, + const void * key) +{ + FusionHashNode **node; + + /*TODO We could also optimize pointer hashing*/ + if (hash->key_type == HASH_STRING ) + { + unsigned int h; + const signed char *p = key; + HASH_STR(h,p) + node = &hash->nodes[h % hash->size]; + } + else + node = &hash->nodes[((unsigned long)key) % hash->size]; + + /* Hash table lookup needs to be fast. + * We therefore remove the extra conditional of testing + * whether to call the key_equal_func or not from + * the inner loop. + */ + if (hash->key_type == HASH_STRING ) { + while(*node && strcmp((const char *)(*node)->key,(const char*)key)) + node = &(*node)->next; + } + else + while (*node && (*node)->key != key) + node = &(*node)->next; + + return node; + +} + + + +#endif /*__FUSION_HASH_H__*/ + |