1 static char rcsid[] = "$Id: tableint.c 182426 2016-01-15 22:06:05Z twu $";
2 #ifdef HAVE_CONFIG_H
3 #include <config.h>
4 #endif
5
6 #include "tableint.h"
7
8 #include <stdio.h>
9 #include <limits.h>
10 #include <stddef.h>
11 #include <stdlib.h> /* For qsort */
12 #include "mem.h"
13 #include "assert.h"
14
15 #define T Tableint_T
16 struct T {
17 int size;
18 int (*cmp)(const void *x, const void *y);
19 unsigned int (*hash)(const void *key);
20 int length;
21 unsigned int timestamp;
22 struct binding {
23 struct binding *link;
24 const void *key;
25 int value;
26 unsigned int timeindex;
27 } **buckets;
28 };
29
30
31 static int
cmpatom(const void * x,const void * y)32 cmpatom (const void *x, const void *y) {
33 return x != y;
34 }
35
36 static unsigned int
hashatom(const void * key)37 hashatom (const void *key) {
38 return (unsigned long)key>>2;
39 }
40
41 T
Tableint_new(int hint,int (* cmp)(const void * x,const void * y),unsigned int hash (const void * key))42 Tableint_new (int hint,
43 int (*cmp)(const void *x, const void *y),
44 unsigned int hash(const void *key)) {
45 T table;
46 int i;
47 static int primes[] = { 509, 509, 1021, 2053, 4093,
48 8191, 16381, 32771, 65521, INT_MAX };
49
50 assert(hint >= 0);
51 for (i = 1; primes[i] < hint; i++) {
52 }
53 table = (T) MALLOC(sizeof(*table) +
54 primes[i-1]*sizeof(table->buckets[0]));
55 table->size = primes[i-1];
56 table->cmp = cmp ? cmp : cmpatom;
57 table->hash = hash ? hash : hashatom;
58 table->buckets = (struct binding **)(table + 1);
59 for (i = 0; i < table->size; i++) {
60 table->buckets[i] = NULL;
61 }
62 table->length = 0;
63 table->timestamp = 0;
64 return table;
65 }
66
67 int
Tableint_get(T table,const void * key)68 Tableint_get (T table, const void *key) {
69 int i;
70 struct binding *p;
71
72 assert(table);
73 /* assert(key); -- Doesn't hold for atomic 0 */
74 i = (*table->hash)(key)%table->size;
75 /* printf("Doing Tableint_get on %s at bucket %d\n",(char *) key, i); */
76 for (p = table->buckets[i]; p; p = p->link) {
77 /* printf(" Comparing %s with %s at %p, key = %p\n",(char *) key, (char *) p->key, p, p->key); */
78 if ((*table->cmp)(key, p->key) == 0) {
79 break;
80 }
81 }
82 return p ? p->value : 0;
83 }
84
85 int
Tableint_put(T table,const void * key,int value)86 Tableint_put (T table, const void *key, int value) {
87 int i;
88 struct binding *p;
89 int prev;
90
91 assert(table);
92 /* assert(key); -- Doesn't hold for atomic 0 */
93 i = (*table->hash)(key)%table->size;
94 for (p = table->buckets[i]; p; p = p->link) {
95 if ((*table->cmp)(key, p->key) == 0) {
96 break;
97 }
98 }
99 if (p == NULL) {
100 NEW(p);
101 p->key = key;
102 /* printf("Doing Tableint_put at %p, key = %p\n",p,p->key); */
103 p->link = table->buckets[i];
104 table->buckets[i] = p;
105 table->length++;
106 prev = 0;
107 } else {
108 prev = p->value;
109 }
110 p->value = value;
111 p->timeindex = table->timestamp;
112 table->timestamp++;
113 return prev;
114 }
115
116 int
Tableint_length(T table)117 Tableint_length (T table) {
118 assert(table);
119 return table->length;
120 }
121
122 void
Tableint_map(T table,void (* apply)(const void * key,int * value,void * cl),void * cl)123 Tableint_map (T table,
124 void (*apply)(const void *key, int *value, void *cl),
125 void *cl) {
126 int i;
127 unsigned int stamp;
128 struct binding *p;
129
130 assert(table);
131 assert(apply);
132 stamp = table->timestamp;
133 for (i = 0; i < table->size; i++)
134 for (p = table->buckets[i]; p; p = p->link) {
135 apply(p->key, &p->value, cl);
136 assert(table->timestamp == stamp);
137 }
138 }
139
140 int
Tableint_remove(T table,const void * key)141 Tableint_remove (T table, const void *key) {
142 int i;
143 struct binding **pp;
144
145 assert(table);
146 /* assert(key); -- Doesn't hold for atomic 0 */
147 table->timestamp++;
148 i = (*table->hash)(key)%table->size;
149 for (pp = &table->buckets[i]; *pp; pp = &(*pp)->link) {
150 if ((*table->cmp)(key, (*pp)->key) == 0) {
151 struct binding *p = *pp;
152 int value = p->value;
153 *pp = p->link;
154 FREE(p);
155 table->length--;
156 return value;
157 }
158 }
159 return 0;
160 }
161
162 void **
Tableint_keys(T table,void * end)163 Tableint_keys (T table, void *end) {
164 void **keyarray;
165 int i, j = 0;
166 struct binding *p;
167
168 assert(table);
169 keyarray = (void **) CALLOC(table->length+1,sizeof(void *));
170 for (i = 0; i < table->size; i++) {
171 for (p = table->buckets[i]; p; p = p->link) {
172 keyarray[j++] = (void *) p->key;
173 }
174 }
175 keyarray[j] = end;
176 return keyarray;
177 }
178
179
180 static int
timeindex_cmp(const void * x,const void * y)181 timeindex_cmp (const void *x, const void *y) {
182 struct binding *a = * (struct binding **) x;
183 struct binding *b = * (struct binding **) y;
184
185 if (a->timeindex < b->timeindex) {
186 return -1;
187 } else if (a->timeindex > b->timeindex) {
188 return +1;
189 } else {
190 return 0;
191 }
192 }
193
194
195 void **
Tableint_keys_by_timeindex(T table,void * end)196 Tableint_keys_by_timeindex (T table, void *end) {
197 void **keyarray;
198 int i, j = 0;
199 struct binding **buckets, *p;
200
201 assert(table);
202 buckets = (struct binding **) CALLOC(table->length,sizeof(struct binding *));
203 for (i = 0; i < table->size; i++) {
204 for (p = table->buckets[i]; p; p = p->link) {
205 buckets[j++] = p;
206 }
207 }
208 qsort(buckets,table->length,sizeof(struct binding *),timeindex_cmp);
209
210 keyarray = (void **) CALLOC(table->length+1,sizeof(void *));
211 for (j = 0; j < table->length; j++) {
212 p = buckets[j];
213 keyarray[j] = (void *) p->key;
214 }
215 keyarray[j] = end;
216
217 FREE(buckets);
218 return keyarray;
219 }
220
221 int *
Tableint_values(T table,int end)222 Tableint_values (T table, int end) {
223 int *valuearray;
224 int i, j = 0;
225 struct binding *p;
226
227 assert(table);
228 valuearray = (int *) CALLOC(table->length+1,sizeof(int));
229 for (i = 0; i < table->size; i++) {
230 for (p = table->buckets[i]; p; p = p->link) {
231 valuearray[j++] = p->value;
232 }
233 }
234 valuearray[j] = end;
235 return valuearray;
236 }
237
238 void
Tableint_free(T * table)239 Tableint_free (T *table) {
240 assert(table && *table);
241 if ((*table)->length > 0) {
242 int i;
243 struct binding *p, *q;
244 for (i = 0; i < (*table)->size; i++) {
245 for (p = (*table)->buckets[i]; p; p = q) {
246 q = p->link;
247 FREE(p);
248 }
249 }
250 }
251 FREE(*table);
252 }
253