1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/base/list.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,401 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +/*
1.9 + * list.c
1.10 + *
1.11 + * This contains the implementation of NSS's thread-safe linked list.
1.12 + */
1.13 +
1.14 +#ifndef BASE_H
1.15 +#include "base.h"
1.16 +#endif /* BASE_H */
1.17 +
1.18 +struct nssListElementStr {
1.19 + PRCList link;
1.20 + void *data;
1.21 +};
1.22 +
1.23 +typedef struct nssListElementStr nssListElement;
1.24 +
1.25 +struct nssListStr {
1.26 + NSSArena *arena;
1.27 + PZLock *lock;
1.28 + nssListElement *head;
1.29 + PRUint32 count;
1.30 + nssListCompareFunc compareFunc;
1.31 + nssListSortFunc sortFunc;
1.32 + PRBool i_alloced_arena;
1.33 +};
1.34 +
1.35 +struct nssListIteratorStr {
1.36 + PZLock *lock;
1.37 + nssList *list;
1.38 + nssListElement *current;
1.39 +};
1.40 +
1.41 +#define NSSLIST_LOCK_IF(list) \
1.42 + if ((list)->lock) PZ_Lock((list)->lock)
1.43 +
1.44 +#define NSSLIST_UNLOCK_IF(list) \
1.45 + if ((list)->lock) PZ_Unlock((list)->lock)
1.46 +
1.47 +static PRBool
1.48 +pointer_compare(void *a, void *b)
1.49 +{
1.50 + return (PRBool)(a == b);
1.51 +}
1.52 +
1.53 +static nssListElement *
1.54 +nsslist_get_matching_element(nssList *list, void *data)
1.55 +{
1.56 + PRCList *link;
1.57 + nssListElement *node;
1.58 + node = list->head;
1.59 + if (!node) {
1.60 + return NULL;
1.61 + }
1.62 + link = &node->link;
1.63 + while (node) {
1.64 + /* using a callback slows things down when it's just compare ... */
1.65 + if (list->compareFunc(node->data, data)) {
1.66 + break;
1.67 + }
1.68 + link = &node->link;
1.69 + if (link == PR_LIST_TAIL(&list->head->link)) {
1.70 + node = NULL;
1.71 + break;
1.72 + }
1.73 + node = (nssListElement *)PR_NEXT_LINK(&node->link);
1.74 + }
1.75 + return node;
1.76 +}
1.77 +
1.78 +NSS_IMPLEMENT nssList *
1.79 +nssList_Create
1.80 +(
1.81 + NSSArena *arenaOpt,
1.82 + PRBool threadSafe
1.83 +)
1.84 +{
1.85 + NSSArena *arena;
1.86 + nssList *list;
1.87 + PRBool i_alloced;
1.88 + if (arenaOpt) {
1.89 + arena = arenaOpt;
1.90 + i_alloced = PR_FALSE;
1.91 + } else {
1.92 + arena = nssArena_Create();
1.93 + i_alloced = PR_TRUE;
1.94 + }
1.95 + if (!arena) {
1.96 + return (nssList *)NULL;
1.97 + }
1.98 + list = nss_ZNEW(arena, nssList);
1.99 + if (!list) {
1.100 + if (!arenaOpt) {
1.101 + NSSArena_Destroy(arena);
1.102 + }
1.103 + return (nssList *)NULL;
1.104 + }
1.105 + if (threadSafe) {
1.106 + list->lock = PZ_NewLock(nssILockOther);
1.107 + if (!list->lock) {
1.108 + if (arenaOpt) {
1.109 + nss_ZFreeIf(list);
1.110 + } else {
1.111 + NSSArena_Destroy(arena);
1.112 + }
1.113 + return (nssList *)NULL;
1.114 + }
1.115 + }
1.116 + list->arena = arena;
1.117 + list->i_alloced_arena = i_alloced;
1.118 + list->compareFunc = pointer_compare;
1.119 + return list;
1.120 +}
1.121 +
1.122 +NSS_IMPLEMENT PRStatus
1.123 +nssList_Destroy(nssList *list)
1.124 +{
1.125 + if (!list->i_alloced_arena) {
1.126 + nssList_Clear(list, NULL);
1.127 + }
1.128 + if (list->lock) {
1.129 + (void)PZ_DestroyLock(list->lock);
1.130 + }
1.131 + if (list->i_alloced_arena) {
1.132 + NSSArena_Destroy(list->arena);
1.133 + list = NULL;
1.134 + }
1.135 + nss_ZFreeIf(list);
1.136 + return PR_SUCCESS;
1.137 +}
1.138 +
1.139 +NSS_IMPLEMENT void
1.140 +nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc)
1.141 +{
1.142 + list->compareFunc = compareFunc;
1.143 +}
1.144 +
1.145 +NSS_IMPLEMENT void
1.146 +nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
1.147 +{
1.148 + /* XXX if list already has elements, sort them */
1.149 + list->sortFunc = sortFunc;
1.150 +}
1.151 +
1.152 +NSS_IMPLEMENT nssListCompareFunc
1.153 +nssList_GetCompareFunction(nssList *list)
1.154 +{
1.155 + return list->compareFunc;
1.156 +}
1.157 +
1.158 +NSS_IMPLEMENT void
1.159 +nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
1.160 +{
1.161 + PRCList *link;
1.162 + nssListElement *node, *tmp;
1.163 + NSSLIST_LOCK_IF(list);
1.164 + node = list->head;
1.165 + list->head = NULL;
1.166 + while (node && list->count > 0) {
1.167 + if (destructor) (*destructor)(node->data);
1.168 + link = &node->link;
1.169 + tmp = (nssListElement *)PR_NEXT_LINK(link);
1.170 + PR_REMOVE_LINK(link);
1.171 + nss_ZFreeIf(node);
1.172 + node = tmp;
1.173 + --list->count;
1.174 + }
1.175 + NSSLIST_UNLOCK_IF(list);
1.176 +}
1.177 +
1.178 +static PRStatus
1.179 +nsslist_add_element(nssList *list, void *data)
1.180 +{
1.181 + nssListElement *node = nss_ZNEW(list->arena, nssListElement);
1.182 + if (!node) {
1.183 + return PR_FAILURE;
1.184 + }
1.185 + PR_INIT_CLIST(&node->link);
1.186 + node->data = data;
1.187 + if (list->head) {
1.188 + if (list->sortFunc) {
1.189 + PRCList *link;
1.190 + nssListElement *currNode;
1.191 + currNode = list->head;
1.192 + /* insert in ordered list */
1.193 + while (currNode) {
1.194 + link = &currNode->link;
1.195 + if (list->sortFunc(data, currNode->data) <= 0) {
1.196 + /* new element goes before current node */
1.197 + PR_INSERT_BEFORE(&node->link, link);
1.198 + /* reset head if this is first */
1.199 + if (currNode == list->head) list->head = node;
1.200 + break;
1.201 + }
1.202 + if (link == PR_LIST_TAIL(&list->head->link)) {
1.203 + /* reached end of list, append */
1.204 + PR_INSERT_AFTER(&node->link, link);
1.205 + break;
1.206 + }
1.207 + currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
1.208 + }
1.209 + } else {
1.210 + /* not sorting */
1.211 + PR_APPEND_LINK(&node->link, &list->head->link);
1.212 + }
1.213 + } else {
1.214 + list->head = node;
1.215 + }
1.216 + ++list->count;
1.217 + return PR_SUCCESS;
1.218 +}
1.219 +
1.220 +NSS_IMPLEMENT PRStatus
1.221 +nssList_Add(nssList *list, void *data)
1.222 +{
1.223 + PRStatus nssrv;
1.224 + NSSLIST_LOCK_IF(list);
1.225 + nssrv = nsslist_add_element(list, data);
1.226 + NSSLIST_UNLOCK_IF(list);
1.227 + return PR_SUCCESS;
1.228 +}
1.229 +
1.230 +NSS_IMPLEMENT PRStatus
1.231 +nssList_AddUnique(nssList *list, void *data)
1.232 +{
1.233 + PRStatus nssrv;
1.234 + nssListElement *node;
1.235 + NSSLIST_LOCK_IF(list);
1.236 + node = nsslist_get_matching_element(list, data);
1.237 + if (node) {
1.238 + /* already in, finish */
1.239 + NSSLIST_UNLOCK_IF(list);
1.240 + return PR_SUCCESS;
1.241 + }
1.242 + nssrv = nsslist_add_element(list, data);
1.243 + NSSLIST_UNLOCK_IF(list);
1.244 + return nssrv;
1.245 +}
1.246 +
1.247 +NSS_IMPLEMENT PRStatus
1.248 +nssList_Remove(nssList *list, void *data)
1.249 +{
1.250 + nssListElement *node;
1.251 + NSSLIST_LOCK_IF(list);
1.252 + node = nsslist_get_matching_element(list, data);
1.253 + if (node) {
1.254 + if (node == list->head) {
1.255 + list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
1.256 + }
1.257 + PR_REMOVE_LINK(&node->link);
1.258 + nss_ZFreeIf(node);
1.259 + if (--list->count == 0) {
1.260 + list->head = NULL;
1.261 + }
1.262 + }
1.263 + NSSLIST_UNLOCK_IF(list);
1.264 + return PR_SUCCESS;
1.265 +}
1.266 +
1.267 +NSS_IMPLEMENT void *
1.268 +nssList_Get(nssList *list, void *data)
1.269 +{
1.270 + nssListElement *node;
1.271 + NSSLIST_LOCK_IF(list);
1.272 + node = nsslist_get_matching_element(list, data);
1.273 + NSSLIST_UNLOCK_IF(list);
1.274 + return (node) ? node->data : NULL;
1.275 +}
1.276 +
1.277 +NSS_IMPLEMENT PRUint32
1.278 +nssList_Count(nssList *list)
1.279 +{
1.280 + return list->count;
1.281 +}
1.282 +
1.283 +NSS_IMPLEMENT PRStatus
1.284 +nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)
1.285 +{
1.286 + nssListElement *node;
1.287 + PRUint32 i = 0;
1.288 + PR_ASSERT(maxElements > 0);
1.289 + node = list->head;
1.290 + if (!node) {
1.291 + return PR_SUCCESS;
1.292 + }
1.293 + NSSLIST_LOCK_IF(list);
1.294 + while (node) {
1.295 + rvArray[i++] = node->data;
1.296 + if (i == maxElements) break;
1.297 + node = (nssListElement *)PR_NEXT_LINK(&node->link);
1.298 + if (node == list->head) {
1.299 + break;
1.300 + }
1.301 + }
1.302 + NSSLIST_UNLOCK_IF(list);
1.303 + return PR_SUCCESS;
1.304 +}
1.305 +
1.306 +NSS_IMPLEMENT nssList *
1.307 +nssList_Clone(nssList *list)
1.308 +{
1.309 + nssList *rvList;
1.310 + nssListElement *node;
1.311 + rvList = nssList_Create(NULL, (list->lock != NULL));
1.312 + if (!rvList) {
1.313 + return NULL;
1.314 + }
1.315 + NSSLIST_LOCK_IF(list);
1.316 + if (list->count > 0) {
1.317 + node = list->head;
1.318 + while (PR_TRUE) {
1.319 + nssList_Add(rvList, node->data);
1.320 + node = (nssListElement *)PR_NEXT_LINK(&node->link);
1.321 + if (node == list->head) {
1.322 + break;
1.323 + }
1.324 + }
1.325 + }
1.326 + NSSLIST_UNLOCK_IF(list);
1.327 + return rvList;
1.328 +}
1.329 +
1.330 +NSS_IMPLEMENT nssListIterator *
1.331 +nssList_CreateIterator(nssList *list)
1.332 +{
1.333 + nssListIterator *rvIterator;
1.334 + rvIterator = nss_ZNEW(NULL, nssListIterator);
1.335 + if (!rvIterator) {
1.336 + return NULL;
1.337 + }
1.338 + rvIterator->list = nssList_Clone(list);
1.339 + if (!rvIterator->list) {
1.340 + nss_ZFreeIf(rvIterator);
1.341 + return NULL;
1.342 + }
1.343 + rvIterator->current = rvIterator->list->head;
1.344 + if (list->lock) {
1.345 + rvIterator->lock = PZ_NewLock(nssILockOther);
1.346 + if (!rvIterator->lock) {
1.347 + nssList_Destroy(rvIterator->list);
1.348 + nss_ZFreeIf(rvIterator);
1.349 + rvIterator = NULL;
1.350 + }
1.351 + }
1.352 + return rvIterator;
1.353 +}
1.354 +
1.355 +NSS_IMPLEMENT void
1.356 +nssListIterator_Destroy(nssListIterator *iter)
1.357 +{
1.358 + if (iter->lock) {
1.359 + (void)PZ_DestroyLock(iter->lock);
1.360 + }
1.361 + nssList_Destroy(iter->list);
1.362 + nss_ZFreeIf(iter);
1.363 +}
1.364 +
1.365 +NSS_IMPLEMENT void *
1.366 +nssListIterator_Start(nssListIterator *iter)
1.367 +{
1.368 + NSSLIST_LOCK_IF(iter);
1.369 + if (iter->list->count == 0) {
1.370 + return NULL;
1.371 + }
1.372 + iter->current = iter->list->head;
1.373 + return iter->current->data;
1.374 +}
1.375 +
1.376 +NSS_IMPLEMENT void *
1.377 +nssListIterator_Next(nssListIterator *iter)
1.378 +{
1.379 + nssListElement *node;
1.380 + PRCList *link;
1.381 + if (iter->list->count == 1 || iter->current == NULL) {
1.382 + /* Reached the end of the list. Don't change the state, force to
1.383 + * user to call nssList_Finish to clean up.
1.384 + */
1.385 + return NULL;
1.386 + }
1.387 + node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
1.388 + link = &node->link;
1.389 + if (link == PR_LIST_TAIL(&iter->list->head->link)) {
1.390 + /* Signal the end of the list. */
1.391 + iter->current = NULL;
1.392 + return node->data;
1.393 + }
1.394 + iter->current = node;
1.395 + return node->data;
1.396 +}
1.397 +
1.398 +NSS_IMPLEMENT PRStatus
1.399 +nssListIterator_Finish(nssListIterator *iter)
1.400 +{
1.401 + iter->current = iter->list->head;
1.402 + return (iter->lock) ? PZ_Unlock(iter->lock) : PR_SUCCESS;
1.403 +}
1.404 +
