00001
00013
00014
00015 #include <stdio.h>
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
00029 #ifndef CP_HASHLIST_MULTIPLE_VALUES
00030 #define CP_HASHLIST_MULTIPLE_VALUES 1
00031 #endif
00032
00033
00034
00035
00036
00037 int cp_hashlist_txlock(cp_hashlist *list, int type);
00038
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
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
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)
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))
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))
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
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
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
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)
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)
01121 iterator->list->head = iterator->list->tail = entry;
01122 else if (iterator->pos == &iterator->list->head->prev)
01123 {
01124 entry->prev = NULL;
01125 entry->next = iterator->list->head;
01126 entry->next->prev = entry;
01127 iterator->list->head = entry;
01128 }
01129 else
01130 {
01131 entry->prev = iterator->list->tail;
01132 entry->prev->next = entry;
01133 iterator->list->tail = entry;
01134 }
01135
01136 iterator->pos = &entry->next;
01137
01138 iterator->list->items++;
01139 }
01140 else
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)
01182 iterator->list->tail = iterator->list->head = entry;
01183 else if (iterator->pos == &iterator->list->tail->next)
01184 {
01185 entry->next = NULL;
01186 entry->prev = iterator->list->tail;
01187 entry->prev->next = entry;
01188 iterator->list->tail = entry;
01189 }
01190 else
01191 {
01192 entry->next = iterator->list->head;
01193 entry->next->prev = entry;
01194 iterator->list->head = entry;
01195 }
01196
01197 iterator->pos = &entry->prev;
01198 iterator->list->items++;
01199 }
01200 else
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
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
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
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)
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
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
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