1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
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__*/
|
