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