5 extern private_t private;
7 void init_private(int pid)
9 private.node = 2 + pid;
12 static unsigned int new_node()
17 static void reclaim(unsigned int node)
22 void init_queue(queue_t *q)
29 /* initialize queue */
30 head = MAKE_POINTER(1, 0);
31 tail = MAKE_POINTER(1, 0);
32 next = MAKE_POINTER(0, 0); // (NULL, 0)
34 atomic_init(&q->nodes[0].next, 0); // assumed inititalized in original example
36 atomic_store(&q->head, head);
37 atomic_store(&q->tail, tail);
38 atomic_store(&q->nodes[1].next, next);
40 /* initialize avail list */
41 for (i = 2; i < MAX_NODES; i++) {
42 next = MAKE_POINTER(i + 1, 0);
43 atomic_store(&q->nodes[i].next, next);
46 next = MAKE_POINTER(0, 0); // (NULL, 0)
47 atomic_store(&q->nodes[MAX_NODES].next, next);
50 void enqueue(queue_t *q, unsigned int val)
59 q->nodes[node].value = val;
60 tmp = atomic_load(&q->nodes[node].next);
61 set_ptr(&tmp, 0); // NULL
62 atomic_store(&q->nodes[node].next, tmp);
65 tail = atomic_load(&q->tail);
66 next = atomic_load(&q->nodes[get_ptr(tail)].next);
67 if (tail == atomic_load(&q->tail)) {
68 if (get_ptr(next) == 0) { // == NULL
69 pointer val = MAKE_POINTER(node, get_count(next) + 1);
70 success = atomic_compare_exchange_weak(&q->nodes[get_ptr(tail)].next,
75 unsigned int ptr = get_ptr(atomic_load(&q->nodes[get_ptr(tail)].next));
76 pointer val = MAKE_POINTER(ptr,
78 atomic_compare_exchange_strong(&q->tail,
85 atomic_compare_exchange_strong(&q->tail,
87 MAKE_POINTER(node, get_count(tail) + 1));
90 unsigned int dequeue(queue_t *q)
99 head = atomic_load(&q->head);
100 tail = atomic_load(&q->tail);
101 next = atomic_load(&q->nodes[get_ptr(head)].next);
102 if (atomic_load(&q->head) == head) {
103 if (get_ptr(head) == get_ptr(tail)) {
104 if (get_ptr(next) == 0) { // NULL
107 atomic_compare_exchange_weak(&q->tail,
109 MAKE_POINTER(get_ptr(next), get_count(tail) + 1));
112 value = q->nodes[get_ptr(next)].value;
113 success = atomic_compare_exchange_weak(&q->head,
115 MAKE_POINTER(get_ptr(next), get_count(head) + 1));
121 reclaim(get_ptr(head));