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