1 /**
2 * WinPR: Windows Portable Runtime
3 * System.Collections.Generic.LinkedList<T>
4 *
5 * Copyright 2013 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/collections.h>
25
26 typedef struct _wLinkedListItem wLinkedListNode;
27
28 struct _wLinkedListItem
29 {
30 void* value;
31 wLinkedListNode* prev;
32 wLinkedListNode* next;
33 };
34
35 struct _wLinkedList
36 {
37 int count;
38 int initial;
39 wLinkedListNode* head;
40 wLinkedListNode* tail;
41 wLinkedListNode* current;
42 wObject object;
43 };
44
45 /**
46 * C equivalent of the C# LinkedList<T> Class:
47 * http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx
48 *
49 * Internal implementation uses a doubly-linked list
50 */
51
52 /**
53 * Properties
54 */
55
56 /**
57 * Gets the number of nodes actually contained in the LinkedList.
58 */
59
LinkedList_Count(wLinkedList * list)60 int LinkedList_Count(wLinkedList* list)
61 {
62 return list->count;
63 }
64
65 /**
66 * Gets the first node of the LinkedList.
67 */
68
LinkedList_First(wLinkedList * list)69 void* LinkedList_First(wLinkedList* list)
70 {
71 if (list->head)
72 return list->head->value;
73 else
74 return NULL;
75 }
76
77 /**
78 * Gets the last node of the LinkedList.
79 */
80
LinkedList_Last(wLinkedList * list)81 void* LinkedList_Last(wLinkedList* list)
82 {
83 if (list->tail)
84 return list->tail->value;
85 else
86 return NULL;
87 }
88
89 /**
90 * Methods
91 */
92
93 /**
94 * Determines whether the LinkedList contains a specific value.
95 */
96
LinkedList_Contains(wLinkedList * list,void * value)97 BOOL LinkedList_Contains(wLinkedList* list, void* value)
98 {
99 wLinkedListNode* item;
100 OBJECT_EQUALS_FN keyEquals;
101
102 if (!list->head)
103 return FALSE;
104
105 item = list->head;
106 keyEquals = list->object.fnObjectEquals;
107
108 while (item)
109 {
110 if (keyEquals(item->value, value))
111 break;
112
113 item = item->next;
114 }
115
116 return (item) ? TRUE : FALSE;
117 }
118
LinkedList_FreeNode(wLinkedList * list,wLinkedListNode * node)119 static wLinkedListNode* LinkedList_FreeNode(wLinkedList* list, wLinkedListNode* node)
120 {
121 wLinkedListNode* next = node->next;
122 wLinkedListNode* prev = node->prev;
123
124 if (prev)
125 prev->next = next;
126
127 if (next)
128 next->prev = prev;
129
130 if (node == list->head)
131 list->head = node->next;
132
133 if (node == list->tail)
134 list->tail = node->prev;
135
136 if (list->object.fnObjectUninit)
137 list->object.fnObjectUninit(node);
138
139 if (list->object.fnObjectFree)
140 list->object.fnObjectFree(node);
141
142 free(node);
143 list->count--;
144 return next;
145 }
146
147 /**
148 * Removes all entries from the LinkedList.
149 */
150
LinkedList_Clear(wLinkedList * list)151 void LinkedList_Clear(wLinkedList* list)
152 {
153 wLinkedListNode* node;
154
155 if (!list->head)
156 return;
157
158 node = list->head;
159
160 while (node)
161 node = LinkedList_FreeNode(list, node);
162
163 list->head = list->tail = NULL;
164 list->count = 0;
165 }
166
LinkedList_Create(wLinkedList * list,void * value)167 static wLinkedListNode* LinkedList_Create(wLinkedList* list, void* value)
168 {
169 wLinkedListNode* node = (wLinkedListNode*)calloc(1, sizeof(wLinkedListNode));
170
171 if (!node)
172 return NULL;
173
174 if (list->object.fnObjectNew)
175 node->value = list->object.fnObjectNew(value);
176 else
177 node->value = value;
178
179 if (list->object.fnObjectInit)
180 list->object.fnObjectInit(node);
181
182 return node;
183 }
184 /**
185 * Adds a new node containing the specified value at the start of the LinkedList.
186 */
187
LinkedList_AddFirst(wLinkedList * list,void * value)188 BOOL LinkedList_AddFirst(wLinkedList* list, void* value)
189 {
190 wLinkedListNode* node = LinkedList_Create(list, value);
191
192 if (!node)
193 return FALSE;
194
195 if (!list->head)
196 {
197 list->tail = list->head = node;
198 }
199 else
200 {
201 list->head->prev = node;
202 node->next = list->head;
203 list->head = node;
204 }
205
206 list->count++;
207 return TRUE;
208 }
209
210 /**
211 * Adds a new node containing the specified value at the end of the LinkedList.
212 */
213
LinkedList_AddLast(wLinkedList * list,void * value)214 BOOL LinkedList_AddLast(wLinkedList* list, void* value)
215 {
216 wLinkedListNode* node = LinkedList_Create(list, value);
217
218 if (!node)
219 return FALSE;
220
221 if (!list->tail)
222 {
223 list->head = list->tail = node;
224 }
225 else
226 {
227 list->tail->next = node;
228 node->prev = list->tail;
229 list->tail = node;
230 }
231
232 list->count++;
233 return TRUE;
234 }
235
236 /**
237 * Removes the first occurrence of the specified value from the LinkedList.
238 */
239
LinkedList_Remove(wLinkedList * list,void * value)240 BOOL LinkedList_Remove(wLinkedList* list, void* value)
241 {
242 wLinkedListNode* node;
243 OBJECT_EQUALS_FN keyEquals;
244 keyEquals = list->object.fnObjectEquals;
245 node = list->head;
246
247 while (node)
248 {
249 if (keyEquals(node->value, value))
250 {
251 LinkedList_FreeNode(list, node);
252 return TRUE;
253 }
254
255 node = node->next;
256 }
257
258 return FALSE;
259 }
260
261 /**
262 * Removes the node at the start of the LinkedList.
263 */
264
LinkedList_RemoveFirst(wLinkedList * list)265 void LinkedList_RemoveFirst(wLinkedList* list)
266 {
267 if (list->head)
268 LinkedList_FreeNode(list, list->head);
269 }
270
271 /**
272 * Removes the node at the end of the LinkedList.
273 */
274
LinkedList_RemoveLast(wLinkedList * list)275 void LinkedList_RemoveLast(wLinkedList* list)
276 {
277 if (list->tail)
278 LinkedList_FreeNode(list, list->tail);
279 }
280
281 /**
282 * Sets the enumerator to its initial position, which is before the first element in the collection.
283 */
284
LinkedList_Enumerator_Reset(wLinkedList * list)285 void LinkedList_Enumerator_Reset(wLinkedList* list)
286 {
287 list->initial = 1;
288 list->current = list->head;
289 }
290
291 /*
292 * Gets the element at the current position of the enumerator.
293 */
294
LinkedList_Enumerator_Current(wLinkedList * list)295 void* LinkedList_Enumerator_Current(wLinkedList* list)
296 {
297 if (list->initial)
298 return NULL;
299
300 if (list->current)
301 return list->current->value;
302 else
303 return NULL;
304 }
305
306 /*
307 * Advances the enumerator to the next element of the LinkedList.
308 */
309
LinkedList_Enumerator_MoveNext(wLinkedList * list)310 BOOL LinkedList_Enumerator_MoveNext(wLinkedList* list)
311 {
312 if (list->initial)
313 list->initial = 0;
314 else if (list->current)
315 list->current = list->current->next;
316
317 if (!list->current)
318 return FALSE;
319
320 return TRUE;
321 }
322
default_equal_function(const void * objA,const void * objB)323 static BOOL default_equal_function(const void* objA, const void* objB)
324 {
325 return objA == objB;
326 }
327
328 /**
329 * Construction, Destruction
330 */
331
LinkedList_New(void)332 wLinkedList* LinkedList_New(void)
333 {
334 wLinkedList* list = NULL;
335 list = (wLinkedList*)calloc(1, sizeof(wLinkedList));
336
337 if (list)
338 {
339 list->object.fnObjectEquals = default_equal_function;
340 }
341
342 return list;
343 }
344
LinkedList_Free(wLinkedList * list)345 void LinkedList_Free(wLinkedList* list)
346 {
347 if (list)
348 {
349 LinkedList_Clear(list);
350 free(list);
351 }
352 }
353
LinkedList_Object(wLinkedList * list)354 wObject* LinkedList_Object(wLinkedList* list)
355 {
356 if (!list)
357 return NULL;
358
359 return &list->object;
360 }
361