1 /* Littlewood-Richardson Calculator
2 * Copyright (C) 1999- Anders S. Buch (asbuch at math rutgers edu)
3 * See the file LICENSE for license information.
4 */
5
6 #include "set.h"
7 #include "vector.h"
8
9
s_new(cmp_t cmp,hash_t hsh)10 set *s_new(cmp_t cmp, hash_t hsh)
11 {
12 set *s = amalloc(sizeof(set));
13 s_cmp(s) = cmp;
14 s_hash(s) = hsh;
15
16 s_tabsz(s) = INIT_TABSZ;
17 s_table(s) = amalloc(INIT_TABSZ * sizeof(size_t));
18
19 s->elts_sz = INIT_ELTSZ;
20 s_elts(s) = amalloc(INIT_ELTSZ * sizeof(struct _element));
21
22 s_reset(s);
23
24 return s;
25 }
26
s_free(set * s)27 void s_free(set *s)
28 {
29 afree(s_table(s));
30 afree(s_elts(s));
31 afree(s);
32 }
33
s_reset(set * s)34 void s_reset(set *s)
35 {
36 size_t i;
37 s_card(s) = 0;
38 for (i = 0; i < s_tabsz(s); i++)
39 s_table(s)[i] = _S_END;
40 for (i = 0; i < s_eltsz(s); i++)
41 s->elts[i].next = i + 1;
42 s->elts[s_eltsz(s) - 1].next = _S_END;
43 s->free_elts = 0;
44 }
45
46
s_find(set * s,void * e,hashkey_t key)47 size_t s_find(set *s, void *e, hashkey_t key)
48 {
49 size_t index = key % s_tabsz(s);
50 size_t i = s->table[index];
51
52 cmp_t cmp = s_cmp(s);
53 struct _element *elts = s->elts;
54
55 while (i != _S_END && cmp(e, elts[i].data))
56 i = elts[i].next;
57
58 return i;
59 }
60
s_makeroom(set * s,size_t sz)61 void s_makeroom(set *s, size_t sz)
62 {
63 if (USE_FAC * sz > s_tabsz(s))
64 {
65 size_t *newtab;
66 size_t newsz;
67 size_t index, i, next;
68 struct _element *elts = s->elts;
69 size_t *oldtab = s->table;
70
71 newsz = 2 * USE_FAC * sz + 1;
72 if (newsz % 3 == 0)
73 newsz += 2;
74 if (newsz % 5 == 0)
75 newsz += 6;
76 if (newsz % 7 == 0)
77 newsz += 30;
78 newtab = amalloc(newsz * sizeof(size_t));
79
80 for (index = 0; index < newsz; index++)
81 newtab[index] = _S_END;
82
83 for (index = 0; index < s_tabsz(s); index++)
84 for (i = oldtab[index]; i != _S_END; i = next)
85 {
86 size_t ind = elts[i].key % newsz;
87 next = elts[i].next;
88 elts[i].next = newtab[ind];
89 newtab[ind] = i;
90 }
91
92 s->table = newtab;
93 s_tabsz(s) = newsz;
94 afree(oldtab);
95 }
96
97 if (sz > s_eltsz(s))
98 {
99 size_t newsz = 2 * sz;
100 size_t i;
101 struct _element *elts;
102 elts = s->elts = arealloc(s->elts, newsz * sizeof(struct _element));
103
104 for (i = s_eltsz(s); i < newsz; i++)
105 elts[i].next = i + 1;
106
107 elts[newsz - 1].next = s->free_elts;
108 s->free_elts = s_eltsz(s);
109
110 s_eltsz(s) = newsz;
111 }
112 }
113
s_insert(set * s,void * e)114 void * s_insert(set *s, void *e)
115 {
116 hashkey_t key = s_hash(s)(e);
117 size_t i = s_find(s, e, key);
118
119 if (i == _S_END)
120 {
121 size_t index;
122 struct _element *elts;
123
124 s_makeroom(s, s_card(s) + 1);
125
126 elts = s->elts;
127 index = key % s_tabsz(s);
128 i = s->free_elts;
129 s->free_elts = elts[i].next;
130
131 elts[i].data = e;
132 elts[i].key = key;
133
134 elts[i].next = s->table[index];
135 s->table[index] = i;
136
137 s_card(s)++;
138
139 return e;
140 }
141 else
142 {
143 return s->elts[i].data;
144 }
145 }
146
147
s_has(set * s,void * e)148 void * s_has(set *s, void *e)
149 {
150 hashkey_t key = s_hash(s)(e);
151 size_t i = s_find(s, e, key);
152
153 return (i == _S_END) ? NULL : s->elts[i].data;
154 }
155
156
s_remove(set * s,void * e)157 void * s_remove(set *s, void *e)
158 {
159 hashkey_t key = s_hash(s)(e);
160 size_t index = key % s_tabsz(s);
161 size_t i = s->table[index];
162 size_t prev = _S_END;
163
164 cmp_t cmp = s_cmp(s);
165 struct _element *elts = s->elts;
166
167 while (i != _S_END && cmp(e, elts[i].data))
168 {
169 prev = i;
170 i = elts[i].next;
171 }
172
173 if (i == _S_END)
174 return NULL;
175
176 if (prev == _S_END)
177 s->table[index] = elts[i].next;
178 else
179 elts[prev].next = elts[i].next;
180
181 elts[i].next = s->free_elts;
182 s->free_elts = i;
183
184 s_card(s)--;
185
186 return elts[i].data;
187 }
188
189
s_elemlist(set * s)190 list *s_elemlist(set *s)
191 {
192 list *lst = l_newsz(s_card(s));
193 struct _element *elts = s_elts(s);
194 size_t index;
195 size_t i;
196
197 for (index = 0; index < s_tabsz(s); index++)
198 for (i = s->table[index]; i != _S_END; i = elts[i].next)
199 l_append(lst, elts[i].data);
200
201 return lst;
202 }
203
204
_s_first(set * s,set_itr * itr)205 void *_s_first(set *s, set_itr *itr)
206 {
207 size_t index, i;
208
209 itr->s = s;
210
211 index = 0;
212 while (index < s_tabsz(s) && s->table[index] == _S_END)
213 index++;
214
215 if (index == s_tabsz(s))
216 return NULL;
217
218 i = s->table[index];
219 itr->index = index;
220 itr->i = i;
221 return s->elts[i].data;
222 }
223
_s_next(set_itr * itr)224 void *_s_next(set_itr *itr)
225 {
226 set *s = itr->s;
227 size_t index = itr->index;
228 size_t i;
229
230 index++;
231 while (index < s_tabsz(s) && s->table[index] == _S_END)
232 index++;
233
234 if (index == s_tabsz(s))
235 return NULL;
236
237 i = s->table[index];
238 itr->index = index;
239 itr->i = i;
240 return s->elts[i].data;
241 }
242
243
s_print_stat(set * s,size_t range)244 void s_print_stat(set *s, size_t range)
245 {
246 vector *stat = v_new_zero(range + 1);
247 size_t index, i;
248
249 for (index = 0; index < s_tabsz(s); index++)
250 {
251 int count = 0;
252 for (i = s->table[index]; i != _S_END; i = s->elts[i].next)
253 count++;
254 if (count > range)
255 count = range;
256 v_elem(stat, count)++;
257 }
258
259 puts("hash table distribution:");
260 v_printnl(stat);
261
262 v_free(stat);
263 }
264