7 static unsigned int *node_nums;
9 static unsigned int new_node()
11 return node_nums[get_thread_num()];
14 static void reclaim(unsigned int node)
16 node_nums[get_thread_num()] = node;
19 void init_queue(queue_t *q, int num_threads)
26 node_nums = malloc(num_threads * sizeof(*node_nums));
27 for (i = 0; i < num_threads; i++)
30 /* Note: needed to add this init manually */
31 atomic_init(&q->nodes[0].next, 0);
33 /* initialize queue */
34 head = MAKE_POINTER(1, 0);
35 tail = MAKE_POINTER(1, 0);
36 next = MAKE_POINTER(0, 0); // (NULL, 0)
38 atomic_init(&q->head, head);
39 atomic_init(&q->tail, tail);
40 atomic_init(&q->nodes[1].next, next);
42 /* initialize avail list */
43 for (i = 2; i < MAX_NODES; i++) {
44 next = MAKE_POINTER(i + 1, 0);
45 atomic_init(&q->nodes[i].next, next);
48 next = MAKE_POINTER(0, 0); // (NULL, 0)
49 atomic_init(&q->nodes[MAX_NODES].next, next);
52 void enqueue(queue_t *q, unsigned int val)
61 store_32(&q->nodes[node].value, val);
62 tmp = atomic_load_explicit(&q->nodes[node].next, memory_order_relaxed);
63 set_ptr(&tmp, 0); // NULL
64 atomic_store_explicit(&q->nodes[node].next, tmp, memory_order_relaxed);
67 tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
68 next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, memory_order_relaxed);
69 if (tail == atomic_load(&q->tail)) {
70 if (get_ptr(next) == 0) { // == NULL
71 pointer value = MAKE_POINTER(node, get_count(next) + 1);
72 success = atomic_compare_exchange_weak_explicit(&q->nodes[get_ptr(tail)].next,
73 &next, value, memory_order_release, memory_order_release);
76 unsigned int ptr = get_ptr(atomic_load(&q->nodes[get_ptr(tail)].next));
77 pointer value = MAKE_POINTER(ptr,
79 atomic_compare_exchange_strong(&q->tail,
85 atomic_compare_exchange_strong_explicit(&q->tail,
87 MAKE_POINTER(node, get_count(tail) + 1),
88 memory_order_release, memory_order_release);
91 unsigned int dequeue(queue_t *q)
100 head = atomic_load_explicit(&q->head, memory_order_relaxed);
101 tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
102 next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, memory_order_relaxed);
103 if (atomic_load(&q->head) == head) {
104 if (get_ptr(head) == get_ptr(tail)) {
105 if (get_ptr(next) == 0) { // NULL
108 atomic_compare_exchange_strong(&q->tail,
110 MAKE_POINTER(get_ptr(next), get_count(tail) + 1));
113 value = load_32(&q->nodes[get_ptr(next)].value);
114 success = atomic_compare_exchange_weak(&q->head,
116 MAKE_POINTER(get_ptr(next), get_count(head) + 1));
122 reclaim(get_ptr(head));