File: hashtab.c

package info (click to toggle)
acct 6.5.4-2.1
  • links: PTS
  • area: main
  • in suites: squeeze
  • size: 3,132 kB
  • ctags: 1,428
  • sloc: sh: 10,390; ansic: 9,695; cpp: 289; makefile: 185
file content (313 lines) | stat: -rw-r--r-- 7,787 bytes parent folder | download | duplicates (6)
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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
/* hashtab.c
 *
 * generic hash table routines
 *
 */

#include "config.h"

#include <stdio.h>

#ifdef HAVE_STRING_H
#include <string.h>
#endif

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#include "common.h"
#include "hashtab.h"

#define INITIAL_TABLE_SIZE 7	/* number of buckets */
#define RESIZE_MULTIPLIER 4	/* grow table by this factor */
#define RESIZE_SIZE_MULTIPLIER 0.6 /* grow table when it's 60% full */

/* A decent string hash function */

static
unsigned long
hash (const char *s, unsigned int len, unsigned long hashsize)
{
  unsigned long hashval;

  for (hashval = 0; len; s++, len--)
    hashval = *s + 31 * hashval;
  return hashval % hashsize;
}


/* Create and return a new hash table.  If NUMERIC is non-zero, items
   to be hashed are numeric and shouldn't be truncated like
   strings. */

struct hashtab *hashtab_init(int numeric)
{
  struct hashtab *new;

  new = (struct hashtab *) xmalloc (sizeof (struct hashtab));
  memset (new, 0, sizeof (struct hashtab));
  new->numeric = numeric;

  return new;
}

/* Return the smaller of the length of a string or the number passed
   in.  If 0 is passed, return the string length unconditionally. */

static unsigned int get_key_len(char *s, unsigned int len, int numeric)
{
  if (numeric)
    {
      if (len == 0)
        fatal ("hashtab.c (get_key_len): hashing a num with len == 0");
      if (len != numeric)
        fatal ("hashtab.c (get_key_len): hashing a num with len != numeric");
      return len;
    }
  else
    {
      if (!len)
        return strlen (s);
      else
        {
          unsigned int i;
          for (i = len; i && (*s != '\0'); s++, i--)
            ;
          return len - i;
        }
    }
}

/* When the number of entries gets too big for efficient use of the
   hash table, resize it. */

static void hashtab_resize(struct hashtab *ht)
{
  unsigned long old_size, bucket;
  struct hashtab_elem **old_table, *elt;

  /* Save the old values. */

  old_size = ht->table_size;
  old_table = ht->table;

  /* Resize and allocate a new table. */

  ht->table_size *= RESIZE_MULTIPLIER;
  ht->resize_size = ht->table_size * RESIZE_SIZE_MULTIPLIER;
  ht->table = (struct hashtab_elem **)
              xmalloc (sizeof (struct hashtab_elem *) * ht->table_size);
  memset (ht->table, 0, sizeof (struct hashtab_elem *) * ht->table_size);

  /* Step through each key in the old table, re-hashing and inserting
     into the new table.  We don't use the HASHTAB_FIRST and
     HASHTAB_CREATE routines because we can do this more efficiently,
     knowing that each element is unique (don't need check the old
     ones in a bin on insert). */

  for (bucket = 0; bucket < old_size; bucket++)
    for (elt = old_table[bucket]; elt != NULL;)
      {
        struct hashtab_elem *old_next = elt->next;

        elt->hashval = hash (elt->key, elt->key_len, ht->table_size);
        elt->prev = NULL;
        elt->next = ht->table[elt->hashval];
        if (ht->table[elt->hashval])
          ht->table[elt->hashval]->prev = elt;
        ht->table[elt->hashval] = elt;

        elt = old_next;
      }

  /* Remove the old table. */

  free (old_table);
}

/* Create an entry for the given key.  If the key already exists,
   return the existing entry with the data cleared.  If LEN is 0,
   assume that the string is null-terminated.  Otherwise, only use LEN
   bytes. */

struct hashtab_elem *hashtab_create(struct hashtab *ht, void *key, unsigned int len)
{
  unsigned long hashval;
  unsigned int key_len;
  struct hashtab_elem *he;

  if (ht->table == NULL)
    {
      /* Create a fresh table. */
      ht->table_size = INITIAL_TABLE_SIZE;
      ht->items_hashed = 0;
      ht->resize_size = ht->table_size * RESIZE_SIZE_MULTIPLIER;
      ht->table = (struct hashtab_elem **)
                  xmalloc (sizeof (struct hashtab_elem *) * ht->table_size);
      memset (ht->table, 0, sizeof (struct hashtab_elem *) * ht->table_size);
    }

  /* Hash the key. */

  key_len = get_key_len (key, len, ht->numeric);
  hashval = hash (key, key_len, ht->table_size);

  /* We could use HASHTAB_FIND, but then we'd have to call STRLEN
     twice & etc. */

  for (he = ht->table[hashval]; he != NULL; he = he->next)
    {
      if ((he->key_len == key_len) && (memcmp (he->key, key, key_len) == 0))
        {
          /* Clear the existing data and return the entry. */
          he->data = NULL;
          return he;
        }
    }

  /* Create a new entry, since we didn't find one. */

  he = (struct hashtab_elem *) xmalloc (sizeof (struct hashtab_elem));
  he->key_len = key_len;
  he->key = (char *) xmalloc (sizeof (char) * (he->key_len + 1));
  memcpy (he->key, key, key_len);

  /* Make sure the key is null-terminated -- this won't hurt if we're
     using a numeric hash value, since the extra zero will never get
     considered. */

  ((char *) he->key)[he->key_len] = '\0';
  he->ht = ht;
  he->prev = NULL;
  he->hashval = hashval;
  he->next = ht->table[hashval];
  if (ht->table[hashval])
    ht->table[hashval]->prev = he;
  ht->table[hashval] = he;

  ht->items_hashed++;

  /* Are there too many items in the table? */

  if (ht->items_hashed > ht->resize_size)
    hashtab_resize (ht);

  return he;
}

/* Find KEY in HT and return the entry associated with it.  If LEN is
   0, assume that the string is null-terminated.  Otherwise, only use
   LEN bytes. */

struct hashtab_elem *hashtab_find(struct hashtab *ht, void *key, unsigned int len)
{
  unsigned long hashval;
  unsigned int key_len;
  struct hashtab_elem *he;

  if (ht->table == NULL)
    return NULL;

  key_len = get_key_len (key, len, ht->numeric);
  hashval = hash (key, key_len, ht->table_size);

  for (he = ht->table[hashval]; he != NULL; he = he->next)
    if ((he->key_len == key_len) && (memcmp (he->key, key, key_len) == 0))
      return he;

  return NULL;
}

/* Return the key associated with HE. */

void *hashtab_get_key(struct hashtab_elem *he)
{
  return he->key;
}

/* Return the data associated with HE. */

void *hashtab_get_value(struct hashtab_elem *he)
{
  return he->data;
}

/* Set the data for HE. */

void hashtab_set_value(struct hashtab_elem *he, void *v, unsigned int len)
{
  he->data = (void *) xmalloc (len);
  memcpy (he->data, v, len);
}

/* Return the first thing in the table. */

struct hashtab_elem *hashtab_first(struct hashtab *ht, struct hashtab_order *ho)
{
  ho->which = 0;
  ho->elem = NULL;
  ho->ht = ht;

  return hashtab_next (ho);
}

/* Given HO, return the next entry in the hash table. */

struct hashtab_elem *hashtab_next(struct hashtab_order *ho)
{
  unsigned long i;
  struct hashtab_elem *he;

  if (ho->elem)
    {
      he = ho->elem;
      ho->elem = he->next;
      if (he->next == NULL)
        ho->which++;
      return he;
    }

  for (i = ho->which; i < ho->ht->table_size; i++)
    for (he = ho->ht->table[i]; he != NULL; he = he->next)
      {
        ho->which = (he->next ? i : i + 1);
        ho->elem = he->next;
        return he;
      }
  return NULL;			/* nothing in the table */
}


void hashtab_dump_keys(struct hashtab *ht, FILE *out)
{
  struct hashtab_order ho;
  struct hashtab_elem *he;

  for (he = hashtab_first (ht, &ho);
       he != NULL;
       he = hashtab_next (&ho))
    fprintf (stddebug, "%s (%d)\n", (char *) he->key, he->key_len);
}

/* Delete the given element from the hash table.  We want to be able
   to call this in between calls to HASHTAB_NEXT so we can use the
   obvious way to delete items from the table. */

void hashtab_delete(struct hashtab_elem *he)
{
  he->ht->items_hashed--;

  if (he->prev)
    he->prev->next = he->next;
  else
    he->ht->table[he->hashval] = he->next;

  if (he->next)
    he->next->prev = he->prev;

  if (he->data)
    free (he->data);
  free (he->key);
  free (he);
}