/src/FreeRDP/winpr/libwinpr/utils/collections/Queue.c
Line | Count | Source (jump to first uncovered line) |
1 | | /** |
2 | | * WinPR: Windows Portable Runtime |
3 | | * System.Collections.Queue |
4 | | * |
5 | | * Copyright 2012 Marc-Andre Moreau <marcandre.moreau@gmail.com> |
6 | | * |
7 | | * Licensed under the Apache License, Version 2.0 (the "License"); |
8 | | * you may not use this file except in compliance with the License. |
9 | | * You may obtain a copy of the License at |
10 | | * |
11 | | * http://www.apache.org/licenses/LICENSE-2.0 |
12 | | * |
13 | | * Unless required by applicable law or agreed to in writing, software |
14 | | * distributed under the License is distributed on an "AS IS" BASIS, |
15 | | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
16 | | * See the License for the specific language governing permissions and |
17 | | * limitations under the License. |
18 | | */ |
19 | | |
20 | | #include <winpr/config.h> |
21 | | |
22 | | #include <winpr/crt.h> |
23 | | #include <winpr/assert.h> |
24 | | |
25 | | #include <winpr/collections.h> |
26 | | |
27 | | struct s_wQueue |
28 | | { |
29 | | size_t capacity; |
30 | | size_t growthFactor; |
31 | | BOOL synchronized; |
32 | | |
33 | | BYTE padding[4]; |
34 | | |
35 | | size_t head; |
36 | | size_t tail; |
37 | | size_t size; |
38 | | void** array; |
39 | | CRITICAL_SECTION lock; |
40 | | HANDLE event; |
41 | | |
42 | | wObject object; |
43 | | BOOL haveLock; |
44 | | |
45 | | BYTE padding2[4]; |
46 | | }; |
47 | | |
48 | | /** |
49 | | * C equivalent of the C# Queue Class: |
50 | | * http://msdn.microsoft.com/en-us/library/system.collections.queue.aspx |
51 | | */ |
52 | | |
53 | | /** |
54 | | * Properties |
55 | | */ |
56 | | |
57 | | /** |
58 | | * Gets the number of elements contained in the Queue. |
59 | | */ |
60 | | |
61 | | size_t Queue_Count(wQueue* queue) |
62 | 0 | { |
63 | 0 | size_t ret = 0; |
64 | |
|
65 | 0 | Queue_Lock(queue); |
66 | |
|
67 | 0 | ret = queue->size; |
68 | |
|
69 | 0 | Queue_Unlock(queue); |
70 | |
|
71 | 0 | return ret; |
72 | 0 | } |
73 | | |
74 | | /** |
75 | | * Lock access to the ArrayList |
76 | | */ |
77 | | |
78 | | void Queue_Lock(wQueue* queue) |
79 | 10.8k | { |
80 | 10.8k | WINPR_ASSERT(queue); |
81 | 10.8k | if (queue->synchronized) |
82 | 10.8k | EnterCriticalSection(&queue->lock); |
83 | 10.8k | } |
84 | | |
85 | | /** |
86 | | * Unlock access to the ArrayList |
87 | | */ |
88 | | |
89 | | void Queue_Unlock(wQueue* queue) |
90 | 10.8k | { |
91 | 10.8k | WINPR_ASSERT(queue); |
92 | 10.8k | if (queue->synchronized) |
93 | 10.8k | LeaveCriticalSection(&queue->lock); |
94 | 10.8k | } |
95 | | |
96 | | /** |
97 | | * Gets an event which is set when the queue is non-empty |
98 | | */ |
99 | | |
100 | | HANDLE Queue_Event(wQueue* queue) |
101 | 345k | { |
102 | 345k | WINPR_ASSERT(queue); |
103 | 345k | return queue->event; |
104 | 345k | } |
105 | | |
106 | | wObject* Queue_Object(wQueue* queue) |
107 | 10.8k | { |
108 | 10.8k | WINPR_ASSERT(queue); |
109 | 10.8k | return &queue->object; |
110 | 10.8k | } |
111 | | |
112 | | /** |
113 | | * Methods |
114 | | */ |
115 | | |
116 | | /** |
117 | | * Removes all objects from the Queue. |
118 | | */ |
119 | | |
120 | | void Queue_Clear(wQueue* queue) |
121 | 10.8k | { |
122 | 10.8k | Queue_Lock(queue); |
123 | | |
124 | 10.8k | for (size_t index = queue->head; index != queue->tail; index = (index + 1) % queue->capacity) |
125 | 0 | { |
126 | 0 | if (queue->object.fnObjectFree) |
127 | 0 | queue->object.fnObjectFree(queue->array[index]); |
128 | |
|
129 | 0 | queue->array[index] = NULL; |
130 | 0 | } |
131 | | |
132 | 10.8k | queue->size = 0; |
133 | 10.8k | queue->head = queue->tail = 0; |
134 | 10.8k | ResetEvent(queue->event); |
135 | 10.8k | Queue_Unlock(queue); |
136 | 10.8k | } |
137 | | |
138 | | /** |
139 | | * Determines whether an element is in the Queue. |
140 | | */ |
141 | | |
142 | | BOOL Queue_Contains(wQueue* queue, const void* obj) |
143 | 0 | { |
144 | 0 | BOOL found = FALSE; |
145 | |
|
146 | 0 | Queue_Lock(queue); |
147 | |
|
148 | 0 | for (size_t index = 0; index < queue->tail; index++) |
149 | 0 | { |
150 | 0 | if (queue->object.fnObjectEquals(queue->array[index], obj)) |
151 | 0 | { |
152 | 0 | found = TRUE; |
153 | 0 | break; |
154 | 0 | } |
155 | 0 | } |
156 | |
|
157 | 0 | Queue_Unlock(queue); |
158 | |
|
159 | 0 | return found; |
160 | 0 | } |
161 | | |
162 | | static BOOL Queue_EnsureCapacity(wQueue* queue, size_t count) |
163 | 10.8k | { |
164 | 10.8k | WINPR_ASSERT(queue); |
165 | | |
166 | 10.8k | if (queue->size + count >= queue->capacity) |
167 | 10.8k | { |
168 | 10.8k | const size_t old_capacity = queue->capacity; |
169 | 10.8k | size_t new_capacity = queue->capacity * queue->growthFactor; |
170 | 10.8k | void** newArray = NULL; |
171 | 10.8k | if (new_capacity < queue->size + count) |
172 | 10.8k | new_capacity = queue->size + count; |
173 | 10.8k | newArray = (void**)realloc(queue->array, sizeof(void*) * new_capacity); |
174 | | |
175 | 10.8k | if (!newArray) |
176 | 0 | return FALSE; |
177 | | |
178 | 10.8k | queue->capacity = new_capacity; |
179 | 10.8k | queue->array = newArray; |
180 | 10.8k | ZeroMemory(&(queue->array[old_capacity]), (new_capacity - old_capacity) * sizeof(void*)); |
181 | | |
182 | | /* rearrange wrapped entries */ |
183 | 10.8k | if (queue->tail <= queue->head) |
184 | 10.8k | { |
185 | 10.8k | CopyMemory(&(queue->array[old_capacity]), queue->array, queue->tail * sizeof(void*)); |
186 | 10.8k | queue->tail += old_capacity; |
187 | 10.8k | } |
188 | 10.8k | } |
189 | 10.8k | return TRUE; |
190 | 10.8k | } |
191 | | |
192 | | /** |
193 | | * Adds an object to the end of the Queue. |
194 | | */ |
195 | | |
196 | | BOOL Queue_Enqueue(wQueue* queue, const void* obj) |
197 | 0 | { |
198 | 0 | BOOL ret = TRUE; |
199 | |
|
200 | 0 | Queue_Lock(queue); |
201 | |
|
202 | 0 | if (!Queue_EnsureCapacity(queue, 1)) |
203 | 0 | goto out; |
204 | | |
205 | 0 | if (queue->object.fnObjectNew) |
206 | 0 | queue->array[queue->tail] = queue->object.fnObjectNew(obj); |
207 | 0 | else |
208 | 0 | { |
209 | 0 | union |
210 | 0 | { |
211 | 0 | const void* cv; |
212 | 0 | void* v; |
213 | 0 | } cnv; |
214 | 0 | cnv.cv = obj; |
215 | 0 | queue->array[queue->tail] = cnv.v; |
216 | 0 | } |
217 | 0 | queue->tail = (queue->tail + 1) % queue->capacity; |
218 | |
|
219 | 0 | const BOOL signalSet = queue->size == 0; |
220 | 0 | queue->size++; |
221 | |
|
222 | 0 | if (signalSet) |
223 | 0 | SetEvent(queue->event); |
224 | 0 | out: |
225 | |
|
226 | 0 | Queue_Unlock(queue); |
227 | |
|
228 | 0 | return ret; |
229 | 0 | } |
230 | | |
231 | | /** |
232 | | * Removes and returns the object at the beginning of the Queue. |
233 | | */ |
234 | | |
235 | | void* Queue_Dequeue(wQueue* queue) |
236 | 0 | { |
237 | 0 | void* obj = NULL; |
238 | |
|
239 | 0 | Queue_Lock(queue); |
240 | |
|
241 | 0 | if (queue->size > 0) |
242 | 0 | { |
243 | 0 | obj = queue->array[queue->head]; |
244 | 0 | queue->array[queue->head] = NULL; |
245 | 0 | queue->head = (queue->head + 1) % queue->capacity; |
246 | 0 | queue->size--; |
247 | 0 | } |
248 | |
|
249 | 0 | if (queue->size < 1) |
250 | 0 | ResetEvent(queue->event); |
251 | |
|
252 | 0 | Queue_Unlock(queue); |
253 | |
|
254 | 0 | return obj; |
255 | 0 | } |
256 | | |
257 | | /** |
258 | | * Returns the object at the beginning of the Queue without removing it. |
259 | | */ |
260 | | |
261 | | void* Queue_Peek(wQueue* queue) |
262 | 0 | { |
263 | 0 | void* obj = NULL; |
264 | |
|
265 | 0 | Queue_Lock(queue); |
266 | |
|
267 | 0 | if (queue->size > 0) |
268 | 0 | obj = queue->array[queue->head]; |
269 | |
|
270 | 0 | Queue_Unlock(queue); |
271 | |
|
272 | 0 | return obj; |
273 | 0 | } |
274 | | |
275 | | void Queue_Discard(wQueue* queue) |
276 | 0 | { |
277 | 0 | void* obj = NULL; |
278 | |
|
279 | 0 | Queue_Lock(queue); |
280 | 0 | obj = Queue_Dequeue(queue); |
281 | |
|
282 | 0 | if (queue->object.fnObjectFree) |
283 | 0 | queue->object.fnObjectFree(obj); |
284 | 0 | Queue_Unlock(queue); |
285 | 0 | } |
286 | | |
287 | | static BOOL default_queue_equals(const void* obj1, const void* obj2) |
288 | 0 | { |
289 | 0 | return (obj1 == obj2); |
290 | 0 | } |
291 | | |
292 | | /** |
293 | | * Construction, Destruction |
294 | | */ |
295 | | |
296 | | wQueue* Queue_New(BOOL synchronized, SSIZE_T capacity, SSIZE_T growthFactor) |
297 | 10.8k | { |
298 | 10.8k | wObject* obj = NULL; |
299 | 10.8k | wQueue* queue = NULL; |
300 | 10.8k | queue = (wQueue*)calloc(1, sizeof(wQueue)); |
301 | | |
302 | 10.8k | if (!queue) |
303 | 0 | return NULL; |
304 | | |
305 | 10.8k | queue->synchronized = synchronized; |
306 | | |
307 | 10.8k | queue->growthFactor = 2; |
308 | 10.8k | if (growthFactor > 0) |
309 | 0 | queue->growthFactor = (size_t)growthFactor; |
310 | | |
311 | 10.8k | if (capacity <= 0) |
312 | 10.8k | capacity = 32; |
313 | 10.8k | if (!InitializeCriticalSectionAndSpinCount(&queue->lock, 4000)) |
314 | 0 | goto fail; |
315 | 10.8k | queue->haveLock = TRUE; |
316 | 10.8k | if (!Queue_EnsureCapacity(queue, (size_t)capacity)) |
317 | 0 | goto fail; |
318 | | |
319 | 10.8k | queue->event = CreateEvent(NULL, TRUE, FALSE, NULL); |
320 | | |
321 | 10.8k | if (!queue->event) |
322 | 0 | goto fail; |
323 | | |
324 | 10.8k | obj = Queue_Object(queue); |
325 | 10.8k | obj->fnObjectEquals = default_queue_equals; |
326 | | |
327 | 10.8k | return queue; |
328 | 0 | fail: |
329 | 0 | WINPR_PRAGMA_DIAG_PUSH |
330 | 0 | WINPR_PRAGMA_DIAG_IGNORED_MISMATCHED_DEALLOC |
331 | 0 | Queue_Free(queue); |
332 | 0 | WINPR_PRAGMA_DIAG_POP |
333 | 0 | return NULL; |
334 | 10.8k | } |
335 | | |
336 | | void Queue_Free(wQueue* queue) |
337 | 10.8k | { |
338 | 10.8k | if (!queue) |
339 | 0 | return; |
340 | | |
341 | 10.8k | if (queue->haveLock) |
342 | 10.8k | { |
343 | 10.8k | Queue_Clear(queue); |
344 | 10.8k | DeleteCriticalSection(&queue->lock); |
345 | 10.8k | } |
346 | 10.8k | CloseHandle(queue->event); |
347 | 10.8k | free(queue->array); |
348 | 10.8k | free(queue); |
349 | 10.8k | } |