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