1 /*
2    (c) Copyright 2001-2009  The world wide DirectFB Open Source Community (directfb.org)
3    (c) Copyright 2000-2004  Convergence (integrated media) GmbH
4 
5    All rights reserved.
6 
7    Written by Denis Oliver Kropp <dok@directfb.org>,
8               Andreas Hundt <andi@fischlustig.de>,
9               Sven Neumann <neo@directfb.org>,
10               Ville Syrjälä <syrjala@sci.fi> and
11               Claudio Ciccani <klan@users.sf.net>.
12 
13    This library is free software; you can redistribute it and/or
14    modify it under the terms of the GNU Lesser General Public
15    License as published by the Free Software Foundation; either
16    version 2 of the License, or (at your option) any later version.
17 
18    This library is distributed in the hope that it will be useful,
19    but WITHOUT ANY WARRANTY; without even the implied warranty of
20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21    Lesser General Public License for more details.
22 
23    You should have received a copy of the GNU Lesser General Public
24    License along with this library; if not, write to the
25    Free Software Foundation, Inc., 59 Temple Place - Suite 330,
26    Boston, MA 02111-1307, USA.
27 */
28 
29 #include <config.h>
30 
31 #include <stdlib.h>
32 
33 #include <direct/debug.h>
34 #include <direct/hash.h>
35 #include <direct/mem.h>
36 #include <direct/messages.h>
37 
38 
39 D_DEBUG_DOMAIN( Direct_Hash, "Direct/Hash", "Hash table implementation" );
40 
41 
42 #define REMOVED  ((void *) -1)
43 
44 typedef struct {
45      unsigned long  key;
46      void          *value;
47 } Element;
48 
49 struct __D_DirectHash {
50      int       magic;
51 
52      int       size;
53 
54      int       count;
55      int       removed;
56 
57      Element  *elements;
58 };
59 
60 /**************************************************************************************************/
61 
62 static inline int
locate_key(const DirectHash * hash,unsigned long key)63 locate_key( const DirectHash *hash, unsigned long key )
64 {
65      int            pos;
66      const Element *element;
67 
68      pos = key % hash->size;
69 
70      element = &hash->elements[pos];
71 
72      while (element->value) {
73           if (element->value != REMOVED && element->key == key)
74                return pos;
75 
76           if (++pos == hash->size)
77                pos = 0;
78 
79           element = &hash->elements[pos];
80      }
81 
82      return -1;
83 }
84 
85 /**************************************************************************************************/
86 
87 DirectResult
direct_hash_create(int size,DirectHash ** ret_hash)88 direct_hash_create( int          size,
89                     DirectHash **ret_hash )
90 {
91      DirectHash *hash;
92 
93      if (size < 17)
94           size = 17;
95 
96      D_DEBUG_AT( Direct_Hash, "Creating hash table with initial capacity of %d...\n", size );
97 
98      hash = D_CALLOC( 1, sizeof (DirectHash) );
99      if (!hash) {
100           D_WARN( "out of memory" );
101           return DR_NOLOCALMEMORY;
102      }
103 
104      hash->size     = size;
105      hash->elements = D_CALLOC( size, sizeof(Element) );
106 
107      if (!hash->elements) {
108           D_WARN( "out of memory" );
109           D_FREE( hash );
110           return DR_NOLOCALMEMORY;
111      }
112 
113      D_MAGIC_SET( hash, DirectHash );
114 
115      *ret_hash = hash;
116 
117      return DR_OK;
118 }
119 
120 void
direct_hash_destroy(DirectHash * hash)121 direct_hash_destroy( DirectHash *hash )
122 {
123      D_MAGIC_ASSERT( hash, DirectHash );
124 
125      D_MAGIC_CLEAR( hash );
126 
127      D_FREE( hash->elements );
128      D_FREE( hash );
129 }
130 
131 DirectResult
direct_hash_insert(DirectHash * hash,unsigned long key,void * value)132 direct_hash_insert( DirectHash    *hash,
133                     unsigned long  key,
134                     void          *value )
135 {
136      int      pos;
137      Element *element;
138 
139      D_MAGIC_ASSERT( hash, DirectHash );
140      D_ASSERT( value != NULL );
141 
142      /* Need to resize the hash table? */
143      if ((hash->count + hash->removed) > hash->size / 4) {
144           int      i, size = hash->size * 3;
145           Element *elements;
146 
147           D_DEBUG_AT( Direct_Hash, "Resizing from %d to %d... (count %d, removed %d)\n",
148                       hash->size, size, hash->count, hash->removed );
149 
150           elements = D_CALLOC( size, sizeof(Element) );
151           if (!elements) {
152                D_WARN( "out of memory" );
153                return DR_NOLOCALMEMORY;
154           }
155 
156           for (i=0; i<hash->size; i++) {
157                Element *element = &hash->elements[i];
158                Element *insertElement;
159 
160                if (element->value && element->value != REMOVED) {
161                     pos = element->key % size;
162 
163                     insertElement = &elements[pos];
164                     while (insertElement->value && insertElement->value != REMOVED) {
165                         if (++pos == size)
166                             pos = 0;
167                         insertElement = &elements[pos];
168                     }
169 
170                     elements[pos] = *element;
171                }
172           }
173 
174           D_FREE( hash->elements );
175 
176           hash->size     = size;
177           hash->elements = elements;
178           hash->removed  = 0;
179      }
180 
181      pos = key % hash->size;
182 
183      D_DEBUG_AT( Direct_Hash, "Attempting to insert key 0x%08lx at position %d...\n", key, pos );
184 
185      element = &hash->elements[pos];
186 
187      while (element->value && element->value != REMOVED) {
188           if (element->key == key) {
189                D_BUG( "key already exists" );
190                return DR_BUG;
191           }
192 
193           if (++pos == hash->size)
194                pos = 0;
195 
196           element = &hash->elements[pos];
197      }
198 
199      if (element->value == REMOVED)
200           hash->removed--;
201 
202      element->key   = key;
203      element->value = value;
204 
205      hash->count++;
206 
207      D_DEBUG_AT( Direct_Hash, "...inserted at %d, new count = %d, removed = %d, size = %d, key = 0x%08lx.\n",
208                  pos, hash->count, hash->removed, hash->size, key );
209 
210      return DR_OK;
211 }
212 
213 void
direct_hash_remove(DirectHash * hash,unsigned long key)214 direct_hash_remove( DirectHash    *hash,
215                     unsigned long  key )
216 {
217      int pos;
218 
219      D_MAGIC_ASSERT( hash, DirectHash );
220 
221      pos = locate_key( hash, key );
222      if (pos == -1) {
223           D_WARN( "key not found" );
224           return;
225      }
226 
227      hash->elements[pos].value = REMOVED;
228 
229      hash->count--;
230      hash->removed++;
231 
232      D_DEBUG_AT( Direct_Hash, "Removed key 0x%08lx at %d, new count = %d, removed = %d, size = %d.\n",
233                  key, pos, hash->count, hash->removed, hash->size );
234 }
235 
236 void *
direct_hash_lookup(DirectHash * hash,unsigned long key)237 direct_hash_lookup( DirectHash    *hash,
238                     unsigned long  key )
239 {
240      int pos;
241 
242      D_MAGIC_ASSERT( hash, DirectHash );
243 
244      pos = locate_key( hash, key );
245 
246      return (pos != -1) ? hash->elements[pos].value : NULL;
247 }
248 
249 void
direct_hash_iterate(DirectHash * hash,DirectHashIteratorFunc func,void * ctx)250 direct_hash_iterate( DirectHash             *hash,
251                      DirectHashIteratorFunc  func,
252                      void                   *ctx )
253 {
254      int i;
255 
256      D_MAGIC_ASSERT( hash, DirectHash );
257 
258      for (i=0; i<hash->size; i++) {
259           Element *element = &hash->elements[i];
260 
261           if (!element->value || element->value == REMOVED)
262                continue;
263 
264           if (!func( hash, element->key, element->value, ctx ) )
265                return;
266      }
267 }
268 
269