3 extern unsigned int iterations;
4 extern private_t private;
5 extern shared_mem_t *smp;
7 void init_private(int pid)
9 private.node = 2 + pid;
10 private.value = 1 + (pid * iterations);
18 static unsigned int new_node()
23 static void reclaim(unsigned int node)
35 /* initialize queue */
36 head = MAKE_POINTER(1, 0);
37 tail = MAKE_POINTER(1, 0);
38 next = MAKE_POINTER(0, 0); // (NULL, 0)
40 atomic_init(&smp->nodes[0].next, 0); // assumed inititalized in original example
42 atomic_store(&smp->head, head);
43 atomic_store(&smp->tail, tail);
44 atomic_store(&smp->nodes[1].next, next);
46 /* initialize avail list */
47 for (i = 2; i < MAX_NODES; i++) {
48 next = MAKE_POINTER(i + 1, 0);
49 atomic_store(&smp->nodes[i].next, next);
52 next = MAKE_POINTER(0, 0); // (NULL, 0)
53 atomic_store(&smp->nodes[MAX_NODES].next, next);
56 void enqueue(unsigned int val)
58 unsigned int success = 0;
65 smp->nodes[node].value = val;
66 tmp = atomic_load(&smp->nodes[node].next);
67 set_ptr(&tmp, 0); // NULL
68 atomic_store(&smp->nodes[node].next, tmp);
71 tail = atomic_load(&smp->tail);
72 next = atomic_load(&smp->nodes[get_ptr(tail)].next);
73 if (tail == atomic_load(&smp->tail)) {
74 if (get_ptr(next) == 0) { // == NULL
75 pointer val = MAKE_POINTER(node, get_count(next) + 1);
76 success = atomic_compare_exchange_weak(&smp->nodes[get_ptr(tail)].next,
81 unsigned int ptr = get_ptr(atomic_load(&smp->nodes[get_ptr(tail)].next));
82 pointer val = MAKE_POINTER(ptr,
84 atomic_compare_exchange_strong(&smp->tail,
91 atomic_compare_exchange_strong(&smp->tail,
93 MAKE_POINTER(node, get_count(tail) + 1));
96 unsigned int dequeue()
104 for (success = FALSE; success == FALSE; ) {
105 head = atomic_load(&smp->head);
106 tail = atomic_load(&smp->tail);
107 next = atomic_load(&smp->nodes[get_ptr(head)].next);
108 if (atomic_load(&smp->head) == head) {
109 if (get_ptr(head) == get_ptr(tail)) {
110 if (get_ptr(next) == 0) { // NULL
113 atomic_compare_exchange_weak(&smp->tail,
115 MAKE_POINTER(get_ptr(next), get_count(tail) + 1));
118 value = smp->nodes[get_ptr(next)].value;
119 success = atomic_compare_exchange_weak(&smp->head,
121 MAKE_POINTER(get_ptr(next), get_count(head) + 1));
122 if (success == FALSE) {
128 reclaim(get_ptr(head));