hashlist.c

Go to the documentation of this file.
00001 
00013 /* ----------------------------------------------------------------- */
00014 
00015 #include <stdio.h> /* debug */
00016 #include <stdlib.h>
00017 #include <errno.h>
00018 
00019 #include "collection.h"
00020 #include "log.h"
00021 #include "common.h"
00022 
00023 #include "hashlist.h"
00024 #include "linked_list.h"
00025 
00026 #include "config.h"
00027 
00028 /* debug */
00029 #ifndef CP_HASHLIST_MULTIPLE_VALUES
00030 #define CP_HASHLIST_MULTIPLE_VALUES 1
00031 #endif
00032 
00033 
00034     /* internal methods */
00035 
00036 /* internal lock function */
00037 int cp_hashlist_txlock(cp_hashlist *list, int type);
00038 /* internal unlock function */
00039 int cp_hashlist_txunlock(cp_hashlist *list);
00040 
00041 static cp_hashlist_entry *
00042     cp_hashlist_create_entry(cp_hashlist *list, int mode, 
00043                              void *key, void *value);
00044 
00045 static void 
00046     cp_hashlist_entry_delete(cp_hashlist_entry *entry);
00047 
00048 static void cp_hashlist_entry_release_by_option(cp_hashlist *list, 
00049                                                 cp_hashlist_entry *entry, 
00050                                                 int mode);
00058 static cp_hashlist_entry *
00059     cp_hashlist_insert_internal(cp_hashlist *list, cp_hashlist_entry *entry);
00060 
00069 static cp_hashlist_entry *
00070     cp_hashlist_remove_internal(cp_hashlist *list, void *key);
00071 
00080 static cp_hashlist_entry *
00081     cp_hashlist_remove_entry_internal(cp_hashlist *list, 
00082                                       cp_hashlist_entry *entry);
00083 
00084 static void *cp_hashlist_get_internal(cp_hashlist *list, void *key);
00085 
00086     /* end internal methods */
00087 
00088 
00089 cp_hashlist *
00090     cp_hashlist_create_by_option(int mode, 
00091                                  unsigned long size_hint, 
00092                                  cp_hashfunction hash_fn, 
00093                                  cp_compare_fn compare_fn,
00094                                  cp_copy_fn copy_key,
00095                                  cp_destructor_fn free_key,
00096                                  cp_copy_fn copy_value,
00097                                  cp_destructor_fn free_value)
00098 {
00099     cp_hashlist *list = (cp_hashlist *) calloc(1, sizeof(cp_hashlist));
00100     if (list == NULL) 
00101     {
00102         errno = ENOMEM;
00103         return NULL;
00104     }
00105 
00106     list->table_size = cp_hashtable_choose_size(size_hint);
00107     list->items = 0;
00108     list->table = (cp_hashlist_entry **) calloc(list->table_size, sizeof(cp_hashlist_entry *));
00109     if (list->table == NULL) 
00110     {
00111         errno = ENOMEM;
00112         return NULL;
00113     }
00114 
00115     list->hash_fn = hash_fn;
00116     list->compare_fn = compare_fn;
00117     list->copy_key = NULL;
00118     list->copy_value = NULL;
00119 
00120     list->head = list->tail = NULL;
00121     list->lock = calloc(1, sizeof(cp_lock));
00122     if (list->lock == NULL)
00123     {
00124         free(list->table);
00125         free(list);
00126         errno = ENOMEM;
00127         return NULL;
00128     }
00129     if (!(mode & COLLECTION_MODE_NOSYNC)) 
00130         if (cp_lock_init(list->lock, NULL))
00131         {
00132             free(list->lock);
00133             free(list->table);
00134             free(list);
00135             return NULL;
00136         }
00137 
00138     list->mode = mode;
00139 
00140     list->copy_key = copy_key;
00141     list->copy_value = copy_value;
00142     list->free_key = free_key;
00143     list->free_value = free_value;
00144 
00145     list->min_size = size_hint;
00146     list->fill_factor_min = CP_HASHTABLE_DEFAULT_MIN_FILL_FACTOR;
00147     list->fill_factor_max = CP_HASHTABLE_DEFAULT_MAX_FILL_FACTOR;
00148 
00149     return list;
00150 }
00151 
00152 
00153 cp_hashlist *cp_hashlist_create_by_mode(int mode, 
00154                                         unsigned long size_hint, 
00155                                         cp_hashfunction hash_fn, 
00156                                         cp_compare_fn compare_fn)
00157 {
00158     return 
00159         cp_hashlist_create_by_option(mode, size_hint, hash_fn, compare_fn,
00160                                      NULL, NULL, NULL, NULL);
00161 }
00162 
00163 static cp_hashlist_entry *
00164     cp_hashlist_create_entry(cp_hashlist *list, int mode,
00165                              void *key, void *value)
00166 {
00167     cp_copy_fn ck = list->copy_key;
00168     cp_copy_fn cv = list->copy_value;
00169     cp_hashlist_entry *entry = 
00170         (cp_hashlist_entry *) calloc(1, sizeof(cp_hashlist_entry));
00171     
00172     if (entry == NULL) 
00173     {
00174         errno = ENOMEM;
00175         return NULL;
00176     }
00177 
00178     entry->next = entry->prev = entry->bucket = NULL;
00179     if (mode & COLLECTION_MODE_COPY) 
00180     {
00181         entry->key = ck ? (*ck)(key) : key;
00182         entry->value = cv ? (*cv)(value) : value;
00183     } 
00184     else 
00185     {
00186         entry->key = key;
00187         entry->value = value;
00188     }
00189 
00190     return entry;
00191 }
00192 
00193 
00194 static void 
00195     cp_hashlist_destroy_internal(cp_hashlist *list, 
00196                                  int mode, 
00197                                  cp_destructor_fn dk,
00198                                  cp_destructor_fn dv)
00199 {
00200     int syncbit = list->mode & COLLECTION_MODE_NOSYNC;
00201 
00202     if (!syncbit) 
00203     {
00204         int rc;
00205 #if (CP_DEBUGLEVEL >= 2) 
00206         cp_thread self = cp_thread_self();
00207         if (list->dtr_caller && list->dtr_caller != self)
00208             DEBUGMSG("cp_hashlist_destroy_internal has already been invoked by a different thread: %ld ", list->dtr_caller);
00209         list->dtr_caller = self;
00210 #endif
00211         rc = cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE);
00212     }
00213 
00214     while (list->head != NULL)
00215     {
00216         cp_hashlist_entry *entry = list->head;
00217         list->head = entry->next;
00218         if (mode & COLLECTION_MODE_DEEP)
00219         {
00220             if (dk) (*dk)(entry->key);
00221             if (dv) (*dv)(entry->value);
00222         }
00223         cp_hashlist_entry_delete(entry);
00224     }
00225 
00226     if (!syncbit) cp_hashlist_txunlock(list);
00227     if (list->lock)
00228     {
00229         cp_lock_destroy(list->lock);
00230         free(list->lock);
00231     }
00232 
00233     free(list->table);
00234     free(list);
00235 }
00236 
00237 void cp_hashlist_destroy(cp_hashlist *list)
00238 {
00239     cp_hashlist_destroy_internal(list, list->mode, 
00240                                  list->free_key, list->free_value);
00241 }
00242 
00243 void cp_hashlist_destroy_deep(cp_hashlist *list)
00244 {
00245     cp_hashlist_set_mode(list, COLLECTION_MODE_DEEP);
00246     cp_hashlist_destroy_custom(list, list->free_key, list->free_value);
00247 }
00248 
00249 void cp_hashlist_destroy_by_option(cp_hashlist *list, int mode)
00250 {
00251     
00252     if (list) 
00253         cp_hashlist_destroy_internal(list, mode, 
00254                                      list->free_key, list->free_value);
00255 }
00256 
00257 void cp_hashlist_destroy_custom(cp_hashlist *list, 
00258                                        cp_destructor_fn dk, 
00259                                        cp_destructor_fn dv)
00260 {
00261     if (list)
00262         cp_hashlist_destroy_internal(list, list->mode, dk, dv);
00263 }
00264 
00265 int cp_hashlist_callback(cp_hashlist *list, 
00266                          int (*cb)(void *key, void *value, void *id),
00267                          void *id)
00268 {
00269     cp_hashlist_entry *entry;
00270 
00271     if (list == NULL || cb == NULL) 
00272     {
00273         errno = EINVAL;
00274         return -1;
00275     }
00276 
00277     if (cp_hashlist_txlock(list, COLLECTION_LOCK_READ)) return -1;
00278 
00279     entry = list->head;
00280     while (entry != NULL) 
00281     {
00282         if ((*cb)(entry->key, entry->value, id) != 0)
00283             break;
00284         entry = entry->next;
00285     }
00286 
00287     cp_hashlist_txunlock(list);
00288     return 0;
00289 }
00290 
00291 int cp_hashlist_get_mode(cp_hashlist *list)
00292 {
00293     return list->mode;
00294 }
00295 
00296 int cp_hashlist_set_mode(cp_hashlist *list, int mode)
00297 {
00298     int rc = EINVAL;
00299     if (list)
00300     {
00301         int syncbit = list->mode & COLLECTION_MODE_NOSYNC;
00302 
00303         /* can't set NOSYNC in the middle of a transaction */
00304         if ((list->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00305             (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00306 
00307         syncbit = list->mode & COLLECTION_MODE_NOSYNC;
00308 
00309         if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return -1;
00310         list->mode |= mode;
00311         if (!syncbit) cp_hashlist_txunlock(list);
00312 
00313         rc = 0;
00314     }
00315 
00316     return rc;
00317 }
00318 
00319 int cp_hashlist_unset_mode(cp_hashlist *list, int mode)
00320 {
00321     int syncbit;
00322     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return -1;
00323     syncbit = list->mode & COLLECTION_MODE_NOSYNC;
00324     list->mode &= list->mode ^ mode;
00325     if (!syncbit) cp_hashlist_txunlock(list);
00326 
00327     return 0;
00328 }
00329 
00330 int cp_hashlist_set_min_size(cp_hashlist *list, unsigned long min_size)
00331 {
00332     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return -1;
00333     list->min_size = min_size;
00334     cp_hashlist_txunlock(list);
00335     return 0;
00336 }
00337 
00338 
00339 int cp_hashlist_set_max_fill_factor(cp_hashlist *list, int fill_factor)
00340 {
00341     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return -1;
00342     list->fill_factor_max = fill_factor;
00343     cp_hashlist_txunlock(list);
00344     return 0;
00345 }
00346 
00347 int cp_hashlist_set_min_fill_factor(cp_hashlist *list, int fill_factor)
00348 {
00349     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return -1;
00350     list->fill_factor_min = fill_factor;
00351     cp_hashlist_txunlock(list);
00352     return 0;
00353 }
00354 
00355 void *cp_hashlist_resize_nosync(cp_hashlist *list, unsigned long new_size)
00356 {
00357     unsigned long old_size;
00358     cp_hashlist_entry **old_table;
00359     cp_hashlist_entry *entry, *next, **insert;
00360     unsigned long i, index;
00361 
00362     old_size = list->table_size;
00363     old_table = list->table;
00364     
00365     new_size = cp_hashtable_choose_size(new_size);
00366     if (old_size == new_size) /* not enough gap to make a change yet */
00367         return list;
00368     else
00369         list->table_size = new_size;
00370 #ifdef __TRACE__
00371     DEBUGMSG("resizing table (nosync): %d to %d\n", old_size, list->table_size);
00372 #endif
00373 
00374     list->table = (cp_hashlist_entry **) calloc(list->table_size, sizeof(cp_hashlist_entry *));
00375 
00376     if (list->table == NULL) 
00377     {
00378         errno = ENOMEM;
00379         return NULL;
00380     }
00381 
00382     for (i = 0; i < old_size; i++) 
00383     {
00384         entry = old_table[i];
00385         while (entry != NULL) 
00386         {
00387             index = abs((*list->hash_fn)(entry->key)) % list->table_size;
00388             next = entry->bucket;
00389             entry->bucket = NULL;
00390             insert = &list->table[index];
00391             while (*insert != NULL) insert = &(*insert)->bucket;
00392             *insert = entry;
00393             
00394             entry = next;
00395         }
00396     }
00397 
00398     free(old_table);
00399 
00400     return list;
00401 }
00402 
00403 void *cp_hashlist_append(cp_hashlist *list, void *key, void *value)
00404 {
00405     return cp_hashlist_append_by_option(list, key, value, list->mode);
00406 }
00407 
00408 static int cp_hashlist_contains_internal(cp_hashlist *list, void *key)
00409 {
00410     int rc = 0;
00411     cp_hashlist_entry *curr;
00412     int index = abs((*list->hash_fn)(key)) % list->table_size;
00413     
00414     curr = list->table[index];
00415 
00416     while (curr != NULL) 
00417     {
00418         if ((*list->compare_fn)(key, curr->key) == 0)
00419         {
00420             rc = 1;
00421             break;
00422         }
00423         curr = curr->bucket;
00424     }
00425 
00426     return rc;
00427 }
00428 
00429 int cp_hashlist_contains(cp_hashlist *list, void *key)
00430 {
00431     int rc = 0;
00432 
00433     if (cp_hashlist_txlock(list, COLLECTION_LOCK_READ)) return -1;
00434     rc = cp_hashlist_contains_internal(list, key);
00435     cp_hashlist_txunlock(list);
00436 
00437     return rc;
00438 }
00439 
00440 void *cp_hashlist_append_by_option(cp_hashlist *list, 
00441                                    void *key, 
00442                                    void *value, 
00443                                    int mode)
00444 {
00445     cp_hashlist_entry *entry;
00446     void *res = NULL;
00447     int rc = 0;
00448 
00449     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00450 
00451     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES) == 0
00452         && cp_hashlist_contains_internal(list, key)) 
00453     {
00454         rc = EINVAL;
00455         goto DONE;
00456     }
00457 
00458     if ((entry = cp_hashlist_create_entry(list, mode, key, value)) == NULL)
00459     {
00460         rc = ENOMEM;
00461         goto DONE;
00462     }
00463 
00464     cp_hashlist_insert_internal(list, entry);
00465 
00466     if (list->tail) 
00467     {
00468         entry->prev = list->tail;
00469         list->tail->next = entry;
00470         list->tail = entry;
00471     }
00472     else list->tail = list->head = entry;
00473 
00474     res = value;
00475 
00476 DONE:
00477     cp_hashlist_txunlock(list);
00478     if (rc) errno = rc;
00479 
00480     return res;
00481 }
00482 
00483 
00484 void *cp_hashlist_insert(cp_hashlist *list, void *key, void *value)
00485 {
00486     return cp_hashlist_insert_by_option(list, key, value, list->mode);
00487 }
00488 
00489 
00490 void *cp_hashlist_insert_by_option(cp_hashlist *list, void *key, 
00491                                    void *value, int mode)
00492 {
00493     cp_hashlist_entry *entry;
00494     void *res = NULL;
00495     int rc = 0;
00496 
00497     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00498 
00499     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES) == 0
00500         && cp_hashlist_contains_internal(list, key)) 
00501     {
00502         rc = EINVAL;
00503         goto DONE;
00504     }
00505 
00506     if ((entry = cp_hashlist_create_entry(list, mode, key, value)) == NULL)
00507     {
00508         rc = errno;
00509         goto DONE;
00510     }
00511 
00512     cp_hashlist_insert_internal(list, entry);
00513     if (list->head) 
00514     {
00515         entry->next = list->head;
00516         list->head->prev = entry;
00517         list->head = entry;
00518     }
00519     else list->head = list->tail = entry;
00520 
00521     res = value;
00522 
00523 DONE:
00524     cp_hashlist_txunlock(list);
00525     if (rc) errno = rc;
00526 
00527     return res;
00528 }
00529     
00530 
00531 void *cp_hashlist_get(cp_hashlist *list, void *key)
00532 {
00533     void *res = NULL;
00534 
00535     if (cp_hashlist_txlock(list, COLLECTION_LOCK_READ)) return NULL;
00536 
00537     res = cp_hashlist_get_internal(list, key);
00538 
00539 #if CP_HASHLIST_MULTIPLE_VALUES
00540     if (!(list->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00541 #endif
00542     if (res) res = ((cp_hashlist_entry *) res)->value;
00543 
00544     cp_hashlist_txunlock(list);
00545 
00546     return res;
00547 }
00548 
00549 static void *cp_hashlist_unlink_internal(cp_hashlist *list, 
00550                                          cp_hashlist_entry *holder,
00551                                          int mode)
00552 {
00553     void *res = NULL;
00554 
00555     if (holder) 
00556     {    
00557         if (holder->next) 
00558             holder->next->prev = holder->prev;
00559         else              
00560             list->tail = holder->prev;
00561         
00562         if (holder->prev) 
00563             holder->prev->next = holder->next;
00564         else              
00565             list->head = holder->next;
00566         
00567         res = holder->value;
00568         cp_hashlist_entry_release_by_option(list, holder, mode);
00569     }
00570     
00571     return res;
00572 }
00573 
00574 void *cp_hashlist_remove_by_option(cp_hashlist *list, void *key, int mode)
00575 {
00576     void *res;
00577     cp_hashlist_entry *holder;
00578 
00579     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00580 
00581     holder = cp_hashlist_remove_internal(list, key);
00582     res = cp_hashlist_unlink_internal(list, holder, mode);
00583 
00584     cp_hashlist_txunlock(list);
00585 
00586     return res;
00587 }
00588 
00589 void *cp_hashlist_remove(cp_hashlist *list, void *key)
00590 {
00591     return cp_hashlist_remove_by_option(list, key, list->mode);
00592 }
00593 
00594 void *cp_hashlist_remove_deep(cp_hashlist *list, void *key)
00595 {
00596     return 
00597         cp_hashlist_remove_by_option(list, key, 
00598                                      list->mode | COLLECTION_MODE_DEEP);
00599 }
00600 
00601 void *cp_hashlist_get_head(cp_hashlist *list)
00602 {
00603     void *res;
00604 
00605     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00606 
00607     res = list->head ? list->head->value : NULL;
00608     
00609     cp_hashlist_txunlock(list);
00610     return res;
00611 }
00612 
00613 void *cp_hashlist_get_tail(cp_hashlist *list)
00614 {
00615     void *res;
00616     
00617     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00618 
00619     res = list->tail ? list->tail->value : NULL;
00620     
00621     cp_hashlist_txunlock(list);
00622     return res;
00623 }
00624 
00625 
00626 void *cp_hashlist_remove_head(cp_hashlist *list)
00627 {
00628     return cp_hashlist_remove_head_by_option(list, list->mode);
00629 }
00630 
00631 void *cp_hashlist_remove_head_by_option(cp_hashlist *list, int mode)
00632 {
00633     cp_hashlist_entry *entry;
00634     void *res = NULL;
00635 
00636     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00637 
00638     entry = list->head;
00639     if (entry) 
00640     {
00641         if (!cp_hashlist_remove_entry_internal(list, entry))  /* should _not_ happen */
00642             printf("failed to remove item from cp_hashlist table: %s\n", (char *) entry->value);
00643 
00644         list->head = list->head->next;
00645         if (list->head) 
00646             list->head->prev = NULL;
00647         else
00648             list->tail = NULL;
00649 
00650         res = entry->value;
00651 
00652         cp_hashlist_entry_release_by_option(list, entry, mode);
00653     }
00654 
00655     cp_hashlist_txunlock(list);
00656     return res;
00657 }
00658 
00659 void *cp_hashlist_remove_tail(cp_hashlist *list)
00660 {
00661     return cp_hashlist_remove_tail_by_option(list, list->mode);
00662 }
00663 
00664 void *cp_hashlist_remove_tail_by_option(cp_hashlist *list, int mode)
00665 {
00666     cp_hashlist_entry *entry;
00667     void *res = NULL;
00668 
00669     if (cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE)) return NULL;
00670 
00671     entry = list->tail;
00672     if (entry) 
00673     {
00674         if (!cp_hashlist_remove_entry_internal(list, entry)) /* should _not_ happen */
00675             printf("failed to remove item from cp_hashlist table: %s\n", (char *) entry->value);
00676 
00677         list->tail = entry->prev;
00678         if (list->tail) 
00679             list->tail->next = NULL;
00680         else
00681             list->head = NULL;
00682 
00683         res = entry->value;
00684         cp_hashlist_entry_release_by_option(list, entry, mode);
00685     }
00686 
00687     cp_hashlist_txunlock(list);
00688     return res;
00689 }
00690 
00691 unsigned long cp_hashlist_item_count(cp_hashlist *list)
00692 {
00693     unsigned long count;
00694     if (cp_hashlist_txlock(list, COLLECTION_LOCK_READ)) return -1;
00695 
00696     count = list->items;
00697 
00698     cp_hashlist_txunlock(list);
00699     return count;
00700 }
00701 
00702     
00703 int cp_hashlist_lock_internal(cp_hashlist *list, int lock_mode)
00704 {
00705     int rc = -1;
00706 
00707     switch (lock_mode) 
00708     {
00709         case COLLECTION_LOCK_READ:
00710             rc = cp_lock_rdlock(list->lock);
00711             break;
00712 
00713         case COLLECTION_LOCK_WRITE:
00714             rc = cp_lock_wrlock(list->lock);
00715             break;
00716 
00717         case COLLECTION_LOCK_NONE:
00718             rc = 0;
00719             break;
00720 
00721         default:
00722             errno = EINVAL;
00723             break;
00724     }
00725 
00726     return rc;
00727 }
00728 
00729 int cp_hashlist_unlock_internal(cp_hashlist *list)
00730 {
00731     return cp_lock_unlock(list->lock);
00732 }
00733 
00734 int cp_hashlist_txlock(cp_hashlist *list, int type)
00735 {
00736 #if (CP_DEBUGLEVEL >= 2)
00737     if (list->dtr_caller)
00738     {
00739         cp_thread dself = cp_thread_self();
00740         if (dself != list->dtr_caller)
00741         {
00742             DEBUGMSG("request for lock after destructor has been called on a differrent thread: %ld", list->dtr_caller);
00743         }
00744     }
00745 #endif
00746 
00747     if (list->mode & COLLECTION_MODE_NOSYNC) return 0;
00748     if (list->mode & COLLECTION_MODE_IN_TRANSACTION && 
00749         list->txtype == COLLECTION_LOCK_WRITE)
00750     {
00751         cp_thread self = cp_thread_self();
00752         if (cp_thread_equal(self, list->txowner)) return 0;
00753     }
00754     return cp_hashlist_lock_internal(list, type);
00755 }
00756 
00757 int cp_hashlist_txunlock(cp_hashlist *list)
00758 {
00759 #if (CP_DEBUGLEVEL >= 2)
00760     if (list->dtr_caller)
00761     {
00762         cp_thread dself = cp_thread_self();
00763         if (dself != list->dtr_caller)
00764         {
00765             DEBUGMSG("releasing lock after destructor has been called on a differrent thread: %ld", list->dtr_caller);
00766         }
00767     }
00768 #endif
00769 
00770     if (list->mode & COLLECTION_MODE_NOSYNC) return 0;
00771     if (list->mode & COLLECTION_MODE_IN_TRANSACTION && 
00772         list->txtype == COLLECTION_LOCK_WRITE)
00773     {
00774         cp_thread self = cp_thread_self();
00775         if (cp_thread_equal(self, list->txowner)) return 0;
00776     }
00777     return cp_hashlist_unlock_internal(list);
00778 }
00779 
00780 /* lock and set the transaction indicators */
00781 int cp_hashlist_lock(cp_hashlist *list, int type)
00782 {
00783     int rc;
00784 
00785 #if (CP_DEBUGLEVEL >= 2)
00786     if (list->dtr_caller)
00787     {
00788         cp_thread dself = cp_thread_self();
00789         if (dself != list->dtr_caller)
00790         {
00791             DEBUGMSG("request for lock after destructor has been called on a differrent thread: %p", list->dtr_caller);
00792         }
00793     }
00794 #endif
00795 
00796     if ((list->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00797     if ((rc = cp_hashlist_lock_internal(list, type))) return rc;
00798     list->txtype = type;
00799     list->txowner = cp_thread_self();
00800     list->mode |= COLLECTION_MODE_IN_TRANSACTION;
00801     return 0;
00802 }
00803 
00804 /* unset the transaction indicators and unlock */
00805 int cp_hashlist_unlock(cp_hashlist *list)
00806 {
00807     cp_thread self;
00808 
00809 #if (CP_DEBUGLEVEL >= 2)
00810     if (list->dtr_caller)
00811     {
00812         cp_thread dself = cp_thread_self();
00813         if (dself != list->dtr_caller)
00814         {
00815             DEBUGMSG("releasing lock after destructor has been called on a differrent thread: %p", list->dtr_caller);
00816         }
00817     }
00818 #endif
00819 
00820     if ((list->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00821 
00822     self = cp_thread_self();
00823     if (list->txowner == self)
00824     {
00825         list->txtype = 0;
00826         list->txowner = 0;
00827         list->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00828     }
00829     else if (list->txtype == COLLECTION_LOCK_WRITE)
00830         return -1;
00831     return cp_hashlist_unlock_internal(list);
00832 }
00833 
00834 
00835 void *cp_hashlist_entry_get_key(cp_hashlist_entry *entry)
00836 {
00837     return (entry) ? entry->key : NULL;
00838 }
00839 
00840 void *cp_hashlist_entry_get_value(cp_hashlist_entry *entry)
00841 {
00842     return (entry) ? entry->value : NULL;
00843 }
00844 
00845 int cp_hashlist_is_empty(cp_hashlist *list)
00846 {
00847     return cp_hashlist_item_count(list) == 0;
00848 }
00849 
00850 
00851 /****************************************************************************
00852  *                                                                          *
00853  *                    cp_hashlist_iterator implementation                   *
00854  *                                                                          *
00855  ****************************************************************************/
00856  
00857 cp_hashlist_iterator* cp_hashlist_create_iterator(cp_hashlist *list, int type)
00858 {
00859     int rc = - 1;
00860     cp_hashlist_iterator *iterator = 
00861         (cp_hashlist_iterator *) malloc(sizeof(cp_hashlist_iterator));
00862     if (iterator == NULL) 
00863     {
00864         errno = CP_MEMORY_ALLOCATION_FAILURE;
00865         return NULL;
00866     }
00867 
00868     iterator->list = list;
00869     iterator->pos = &list->head;
00870     iterator->lock_type = type;
00871 
00872     switch (type)
00873     {
00874         case COLLECTION_LOCK_READ : 
00875             rc = cp_hashlist_txlock(list, COLLECTION_LOCK_READ);
00876             break;
00877 
00878         case COLLECTION_LOCK_WRITE :
00879             rc = cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE);
00880             break;
00881     
00882         default :
00883             rc = 0;
00884     }
00885 
00886     if (rc) /* locking failed */
00887     {
00888         free(iterator);
00889         errno = CP_LOCK_FAILED;
00890         iterator = NULL;
00891     }
00892 
00893     return iterator;
00894 }
00895 
00896 int cp_hashlist_iterator_init(cp_hashlist_iterator *iterator, 
00897                               cp_hashlist *list, int type)
00898 {
00899     int rc;
00900     iterator->list = list;
00901     iterator->pos = &list->head;
00902     iterator->lock_type = type;
00903 
00904     switch (type)
00905     {
00906         case COLLECTION_LOCK_READ : 
00907             rc = cp_hashlist_txlock(list, COLLECTION_LOCK_READ);
00908             break;
00909 
00910         case COLLECTION_LOCK_WRITE :
00911             rc = cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE);
00912             break;
00913     
00914         default :
00915             rc = 0;
00916     }
00917 
00918     return rc;
00919 }
00920 
00921 
00922 int cp_hashlist_iterator_head(cp_hashlist_iterator *iterator)
00923 {
00924     if (iterator == NULL) return -1;
00925     iterator->pos = &iterator->list->head;
00926 
00927     return 0;
00928 }
00929 
00930 int cp_hashlist_iterator_tail(cp_hashlist_iterator *iterator)
00931 {
00932     if (iterator == NULL) return -1;
00933     iterator->pos = &iterator->list->tail;
00934 
00935     return 0;
00936 }
00937 
00938 int cp_hashlist_iterator_init_tail(cp_hashlist_iterator *iterator, cp_hashlist *list, int type)
00939 {
00940     int rc;
00941     iterator->list = list;
00942     iterator->pos = &list->tail;
00943     iterator->lock_type = type;
00944 
00945     switch (type)
00946     {
00947         case COLLECTION_LOCK_READ : 
00948             rc = cp_hashlist_txlock(list, COLLECTION_LOCK_READ);
00949             break;
00950 
00951         case COLLECTION_LOCK_WRITE :
00952             rc = cp_hashlist_txlock(list, COLLECTION_LOCK_WRITE);
00953             break;
00954     
00955         default :
00956             rc = 0;
00957     }
00958 
00959     return rc;
00960 }
00961 
00962 int cp_hashlist_iterator_to_key(cp_hashlist_iterator *iterator, void *key)
00963 {
00964     cp_hashlist_entry *entry = NULL;
00965     
00966 #if CP_HASHLIST_MULTIPLE_VALUES
00967     if ((iterator->list->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00968     {
00969         cp_list *res = cp_hashlist_get_internal(iterator->list, key);
00970         if (res)
00971         {
00972             entry = cp_list_get_head(res);
00973             cp_list_destroy(res);
00974         }
00975     }
00976     else
00977 #endif
00978     entry = cp_hashlist_get_internal(iterator->list, key);
00979 
00980     if (entry == NULL) return -1;
00981 
00982     if (entry->prev) 
00983         iterator->pos = &entry->prev->next;
00984     else 
00985         iterator->pos = &iterator->list->head;
00986 
00987     return 0;
00988 }
00989 
00990 
00991 int cp_hashlist_iterator_release(cp_hashlist_iterator *iterator)
00992 {
00993     int rc = 0;
00994     if (iterator->lock_type != COLLECTION_LOCK_NONE) 
00995         rc = cp_hashlist_txunlock(iterator->list);
00996 
00997     return rc;
00998 }
00999 
01000 int cp_hashlist_iterator_destroy(cp_hashlist_iterator *iterator)
01001 {
01002     int rc = cp_hashlist_iterator_release(iterator);
01003     free(iterator);
01004 
01005     return rc;
01006 }
01007 
01008 cp_hashlist_entry *cp_hashlist_iterator_next(cp_hashlist_iterator *iterator)
01009 {
01010     cp_hashlist_entry *entry = NULL;
01011 
01012     if (*(iterator->pos)) 
01013     {
01014         entry = (*iterator->pos);
01015         iterator->pos = &(*(iterator->pos))->next;
01016     }
01017     else if (iterator->list->head && 
01018              iterator->pos == &iterator->list->head->prev)
01019     {
01020         entry = iterator->list->head;
01021         iterator->pos = &iterator->list->head;
01022     }
01023 
01024     return entry;
01025 }
01026 
01027 void *cp_hashlist_iterator_next_key(cp_hashlist_iterator *iterator)
01028 {
01029     return cp_hashlist_entry_get_key(cp_hashlist_iterator_next(iterator));
01030 }
01031 
01032 void *cp_hashlist_iterator_next_value(cp_hashlist_iterator *iterator)
01033 {
01034     return cp_hashlist_entry_get_value(cp_hashlist_iterator_next(iterator));
01035 }
01036 
01037 cp_hashlist_entry *cp_hashlist_iterator_prev(cp_hashlist_iterator *iterator)
01038 {
01039     cp_hashlist_entry  *entry = NULL;
01040 
01041     if (*iterator->pos) 
01042     {
01043         entry = (*iterator->pos);
01044         iterator->pos = &(*iterator->pos)->prev;
01045     }
01046     else if (iterator->list->tail && 
01047              iterator->pos == &iterator->list->tail->next)
01048     {
01049         entry = iterator->list->tail;
01050         iterator->pos = &iterator->list->tail;
01051     }
01052 
01053     return entry;
01054 }
01055 
01056 void *cp_hashlist_iterator_prev_key(cp_hashlist_iterator *iterator)
01057 {
01058     return cp_hashlist_entry_get_key(cp_hashlist_iterator_prev(iterator));
01059 }
01060 
01061 void *cp_hashlist_iterator_prev_value(cp_hashlist_iterator *iterator)
01062 {
01063     return cp_hashlist_entry_get_value(cp_hashlist_iterator_prev(iterator));
01064 }
01065 
01066 cp_hashlist_entry *cp_hashlist_iterator_curr(cp_hashlist_iterator *iterator)
01067 {
01068     cp_hashlist_entry *item = NULL;
01069 
01070     if (*iterator->pos)
01071         item = (*iterator->pos);
01072 
01073     return item;
01074 }
01075 
01076 void *cp_hashlist_iterator_curr_key(cp_hashlist_iterator *iterator)
01077 {
01078     return cp_hashlist_entry_get_key(cp_hashlist_iterator_curr(iterator));
01079 }
01080 
01081 void *cp_hashlist_iterator_curr_value(cp_hashlist_iterator *iterator)
01082 {
01083     return cp_hashlist_entry_get_value(cp_hashlist_iterator_curr(iterator));
01084 }
01085 
01086 cp_hashlist_entry *cp_hashlist_iterator_insert(cp_hashlist_iterator *iterator, 
01087                                                void *key, 
01088                                                void *value)
01089 {
01090     cp_hashlist_entry *new_entry = NULL;
01091 
01092     if ((iterator->list->mode & COLLECTION_MODE_NOSYNC) || 
01093         (iterator->lock_type == COLLECTION_LOCK_WRITE))
01094     {
01095         cp_hashlist_entry *entry; 
01096         if ((iterator->list->mode & COLLECTION_MODE_MULTIPLE_VALUES) == 0
01097             && cp_hashlist_contains_internal(iterator->list, key)) 
01098         {
01099             errno = EINVAL;
01100             return NULL;
01101         }
01102         
01103         entry = cp_hashlist_create_entry(iterator->list, 
01104                                          iterator->list->mode, 
01105                                          key, 
01106                                          value);
01107         if (entry == NULL) return NULL;
01108         cp_hashlist_insert_internal(iterator->list, entry);
01109         new_entry = entry;
01110         
01111         entry->next = *iterator->pos;
01112 
01113         if (*iterator->pos)
01114         {
01115             entry->prev = (*iterator->pos)->prev;
01116             (*iterator->pos)->prev = entry;
01117             if (entry->prev)
01118                 entry->prev->next = entry;
01119         }
01120         else if (iterator->list->head == NULL) /* iterator not pointing at much - list may be empty */
01121             iterator->list->head = iterator->list->tail = entry;
01122         else if (iterator->pos == &iterator->list->head->prev) /* iterator moved before head */
01123         {
01124             entry->prev = NULL;
01125             entry->next = iterator->list->head;
01126             entry->next->prev = entry;
01127             iterator->list->head = entry;
01128         }
01129         else /* iterator moved after tail */
01130         {
01131             entry->prev = iterator->list->tail;
01132             entry->prev->next = entry;
01133             iterator->list->tail = entry;
01134         }
01135 
01136         iterator->pos = &entry->next; /* keep iterator on same entry */
01137         
01138         iterator->list->items++;
01139     }
01140     else /* mode is not NOSYNC and no LOCK_WRITE */
01141         errno = EINVAL;
01142 
01143     return new_entry;
01144 }
01145 
01146 cp_hashlist_entry *cp_hashlist_iterator_append(cp_hashlist_iterator *iterator, 
01147                                                void *key,
01148                                                void *value)
01149 {
01150     cp_hashlist_entry *new_entry = NULL;
01151 
01152     if ((iterator->list->mode & COLLECTION_MODE_NOSYNC) || 
01153         (iterator->lock_type == COLLECTION_LOCK_WRITE))
01154     {
01155         cp_hashlist_entry *entry;
01156 
01157         if ((iterator->list->mode & COLLECTION_MODE_MULTIPLE_VALUES) == 0
01158             && cp_hashlist_contains_internal(iterator->list, key)) 
01159         {
01160             errno = EINVAL;
01161             return NULL;
01162         }
01163 
01164         entry = cp_hashlist_create_entry(iterator->list, 
01165                                          iterator->list->mode,
01166                                          key, 
01167                                          value);
01168         if (entry == NULL) return NULL;
01169         cp_hashlist_insert_internal(iterator->list, entry);
01170         new_entry = entry;
01171         
01172         entry->prev = *iterator->pos;
01173 
01174         if (*iterator->pos)
01175         {
01176             entry->next = (*iterator->pos)->next;
01177             (*iterator->pos)->next = entry;
01178             if (entry->next)
01179                 entry->next->prev = entry;
01180         }
01181         else if (iterator->list->tail == NULL) /* iterator not pointing at much - list may be empty */
01182             iterator->list->tail = iterator->list->head = entry;
01183         else if (iterator->pos == &iterator->list->tail->next) /* iterator moved after tail */
01184         {
01185             entry->next = NULL;
01186             entry->prev = iterator->list->tail;
01187             entry->prev->next = entry;
01188             iterator->list->tail = entry;
01189         }
01190         else /* iterator moved before head */
01191         {
01192             entry->next = iterator->list->head;
01193             entry->next->prev = entry;
01194             iterator->list->head = entry;
01195         }
01196 
01197         iterator->pos = &entry->prev; /* keep iterator on same entry */
01198         iterator->list->items++;
01199     }
01200     else /* mode is not NOSYNC and no LOCK_WRITE */
01201         errno = EINVAL;
01202 
01203     return new_entry;
01204 }
01205 
01206 void *cp_hashlist_iterator_remove(cp_hashlist_iterator *iterator)
01207 {
01208     void *rm_value = NULL;
01209 
01210     if ((iterator->list->mode & COLLECTION_MODE_NOSYNC) || 
01211         (iterator->lock_type == COLLECTION_LOCK_WRITE))
01212     {
01213         if (*iterator->pos)
01214         {
01215             cp_hashlist_entry *curr = *iterator->pos;
01216 
01217             if (curr->next)
01218                 iterator->pos = &curr->next->prev;
01219             else if (curr->prev)
01220                 iterator->pos = &curr->prev->next;
01221             else /* removing last item */
01222                 iterator->pos = &iterator->list->head;          
01223 
01224             curr = cp_hashlist_remove_internal(iterator->list, curr->key);
01225             rm_value = 
01226                 cp_hashlist_unlink_internal(iterator->list, 
01227                                             curr, iterator->list->mode);
01228         }
01229     }
01230 
01231     return rm_value;
01232 }
01233 
01234 /* ----------------------------------------------------------------- */
01238 /* ----------------------------------------------------------------- */
01239 /* Internal methods */
01240 /* ----------------------------------------------------------------- */
01241 
01242 static cp_hashlist_entry *
01243     cp_hashlist_insert_internal(cp_hashlist *list, 
01244                                 cp_hashlist_entry *entry)
01245 {
01246     cp_hashlist_entry **insert;
01247     unsigned long index;
01248 
01249     if (!(list->mode & COLLECTION_MODE_NORESIZE) && 
01250         list->items * 100 > list->table_size * list->fill_factor_max)
01251         cp_hashlist_resize_nosync(list, list->table_size * 2);
01252 
01253     index = abs((*list->hash_fn)(entry->key)) % list->table_size;
01254     insert = &list->table[index];
01255 
01256     /* accept doubles */
01257     while (*insert != NULL) 
01258         insert = &(*insert)->bucket;
01259 
01260     *insert = entry;
01261     list->items++;
01262 
01263     return entry;
01264 }
01265 
01266 
01267 static void *cp_hashlist_get_internal(cp_hashlist *list, void *key)
01268 {
01269     unsigned long index;
01270     cp_hashlist_entry *entry;
01271 
01272     index = abs((*list->hash_fn)(key)) % list->table_size;
01273     entry = list->table[index];
01274     while (entry && (*list->compare_fn)(entry->key, key)) 
01275         entry = entry->bucket;
01276 
01277 #if CP_HASHLIST_MULTIPLE_VALUES
01278     if ((list->mode & COLLECTION_MODE_MULTIPLE_VALUES) && entry)
01279     {
01280         cp_list *res = 
01281             cp_list_create_view(list->mode, 
01282                                 NULL, 
01283                                 list->copy_value,
01284                                 list->free_value,
01285                                 list->lock);
01286         cp_list_insert(res, entry->value);
01287 
01288         if (list->mode & COLLECTION_MODE_LIST_ORDER) /* list order */
01289         {
01290             cp_hashlist_entry *i;
01291             for (i = entry->prev; i; i++)
01292                 if ((*list->compare_fn)(i->key, key) == 0)
01293                     cp_list_insert(res, i->value);
01294 
01295             for (i = entry->next; i; i++)
01296                 if ((*list->compare_fn)(i->key, key) == 0)
01297                     cp_list_append(res, i->value);
01298         }
01299         else /* insertion order */
01300         {
01301             entry = entry->bucket;
01302             while (entry)
01303                 if ((*list->compare_fn)(entry->key, key) == 0)
01304                     cp_list_append(res, entry->value);
01305         }
01306 
01307         return res;
01308     }
01309 #endif
01310             
01311     return entry;
01312 }
01313 
01314 
01315 static cp_hashlist_entry *
01316     cp_hashlist_remove_entry_internal(cp_hashlist *list, 
01317                                       cp_hashlist_entry *entry)
01318 {
01319     cp_hashlist_entry **remove;
01320     unsigned long index;
01321 
01322     index = abs((*list->hash_fn)(entry->key)) % list->table_size;
01323     remove = &list->table[index];
01324     while (*remove != NULL) 
01325     {
01326         if (*remove == entry) break;
01327         remove = &(*remove)->bucket;
01328     }
01329 
01330     if (*remove) 
01331     {
01332         *remove = (*remove)->bucket;
01333         list->items--;
01334     } 
01335     else /* should _not_ happen */
01336     {
01337         printf("may day, cannot find that entry: %s\n", (char *) entry->key);
01338         return NULL;
01339     }
01340 
01341     return entry;
01342 }
01343 
01344 static cp_hashlist_entry *
01345     cp_hashlist_remove_internal(cp_hashlist *list, void *key)
01346 {
01347     cp_hashlist_entry **remove, *holder;
01348     unsigned long index;
01349 
01350     if (!(list->mode & COLLECTION_MODE_NORESIZE) && 
01351         list->items * 100 < list->table_size * list->fill_factor_min &&
01352         list->items > list->min_size)
01353         cp_hashlist_resize_nosync(list, list->table_size / 2);
01354 
01355     index = abs((*list->hash_fn)(key)) % list->table_size;
01356     remove = &list->table[index];
01357     while (*remove != NULL) 
01358     {
01359         if ((*list->compare_fn)((*remove)->key, key) == 0) break;
01360         remove = &(*remove)->bucket;
01361     }
01362 
01363     holder = NULL;
01364     if (*remove) 
01365     {
01366         holder = *remove;
01367         *remove = (*remove)->bucket;
01368         list->items--;
01369     }
01370 
01371     return holder;
01372 }
01373 
01374 
01375 static void cp_hashlist_entry_delete(cp_hashlist_entry *entry)
01376 {
01377     if (entry) free(entry);
01378 }
01379 
01380 static void 
01381     cp_hashlist_entry_release_by_option(cp_hashlist *list, 
01382                                         cp_hashlist_entry *entry, 
01383                                         int mode)
01384 {
01385     if (entry) 
01386     {
01387         if (mode & COLLECTION_MODE_DEEP) 
01388         {
01389             if (list->free_key) (*list->free_key)(entry->key);
01390             if (list->free_value) (*list->free_value)(entry->value);
01391         }
01392         free(entry);
01393     }
01394 }
01395 

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