Mercurial > hg > Gears > GearsAgda

annotate src/parallel_execution/SynchronizedQueue.cbc @ 386:89a9e9c14498

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add comment to createOneDimiterateTask
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Wed, 26 Jul 2017 18:57:19 +0900
parents a2c01ab30ea2
children 0c024ea61601
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
280
2c2e4e597eb0 generate no compile errors
mir3636
parents: 276
diff changeset
1 #include "../context.h"
2c2e4e597eb0 generate no compile errors
mir3636
parents: 276
diff changeset
2
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
3 #include <stdio.h>
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
4
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
5 /*
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
6 * Nonnon-blocking queue of Paper: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms(https://www.research.ibm.com/people/m/michael/podc-1996.pdf).
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
7 */
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
8
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
9 Queue* createSynchronizedQueue(struct Context* context) {
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
10 struct Queue* queue = new Queue();
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
11 struct SynchronizedQueue* synchronizedQueue = new SynchronizedQueue();
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
12 synchronizedQueue->top = new Element();
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
13 synchronizedQueue->top->next = NULL;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
14 synchronizedQueue->last = synchronizedQueue->top;
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
15 queue->queue = (union Data*)synchronizedQueue;
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
16 queue->take = C_takeSynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
17 queue->put = C_putSynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
18 queue->isEmpty = C_isEmptySynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
19 queue->clear = C_clearSynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
20 return queue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
21 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
22
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
23 __code clearSynchronizedQueue(struct SynchronizedQueue* queue, __code next(...)) {
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
24 struct Element* top = queue->top;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
25 if (__sync_bool_compare_and_swap(&queue->top, top, NULL)) {
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
26 goto next(...);
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
27 } else {
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
28 goto meta(context, C_clearSynchronizedQueue);
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
29 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
30 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
31
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
32 __code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) {
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
33 Element* element = new Element();
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
34 element->data = data;
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
35 element->next = NULL;
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
36 Element* last = queue->last;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
37 Element* nextElement = last->next;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
38 if (last != queue->last) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
39 goto meta(context, C_putSynchronizedQueue);
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
40 }
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
41 if (nextElement == NULL) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
42 if (__sync_bool_compare_and_swap(&last->next, nextElement, element)) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
43 __sync_bool_compare_and_swap(&queue->last, last, element);
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
44 goto next(...);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
45 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
46 } else {
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
47 __sync_bool_compare_and_swap(&queue->last, last, nextElement);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
48 }
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
49 goto meta(context, C_putSynchronizedQueue);
287
6b099d73949c Add queueCount sem to SynchronizedQueue
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 282
diff changeset
50 }
6b099d73949c Add queueCount sem to SynchronizedQueue
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 282
diff changeset
51
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
52 __code takeSynchronizedQueue(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) {
287
6b099d73949c Add queueCount sem to SynchronizedQueue
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 282
diff changeset
53 struct Element* top = queue->top;
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
54 struct Element* last = queue->last;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
55 struct Element* nextElement = top->next;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
56 if (top != queue->top) {
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
57 goto meta(context, C_takeSynchronizedQueue);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
58 }
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
59 if (top == last) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
60 if (nextElement != NULL) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
61 __sync_bool_compare_and_swap(&queue->last, last, nextElement);
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
62 }
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
63 } else {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
64 if (__sync_bool_compare_and_swap(&queue->top, top, nextElement)) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
65 data = nextElement->data;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
66 goto next(data, ...);
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
67 }
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
68 }
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
69 goto meta(context, C_takeSynchronizedQueue);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
70 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
71
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
72 __code isEmptySynchronizedQueue(struct SynchronizedQueue* queue, __code next(...), __code whenEmpty(...)) {
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
73 if (queue->top)
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
74 goto next(...);
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
75 else
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
76 goto whenEmpty(...);
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
77 }