1 /*
2 cs_par_base.c:
3
4 Copyright (C) 2009: Chris Wilson and John ffitch
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
24 #include <stdio.h>
25 #include <stdlib.h>
26
27 #include "csoundCore.h"
28
29 #include "cs_par_base.h"
30 static int csp_set_exists(struct set_t *set, void *data);
31
csp_thread_index_get(CSOUND * csound)32 int csp_thread_index_get(CSOUND *csound)
33 {
34 void *threadId = csound->GetCurrentThreadID();
35
36 int index = 0;
37 THREADINFO *current = csound->multiThreadedThreadInfo;
38
39 if (UNLIKELY(current == NULL)) {
40 return -1;
41 }
42
43 while (current != NULL) {
44 // PTHREAD: this should be a class in threads.c to abstract this away
45 #if defined(HAVE_PTHREAD) && !defined(WIN32)
46 if (pthread_equal(*(pthread_t *)threadId, *(pthread_t *)current->threadId)) {
47 #else
48 // FIXME not entirely sure what this should be...
49 //if ((DWORD)csoundGetCurrentThreadId () == (DWORD)threadId)
50 /*if ((DWORD)current->threadId == (DWORD)threadId) {*/
51 if (current->threadId == threadId) {
52 #endif
53 free(threadId);
54 return index;
55 }
56 index++;
57 current = current->next;
58 }
59 return -1;
60 }
61
62
63 /* **** An implementation of Barriers for MAC that lacks them **** */
64 #if defined(__MACH__) || defined(ANDROID) || defined(NACL) || defined(__HAIKU__)
65 /*#define BARRIER_SERIAL_THREAD (-1)
66
67 typedef struct {
68 pthread_mutex_t mut;
69 pthread_cond_t cond;
70 unsigned int count, max, iteration;
71 } barrier_t;
72 */
73 extern int barrier_init(barrier_t *b, void *,unsigned int max);
74 extern int barrier_destroy(barrier_t *b);
75 extern int barrier_wait(barrier_t *b);
76
77 #ifndef PTHREAD_BARRIER_SERIAL_THREAD
78 /*#define pthread_barrier_t barrier_t */
79 #define PTHREAD_BARRIER_SERIAL_THREAD BARRIER_SERIAL_THREAD
80 #define pthread_barrier_init(barrier, attr, count) \
81 barrier_init(barrier,NULL,count)
82 #define pthread_barrier_destroy barrier_destroy
83 #define pthread_barrier_wait barrier_wait
84 #endif
85
86 int barrier_init(barrier_t *b, void *dump, unsigned int max)
87 {
88 IGN(dump);
89 if (UNLIKELY(max == 0)) return EINVAL;
90
91 if (UNLIKELY(pthread_mutex_init(&b->mut, NULL))) {
92 return -1;
93 }
94
95 if (UNLIKELY(pthread_cond_init(&b->cond, NULL))) {
96 int err = errno;
97 pthread_mutex_destroy(&b->mut);
98 errno = err;
99 return -1;
100 }
101
102 b->count = 0;
103 b->iteration = 0;
104 b->max = max;
105
106 return 0;
107 }
108
109 int barrier_destroy(barrier_t *b)
110 {
111 if (UNLIKELY(b->count > 0)) return EBUSY;
112
113 pthread_cond_destroy(&b->cond);
114 pthread_mutex_destroy(&b->mut);
115
116 return 0;
117 }
118
119 /* when barrier is passed, all threads except one return 0 */
120 int barrier_wait(barrier_t *b)
121 {
122 int ret;
123 unsigned int it;
124
125 pthread_mutex_lock(&b->mut);
126 b->count++;
127 it = b->iteration;
128 if (b->count >= b->max) {
129 b->count = 0;
130 b->iteration++;
131 pthread_cond_broadcast(&b->cond);
132 ret = BARRIER_SERIAL_THREAD;
133 }
134 else {
135 while (it == b->iteration) pthread_cond_wait(&b->cond, &b->mut);
136 ret = 0;
137 }
138 pthread_mutex_unlock(&b->mut);
139
140 return ret;
141 }
142 #endif
143
144 /***********************************************************************
145 * parallel primitives
146 */
147 void csp_barrier_alloc(CSOUND *csound, void **barrier,
148 int thread_count)
149 {
150 if (UNLIKELY(barrier == NULL))
151 csound->Die(csound, Str("Invalid NULL Parameter barrier"));
152 if (UNLIKELY(thread_count < 1))
153 csound->Die(csound, Str("Invalid Parameter thread_count must be > 0"));
154
155 *barrier = csound->CreateBarrier(thread_count);
156 if (UNLIKELY(*barrier == NULL)) {
157 csound->Die(csound, Str("Failed to allocate barrier"));
158 }
159 }
160
161 void csp_barrier_dealloc(CSOUND *csound, void **barrier)
162 {
163 if (UNLIKELY(barrier == NULL || *barrier == NULL))
164 csound->Die(csound, Str("Invalid NULL Parameter barrier"));
165
166 csound->DestroyBarrier(*barrier);
167 }
168
169
170
171 /***********************************************************************
172 * set data structure
173 */
174
175 /* static prototypes */
176 static void set_element_delloc(CSOUND *csound,
177 struct set_element_t **set_element);
178 static struct set_element_t *set_element_alloc(CSOUND *csound,
179 char *data);
180 static int set_is_set(struct set_t *set);
181 #if 0
182 static int
183 set_element_is_set_element(CSOUND *csound,
184 struct set_element_t *set_element);
185 #endif
186 struct set_t *csp_set_alloc(CSOUND *csound,
187 set_element_data_eq *ele_eq_func,
188 set_element_data_print *ele_print_func)
189 {
190 struct set_t *p = csound->Malloc(csound, sizeof(struct set_t));
191 if (UNLIKELY(p == NULL)) {
192 csound->Die(csound, Str("Failed to allocate set"));
193 }
194 memset(p, 0, sizeof(struct set_t));
195 memcpy(p->hdr, SET_HDR, HDR_LEN);
196 p->ele_eq_func = ele_eq_func;
197 p->ele_print_func = ele_print_func;
198 p->cache = NULL;
199 //printf("csp_set_alloc: %p\n", p);
200 return p;
201 }
202
203 void csp_set_dealloc(CSOUND *csound, struct set_t **set)
204 {
205 struct set_element_t *ele;
206 struct set_t *p = *set;
207 if (UNLIKELY(set == NULL || *set == NULL))
208 csound->Die(csound, Str("Invalid NULL Parameter set"));
209 if (UNLIKELY(!set_is_set(*set)))
210 csound->Die(csound, Str("Invalid Parameter set not a set"));
211
212 if (p->cache != NULL) csound->Free(csound, p->cache);
213
214 ele = p->head;
215 while (ele != NULL) {
216 struct set_element_t *next = ele->next;
217 set_element_delloc(csound, &ele);
218 ele = next;
219 }
220 //printf("csp_set_dealloc: %p\n", p);
221 csound->Free(csound, p);
222 *set = NULL;
223
224 return;
225 }
226
227 static struct set_element_t* set_element_alloc(CSOUND *csound,
228 char *data)
229 {
230 struct set_element_t *p;
231 if (data == NULL)
232 csound->Die(csound, Str("Invalid NULL Parameter data"));
233
234 p = (struct set_element_t*)csound->Malloc(csound, sizeof(struct set_element_t));
235 if (UNLIKELY(p == NULL)) {
236 csound->Die(csound, Str("Failed to allocate set element"));
237 }
238 memset(p, 0, sizeof(struct set_element_t));
239 memcpy(p->hdr, SET_ELEMENT_HDR, HDR_LEN);
240 p->data = cs_strdup(csound, data);
241
242 return p;
243 }
244
245 static void set_element_delloc(CSOUND *csound,
246 struct set_element_t **set_element)
247 {
248 if (UNLIKELY(set_element == NULL || *set_element == NULL))
249 csound->Die(csound, Str("Invalid NULL Parameter set_element"));
250 csound->Free(csound, *set_element);
251 *set_element = NULL;
252
253 return;
254 }
255
256 static int set_is_set(struct set_t *set)
257 {
258 char buf[4];
259 if (set == NULL) return 0;
260 memcpy(buf, (char *)set, HDR_LEN);
261 buf[3] = 0;
262 return strcmp(buf, SET_HDR) == 0;
263 }
264
265 #if 0
266 static int
267 set_element_is_set_element(CSOUND *csound,
268 struct set_element_t *set_element)
269 {
270 char buf[4];
271 if (set_element == NULL) return 0;
272 memcpy(buf, (char *)set_element, HDR_LEN-1);
273 buf[3] = 0;
274 return strcmp(buf, SET_ELEMENT_HDR) == 0;
275 }
276 #endif
277
278 struct set_t *csp_set_alloc_string(CSOUND *csound)
279 {
280 return csp_set_alloc(csound,
281 csp_set_element_string_eq,
282 csp_set_element_string_print);
283 }
284
285 int csp_set_element_string_eq(struct set_element_t *ele1,
286 struct set_element_t *ele2)
287 {
288 return strcmp((char *)ele1->data, (char *)ele2->data) == 0;
289 }
290
291 #if 0
292 int csp_set_element_ptr_eq(struct set_element_t *ele1,
293 struct set_element_t *ele2)
294 {
295 return (ele1->data == ele2->data);
296 }
297 #endif
298
299 void csp_set_element_string_print(CSOUND *csound,
300 struct set_element_t *ele)
301 {
302 csound->Message(csound, "%s", (char *)ele->data);
303 }
304
305 void csp_set_element_ptr_print(CSOUND *csound,
306 struct set_element_t *ele)
307 {
308 csound->Message(csound, "%p", ele->data);
309 }
310
311 static void set_update_cache(CSOUND *csound, struct set_t *set)
312 {
313 if (set->cache != NULL) {
314 csound->Free(csound, set->cache);
315 set->cache = NULL;
316 }
317 if (set->count > 0) {
318 struct set_element_t *ele;
319 int ctr = 0;
320 set->cache =
321 csound->Malloc(csound,
322 sizeof(struct set_element_t *) * set->count);
323 ele = set->head;
324 while (ele != NULL) {
325 set->cache[ctr] = ele;
326 ctr++;
327 ele = ele->next;
328 }
329 }
330 return;
331 }
332
333 /*
334 * if out_set_element is not NULL and the element corresponding to
335 * data is not found it will not be changed
336 */
337 static void set_element_get(struct set_t *set,
338 char *data,
339 struct set_element_t **out_set_element)
340 {
341 struct set_element_t *ele = set->head;
342 struct set_element_t data_ele = { SET_ELEMENT_HDR, data, 0 };
343 while (ele != NULL) {
344 if (set->ele_eq_func(ele, &data_ele)) {
345 *out_set_element = ele;
346 break;
347 }
348 ele = ele->next;
349 }
350 return;
351 }
352
353 void csp_set_add(CSOUND *csound, struct set_t *set, void *data)
354 {
355 struct set_element_t *ele = NULL;
356 #ifdef SET_DEBUG
357 if (UNLIKELY(set == NULL))
358 csound->Die(csound, "Invalid NULL Parameter set");
359 if (UNLIKELY(data == NULL))
360 csound->Die(csound, "Invalid NULL Parameter data");
361 #endif
362
363 if (csp_set_exists(set, data)) {
364 return;
365 }
366
367 ele = set_element_alloc(csound, data);
368 if (set->head == NULL) {
369 set->head = ele;
370 set->tail = ele;
371 }
372 else {
373 set->tail->next = ele;
374 set->tail = ele;
375 }
376 set->count++;
377
378 set_update_cache(csound, set);
379
380 return;
381 }
382
383 void csp_set_remove(CSOUND *csound, struct set_t *set, void *data)
384 {
385 #ifdef SET_DEBUG
386 if (UNLIKELY(set == NULL))
387 csound->Die(csound, "Invalid NULL Parameter set");
388 if (UNLIKELY(data == NULL))
389 csound->Die(csound, "Invalid NULL Parameter data");
390 #endif
391 {
392 struct set_element_t *ele = set->head, *prev = NULL;
393 struct set_element_t data_ele = { SET_ELEMENT_HDR, data, 0 };
394 while (ele != NULL) {
395 if (set->ele_eq_func(ele, &data_ele)) {
396 if (ele == set->head && ele == set->tail) {
397 set->head = NULL;
398 set->tail = NULL;
399 }
400 else if (ele == set->head) {
401 set->head = ele->next;
402 }
403 else {
404 prev->next = ele->next;
405 }
406 set_element_delloc(csound, &ele);
407 set->count--;
408 break;
409 }
410 prev = ele;
411 ele = ele->next;
412 }
413 }
414 set_update_cache(csound, set);
415
416 return;
417 }
418
419 static int csp_set_exists(struct set_t *set, void *data)
420 {
421 struct set_element_t *ele = NULL;
422 /* #ifdef SET_DEBUG */
423 /* if (UNLIKELY(set == NULL)) */
424 /* csound->Die(csound, "Invalid NULL Parameter set"); */
425 /* if (UNLIKELY(data == NULL)) */
426 /* csound->Die(csound, "Invalid NULL Parameter data"); */
427 /* #endif */
428 set_element_get(set, data, &ele);
429
430 return (ele == NULL ? 0 : 1);
431 }
432
433 void csp_set_print(CSOUND *csound, struct set_t *set)
434 {
435 struct set_element_t *ele;
436 #ifdef SET_DEBUG
437 if (UNLIKELY(set == NULL))
438 csound->Die(csound, "Invalid NULL Parameter set");
439 if (UNLIKELY(!set_is_set(set)))
440 csound->Die(csound, "Invalid Parameter set not a set");
441 #endif
442
443 ele = set->head;
444
445 csound->Message(csound, "{ ");
446 while (ele != NULL) {
447 set->ele_print_func(csound, ele);
448 if (ele->next != NULL) csound->Message(csound, ", ");
449 ele = ele->next;
450 }
451 csound->Message(csound, " }\n");
452
453 return;
454 }
455
456 inline int csp_set_count(struct set_t *set)
457 {
458 /* #ifdef SET_DEBUG */
459 /* if (UNLIKELY(set == NULL)) */
460 /* csound->Die(csound, "Invalid NULL Parameter set"); */
461 /* if (UNLIKELY(!set_is_set(set))) */
462 /* csound->Die(csound, "Invalid Parameter set not a set"); */
463 /* #endif */
464
465 return set->count;
466 }
467
468 /* 0 indexed */
469 // FIXME inlining breaks linkage for MSVC
470 inline static void* csp_set_get_num(struct set_t *set, int num)
471 {
472 /* #ifdef SET_DEBUG */
473 /* if (UNLIKELY(set == NULL)) */
474 /* csound->Die(csound, "Invalid NULL Parameter set"); */
475 /* if (UNLIKELY(!set_is_set(set))) */
476 /* csound->Die(csound, "Invalid Parameter set not a set"); */
477 /* if (UNLIKELY(um >= set->count)) */
478 /* csound->Die(csound, "Invalid Parameter num is out of bounds"); */
479 /* if (UNLIKELY(data == NULL)) */
480 /* csound->Die(csound, "Invalid NULL Parameter data"); */
481 /* #endif */
482
483 return set->cache[num]->data;
484
485 /* if (set->cache != NULL) { */
486
487 /* } */
488 /* else { */
489 /* int ctr = 0; */
490 /* struct set_element_t *ele = set->head; */
491 /* while (ctr < num && ele != NULL) { */
492 /* ctr++; */
493 /* ele = ele->next; */
494 /* } */
495 /* if (ctr == num && ele != NULL) { */
496 /* *data = ele->data; */
497 /* } */
498 /* } */
499
500 }
501
502 struct set_t *csp_set_union(CSOUND *csound, struct set_t *first,
503 struct set_t *second)
504 {
505 int ctr = 0;
506 int first_len;
507 int second_len;
508 struct set_t *result;
509 #ifdef SET_DEBUG
510 if (UNLIKELY(first == NULL))
511 csound->Die(csound, "Invalid NULL Parameter first");
512 if (UNLIKELY(!set_is_set(first)))
513 csound->Die(csound, "Invalid Parameter set not a first");
514 if (UNLIKELY(second == NULL))
515 csound->Die(csound, "Invalid NULL Parameter second");
516 if (UNLIKELY(!set_is_set(second)))
517 csound->Die(csound, "Invalid Parameter set not a second");
518 if (UNLIKELY(result == NULL))
519 csound->Die(csound, "Invalid NULL Parameter result");
520 if (UNLIKELY(first->ele_eq_func != second->ele_eq_func))
521 csound->Die(csound,
522 "Invalid sets for comparison (different equality)");
523 #endif
524
525 result = csp_set_alloc(csound,
526 first->ele_eq_func, first->ele_print_func);
527
528 first_len = csp_set_count(first);
529 second_len = csp_set_count(second);
530
531 while (ctr < first_len) {
532 void *data = NULL;
533 data = csp_set_get_num(first, ctr);
534 csp_set_add(csound, result, data);
535 ctr++;
536 }
537
538 ctr = 0;
539 while (ctr < second_len) {
540 void *data = NULL;
541 data = csp_set_get_num(second, ctr);
542 csp_set_add(csound, result, data);
543 ctr++;
544 }
545 return result;
546 }
547
548 struct set_t *csp_set_intersection(CSOUND *csound, struct set_t *first,
549 struct set_t *second)
550 {
551 int ctr = 0;
552 int first_len;
553 struct set_t *result;
554 #ifdef SET_DEBUG
555 if (UNLIKELY(first == NULL))
556 csound->Die(csound, "Invalid NULL Parameter first");
557 if (UNLIKELY(!set_is_set(first)))
558 csound->Die(csound, "Invalid Parameter set not a first");
559 if (UNLIKELY(second == NULL))
560 csound->Die(csound, "Invalid NULL Parameter second");
561 if (UNLIKELY(!set_is_set(second)))
562 csound->Die(csound, "Invalid Parameter set not a second");
563 if (UNLIKELY(result == NULL))
564 csound->Die(csound, "Invalid NULL Parameter result");
565 if (UNLIKELY(first->ele_eq_func != second->ele_eq_func))
566 csound->Die(csound,
567 "Invalid sets for comparison (different equality)");
568 #endif
569
570 result = csp_set_alloc(csound,
571 first->ele_eq_func, first->ele_print_func);
572
573 first_len = csp_set_count(first);
574
575 while (ctr < first_len) {
576 void *data = NULL;
577 data = csp_set_get_num(first, ctr);
578 if (csp_set_exists(second, data)) {
579 csp_set_add(csound, result, data);
580 }
581 ctr++;
582 }
583
584 return result;
585 }
586