IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Ignore:
Timestamp:
Dec 9, 2004, 4:50:16 PM (22 years ago)
Author:
desonia
Message:

Changed psList API for iterators, etc.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/psLib/src/collections/psList.c

    r2375 r2681  
    66 *  @author Robert Daniel DeSonia, MHPCC
    77 *
    8  *  @version $Revision: 1.22 $ $Name: not supported by cvs2svn $
    9  *  @date $Date: 2004-11-16 20:00:20 $
     8 *  @version $Revision: 1.23 $ $Name: not supported by cvs2svn $
     9 *  @date $Date: 2004-12-10 02:50:14 $
    1010 *
    1111 *  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
    … …  
    2929
    3030// private functions.
    31 static psListElem* listGetIterator(psList* list);
    32 static psS32 listGetIteratorIndex(psList* list);
    33 static void listSetIterator(psList* list, psS32 where, psBool lockList);
    3431static void listFree(psList* list);
    35 
    36 psList* psListAlloc(psPtr data)
    37 {
    38     psList* list = psAlloc(sizeof(psList));
    39 
    40     p_psMemSetDeallocator(list, (psFreeFcn) listFree);
    41 
    42     list->size = 0;
    43     list->head = list->tail = NULL;
    44     list->p_iter = ITER_INIT_HEAD;
    45     list->p_iterIndex = PS_LIST_HEAD;
    46 
    47     pthread_mutex_init(&(list->lock), NULL)
    48     ;
    49 
    50     if (data != NULL) {
    51         psListAdd(list, PS_LIST_TAIL, data);
    52     }
    53 
    54     return list;
    55 }
     32static void listIteratorFree(psListIterator* iter);
     33static psBool listIteratorRemove(psListIterator* iterator);
    5634
    5735static void listFree(psList* list)
    … …  
    6442    ;
    6543
     44    psFree(list->iterators);
     45
    6646    for (psListElem* ptr = list->head; ptr != NULL;) {
    6747        psListElem* next = ptr->next;
    … …  
    8161}
    8262
    83 psBool psListAdd(psList* list, psS32 location, psPtr data)
    84 {
    85     psListElem* position;
    86     psListElem* elem;
    87     psS32 cursorIndex = 0;
    88 
    89     if (list == NULL) {
    90         return false;
    91     }
    92 
    93     if (data == NULL) {
    94         return false;
    95     }
    96 
    97     if (location <= PS_LIST_UNKNOWN) {
    98         // / XXX What is the better way to communicate this failure to the caller?
    99         psLogMsg(__func__, PS_LOG_WARN, "The given insert location (%i) for psListAdd is invalid.", location);
    100         return false;
    101     }
    102 
    103     elem = psAlloc(sizeof(psListElem));
     63static void listIteratorFree(psListIterator* iter)
     64{
     65    if (iter == NULL) {
     66        return;
     67    }
     68
     69    // remove this iterator from the parent list
     70    psArrayRemove(iter->list->iterators,iter);
     71
     72}
     73
     74static psBool listIteratorRemove(psListIterator* iterator)
     75{
     76    if (iterator == NULL) {
     77        return false;
     78    }
     79
     80    psListElem* elem = iterator->cursor;
     81    psList* list = iterator->list;
     82    int index = iterator->index;
    10483
    10584    pthread_mutex_lock(&list->lock)
    10685    ;
    10786
    108     if (location > 0 && location > list->size) {
    109         psLogMsg(__func__, PS_LOG_WARN,
    110                  "Invalid index %d (only %d elements in psList); assuming tail.", location, list->size);
    111         location = PS_LIST_TAIL;
    112     }
    113 
    114     if (location == PS_LIST_TAIL || list->size == 0) {
    115         // insert the element at the end of the list
    116         elem->prev = list->tail;
    117         elem->next = NULL;
    118 
    119         if (list->tail != NULL) {
    120             list->tail->next = elem;
    121         }
    122 
    123         if (list->head == NULL) {
    124             list->head = elem;
    125         }
    126         list->tail = elem;
    127 
    128         list->size++;
    129         list->p_iter = elem;
    130         list->p_iterIndex = list->size - 1;
    131     } else {
    132         // move ourselves to the given position
    133         listSetIterator(list, location, false);
    134         position = listGetIterator(list);
    135         cursorIndex = listGetIteratorIndex(list);
    136 
    137         if (position == NULL) {
    138             psError(PS_ERR_BAD_PARAMETER_VALUE, true,
    139                     "Failed to move cursor to specified location (%d)", location);
    140             position = list->head;         // since we no list->size != 0, this must be non-NULL
    141         }
    142         // insert our new element in front of the given position
    143         elem->prev = position->prev;
    144         elem->next = position;
    145         position->prev = elem;
    146 
    147         if (elem->prev == NULL) {          // must be front of list
    148             list->head = elem;
    149         } else {
    150             elem->prev->next = elem;
    151         }
    152 
    153         list->size++;
    154         list->p_iter = elem;
    155         list->p_iterIndex = cursorIndex;
    156     }
    157 
    158     elem->data = psMemIncrRefCounter(data);
    159 
    160     pthread_mutex_unlock(&list->lock)
    161     ;
    162 
    163     return true;
    164 }
    165 
    166 
    167 /*
    168  * Remove an element from a list
    169  */
    170 psBool psListRemove(psList* list, psS32 location, psPtr data)
    171 {
    172     psListElem* elem = NULL;    // element to remove
    173     psS32 cursorIndex = 0;
    174 
    175     if (list == NULL) {
    176         psError(PS_ERR_BAD_PARAMETER_NULL, true, "list parameter found to be NULL.");
    177         return false;
    178     }
    179     // get exclusive access to list so that other threads will not get in the way.
    180     pthread_mutex_lock(&list->lock)
    181     ;
    182 
    183     if (location == PS_LIST_UNKNOWN) {
    184         // search list for the data item.
    185 
    186         psS32 i = 0;              // index
    187 
    188         for (psListElem* ptr = list->head; ptr != NULL; ptr = ptr->next) {
    189             if (ptr->data == data) {
    190                 location = i;
    191                 break;
    192             }
    193             i++;
    194         }
    195 
    196         if (location == PS_LIST_UNKNOWN) {
    197             psError(PS_ERR_BAD_PARAMETER_VALUE, true, "Failed to find item in given psList.");
    198             pthread_mutex_unlock(&list->lock)
    199             ;
    200             return false;
    201         }
    202     }
    203     // position the list's cursor to the desired location
    204     listSetIterator(list, location, false);
    205     elem = listGetIterator(list);
    206     cursorIndex = listGetIteratorIndex(list);
    207 
    208     if (elem == NULL) {
    209         psError(PS_ERR_BAD_PARAMETER_VALUE, true,
    210                 "Couldn't position to given index (%d) to remove element from list.", location);
    211         pthread_mutex_unlock(&list->lock)
    212         ;
    213         return false;
    214     }
    215 
    216     list->size--;
    217 
    218     if (elem->prev == NULL) {              // head of list?
     87    if (elem == list->head) {        // head of list?
    21988        list->head = elem->next;
    22089    } else {
    … …  
    22291    }
    22392
    224     if (elem->next == NULL) {              // tail of list?
     93    if (elem == list->tail) {        // tail of list?
    22594        list->tail = elem->prev;
    226 
    227         // removed tail, so iter should be the last element of list to keep it valid
    228         if (list->size > 0) {
    229             list->p_iter = list->tail;
    230             list->p_iterIndex = list->size - 1;
     95    } else {
     96        elem->next->prev = elem->prev;
     97    }
     98
     99    psArray* iterators = list->iterators;
     100    for (int i = 0; i < iterators->n; i++) {
     101        psListIterator* iter = (psListIterator*) iterators->data[i];
     102        if (iter->cursor == elem) {
     103            iter->cursor = NULL;
     104        } else if (iter->index > index) {
     105            iter->index--;
     106        }
     107    }
     108
     109    list->size--;
     110
     111    pthread_mutex_unlock(&list->lock)
     112    ;
     113
     114    // OK, delete orphaned list element and its data
     115    psFree(elem->data);
     116    psFree(elem);
     117
     118    return true;
     119}
     120
     121psList* psListAlloc(psPtr data)
     122{
     123    psList* list = psAlloc(sizeof(psList));
     124
     125    p_psMemSetDeallocator(list, (psFreeFcn) listFree);
     126
     127    list->size = 0;
     128    list->head = list->tail = NULL;
     129    list->iterators = psArrayAlloc(16);
     130
     131    // create a default iterator
     132    list->iterators->data[0] = psListIteratorAlloc(list,PS_LIST_HEAD);
     133    list->iterators->n = 1;
     134
     135    pthread_mutex_init(&(list->lock), NULL)
     136    ;
     137
     138    if (data != NULL) {
     139        psListAdd(list, PS_LIST_TAIL, data);
     140    }
     141
     142    return list;
     143}
     144
     145psListIterator* psListIteratorAlloc(psList* list, int location)
     146{
     147    psListIterator* iter = psAlloc(sizeof(psListIterator));
     148
     149    p_psMemSetDeallocator(iter, (psFreeFcn) listIteratorFree);
     150
     151    // initialize the attributes
     152    iter->list = list;
     153    iter->cursor = NULL;
     154    iter->index = 0;
     155    iter->offEnd = false;
     156
     157    // add to the list's array of iterators
     158    psArray* listIterators = list->iterators;
     159    int num = listIterators->n;
     160    if ( num >= listIterators->nalloc) {
     161        // need to resize the array to make more room for another iterator.
     162        list->iterators = psArrayRealloc(listIterators,listIterators->nalloc*2);
     163        listIterators = list->iterators;
     164    }
     165    listIterators->data[num] = iter;
     166    listIterators->n = num+1;
     167
     168    if (! psListIteratorSet(iter,location)) {
     169        psFree(iter);
     170        iter = NULL;
     171    }
     172
     173    return iter;
     174}
     175
     176psBool psListIteratorSet(psListIterator* iterator,
     177                         int location)
     178{
     179    if (iterator == NULL) {
     180        return false;
     181    }
     182
     183    psList* list = iterator->list;
     184
     185    if (location >= list->size) {
     186        psLogMsg(__func__, PS_LOG_WARN,
     187                 "Specified index, %d, is beyond the end of the psList, which "
     188                 "has only %d elements.  Assuming tail.",
     189                 location, list->size);
     190        location = PS_LIST_TAIL;
     191    }
     192
     193    if (location == PS_LIST_TAIL) {
     194        iterator->cursor = list->tail;
     195        iterator->index = list->size - 1;
     196        iterator->offEnd = false;
     197        return true;
     198    }
     199
     200    if (location <= 0) {   // Invalid index
     201        return false;
     202    }
     203
     204
     205    psListElem* cursor = iterator->cursor;
     206    int index = iterator->index;
     207    if (cursor == NULL) {      // set the cursor to the head if it is NULL
     208        if (location > list->size/2) { // closer to tail or head?
     209            cursor = list->tail;
     210            index = list->size - 1;
    231211        } else {
    232             list->p_iter = ITER_INIT_TAIL;
     212            cursor = list->head;
     213            index = 0;
     214        }
     215    }
     216
     217    if (location < index) {
     218        psS32 diff = index - location;
     219
     220        for (psS32 count = 0; count < diff; count++) {
     221            cursor = cursor->prev; // shouldn't need to check for NULL
    233222        }
    234223    } else {
    235         elem->next->prev = elem->prev;
    236         list->p_iter = elem->next;
    237         list->p_iterIndex = cursorIndex;
     224        psS32 diff = location - index;
     225
     226        for (psS32 count = 0; count < diff; count++) {
     227            cursor = cursor->next; // shouldn't need to check for NULL
     228        }
     229    }
     230    iterator->cursor = cursor;
     231    iterator->index = location;
     232    iterator->offEnd = false;
     233
     234    return true;
     235}
     236
     237psBool psListAdd(psList* list, psS32 location, psPtr data)
     238{
     239
     240    if (list == NULL) {
     241        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     242                PS_ERRORTEXT_psList_LIST_NULL);
     243        return false;
     244    }
     245
     246    if (data == NULL) {
     247        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     248                PS_ERRORTEXT_psList_DATA_NULL);
     249        return false;
     250    }
     251
     252    // move ourselves to the given position
     253    if (list->iterators->n < 1 ||
     254            ! psListIteratorSet(list->iterators->data[0],location)) {
     255        // oh no, I can't find where to add this!
     256        psError(PS_ERR_UNKNOWN, false,
     257                PS_ERRORTEXT_psList_LOCATION_INVALID,
     258                location);
     259        return false;
     260    }
     261
     262    if (location == PS_LIST_TAIL) {
     263        // insert the element at the end of the list
     264        return psListAddAfter(list->iterators->data[0],data);
     265    } else {
     266        return psListAddBefore(list->iterators->data[0],data);
     267    }
     268}
     269
     270bool psListAddAfter(psListIterator* iterator, void* data)
     271{
     272    if (data == NULL) {
     273        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     274                PS_ERRORTEXT_psList_DATA_NULL);
     275        return false;
     276    }
     277
     278    if (iterator == NULL) {
     279        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     280                PS_ERRORTEXT_psList_ITERATOR_NULL);
     281        return false;
     282    }
     283
     284    psListElem* cursor = iterator->cursor;
     285
     286    if (cursor == NULL) {
     287        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
     288                PS_ERRORTEXT_psList_ITERATOR_INVALID);
     289        return false;
     290    }
     291
     292    psList* list = iterator->list;
     293    psListElem* elem = psAlloc(sizeof(psListElem));
     294
     295    pthread_mutex_lock(&list->lock)
     296    ;
     297
     298    // set the new list element's attributes
     299    elem->prev = cursor;
     300    elem->next = cursor->next;
     301    elem->data = data;
     302
     303    cursor->next = elem;
     304    list->size++;
     305
     306    if (cursor == list->tail) {
     307        list->tail = elem;
     308    }
     309
     310    psArray* iterators = list->iterators;
     311    int index = iterator->index;
     312    for (int i = 0; i < iterators->n; i++) {
     313        psListIterator* iter = (psListIterator*) iterators->data[i];
     314        if (iter->index > index) {
     315            iter->index++;
     316        }
    238317    }
    239318
    … …  
    241320    ;
    242321
    243     // OK, delete list element and its data
    244     psFree(elem->data);
    245     psFree(elem);
    246 
    247322    return true;
    248323}
    249324
    250 void psListSetIterator(psList* list, psS32 where)
    251 {
    252     listSetIterator(list, where, true);
    253 }
    254 
    255 static void listSetIterator(psList* list, psS32 where, psBool lockList)
    256 {
    257     psListElem* cursor;
    258     psS32 position;
    259 
     325bool psListAddBefore(psListIterator* iterator, void* data)
     326{
     327    if (data == NULL) {
     328        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     329                PS_ERRORTEXT_psList_DATA_NULL);
     330        return false;
     331    }
     332
     333    if (iterator == NULL) {
     334        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     335                PS_ERRORTEXT_psList_ITERATOR_NULL);
     336        return false;
     337    }
     338
     339    psListElem* cursor = iterator->cursor;
     340
     341    if (cursor == NULL) {
     342        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
     343                PS_ERRORTEXT_psList_ITERATOR_INVALID);
     344        return false;
     345    }
     346
     347    psList* list = iterator->list;
     348    psListElem* elem = psAlloc(sizeof(psListElem));
     349
     350    pthread_mutex_lock(&list->lock)
     351    ;
     352
     353    // set the new list element's attributes
     354    elem->prev = cursor->prev;
     355    elem->next = cursor;
     356    elem->data = data;
     357
     358    cursor->prev = elem;
     359    list->size++;
     360
     361    if (cursor == list->head) {
     362        list->head = elem;
     363    }
     364
     365    psArray* iterators = list->iterators;
     366    int index = iterator->index;
     367    for (int i = 0; i < iterators->n; i++) {
     368        psListIterator* iter = (psListIterator*) iterators->data[i];
     369        if (iter->index >= index) {
     370            iter->index++;
     371        }
     372    }
     373
     374    pthread_mutex_unlock(&list->lock)
     375    ;
     376
     377    return true;
     378}
     379
     380psBool psListRemove(psList* list,
     381                    psS32 location)
     382{
    260383    if (list == NULL) {
    261384        psError(PS_ERR_BAD_PARAMETER_NULL, true,
    262                 "Unexpected null pointer for psList parameter.");
    263         return;
    264     }
    265 
    266     if (where == PS_LIST_CURRENT) {
    267         return;
    268     }
    269 
    270     if (lockList) {
    271         pthread_mutex_lock(&list->lock)
    272         ;
    273         // don't want the list changing on us while we move about
    274     }
    275 
    276     if (where >= (psS32)list->size) {
    277         list->p_iter = NULL;
    278         if (lockList) {
    279             pthread_mutex_unlock(&list->lock)
    280             ;
    281         }
    282         return;
    283     }
    284 
    285     switch (where) {
    286     case PS_LIST_HEAD:
    287         list->p_iter = ITER_INIT_HEAD;
    288         break;
    289 
    290     case PS_LIST_TAIL:
    291         list->p_iter = ITER_INIT_TAIL;
    292         break;
    293 
    294     case PS_LIST_PREVIOUS:
    295         cursor = listGetIterator(list);
    296         position = listGetIteratorIndex(list);
    297 
    298         if (cursor != NULL) {
    299             list->p_iter = cursor->prev;
    300             list->p_iterIndex = position - 1;
    301         }
    302         break;
    303 
    304     case PS_LIST_NEXT:
    305         cursor = listGetIterator(list);
    306         position = listGetIteratorIndex(list);
    307 
    308         if (cursor != NULL) {
    309             list->p_iter = cursor->next;
    310             list->p_iterIndex = position + 1;
    311         }
    312         break;
    313 
    314     case PS_LIST_CURRENT:
    315         break;
    316 
    317     default:
    318         if (where <= PS_LIST_HEAD) {   // bascially same as PS_LIST_UNKNOWN above
    319             psError(PS_ERR_BAD_PARAMETER_VALUE, true,
    320                     "Can't move to an unknown position.  Not moving the iterator position.");
    321         } else {
    322             cursor = listGetIterator(list);
    323             if (cursor == NULL) {      // reset the iterator if it is invalid
    324                 list->p_iter = ITER_INIT_HEAD;
    325                 list->p_iterIndex = 0;
    326             }
    327 
    328             psS32 position = listGetIteratorIndex(list);
    329 
    330             if (where < position) {
    331                 psS32 diff = position - where;
    332 
    333                 for (psS32 count = 0; count < diff; count++) {
    334                     listSetIterator(list, PS_LIST_PREVIOUS, false);
    335                 }
    336             } else {
    337                 psS32 diff = where - position;
    338 
    339                 for (psS32 count = 0; count < diff; count++) {
    340                     listSetIterator(list, PS_LIST_NEXT, false);
    341                 }
    342             }
    343         }
    344         break;
    345     }
    346 
    347     if (lockList) {
    348         pthread_mutex_unlock(&list->lock)
    349         ;
    350     }
    351 }
    352 
    353 psListElem* listGetIterator(psList* list)
     385                PS_ERRORTEXT_psList_LIST_NULL);
     386        return false;
     387    }
     388
     389    // move ourselves to the given position
     390    psListIterator* defaultIterator = list->iterators->data[0];
     391    if (list->iterators->n < 1 ||
     392            ! psListIteratorSet(defaultIterator,location)) {
     393        // oh no, I can't find where to add this!
     394        psError(PS_ERR_UNKNOWN, false,
     395                PS_ERRORTEXT_psList_LOCATION_INVALID,
     396                location);
     397        return false;
     398    }
     399
     400    return listIteratorRemove(defaultIterator);
     401}
     402
     403psBool psListRemoveData(psList* list,
     404                        psPtr data)
    354405{
    355406    if (list == NULL) {
     407        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     408                PS_ERRORTEXT_psList_LIST_NULL);
     409        return false;
     410    }
     411
     412    if (data == NULL) {
     413        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     414                PS_ERRORTEXT_psList_DATA_NULL);
     415        return false;
     416    }
     417
     418    psListIterator* iterator = list->iterators->data[0];
     419    psListIteratorSet(iterator,PS_LIST_HEAD);
     420
     421    psPtr iteratorData = psListGetNext(iterator);
     422    while (iteratorData != NULL && iteratorData != data) {
     423        iteratorData = psListGetNext(iterator);
     424    }
     425
     426    if (iteratorData == NULL) {
     427        psError(PS_ERR_BAD_PARAMETER_NULL, true,
     428                PS_ERRORTEXT_psList_DATA_NOT_FOUND);
     429        return false;
     430    }
     431
     432    return listIteratorRemove(iterator);
     433}
     434
     435psPtr psListGet(psList* list, psS32 location)
     436{
     437    psListIterator* iterator = list->iterators->data[0];
     438
     439    if (! psListIteratorSet(iterator,location)) {
     440        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
     441                PS_ERRORTEXT_psList_LOCATION_INVALID,
     442                location);
    356443        return NULL;
    357444    }
    358445
    359     if (list->p_iter == ITER_INIT_HEAD) {
    360         return list->head;
    361     } else if (list->p_iter == ITER_INIT_TAIL) {
    362         return list->tail;
    363     } else {
    364         return list->p_iter;
    365     }
    366 }
    367 
    368 psS32 listGetIteratorIndex(psList* list)
    369 {
    370     if (list->p_iter == ITER_INIT_HEAD) {
    371         return 0;
    372     } else if (list->p_iter == ITER_INIT_TAIL) {
    373         return list->size - 1;
    374     } else {
    375         return list->p_iterIndex;
    376     }
    377 }
    378 
    379 psPtr psListGet(psList* list, psS32 location)
    380 {
    381     psListElem* element;
    382 
    383     psListSetIterator(list, location);
    384     element = listGetIterator(list);
    385 
    386     if (element == NULL) {
    387         return NULL;
    388     } else {
    389         return element->data;
    390     }
     446    return iterator->cursor->data;
    391447}
    392448
    … …  
    394450 * and now return the previous/next element of the list
    395451 */
    396 psPtr psListGetNext(psList* list)
    397 {
    398     return psListGet(list, PS_LIST_NEXT);
    399 }
    400 
    401 psPtr psListGetPrevious(psList* list)
    402 {
    403     return psListGet(list, PS_LIST_PREVIOUS);
    404 }
    405 
    406 psPtr psListGetCurrent(psList* list)
    407 {
    408     return psListGet(list, PS_LIST_CURRENT);
     452psPtr psListGetNext(psListIterator* iterator)
     453{
     454    if (iterator == NULL || iterator->cursor == NULL) {
     455        return NULL;
     456    }
     457
     458    psPtr data = iterator->cursor->data;
     459
     460    iterator->cursor = iterator->cursor->next;
     461    iterator->index++;
     462    if (iterator->cursor == NULL) {
     463        iterator->offEnd = true;
     464    }
     465
     466    return data;
     467}
     468
     469psPtr psListGetPrevious(psListIterator* iterator)
     470{
     471    if (iterator == NULL || iterator->cursor == NULL) {
     472        return NULL;
     473    }
     474
     475    psPtr data = iterator->cursor->data;
     476
     477    iterator->cursor = iterator->cursor->prev;
     478    iterator->index--;
     479
     480    return data;
    409481}
    410482
    … …  
    467539    // convert to indexable vector for use by qsort.
    468540    arr = psListToArray(list);
     541    psArray* iterators = psMemIncrRefCounter(list->iterators);
    469542    psFree(list);
    470543
    … …  
    473546    // convert back to linked list
    474547    list = psArrayToList(arr);
     548    psFree(list->iterators);
     549    list->iterators = iterators;
    475550    psFree(arr);
    476551
     552    // sorting should invalidate all iterator positions.
     553    for (int i = 0; i < iterators->n; i++) {
     554        ((psListIterator*)iterators->data[i])->cursor = NULL;
     555    }
     556
    477557    return list;
    478558}
Note: See TracChangeset for help on using the changeset viewer.