OLD | NEW |
| (Empty) |
1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
2 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
4 | |
5 /* | |
6 * list.c | |
7 * | |
8 * This contains the implementation of NSS's thread-safe linked list. | |
9 */ | |
10 | |
11 #ifndef BASE_H | |
12 #include "base.h" | |
13 #endif /* BASE_H */ | |
14 | |
15 struct nssListElementStr { | |
16 PRCList link; | |
17 void *data; | |
18 }; | |
19 | |
20 typedef struct nssListElementStr nssListElement; | |
21 | |
22 struct nssListStr { | |
23 NSSArena *arena; | |
24 PZLock *lock; | |
25 nssListElement *head; | |
26 PRUint32 count; | |
27 nssListCompareFunc compareFunc; | |
28 nssListSortFunc sortFunc; | |
29 PRBool i_alloced_arena; | |
30 }; | |
31 | |
32 struct nssListIteratorStr { | |
33 PZLock *lock; | |
34 nssList *list; | |
35 nssListElement *current; | |
36 }; | |
37 | |
38 #define NSSLIST_LOCK_IF(list) \ | |
39 if ((list)->lock) \ | |
40 PZ_Lock((list)->lock) | |
41 | |
42 #define NSSLIST_UNLOCK_IF(list) \ | |
43 if ((list)->lock) \ | |
44 PZ_Unlock((list)->lock) | |
45 | |
46 static PRBool | |
47 pointer_compare(void *a, void *b) | |
48 { | |
49 return (PRBool)(a == b); | |
50 } | |
51 | |
52 static nssListElement * | |
53 nsslist_get_matching_element(nssList *list, void *data) | |
54 { | |
55 PRCList *link; | |
56 nssListElement *node; | |
57 node = list->head; | |
58 if (!node) { | |
59 return NULL; | |
60 } | |
61 link = &node->link; | |
62 while (node) { | |
63 /* using a callback slows things down when it's just compare ... */ | |
64 if (list->compareFunc(node->data, data)) { | |
65 break; | |
66 } | |
67 link = &node->link; | |
68 if (link == PR_LIST_TAIL(&list->head->link)) { | |
69 node = NULL; | |
70 break; | |
71 } | |
72 node = (nssListElement *)PR_NEXT_LINK(&node->link); | |
73 } | |
74 return node; | |
75 } | |
76 | |
77 NSS_IMPLEMENT nssList * | |
78 nssList_Create(NSSArena *arenaOpt, PRBool threadSafe) | |
79 { | |
80 NSSArena *arena; | |
81 nssList *list; | |
82 PRBool i_alloced; | |
83 if (arenaOpt) { | |
84 arena = arenaOpt; | |
85 i_alloced = PR_FALSE; | |
86 } else { | |
87 arena = nssArena_Create(); | |
88 i_alloced = PR_TRUE; | |
89 } | |
90 if (!arena) { | |
91 return (nssList *)NULL; | |
92 } | |
93 list = nss_ZNEW(arena, nssList); | |
94 if (!list) { | |
95 if (!arenaOpt) { | |
96 NSSArena_Destroy(arena); | |
97 } | |
98 return (nssList *)NULL; | |
99 } | |
100 if (threadSafe) { | |
101 list->lock = PZ_NewLock(nssILockOther); | |
102 if (!list->lock) { | |
103 if (arenaOpt) { | |
104 nss_ZFreeIf(list); | |
105 } else { | |
106 NSSArena_Destroy(arena); | |
107 } | |
108 return (nssList *)NULL; | |
109 } | |
110 } | |
111 list->arena = arena; | |
112 list->i_alloced_arena = i_alloced; | |
113 list->compareFunc = pointer_compare; | |
114 return list; | |
115 } | |
116 | |
117 NSS_IMPLEMENT PRStatus | |
118 nssList_Destroy(nssList *list) | |
119 { | |
120 if (!list->i_alloced_arena) { | |
121 nssList_Clear(list, NULL); | |
122 } | |
123 if (list->lock) { | |
124 (void)PZ_DestroyLock(list->lock); | |
125 } | |
126 if (list->i_alloced_arena) { | |
127 NSSArena_Destroy(list->arena); | |
128 list = NULL; | |
129 } | |
130 nss_ZFreeIf(list); | |
131 return PR_SUCCESS; | |
132 } | |
133 | |
134 NSS_IMPLEMENT void | |
135 nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc) | |
136 { | |
137 list->compareFunc = compareFunc; | |
138 } | |
139 | |
140 NSS_IMPLEMENT void | |
141 nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc) | |
142 { | |
143 /* XXX if list already has elements, sort them */ | |
144 list->sortFunc = sortFunc; | |
145 } | |
146 | |
147 NSS_IMPLEMENT nssListCompareFunc | |
148 nssList_GetCompareFunction(nssList *list) | |
149 { | |
150 return list->compareFunc; | |
151 } | |
152 | |
153 NSS_IMPLEMENT void | |
154 nssList_Clear(nssList *list, nssListElementDestructorFunc destructor) | |
155 { | |
156 PRCList *link; | |
157 nssListElement *node, *tmp; | |
158 NSSLIST_LOCK_IF(list); | |
159 node = list->head; | |
160 list->head = NULL; | |
161 while (node && list->count > 0) { | |
162 if (destructor) | |
163 (*destructor)(node->data); | |
164 link = &node->link; | |
165 tmp = (nssListElement *)PR_NEXT_LINK(link); | |
166 PR_REMOVE_LINK(link); | |
167 nss_ZFreeIf(node); | |
168 node = tmp; | |
169 --list->count; | |
170 } | |
171 NSSLIST_UNLOCK_IF(list); | |
172 } | |
173 | |
174 static PRStatus | |
175 nsslist_add_element(nssList *list, void *data) | |
176 { | |
177 nssListElement *node = nss_ZNEW(list->arena, nssListElement); | |
178 if (!node) { | |
179 return PR_FAILURE; | |
180 } | |
181 PR_INIT_CLIST(&node->link); | |
182 node->data = data; | |
183 if (list->head) { | |
184 if (list->sortFunc) { | |
185 PRCList *link; | |
186 nssListElement *currNode; | |
187 currNode = list->head; | |
188 /* insert in ordered list */ | |
189 while (currNode) { | |
190 link = &currNode->link; | |
191 if (list->sortFunc(data, currNode->data) <= 0) { | |
192 /* new element goes before current node */ | |
193 PR_INSERT_BEFORE(&node->link, link); | |
194 /* reset head if this is first */ | |
195 if (currNode == list->head) | |
196 list->head = node; | |
197 break; | |
198 } | |
199 if (link == PR_LIST_TAIL(&list->head->link)) { | |
200 /* reached end of list, append */ | |
201 PR_INSERT_AFTER(&node->link, link); | |
202 break; | |
203 } | |
204 currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link); | |
205 } | |
206 } else { | |
207 /* not sorting */ | |
208 PR_APPEND_LINK(&node->link, &list->head->link); | |
209 } | |
210 } else { | |
211 list->head = node; | |
212 } | |
213 ++list->count; | |
214 return PR_SUCCESS; | |
215 } | |
216 | |
217 NSS_IMPLEMENT PRStatus | |
218 nssList_Add(nssList *list, void *data) | |
219 { | |
220 NSSLIST_LOCK_IF(list); | |
221 (void)nsslist_add_element(list, data); | |
222 NSSLIST_UNLOCK_IF(list); | |
223 return PR_SUCCESS; | |
224 } | |
225 | |
226 NSS_IMPLEMENT PRStatus | |
227 nssList_AddUnique(nssList *list, void *data) | |
228 { | |
229 PRStatus nssrv; | |
230 nssListElement *node; | |
231 NSSLIST_LOCK_IF(list); | |
232 node = nsslist_get_matching_element(list, data); | |
233 if (node) { | |
234 /* already in, finish */ | |
235 NSSLIST_UNLOCK_IF(list); | |
236 return PR_SUCCESS; | |
237 } | |
238 nssrv = nsslist_add_element(list, data); | |
239 NSSLIST_UNLOCK_IF(list); | |
240 return nssrv; | |
241 } | |
242 | |
243 NSS_IMPLEMENT PRStatus | |
244 nssList_Remove(nssList *list, void *data) | |
245 { | |
246 nssListElement *node; | |
247 NSSLIST_LOCK_IF(list); | |
248 node = nsslist_get_matching_element(list, data); | |
249 if (node) { | |
250 if (node == list->head) { | |
251 list->head = (nssListElement *)PR_NEXT_LINK(&node->link); | |
252 } | |
253 PR_REMOVE_LINK(&node->link); | |
254 nss_ZFreeIf(node); | |
255 if (--list->count == 0) { | |
256 list->head = NULL; | |
257 } | |
258 } | |
259 NSSLIST_UNLOCK_IF(list); | |
260 return PR_SUCCESS; | |
261 } | |
262 | |
263 NSS_IMPLEMENT void * | |
264 nssList_Get(nssList *list, void *data) | |
265 { | |
266 nssListElement *node; | |
267 NSSLIST_LOCK_IF(list); | |
268 node = nsslist_get_matching_element(list, data); | |
269 NSSLIST_UNLOCK_IF(list); | |
270 return (node) ? node->data : NULL; | |
271 } | |
272 | |
273 NSS_IMPLEMENT PRUint32 | |
274 nssList_Count(nssList *list) | |
275 { | |
276 return list->count; | |
277 } | |
278 | |
279 NSS_IMPLEMENT PRStatus | |
280 nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements) | |
281 { | |
282 nssListElement *node; | |
283 PRUint32 i = 0; | |
284 PR_ASSERT(maxElements > 0); | |
285 node = list->head; | |
286 if (!node) { | |
287 return PR_SUCCESS; | |
288 } | |
289 NSSLIST_LOCK_IF(list); | |
290 while (node) { | |
291 rvArray[i++] = node->data; | |
292 if (i == maxElements) | |
293 break; | |
294 node = (nssListElement *)PR_NEXT_LINK(&node->link); | |
295 if (node == list->head) { | |
296 break; | |
297 } | |
298 } | |
299 NSSLIST_UNLOCK_IF(list); | |
300 return PR_SUCCESS; | |
301 } | |
302 | |
303 NSS_IMPLEMENT nssList * | |
304 nssList_Clone(nssList *list) | |
305 { | |
306 nssList *rvList; | |
307 nssListElement *node; | |
308 rvList = nssList_Create(NULL, (list->lock != NULL)); | |
309 if (!rvList) { | |
310 return NULL; | |
311 } | |
312 NSSLIST_LOCK_IF(list); | |
313 if (list->count > 0) { | |
314 node = list->head; | |
315 while (PR_TRUE) { | |
316 nssList_Add(rvList, node->data); | |
317 node = (nssListElement *)PR_NEXT_LINK(&node->link); | |
318 if (node == list->head) { | |
319 break; | |
320 } | |
321 } | |
322 } | |
323 NSSLIST_UNLOCK_IF(list); | |
324 return rvList; | |
325 } | |
326 | |
327 NSS_IMPLEMENT nssListIterator * | |
328 nssList_CreateIterator(nssList *list) | |
329 { | |
330 nssListIterator *rvIterator; | |
331 rvIterator = nss_ZNEW(NULL, nssListIterator); | |
332 if (!rvIterator) { | |
333 return NULL; | |
334 } | |
335 rvIterator->list = nssList_Clone(list); | |
336 if (!rvIterator->list) { | |
337 nss_ZFreeIf(rvIterator); | |
338 return NULL; | |
339 } | |
340 rvIterator->current = rvIterator->list->head; | |
341 if (list->lock) { | |
342 rvIterator->lock = PZ_NewLock(nssILockOther); | |
343 if (!rvIterator->lock) { | |
344 nssList_Destroy(rvIterator->list); | |
345 nss_ZFreeIf(rvIterator); | |
346 rvIterator = NULL; | |
347 } | |
348 } | |
349 return rvIterator; | |
350 } | |
351 | |
352 NSS_IMPLEMENT void | |
353 nssListIterator_Destroy(nssListIterator *iter) | |
354 { | |
355 if (iter->lock) { | |
356 (void)PZ_DestroyLock(iter->lock); | |
357 } | |
358 nssList_Destroy(iter->list); | |
359 nss_ZFreeIf(iter); | |
360 } | |
361 | |
362 NSS_IMPLEMENT void * | |
363 nssListIterator_Start(nssListIterator *iter) | |
364 { | |
365 NSSLIST_LOCK_IF(iter); | |
366 if (iter->list->count == 0) { | |
367 return NULL; | |
368 } | |
369 iter->current = iter->list->head; | |
370 return iter->current->data; | |
371 } | |
372 | |
373 NSS_IMPLEMENT void * | |
374 nssListIterator_Next(nssListIterator *iter) | |
375 { | |
376 nssListElement *node; | |
377 PRCList *link; | |
378 if (iter->list->count == 1 || iter->current == NULL) { | |
379 /* Reached the end of the list. Don't change the state, force to | |
380 * user to call nssList_Finish to clean up. | |
381 */ | |
382 return NULL; | |
383 } | |
384 node = (nssListElement *)PR_NEXT_LINK(&iter->current->link); | |
385 link = &node->link; | |
386 if (link == PR_LIST_TAIL(&iter->list->head->link)) { | |
387 /* Signal the end of the list. */ | |
388 iter->current = NULL; | |
389 return node->data; | |
390 } | |
391 iter->current = node; | |
392 return node->data; | |
393 } | |
394 | |
395 NSS_IMPLEMENT PRStatus | |
396 nssListIterator_Finish(nssListIterator *iter) | |
397 { | |
398 iter->current = iter->list->head; | |
399 return (iter->lock) ? PZ_Unlock(iter->lock) : PR_SUCCESS; | |
400 } | |
OLD | NEW |