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
|
/* hash.c
*
* Copyright (C) 1991, 1992, 1993, 1994, 1995, 1999, 2000, 2001, 2002,
* 2005 by Larry Wall and others
*
* You may distribute under the terms of either the GNU General Public
* License or the Artistic License, as specified in the README file.
*/
#include <stdio.h>
#include "EXTERN.h"
#include "a2p.h"
#include "util.h"
#ifdef NETWARE
char *savestr(char *str);
#endif
STR *
hfetch(register HASH *tb, char *key)
{
register char *s;
register int i;
register int hash;
register HENT *entry;
if (!tb)
return Nullstr;
for (s=key, i=0, hash = 0;
/* while */ *s;
s++, i++, hash *= 5) {
hash += *s * coeff[i];
}
entry = tb->tbl_array[hash & tb->tbl_max];
for (; entry; entry = entry->hent_next) {
if (entry->hent_hash != hash) /* strings can't be equal */
continue;
if (strNE(entry->hent_key,key)) /* is this it? */
continue;
return entry->hent_val;
}
return Nullstr;
}
bool
hstore(register HASH *tb, char *key, STR *val)
{
register char *s;
register int i;
register int hash;
register HENT *entry;
register HENT **oentry;
if (!tb)
return FALSE;
for (s=key, i=0, hash = 0;
/* while */ *s;
s++, i++, hash *= 5) {
hash += *s * coeff[i];
}
oentry = &(tb->tbl_array[hash & tb->tbl_max]);
i = 1;
for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
if (entry->hent_hash != hash) /* strings can't be equal */
continue;
if (strNE(entry->hent_key,key)) /* is this it? */
continue;
/*NOSTRICT*/
safefree(entry->hent_val);
entry->hent_val = val;
return TRUE;
}
/*NOSTRICT*/
entry = (HENT*) safemalloc(sizeof(HENT));
entry->hent_key = savestr(key);
entry->hent_val = val;
entry->hent_hash = hash;
entry->hent_next = *oentry;
*oentry = entry;
if (i) { /* initial entry? */
tb->tbl_fill++;
if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
hsplit(tb);
}
return FALSE;
}
void
hsplit(HASH *tb)
{
const int oldsize = tb->tbl_max + 1;
register int newsize = oldsize * 2;
register int i;
register HENT **a;
register HENT **b;
register HENT *entry;
register HENT **oentry;
a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
memset(&a[oldsize], 0, oldsize * sizeof(HENT*)); /* zero second half */
tb->tbl_max = --newsize;
tb->tbl_array = a;
for (i=0; i<oldsize; i++,a++) {
if (!*a) /* non-existent */
continue;
b = a+oldsize;
for (oentry = a, entry = *a; entry; entry = *oentry) {
if ((entry->hent_hash & newsize) != i) {
*oentry = entry->hent_next;
entry->hent_next = *b;
if (!*b)
tb->tbl_fill++;
*b = entry;
continue;
}
else
oentry = &entry->hent_next;
}
if (!*a) /* everything moved */
tb->tbl_fill--;
}
}
HASH *
hnew(void)
{
register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
tb->tbl_fill = 0;
tb->tbl_max = 7;
hiterinit(tb); /* so each() will start off right */
memset(tb->tbl_array, 0, 8 * sizeof(HENT*));
return tb;
}
int
hiterinit(register HASH *tb)
{
tb->tbl_riter = -1;
tb->tbl_eiter = Null(HENT*);
return tb->tbl_fill;
}
|
