security/nss/lib/base/list.c

Thu, 22 Jan 2015 13:21:57 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Thu, 22 Jan 2015 13:21:57 +0100
branch
TOR_BUG_9701
changeset 15
b8a032363ba2
permissions
-rw-r--r--

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

mercurial