1 #ifndef HAVE_SEARCH_H
2 /*
3 * hsearch() on Mac OS X 10.1.2 appears to be broken: there is no
4 * search.h; there is a search() in the C library, but it doesn't work
5 * properly. We include some hash functions here, protected by
6 * HAVE_SEARCH_H. Hopefully when search.h appears in Mac OS X,
7 * hsearch() will be fixed at the same time...
8 *
9 * Part of HTML-XML-utils, see:
10 * http://www.w3.org/Tools/HTML-XML-utils/
11 */
12
13 #include "config.h"
14 #include <stdlib.h>
15 #include <assert.h>
16 #include <string.h>
17 #include "export.h"
18 #include "heap.e"
19
20
21 EXPORT typedef struct entry {char *key; void *data;} ENTRY;
22 EXPORT typedef enum {FIND, ENTER} ACTION;
23
24 static ENTRY *htab;
25 static int *htab_index1, *htab_index2;
26 static unsigned int htab_size = 0;
27 static unsigned int htab_inited;
28
29
30 /* isprime -- test if n is a prime number */
isprime(unsigned int n)31 static int isprime(unsigned int n)
32 {
33 /* Simplistic algorithm, probably good enough for now */
34 unsigned int i;
35 assert(n % 2); /* n not even */
36 for (i = 3; i * i < n; i += 2) if (n % i == 0) return 0;
37 return 1;
38 }
39
40
41 /* hcreate -- create a hash table for at least nel entries */
hcreate(size_t nel)42 EXPORT int hcreate(size_t nel)
43 {
44 /* Change nel to next higher prime */
45 for (nel |= 1; !isprime(nel); nel += 2) ;
46
47 /* Allocate hash table and array to keep track of initialized entries */
48 newarray(htab, nel);
49 newarray(htab_index1, nel);
50 newarray(htab_index2, nel);
51 if (!htab || !htab_index1 || !htab_index2) {
52 dispose(htab);
53 dispose(htab_index1);
54 dispose(htab_index2);
55 return 0; /* Out of memory */
56 }
57 htab_inited = 0;
58 htab_size = nel;
59 return 1;
60 }
61
62
63 /* hdestroy -- deallocate hash table */
hdestroy(void)64 EXPORT void hdestroy(void)
65 {
66 assert(htab_size);
67 dispose(htab_index1);
68 dispose(htab_index2);
69 dispose(htab);
70 htab_size = 0;
71 }
72
73
74 /* hsearch -- search for and/or insert an entry in the hash table */
hsearch(ENTRY item,ACTION action)75 EXPORT ENTRY *hsearch(ENTRY item, ACTION action)
76 {
77 unsigned int hval, i;
78 char *p;
79
80 assert(htab_size); /* There must be a hash table */
81
82 /* Compute a hash value */
83 #if 1
84 /* This function suggested by Dan Bernstein */
85 for (hval = 5381, p = item.key; *p; p++) hval = (hval * 33) ^ *p;
86 #else
87 i = hval = strlen(item.key);
88 do {i--; hval = (hval << 1) + item.key[i];} while (i > 0);
89 #endif
90 hval %= htab_size;
91 /* if (action == ENTER) debug("%d\n", hval); */
92
93 /* Look for either an empty slot or an entry with the wanted key */
94 i = hval;
95 while (htab_index1[i] < htab_inited
96 && htab_index2[htab_index1[i]] == i
97 && strcmp(htab[i].key, item.key) != 0) {
98 i = (i + 1) % htab_size; /* "Open" hash method */
99 if (i == hval) return NULL; /* Made full round */
100 }
101 /* Now we either have an empty slot or an entry with the same key */
102 if (action == ENTER) {
103 htab[i].key = item.key; /* Put the item in this slot */
104 htab[i].data = item.data;
105 if (htab_index1[i] >= htab_inited || htab_index2[htab_index1[i]] != i) {
106 /* Item was not yet used, mark it as used */
107 htab_index1[i] = htab_inited;
108 htab_index2[htab_inited] = i;
109 htab_inited++;
110 }
111 return &htab[i];
112 } else if (htab_index1[i] < htab_inited && htab_index2[htab_index1[i]] == i)
113 return &htab[i]; /* action == FIND, found key */
114
115 return NULL; /* Found empty slot */
116 }
117
118 #endif /* HAVE_SEARCH_H */
119