linked_list.c

Go to the documentation of this file.
00001 
00014 /* ----------------------------------------------------------------- */
00015 
00016 #include <stdio.h>
00017 #include <stdlib.h>
00018 #include <errno.h>
00019 #include "linked_list.h"
00020 
00021 /* fwd declarations of internal locking functions */
00022 int cp_list_txlock(cp_list *list, int type);
00023 /* fwd declarations of internal locking functions */
00024 int cp_list_txunlock(cp_list *list);
00025 
00035 static cp_list_entry *cp_list_create_entry(cp_list *list, void *item);
00036 
00037 //static void cp_list_destroy_entry(cp_list *list, cp_list_entry *entry);
00038 
00043 static cp_list_entry *cp_list_insert_internal(cp_list *list, void *item);
00044 
00048 static cp_list_entry *cp_list_remove_internal(cp_list *list, cp_list_entry *entry);
00049 
00053 static cp_list_entry *cp_list_append_internal(cp_list *list, void *item);
00054 
00060 static cp_list_entry *cp_list_remove_head_internal(cp_list *list);
00061 
00067 static cp_list_entry *cp_list_remove_tail_internal(cp_list *list);
00068 
00069 
00070 cp_list *cp_list_create_internal(int mode, 
00071                                  cp_compare_fn compare_fn,
00072                                  cp_copy_fn copy_fn,
00073                                  cp_destructor_fn item_destructor,
00074                                  int is_view)
00075 {
00076     cp_list *list = NULL;
00077 
00078     list = (cp_list *) calloc(1, sizeof(cp_list));
00079     if (list == NULL) 
00080     {
00081         errno = ENOMEM;
00082         return NULL;
00083     }
00084 
00085     list->head       = NULL;
00086     list->tail       = NULL;
00087     list->compare_fn = compare_fn;
00088     list->copy_fn    = copy_fn;
00089     list->free_fn    = item_destructor;
00090     list->mode       = mode;
00091     list->items      = 0;
00092 
00093     list->is_view    = is_view;
00094 
00095     if (!(mode & COLLECTION_MODE_NOSYNC) && !is_view)
00096     {
00097         list->lock = malloc(sizeof(cp_lock));
00098         if (list->lock == NULL)
00099         {
00100             free(list);
00101             errno = ENOMEM;
00102             return NULL;
00103         }
00104         if (cp_lock_init(list->lock, NULL))
00105         {
00106             free(list->lock);
00107             free(list);
00108             return NULL;
00109         }
00110     }
00111 
00112     return list;
00113 }
00114 
00115 cp_list *cp_list_create()
00116 {
00117     return 
00118         cp_list_create_internal(COLLECTION_MODE_MULTIPLE_VALUES,
00119                 NULL, NULL, NULL, 0);
00120 }
00121 
00122 cp_list *cp_list_create_nosync()
00123 {
00124     return 
00125         cp_list_create_internal(COLLECTION_MODE_MULTIPLE_VALUES |
00126                                 COLLECTION_MODE_NOSYNC, 
00127                                 NULL, NULL, NULL, 0);
00128 }
00129 
00130 cp_list *cp_list_create_list(int mode, 
00131                              cp_compare_fn compare_fn, 
00132                              cp_copy_fn copy_fn,
00133                              cp_destructor_fn item_destructor)
00134 {
00135     return 
00136         cp_list_create_internal(mode, compare_fn, copy_fn, item_destructor, 0);
00137 }
00138 
00139 
00140 cp_list *cp_list_create_view(int mode, 
00141                              cp_compare_fn compare_fn, 
00142                              cp_copy_fn copy_fn,
00143                              cp_destructor_fn item_destructor,
00144                              cp_lock *lock)
00145 {
00146     cp_list *list = 
00147         cp_list_create_internal(mode, compare_fn, copy_fn, item_destructor, 1);
00148 
00149     list->lock = lock; //~~ test
00150 
00151     return list;
00152 }
00153 
00154 /* 
00155  * locking provides some protection if the list is being destroyed while it is
00156  * still in use. However if the lock causes a different thread to block the 
00157  * other thread is likely to crash when releasing the lock which will possibly
00158  * have been deallocated in the meanwhile. It is the applications 
00159  * responsibility to assure the list isn't being accessed and destroyed in
00160  * different threads simultaneously.
00161  */
00162 void cp_list_destroy_internal(cp_list *list, cp_destructor_fn fn, int mode)
00163 {
00164     cp_list_entry *curr, *next;
00165     int shared_pool;
00166 
00167     cp_list_txlock(list, COLLECTION_LOCK_WRITE);
00168     
00169     shared_pool = list->mempool && list->mempool->refcount > 1;
00170         
00171     curr = list->head;
00172     while (curr) 
00173     {
00174         next = curr->next;
00175         if ((mode & COLLECTION_MODE_DEEP) && fn)
00176             (*fn)(curr->item);
00177         if (list->mempool) 
00178         {
00179             if (shared_pool)
00180                 cp_mempool_free(list->mempool, curr);
00181         }
00182         else
00183             free(curr);
00184         curr = next;
00185     }
00186     cp_list_txunlock(list);
00187     
00188     if (list->lock && !list->is_view)
00189     {
00190         cp_lock_destroy(list->lock);
00191         free(list->lock);
00192     }
00193 
00194     if (list->mempool) cp_mempool_destroy(list->mempool);
00195 
00196     free(list);
00197 }
00198 
00199 void cp_list_destroy(cp_list *list)
00200 {
00201     cp_list_destroy_internal(list, list->free_fn, list->mode);
00202 }
00203 
00204 void cp_list_destroy_by_option(cp_list *list, int option)
00205 {
00206     cp_list_destroy_internal(list, list->free_fn, option);
00207 }
00208 
00209 void cp_list_destroy_custom(cp_list *list, cp_destructor_fn fn)
00210 {
00211     cp_list_destroy_internal(list, fn, list->mode | COLLECTION_MODE_DEEP);
00212 }
00213 
00214 long cp_list_item_count(cp_list *list)
00215 {
00216     return (list == NULL) ? 0 : list->items;
00217 }
00218 
00219 
00220 static cp_list_entry **cp_list_get_entry_ref(cp_list *list, void *item)
00221 {
00222     cp_list_entry **here = &list->head;
00223 
00224     while (*here != NULL && (*list->compare_fn)(item, (*here)->item)) 
00225         here = &(*here)-> next;
00226 
00227     return here;
00228 }
00229 
00230 void *cp_list_insert(cp_list *list, void *item)
00231 {
00232     cp_list_entry *entry, **lookup;
00233     void *res = NULL;
00234 
00235     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00236 
00237     entry = NULL;
00238     if (!(list->mode & COLLECTION_MODE_MULTIPLE_VALUES)) 
00239     {
00240         lookup = cp_list_get_entry_ref(list, item);
00241         if (lookup) entry = *lookup;
00242     }
00243     if (entry == NULL) entry = cp_list_insert_internal(list, item);
00244     if (entry) res = entry->item;
00245 
00246     cp_list_txunlock(list);
00247     
00248     return res;
00249 }
00250 
00251 void *cp_list_remove(cp_list *list, void *item)
00252 {
00253     void *res = NULL;
00254     cp_list_entry *here, *curr;
00255     int mvalbit = list->mode & COLLECTION_MODE_MULTIPLE_VALUES;
00256     int deepbit = list->mode & COLLECTION_MODE_DEEP;
00257 
00258     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00259 
00260     here = list->head;
00261     while (here != NULL) 
00262     {
00263         curr = here;
00264         here = here->next;
00265         if ((*list->compare_fn)(item, curr->item) == 0) 
00266         {
00267             cp_list_remove_internal(list, curr);
00268             if (deepbit && list->free_fn) (*list->free_fn)(curr->item);
00269             if (list->mempool)
00270                 cp_mempool_free(list->mempool, curr);
00271             else
00272                 free(curr);
00273     
00274             if (!mvalbit) break;
00275         }
00276     }
00277 
00278     cp_list_txunlock(list);
00279 
00280     return res;
00281 }
00282 
00283 void *cp_list_insert_after(cp_list *list, void *item, void *existing)
00284 {
00285     cp_list_entry **here, *entry;
00286 
00287     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00288 
00289     if (!((list->mode) & COLLECTION_MODE_MULTIPLE_VALUES))
00290     {
00291         here = cp_list_get_entry_ref(list, item);
00292         if (*here != NULL) 
00293         {
00294             cp_list_txunlock(list);
00295             return (*here)->item;
00296         }
00297     }
00298 
00299     entry = cp_list_create_entry(list, item);
00300     if (entry == NULL) 
00301     {
00302         cp_list_txunlock(list);
00303         return NULL;
00304     }
00305 
00306     here = cp_list_get_entry_ref(list, existing);
00307 
00308     if (*here == NULL) /* no match - append to end of list */
00309         here = &list->tail;
00310 
00311     entry->prev = *here;
00312     entry->next = (*here)->next;
00313     (*here)->next = entry;
00314 
00315     if (entry->next) 
00316         entry->next->prev = entry;
00317     else
00318         list->tail = entry;
00319     
00320     list->items++;
00321     
00322     cp_list_txunlock(list);
00323 
00324     return entry->item;
00325 }
00326 
00327 void *cp_list_insert_before(cp_list *list, void *item, void *existing)
00328 {
00329     cp_list_entry **here, *entry;
00330 
00331     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00332 
00333     if (!((list->mode) & COLLECTION_MODE_MULTIPLE_VALUES))
00334     {
00335         here = cp_list_get_entry_ref(list, item);
00336         if (*here != NULL) 
00337         {
00338             cp_list_txunlock(list);
00339             return (*here)->item;
00340         }
00341     }
00342 
00343     entry = cp_list_create_entry(list, item);
00344     if (entry == NULL) 
00345     {
00346         cp_list_txunlock(list);
00347         return NULL;
00348     }
00349 
00350     here = cp_list_get_entry_ref(list, existing);
00351 
00352     if (*here == NULL) /* no match - insert at top of list */
00353         here = &list->head;
00354         
00355     entry->next = *here;
00356     entry->prev = (*here)->prev;
00357     (*here)->prev = entry;
00358     if (entry->prev)
00359         entry->prev->next = entry;
00360     else
00361         list->head = entry;
00362 
00363     list->items++;
00364         
00365     cp_list_txunlock(list);
00366 
00367     return entry->item;
00368 }
00369 
00370 void *cp_list_search(cp_list *list, void *item)
00371 {
00372     cp_list_entry **here;
00373     void *res;
00374 
00375     if (cp_list_txlock(list, COLLECTION_LOCK_READ)) return NULL;
00376 
00377     here = cp_list_get_entry_ref(list, item);
00378     res = *here ? (*here)->item : NULL;
00379 
00380     cp_list_txunlock(list);
00381     
00382     return res;
00383 }
00384 
00385 int cp_list_callback(cp_list *l, int (*item_action)(void *, void *), void *id)
00386 {
00387     int rc = 0;
00388     cp_list_entry *curr;
00389 
00390     if ((rc = cp_list_txlock(l, COLLECTION_LOCK_READ))) return rc;
00391 
00392     for (curr = l->head; curr; curr = curr->next)
00393         if ((rc = (*item_action)(curr->item, id)))
00394             break;
00395 
00396     cp_list_txunlock(l);
00397 
00398     return rc;
00399 }
00400 
00401 
00402 void *cp_list_append(cp_list *list, void *item)
00403 {
00404     cp_list_entry **lookup, *entry;
00405     void *res = NULL;
00406 
00407     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00408 
00409     if (!(list->mode & COLLECTION_MODE_MULTIPLE_VALUES)) 
00410     {
00411         lookup = cp_list_get_entry_ref(list, item);
00412         if (lookup != NULL) 
00413         {
00414             cp_list_txunlock(list);
00415             return (*lookup)->item;
00416         }
00417     }
00418 
00419     entry = cp_list_append_internal(list, item);
00420     if (entry) res = entry->item;
00421 
00422     cp_list_txunlock(list);
00423 
00424     return res;
00425 }
00426 
00427 void *cp_list_get_head(cp_list *list)
00428 {
00429     void *item = NULL;
00430         
00431     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00432     if (list->head) item = list->head->item;
00433     cp_list_txunlock(list);
00434 
00435     return item;
00436 }
00437 
00438 void *cp_list_get_tail(cp_list *list)
00439 {
00440     void *item = NULL;
00441         
00442     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00443     if (list->tail) item = list->tail->item;
00444     cp_list_txunlock(list);
00445 
00446     return item;
00447 }
00448 
00449 
00450 void *cp_list_remove_head(cp_list *list)
00451 {
00452     cp_list_entry *old_head;
00453     void *res = NULL;
00454     
00455     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00456        
00457     old_head = cp_list_remove_head_internal(list);
00458     if (old_head) 
00459     {
00460         res = old_head->item;
00461         if ((list->mode & COLLECTION_MODE_DEEP) && list->free_fn)
00462             (*list->free_fn)(old_head->item);
00463         if (list->mempool)
00464             cp_mempool_free(list->mempool, old_head);
00465         else
00466             free(old_head);
00467     }
00468 
00469     cp_list_txunlock(list);
00470 
00471     return res;
00472 }
00473 
00474 void *cp_list_remove_tail(cp_list *list)
00475 {
00476     cp_list_entry *old_tail;
00477     void *res = NULL;
00478 
00479     if (cp_list_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00480 
00481     old_tail = cp_list_remove_tail_internal(list);
00482     if (old_tail) 
00483     {
00484         res = old_tail->item;
00485         if (list->mempool)
00486             cp_mempool_free(list->mempool, old_tail);
00487         else
00488             free(old_tail);
00489     }
00490 
00491     cp_list_txunlock(list);
00492 
00493     return res;
00494 }
00495 
00496 
00497 int cp_list_is_empty(cp_list *list)
00498 {
00499     int empty = 0;
00500 
00501     cp_list_txlock(list, COLLECTION_LOCK_READ);
00502     empty = list->head == NULL;
00503    cp_list_txunlock(list);
00504 
00505     return empty;
00506 }
00507 
00508 int cp_list_lock_internal(cp_list *list, int mode)
00509 {
00510     int rc;
00511 
00512     if (mode == COLLECTION_LOCK_READ) 
00513         rc = cp_lock_rdlock(list->lock);
00514     else
00515         rc = cp_lock_wrlock(list->lock);
00516 
00517     return rc;
00518 }
00519 
00520 int cp_list_unlock_internal(cp_list *list)
00521 {
00522     return cp_lock_unlock(list->lock);
00523 }
00524 
00525 int cp_list_txlock(cp_list *list, int type)
00526 {
00527     if (list->mode & COLLECTION_MODE_NOSYNC) return 0;
00528     if (list->mode & COLLECTION_MODE_IN_TRANSACTION && 
00529         list->txtype == COLLECTION_LOCK_WRITE)
00530     {
00531         cp_thread self = cp_thread_self();
00532         if (cp_thread_equal(self, list->txowner)) return 0;
00533     }
00534     return cp_list_lock_internal(list, type);
00535 }
00536 
00537 int cp_list_txunlock(cp_list *list)
00538 {
00539     if (list->mode & COLLECTION_MODE_NOSYNC) return 0;
00540     if (list->mode & COLLECTION_MODE_IN_TRANSACTION && 
00541         list->txtype == COLLECTION_LOCK_WRITE)
00542     {
00543         cp_thread self = cp_thread_self();
00544         if (cp_thread_equal(self, list->txowner)) return 0;
00545     }
00546     return cp_list_unlock_internal(list);
00547 }
00548 
00549 /* lock and set the transaction indicators */
00550 int cp_list_lock(cp_list *list, int type)
00551 {
00552     int rc;
00553     if ((list->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00554     if ((rc = cp_list_lock_internal(list, type))) return rc;
00555     list->txtype = type;
00556     list->txowner = cp_thread_self();
00557     list->mode |= COLLECTION_MODE_IN_TRANSACTION;
00558     return 0;
00559 }
00560 
00561 /* unset the transaction indicators and unlock */
00562 int cp_list_unlock(cp_list *list)
00563 {
00564     cp_thread self = cp_thread_self();
00565     if (list->txowner == self)
00566     {
00567         list->txtype = 0;
00568         list->txowner = 0;
00569         list->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00570     }
00571     else if (list->txtype == COLLECTION_LOCK_WRITE) 
00572         return -1;
00573 
00574     return cp_list_unlock_internal(list);
00575 }
00576 
00577 /* get the current collection mode */
00578 int cp_list_get_mode(cp_list *list)
00579 {
00580     return list->mode;
00581 }
00582 
00583 /* set mode bits on the list mode indicator */
00584 int cp_list_set_mode(cp_list *list, int mode)
00585 {
00586     int nosync;
00587 
00588     /* can't set NOSYNC in the middle of a transaction */
00589     if ((list->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00590         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00591     
00592     nosync = list->mode & COLLECTION_MODE_NOSYNC;
00593     if (!nosync)
00594         if (cp_list_txlock(list, COLLECTION_LOCK_WRITE))
00595             return -1;
00596 
00597     list->mode |= mode;
00598 
00599     if (!nosync)
00600         cp_list_txunlock(list);
00601 
00602     return 0;
00603 }
00604 
00605 /* unset mode bits on the list mode indicator. if unsetting 
00606  * COLLECTION_MODE_NOSYNC and the list was not previously synchronized, the 
00607  * internal synchronization structure is initalized.
00608  */
00609 int cp_list_unset_mode(cp_list *list, int mode)
00610 {
00611     int nosync = list->mode & COLLECTION_MODE_NOSYNC;
00612 
00613     if (!nosync)
00614         if (cp_list_txlock(list, COLLECTION_LOCK_WRITE))
00615             return -1;
00616     
00617     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00618     if ((mode & COLLECTION_MODE_NOSYNC) && list->lock == NULL)
00619     {
00620         /* list can't be locked in this case, no need to unlock on failure */
00621         if ((list->lock = malloc(sizeof(cp_lock))) == NULL)
00622             return -1; 
00623         if (cp_lock_init(list->lock, NULL))
00624             return -1;
00625     }
00626     
00627     /* unset specified bits */
00628     list->mode &= list->mode ^ mode;
00629     if (!nosync)
00630         cp_list_txunlock(list);
00631 
00632     return 0;
00633 }
00634 
00635 /* set list to use given mempool or allocate a new one if pool is NULL */
00636 int cp_list_use_mempool(cp_list *list, cp_mempool *pool)
00637 {
00638     int rc = 0;
00639     
00640     if ((rc = cp_list_txlock(list, COLLECTION_LOCK_WRITE))) return rc;
00641     
00642     if (pool)
00643     {
00644         if (pool->item_size < sizeof(cp_list_entry))
00645         {
00646             rc = EINVAL;
00647             goto DONE;
00648         }
00649         if (list->mempool) 
00650         {
00651             if (list->items) 
00652             {
00653                 rc = ENOTEMPTY;
00654                 goto DONE;
00655             }
00656             cp_mempool_destroy(list->mempool);
00657         }
00658         cp_mempool_inc_refcount(pool);
00659         list->mempool = pool;
00660     }
00661     else
00662     {
00663         list->mempool = 
00664             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
00665                                         sizeof(cp_list_entry), 0);
00666         if (list->mempool == NULL) 
00667         {
00668             rc = ENOMEM;
00669             goto DONE;
00670         }
00671     }
00672 
00673 DONE:
00674     cp_list_txunlock(list);
00675     return rc;
00676 }
00677 
00678 
00679 /* set list to use a shared memory pool */
00680 int cp_list_share_mempool(cp_list *list, cp_shared_mempool *pool)
00681 {
00682     int rc;
00683 
00684     if ((rc = cp_list_txlock(list, COLLECTION_LOCK_WRITE))) return rc;
00685 
00686     if (list->mempool)
00687     {
00688         if (list->items)
00689         {
00690             rc = ENOTEMPTY;
00691             goto DONE;
00692         }
00693 
00694         cp_mempool_destroy(list->mempool);
00695     }
00696 
00697     list->mempool = cp_shared_mempool_register(pool, sizeof(cp_list_entry));
00698     if (list->mempool == NULL) 
00699     {
00700         rc = ENOMEM;
00701         goto DONE;
00702     }
00703     
00704 DONE:
00705     cp_list_txunlock(list);
00706     return rc;
00707 }
00708 
00709 
00710 /****************************************************************************
00711  *                                                                          *
00712  *                    cp_list_iterator implementation                       *
00713  *                                                                          *
00714  ****************************************************************************/
00715  
00716 cp_list_iterator* cp_list_create_iterator(cp_list *list, int type)
00717 {
00718     int rc = - 1;
00719     cp_list_iterator *iterator = (cp_list_iterator *) malloc(sizeof(cp_list_iterator));
00720     iterator->list = list;
00721     iterator->pos = &list->head;
00722     iterator->lock_type = type;
00723 
00724     rc = cp_list_txlock(list, type);
00725     if (rc) /* locking failed */
00726     {
00727         free(iterator);
00728         iterator = NULL;
00729     }
00730 
00731     return iterator;
00732 }
00733 
00734 int cp_list_iterator_init(cp_list_iterator *iterator, cp_list *list, int type)
00735 {
00736     iterator->list = list;
00737     iterator->pos = &list->head;
00738     iterator->lock_type = type;
00739     return cp_list_txlock(list, type);
00740 }
00741 
00742 
00743 int cp_list_iterator_head(cp_list_iterator *iterator)
00744 {
00745     if (iterator == NULL) return -1;
00746     iterator->pos = &iterator->list->head;
00747 
00748     return 0;
00749 }
00750 
00751 int cp_list_iterator_tail(cp_list_iterator *iterator)
00752 {
00753     if (iterator == NULL) return -1;
00754     iterator->pos = &iterator->list->tail;
00755 
00756     return 0;
00757 }
00758 
00759 int cp_list_iterator_init_tail(cp_list_iterator *iterator, 
00760                                cp_list *list, 
00761                                int type)
00762 {
00763     iterator->list = list;
00764     iterator->pos = &list->tail;
00765     iterator->lock_type = type;
00766     return cp_list_txlock(list, type);
00767 }
00768 
00769 int cp_list_iterator_release(cp_list_iterator *iterator)
00770 {
00771     int rc = 0;
00772     if (iterator->lock_type != COLLECTION_LOCK_NONE) 
00773         rc = cp_list_txunlock(iterator->list);
00774 
00775     return rc;
00776 }
00777 
00778 int cp_list_iterator_destroy(cp_list_iterator *iterator)
00779 {
00780     int rc = cp_list_iterator_release(iterator);
00781     free(iterator);
00782 
00783     return rc;
00784 }
00785 
00786 void *cp_list_iterator_next(cp_list_iterator *iterator)
00787 {
00788     void *item = NULL;
00789 
00790     if (*(iterator->pos)) 
00791     {
00792         item = (*iterator->pos)->item;
00793         iterator->pos = &(*(iterator->pos))->next;
00794     }
00795     else if (iterator->list->head && 
00796              iterator->pos == &iterator->list->head->prev)
00797     {
00798         item = iterator->list->head;
00799         iterator->pos = &iterator->list->head;
00800     }
00801 
00802     return item;
00803 }
00804 
00805 void *cp_list_iterator_prev(cp_list_iterator *iterator)
00806 {
00807     void *item = NULL;
00808 
00809     if (*iterator->pos) 
00810     {
00811         item = (*iterator->pos)->item;
00812         iterator->pos = &(*iterator->pos)->prev;
00813     }
00814     else if (iterator->list->tail && 
00815              iterator->pos == &iterator->list->tail->next)
00816     {
00817         item = iterator->list->tail->item;
00818         iterator->pos = &iterator->list->tail->prev;
00819     }
00820 
00821     return item;
00822 }
00823 
00824 void *cp_list_iterator_curr(cp_list_iterator *iterator)
00825 {
00826     void *item = NULL;
00827 
00828     if (*iterator->pos)
00829         item = (*iterator->pos)->item;
00830 
00831     return item;
00832 }
00833 
00834 void *cp_list_iterator_insert(cp_list_iterator *iterator, void *item)
00835 {
00836     void *new_item = NULL;
00837 
00838     if ((iterator->list->mode & COLLECTION_MODE_NOSYNC) || 
00839         (iterator->lock_type == COLLECTION_LOCK_WRITE))
00840     {
00841         cp_list_entry *entry = cp_list_create_entry(iterator->list, item);
00842         if (entry == NULL) return NULL;
00843         new_item = entry->item;
00844         
00845         entry->next = *iterator->pos;
00846 
00847         if (*iterator->pos)
00848         {
00849             entry->prev = (*iterator->pos)->prev;
00850             (*iterator->pos)->prev = entry;
00851             if (entry->prev)
00852                 entry->prev->next = entry;
00853         }
00854         else if (iterator->list->head == NULL) /* iterator not pointing at much - list may be empty */
00855             iterator->list->head = iterator->list->tail = entry;
00856         else if (iterator->pos == &iterator->list->head->prev) /* iterator moved before head */
00857         {
00858             entry->prev = NULL;
00859             entry->next = iterator->list->head;
00860             entry->next->prev = entry;
00861             iterator->list->head = entry;
00862         }
00863         else /* iterator moved after tail */
00864         {
00865             entry->prev = iterator->list->tail;
00866             entry->prev->next = entry;
00867             iterator->list->tail = entry;
00868         }
00869 
00870         iterator->pos =  &entry->next; /* keep iterator at same position */
00871         iterator->list->items++;
00872     }
00873     else /* mode is not NOSYNC and no LOCK_WRITE */
00874         errno = EINVAL;
00875 
00876     return new_item;
00877 }
00878 
00879 void *cp_list_iterator_append(cp_list_iterator *iterator, void *item)
00880 {
00881     void *new_item = NULL;
00882 
00883     if ((iterator->list->mode & COLLECTION_MODE_NOSYNC) || 
00884         (iterator->lock_type == COLLECTION_LOCK_WRITE))
00885     {
00886         cp_list_entry *entry = cp_list_create_entry(iterator->list, item);
00887         if (entry == NULL) return NULL;
00888         new_item = entry->item;
00889         
00890         entry->prev = *iterator->pos;
00891 
00892         if (*iterator->pos)
00893         {
00894             entry->next = (*iterator->pos)->next;
00895             (*iterator->pos)->next = entry;
00896             if (entry->next)
00897                 entry->next->prev = entry;
00898         }
00899         else if (iterator->list->tail == NULL) /* iterator not pointing at much - list may be empty */
00900             iterator->list->tail = iterator->list->head = entry;
00901         else if (iterator->pos == &iterator->list->tail->next) /* iterator moved after tail */
00902         {
00903             entry->next = NULL;
00904             entry->prev = iterator->list->tail;
00905             entry->prev->next = entry;
00906             iterator->list->tail = entry;
00907         }
00908         else /* iterator moved before head */
00909         {
00910             entry->next = iterator->list->head;
00911             entry->next->prev = entry;
00912             iterator->list->head = entry;
00913         }
00914 
00915         iterator->pos = &entry->prev; /* keep iterator at same position */
00916         iterator->list->items++;
00917     }
00918     else /* mode is not NOSYNC and no LOCK_WRITE */
00919         errno = EINVAL;
00920 
00921     return new_item;
00922 }
00923 
00924 void *cp_list_iterator_remove(cp_list_iterator *iterator)
00925 {
00926     void *rm_item = NULL;
00927 
00928     if ((iterator->list->mode & COLLECTION_MODE_NOSYNC) || 
00929         (iterator->lock_type == COLLECTION_LOCK_WRITE))
00930     {
00931         if (*iterator->pos)
00932         {
00933             cp_list_entry *curr = *iterator->pos;
00934             if (curr->prev)
00935                 iterator->pos = &curr->prev->next;
00936             else if (curr->prev)
00937                 iterator->pos = &curr->next->prev;
00938             else /* removing last item */
00939                 iterator->pos = &iterator->list->head;
00940 
00941             cp_list_remove_internal(iterator->list, curr);
00942             if (iterator->list->mode & COLLECTION_MODE_DEEP && 
00943                 iterator->list->free_fn) (*iterator->list->free_fn)(curr->item);
00944             if (iterator->list->mempool)
00945                 cp_mempool_free(iterator->list->mempool, curr);
00946             else
00947                 free(curr);
00948         }
00949     }
00950 
00951     return rm_item;
00952 }
00953 
00954 
00955 
00956 
00957 /* ----------------------------------------------------------------- */
00960 static cp_list_entry *cp_list_create_entry(cp_list *list, void *item)
00961 {
00962     cp_list_entry *entry;
00963     
00964     if (list->mempool)
00965         entry = (cp_list_entry *) cp_mempool_calloc(list->mempool);
00966     else
00967         entry = (cp_list_entry *) calloc(1, sizeof(cp_list_entry));
00968 
00969     if (entry == NULL) 
00970     {
00971         errno = ENOMEM;
00972         return NULL;
00973     }
00974     entry->item = (list->mode & COLLECTION_MODE_COPY) ? (*list->copy_fn)(item) : item;
00975 
00976     return entry;
00977 }
00978 
00979 static cp_list_entry *cp_list_insert_internal(cp_list *list, void *item)
00980 {
00981     cp_list_entry *entry;
00982 
00983     entry = cp_list_create_entry(list, item);
00984     if (entry == NULL) return NULL;
00985 
00986     entry->next = list->head;
00987     list->head = entry;
00988     if (entry->next) entry->next->prev = entry;
00989     if (list->tail == NULL) list->tail = entry;
00990 
00991     list->items++;
00992 
00993     return entry;
00994 }
00995 
00996 static cp_list_entry *
00997     cp_list_remove_internal(cp_list *list, cp_list_entry *entry)
00998 {
00999     if (entry->prev) 
01000         entry->prev->next = entry->next;
01001     else
01002         list->head = entry->next;
01003 
01004     if (entry->next)
01005         entry->next->prev = entry->prev;
01006     else
01007         list->tail = entry->prev;
01008 
01009     list->items--;
01010 
01011     return entry;
01012 }
01013 
01014 static cp_list_entry *cp_list_append_internal(cp_list *list, void *item)
01015 {
01016     cp_list_entry *entry;
01017 
01018     entry = cp_list_create_entry(list, item);
01019     if (entry == NULL) return NULL;
01020 
01021     entry->prev = list->tail;
01022     list->tail = entry;
01023 
01024     if (entry->prev) entry->prev->next = entry;
01025 
01026     if (list->head == NULL) list->head = entry;
01027 
01028     list->items++;
01029 
01030     return entry;
01031 }
01032 
01033 static cp_list_entry *cp_list_remove_head_internal(cp_list *list)
01034 {
01035     cp_list_entry *old_head;
01036 
01037     old_head = list->head;
01038     if (old_head) 
01039     {
01040         list->head = list->head->next;
01041 
01042         if (list->head == NULL) 
01043             list->tail = NULL;
01044         else
01045             list->head->prev = NULL;
01046 
01047         list->items--;
01048     }
01049 
01050     return old_head;
01051 }
01052 
01053 static cp_list_entry *cp_list_remove_tail_internal(cp_list *list)
01054 {
01055     cp_list_entry *old_tail;
01056 
01057     old_tail = list->tail;
01058     if (old_tail) 
01059     {
01060         list->tail = list->tail->prev;
01061 
01062         if (list->tail == NULL) 
01063             list->head = NULL;
01064         else
01065             list->tail->next = NULL;
01066 
01067         list->items--;
01068     }
01069 
01070     return old_tail;
01071 }
01072 

Generated on Mon Dec 5 23:00:22 2011 for cprops by  doxygen 1.4.7