← Back to branch summary

~ubuntu-branches/ubuntu/trusty/lifelines/trusty

« back to all changes in this revision

Viewing changes to src/stdlib/hashtab.c

  • Committer: Bazaar Package Importer
  • Author(s): Felipe Augusto van de Wiel (faw)
  • Date: 2007-05-23 23:49:53 UTC
  • mfrom: (3.1.3 edgy)
  • Revision ID: james.westby@ubuntu.com-20070523234953-ogno9rnbmth61i7p
Tags: 3.0.50-2etch1
http://bugs.debian.org/418347
http://bugs.debian.org/405500
http://bugs.debian.org/356671
* Changing docs/ll-reportmanual.xml and docs/ll-userguide.xml to fix
  documentation build problems (Closes: #418347).

* lifelines-reports
  - Adding a dependency to lifelines >= 3.0.50 to prevent file conflict.
    (Closes: #405500).

* Updating French translation. Thanks to Bernard Adrian. (Closes: #356671).

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/stdlib/hashtab.c
 
1
/* 
 
2
   Copyright (c) 1991-1999 Thomas T. Wetmore IV
 
3
 
 
4
   Permission is hereby granted, free of charge, to any person
 
5
   obtaining a copy of this software and associated documentation
 
6
   files (the "Software"), to deal in the Software without
 
7
   restriction, including without limitation the rights to use, copy,
 
8
   modify, merge, publish, distribute, sublicense, and/or sell copies
 
9
   of the Software, and to permit persons to whom the Software is
 
10
   furnished to do so, subject to the following conditions:
 
11
 
 
12
   The above copyright notice and this permission notice shall be
 
13
   included in all copies or substantial portions of the Software.
 
14
 
 
15
   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 
16
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 
17
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 
18
   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 
19
   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 
20
   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 
21
   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 
22
   SOFTWARE.
 
23
*/
 
24
 
 
25
/*
 
26
 hashtab contains a simple hash table implementation
 
27
 keys are strings (hash table copies & manages memory itself for keys
 
28
 values (void * pointers, they are client's responsibility to free) 
 
29
*/
 
30
 
 
31
#include "llstdlib.h"
 
32
#include "hashtab.h"
 
33
 
 
34
/*********************************************
 
35
 * local enums & defines
 
36
 *********************************************/
 
37
 
 
38
#define MAXHASH_DEF 512
 
39
 
 
40
/*********************************************
 
41
 * local types
 
42
 *********************************************/
 
43
 
 
44
/* entry in hash table */
 
45
struct tag_hashent {
 
46
        CNSTRING magic;
 
47
        CNSTRING ekey;
 
48
        HVALUE val;
 
49
        struct tag_hashent *enext;
 
50
};
 
51
typedef struct tag_hashent *HASHENT;
 
52
 
 
53
/* hash table */
 
54
struct tag_hashtab {
 
55
        CNSTRING magic;
 
56
        HASHENT *entries;
 
57
        INT count; /* #entries */
 
58
        INT maxhash;
 
59
};
 
60
/* typedef struct tag_hashtab *HASHTAB */ /* in hashtab.h */
 
61
 
 
62
/* hash table iterator */
 
63
struct tag_hashtab_iter {
 
64
        CNSTRING magic;
 
65
        HASHTAB hashtab;
 
66
        INT index;
 
67
        HASHENT enext;
 
68
};
 
69
 
 
70
/*********************************************
 
71
 * local function prototypes
 
72
 *********************************************/
 
73
 
 
74
static HASHENT create_entry(CNSTRING key, HVALUE val);
 
75
static HASHENT fndentry(HASHTAB tab, CNSTRING key);
 
76
static INT hash(HASHTAB tab, CNSTRING key);
 
77
 
 
78
/*********************************************
 
79
 * local variables
 
80
 *********************************************/
 
81
 
 
82
/* fixed magic strings to verify object identity */
 
83
static CNSTRING hashtab_magic = "HASHTAB_MAGIC";
 
84
static CNSTRING hashent_magic = "HASHENT_MAGIC";
 
85
static CNSTRING hashtab_iter_magic = "HASHTAB_ITER_MAGIC";
 
86
 
 
87
/*********************************************
 
88
 * local & exported function definitions
 
89
 * body of module
 
90
 *********************************************/
 
91
 
 
92
/*================================
 
93
 * create_hashtab -- Create & return new hash table
 
94
 *==============================*/
 
95
HASHTAB
 
96
create_hashtab (void)
 
97
{
 
98
        HASHTAB tab = (HASHTAB)stdalloc(sizeof(*tab));
 
99
        tab->magic = hashtab_magic;
 
100
        tab->maxhash = MAXHASH_DEF;
 
101
        tab->entries = (HASHENT *)stdalloc(tab->maxhash * sizeof(HASHENT));
 
102
        return tab;
 
103
}
 
104
/*================================
 
105
 * destroy_hashtab -- Destroy hash table
 
106
 *==============================*/
 
107
void
 
108
destroy_hashtab (HASHTAB tab, DELFUNC func)
 
109
{
 
110
        INT i=0;
 
111
        if (!tab) return;
 
112
        ASSERT(tab->magic == hashtab_magic);
 
113
        for (i=0; i<tab->maxhash; ++i) {
 
114
                HASHENT entry = tab->entries[i];
 
115
                HASHENT next=0;
 
116
                while (entry) {
 
117
                        ASSERT(entry->magic == hashent_magic);
 
118
                        next = entry->enext;
 
119
                        if (func)
 
120
                                (*func)(entry->val);
 
121
                        entry->val = 0;
 
122
                        strfree((STRING *)&entry->ekey);
 
123
                        stdfree(entry);
 
124
                        entry = next;
 
125
                }
 
126
        }
 
127
        stdfree(tab->entries);
 
128
        tab->entries = 0;
 
129
        stdfree(tab);
 
130
}
 
131
/*======================
 
132
 * get_hashtab_count -- Return number of elements currently contained
 
133
 *====================*/
 
134
INT
 
135
get_hashtab_count (HASHTAB tab)
 
136
{
 
137
        ASSERT(tab);
 
138
        ASSERT(tab->magic == hashtab_magic);
 
139
 
 
140
        return tab->count;
 
141
}
 
142
/*======================
 
143
 * insert_hashtab -- Add new value to hash table
 
144
 * return previous value for this key, if any
 
145
 *====================*/
 
146
HVALUE
 
147
insert_hashtab (HASHTAB tab, CNSTRING key, HVALUE val)
 
148
{
 
149
        HASHENT entry=0;
 
150
        INT hval=0;
 
151
 
 
152
        ASSERT(tab);
 
153
        ASSERT(tab->magic == hashtab_magic);
 
154
 
 
155
        /* find appropriate has chain */
 
156
        hval = hash(tab, key);
 
157
        if (!tab->entries[hval]) {
 
158
                /* table lacks entry for this key, create it */
 
159
                entry = create_entry(key, val);
 
160
                tab->entries[hval] = entry;
 
161
                ++tab->count;
 
162
                return 0; /* no old value */
 
163
        }
 
164
        entry = tab->entries[hval];
 
165
        while (TRUE) {
 
166
                ASSERT(entry->magic == hashent_magic);
 
167
                if (eqstr(key, entry->ekey)) {
 
168
                        /* table already has entry for this key, replace it */
 
169
                        HVALUE old = entry->val;
 
170
                        entry->val = val;
 
171
                        return old;
 
172
                }
 
173
                if (!entry->enext) {
 
174
                        /* table lacks entry for this key, create it */
 
175
                        HASHENT newent = create_entry(key, val);
 
176
                        entry->enext = newent;
 
177
                        ++tab->count;
 
178
                        return 0; /* no old value */
 
179
                }
 
180
                entry = entry->enext;
 
181
        }
 
182
}
 
183
/*======================
 
184
 * remove_hashtab -- Remove element from table
 
185
 * return old value if found
 
186
 *====================*/
 
187
HVALUE
 
188
remove_hashtab (HASHTAB tab, CNSTRING key)
 
189
{
 
190
        HVALUE val=0;
 
191
        INT hval=0;
 
192
        HASHENT preve=0, thise=0;
 
193
 
 
194
        ASSERT(tab);
 
195
        ASSERT(tab->magic == hashtab_magic);
 
196
 
 
197
        hval = hash(tab, key);
 
198
        thise = tab->entries[hval];
 
199
        while (thise && nestr(key, thise->ekey)) {
 
200
                ASSERT(thise->magic == hashent_magic);
 
201
                preve = thise;
 
202
                thise = thise->enext;
 
203
        }
 
204
        if (!thise) return 0;
 
205
        if (preve)
 
206
                preve->enext = thise->enext;
 
207
        else
 
208
                tab->entries[hval] = thise->enext;
 
209
 
 
210
        val = thise->val;
 
211
        strfree((STRING *)&thise->ekey);
 
212
        thise->val = 0;
 
213
        stdfree(thise);
 
214
        --tab->count;
 
215
        return val;
 
216
}
 
217
/*======================
 
218
 * find_hashtab -- Find and return value
 
219
 *  set optional present arg to indicate whether value was found
 
220
 *====================*/
 
221
HVALUE
 
222
find_hashtab (HASHTAB tab, CNSTRING key, BOOLEAN * present)
 
223
{
 
224
        HASHENT entry=0;
 
225
 
 
226
        ASSERT(tab);
 
227
        ASSERT(tab->magic == hashtab_magic);
 
228
 
 
229
        entry = fndentry(tab, key);
 
230
        if (present) *present = !!entry;
 
231
        if (!entry) return 0;
 
232
 
 
233
        ASSERT(entry->magic == hashent_magic);
 
234
        return entry->val;
 
235
}
 
236
/*======================
 
237
 * in_hashtab -- Find and return value
 
238
 *====================*/
 
239
BOOLEAN
 
240
in_hashtab (HASHTAB tab, CNSTRING key)
 
241
{
 
242
        HASHENT entry=0;
 
243
 
 
244
        ASSERT(tab);
 
245
        ASSERT(tab->magic == hashtab_magic);
 
246
 
 
247
        entry = fndentry(tab, key);
 
248
        return (entry != 0);
 
249
}
 
250
/*================================
 
251
 * fndentry -- Find entry in table
 
252
 *==============================*/
 
253
static HASHENT
 
254
fndentry (HASHTAB tab, CNSTRING key)
 
255
{
 
256
        HASHENT entry=0;
 
257
        if (!tab || !key) return NULL;
 
258
        entry = tab->entries[hash(tab, key)];
 
259
        while (entry) {
 
260
                if (eqstr(key, entry->ekey)) return entry;
 
261
                entry = entry->enext;
 
262
        }
 
263
        return NULL;
 
264
}
 
265
/*======================
 
266
 * hash -- Hash function
 
267
 *====================*/
 
268
static INT
 
269
hash (HASHTAB tab, CNSTRING key)
 
270
{
 
271
        const unsigned char *ckey = (const unsigned char *)key;
 
272
        INT hval = 0;
 
273
        while (*ckey)
 
274
                hval += *ckey++;
 
275
        hval %= tab->maxhash;
 
276
        ASSERT(hval>=0 && hval < tab->maxhash);
 
277
        return hval;
 
278
}
 
279
/*================================
 
280
 * create_entry -- Create and return new hash entry
 
281
 *==============================*/
 
282
static HASHENT
 
283
create_entry (CNSTRING key, HVALUE val)
 
284
{
 
285
        HASHENT entry = (HASHENT)stdalloc(sizeof(*entry));
 
286
        entry->magic = hashent_magic;
 
287
        entry->ekey = strsave(key);
 
288
        entry->val = val;
 
289
        return entry;
 
290
}
 
291
/*================================
 
292
 * begin_hashtab -- Create new iterator for hash table
 
293
 *==============================*/
 
294
HASHTAB_ITER
 
295
begin_hashtab (HASHTAB tab)
 
296
{
 
297
        HASHTAB_ITER tabit=0;
 
298
        ASSERT(tab);
 
299
        ASSERT(tab->magic == hashtab_magic);
 
300
 
 
301
        tabit = (HASHTAB_ITER)stdalloc(sizeof(*tabit));
 
302
        tabit->magic = hashtab_iter_magic;
 
303
        tabit->hashtab = tab;
 
304
        /* table iterator starts at index=0, enext=0 */
 
305
        /* stdalloc gave us all zero memory */
 
306
        return tabit;
 
307
}
 
308
/*================================
 
309
 * next_hashtab -- Advance hash table iterator
 
310
 * If not finished, set pointers and return TRUE
 
311
 * If no more entries, return FALSE
 
312
 *==============================*/
 
313
BOOLEAN
 
314
next_hashtab (HASHTAB_ITER tabit, CNSTRING *pkey, HVALUE *pval)
 
315
{
 
316
        HASHTAB tab=0;
 
317
        ASSERT(tabit);
 
318
        ASSERT(tabit->magic == hashtab_iter_magic);
 
319
 
 
320
        if (!tabit->hashtab) return FALSE;
 
321
        tab = tabit->hashtab;
 
322
 
 
323
        if (tabit->index == -1 || tab->count == 0)
 
324
                return FALSE;
 
325
 
 
326
        /* continue current hash chain */
 
327
        if (tabit->enext) {
 
328
                tabit->enext = tabit->enext->enext;
 
329
                if (tabit->enext)
 
330
                        goto returnit;
 
331
                ++tabit->index;
 
332
        }
 
333
        /* find next populated hash chain */
 
334
        for ( ; tabit->index < tab->maxhash; ++tabit->index) {
 
335
                        tabit->enext = tab->entries[tabit->index];
 
336
                        if (tabit->enext)
 
337
                                goto returnit;
 
338
        }
 
339
        /* finished (ran out of hash chains) */
 
340
        tabit->index = -1;
 
341
        tabit->enext = 0;
 
342
        return FALSE;
 
343
 
 
344
        /* found entry */
 
345
returnit:
 
346
        *pkey = tabit->enext->ekey;
 
347
        *pval = tabit->enext->val;
 
348
        return TRUE;
 
349
 
 
350
}
 
351
/*================================
 
352
 * end_hashtab -- Release/destroy hash table iterator
 
353
 *==============================*/
 
354
void
 
355
end_hashtab (HASHTAB_ITER * ptabit)
 
356
{
 
357
        HASHTAB_ITER tabit = *ptabit;
 
358
        ASSERT(tabit);
 
359
        ASSERT(tabit->magic == hashtab_iter_magic);
 
360
 
 
361
        memset(tabit, 0, sizeof(*tabit));
 
362
        stdfree(tabit);
 
363
        *ptabit = 0;
 
364
}