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 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif
23
24 #include <winpr/crt.h>
25
26 #include <winpr/collections.h>
27
28 /**
29 * C equivalent of the C# Queue Class:
30 * http://msdn.microsoft.com/en-us/library/system.collections.queue.aspx
31 */
32
33 /**
34 * Properties
35 */
36
37 /**
38 * Gets the number of elements contained in the Queue.
39 */
40
Queue_Count(wQueue * queue)41 int Queue_Count(wQueue* queue)
42 {
43 int ret;
44
45 if (queue->synchronized)
46 EnterCriticalSection(&queue->lock);
47
48 ret = queue->size;
49
50 if (queue->synchronized)
51 LeaveCriticalSection(&queue->lock);
52
53 return ret;
54 }
55
56 /**
57 * Lock access to the ArrayList
58 */
59
Queue_Lock(wQueue * queue)60 void Queue_Lock(wQueue* queue)
61 {
62 EnterCriticalSection(&queue->lock);
63 }
64
65 /**
66 * Unlock access to the ArrayList
67 */
68
Queue_Unlock(wQueue * queue)69 void Queue_Unlock(wQueue* queue)
70 {
71 LeaveCriticalSection(&queue->lock);
72 }
73
74 /**
75 * Gets an event which is set when the queue is non-empty
76 */
77
Queue_Event(wQueue * queue)78 HANDLE Queue_Event(wQueue* queue)
79 {
80 return queue->event;
81 }
82
83 /**
84 * Methods
85 */
86
87 /**
88 * Removes all objects from the Queue.
89 */
90
Queue_Clear(wQueue * queue)91 void Queue_Clear(wQueue* queue)
92 {
93 int index;
94
95 if (queue->synchronized)
96 EnterCriticalSection(&queue->lock);
97
98 for (index = queue->head; index != queue->tail; index = (index + 1) % queue->capacity)
99 {
100 if (queue->object.fnObjectFree)
101 queue->object.fnObjectFree(queue->array[index]);
102
103 queue->array[index] = NULL;
104 }
105
106 queue->size = 0;
107 queue->head = queue->tail = 0;
108
109 if (queue->synchronized)
110 LeaveCriticalSection(&queue->lock);
111 }
112
113 /**
114 * Determines whether an element is in the Queue.
115 */
116
Queue_Contains(wQueue * queue,void * obj)117 BOOL Queue_Contains(wQueue* queue, void* obj)
118 {
119 int index;
120 BOOL found = FALSE;
121
122 if (queue->synchronized)
123 EnterCriticalSection(&queue->lock);
124
125 for (index = 0; index < queue->tail; index++)
126 {
127 if (queue->object.fnObjectEquals(queue->array[index], obj))
128 {
129 found = TRUE;
130 break;
131 }
132 }
133
134 if (queue->synchronized)
135 LeaveCriticalSection(&queue->lock);
136
137 return found;
138 }
139
140 /**
141 * Adds an object to the end of the Queue.
142 */
143
Queue_Enqueue(wQueue * queue,void * obj)144 BOOL Queue_Enqueue(wQueue* queue, void* obj)
145 {
146 BOOL ret = TRUE;
147
148 if (queue->synchronized)
149 EnterCriticalSection(&queue->lock);
150
151 if (queue->size == queue->capacity)
152 {
153 int old_capacity;
154 int new_capacity;
155 void** newArray;
156 old_capacity = queue->capacity;
157 new_capacity = queue->capacity * queue->growthFactor;
158 newArray = (void**)realloc(queue->array, sizeof(void*) * new_capacity);
159
160 if (!newArray)
161 {
162 ret = FALSE;
163 goto out;
164 }
165
166 queue->capacity = new_capacity;
167 queue->array = newArray;
168 ZeroMemory(&(queue->array[old_capacity]), (new_capacity - old_capacity) * sizeof(void*));
169
170 /* rearrange wrapped entries */
171 if (queue->tail <= queue->head)
172 {
173 CopyMemory(&(queue->array[old_capacity]), queue->array, queue->tail * sizeof(void*));
174 queue->tail += old_capacity;
175 }
176 }
177
178 queue->array[queue->tail] = obj;
179 queue->tail = (queue->tail + 1) % queue->capacity;
180 queue->size++;
181 SetEvent(queue->event);
182 out:
183
184 if (queue->synchronized)
185 LeaveCriticalSection(&queue->lock);
186
187 return ret;
188 }
189
190 /**
191 * Removes and returns the object at the beginning of the Queue.
192 */
193
Queue_Dequeue(wQueue * queue)194 void* Queue_Dequeue(wQueue* queue)
195 {
196 void* obj = NULL;
197
198 if (queue->synchronized)
199 EnterCriticalSection(&queue->lock);
200
201 if (queue->size > 0)
202 {
203 obj = queue->array[queue->head];
204 queue->array[queue->head] = NULL;
205 queue->head = (queue->head + 1) % queue->capacity;
206 queue->size--;
207 }
208
209 if (queue->size < 1)
210 ResetEvent(queue->event);
211
212 if (queue->synchronized)
213 LeaveCriticalSection(&queue->lock);
214
215 return obj;
216 }
217
218 /**
219 * Returns the object at the beginning of the Queue without removing it.
220 */
221
Queue_Peek(wQueue * queue)222 void* Queue_Peek(wQueue* queue)
223 {
224 void* obj = NULL;
225
226 if (queue->synchronized)
227 EnterCriticalSection(&queue->lock);
228
229 if (queue->size > 0)
230 obj = queue->array[queue->head];
231
232 if (queue->synchronized)
233 LeaveCriticalSection(&queue->lock);
234
235 return obj;
236 }
237
default_queue_equals(const void * obj1,const void * obj2)238 static BOOL default_queue_equals(const void* obj1, const void* obj2)
239 {
240 return (obj1 == obj2);
241 }
242
243 /**
244 * Construction, Destruction
245 */
246
Queue_New(BOOL synchronized,int capacity,int growthFactor)247 wQueue* Queue_New(BOOL synchronized, int capacity, int growthFactor)
248 {
249 wQueue* queue = NULL;
250 queue = (wQueue*)calloc(1, sizeof(wQueue));
251
252 if (!queue)
253 return NULL;
254
255 queue->capacity = 32;
256 queue->growthFactor = 2;
257 queue->synchronized = synchronized;
258
259 if (capacity > 0)
260 queue->capacity = capacity;
261
262 if (growthFactor > 0)
263 queue->growthFactor = growthFactor;
264
265 queue->array = (void**)calloc(queue->capacity, sizeof(void*));
266
267 if (!queue->array)
268 goto out_free;
269
270 queue->event = CreateEvent(NULL, TRUE, FALSE, NULL);
271
272 if (!queue->event)
273 goto out_free_array;
274
275 if (!InitializeCriticalSectionAndSpinCount(&queue->lock, 4000))
276 goto out_free_event;
277
278 queue->object.fnObjectEquals = default_queue_equals;
279 return queue;
280 out_free_event:
281 CloseHandle(queue->event);
282 out_free_array:
283 free(queue->array);
284 out_free:
285 free(queue);
286 return NULL;
287 }
288
Queue_Free(wQueue * queue)289 void Queue_Free(wQueue* queue)
290 {
291 if (!queue)
292 return;
293
294 Queue_Clear(queue);
295 CloseHandle(queue->event);
296 DeleteCriticalSection(&queue->lock);
297 free(queue->array);
298 free(queue);
299 }
300