IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Ignore:
Timestamp:
Apr 22, 2004, 2:19:42 PM (22 years ago)
Author:
desonia
Message:

added thread-safety to dlist and enhanced the implementation to allow smarter use of the list 'cursor'.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/psLib/src/sysUtils/psDList.c

    r484 r506  
    66 *  @author Robert Daniel DeSonia, MHPCC
    77 *
    8  *  @version $Revision: 1.4 $ $Name: not supported by cvs2svn $
    9  *  @date $Date: 2004-04-21 00:15:17 $
     8 *  @version $Revision: 1.5 $ $Name: not supported by cvs2svn $
     9 *  @date $Date: 2004-04-23 00:19:42 $
    1010 *
    1111 *  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
    … …  
    1313
    1414#include <stdlib.h>
     15#include <stdbool.h>
    1516#include <stdio.h>
    16 #include <assert.h>
     17#include <pthread.h>                   // we need a mutex to make this stuff thread safe.
     18
    1719#include "psError.h"
    1820#include "psAbort.h"
    … …  
    2123#include "psTrace.h"
    2224
     25#define ITER_INIT_HEAD ((void *)1) // next iteration should return head
     26#define ITER_INIT_TAIL ((void *)2) // next iteration should return tail
     27
     28// private functions.
     29psDlistElem* dlistGetIterator(psDlist* list);
     30int dlistGetIteratorIndex(psDlist* list);
     31void dlistSetIterator(psDlist *list, int where, bool lockList);
     32
     33
     34
    2335static psDlistElem *dlistElemAlloc(void)
    2436{
    … …  
    3547    psDlist *list = psAlloc(sizeof(psDlist));
    3648
    37     list->n = 0;
     49    list->size = 0;
    3850    list->head = list->tail = NULL;
    39     list->iter = NULL;
    40     list->iterIndex = 0;
     51    list->iter = ITER_INIT_HEAD;
     52    list->iterIndex = PS_DLIST_HEAD;
     53    pthread_mutex_init(&(list->lock),NULL)
     54    ;
     55
    4156    if (data != NULL) {
    4257        psDlistAdd(list, data, PS_DLIST_TAIL);
    … …  
    5166        return;
    5267    }
     68
     69    pthread_mutex_lock(&list->lock)
     70    ;
    5371
    5472    for(psDlistElem *ptr = list->head; ptr != NULL; ) {
    … …  
    6583    }
    6684
     85    pthread_mutex_unlock(&list->lock)
     86    ;
     87
     88    pthread_mutex_destroy(&list->lock)
     89    ;
     90
    6791    psFree(list);
    6892}
    … …  
    7094psDlist *psDlistAdd(psDlist *list, void *data, int where)
    7195{
    72     psDlistElem *elem = dlistElemAlloc();
     96    psDlistElem* position;
     97    psDlistElem* elem = dlistElemAlloc();
    7398
    7499    if (list == NULL) {
    … …  
    76101    }
    77102
    78     if (where > list->n) {
    79         psError(__FILE__, "Invalid index %d (only %d elements in psDList); assuming tail.", where, list->n);
     103    pthread_mutex_lock(&list->lock)
     104    ;
     105
     106    if (where <= PS_DLIST_UNKNOWN) {
     107        /// XXX What is the better way to communicate this failure to the caller?
     108        psError(__func__,"The given insert location (%i) for psDlistAdd is invalid. "
     109                "Adding to head instead.",where);
     110        where = PS_DLIST_HEAD; // given I can't tell caller about this, should just add it somewhere???
     111    }
     112
     113    if (where > list->size) {
     114        psError(__FILE__, "Invalid index %d (only %d elements in psDList); assuming tail.", where,
     115                list->size);
    80116        where = PS_DLIST_TAIL;
    81117    }
    82118
    83     if (where == PS_DLIST_PREVIOUS) {
    84         if (list->iter == NULL) { // if no iterator position, just insert it in the front of the list.
    85             where = PS_DLIST_HEAD;
    86         } else {
    87             elem->prev = list->iter->prev;
    88             elem->next = list->iter;
    89             elem->data = psMemIncrRefCounter(data);
    90 
    91             list->iter->prev = elem;
    92             if (elem->prev != NULL) {
    93                 elem->prev->next = elem;
    94             }
    95 
    96             list->n++;
    97         }
    98     }
    99 
    100     if (where == PS_DLIST_HEAD) {
    101         elem->prev = NULL;
    102         elem->next = list->head;
    103         elem->data = psMemIncrRefCounter(data);
    104 
    105         if (list->head != NULL) {
    106             list->head->prev = elem;
    107         }
    108 
    109         list->head = elem;
    110         if (list->tail == NULL) {
    111             list->tail = elem;
    112         }
    113         list->n++;
    114     } else if (where == PS_DLIST_TAIL) {
     119    if (where == PS_DLIST_TAIL || list->size == 0) {
     120        // insert the element at the end of the list
    115121        elem->prev = list->tail;
    116122        elem->next = NULL;
    117         elem->data = psMemIncrRefCounter(data);
    118123
    119124        if (list->tail != NULL) {
    … …  
    121126        }
    122127
    123         list->tail = elem;
    124128        if (list->head == NULL) {
    125129            list->head = elem;
    126130        }
    127         list->n++;
    128     } else
    129         else if (where == PS_DLIST_NEXT) {
    130             if (list->iter == NULL) {
    131                 return psDlistAdd(list,data,PS_DLIST_TAIL);
    132             }
    133             elem->prev = list->iter;
    134             elem->next = list->iter->next;
    135             elem->data = psMemIncrRefCounter(data);
    136 
    137             list->iter->next = elem;
    138             if (elem->next != NULL) {
    139                 elem->next->prev = elem;
    140             }
    141 
    142             list->n++;
    143         } else if (where < 0) {
    144             /// XXX What is the best way to communicate this failure to the caller?
    145             psError(__func__,"The given insert location (%i) for psDlistAdd is invalid. "
    146                     "Adding to head instead.",where);
    147             return psDlistAdd(list,data,PS_DLIST_HEAD); // should add it somewhere...
    148         } else {}
     131        list->tail = elem;
     132
     133        list->size++;
     134        list->iter = elem;
     135        list->iterIndex = list->size - 1;
     136    } else {
     137        // move ourselves to the given position
     138        dlistSetIterator(list, where, false);
     139        position = dlistGetIterator(list);
     140
     141        if (position == NULL) {
     142            psError(__func__,"%s failed to move cursor to specified location (%d)",__func__,where);
     143            position = list->head; // since we no list->size != 0, this must be non-NULL
     144        }
     145
     146        // insert our new element in front of the given position
     147        elem->prev = position->prev;
     148        elem->next = position;
     149        position->prev = elem;
     150
     151        if (elem->prev == NULL) { // must be front of list
     152            list->head = elem;
     153        } else {
     154            elem->prev->next = elem;
     155        }
     156
     157        list->size++;
     158        list->iter = elem;
     159    }
     160
     161    elem->data = psMemIncrRefCounter(data);
     162
     163    pthread_mutex_unlock(&list->lock)
     164    ;
    149165
    150166    return list;
    … …  
    153169/*****************************************************************************/
    154170
    155 psDlist *psDlistAppend(psDlist *list, // list to add to; may be NULL
    156                        void *data) // data to add at end
     171psDlist *psDlistAppend(psDlist *list, void *data)
    157172{
    158173    return psDlistAdd(list, data, PS_DLIST_TAIL);
    … …  
    163178 * Remove an element from a list
    164179 */
    165 void *psDlistRemove(psDlist *list, // list to remove element from
    166                     void *data,  // data item to remove (or NULL)
    167                     int which)  // index of item, if known.
    168 // PS_DLIST_UNKNOWN, or PS_DLIST_HEAD,
    169 // or PS_DLIST_TAIL
     180void *psDlistRemove(psDlist *list, void *data,  int which)
    170181{
    171182    psDlistElem *elem = NULL;  // element to remove
    172     assert (list != NULL);
    173 
    174     if (data != NULL)
    175     {
    176         assert (which == PS_DLIST_UNKNOWN);
     183    if (list == NULL) {
     184        psError(__func__,"list parameter found to be NULL in %s",__func__);
     185        return NULL;
     186    }
     187
     188    // get exclusive access to list so that other threads will not get in the way.
     189    pthread_mutex_lock(&list->lock)
     190    ;
     191
     192    if (which == PS_DLIST_UNKNOWN) {
     193        // search list for the data item.
    177194
    178195        int i = 0;   // index
    179         for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next, i++) {
     196        for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next) {
    180197            if (ptr->data == data) {
    181                 return psDlistRemove(list, NULL, i);
     198                which = i;
     199                break;
    182200            }
    183         }
    184 
    185         psTrace(__FILE__, 5, "Failed to find 0x%x on psDlist 0x%x", data, list);
    186 
     201            i++;
     202        }
     203
     204        if (which == PS_DLIST_UNKNOWN) {
     205            psError(__func__, "Failed to find 0x%x on psDlist 0x%x in %s.", data, list,__func__);
     206            return NULL;
     207        }
     208    }
     209
     210    // position the list's cursor to the desired location
     211    dlistSetIterator(list,which,false);
     212    elem = dlistGetIterator(list);
     213
     214    if (elem == NULL) {
     215        psError(__func__, "Couldn't position to given index (%d) to remove element from list.",which);
    187216        return NULL;
    188217    }
    189218
    190     if (which == PS_DLIST_HEAD || which == 0)
    191     {
    192         if (list->head == NULL) {
    193             return NULL;
     219    list->size--;
     220
     221    if (elem->prev == NULL) { // head of list?
     222        list->head = elem->next;
     223    } else {
     224        elem->prev->next = elem->next;
     225    }
     226
     227    if (elem->next == NULL) { // tail of list?
     228        list->tail = elem->prev;
     229
     230        // removed tail, so iter should be the last element of list to keep it valid
     231        if (list->size > 0) {
     232            list->iter = list->tail;
     233            list->iterIndex = list->size - 1;
    194234        } else {
    195             elem = list->head;
    196 
    197             if (list->head->next != NULL) {
    198                 list->head->next->prev = NULL;
    199             }
    200             list->head = list->head->next;
    201             list->n--;
    202 
    203             if (list->head == NULL) {
    204                 list->tail = NULL;
    205             }
    206         }
    207     } else if (which == PS_DLIST_TAIL || which == list->n - 1)
    208     {
    209         if (list->tail == NULL) {
    210             return NULL;
    211         } else {
    212             elem = list->tail;
    213             if (list->tail->prev != NULL) {
    214                 list->tail->prev->next = NULL;
    215             }
    216             list->tail = list->tail->prev;
    217             list->n--;
    218 
    219             if (list->tail == NULL) {
    220                 list->head = NULL;
    221             }
    222         }
    223     } else if (which != PS_DLIST_UNKNOWN)
    224     { // an index in the middle of the list
    225         assert (which != 0 && which != list->n - 1);
    226 
    227         if (which < 0 || which >= list->n) { // out of bounds
    228             psError(__func__,"Index %d is not in range [0..%d] for list 0x%x", which, list->n,
    229                     list);
    230             return NULL;
    231         }
    232 
    233         int i = 0;   // index
    234         for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next, i++) {
    235             if (i == which) {
    236                 ptr->prev->next = ptr->next;
    237                 ptr->next->prev = ptr->prev;
    238 
    239                 elem = ptr;
    240             }
    241         }
    242     }
     235            list->iter = ITER_INIT_TAIL;
     236        }
     237    } else {
     238        elem->next->prev = elem->prev;
     239        list->iter = elem->next;
     240    }
     241
     242    pthread_mutex_unlock(&list->lock)
     243    ;
     244
    243245    /*
    244246     * OK, delete list element and return the data
    245247     */
    246     assert (elem != NULL);
    247248    data = elem->data;
    248249    dlistElemFree(elem);
    249 
    250250    return psMemDecrRefCounter(data);
    251251}
    252252
    253 /*
    254  * Retrieve an element from the list, or iterate over list.
    255  *
    256  * If which is psDlist{Next,Prev} return the next/previous
    257  * data and move the iteration cursor
    258  *
    259  * If which is psDlist{Head,Tail} initialize the iteration pointer
    260  * and return the head/tail
    261  *
    262  * Otherwise, return the desired element
    263  */
    264 #define ITER_INIT_HEAD ((void *)1) // next iteration should return head
    265 #define ITER_INIT_TAIL ((void *)2) // next iteration should return tail
    266 
    267 void *psDlistGet(const psDlist *list, int which)
    268 {
     253void psDlistSetIterator(psDlist *list, int where)
     254{
     255    dlistSetIterator(list,where,true);
     256}
     257
     258void dlistSetIterator(psDlist* list, int where, bool lockList)
     259{
     260    psDlistElem* cursor;
     261    int position;
     262
    269263    if (list == NULL) {
    270264        psError(__func__,"Unexpected null pointer for psDlist parameter (%s:%d).",__FILE__,__LINE__);
     265        return;
     266    }
     267
     268    if (where == PS_DLIST_CURRENT) {
     269        return;
     270    }
     271
     272    if (lockList) {
     273        pthread_mutex_lock(&list->lock)
     274        ;  // don't want the list changing on us while we move about
     275    }
     276
     277    if (where >= list->size) {
     278        psError(__func__,"Tried to access an element beyond list end. "
     279                "Moved to last element of list instead.");
     280        where = list->size-1;
     281
     282        switch (where) {
     283        case PS_DLIST_HEAD:
     284            list->iter = ITER_INIT_HEAD;
     285            break;
     286
     287        case PS_DLIST_TAIL:
     288            list->iter = ITER_INIT_TAIL;
     289            break;
     290
     291        case PS_DLIST_PREVIOUS:
     292            cursor = dlistGetIterator(list);
     293            position = dlistGetIteratorIndex(list);
     294
     295            if (cursor == NULL) { // list empty?
     296                ((psDlist *)list)->iter = ITER_INIT_HEAD;
     297            } else {
     298                if (cursor->prev != NULL) { // don't go past head
     299                    list->iter = cursor->prev;
     300                    list->iterIndex = position-1;
     301                    break;
     302                }
     303            }
     304
     305        case PS_DLIST_NEXT:
     306            cursor = dlistGetIterator(list);
     307            position = dlistGetIteratorIndex(list);
     308
     309            if (cursor == NULL) { // list empty?
     310                ((psDlist *)list)->iter = ITER_INIT_HEAD;
     311            } else {
     312                if (cursor->next != NULL) { // don't go pase tail
     313                    list->iter = cursor->next;
     314                    list->iterIndex = position+1;
     315                    break;
     316                }
     317            }
     318
     319        case PS_DLIST_UNKNOWN:
     320            psError(__func__,"Can't move to the PS_DLIST_UNKNOWN position.  Not moving the iterator position.");
     321            break;
     322        case PS_DLIST_CURRENT:
     323            break;
     324
     325        default:
     326            if (where < PS_DLIST_HEAD) { // bascially same as PS_DLIST_UNKNOWN above
     327                psError(__func__,"Can't move to an unknown position.  Not moving the iterator position.");
     328                break;
     329            } else {
     330                int position = dlistGetIteratorIndex(list);
     331
     332                if (where < position) {
     333                    int diff = position-where;
     334                    for (int count=0;count < diff; count++) {
     335                        dlistSetIterator(list,PS_DLIST_PREVIOUS,false);
     336                    }
     337                } else {
     338                    int diff = where-position;
     339                    for (int count=0;count < diff; count++) {
     340                        dlistSetIterator(list,PS_DLIST_NEXT,false);
     341                    }
     342                }
     343            }
     344            break;
     345        }
     346
     347        if (lockList) {
     348            pthread_mutex_unlock(&list->lock)
     349            ;
     350        }
     351    }
     352}
     353
     354psDlistElem* dlistGetIterator(psDlist* list)
     355{
     356    if (list->iter == ITER_INIT_HEAD) {
     357        return list->head;
     358    } else if (list->iter == ITER_INIT_TAIL) {
     359        return list->tail;
     360    } else {
     361        return list->iter;
     362    }
     363}
     364
     365int dlistGetIteratorIndex(psDlist* list)
     366{
     367    if (list->iter == ITER_INIT_HEAD) {
     368        return 0;
     369    } else if (list->iter == ITER_INIT_TAIL) {
     370        return list->size-1;
     371    } else {
     372        return list->iterIndex;
     373    }
     374}
     375
     376void* psDlistGet(psDlist* list,int which)
     377{
     378    psDlistElem* element;
     379
     380    psDlistSetIterator(list,which);
     381    element = dlistGetIterator(list);
     382
     383    if (element == NULL) {
    271384        return NULL;
    272     }
    273 
    274     switch (which) {
    275     case PS_DLIST_HEAD:
    276         ((psDlist *)list)->iter = ITER_INIT_HEAD;
    277         return (list->head == NULL) ? NULL : list->head->data;
    278 
    279     case PS_DLIST_TAIL:
    280         ((psDlist *)list)->iter = ITER_INIT_TAIL;
    281         return (list->tail == NULL) ? NULL : list->tail->data;
    282 
    283     case PS_DLIST_PREVIOUS:  // use iterator
    284     case PS_DLIST_NEXT:
    285         if (list->iter == NULL) {
    286             return NULL;
    287         } else if (list->iter == ITER_INIT_HEAD) {
    288             ((psDlist *)list)->iter = list->head;
    289         } else if (list->iter == ITER_INIT_TAIL) {
    290             ((psDlist *)list)->iter = list->tail;
    291         } else if (which == PS_DLIST_PREVIOUS) {
    292             ((psDlist *)list)->iter = list->iter->prev;
    293         } else if (which == PS_DLIST_NEXT) {
    294             ((psDlist *)list)->iter = list->iter->next;
    295         } else {
    296             psAbort(__func__,"Unreachable line was reached in %s:%d?",__FILE__,__LINE__);
    297         }
    298 
    299         if (list->iter == NULL) {
    300             return NULL;
    301         }
    302         return list->iter->data; // XXX what if data is NULL?
    303 
    304         break;
    305     default:
    306         if (which < 0) {
    307             psError(__func__,"the position is invalid for %s",__func__);
    308             return NULL;
    309         }
    310         ((psDlist *)list)->iter = list->head;
    311         for (int i=0;i<which;i++) {}
    312 
    313         if (list->iter == NULL) {
    314             return NULL;
    315         }
    316         return list->iter->data; // XXX what if data is NULL?
    317     }
    318 }
    319 
    320 psDlistElem* dlistGetIterator(psDlist* list)
    321 {
    322 
    323 
    324     /*
    325      * Some wrappers for those iteration calls using psDlistGet.
    326      *
    327      * First a call to set the iteration pointer to the head of the list
    328      */
    329     void psDlistSetIterator(psDlist *list,
    330                             int where) {
    331         if (where != PS_DLIST_HEAD && where != PS_DLIST_TAIL) {
    332             psError(__func__, "Invalid where argument: %d; assuming PS_DLIST_HEAD", where);
    333             where = PS_DLIST_HEAD;
    334         }
    335 
    336         psDlistGet(list, where); // initialise iterator at head/tail
    337     }
    338 
    339     /*
    340      * and now return the previous/next element of the list
    341      */
    342     void *psDlistGetNext(psDlist *list) {
    343         return psDlistGet(list, PS_DLIST_NEXT);
    344     }
    345 
    346     void *psDlistGetPrevious(psDlist *list) {
    347         return psDlistGet(list, PS_DLIST_PREVIOUS);
    348     }
    349 
    350     void *psDlistGetCurrent(psDlist *list) {
    351         return psDlistGet(list, PS_DLIST_CURRENT);
    352     }
    353 
    354     #if 0
    355     /*
    356      * Convert a psDlist to/from a psVoidPtrArray
    357      */
    358     psVoidPtrArray *psDlistToArray(psDlist *restrict dlist) {
    359         if (dlist == NULL) {
    360             return NULL;
    361         }
    362 
    363         psVoidPtrArray *restrict arr = psVoidPtrArrayAlloc(dlist->n, dlist->n);
    364 
    365         psDlistElem *ptr = dlist->head;
    366         for (int i = 0, n = dlist->n; i < n; i++) {
    367             arr->arr[i] = ptr->data;
    368 
    369             ptr->data = NULL;
    370             ptr = ptr->next;
    371         }
    372 
    373         psDlistFree(dlist, NULL);
    374 
    375         return arr;
    376     }
    377 
    378     psDlist *psArrayToDlist(psVoidPtrArray *arr) {
    379         psDlist *list = psDlistAlloc(NULL); // list of elements
    380 
    381         for (int i = 0, n = arr->n; i < n; i++) {
    382             psDlistAppend(list,
    383                           psMemDecrRefCounter(arr->arr[i])); // it's already Incr
    384             arr->arr[i] = NULL;
    385         }
    386 
    387         psVoidPtrArrayFree(arr, NULL);
    388 
    389         return list;
    390     }
    391 
    392     #endif
     385    } else {
     386        return element->data;
     387    }
     388}
     389/*
     390 * and now return the previous/next element of the list
     391 */
     392void *psDlistGetNext(psDlist *list)
     393{
     394    return psDlistGet(list, PS_DLIST_NEXT);
     395}
     396
     397void *psDlistGetPrevious(psDlist *list)
     398{
     399    return psDlistGet(list, PS_DLIST_PREVIOUS);
     400}
     401
     402void *psDlistGetCurrent(psDlist *list)
     403{
     404    return psDlistGet(list, PS_DLIST_CURRENT);
     405}
     406
     407#if 0
     408/*
     409 * Convert a psDlist to/from a psVoidPtrArray
     410 */
     411psVoidPtrArray *psDlistToArray(psDlist *restrict dlist)
     412{
     413    if (dlist == NULL) {
     414        return NULL;
     415    }
     416
     417    psVoidPtrArray *restrict arr = psVoidPtrArrayAlloc(dlist->size, dlist->size);
     418
     419    psDlistElem *ptr = dlist->head;
     420    for (int i = 0, n = dlist->size; i < n; i++) {
     421        arr->arr[i] = ptr->data;
     422
     423        ptr->data = NULL;
     424        ptr = ptr->next;
     425    }
     426
     427    psDlistFree(dlist, NULL);
     428
     429    return arr;
     430}
     431
     432psDlist *psArrayToDlist(psVoidPtrArray *arr)
     433{
     434    psDlist *list = psDlistAlloc(NULL); // list of elements
     435
     436    for (int i = 0, n = arr->size; i < n; i++) {
     437        psDlistAppend(list,
     438                      psMemDecrRefCounter(arr->arr[i])); // it's already Incr
     439        arr->arr[i] = NULL;
     440    }
     441
     442    psVoidPtrArrayFree(arr, NULL);
     443
     444    return list;
     445}
     446
     447#endif
Note: See TracChangeset for help on using the changeset viewer.