1 /*
2 csound_data_structures.c:
3
4 Copyright (C) 2013 Steven Yi
5
6 This file is part of Csound.
7
8 The Csound Library is free software; you can redistribute it
9 and/or modify it under the terms of the GNU Lesser General Public
10 License as published by the Free Software Foundation; either
11 version 2.1 of the License, or (at your option) any later version.
12
13 Csound is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU Lesser General Public License for more details.
17
18 You should have received a copy of the GNU Lesser General Public
19 License along with Csound; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
21 02110-1301 USA
22 */
23 #include "csoundCore.h"
24 #include "csound_data_structures.h"
25
26 #define HASH_LOAD_FACTOR 0.75
27
28 char* cs_hash_table_put_no_key_copy(CSOUND* csound,
29 CS_HASH_TABLE* hashTable,
30 char* key, void* value);
31
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35
36 /* FUNCTIONS FOR CONS_CELL */
37
cs_cons(CSOUND * csound,void * val,CONS_CELL * cons)38 PUBLIC CONS_CELL* cs_cons(CSOUND* csound, void* val, CONS_CELL* cons) {
39 CONS_CELL* cell = csound->Malloc(csound, sizeof(CONS_CELL));
40 cell->value = val;
41 cell->next = cons;
42
43 return cell;
44 }
45
cs_cons_append(CONS_CELL * cons1,CONS_CELL * cons2)46 PUBLIC CONS_CELL* cs_cons_append(CONS_CELL* cons1, CONS_CELL* cons2) {
47 if (cons1 == NULL) return cons2;
48 if (cons2 == NULL) return cons1;
49
50 CONS_CELL* c = cons1;
51
52 while (c->next != NULL) c = c->next;
53
54 c->next = cons2;
55
56 return cons1;
57 }
58
cs_cons_length(CONS_CELL * head)59 PUBLIC int cs_cons_length(CONS_CELL* head) {
60 CONS_CELL* current = head;
61 int count = 0;
62 while (current != NULL) {
63 count++;
64 current = current->next;
65 }
66 return count;
67 }
68
cs_cons_free(CSOUND * csound,CONS_CELL * head)69 PUBLIC void cs_cons_free(CSOUND* csound, CONS_CELL* head) {
70 CONS_CELL *current, *next;
71
72 if (head == NULL) return;
73
74 current = head;
75
76 while (current != NULL) {
77 next = current->next;
78 csound->Free(csound, current);
79 current = next;
80 }
81 }
82
83
cs_cons_free_complete(CSOUND * csound,CONS_CELL * head)84 PUBLIC void cs_cons_free_complete(CSOUND* csound, CONS_CELL* head) {
85
86 CONS_CELL *current, *next;
87
88 if (head == NULL) return;
89
90 current = head;
91
92 while (current != NULL) {
93 next = current->next;
94 csound->Free(csound, current->value);
95 csound->Free(csound, current);
96 current = next;
97 }
98 }
99
100 /* FUNCTION FOR HASH SET */
101
cs_hash_table_create(CSOUND * csound)102 PUBLIC CS_HASH_TABLE* cs_hash_table_create(CSOUND* csound) {
103 CS_HASH_TABLE* table =
104 (CS_HASH_TABLE*) csound->Calloc(csound, sizeof(CS_HASH_TABLE));
105 table->count = 0;
106 table->table_size = 8192;
107 table->buckets = csound->Calloc(csound, sizeof(CS_HASH_TABLE_ITEM*) * 8192);
108
109 return table;
110 }
111
cs_hash_table_check_resize(CSOUND * csound,CS_HASH_TABLE * table)112 static int cs_hash_table_check_resize(CSOUND* csound, CS_HASH_TABLE* table) {
113 if (table->count + 1 > table->table_size * HASH_LOAD_FACTOR) {
114 int oldSize = table->table_size;
115 int newSize = oldSize * 2;
116 CS_HASH_TABLE_ITEM** oldTable = table->buckets;
117 CS_HASH_TABLE_ITEM** newTable =
118 csound->Calloc(csound, newSize * sizeof(CS_HASH_TABLE_ITEM*));
119
120 table->buckets = newTable;
121 table->table_size = newSize;
122
123 for (int i = 0; i < oldSize; i++) {
124 CS_HASH_TABLE_ITEM* item = oldTable[i];
125 while (item != NULL) {
126 cs_hash_table_put_no_key_copy(csound, table, item->key,
127 item->value);
128 item->key = NULL;
129 CS_HASH_TABLE_ITEM* next = item->next;
130 csound->Free(csound, item);
131 item = next;
132 }
133 }
134 return 1;
135 }
136 return 0;
137 }
138
cs_name_hash(CS_HASH_TABLE * table,char * s)139 static unsigned int cs_name_hash(CS_HASH_TABLE* table, char *s)
140 {
141 unsigned int h = 0;
142 while (*s != '\0') {
143 h = (h<<4) ^ *s++;
144 }
145 return (h % table->table_size);
146 }
147
cs_hash_table_get(CSOUND * csound,CS_HASH_TABLE * hashTable,char * key)148 PUBLIC void* cs_hash_table_get(CSOUND* csound,
149 CS_HASH_TABLE* hashTable, char* key) {
150 IGN(csound);
151 unsigned int index;
152 CS_HASH_TABLE_ITEM* item;
153
154 if (key == NULL) {
155 return NULL;
156 }
157
158 index = cs_name_hash(hashTable, key);
159 item = hashTable->buckets[index];
160 while (item != NULL) {
161 if (strcmp(key, item->key) == 0) {
162 return item->value;
163 }
164 item = item->next;
165 }
166
167 return NULL;
168 }
169
cs_hash_table_get_key(CSOUND * csound,CS_HASH_TABLE * hashTable,char * key)170 PUBLIC char* cs_hash_table_get_key(CSOUND* csound,
171 CS_HASH_TABLE* hashTable, char* key) {
172 unsigned int index;
173 CS_HASH_TABLE_ITEM* item;
174 IGN(csound);
175
176 if (key == NULL) {
177 return NULL;
178 }
179
180 index = cs_name_hash(hashTable, key);
181 item = hashTable->buckets[index];
182
183 while (item != NULL) {
184 if (strcmp(key, item->key) == 0) {
185 return item->key;
186 }
187 item = item->next;
188 }
189
190 return NULL;
191 }
192
193 /*
194 * If item exists, replace.
195 * Else, check for resize, then do insert.
196 */
cs_hash_table_put_no_key_copy(CSOUND * csound,CS_HASH_TABLE * hashTable,char * key,void * value)197 char* cs_hash_table_put_no_key_copy(CSOUND* csound,
198 CS_HASH_TABLE* hashTable,
199 char* key, void* value) {
200 if (key == NULL) {
201 return NULL;
202 }
203
204 unsigned int index = cs_name_hash(hashTable, key);
205
206 CS_HASH_TABLE_ITEM* item = hashTable->buckets[index];
207
208 while (item != NULL) {
209 if (strcmp(key, item->key) == 0) {
210 item->value = value;
211 return item->key;
212 }
213 item = item->next;
214 }
215
216 int modified = cs_hash_table_check_resize(csound, hashTable);
217
218 if (modified) {
219 index = cs_name_hash(hashTable, key);
220 }
221 CS_HASH_TABLE_ITEM* newItem = csound->Malloc(csound,
222 sizeof(CS_HASH_TABLE_ITEM));
223 newItem->key = key;
224 newItem->value = value;
225 newItem->next = NULL;
226
227 item = hashTable->buckets[index];
228 hashTable->count++;
229
230 if (item) {
231 while (item->next != NULL) {
232 item = item->next;
233 }
234
235 item->next = newItem;
236 } else {
237 hashTable->buckets[index] = newItem;
238 }
239
240 return key;
241 }
242
cs_hash_table_put(CSOUND * csound,CS_HASH_TABLE * hashTable,char * key,void * value)243 PUBLIC void cs_hash_table_put(CSOUND* csound,
244 CS_HASH_TABLE* hashTable, char* key, void* value) {
245 cs_hash_table_put_no_key_copy(csound, hashTable,
246 cs_strdup(csound, key), value);
247 }
248
cs_hash_table_put_key(CSOUND * csound,CS_HASH_TABLE * hashTable,char * key)249 PUBLIC char* cs_hash_table_put_key(CSOUND* csound,
250 CS_HASH_TABLE* hashTable, char* key) {
251 return cs_hash_table_put_no_key_copy(csound, hashTable,
252 cs_strdup(csound, key), NULL);
253 }
254
cs_hash_table_remove(CSOUND * csound,CS_HASH_TABLE * hashTable,char * key)255 PUBLIC void cs_hash_table_remove(CSOUND* csound,
256 CS_HASH_TABLE* hashTable, char* key) {
257 CS_HASH_TABLE_ITEM *previous, *item;
258 unsigned int index;
259
260 if (key == NULL) {
261 return;
262 }
263
264 index = cs_name_hash(hashTable, key);
265
266 previous = NULL;
267 item = hashTable->buckets[index];
268
269 while (item != NULL) {
270 if (strcmp(key, item->key) == 0) {
271 if (previous == NULL) {
272 hashTable->buckets[index] = item->next;
273 } else {
274 previous->next = item->next;
275 }
276 csound->Free(csound, item);
277 hashTable->count--;
278 return;
279 }
280 previous = item;
281 item = item->next;
282 }
283 }
284
cs_hash_table_keys(CSOUND * csound,CS_HASH_TABLE * hashTable)285 PUBLIC CONS_CELL* cs_hash_table_keys(CSOUND* csound, CS_HASH_TABLE* hashTable) {
286 CONS_CELL* head = NULL;
287
288 int i = 0;
289
290 for (i = 0; i < hashTable->table_size; i++) {
291 CS_HASH_TABLE_ITEM* item = hashTable->buckets[i];
292
293 while (item != NULL) {
294 head = cs_cons(csound, item->key, head);
295 item = item->next;
296 }
297 }
298 return head;
299 }
300
cs_hash_table_values(CSOUND * csound,CS_HASH_TABLE * hashTable)301 PUBLIC CONS_CELL* cs_hash_table_values(CSOUND* csound, CS_HASH_TABLE* hashTable) {
302 CONS_CELL* head = NULL;
303
304 int i = 0;
305
306 for (i = 0; i < hashTable->table_size; i++) {
307 CS_HASH_TABLE_ITEM* item = hashTable->buckets[i];
308
309 while (item != NULL) {
310 head = cs_cons(csound, item->value, head);
311 item = item->next;
312 }
313 }
314 return head;
315 }
316
cs_hash_table_merge(CSOUND * csound,CS_HASH_TABLE * target,CS_HASH_TABLE * source)317 PUBLIC void cs_hash_table_merge(CSOUND* csound,
318 CS_HASH_TABLE* target, CS_HASH_TABLE* source) {
319 // TODO - check if this is the best strategy for merging
320 int i = 0;
321
322 for (i = 0; i < source->table_size; i++) {
323 CS_HASH_TABLE_ITEM* item = source->buckets[i];
324
325 while (item != NULL) {
326 CS_HASH_TABLE_ITEM* next = item->next;
327 char* new_key =
328 cs_hash_table_put_no_key_copy(csound, target, item->key, item->value);
329
330 if (new_key != item->key) {
331 csound->Free(csound, item->key);
332 }
333
334 csound->Free(csound, item);
335 item = next;
336 }
337 source->buckets[i] = NULL;
338 }
339
340 }
341
cs_hash_table_free(CSOUND * csound,CS_HASH_TABLE * hashTable)342 PUBLIC void cs_hash_table_free(CSOUND* csound, CS_HASH_TABLE* hashTable) {
343 int i;
344
345 for (i = 0; i < hashTable->table_size; i++) {
346 CS_HASH_TABLE_ITEM* item = hashTable->buckets[i];
347
348 while(item != NULL) {
349 CS_HASH_TABLE_ITEM* next = item->next;
350 csound->Free(csound, item->key);
351 csound->Free(csound, item);
352 item = next;
353 }
354 }
355 csound->Free(csound, hashTable);
356 }
357
cs_hash_table_mfree_complete(CSOUND * csound,CS_HASH_TABLE * hashTable)358 PUBLIC void cs_hash_table_mfree_complete(CSOUND* csound, CS_HASH_TABLE* hashTable) {
359
360 int i;
361
362 for (i = 0; i < hashTable->table_size; i++) {
363 CS_HASH_TABLE_ITEM* item = hashTable->buckets[i];
364
365 while(item != NULL) {
366 CS_HASH_TABLE_ITEM* next = item->next;
367 csound->Free(csound, item->key);
368 csound->Free(csound, item->value);
369 csound->Free(csound, item);
370 item = next;
371 }
372 }
373 csound->Free(csound, hashTable);
374 }
375
cs_hash_table_free_complete(CSOUND * csound,CS_HASH_TABLE * hashTable)376 PUBLIC void cs_hash_table_free_complete(CSOUND* csound, CS_HASH_TABLE* hashTable) {
377
378 int i;
379
380 for (i = 0; i < hashTable->table_size; i++) {
381 CS_HASH_TABLE_ITEM* item = hashTable->buckets[i];
382
383 while(item != NULL) {
384 CS_HASH_TABLE_ITEM* next = item->next;
385 csound->Free(csound, item->key);
386
387 /* NOTE: This needs to be free, not csound->Free.
388 To use mfree on keys, use cs_hash_table_mfree_complete
389 TODO: Check if this is even necessary anymore... */
390 free(item->value);
391 csound->Free(csound, item);
392 item = next;
393 }
394 }
395 csound->Free(csound, hashTable);
396 }
397
cs_inverse_hash_get(CSOUND * csound,CS_HASH_TABLE * hashTable,int n)398 char *cs_inverse_hash_get(CSOUND* csound, CS_HASH_TABLE* hashTable, int n)
399 {
400 int k;
401 IGN(csound);
402 for (k=0; k<hashTable->table_size;k++) {
403 CS_HASH_TABLE_ITEM* item = hashTable->buckets[k];
404 while (item) {
405 if (n==*(int*)item->value) return item->key;
406 item = item->next;
407 }
408 }
409 return "";
410 }
411
412
413
414
415 #ifdef __cplusplus
416 extern "C" {
417 #endif
418