blob: 3f3a85540d66c98b9b3e0936258f98f320146bb7 (
plain)
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
|
#include "strset.h"
#include "alloc.h"
#include "byte.h"
#include "str.h"
uint32 strset_hash(char *s)
{
unsigned char ch;
uint32 h;
h = 5381LL;
while ((ch = *s)) {
h = ((h << 5) + h) ^ ch;
++s;
}
return h;
}
int strset_init(strset *set)
{
int h;
set->mask = 15;
set->n = 0;
set->a = 10;
set->first = (int *)alloc(sizeof(int) * (set->mask + 1));
if (!set->first) return 0;
set->p = (strset_list *)alloc(sizeof(strset_list) * set->a);
if (!set->p) {
alloc_free(set->first);
return 0;
}
set->x = (char **)alloc(sizeof(char *) * set->a);
if (!set->x) {
alloc_free(set->p);
alloc_free(set->first);
return 0;
}
for (h = 0; h <= set->mask; ++h) set->first[h] = -1;
return 1;
}
char *strset_in(strset *set, char *s)
{
uint32 h;
strset_list *sl;
int i;
char *xi;
h = strset_hash(s);
i = set->first[h & set->mask];
while (i >= 0) {
sl = set->p + i;
if (sl->h == h) {
xi = set->x[i];
if (!str_diff(xi, s)) return xi;
}
i = sl->next;
}
return 0;
}
int strset_add(strset *set, char *s)
{
uint32 h;
int n;
strset_list *sl;
n = set->n;
if (n == set->a) {
int newa;
strset_list *newp;
char **newx;
newa = n + 10 + (n >> 3);
newp = (strset_list *)alloc(sizeof(strset_list) * newa);
if (!newp) return 0;
newx = (char **)alloc(sizeof(char *) * newa);
if (!newx) {
alloc_free(newp);
return 0;
}
byte_copy(newp, sizeof(strset_list) * n, set->p);
byte_copy(newx, sizeof(char *) * n, set->x);
alloc_free(set->p);
alloc_free(set->x);
set->p = newp;
set->x = newx;
set->a = newa;
if (n + n + n > set->mask) {
int newmask;
int *newfirst;
int i;
uint32 h;
newmask = set->mask + set->mask + 1;
newfirst = (int *)alloc(sizeof(int) * (newmask + 1));
if (!newfirst) return 0;
for (h = 0; h <= newmask; ++h) newfirst[h] = -1;
for (i = 0; i < n; ++i) {
sl = set->p + i;
h = sl->h & newmask;
sl->next = newfirst[h];
newfirst[h] = i;
}
alloc_free(set->first);
set->first = newfirst;
set->mask = newmask;
}
}
h = strset_hash(s);
sl = set->p + n;
sl->h = h;
h &= set->mask;
sl->next = set->first[h];
set->first[h] = n;
set->x[n] = s;
set->n = n + 1;
return 1;
}
|
