The Tor Browser: security/nss/lib/base/list.c@b8a032363ba2

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     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/. */

     5 /*

     6  * list.c

     7  *

     8  * This contains the implementation of NSS's thread-safe linked list.

     9  */

    11 #ifndef BASE_H

    12 #include "base.h"

    13 #endif /* BASE_H */

    15 struct nssListElementStr {

    16     PRCList  link;

    17     void    *data;

    18 };

    20 typedef struct nssListElementStr nssListElement;

    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 };

    32 struct nssListIteratorStr {

    33     PZLock *lock;

    34     nssList *list;

    35     nssListElement *current;

    36 };

    38 #define NSSLIST_LOCK_IF(list) \

    39     if ((list)->lock) PZ_Lock((list)->lock)

    41 #define NSSLIST_UNLOCK_IF(list) \

    42     if ((list)->lock) PZ_Unlock((list)->lock)

    44 static PRBool

    45 pointer_compare(void *a, void *b)

    46 {

    47     return (PRBool)(a == b);

    48 }

    50 static nssListElement *

    51 nsslist_get_matching_element(nssList *list, void *data)

    52 {

    53     PRCList *link;

    54     nssListElement *node;

    55     node = list->head;

    56     if (!node) {

    57 	return NULL;

    58     }

    59     link = &node->link;

    60     while (node) {

    61 	/* using a callback slows things down when it's just compare ... */

    62 	if (list->compareFunc(node->data, data)) {

    63 	    break;

    64 	}

    65 	link = &node->link;

    66 	if (link == PR_LIST_TAIL(&list->head->link)) {

    67 	    node = NULL;

    68 	    break;

    69 	}

    70 	node = (nssListElement *)PR_NEXT_LINK(&node->link);

    71     }

    72     return node;

    73 }

    75 NSS_IMPLEMENT nssList *

    76 nssList_Create

    77 (

    78   NSSArena *arenaOpt,

    79   PRBool threadSafe

    80 )

    81 {

    82     NSSArena *arena;

    83     nssList *list;

    84     PRBool i_alloced;

    85     if (arenaOpt) {

    86 	arena = arenaOpt;

    87 	i_alloced = PR_FALSE;

    88     } else {

    89 	arena = nssArena_Create();

    90 	i_alloced = PR_TRUE;

    91     }

    92     if (!arena) {

    93 	return (nssList *)NULL;

    94     }

    95     list = nss_ZNEW(arena, nssList);

    96     if (!list) {

    97 	if (!arenaOpt) {

    98 	    NSSArena_Destroy(arena);

    99 	}

   100 	return (nssList *)NULL;

   101     }

   102     if (threadSafe) {

   103 	list->lock = PZ_NewLock(nssILockOther);

   104 	if (!list->lock) {

   105 	    if (arenaOpt) {

   106 		nss_ZFreeIf(list);

   107 	    } else {

   108 		NSSArena_Destroy(arena);

   109 	    }

   110 	    return (nssList *)NULL;

   111 	}

   112     }

   113     list->arena = arena;

   114     list->i_alloced_arena = i_alloced;

   115     list->compareFunc = pointer_compare;

   116     return list;

   117 }

   119 NSS_IMPLEMENT PRStatus

   120 nssList_Destroy(nssList *list)

   121 {

   122     if (!list->i_alloced_arena) {

   123 	nssList_Clear(list, NULL);

   124     }

   125     if (list->lock) {

   126 	(void)PZ_DestroyLock(list->lock);

   127     }

   128     if (list->i_alloced_arena) {

   129 	NSSArena_Destroy(list->arena);

   130 	list = NULL;

   131     }

   132     nss_ZFreeIf(list);

   133     return PR_SUCCESS;

   134 }

   136 NSS_IMPLEMENT void

   137 nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc)

   138 {

   139     list->compareFunc = compareFunc;

   140 }

   142 NSS_IMPLEMENT void

   143 nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)

   144 {

   145     /* XXX if list already has elements, sort them */

   146     list->sortFunc = sortFunc;

   147 }

   149 NSS_IMPLEMENT nssListCompareFunc

   150 nssList_GetCompareFunction(nssList *list)

   151 {

   152     return list->compareFunc;

   153 }

   155 NSS_IMPLEMENT void

   156 nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)

   157 {

   158     PRCList *link;

   159     nssListElement *node, *tmp;

   160     NSSLIST_LOCK_IF(list);

   161     node = list->head;

   162     list->head = NULL;

   163     while (node && list->count > 0) {

   164 	if (destructor) (*destructor)(node->data);

   165 	link = &node->link;

   166 	tmp = (nssListElement *)PR_NEXT_LINK(link);

   167 	PR_REMOVE_LINK(link);

   168 	nss_ZFreeIf(node);

   169 	node = tmp;

   170 	--list->count;

   171     }

   172     NSSLIST_UNLOCK_IF(list);

   173 }

   175 static PRStatus

   176 nsslist_add_element(nssList *list, void *data)

   177 {

   178     nssListElement *node = nss_ZNEW(list->arena, nssListElement);

   179     if (!node) {

   180 	return PR_FAILURE;

   181     }

   182     PR_INIT_CLIST(&node->link);

   183     node->data = data;

   184     if (list->head) {

   185 	if (list->sortFunc) {

   186 	    PRCList *link;

   187 	    nssListElement *currNode;

   188 	    currNode = list->head;

   189 	    /* insert in ordered list */

   190 	    while (currNode) {

   191 		link = &currNode->link;

   192 		if (list->sortFunc(data, currNode->data) <= 0) {

   193 		    /* new element goes before current node */

   194 		    PR_INSERT_BEFORE(&node->link, link);

   195 		    /* reset head if this is first */

   196 		    if (currNode == list->head) 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 }

   217 NSS_IMPLEMENT PRStatus

   218 nssList_Add(nssList *list, void *data)

   219 {

   220     PRStatus nssrv;

   221     NSSLIST_LOCK_IF(list);

   222     nssrv = nsslist_add_element(list, data);

   223     NSSLIST_UNLOCK_IF(list);

   224     return PR_SUCCESS;

   225 }

   227 NSS_IMPLEMENT PRStatus

   228 nssList_AddUnique(nssList *list, void *data)

   229 {

   230     PRStatus nssrv;

   231     nssListElement *node;

   232     NSSLIST_LOCK_IF(list);

   233     node = nsslist_get_matching_element(list, data);

   234     if (node) {

   235 	/* already in, finish */

   236 	NSSLIST_UNLOCK_IF(list);

   237 	return PR_SUCCESS;

   238     }

   239     nssrv = nsslist_add_element(list, data);

   240     NSSLIST_UNLOCK_IF(list);

   241     return nssrv;

   242 }

   244 NSS_IMPLEMENT PRStatus

   245 nssList_Remove(nssList *list, void *data)

   246 {

   247     nssListElement *node;

   248     NSSLIST_LOCK_IF(list);

   249     node = nsslist_get_matching_element(list, data);

   250     if (node) {

   251 	if (node == list->head) {

   252 	    list->head = (nssListElement *)PR_NEXT_LINK(&node->link);

   253 	}

   254 	PR_REMOVE_LINK(&node->link);

   255 	nss_ZFreeIf(node);

   256 	if (--list->count == 0) {

   257 	    list->head = NULL;

   258 	}

   259     }

   260     NSSLIST_UNLOCK_IF(list);

   261     return PR_SUCCESS;

   262 }

   264 NSS_IMPLEMENT void *

   265 nssList_Get(nssList *list, void *data)

   266 {

   267     nssListElement *node;

   268     NSSLIST_LOCK_IF(list);

   269     node = nsslist_get_matching_element(list, data);

   270     NSSLIST_UNLOCK_IF(list);

   271     return (node) ? node->data : NULL;

   272 }

   274 NSS_IMPLEMENT PRUint32

   275 nssList_Count(nssList *list)

   276 {

   277     return list->count;

   278 }

   280 NSS_IMPLEMENT PRStatus

   281 nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)

   282 {

   283     nssListElement *node;

   284     PRUint32 i = 0;

   285     PR_ASSERT(maxElements > 0);

   286     node = list->head;

   287     if (!node) {

   288 	return PR_SUCCESS;

   289     }

   290     NSSLIST_LOCK_IF(list);

   291     while (node) {

   292 	rvArray[i++] = node->data;

   293 	if (i == maxElements) 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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

The Tor Browser / file revision

security/nss/lib/base/list.c@b8a032363ba2

security/nss/lib/base/list.c