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

     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 }

mercurial