BRL-CAD
hash.c
Go to the documentation of this file.
1 /* H A S H . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #include "common.h"
22 
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <math.h>
26 #include <string.h>
27 
28 #include "bu/magic.h"
29 #include "bu/hash.h"
30 
31 unsigned long
32 bu_hash(const unsigned char *str, int len)
33 {
34  unsigned long hash = 5381;
35  int i, c;
36 
37  for (i=0; i<len; i++) {
38  c = *str;
39  hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
40  str++;
41  }
42 
43  return hash;
44 }
45 
46 
47 struct bu_hash_tbl *
48 bu_hash_tbl_create(unsigned long tbl_size)
49 {
50  struct bu_hash_tbl *hsh_tbl;
51  unsigned long power_of_two=64;
52  int power=6;
53  int max_power=(sizeof(unsigned long) * 8) - 1;
54 
55  /* allocate the table structure (do not use bu_malloc() as this
56  * may be used for MEM_DEBUG).
57  */
58  hsh_tbl = (struct bu_hash_tbl *)malloc(sizeof(struct bu_hash_tbl));
59  if (UNLIKELY(!hsh_tbl)) {
60  fprintf(stderr, "Failed to allocate hash table\n");
61  return (struct bu_hash_tbl *)NULL;
62  }
63 
64  /* the number of bins in the hash table will be a power of two */
65  while (power_of_two < tbl_size && power < max_power) {
66  power_of_two = power_of_two << 1;
67  power++;
68  }
69 
70  if (power == max_power) {
71  int i;
72 
73  hsh_tbl->mask = 1;
74  for (i=1; i<max_power; i++) {
75  hsh_tbl->mask = (hsh_tbl->mask << 1) + 1;
76  }
77  hsh_tbl->num_lists = hsh_tbl->mask + 1;
78  } else {
79  hsh_tbl->num_lists = power_of_two;
80  hsh_tbl->mask = power_of_two - 1;
81  }
82 
83  /* allocate the bins (do not use bu_malloc() as this may be used
84  * for MEM_DEBUG)
85  */
86  hsh_tbl->lists = (struct bu_hash_entry **)calloc(hsh_tbl->num_lists, sizeof(struct bu_hash_entry *));
87 
88  hsh_tbl->num_entries = 0;
89  hsh_tbl->magic = BU_HASH_TBL_MAGIC;
90 
91  return hsh_tbl;
92 }
93 
94 struct bu_hash_entry *
95 bu_hash_tbl_find(const struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, struct bu_hash_entry **prev, unsigned long *idx)
96 {
97  struct bu_hash_entry *hsh_entry=NULL;
98  int found=0;
99 
100  BU_CK_HASH_TBL(hsh_tbl);
101 
102  /* calculate the index into the bin array */
103  *idx = bu_hash(key, key_len) & hsh_tbl->mask;
104  if (*idx >= hsh_tbl->num_lists) {
105  fprintf(stderr, "hash function returned too large value (%ld), only have %ld lists\n",
106  *idx, hsh_tbl->num_lists);
107  *prev = NULL;
108  return (struct bu_hash_entry *)NULL;
109  }
110 
111  /* look for the provided key in the list of entries in this bin */
112  *prev = NULL;
113  if (hsh_tbl->lists[*idx]) {
114  *prev = NULL;
115  hsh_entry = hsh_tbl->lists[*idx];
116  while (hsh_entry) {
117  const unsigned char *c1, *c2;
118  int i;
119 
120  /* compare key lengths first for performance */
121  if (hsh_entry->key_len != key_len) {
122  *prev = hsh_entry;
123  hsh_entry = hsh_entry->next;
124  continue;
125  }
126 
127  /* key lengths are the same, now compare the actual keys */
128  found = 1;
129  c1 = key;
130  c2 = hsh_entry->key;
131  for (i=0; i<key_len; i++) {
132  if (*c1 != *c2) {
133  found = 0;
134  break;
135  }
136  c1++;
137  c2++;
138  }
139 
140  /* if we have a match, get out of this loop */
141  if (found) break;
142 
143  /* step to next entry in this bin */
144  *prev = hsh_entry;
145  hsh_entry = hsh_entry->next;
146  }
147  }
148 
149  if (found) {
150  /* return the found entry */
151  return hsh_entry;
152  } else {
153  /* did not find the entry, return NULL */
154  return (struct bu_hash_entry *)NULL;
155  }
156 }
157 
158 
159 void
160 bu_set_hash_value(struct bu_hash_entry *hsh_entry, unsigned char *value)
161 {
162  BU_CK_HASH_ENTRY(hsh_entry);
163 
164  /* just copy a pointer */
165  hsh_entry->value = value;
166 }
167 
168 
169 unsigned char *
170 bu_get_hash_value(const struct bu_hash_entry *hsh_entry)
171 {
172  BU_CK_HASH_ENTRY(hsh_entry);
173 
174  return hsh_entry->value;
175 }
176 
177 
178 unsigned char *
179 bu_get_hash_key(const struct bu_hash_entry *hsh_entry)
180 {
181  BU_CK_HASH_ENTRY(hsh_entry);
182 
183  return hsh_entry->key;
184 }
185 
186 
187 struct bu_hash_entry *
188 bu_hash_tbl_add(struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, int *new_entry)
189 {
190  struct bu_hash_entry *hsh_entry, *prev;
191  unsigned long idx;
192 
193  BU_CK_HASH_TBL(hsh_tbl);
194 
195  /* do a find for three reasons.
196  * does this key already exist in the table?
197  * get the hash bin index for this key.
198  * find the previous entry to link the new one to.
199  */
200  hsh_entry = bu_hash_tbl_find(hsh_tbl, key, key_len, &prev, &idx);
201 
202  if (hsh_entry) {
203  /* this key is already in the table, return the entry, with
204  * flag set to 0
205  */
206  *new_entry = 0;
207  return hsh_entry;
208  }
209 
210  if (prev) {
211  /* already have an entry in this bin, just link to it */
212  prev->next = (struct bu_hash_entry *)calloc(1, sizeof(struct bu_hash_entry));
213  hsh_entry = prev->next;
214  } else {
215  /* first entry in this bin */
216  hsh_entry = (struct bu_hash_entry *)calloc(1, sizeof(struct bu_hash_entry));
217  hsh_tbl->lists[idx] = hsh_entry;
218  }
219 
220  /* fill in the structure */
221  hsh_entry->next = NULL;
222  hsh_entry->value = NULL;
223  hsh_entry->key_len = key_len;
224  hsh_entry->magic = BU_HASH_ENTRY_MAGIC;
225 
226  /* make a copy of the key */
227  hsh_entry->key = (unsigned char *)malloc((size_t)key_len);
228  memcpy(hsh_entry->key, key, (size_t)key_len);
229 
230  /* set "new" flag, increment count of entries, and return new
231  * entry.
232  */
233  *new_entry = 1;
234  hsh_tbl->num_entries++;
235  return hsh_entry;
236 }
237 
238 
239 void
240 bu_hash_tbl_print(const struct bu_hash_tbl *hsh_tbl, const char *str)
241 {
242  unsigned long idx;
243  struct bu_hash_entry *hsh_entry;
244 
245  BU_CK_HASH_TBL(hsh_tbl);
246 
247  fprintf(stderr, "%s\n", str);
248  fprintf(stderr, "bu_hash_table (%ld entries):\n", hsh_tbl->num_entries);
249 
250  /* visit all the entries in this table */
251  for (idx=0; idx<hsh_tbl->num_lists; idx++) {
252  hsh_entry = hsh_tbl->lists[idx];
253  while (hsh_entry) {
254  BU_CK_HASH_ENTRY(hsh_entry);
255  fprintf(stderr, "\tindex=%ld, key=%p, value=%p\n", idx, (void *)hsh_entry->key, (void *)hsh_entry->value);
256  hsh_entry = hsh_entry->next;
257  }
258  }
259 }
260 
261 
262 void
264 {
265  unsigned long idx;
266  struct bu_hash_entry *hsh_entry, *tmp;
267 
268  BU_CK_HASH_TBL(hsh_tbl);
269 
270  /* loop through all the bins in this hash table */
271  for (idx=0; idx<hsh_tbl->num_lists; idx++) {
272  /* traverse all the entries in the list for this bin */
273  hsh_entry = hsh_tbl->lists[idx];
274  while (hsh_entry) {
275  BU_CK_HASH_ENTRY(hsh_entry);
276  tmp = hsh_entry->next;
277 
278  /* free the copy of the key, and this entry */
279  free(hsh_entry->key);
280  free(hsh_entry);
281 
282  /* step to next entry in linked list */
283  hsh_entry = tmp;
284  }
285  }
286 
287  /* free the array of bins */
288  free(hsh_tbl->lists);
289 
290  /* free the actual hash table structure */
291  free(hsh_tbl);
292 }
293 
294 
295 struct bu_hash_entry *
296 bu_hash_tbl_first(const struct bu_hash_tbl *hsh_tbl, struct bu_hash_record *rec)
297 {
298  BU_CK_HASH_TBL(hsh_tbl);
299 
300  /* initialize the record structure */
302  rec->tbl = hsh_tbl;
303  rec->index = (unsigned long)-1;
304  rec->hsh_entry = (struct bu_hash_entry *)NULL;
305 
306  if (hsh_tbl->num_entries == 0) {
307  /* this table is empty */
308  return (struct bu_hash_entry *)NULL;
309  }
310 
311  /* loop through all the bins in this hash table, looking for a
312  * non-null entry
313  */
314  for (rec->index=0; rec->index < hsh_tbl->num_lists; rec->index++) {
315  rec->hsh_entry = hsh_tbl->lists[rec->index];
316  if (rec->hsh_entry) {
317  return rec->hsh_entry;
318  }
319  }
320 
321  /* no entry found, return NULL */
322  return (struct bu_hash_entry *)NULL;
323 }
324 
325 
326 struct bu_hash_entry *
328 {
329  const struct bu_hash_tbl *hsh_tbl;
330 
331  BU_CK_HASH_RECORD(rec);
332  hsh_tbl = rec->tbl;
333  BU_CK_HASH_TBL(hsh_tbl);
334 
335  /* if the entry in the record structure has a non-null "next",
336  * return it, and update the record structure
337  */
338  if (rec->hsh_entry) {
339  rec->hsh_entry = rec->hsh_entry->next;
340  if (rec->hsh_entry) {
341  return rec->hsh_entry;
342  }
343  }
344 
345  /* must move to a new bin to find another entry */
346  for (rec->index++; rec->index < hsh_tbl->num_lists; rec->index++) {
347  rec->hsh_entry = hsh_tbl->lists[rec->index];
348  if (rec->hsh_entry) {
349  return rec->hsh_entry;
350  }
351  }
352 
353  /* no more entries, return NULL */
354  return (struct bu_hash_entry *)NULL;
355 }
356 
357 struct bu_hash_entry *
358 bu_hash_tbl_traverse(struct bu_hash_tbl *hsh_tbl, int (*func)(struct bu_hash_entry *, void *), void *func_arg)
359 {
360  int ret;
361  struct bu_hash_record rec;
362  struct bu_hash_entry *entry;
363 
364  entry = bu_hash_tbl_first(hsh_tbl, &rec);
365  while (entry) {
366  ret = func(entry, func_arg);
367  if (ret) {
368  return entry;
369  }
370  entry = bu_hash_tbl_next(&rec);
371  }
372  return NULL;
373 }
374 
375 
376 /*
377  * Local Variables:
378  * mode: C
379  * tab-width: 8
380  * indent-tabs-mode: t
381  * c-file-style: "stroustrup"
382  * End:
383  * ex: shiftwidth=4 tabstop=8
384  */
unsigned char * bu_get_hash_value(const struct bu_hash_entry *hsh_entry)
Definition: hash.c:170
uint32_t magic
Definition: hash.h:85
void bu_hash_tbl_free(struct bu_hash_tbl *hsh_tbl)
Definition: hash.c:263
#define BU_HASH_RECORD_MAGIC
Definition: magic.h:51
void bu_set_hash_value(struct bu_hash_entry *hsh_entry, unsigned char *value)
Definition: hash.c:160
struct bu_hash_entry * bu_hash_tbl_first(const struct bu_hash_tbl *hsh_tbl, struct bu_hash_record *rec)
Definition: hash.c:296
unsigned char * bu_get_hash_key(const struct bu_hash_entry *hsh_entry)
Definition: hash.c:179
Header file for the BRL-CAD common definitions.
unsigned char * value
Definition: hash.h:47
Definition: hash.h:44
void bu_hash_tbl_print(const struct bu_hash_tbl *hsh_tbl, const char *str)
Definition: hash.c:240
unsigned long index
Definition: hash.h:126
struct bu_hash_entry * hsh_entry
Definition: hash.h:127
unsigned long mask
Definition: hash.h:86
#define BU_HASH_ENTRY_MAGIC
Definition: magic.h:50
int key_len
Definition: hash.h:48
const struct bu_hash_tbl * tbl
Definition: hash.h:125
#define BU_CK_HASH_RECORD(_rp)
Definition: hash.h:135
struct bu_hash_entry * bu_hash_tbl_add(struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, int *new_entry)
Definition: hash.c:188
unsigned long num_lists
Definition: hash.h:87
#define BU_HASH_TBL_MAGIC
Definition: magic.h:52
unsigned char * key
Definition: hash.h:46
struct bu_hash_entry * bu_hash_tbl_next(struct bu_hash_record *rec)
Definition: hash.c:327
#define BU_CK_HASH_ENTRY(_ep)
Definition: hash.h:57
unsigned long bu_hash(const unsigned char *str, int len)
Definition: hash.c:32
#define BU_CK_HASH_TBL(_hp)
Definition: hash.h:97
unsigned long num_entries
Definition: hash.h:88
struct bu_hash_tbl * bu_hash_tbl_create(unsigned long tbl_size)
Definition: hash.c:48
struct bu_hash_entry ** lists
Definition: hash.h:89
struct bu_hash_entry * bu_hash_tbl_find(const struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, struct bu_hash_entry **prev, unsigned long *idx)
Definition: hash.c:95
struct bu_hash_entry * next
Definition: hash.h:49
uint32_t magic
Definition: hash.h:45
struct bu_hash_entry * bu_hash_tbl_traverse(struct bu_hash_tbl *hsh_tbl, int(*func)(struct bu_hash_entry *, void *), void *func_arg)
Definition: hash.c:358
uint32_t magic
Definition: hash.h:124
#define UNLIKELY(expression)
Definition: common.h:282