| 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 |
|---|
Chromium Code Reviews
Issue 2078763002:
Delete bundled copy of NSS and replace with README. (Closed)
Base URL: https://chromium.googlesource.com/chromium/deps/nss@master