1 /**
2 * WinPR: Windows Portable Runtime
3 * System.Collections.ArrayList
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# ArrayList Class:
30 * http://msdn.microsoft.com/en-us/library/system.collections.arraylist.aspx
31 */
32
33 /**
34 * Properties
35 */
36
37 /**
38 * Gets or sets the number of elements that the ArrayList can contain.
39 */
40
ArrayList_Capacity(wArrayList * arrayList)41 int ArrayList_Capacity(wArrayList* arrayList)
42 {
43 return arrayList->capacity;
44 }
45
46 /**
47 * Gets the number of elements actually contained in the ArrayList.
48 */
49
ArrayList_Count(wArrayList * arrayList)50 int ArrayList_Count(wArrayList* arrayList)
51 {
52 return arrayList->size;
53 }
54
55 /**
56 * Gets the internal list of items contained in the ArrayList.
57 */
58
ArrayList_Items(wArrayList * arrayList,ULONG_PTR ** ppItems)59 int ArrayList_Items(wArrayList* arrayList, ULONG_PTR** ppItems)
60 {
61 *ppItems = (ULONG_PTR*)arrayList->array;
62 return arrayList->size;
63 }
64
65 /**
66 * Gets a value indicating whether the ArrayList has a fixed size.
67 */
68
ArrayList_IsFixedSized(wArrayList * arrayList)69 BOOL ArrayList_IsFixedSized(wArrayList* arrayList)
70 {
71 return FALSE;
72 }
73
74 /**
75 * Gets a value indicating whether the ArrayList is read-only.
76 */
77
ArrayList_IsReadOnly(wArrayList * arrayList)78 BOOL ArrayList_IsReadOnly(wArrayList* arrayList)
79 {
80 return FALSE;
81 }
82
83 /**
84 * Gets a value indicating whether access to the ArrayList is synchronized (thread safe).
85 */
86
ArrayList_IsSynchronized(wArrayList * arrayList)87 BOOL ArrayList_IsSynchronized(wArrayList* arrayList)
88 {
89 return arrayList->synchronized;
90 }
91
92 /**
93 * Lock access to the ArrayList
94 */
95
ArrayList_Lock(wArrayList * arrayList)96 void ArrayList_Lock(wArrayList* arrayList)
97 {
98 EnterCriticalSection(&arrayList->lock);
99 }
100
101 /**
102 * Unlock access to the ArrayList
103 */
104
ArrayList_Unlock(wArrayList * arrayList)105 void ArrayList_Unlock(wArrayList* arrayList)
106 {
107 LeaveCriticalSection(&arrayList->lock);
108 }
109
110 /**
111 * Gets the element at the specified index.
112 */
113
ArrayList_GetItem(wArrayList * arrayList,int index)114 void* ArrayList_GetItem(wArrayList* arrayList, int index)
115 {
116 void* obj = NULL;
117
118 if ((index >= 0) && (index < arrayList->size))
119 {
120 obj = arrayList->array[index];
121 }
122
123 return obj;
124 }
125
126 /**
127 * Sets the element at the specified index.
128 */
129
ArrayList_SetItem(wArrayList * arrayList,int index,void * obj)130 void ArrayList_SetItem(wArrayList* arrayList, int index, void* obj)
131 {
132 if ((index >= 0) && (index < arrayList->size))
133 {
134 arrayList->array[index] = obj;
135 }
136 }
137
138 /**
139 * Methods
140 */
141
142 /**
143 * Shift a section of the list.
144 */
145
ArrayList_Shift(wArrayList * arrayList,int index,int count)146 static BOOL ArrayList_Shift(wArrayList* arrayList, int index, int count)
147 {
148 if (count > 0)
149 {
150 if (arrayList->size + count > arrayList->capacity)
151 {
152 void** newArray;
153 int newCapacity = arrayList->capacity * arrayList->growthFactor;
154 newArray = (void**)realloc(arrayList->array, sizeof(void*) * newCapacity);
155
156 if (!newArray)
157 return FALSE;
158
159 arrayList->array = newArray;
160 arrayList->capacity = newCapacity;
161 }
162
163 MoveMemory(&arrayList->array[index + count], &arrayList->array[index],
164 (arrayList->size - index) * sizeof(void*));
165 arrayList->size += count;
166 }
167 else if (count < 0)
168 {
169 int chunk = arrayList->size - index + count;
170
171 if (chunk > 0)
172 MoveMemory(&arrayList->array[index], &arrayList->array[index - count],
173 chunk * sizeof(void*));
174
175 arrayList->size += count;
176 }
177
178 return TRUE;
179 }
180
181 /**
182 * Removes all elements from the ArrayList.
183 */
184
ArrayList_Clear(wArrayList * arrayList)185 void ArrayList_Clear(wArrayList* arrayList)
186 {
187 int index;
188
189 if (arrayList->synchronized)
190 EnterCriticalSection(&arrayList->lock);
191
192 for (index = 0; index < arrayList->size; index++)
193 {
194 if (arrayList->object.fnObjectFree)
195 arrayList->object.fnObjectFree(arrayList->array[index]);
196
197 arrayList->array[index] = NULL;
198 }
199
200 arrayList->size = 0;
201
202 if (arrayList->synchronized)
203 LeaveCriticalSection(&arrayList->lock);
204 }
205
206 /**
207 * Determines whether an element is in the ArrayList.
208 */
209
ArrayList_Contains(wArrayList * arrayList,void * obj)210 BOOL ArrayList_Contains(wArrayList* arrayList, void* obj)
211 {
212 int index;
213 BOOL rc = FALSE;
214
215 if (arrayList->synchronized)
216 EnterCriticalSection(&arrayList->lock);
217
218 for (index = 0; index < arrayList->size; index++)
219 {
220 rc = arrayList->object.fnObjectEquals(arrayList->array[index], obj);
221
222 if (rc)
223 break;
224 }
225
226 if (arrayList->synchronized)
227 LeaveCriticalSection(&arrayList->lock);
228
229 return rc;
230 }
231
232 /**
233 * Adds an object to the end of the ArrayList.
234 */
235
ArrayList_Add(wArrayList * arrayList,void * obj)236 int ArrayList_Add(wArrayList* arrayList, void* obj)
237 {
238 int index = -1;
239
240 if (arrayList->synchronized)
241 EnterCriticalSection(&arrayList->lock);
242
243 if (arrayList->size + 1 > arrayList->capacity)
244 {
245 void** newArray;
246 int newCapacity = arrayList->capacity * arrayList->growthFactor;
247 newArray = (void**)realloc(arrayList->array, sizeof(void*) * newCapacity);
248
249 if (!newArray)
250 goto out;
251
252 arrayList->array = newArray;
253 arrayList->capacity = newCapacity;
254 }
255
256 arrayList->array[arrayList->size++] = obj;
257 index = arrayList->size;
258 out:
259
260 if (arrayList->synchronized)
261 LeaveCriticalSection(&arrayList->lock);
262
263 return index;
264 }
265
266 /*
267 * Inserts an element into the ArrayList at the specified index.
268 */
269
ArrayList_Insert(wArrayList * arrayList,int index,void * obj)270 BOOL ArrayList_Insert(wArrayList* arrayList, int index, void* obj)
271 {
272 BOOL ret = TRUE;
273
274 if (arrayList->synchronized)
275 EnterCriticalSection(&arrayList->lock);
276
277 if ((index >= 0) && (index < arrayList->size))
278 {
279 if (!ArrayList_Shift(arrayList, index, 1))
280 {
281 ret = FALSE;
282 }
283 else
284 {
285 arrayList->array[index] = obj;
286 }
287 }
288
289 if (arrayList->synchronized)
290 LeaveCriticalSection(&arrayList->lock);
291
292 return ret;
293 }
294
295 /**
296 * Removes the first occurrence of a specific object from the ArrayList.
297 */
298
ArrayList_Remove(wArrayList * arrayList,void * obj)299 BOOL ArrayList_Remove(wArrayList* arrayList, void* obj)
300 {
301 int index;
302 BOOL found = FALSE;
303 BOOL ret = TRUE;
304
305 if (arrayList->synchronized)
306 EnterCriticalSection(&arrayList->lock);
307
308 for (index = 0; index < arrayList->size; index++)
309 {
310 if (arrayList->object.fnObjectEquals(arrayList->array[index], obj))
311 {
312 found = TRUE;
313 break;
314 }
315 }
316
317 if (found)
318 {
319 if (arrayList->object.fnObjectFree)
320 arrayList->object.fnObjectFree(arrayList->array[index]);
321
322 ret = ArrayList_Shift(arrayList, index, -1);
323 }
324
325 if (arrayList->synchronized)
326 LeaveCriticalSection(&arrayList->lock);
327
328 return ret;
329 }
330
331 /**
332 * Removes the element at the specified index of the ArrayList.
333 */
334
ArrayList_RemoveAt(wArrayList * arrayList,int index)335 BOOL ArrayList_RemoveAt(wArrayList* arrayList, int index)
336 {
337 BOOL ret = TRUE;
338
339 if (arrayList->synchronized)
340 EnterCriticalSection(&arrayList->lock);
341
342 if ((index >= 0) && (index < arrayList->size))
343 {
344 if (arrayList->object.fnObjectFree)
345 arrayList->object.fnObjectFree(arrayList->array[index]);
346
347 ret = ArrayList_Shift(arrayList, index, -1);
348 }
349
350 if (arrayList->synchronized)
351 LeaveCriticalSection(&arrayList->lock);
352
353 return ret;
354 }
355
356 /**
357 * Searches for the specified Object and returns the zero-based index of the first occurrence within
358 * the entire ArrayList.
359 *
360 * Searches for the specified Object and returns the zero-based index of the last occurrence within
361 * the range of elements in the ArrayList that extends from the first element to the specified
362 * index.
363 *
364 * Searches for the specified Object and returns the zero-based index of the last occurrence within
365 * the range of elements in the ArrayList that contains the specified number of elements and ends at
366 * the specified index.
367 */
368
ArrayList_IndexOf(wArrayList * arrayList,void * obj,int startIndex,int count)369 int ArrayList_IndexOf(wArrayList* arrayList, void* obj, int startIndex, int count)
370 {
371 int index;
372 BOOL found = FALSE;
373
374 if (arrayList->synchronized)
375 EnterCriticalSection(&arrayList->lock);
376
377 if (startIndex < 0)
378 startIndex = 0;
379
380 if (count < 0)
381 count = arrayList->size;
382
383 for (index = startIndex; index < startIndex + count; index++)
384 {
385 if (arrayList->object.fnObjectEquals(arrayList->array[index], obj))
386 {
387 found = TRUE;
388 break;
389 }
390 }
391
392 if (!found)
393 index = -1;
394
395 if (arrayList->synchronized)
396 LeaveCriticalSection(&arrayList->lock);
397
398 return index;
399 }
400
401 /**
402 * Searches for the specified Object and returns the zero-based index of the last occurrence within
403 * the entire ArrayList.
404 *
405 * Searches for the specified Object and returns the zero-based index of the last occurrence within
406 * the range of elements in the ArrayList that extends from the first element to the specified
407 * index.
408 *
409 * Searches for the specified Object and returns the zero-based index of the last occurrence within
410 * the range of elements in the ArrayList that contains the specified number of elements and ends at
411 * the specified index.
412 */
413
ArrayList_LastIndexOf(wArrayList * arrayList,void * obj,int startIndex,int count)414 int ArrayList_LastIndexOf(wArrayList* arrayList, void* obj, int startIndex, int count)
415 {
416 int index;
417 BOOL found = FALSE;
418
419 if (arrayList->synchronized)
420 EnterCriticalSection(&arrayList->lock);
421
422 if (startIndex < 0)
423 startIndex = 0;
424
425 if (count < 0)
426 count = arrayList->size;
427
428 for (index = startIndex + count - 1; index >= startIndex; index--)
429 {
430 if (arrayList->object.fnObjectEquals(arrayList->array[index], obj))
431 {
432 found = TRUE;
433 break;
434 }
435 }
436
437 if (!found)
438 index = -1;
439
440 if (arrayList->synchronized)
441 LeaveCriticalSection(&arrayList->lock);
442
443 return index;
444 }
445
ArrayList_DefaultCompare(const void * objA,const void * objB)446 static BOOL ArrayList_DefaultCompare(const void* objA, const void* objB)
447 {
448 return objA == objB ? TRUE : FALSE;
449 }
450
451 /**
452 * Construction, Destruction
453 */
454
ArrayList_New(BOOL synchronized)455 wArrayList* ArrayList_New(BOOL synchronized)
456 {
457 wArrayList* arrayList = NULL;
458 arrayList = (wArrayList*)calloc(1, sizeof(wArrayList));
459
460 if (!arrayList)
461 return NULL;
462
463 arrayList->synchronized = synchronized;
464 arrayList->capacity = 32;
465 arrayList->growthFactor = 2;
466 arrayList->object.fnObjectEquals = ArrayList_DefaultCompare;
467 arrayList->array = (void**)calloc(arrayList->capacity, sizeof(void*));
468
469 if (!arrayList->array)
470 goto out_free;
471
472 InitializeCriticalSectionAndSpinCount(&arrayList->lock, 4000);
473 return arrayList;
474 out_free:
475 free(arrayList);
476 return NULL;
477 }
478
ArrayList_Free(wArrayList * arrayList)479 void ArrayList_Free(wArrayList* arrayList)
480 {
481 if (!arrayList)
482 return;
483
484 ArrayList_Clear(arrayList);
485 DeleteCriticalSection(&arrayList->lock);
486 free(arrayList->array);
487 free(arrayList);
488 }
489