Mercurial > hg > GearsTemplate

annotate src/parallel_execution/SynchronizedQueue.cbc @ 462:8d7e5d48cad3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Running CPU examples
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Wed, 20 Dec 2017 22:05:08 +0900
parents 57132ef16009
children ac244346c85d
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"
462
8d7e5d48cad3 Running CPU examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 447
diff changeset
2 #include "Queue.h"
8d7e5d48cad3 Running CPU examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 447
diff changeset
3 #include "Atomic.h"
280
2c2e4e597eb0 generate no compile errors
mir3636
parents: 276
diff changeset
4
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
5 #include <stdio.h>
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
6
447
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
7 /*
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
8 * 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
9 */
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
10
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
11 Queue* createSynchronizedQueue(struct Context* context) {
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
12 struct Queue* queue = new Queue();
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
13 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
14 synchronizedQueue->top = new Element();
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
15 synchronizedQueue->top->next = NULL;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
16 synchronizedQueue->last = synchronizedQueue->top;
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
17 synchronizedQueue->atomic = createAtomicReference(context);
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
18 queue->queue = (union Data*)synchronizedQueue;
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
19 queue->take = C_takeSynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
20 queue->put = C_putSynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
21 queue->isEmpty = C_isEmptySynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
22 queue->clear = C_clearSynchronizedQueue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
23 return queue;
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
24 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
25
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
26 __code clearSynchronizedQueue(struct SynchronizedQueue* queue, __code next(...)) {
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
27 struct Element* top = queue->top;
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
28 struct Atomic* atomic = queue->atomic;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
29 goto atomic->checkAndSet(&queue->top, top, NULL, next(...), clearSynchronizedQueue);
276
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) {
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
42 struct Atomic* atomic = queue->atomic;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
43 goto atomic->checkAndSet(&last->next, nextElement, element, next(...), putSynchronizedQueue);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
44 } else {
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
45 struct Atomic* atomic = queue->atomic;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
46 goto atomic->checkAndSet(&queue->last, last, nextElement, putSynchronizedQueue, putSynchronizedQueue);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
47 }
287
6b099d73949c Add queueCount sem to SynchronizedQueue
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 282
diff changeset
48 }
6b099d73949c Add queueCount sem to SynchronizedQueue
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 282
diff changeset
49
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
50 __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
51 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
52 struct Element* last = queue->last;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
53 struct Element* nextElement = top->next;
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
54 if (top != queue->top) {
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
55 goto meta(context, C_takeSynchronizedQueue);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
56 }
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
57 if (top == last) {
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
58 if (nextElement != NULL) {
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
59 struct Atomic* atomic = queue->atomic;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
60 goto atomic->checkAndSet(&queue->last, last, nextElement, takeSynchronizedQueue, takeSynchronizedQueue);
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
61 }
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
62 } else {
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
63 struct Atomic* atomic = queue->atomic;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
64 goto atomic->checkAndSet(&queue->top, top, nextElement, takeSynchronizedQueue1, takeSynchronizedQueue);
361
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
65 }
a2c01ab30ea2 Add synchronized queue of paper
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 288
diff changeset
66 goto meta(context, C_takeSynchronizedQueue);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
67 }
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
68
444
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
69 __code takeSynchronizedQueue1(struct SynchronizedQueue* queue, __code next(union Data* data, ...), struct Element* nextElement) {
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
70 data = nextElement->data;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
71 goto next(data, ...);
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
72 }
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
73
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
74 __code takeSynchronizedQueue1_stub(struct Context* context) {
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
75 SynchronizedQueue* queue = (SynchronizedQueue*)GearImpl(context, Queue, queue);
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
76 enum Code next = Gearef(context, Queue)->next;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
77 Data** O_data = &Gearef(context, Queue)->data;
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
78 goto takeSynchronizedQueue1(context,
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
79 queue,
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
80 next,
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
81 O_data,
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
82 (struct Element*)Gearef(context, Atomic)->newData);
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
83 }
0c024ea61601 Using cas interface but occurred warning
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 361
diff changeset
84
282
a3448b0f0a56 Add input data gear
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 280
diff changeset
85 __code isEmptySynchronizedQueue(struct SynchronizedQueue* queue, __code next(...), __code whenEmpty(...)) {
447
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
86 struct Element* top = queue->top;
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
87 struct Element* last = queue->last;
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
88 struct Element* nextElement = top->next;
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
89 if (top != queue->top) {
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
90 goto meta(context, C_isEmptySynchronizedQueue);
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
91 }
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
92 if (top == last && nextElement == NULL) {
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
93 goto whenEmpty(...);
447
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
94 }
57132ef16009 Remove ALLOCATE_DATA_GEAR from par goto code gear arguments
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 444
diff changeset
95 goto next(...);
276
27bc962020de add SynchronizedQueue.cbc
mir3636
parents:
diff changeset
96 }