Coverage Report

Created: 2024-09-08 06:18

/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
}