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
|
/*-----------------------------------------------------------------------------------*/
#include <string.h>
#ifdef __STDC__
#include <stdlib.h>
#else
#include <malloc.h>
#endif
#include "../os_specific/sci_mem_alloc.h" /* MALLOC */
#include "mysearch.h"
/*-----------------------------------------------------------------------------------*/
typedef struct {
int used;
ENTRY entry;
} _ENTRY;
/*-----------------------------------------------------------------------------------*/
static _ENTRY * htable = NULL;
static unsigned hsize;
static unsigned filled;
/*-----------------------------------------------------------------------------------*/
/*
* For the used double hash method the table size has to be a prime. To
* correct the user given table size we need a prime test. This trivial
* algorithm is adequate because
* a) the code is (most probably) only called once per program run and
* b) the number is small because the table must fit in the core
*/
static int isprime(unsigned number)
{
/* no even number will be passed */
unsigned div = 3;
while (div*div < number && number%div != 0)
div += 2;
return number%div != 0;
}
/*-----------------------------------------------------------------------------------*/
/*
* Before using the hash table we must allocate memory for it.
* Test for an existing table are done. We allocate one element
* more as the found prime number says. This is done for more effective
* indexing as explained in the comment for the hsearch function.
* The contents of the table is zeroed, especially the field used
* becomes zero.
*/
int myhcreate(unsigned nel)
{
/* There is still another table active. Return with error. */
if (htable != NULL)
return 0;
/* Change nel to the first prime number not smaller as nel. */
nel |= 1; /* make odd */
while (!isprime(nel)) nel += 2;
hsize = nel;
filled = 0;
/* allocate memory and zero out */
if ((htable = (_ENTRY *)CALLOC(hsize+1, sizeof(_ENTRY))) == NULL)
return 0;
/* everything went alright */
return 1;
}
/*-----------------------------------------------------------------------------------*/
/*
* After using the hash table it has to be destroyed. The used memory can
* be freed and the local static variable can be marked as not used.
*/
void myhdestroy()
{
/* free used memory */
FREE(htable);
/* the sign for an existing table is an value != NULL in htable */
htable = NULL;
}
/*-----------------------------------------------------------------------------------*/
/*
* This is the search function. It uses double hashing with open adressing.
* The argument item.key has to be a pointer to an zero terminated, most
* probably strings of chars. The function for generating a number of the
* strings is simple but fast. It can be replaced by a more complex function
* like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
*
* We use an trick to speed up the lookup. The table is created by hcreate
* with one more element available. This enables us to use the index zero
* special. This index will never be used because we store the first hash
* index in the field used where zero means not used. Every other value
* means used. The used field can be used as a first fast comparison for
* equality of the stored and the parameter value. This helps to prevent
* unnecessary expensive calls of strcmp.
*/
ENTRY* myhsearch(ENTRY item,SCIACTION action)
{
register unsigned hval;
register unsigned hval2;
register unsigned count;
register unsigned len = strlen(item.key);
register unsigned idx;
/*
* If table is full and another entry should be entered return with
* error.
*/
if (action == SCIENTER && filled == hsize)
return NULL;
/* Compute an value for the given string. Perhaps use a better method. */
hval = len;
count = len;
while (count-- > 0) {
hval <<= 4;
hval += item.key[count];
}
/* First hash function: simply take the modul but prevent zero. */
hval %= hsize;
if (hval == 0) hval++;
/* The first index tried. */
idx = hval;
if (htable[idx].used) {
/* Further action might be required according to the action value. */
if (htable[idx].used == hval &&
strcmp(item.key, htable[idx].entry.key) == 0) {
if (action == SCIENTER)
htable[idx].entry.data = item.data;
return &htable[idx].entry;
}
/* Second hash function, as suggested in [Knuth] */
hval2 = 1 + hval % (hsize-2);
do {
/*
* Because hsize is prime this guarantees to step through all
* available indeces.
*/
if (idx <= hval2)
idx = hsize+idx-hval2;
else
idx -= hval2;
/* If entry is found use it. */
if (htable[idx].used == hval &&
strcmp(item.key, htable[idx].entry.key) == 0) {
if (action == SCIENTER)
htable[idx].entry.data = item.data;
return &htable[idx].entry;
}
} while (htable[idx].used);
}
/* An empty bucket has been found. */
if (action == SCIENTER) {
htable[idx].used = hval;
htable[idx].entry = item;
filled++;
return &htable[idx].entry;
} else
return NULL;
}
/*-----------------------------------------------------------------------------------*/
|
