-
Notifications
You must be signed in to change notification settings - Fork 0
/
LLQueue.c
180 lines (144 loc) · 5.22 KB
/
LLQueue.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <malloc.h>
#include <stdatomic.h>
#include <stdbool.h>
#include "HazardPointer.h"
#include "LLQueue.h"
struct LLNode;
typedef struct LLNode LLNode;
typedef _Atomic(LLNode*) AtomicLLNodePtr;
struct LLNode {
AtomicLLNodePtr next;
Value item;
};
LLNode* LLNode_new(Value item) {
LLNode* node = (LLNode*)malloc(sizeof(LLNode));
atomic_store(&node->next, NULL);
node->item = item;
return node;
}
struct LLQueue {
AtomicLLNodePtr head;
AtomicLLNodePtr tail;
HazardPointer *hp;
};
LLQueue* LLQueue_new(void) {
LLQueue* queue = (LLQueue*)malloc(sizeof(LLQueue));
LLNode* dummy = LLNode_new(EMPTY_VALUE);
atomic_store(&queue->head, dummy);
atomic_store(&queue->tail, dummy);
queue->hp = malloc(sizeof(HazardPointer));
HazardPointer_initialize(queue->hp);
return queue;
}
void LLQueue_delete(LLQueue* queue) {
LLNode* current = atomic_load(&queue->head);
while (current != NULL) {
LLNode* next = atomic_load(¤t->next);
HazardPointer_retire(queue->hp, current);
current = next;
}
HazardPointer_finalize(queue->hp);
free(queue);
}
void LLQueue_push(LLQueue* queue, Value item) {
LLNode* new_node = LLNode_new(item); // Tworzymy nowy węzeł.
LLNode* tail;
while (true) {
tail = atomic_load(&queue->tail); // Zabezpieczamy ogon przed zmianą przez inne wątki.
// "Chronimy" ogon za pomocą Hazard Pointer przed usunięciem.
HazardPointer_protect(queue->hp, (const _Atomic(void*)*)&queue->tail);
LLNode* next = atomic_load(&tail->next);
// Ponownie sprawdzamy, czy ogon się nie zmienił.
if (tail == atomic_load(&queue->tail)) {
if (next == NULL) {
// Próbujemy dodać nowy węzeł na koniec kolejki.
if (atomic_compare_exchange_strong(&tail->next, &next, new_node)) {
// Jeśli się udało, aktualizujemy ogon kolejki.
atomic_compare_exchange_strong(&queue->tail, &tail, new_node);
// Usuwamy zabezpieczenie dla ogona, ponieważ skończyliśmy operację.
HazardPointer_clear(queue->hp);
break;
}
} else {
// Jeśli ogon ma już następnik, próbujemy przesunąć ogon dalej.
atomic_compare_exchange_strong(&queue->tail, &tail, next);
}
}
// Jeśli ogon został zmieniony przez inny wątek, usuwamy zabezpieczenie i próbujemy ponownie.
HazardPointer_clear(queue->hp);
}
}
Value LLQueue_pop(LLQueue* queue) {
LLNode* head;
LLNode* next;
Value result;
while (true) {
head = atomic_load(&queue->head);
// Zabezpieczamy 'head' za pomocą Hazard Pointer.
HazardPointer_protect(queue->hp, (const _Atomic(void*)*)&queue->head);
next = atomic_load(&head->next);
if (head != atomic_load(&queue->head)) {
// Stan kolejki zmienił się, próbujemy ponownie.
continue;
}
if (next == NULL) {
// Kolejka jest pusta.
HazardPointer_clear(queue->hp); // Czyszczenie zabezpieczenia.
return EMPTY_VALUE;
}
// Próbujemy zaktualizować 'head' na 'next'.
if (atomic_compare_exchange_strong(&queue->head, &head, next)) {
result = next->item;
// Usuwamy zabezpieczenie dla 'head', ponieważ 'head' już nie jest częścią kolejki.
HazardPointer_clear(queue->hp);
// 'head' jest teraz bezużyteczny, więc możemy go bezpiecznie "usunąć".
HazardPointer_retire(queue->hp, head);
return result;
}
// Czyszczenie zabezpieczenia, jeśli aktualizacja 'head' się nie powiodła.
HazardPointer_clear(queue->hp);
}
}
// Value LLQueue_pop(LLQueue* queue)
// {
// AtomicLLNodePtr head;
// AtomicLLNodePtr next;
// Value result;
// do {
// head = atomic_load(&queue->head);
// HazardPointer_protect(queue->hp, (const _Atomic(void*)*)&head);
// result = atomic_exchange(&head->item, EMPTY_VALUE);
// if (result != EMPTY_VALUE) {
// atomic_compare_exchange_weak()
// return result;
// } else {
// if ()
// }
// } while (true)
// }
// void* pop(_Atomic Stack* stack) {
// void* data;
// Stack next, prev;
// prev = atomic_load(stack);
// do {
// if (prev.head == NULL) {
// return NULL;
// }
// next.head = prev.head->next;
// next.tag = prev.tag + 1;
// } while(!atomic_compare_exchange_weak(stack, &prev, next));
// data = prev.head->data;
// free(prev.head);
// return data;
// }
bool LLQueue_is_empty(LLQueue* queue)
{
LLNode* head = atomic_load(&queue->head);
// Zabezpieczamy 'head->next' za pomocą Hazard Pointer, aby upewnić się, że jest aktualne.
HazardPointer_protect(queue->hp, (const _Atomic(void*)*)&head->next);
LLNode* next = atomic_load(&head->next);
// Usuwamy zabezpieczenie, ponieważ nie będziemy już korzystać z 'next'.
HazardPointer_clear(queue->hp);
// Jeśli 'next' od 'head' jest NULL, kolejka jest pusta.
return next == NULL;
}