Back to index

lightning-sunbird  0.9+nobinonly
list.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is the Netscape security libraries.
00015  *
00016  * The Initial Developer of the Original Code is
00017  * Netscape Communications Corporation.
00018  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00019  * the Initial Developer. All Rights Reserved.
00020  *
00021  * Contributor(s):
00022  *
00023  * Alternatively, the contents of this file may be used under the terms of
00024  * either the GNU General Public License Version 2 or later (the "GPL"), or
00025  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00026  * in which case the provisions of the GPL or the LGPL are applicable instead
00027  * of those above. If you wish to allow use of your version of this file only
00028  * under the terms of either the GPL or the LGPL, and not to allow others to
00029  * use your version of this file under the terms of the MPL, indicate your
00030  * decision by deleting the provisions above and replace them with the notice
00031  * and other provisions required by the GPL or the LGPL. If you do not delete
00032  * the provisions above, a recipient may use your version of this file under
00033  * the terms of any one of the MPL, the GPL or the LGPL.
00034  *
00035  * ***** END LICENSE BLOCK ***** */
00036 
00037 #ifdef DEBUG
00038 static const char CVS_ID[] = "@(#) $RCSfile: list.c,v $ $Revision: 1.19 $ $Date: 2005/01/20 02:25:45 $";
00039 #endif /* DEBUG */
00040 
00041 /*
00042  * list.c
00043  *
00044  * This contains the implementation of NSS's thread-safe linked list.
00045  */
00046 
00047 #ifndef BASE_H
00048 #include "base.h"
00049 #endif /* BASE_H */
00050 
00051 struct nssListElementStr {
00052     PRCList  link;
00053     void    *data;
00054 };
00055 
00056 typedef struct nssListElementStr nssListElement;
00057 
00058 struct nssListStr {
00059     NSSArena       *arena;
00060     PZLock         *lock;
00061     nssListElement *head;
00062     PRUint32        count;
00063     nssListCompareFunc compareFunc;
00064     nssListSortFunc    sortFunc;
00065     PRBool i_alloced_arena;
00066 };
00067 
00068 struct nssListIteratorStr {
00069     PZLock *lock;
00070     nssList *list;
00071     nssListElement *current;
00072 };
00073 
00074 #define NSSLIST_LOCK_IF(list) \
00075     if ((list)->lock) PZ_Lock((list)->lock)
00076 
00077 #define NSSLIST_UNLOCK_IF(list) \
00078     if ((list)->lock) PZ_Unlock((list)->lock)
00079 
00080 static PRBool
00081 pointer_compare(void *a, void *b)
00082 {
00083     return (PRBool)(a == b);
00084 }
00085 
00086 static nssListElement *
00087 nsslist_get_matching_element(nssList *list, void *data)
00088 {
00089     PRCList *link;
00090     nssListElement *node;
00091     node = list->head;
00092     if (!node) {
00093        return NULL;
00094     }
00095     link = &node->link;
00096     while (node) {
00097        /* using a callback slows things down when it's just compare ... */
00098        if (list->compareFunc(node->data, data)) {
00099            break;
00100        }
00101        link = &node->link;
00102        if (link == PR_LIST_TAIL(&list->head->link)) {
00103            node = NULL;
00104            break;
00105        }
00106        node = (nssListElement *)PR_NEXT_LINK(&node->link);
00107     }
00108     return node;
00109 }
00110 
00111 NSS_IMPLEMENT nssList *
00112 nssList_Create
00113 (
00114   NSSArena *arenaOpt,
00115   PRBool threadSafe
00116 )
00117 {
00118     NSSArena *arena;
00119     nssList *list;
00120     PRBool i_alloced;
00121     if (arenaOpt) {
00122        arena = arenaOpt;
00123        i_alloced = PR_FALSE;
00124     } else {
00125        arena = nssArena_Create();
00126        i_alloced = PR_TRUE;
00127     }
00128     if (!arena) {
00129        return (nssList *)NULL;
00130     }
00131     list = nss_ZNEW(arena, nssList);
00132     if (!list) {
00133        if (!arenaOpt) {
00134            NSSArena_Destroy(arena);
00135        }
00136        return (nssList *)NULL;
00137     }
00138     if (threadSafe) {
00139        list->lock = PZ_NewLock(nssILockOther);
00140        if (!list->lock) {
00141            if (arenaOpt) {
00142               nss_ZFreeIf(list);
00143            } else {
00144               NSSArena_Destroy(arena);
00145            }
00146            return (nssList *)NULL;
00147        }
00148     }
00149     list->arena = arena;
00150     list->i_alloced_arena = i_alloced;
00151     list->compareFunc = pointer_compare;
00152     return list;
00153 }
00154 
00155 NSS_IMPLEMENT PRStatus
00156 nssList_Destroy(nssList *list)
00157 {
00158     if (!list->i_alloced_arena) {
00159        nssList_Clear(list, NULL);
00160     }
00161     if (list->lock) {
00162        (void)PZ_DestroyLock(list->lock);
00163     }
00164     if (list->i_alloced_arena) {
00165        NSSArena_Destroy(list->arena);
00166        list = NULL;
00167     }
00168     nss_ZFreeIf(list);
00169     return PR_SUCCESS;
00170 }
00171 
00172 NSS_IMPLEMENT void
00173 nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc)
00174 {
00175     list->compareFunc = compareFunc;
00176 }
00177 
00178 NSS_IMPLEMENT void
00179 nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
00180 {
00181     /* XXX if list already has elements, sort them */
00182     list->sortFunc = sortFunc;
00183 }
00184 
00185 NSS_IMPLEMENT nssListCompareFunc
00186 nssList_GetCompareFunction(nssList *list)
00187 {
00188     return list->compareFunc;
00189 }
00190 
00191 NSS_IMPLEMENT void
00192 nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
00193 {
00194     PRCList *link;
00195     nssListElement *node, *tmp;
00196     NSSLIST_LOCK_IF(list);
00197     node = list->head;
00198     list->head = NULL;
00199     while (node && list->count > 0) {
00200        if (destructor) (*destructor)(node->data);
00201        link = &node->link;
00202        tmp = (nssListElement *)PR_NEXT_LINK(link);
00203        PR_REMOVE_LINK(link);
00204        nss_ZFreeIf(node);
00205        node = tmp;
00206        --list->count;
00207     }
00208     NSSLIST_UNLOCK_IF(list);
00209 }
00210 
00211 static PRStatus
00212 nsslist_add_element(nssList *list, void *data)
00213 {
00214     nssListElement *node = nss_ZNEW(list->arena, nssListElement);
00215     if (!node) {
00216        return PR_FAILURE;
00217     }
00218     PR_INIT_CLIST(&node->link);
00219     node->data = data;
00220     if (list->head) {
00221        if (list->sortFunc) {
00222            PRCList *link;
00223            nssListElement *currNode;
00224            currNode = list->head;
00225            /* insert in ordered list */
00226            while (currNode) {
00227               link = &currNode->link;
00228               if (list->sortFunc(data, currNode->data) <= 0) {
00229                   /* new element goes before current node */
00230                   PR_INSERT_BEFORE(&node->link, link);
00231                   /* reset head if this is first */
00232                   if (currNode == list->head) list->head = node;
00233                   break;
00234               }
00235               if (link == PR_LIST_TAIL(&list->head->link)) {
00236                   /* reached end of list, append */
00237                   PR_INSERT_AFTER(&node->link, link);
00238                   break;
00239               }
00240               currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
00241            }
00242        } else {
00243            /* not sorting */
00244            PR_APPEND_LINK(&node->link, &list->head->link);
00245        }
00246     } else {
00247        list->head = node;
00248     }
00249     ++list->count;
00250     return PR_SUCCESS;
00251 }
00252 
00253 NSS_IMPLEMENT PRStatus
00254 nssList_Add(nssList *list, void *data)
00255 {
00256     PRStatus nssrv;
00257     NSSLIST_LOCK_IF(list);
00258     nssrv = nsslist_add_element(list, data);
00259     NSSLIST_UNLOCK_IF(list);
00260     return PR_SUCCESS;
00261 }
00262 
00263 NSS_IMPLEMENT PRStatus
00264 nssList_AddUnique(nssList *list, void *data)
00265 {
00266     PRStatus nssrv;
00267     nssListElement *node;
00268     NSSLIST_LOCK_IF(list);
00269     node = nsslist_get_matching_element(list, data);
00270     if (node) {
00271        /* already in, finish */
00272        NSSLIST_UNLOCK_IF(list);
00273        return PR_SUCCESS;
00274     }
00275     nssrv = nsslist_add_element(list, data);
00276     NSSLIST_UNLOCK_IF(list);
00277     return nssrv;
00278 }
00279 
00280 NSS_IMPLEMENT PRStatus
00281 nssList_Remove(nssList *list, void *data)
00282 {
00283     nssListElement *node;
00284     NSSLIST_LOCK_IF(list);
00285     node = nsslist_get_matching_element(list, data);
00286     if (node) {
00287        if (node == list->head) {
00288            list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
00289        }
00290        PR_REMOVE_LINK(&node->link);
00291        nss_ZFreeIf(node);
00292        if (--list->count == 0) {
00293            list->head = NULL;
00294        }
00295     }
00296     NSSLIST_UNLOCK_IF(list);
00297     return PR_SUCCESS;
00298 }
00299 
00300 NSS_IMPLEMENT void *
00301 nssList_Get(nssList *list, void *data)
00302 {
00303     nssListElement *node;
00304     NSSLIST_LOCK_IF(list);
00305     node = nsslist_get_matching_element(list, data);
00306     NSSLIST_UNLOCK_IF(list);
00307     return (node) ? node->data : NULL;
00308 }
00309 
00310 NSS_IMPLEMENT PRUint32
00311 nssList_Count(nssList *list)
00312 {
00313     return list->count;
00314 }
00315 
00316 NSS_IMPLEMENT PRStatus
00317 nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)
00318 {
00319     nssListElement *node;
00320     PRUint32 i = 0;
00321     PR_ASSERT(maxElements > 0);
00322     node = list->head;
00323     if (!node) {
00324        return PR_SUCCESS;
00325     }
00326     NSSLIST_LOCK_IF(list);
00327     while (node) {
00328        rvArray[i++] = node->data;
00329        if (i == maxElements) break;
00330        node = (nssListElement *)PR_NEXT_LINK(&node->link);
00331        if (node == list->head) {
00332            break;
00333        }
00334     }
00335     NSSLIST_UNLOCK_IF(list);
00336     return PR_SUCCESS;
00337 }
00338 
00339 NSS_IMPLEMENT nssList *
00340 nssList_Clone(nssList *list)
00341 {
00342     nssList *rvList;
00343     nssListElement *node;
00344     rvList = nssList_Create(NULL, (list->lock != NULL));
00345     if (!rvList) {
00346        return NULL;
00347     }
00348     NSSLIST_LOCK_IF(list);
00349     if (list->count > 0) {
00350        node = list->head;
00351        while (PR_TRUE) {
00352            nssList_Add(rvList, node->data);
00353            node = (nssListElement *)PR_NEXT_LINK(&node->link);
00354            if (node == list->head) {
00355               break;
00356            }
00357        }
00358     }
00359     NSSLIST_UNLOCK_IF(list);
00360     return rvList;
00361 }
00362 
00363 NSS_IMPLEMENT nssListIterator *
00364 nssList_CreateIterator(nssList *list)
00365 {
00366     nssListIterator *rvIterator;
00367     rvIterator = nss_ZNEW(NULL, nssListIterator);
00368     if (!rvIterator) {
00369        return NULL;
00370     }
00371     rvIterator->list = nssList_Clone(list);
00372     if (!rvIterator->list) {
00373        nss_ZFreeIf(rvIterator);
00374        return NULL;
00375     }
00376     rvIterator->current = rvIterator->list->head;
00377     if (list->lock) {
00378        rvIterator->lock = PZ_NewLock(nssILockOther);
00379        if (!rvIterator->lock) {
00380            nssList_Destroy(rvIterator->list);
00381            nss_ZFreeIf(rvIterator);
00382        }
00383     }
00384     return rvIterator;
00385 }
00386 
00387 NSS_IMPLEMENT void
00388 nssListIterator_Destroy(nssListIterator *iter)
00389 {
00390     if (iter->lock) {
00391        (void)PZ_DestroyLock(iter->lock);
00392     }
00393     nssList_Destroy(iter->list);
00394     nss_ZFreeIf(iter);
00395 }
00396 
00397 NSS_IMPLEMENT void *
00398 nssListIterator_Start(nssListIterator *iter)
00399 {
00400     NSSLIST_LOCK_IF(iter);
00401     if (iter->list->count == 0) {
00402        return NULL;
00403     }
00404     iter->current = iter->list->head;
00405     return iter->current->data;
00406 }
00407 
00408 NSS_IMPLEMENT void *
00409 nssListIterator_Next(nssListIterator *iter)
00410 {
00411     nssListElement *node;
00412     PRCList *link;
00413     if (iter->list->count == 1 || iter->current == NULL) {
00414        /* Reached the end of the list.  Don't change the state, force to
00415         * user to call nssList_Finish to clean up.
00416         */
00417        return NULL;
00418     }
00419     node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
00420     link = &node->link;
00421     if (link == PR_LIST_TAIL(&iter->list->head->link)) {
00422        /* Signal the end of the list. */
00423        iter->current = NULL;
00424        return node->data;
00425     }
00426     iter->current = node;
00427     return node->data;
00428 }
00429 
00430 NSS_IMPLEMENT PRStatus
00431 nssListIterator_Finish(nssListIterator *iter)
00432 {
00433     iter->current = iter->list->head;
00434     return (iter->lock) ? PZ_Unlock(iter->lock) : PR_SUCCESS;
00435 }
00436