michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * list.c
michael@0:  *
michael@0:  * This contains the implementation of NSS's thread-safe linked list.
michael@0:  */
michael@0: 
michael@0: #ifndef BASE_H
michael@0: #include "base.h"
michael@0: #endif /* BASE_H */
michael@0: 
michael@0: struct nssListElementStr {
michael@0:     PRCList  link;
michael@0:     void    *data;
michael@0: };
michael@0: 
michael@0: typedef struct nssListElementStr nssListElement;
michael@0: 
michael@0: struct nssListStr {
michael@0:     NSSArena       *arena;
michael@0:     PZLock         *lock;
michael@0:     nssListElement *head;
michael@0:     PRUint32        count;
michael@0:     nssListCompareFunc compareFunc;
michael@0:     nssListSortFunc    sortFunc;
michael@0:     PRBool i_alloced_arena;
michael@0: };
michael@0: 
michael@0: struct nssListIteratorStr {
michael@0:     PZLock *lock;
michael@0:     nssList *list;
michael@0:     nssListElement *current;
michael@0: };
michael@0: 
michael@0: #define NSSLIST_LOCK_IF(list) \
michael@0:     if ((list)->lock) PZ_Lock((list)->lock)
michael@0: 
michael@0: #define NSSLIST_UNLOCK_IF(list) \
michael@0:     if ((list)->lock) PZ_Unlock((list)->lock)
michael@0: 
michael@0: static PRBool
michael@0: pointer_compare(void *a, void *b)
michael@0: {
michael@0:     return (PRBool)(a == b);
michael@0: }
michael@0: 
michael@0: static nssListElement *
michael@0: nsslist_get_matching_element(nssList *list, void *data)
michael@0: {
michael@0:     PRCList *link;
michael@0:     nssListElement *node;
michael@0:     node = list->head;
michael@0:     if (!node) {
michael@0: 	return NULL;
michael@0:     }
michael@0:     link = &node->link;
michael@0:     while (node) {
michael@0: 	/* using a callback slows things down when it's just compare ... */
michael@0: 	if (list->compareFunc(node->data, data)) {
michael@0: 	    break;
michael@0: 	}
michael@0: 	link = &node->link;
michael@0: 	if (link == PR_LIST_TAIL(&list->head->link)) {
michael@0: 	    node = NULL;
michael@0: 	    break;
michael@0: 	}
michael@0: 	node = (nssListElement *)PR_NEXT_LINK(&node->link);
michael@0:     }
michael@0:     return node;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT nssList *
michael@0: nssList_Create
michael@0: (
michael@0:   NSSArena *arenaOpt,
michael@0:   PRBool threadSafe
michael@0: )
michael@0: {
michael@0:     NSSArena *arena;
michael@0:     nssList *list;
michael@0:     PRBool i_alloced;
michael@0:     if (arenaOpt) {
michael@0: 	arena = arenaOpt;
michael@0: 	i_alloced = PR_FALSE;
michael@0:     } else {
michael@0: 	arena = nssArena_Create();
michael@0: 	i_alloced = PR_TRUE;
michael@0:     }
michael@0:     if (!arena) {
michael@0: 	return (nssList *)NULL;
michael@0:     }
michael@0:     list = nss_ZNEW(arena, nssList);
michael@0:     if (!list) {
michael@0: 	if (!arenaOpt) {
michael@0: 	    NSSArena_Destroy(arena);
michael@0: 	}
michael@0: 	return (nssList *)NULL;
michael@0:     }
michael@0:     if (threadSafe) {
michael@0: 	list->lock = PZ_NewLock(nssILockOther);
michael@0: 	if (!list->lock) {
michael@0: 	    if (arenaOpt) {
michael@0: 		nss_ZFreeIf(list);
michael@0: 	    } else {
michael@0: 		NSSArena_Destroy(arena);
michael@0: 	    }
michael@0: 	    return (nssList *)NULL;
michael@0: 	}
michael@0:     }
michael@0:     list->arena = arena;
michael@0:     list->i_alloced_arena = i_alloced;
michael@0:     list->compareFunc = pointer_compare;
michael@0:     return list;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRStatus
michael@0: nssList_Destroy(nssList *list)
michael@0: {
michael@0:     if (!list->i_alloced_arena) {
michael@0: 	nssList_Clear(list, NULL);
michael@0:     }
michael@0:     if (list->lock) {
michael@0: 	(void)PZ_DestroyLock(list->lock);
michael@0:     }
michael@0:     if (list->i_alloced_arena) {
michael@0: 	NSSArena_Destroy(list->arena);
michael@0: 	list = NULL;
michael@0:     }
michael@0:     nss_ZFreeIf(list);
michael@0:     return PR_SUCCESS;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void
michael@0: nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc)
michael@0: {
michael@0:     list->compareFunc = compareFunc;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void
michael@0: nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
michael@0: {
michael@0:     /* XXX if list already has elements, sort them */
michael@0:     list->sortFunc = sortFunc;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT nssListCompareFunc
michael@0: nssList_GetCompareFunction(nssList *list)
michael@0: {
michael@0:     return list->compareFunc;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void
michael@0: nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
michael@0: {
michael@0:     PRCList *link;
michael@0:     nssListElement *node, *tmp;
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     node = list->head;
michael@0:     list->head = NULL;
michael@0:     while (node && list->count > 0) {
michael@0: 	if (destructor) (*destructor)(node->data);
michael@0: 	link = &node->link;
michael@0: 	tmp = (nssListElement *)PR_NEXT_LINK(link);
michael@0: 	PR_REMOVE_LINK(link);
michael@0: 	nss_ZFreeIf(node);
michael@0: 	node = tmp;
michael@0: 	--list->count;
michael@0:     }
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0: }
michael@0: 
michael@0: static PRStatus
michael@0: nsslist_add_element(nssList *list, void *data)
michael@0: {
michael@0:     nssListElement *node = nss_ZNEW(list->arena, nssListElement);
michael@0:     if (!node) {
michael@0: 	return PR_FAILURE;
michael@0:     }
michael@0:     PR_INIT_CLIST(&node->link);
michael@0:     node->data = data;
michael@0:     if (list->head) {
michael@0: 	if (list->sortFunc) {
michael@0: 	    PRCList *link;
michael@0: 	    nssListElement *currNode;
michael@0: 	    currNode = list->head;
michael@0: 	    /* insert in ordered list */
michael@0: 	    while (currNode) {
michael@0: 		link = &currNode->link;
michael@0: 		if (list->sortFunc(data, currNode->data) <= 0) {
michael@0: 		    /* new element goes before current node */
michael@0: 		    PR_INSERT_BEFORE(&node->link, link);
michael@0: 		    /* reset head if this is first */
michael@0: 		    if (currNode == list->head) list->head = node;
michael@0: 		    break;
michael@0: 		}
michael@0: 		if (link == PR_LIST_TAIL(&list->head->link)) {
michael@0: 		    /* reached end of list, append */
michael@0: 		    PR_INSERT_AFTER(&node->link, link);
michael@0: 		    break;
michael@0: 		}
michael@0: 		currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
michael@0: 	    }
michael@0: 	} else {
michael@0: 	    /* not sorting */
michael@0: 	    PR_APPEND_LINK(&node->link, &list->head->link);
michael@0: 	}
michael@0:     } else {
michael@0: 	list->head = node;
michael@0:     }
michael@0:     ++list->count;
michael@0:     return PR_SUCCESS;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRStatus
michael@0: nssList_Add(nssList *list, void *data)
michael@0: {
michael@0:     PRStatus nssrv;
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     nssrv = nsslist_add_element(list, data);
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0:     return PR_SUCCESS;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRStatus
michael@0: nssList_AddUnique(nssList *list, void *data)
michael@0: {
michael@0:     PRStatus nssrv;
michael@0:     nssListElement *node;
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     node = nsslist_get_matching_element(list, data);
michael@0:     if (node) {
michael@0: 	/* already in, finish */
michael@0: 	NSSLIST_UNLOCK_IF(list);
michael@0: 	return PR_SUCCESS;
michael@0:     }
michael@0:     nssrv = nsslist_add_element(list, data);
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0:     return nssrv;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRStatus
michael@0: nssList_Remove(nssList *list, void *data)
michael@0: {
michael@0:     nssListElement *node;
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     node = nsslist_get_matching_element(list, data);
michael@0:     if (node) {
michael@0: 	if (node == list->head) {
michael@0: 	    list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
michael@0: 	}
michael@0: 	PR_REMOVE_LINK(&node->link);
michael@0: 	nss_ZFreeIf(node);
michael@0: 	if (--list->count == 0) {
michael@0: 	    list->head = NULL;
michael@0: 	}
michael@0:     }
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0:     return PR_SUCCESS;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void *
michael@0: nssList_Get(nssList *list, void *data)
michael@0: {
michael@0:     nssListElement *node;
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     node = nsslist_get_matching_element(list, data);
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0:     return (node) ? node->data : NULL;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRUint32
michael@0: nssList_Count(nssList *list)
michael@0: {
michael@0:     return list->count;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRStatus
michael@0: nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)
michael@0: {
michael@0:     nssListElement *node;
michael@0:     PRUint32 i = 0;
michael@0:     PR_ASSERT(maxElements > 0);
michael@0:     node = list->head;
michael@0:     if (!node) {
michael@0: 	return PR_SUCCESS;
michael@0:     }
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     while (node) {
michael@0: 	rvArray[i++] = node->data;
michael@0: 	if (i == maxElements) break;
michael@0: 	node = (nssListElement *)PR_NEXT_LINK(&node->link);
michael@0: 	if (node == list->head) {
michael@0: 	    break;
michael@0: 	}
michael@0:     }
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0:     return PR_SUCCESS;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT nssList *
michael@0: nssList_Clone(nssList *list)
michael@0: {
michael@0:     nssList *rvList;
michael@0:     nssListElement *node;
michael@0:     rvList = nssList_Create(NULL, (list->lock != NULL));
michael@0:     if (!rvList) {
michael@0: 	return NULL;
michael@0:     }
michael@0:     NSSLIST_LOCK_IF(list);
michael@0:     if (list->count > 0) {
michael@0: 	node = list->head;
michael@0: 	while (PR_TRUE) {
michael@0: 	    nssList_Add(rvList, node->data);
michael@0: 	    node = (nssListElement *)PR_NEXT_LINK(&node->link);
michael@0: 	    if (node == list->head) {
michael@0: 		break;
michael@0: 	    }
michael@0: 	}
michael@0:     }
michael@0:     NSSLIST_UNLOCK_IF(list);
michael@0:     return rvList;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT nssListIterator *
michael@0: nssList_CreateIterator(nssList *list)
michael@0: {
michael@0:     nssListIterator *rvIterator;
michael@0:     rvIterator = nss_ZNEW(NULL, nssListIterator);
michael@0:     if (!rvIterator) {
michael@0: 	return NULL;
michael@0:     }
michael@0:     rvIterator->list = nssList_Clone(list);
michael@0:     if (!rvIterator->list) {
michael@0: 	nss_ZFreeIf(rvIterator);
michael@0: 	return NULL;
michael@0:     }
michael@0:     rvIterator->current = rvIterator->list->head;
michael@0:     if (list->lock) {
michael@0: 	rvIterator->lock = PZ_NewLock(nssILockOther);
michael@0: 	if (!rvIterator->lock) {
michael@0: 	    nssList_Destroy(rvIterator->list);
michael@0: 	    nss_ZFreeIf(rvIterator);
michael@0: 	    rvIterator = NULL;
michael@0: 	}
michael@0:     }
michael@0:     return rvIterator;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void
michael@0: nssListIterator_Destroy(nssListIterator *iter)
michael@0: {
michael@0:     if (iter->lock) {
michael@0: 	(void)PZ_DestroyLock(iter->lock);
michael@0:     }
michael@0:     nssList_Destroy(iter->list);
michael@0:     nss_ZFreeIf(iter);
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void *
michael@0: nssListIterator_Start(nssListIterator *iter)
michael@0: {
michael@0:     NSSLIST_LOCK_IF(iter);
michael@0:     if (iter->list->count == 0) {
michael@0: 	return NULL;
michael@0:     }
michael@0:     iter->current = iter->list->head;
michael@0:     return iter->current->data;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT void *
michael@0: nssListIterator_Next(nssListIterator *iter)
michael@0: {
michael@0:     nssListElement *node;
michael@0:     PRCList *link;
michael@0:     if (iter->list->count == 1 || iter->current == NULL) {
michael@0: 	/* Reached the end of the list.  Don't change the state, force to
michael@0: 	 * user to call nssList_Finish to clean up.
michael@0: 	 */
michael@0: 	return NULL;
michael@0:     }
michael@0:     node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
michael@0:     link = &node->link;
michael@0:     if (link == PR_LIST_TAIL(&iter->list->head->link)) {
michael@0: 	/* Signal the end of the list. */
michael@0: 	iter->current = NULL;
michael@0: 	return node->data;
michael@0:     }
michael@0:     iter->current = node;
michael@0:     return node->data;
michael@0: }
michael@0: 
michael@0: NSS_IMPLEMENT PRStatus
michael@0: nssListIterator_Finish(nssListIterator *iter)
michael@0: {
michael@0:     iter->current = iter->list->head;
michael@0:     return (iter->lock) ? PZ_Unlock(iter->lock) : PR_SUCCESS;
michael@0: }
michael@0: