Commit | Line | Data |
---|---|---|
8d5530c4 MW |
1 | #include "strset.h" |
2 | #include "str.h" | |
3 | #include "byte.h" | |
4 | ||
5 | uint32 strset_hash(s) | |
6 | char *s; | |
7 | { | |
8 | unsigned char ch; | |
9 | uint32 h; | |
10 | h = 5381; | |
11 | while (ch = *s) | |
12 | { | |
13 | h = ((h << 5) + h) ^ ch; | |
14 | ++s; | |
15 | } | |
16 | return h; | |
17 | } | |
18 | ||
19 | int strset_init(set) | |
20 | strset *set; | |
21 | { | |
22 | int h; | |
23 | set->mask = 15; | |
24 | set->n = 0; | |
25 | set->a = 10; | |
26 | ||
27 | set->first = (int *) alloc(sizeof(int) * (set->mask + 1)); | |
28 | if (!set->first) return 0; | |
29 | set->p = (strset_list *) alloc(sizeof(strset_list) * set->a); | |
30 | if (!set->p) { alloc_free(set->first); return 0; } | |
31 | set->x = (char **) alloc(sizeof(char *) * set->a); | |
32 | if (!set->x) { alloc_free(set->p); alloc_free(set->first); return 0; } | |
33 | ||
34 | for (h = 0;h <= set->mask;++h) set->first[h] = -1; | |
35 | ||
36 | return 1; | |
37 | } | |
38 | ||
39 | char *strset_in(set,s) | |
40 | strset *set; | |
41 | char *s; | |
42 | { | |
43 | uint32 h; | |
44 | strset_list *sl; | |
45 | int i; | |
46 | char *xi; | |
47 | ||
48 | h = strset_hash(s); | |
49 | i = set->first[h & set->mask]; | |
50 | while (i >= 0) | |
51 | { | |
52 | sl = set->p + i; | |
53 | if (sl->h == h) | |
54 | { | |
55 | xi = set->x[i]; | |
56 | if (!str_diff(xi,s)) return xi; | |
57 | } | |
58 | i = sl->next; | |
59 | } | |
60 | return 0; | |
61 | } | |
62 | ||
63 | int strset_add(set,s) | |
64 | strset *set; | |
65 | char *s; | |
66 | { | |
67 | uint32 h; | |
68 | int n; | |
69 | strset_list *sl; | |
70 | ||
71 | n = set->n; | |
72 | ||
73 | if (n == set->a) | |
74 | { | |
75 | int newa; | |
76 | strset_list *newp; | |
77 | char **newx; | |
78 | ||
79 | newa = n + 10 + (n >> 3); | |
80 | newp = (strset_list *) alloc(sizeof(strset_list) * newa); | |
81 | if (!newp) return 0; | |
82 | newx = (char **) alloc(sizeof(char *) * newa); | |
83 | if (!newx) { alloc_free(newp); return 0; } | |
84 | ||
85 | byte_copy(newp,sizeof(strset_list) * n,set->p); | |
86 | byte_copy(newx,sizeof(char *) * n,set->x); | |
87 | alloc_free(set->p); | |
88 | alloc_free(set->x); | |
89 | set->p = newp; | |
90 | set->x = newx; | |
91 | set->a = newa; | |
92 | ||
93 | if (n + n + n > set->mask) | |
94 | { | |
95 | int newmask; | |
96 | int *newfirst; | |
97 | int i; | |
98 | uint32 h; | |
99 | ||
100 | newmask = set->mask + set->mask + 1; | |
101 | newfirst = (int *) alloc(sizeof(int) * (newmask + 1)); | |
102 | if (!newfirst) return 0; | |
103 | ||
104 | for (h = 0;h <= newmask;++h) newfirst[h] = -1; | |
105 | ||
106 | for (i = 0;i < n;++i) | |
107 | { | |
108 | sl = set->p + i; | |
109 | h = sl->h & newmask; | |
110 | sl->next = newfirst[h]; | |
111 | newfirst[h] = i; | |
112 | } | |
113 | ||
114 | alloc_free(set->first); | |
115 | set->first = newfirst; | |
116 | set->mask = newmask; | |
117 | } | |
118 | } | |
119 | ||
120 | h = strset_hash(s); | |
121 | ||
122 | sl = set->p + n; | |
123 | sl->h = h; | |
124 | h &= set->mask; | |
125 | sl->next = set->first[h]; | |
126 | set->first[h] = n; | |
127 | set->x[n] = s; | |
128 | set->n = n + 1; | |
129 | return 1; | |
130 | } |