tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

list.c (9770B)

      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/. */
      4 
      5 /*
      6 * list.c
      7 *
      8 * This contains the implementation of NSS's thread-safe linked list.
      9 */
     10 
     11 #ifndef BASE_H
     12 #include "base.h"
     13 #endif /* BASE_H */
     14 
     15 struct nssListElementStr {
     16    PRCList link;
     17    void *data;
     18 };
     19 
     20 typedef struct nssListElementStr nssListElement;
     21 
     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 };
     31 
     32 struct nssListIteratorStr {
     33    PZLock *lock;
     34    nssList *list;
     35    nssListElement *current;
     36 };
     37 
     38 #define NSSLIST_LOCK_IF(list) \
     39    if ((list)->lock)         \
     40    PZ_Lock((list)->lock)
     41 
     42 #define NSSLIST_UNLOCK_IF(list) \
     43    if ((list)->lock)           \
     44    PZ_Unlock((list)->lock)
     45 
     46 static PRBool
     47 pointer_compare(void *a, void *b)
     48 {
     49    return (PRBool)(a == b);
     50 }
     51 
     52 static nssListElement *
     53 nsslist_get_matching_element(nssList *list, void *data)
     54 {
     55    nssListElement *node;
     56    node = list->head;
     57    if (!node) {
     58        return NULL;
     59    }
     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        if (&node->link == PR_LIST_TAIL(&list->head->link)) {
     66            node = NULL;
     67            break;
     68        }
     69        node = (nssListElement *)PR_NEXT_LINK(&node->link);
     70    }
     71    return node;
     72 }
     73 
     74 NSS_IMPLEMENT nssList *
     75 nssList_Create(NSSArena *arenaOpt, PRBool threadSafe)
     76 {
     77    NSSArena *arena;
     78    nssList *list;
     79    PRBool i_alloced;
     80    if (arenaOpt) {
     81        arena = arenaOpt;
     82        i_alloced = PR_FALSE;
     83    } else {
     84        arena = nssArena_Create();
     85        i_alloced = PR_TRUE;
     86    }
     87    if (!arena) {
     88        return (nssList *)NULL;
     89    }
     90    list = nss_ZNEW(arena, nssList);
     91    if (!list) {
     92        if (!arenaOpt) {
     93            NSSArena_Destroy(arena);
     94        }
     95        return (nssList *)NULL;
     96    }
     97    if (threadSafe) {
     98        list->lock = PZ_NewLock(nssILockOther);
     99        if (!list->lock) {
    100            if (arenaOpt) {
    101                nss_ZFreeIf(list);
    102            } else {
    103                NSSArena_Destroy(arena);
    104            }
    105            return (nssList *)NULL;
    106        }
    107    }
    108    list->arena = arena;
    109    list->i_alloced_arena = i_alloced;
    110    list->compareFunc = pointer_compare;
    111    return list;
    112 }
    113 
    114 NSS_IMPLEMENT PRStatus
    115 nssList_Destroy(nssList *list)
    116 {
    117    if (!list) {
    118        return PR_SUCCESS;
    119    }
    120    if (!list->i_alloced_arena) {
    121        nssList_Clear(list, NULL);
    122    }
    123    if (list->lock) {
    124        (void)PZ_DestroyLock(list->lock);
    125    }
    126    if (list->i_alloced_arena) {
    127        NSSArena_Destroy(list->arena);
    128        list = NULL;
    129    }
    130    nss_ZFreeIf(list);
    131    return PR_SUCCESS;
    132 }
    133 
    134 NSS_IMPLEMENT void
    135 nssList_SetCompareFunction(nssList *list, nssListCompareFunc compareFunc)
    136 {
    137    list->compareFunc = compareFunc;
    138 }
    139 
    140 NSS_IMPLEMENT void
    141 nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
    142 {
    143    /* XXX if list already has elements, sort them */
    144    list->sortFunc = sortFunc;
    145 }
    146 
    147 NSS_IMPLEMENT nssListCompareFunc
    148 nssList_GetCompareFunction(nssList *list)
    149 {
    150    return list->compareFunc;
    151 }
    152 
    153 NSS_IMPLEMENT void
    154 nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
    155 {
    156    PRCList *link;
    157    nssListElement *node, *tmp;
    158    if (!list) {
    159        return;
    160    }
    161    NSSLIST_LOCK_IF(list);
    162    node = list->head;
    163    list->head = NULL;
    164    while (node && list->count > 0) {
    165        if (destructor)
    166            (*destructor)(node->data);
    167        link = &node->link;
    168        tmp = (nssListElement *)PR_NEXT_LINK(link);
    169        PR_REMOVE_LINK(link);
    170        nss_ZFreeIf(node);
    171        node = tmp;
    172        --list->count;
    173    }
    174    NSSLIST_UNLOCK_IF(list);
    175 }
    176 
    177 static PRStatus
    178 nsslist_add_element(nssList *list, void *data)
    179 {
    180    nssListElement *node = nss_ZNEW(list->arena, nssListElement);
    181    if (!node) {
    182        return PR_FAILURE;
    183    }
    184    PR_INIT_CLIST(&node->link);
    185    node->data = data;
    186    if (list->head) {
    187        if (list->sortFunc) {
    188            PRCList *link;
    189            nssListElement *currNode;
    190            currNode = list->head;
    191            /* insert in ordered list */
    192            while (currNode) {
    193                link = &currNode->link;
    194                if (list->sortFunc(data, currNode->data) <= 0) {
    195                    /* new element goes before current node */
    196                    PR_INSERT_BEFORE(&node->link, link);
    197                    /* reset head if this is first */
    198                    if (currNode == list->head)
    199                        list->head = node;
    200                    break;
    201                }
    202                if (link == PR_LIST_TAIL(&list->head->link)) {
    203                    /* reached end of list, append */
    204                    PR_INSERT_AFTER(&node->link, link);
    205                    break;
    206                }
    207                currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
    208            }
    209        } else {
    210            /* not sorting */
    211            PR_APPEND_LINK(&node->link, &list->head->link);
    212        }
    213    } else {
    214        list->head = node;
    215    }
    216    ++list->count;
    217    return PR_SUCCESS;
    218 }
    219 
    220 NSS_IMPLEMENT PRStatus
    221 nssList_Add(nssList *list, void *data)
    222 {
    223    NSSLIST_LOCK_IF(list);
    224    (void)nsslist_add_element(list, data);
    225    NSSLIST_UNLOCK_IF(list);
    226    return PR_SUCCESS;
    227 }
    228 
    229 NSS_IMPLEMENT PRStatus
    230 nssList_AddUnique(nssList *list, void *data)
    231 {
    232    PRStatus nssrv;
    233    nssListElement *node;
    234    NSSLIST_LOCK_IF(list);
    235    node = nsslist_get_matching_element(list, data);
    236    if (node) {
    237        /* already in, finish */
    238        NSSLIST_UNLOCK_IF(list);
    239        return PR_SUCCESS;
    240    }
    241    nssrv = nsslist_add_element(list, data);
    242    NSSLIST_UNLOCK_IF(list);
    243    return nssrv;
    244 }
    245 
    246 NSS_IMPLEMENT PRStatus
    247 nssList_Remove(nssList *list, void *data)
    248 {
    249    nssListElement *node;
    250    NSSLIST_LOCK_IF(list);
    251    node = nsslist_get_matching_element(list, data);
    252    if (node) {
    253        if (node == list->head) {
    254            list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
    255        }
    256        PR_REMOVE_LINK(&node->link);
    257        nss_ZFreeIf(node);
    258        if (--list->count == 0) {
    259            list->head = NULL;
    260        }
    261    }
    262    NSSLIST_UNLOCK_IF(list);
    263    return PR_SUCCESS;
    264 }
    265 
    266 NSS_IMPLEMENT void *
    267 nssList_Get(nssList *list, void *data)
    268 {
    269    nssListElement *node;
    270    NSSLIST_LOCK_IF(list);
    271    node = nsslist_get_matching_element(list, data);
    272    NSSLIST_UNLOCK_IF(list);
    273    return (node) ? node->data : NULL;
    274 }
    275 
    276 NSS_IMPLEMENT PRUint32
    277 nssList_Count(nssList *list)
    278 {
    279    return list->count;
    280 }
    281 
    282 NSS_IMPLEMENT PRStatus
    283 nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)
    284 {
    285    nssListElement *node;
    286    PRUint32 i = 0;
    287    PR_ASSERT(maxElements > 0);
    288    node = list->head;
    289    if (!node) {
    290        return PR_SUCCESS;
    291    }
    292    NSSLIST_LOCK_IF(list);
    293    while (node) {
    294        rvArray[i++] = node->data;
    295        if (i == maxElements)
    296            break;
    297        node = (nssListElement *)PR_NEXT_LINK(&node->link);
    298        if (node == list->head) {
    299            break;
    300        }
    301    }
    302    NSSLIST_UNLOCK_IF(list);
    303    return PR_SUCCESS;
    304 }
    305 
    306 NSS_IMPLEMENT nssList *
    307 nssList_Clone(nssList *list)
    308 {
    309    nssList *rvList;
    310    nssListElement *node;
    311    rvList = nssList_Create(NULL, (list->lock != NULL));
    312    if (!rvList) {
    313        return NULL;
    314    }
    315    NSSLIST_LOCK_IF(list);
    316    if (list->count > 0) {
    317        node = list->head;
    318        while (PR_TRUE) {
    319            nssList_Add(rvList, node->data);
    320            node = (nssListElement *)PR_NEXT_LINK(&node->link);
    321            if (node == list->head) {
    322                break;
    323            }
    324        }
    325    }
    326    NSSLIST_UNLOCK_IF(list);
    327    return rvList;
    328 }
    329 
    330 NSS_IMPLEMENT nssListIterator *
    331 nssList_CreateIterator(nssList *list)
    332 {
    333    nssListIterator *rvIterator;
    334    rvIterator = nss_ZNEW(NULL, nssListIterator);
    335    if (!rvIterator) {
    336        return NULL;
    337    }
    338    rvIterator->list = nssList_Clone(list);
    339    if (!rvIterator->list) {
    340        nss_ZFreeIf(rvIterator);
    341        return NULL;
    342    }
    343    rvIterator->current = rvIterator->list->head;
    344    if (list->lock) {
    345        rvIterator->lock = PZ_NewLock(nssILockOther);
    346        if (!rvIterator->lock) {
    347            nssList_Destroy(rvIterator->list);
    348            nss_ZFreeIf(rvIterator);
    349            rvIterator = NULL;
    350        }
    351    }
    352    return rvIterator;
    353 }
    354 
    355 NSS_IMPLEMENT void
    356 nssListIterator_Destroy(nssListIterator *iter)
    357 {
    358    if (iter->lock) {
    359        (void)PZ_DestroyLock(iter->lock);
    360    }
    361    if (iter->list) {
    362        nssList_Destroy(iter->list);
    363    }
    364    nss_ZFreeIf(iter);
    365 }
    366 
    367 NSS_IMPLEMENT void *
    368 nssListIterator_Start(nssListIterator *iter)
    369 {
    370    NSSLIST_LOCK_IF(iter);
    371    if (iter->list->count == 0) {
    372        return NULL;
    373    }
    374    iter->current = iter->list->head;
    375    return iter->current->data;
    376 }
    377 
    378 NSS_IMPLEMENT void *
    379 nssListIterator_Next(nssListIterator *iter)
    380 {
    381    nssListElement *node;
    382    PRCList *link;
    383    if (iter->list->count == 1 || iter->current == NULL) {
    384        /* Reached the end of the list.  Don't change the state, force to
    385         * user to call nssList_Finish to clean up.
    386         */
    387        return NULL;
    388    }
    389    node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
    390    link = &node->link;
    391    if (link == PR_LIST_TAIL(&iter->list->head->link)) {
    392        /* Signal the end of the list. */
    393        iter->current = NULL;
    394        return node->data;
    395    }
    396    iter->current = node;
    397    return node->data;
    398 }
    399 
    400 NSS_IMPLEMENT PRStatus
    401 nssListIterator_Finish(nssListIterator *iter)
    402 {
    403    iter->current = iter->list->head;
    404    return (iter->lock) ? PZ_Unlock(iter->lock) : PR_SUCCESS;
    405 }