security/nss/lib/base/list.c

   1 /* ***** BEGIN LICENSE BLOCK *****
   2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3  *
   4  * The contents of this file are subject to the Mozilla Public License Version
   5  * 1.1 (the "License"); you may not use this file except in compliance with
   6  * the License. You may obtain a copy of the License at
   7  * http://www.mozilla.org/MPL/
   8  *
   9  * Software distributed under the License is distributed on an "AS IS" basis,
  10  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11  * for the specific language governing rights and limitations under the
  12  * License.
  13  *
  14  * The Original Code is the Netscape security libraries.
  15  *
  16  * The Initial Developer of the Original Code is
  17  * Netscape Communications Corporation.
  18  * Portions created by the Initial Developer are Copyright (C) 1994-2000
  19  * the Initial Developer. All Rights Reserved.
  20  *
  21  * Contributor(s):
  22  *
  23  * Alternatively, the contents of this file may be used under the terms of
  24  * either the GNU General Public License Version 2 or later (the "GPL"), or
  25  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  26  * in which case the provisions of the GPL or the LGPL are applicable instead
  27  * of those above. If you wish to allow use of your version of this file only
  28  * under the terms of either the GPL or the LGPL, and not to allow others to
  29  * use your version of this file under the terms of the MPL, indicate your
  30  * decision by deleting the provisions above and replace them with the notice
  31  * and other provisions required by the GPL or the LGPL. If you do not delete
  32  * the provisions above, a recipient may use your version of this file under
  33  * the terms of any one of the MPL, the GPL or the LGPL.
  34  *
  35  * ***** END LICENSE BLOCK ***** */
  36
  37 #ifdef DEBUG
  38 static const char CVS_ID[] = "@(#) $RCSfile: list.c,v $ $Revision: 1.20 $ $Date: 2006/09/29 20:13:30 $";
  39 #endif /* DEBUG */
  40
  41 /*
  42  * list.c
  43  *
  44  * This contains the implementation of NSS's thread-safe linked list.
  45  */
  46
  47 #ifndef BASE_H
  48 #include "base.h"
  49 #endif /* BASE_H */
  50
  51 struct nssListElementStr {
  52     PRCList  link;
  53     void    *data;
  54 };
  55
  56 typedef struct nssListElementStr nssListElement;
  57
  58 struct nssListStr {
  59     NSSArena       *arena;
  60     PZLock         *lock;
  61     nssListElement *head;
  62     PRUint32        count;
  63     nssListCompareFunc compareFunc;
  64     nssListSortFunc    sortFunc;
  65     PRBool i_alloced_arena;
  66 };
  67
  68 struct nssListIteratorStr {
  69     PZLock *lock;
  70     nssList *list;
  71     nssListElement *current;
  72 };
  73
  74 #define NSSLIST_LOCK_IF(list) \
  75     if ((list)->lock) PZ_Lock((list)->lock)
  76
  77 #define NSSLIST_UNLOCK_IF(list) \
  78     if ((list)->lock) PZ_Unlock((list)->lock)
  79
  80 static PRBool
  81 pointer_compare(void *a, void *b)
  82 {
  83     return (PRBool)(a == b);
  84 }
  85
  86 static nssListElement *
  87 nsslist_get_matching_element(nssList *list, void *data)
  88 {
  89     PRCList *link;
  90     nssListElement *node;
  91     node = list->head;
  92     if (!node) {
  93         return NULL;
  94     }
  95     link = &node->link;
  96     while (node) {
  97         /* using a callback slows things down when it's just compare ... */
  98         if (list->compareFunc(node->data, data)) {
  99             break;
 100         }
 101         link = &node->link;
 102         if (link == PR_LIST_TAIL(&list->head->link)) {
 103             node = NULL;
 104             break;
 105         }
 106         node = (nssListElement *)PR_NEXT_LINK(&node->link);
 107     }
 108     return node;
 109 }
 110
 111 NSS_IMPLEMENT nssList *
 112 nssList_Create
 113 (
 114   NSSArena *arenaOpt,
 115   PRBool threadSafe
 116 )
 117 {
 118     NSSArena *arena;
 119     nssList *list;
 120     PRBool i_alloced;
 121     if (arenaOpt) {
 122         arena = arenaOpt;
 123         i_alloced = PR_FALSE;
 124     } else {
 125         arena = nssArena_Create();
 126         i_alloced = PR_TRUE;
 127     }
 128     if (!arena) {
 129         return (nssList *)NULL;
 130     }
 131     list = nss_ZNEW(arena, nssList);
 132     if (!list) {
 133         if (!arenaOpt) {
 134             NSSArena_Destroy(arena);
 135         }
 136         return (nssList *)NULL;
 137     }
 138     if (threadSafe) {
 139         list->lock = PZ_NewLock(nssILockOther);
 140         if (!list->lock) {
 141             if (arenaOpt) {
 142                 nss_ZFreeIf(list);
 143             } else {
 144                 NSSArena_Destroy(arena);
 145             }
 146             return (nssList *)NULL;
 147         }
 148     }
 149     list->arena = arena;
 150     list->i_alloced_arena = i_alloced;
 151     list->compareFunc = pointer_compare;
 152     return list;
 153 }
 154
 155 NSS_IMPLEMENT PRStatus
 156 nssList_Destroy(nssList *list)
 157 {
 158     if (!list->i_alloced_arena) {
 159         nssList_Clear(list, NULL);
 160     }
 161     if (list->lock) {
 162         (void)PZ_DestroyLock(list->lock);
 163     }
 164     if (list->i_alloced_arena) {
 165         NSSArena_Destroy(list->arena);
 166         list = NULL;
 167     }
 168     nss_ZFreeIf(list);
 169     return PR_SUCCESS;
 170 }
 171
 172 NSS_IMPLEMENT void
 173 nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc)
 174 {
 175     list->compareFunc = compareFunc;
 176 }
 177
 178 NSS_IMPLEMENT void
 179 nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
 180 {
 181     /* XXX if list already has elements, sort them */
 182     list->sortFunc = sortFunc;
 183 }
 184
 185 NSS_IMPLEMENT nssListCompareFunc
 186 nssList_GetCompareFunction(nssList *list)
 187 {
 188     return list->compareFunc;
 189 }
 190
 191 NSS_IMPLEMENT void
 192 nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
 193 {
 194     PRCList *link;
 195     nssListElement *node, *tmp;
 196     NSSLIST_LOCK_IF(list);
 197     node = list->head;
 198     list->head = NULL;
 199     while (node && list->count > 0) {
 200         if (destructor) (*destructor)(node->data);
 201         link = &node->link;
 202         tmp = (nssListElement *)PR_NEXT_LINK(link);
 203         PR_REMOVE_LINK(link);
 204         nss_ZFreeIf(node);
 205         node = tmp;
 206         --list->count;
 207     }
 208     NSSLIST_UNLOCK_IF(list);
 209 }
 210
 211 static PRStatus
 212 nsslist_add_element(nssList *list, void *data)
 213 {
 214     nssListElement *node = nss_ZNEW(list->arena, nssListElement);
 215     if (!node) {
 216         return PR_FAILURE;
 217     }
 218     PR_INIT_CLIST(&node->link);
 219     node->data = data;
 220     if (list->head) {
 221         if (list->sortFunc) {
 222             PRCList *link;
 223             nssListElement *currNode;
 224             currNode = list->head;
 225             /* insert in ordered list */
 226             while (currNode) {
 227                 link = &currNode->link;
 228                 if (list->sortFunc(data, currNode->data) <= 0) {
 229                     /* new element goes before current node */
 230                     PR_INSERT_BEFORE(&node->link, link);
 231                     /* reset head if this is first */
 232                     if (currNode == list->head) list->head = node;
 233                     break;
 234                 }
 235                 if (link == PR_LIST_TAIL(&list->head->link)) {
 236                     /* reached end of list, append */
 237                     PR_INSERT_AFTER(&node->link, link);
 238                     break;
 239                 }
 240                 currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
 241             }
 242         } else {
 243             /* not sorting */
 244             PR_APPEND_LINK(&node->link, &list->head->link);
 245         }
 246     } else {
 247         list->head = node;
 248     }
 249     ++list->count;
 250     return PR_SUCCESS;
 251 }
 252
 253 NSS_IMPLEMENT PRStatus
 254 nssList_Add(nssList *list, void *data)
 255 {
 256     PRStatus nssrv;
 257     NSSLIST_LOCK_IF(list);
 258     nssrv = nsslist_add_element(list, data);
 259     NSSLIST_UNLOCK_IF(list);
 260     return PR_SUCCESS;
 261 }
 262
 263 NSS_IMPLEMENT PRStatus
 264 nssList_AddUnique(nssList *list, void *data)
 265 {
 266     PRStatus nssrv;
 267     nssListElement *node;
 268     NSSLIST_LOCK_IF(list);
 269     node = nsslist_get_matching_element(list, data);
 270     if (node) {
 271         /* already in, finish */
 272         NSSLIST_UNLOCK_IF(list);
 273         return PR_SUCCESS;
 274     }
 275     nssrv = nsslist_add_element(list, data);
 276     NSSLIST_UNLOCK_IF(list);
 277     return nssrv;
 278 }
 279
 280 NSS_IMPLEMENT PRStatus
 281 nssList_Remove(nssList *list, void *data)
 282 {
 283     nssListElement *node;
 284     NSSLIST_LOCK_IF(list);
 285     node = nsslist_get_matching_element(list, data);
 286     if (node) {
 287         if (node == list->head) {
 288             list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
 289         }
 290         PR_REMOVE_LINK(&node->link);
 291         nss_ZFreeIf(node);
 292         if (--list->count == 0) {
 293             list->head = NULL;
 294         }
 295     }
 296     NSSLIST_UNLOCK_IF(list);
 297     return PR_SUCCESS;
 298 }
 299
 300 NSS_IMPLEMENT void *
 301 nssList_Get(nssList *list, void *data)
 302 {
 303     nssListElement *node;
 304     NSSLIST_LOCK_IF(list);
 305     node = nsslist_get_matching_element(list, data);
 306     NSSLIST_UNLOCK_IF(list);
 307     return (node) ? node->data : NULL;
 308 }
 309
 310 NSS_IMPLEMENT PRUint32
 311 nssList_Count(nssList *list)
 312 {
 313     return list->count;
 314 }
 315
 316 NSS_IMPLEMENT PRStatus
 317 nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)
 318 {
 319     nssListElement *node;
 320     PRUint32 i = 0;
 321     PR_ASSERT(maxElements > 0);
 322     node = list->head;
 323     if (!node) {
 324         return PR_SUCCESS;
 325     }
 326     NSSLIST_LOCK_IF(list);
 327     while (node) {
 328         rvArray[i++] = node->data;
 329         if (i == maxElements) break;
 330         node = (nssListElement *)PR_NEXT_LINK(&node->link);
 331         if (node == list->head) {
 332             break;
 333         }
 334     }
 335     NSSLIST_UNLOCK_IF(list);
 336     return PR_SUCCESS;
 337 }
 338
 339 NSS_IMPLEMENT nssList *
 340 nssList_Clone(nssList *list)
 341 {
 342     nssList *rvList;
 343     nssListElement *node;
 344     rvList = nssList_Create(NULL, (list->lock != NULL));
 345     if (!rvList) {
 346         return NULL;
 347     }
 348     NSSLIST_LOCK_IF(list);
 349     if (list->count > 0) {
 350         node = list->head;
 351         while (PR_TRUE) {
 352             nssList_Add(rvList, node->data);
 353             node = (nssListElement *)PR_NEXT_LINK(&node->link);
 354             if (node == list->head) {
 355                 break;
 356             }
 357         }
 358     }
 359     NSSLIST_UNLOCK_IF(list);
 360     return rvList;
 361 }
 362
 363 NSS_IMPLEMENT nssListIterator *
 364 nssList_CreateIterator(nssList *list)
 365 {
 366     nssListIterator *rvIterator;
 367     rvIterator = nss_ZNEW(NULL, nssListIterator);
 368     if (!rvIterator) {
 369         return NULL;
 370     }
 371     rvIterator->list = nssList_Clone(list);
 372     if (!rvIterator->list) {
 373         nss_ZFreeIf(rvIterator);
 374         return NULL;
 375     }
 376     rvIterator->current = rvIterator->list->head;
 377     if (list->lock) {
 378         rvIterator->lock = PZ_NewLock(nssILockOther);
 379         if (!rvIterator->lock) {
 380             nssList_Destroy(rvIterator->list);
 381             nss_ZFreeIf(rvIterator);
 382             rvIterator = NULL;
 383         }
 384     }
 385     return rvIterator;
 386 }
 387
 388 NSS_IMPLEMENT void
 389 nssListIterator_Destroy(nssListIterator *iter)
 390 {
 391     if (iter->lock) {
 392         (void)PZ_DestroyLock(iter->lock);
 393     }
 394     nssList_Destroy(iter->list);
 395     nss_ZFreeIf(iter);
 396 }
 397
 398 NSS_IMPLEMENT void *
 399 nssListIterator_Start(nssListIterator *iter)
 400 {
 401     NSSLIST_LOCK_IF(iter);
 402     if (iter->list->count == 0) {
 403         return NULL;
 404     }
 405     iter->current = iter->list->head;
 406     return iter->current->data;
 407 }
 408
 409 NSS_IMPLEMENT void *
 410 nssListIterator_Next(nssListIterator *iter)
 411 {
 412     nssListElement *node;
 413     PRCList *link;
 414     if (iter->list->count == 1 || iter->current == NULL) {
 415         /* Reached the end of the list.  Don't change the state, force to
 416          * user to call nssList_Finish to clean up.
 417          */
 418         return NULL;
 419     }
 420     node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
 421     link = &node->link;
 422     if (link == PR_LIST_TAIL(&iter->list->head->link)) {
 423         /* Signal the end of the list. */
 424         iter->current = NULL;
 425         return node->data;
 426     }
 427     iter->current = node;
 428     return node->data;
 429 }
 430
 431 NSS_IMPLEMENT PRStatus
 432 nssListIterator_Finish(nssListIterator *iter)
 433 {
 434     iter->current = iter->list->head;
 435     return (iter->lock) ? PZ_Unlock(iter->lock) : PR_SUCCESS;
 436 }
 437