hashtable.c

Go to the documentation of this file.
00001 
00015 /* ----------------------------------------------------------------- */
00016 
00017 #include <stdlib.h>
00018 #include <stdio.h>
00019 #include <string.h>
00020 #include <errno.h>
00021 #include "hashtable.h"
00022 #include "linked_list.h"
00023 #include "log.h"
00024 #include "common.h"
00025 #include "collection.h"
00026 #include "thread.h"
00027 #include "util.h"
00028 
00029 #include "config.h"
00030 #ifdef CP_HAS_STRINGS_H
00031 #include <strings.h>
00032 #endif
00033 
00034 #ifdef __OpenBSD__
00035 #include <sys/types.h>
00036 #include <sys/time.h>
00037 #include <unistd.h>
00038 #endif /* __OpenBSD__ */
00039 
00040 #ifndef CP_HASHTABLE_MULTIPLE_VALUES
00041 #define CP_HASHTABLE_MULTIPLE_VALUES 1
00042 #endif
00043 
00044 static int table_sizes[] = 
00045     {
00046            5,        7,       11,       23,       47,
00047           79,       97,      157,      197,      299,
00048          397,      599,      797,     1297,     1597,
00049         2499,     3199,     4799,     6397,     9599,
00050        12799,    19199,    25597,    38399,    51199,
00051        76799,   102397,   153599,   204797,   306797,
00052       409597,   614399,   819199,  1288799,  1638397, 
00053      2457599,  3276799,  4915217,  6553577,  9830393 
00054     };
00055 
00056 static int table_sizes_len = 40;
00057 
00058 
00059 unsigned long cp_hashtable_choose_size(unsigned long size_request)
00060 {
00061     unsigned long new_size;
00062 
00063     if (table_sizes[table_sizes_len - 1] < size_request)
00064     {
00065         for (new_size = table_sizes[table_sizes_len - 1]; 
00066              new_size < size_request; 
00067              new_size = new_size * 2 + 1);
00068     }
00069     else
00070     {
00071         int min = -1;
00072         int max = table_sizes_len - 1;
00073         int pos;
00074 
00075         while (max > min + 1)
00076         {
00077             pos = (max + min + 1) / 2;
00078             if (table_sizes[pos] < size_request)
00079                 min = pos;
00080             else
00081                 max = pos;
00082         }
00083 
00084         new_size = table_sizes[max];
00085     }
00086          
00087     return new_size;
00088 }
00089 
00090 cp_hashtable *cp_hashtable_create(unsigned long size_hint, 
00091                                   cp_hashfunction hash_fn, 
00092                                   cp_compare_fn compare_fn)
00093 {
00094     return cp_hashtable_create_by_option(0, size_hint, hash_fn, 
00095                                          compare_fn, NULL, NULL, NULL, NULL);
00096 }
00097 
00098 
00099 cp_hashtable *
00100     cp_hashtable_create_copy_mode(unsigned long size_hint, 
00101                                   cp_hashfunction hash_fn, 
00102                                   cp_compare_fn compare_fn, 
00103                                   cp_copy_fn copy_key, 
00104                                   cp_destructor_fn free_key,
00105                                   cp_copy_fn copy_value,
00106                                   cp_destructor_fn free_value)
00107 {
00108     return cp_hashtable_create_by_option(COLLECTION_MODE_DEEP | 
00109                                          COLLECTION_MODE_COPY, 
00110                                          size_hint, 
00111                                          hash_fn, 
00112                                          compare_fn, 
00113                                          copy_key, 
00114                                          free_key,
00115                                          copy_value,
00116                                          free_value);
00117 }
00118 
00119 cp_hashtable *
00120     cp_hashtable_create_by_option(int mode, unsigned long size_hint, 
00121                                   cp_hashfunction hash_fn, 
00122                                   cp_compare_fn compare_fn, 
00123                                   cp_copy_fn copy_key, 
00124                                   cp_destructor_fn free_key,
00125                                   cp_copy_fn copy_value,
00126                                   cp_destructor_fn free_value)
00127 {
00128     cp_hashtable *table;
00129     
00130     table = (cp_hashtable *) calloc(1, sizeof(cp_hashtable));
00131     if (table == NULL)
00132     {
00133         errno = ENOMEM;
00134         return NULL;
00135     }
00136 
00137     table->table_size = cp_hashtable_choose_size(size_hint);
00138     table->items = 0;
00139     table->table = (cp_hashtable_entry **) 
00140         calloc(table->table_size, sizeof(cp_hashtable_entry *));
00141     if (table->table == NULL) 
00142     {
00143         errno = ENOMEM;
00144         return NULL;
00145     }
00146 
00147     table->hash_fn = hash_fn;
00148     table->compare_fn = compare_fn;
00149     table->copy_key = copy_key;
00150     table->copy_value = copy_value;
00151     table->free_key = free_key;
00152     table->free_value = free_value;
00153 
00154     table->mode = mode;
00155 
00156     table->min_size = size_hint;
00157     table->fill_factor_min = CP_HASHTABLE_DEFAULT_MIN_FILL_FACTOR;
00158     table->fill_factor_max = CP_HASHTABLE_DEFAULT_MAX_FILL_FACTOR;
00159 
00160     table->resizing = 0;
00161 
00162     table->lock = malloc(sizeof(cp_lock));
00163     if (table->lock == NULL)
00164     {
00165         free(table->table);
00166         free(table);
00167         errno = ENOMEM;
00168         return NULL;
00169     }
00170   
00171     if (cp_lock_init(table->lock, NULL))
00172     {
00173         free(table->lock);
00174         free(table->table);
00175         free(table);
00176         return NULL;
00177     }
00178 
00179     return table;
00180 }
00181 
00182 cp_hashtable_entry *
00183     cp_hashtable_create_entry(cp_hashtable *table, 
00184                               int mode, 
00185                               void *key, 
00186                               void *value, 
00187                               long hashcode)
00188 {
00189     cp_hashtable_entry *entry;
00190 
00191     entry = (cp_hashtable_entry *) malloc(sizeof(cp_hashtable_entry));
00192     if (entry == NULL) 
00193     {
00194         errno = ENOMEM;
00195         return NULL;
00196     }
00197 
00198     if (mode & COLLECTION_MODE_COPY) 
00199     {
00200         entry->key = table->copy_key ? (*table->copy_key)(key) : key;
00201         entry->value = table->copy_value ? (*table->copy_value)(value) :value;
00202     } 
00203     else 
00204     {
00205         entry->key = key;
00206         entry->value = value;    
00207     }
00208 
00209     entry->hashcode = hashcode;
00210     entry->next = NULL;
00211 
00212     return entry;
00213 }
00214 
00215     
00216 void cp_hashtable_destroy(cp_hashtable *table)
00217 {
00218     long i;
00219     cp_hashtable_entry *entry, *next;
00220     
00221     table->mode |= COLLECTION_MODE_NORESIZE;
00222 
00223     if (table->resizing) 
00224     {
00225         struct timeval timeout;
00226         timeout.tv_sec = 0;
00227         timeout.tv_usec = 10;
00228         while (table->resizing)
00229             select(0, NULL, NULL, NULL, &timeout);
00230     }
00231         
00232     for (i = 0; i < table->table_size; i++) 
00233     {
00234         entry = table->table[i];
00235         while (entry != NULL) 
00236         {
00237             next = entry->next;
00238             if (table->mode & COLLECTION_MODE_DEEP) 
00239             {
00240                 if (table->free_key)
00241                     (*table->free_key)(entry->key);
00242                 if (table->free_value)
00243                     (*table->free_value)(entry->value);
00244             }
00245             free(entry);
00246             entry = next;
00247         }
00248     }
00249         
00250     free(table->table);
00251     cp_lock_destroy(table->lock);
00252     free(table->lock);
00253     free(table);
00254 }
00255 
00256 void cp_hashtable_destroy_deep(cp_hashtable *table)
00257 {
00258     cp_hashtable_set_mode(table, COLLECTION_MODE_DEEP);
00259     cp_hashtable_destroy_custom(table, table->free_key, table->free_value);
00260 }
00261 
00262 void cp_hashtable_destroy_custom(cp_hashtable *table, cp_destructor_fn dk, cp_destructor_fn dv)
00263 {
00264     long i;
00265     cp_hashtable_entry *entry, *next;
00266 
00267     if (table->resizing) 
00268     {
00269         struct timeval timeout;
00270         timeout.tv_sec = 0;
00271         timeout.tv_usec = 10;
00272         while (table->resizing)
00273             select(0, NULL, NULL, NULL, &timeout);
00274     }
00275 
00276     for (i = 0; i < table->table_size; i++) 
00277     {
00278         entry = table->table[i];
00279         while (entry != NULL) 
00280         {
00281             next = entry->next;
00282             if (dk) (*dk)(entry->key);
00283             if (dv) (*dv)(entry->value);
00284             free(entry);
00285             entry = next;
00286         }
00287     }
00288         
00289     free(table->table);
00290     cp_lock_destroy(table->lock);
00291     free(table->lock);
00292     free(table);
00293 }
00294 
00295 
00296 void cp_hashtable_destroy_shallow(cp_hashtable *table)
00297 {
00298     cp_hashtable_unset_mode(table, COLLECTION_MODE_DEEP);
00299     cp_hashtable_destroy(table);
00300 }
00301 
00302 int cp_hashtable_lock_internal(cp_hashtable *table, int type)
00303 {
00304     int rc;
00305 
00306     switch (type)
00307     {
00308         case COLLECTION_LOCK_READ:
00309             rc = cp_lock_rdlock(table->lock);
00310             break;
00311 
00312         case COLLECTION_LOCK_WRITE:
00313             rc = cp_lock_wrlock(table->lock);
00314             break;
00315 
00316         case COLLECTION_LOCK_NONE:
00317             rc = 0;
00318             break;
00319 
00320         default:
00321             rc = EINVAL;
00322             break;
00323     }
00324 
00325     return rc;
00326 }
00327     
00328 int cp_hashtable_unlock_internal(cp_hashtable *table)
00329 {
00330     return cp_lock_unlock(table->lock);
00331 }
00332 
00333 int cp_hashtable_txlock(cp_hashtable *table, int type)
00334 {
00335     if (table->mode & COLLECTION_MODE_NOSYNC) return 0;
00336     if (table->mode & COLLECTION_MODE_IN_TRANSACTION && 
00337         table->txtype == COLLECTION_LOCK_WRITE)
00338     {
00339         cp_thread self = cp_thread_self();
00340         if (cp_thread_equal(self, table->txowner)) return 0;
00341     }
00342     return cp_hashtable_lock_internal(table, type);
00343 }
00344 
00345 int cp_hashtable_txunlock(cp_hashtable *table)
00346 {
00347     if (table->mode & COLLECTION_MODE_NOSYNC) return 0;
00348     if (table->mode & COLLECTION_MODE_IN_TRANSACTION && 
00349         table->txtype == COLLECTION_LOCK_WRITE)
00350     {
00351         cp_thread self = cp_thread_self();
00352         if (cp_thread_equal(self, table->txowner)) return 0;
00353     }
00354     return cp_hashtable_unlock_internal(table);
00355 }
00356 
00357 /* lock and set the transaction indicators */
00358 int cp_hashtable_lock(cp_hashtable *table, int type)
00359 {
00360     int rc;
00361     if ((table->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00362     if ((rc = cp_hashtable_lock_internal(table, type))) return rc;
00363     table->txtype = type;
00364     table->txowner = cp_thread_self();
00365     table->mode |= COLLECTION_MODE_IN_TRANSACTION;
00366     return 0;
00367 }
00368 
00369 /* unset the transaction indicators and unlock */
00370 int cp_hashtable_unlock(cp_hashtable *table)
00371 {
00372     cp_thread self = cp_thread_self();
00373     if (table->txowner == self)
00374     {
00375         table->txtype = 0;
00376         table->txowner = 0;
00377         table->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00378     }
00379     else if (table->txtype == COLLECTION_LOCK_WRITE)
00380         return -1;
00381     return cp_hashtable_unlock_internal(table);
00382 }
00383 
00384 
00385 
00386 int cp_hashtable_set_mode(cp_hashtable *table, int mode)
00387 {
00388     int syncbit; 
00389     /* can't set NOSYNC in the middle of a transaction */
00390     if ((table->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00391         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00392 
00393     syncbit = table->mode & COLLECTION_MODE_NOSYNC;
00394     if (!syncbit)
00395         cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE);
00396     table->mode |= mode;
00397     if (!syncbit)
00398         cp_hashtable_txunlock(table);
00399 
00400     return 0;
00401 }
00402 
00403 int cp_hashtable_get_mode(cp_hashtable *table)
00404 {
00405     return table->mode;
00406 }
00407 
00408 int cp_hashtable_unset_mode(cp_hashtable *table, int mode)
00409 {
00410     int syncbit = table->mode & COLLECTION_MODE_NOSYNC;
00411     if (!syncbit)
00412         cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE);
00413     table->mode &= table->mode ^ mode;
00414     if (!syncbit)
00415         cp_hashtable_txunlock(table);
00416     return 0;
00417 }
00418 
00430 void *lookup_internal(cp_hashtable *table, void *key, long code, int option, int resize)
00431 {
00432     cp_hashtable_entry *entry;
00433     void *ret = NULL;
00434 
00435     entry = resize ? table->resize_table[code % table->resize_len]
00436                    : table->table[code % table->table_size];
00437 
00438     while (entry != NULL && (*table->compare_fn)(key, entry->key)) 
00439         entry = entry->next;
00440     
00441     if (entry)
00442     {
00443 #if CP_HASHTABLE_MULTIPLE_VALUES
00444         if (option & COLLECTION_MODE_MULTIPLE_VALUES)
00445         {
00446             cp_list *l = 
00447                 cp_list_create_view(table->mode, 
00448                                     NULL, 
00449                                     table->copy_value,
00450                                     table->free_value,
00451                                     table->lock);
00452             cp_list_insert(l, entry->value);
00453             entry = entry->next;
00454             while (entry != NULL) 
00455             {
00456                 if ((*table->compare_fn)(key, entry->key) == 0) 
00457                     cp_list_append(l, entry->value);
00458 
00459                 entry = entry->next;
00460             }
00461 
00462             ret = l;
00463         }
00464         else 
00465 #endif
00466         ret = entry->value;
00467     }
00468 
00469     return ret;
00470 }
00471 
00481 void *cp_hashtable_get_by_option(cp_hashtable *table, void *key, int option)
00482 {
00483     long code;
00484     void *ret;
00485 
00486     if (table == NULL || key == NULL)
00487     {
00488         errno = EINVAL;
00489         return NULL;
00490     }
00491 
00492     if (cp_hashtable_txlock(table, COLLECTION_LOCK_READ)) return NULL;
00493 
00494     code = abs((*table->hash_fn)(key));
00495     ret = lookup_internal(table, key, code, option, 0);
00496     /* when resizing, search also there */
00497     if (ret == NULL && table->resizing) 
00498         ret = lookup_internal(table, key, code, option, 1);
00499 
00500     cp_hashtable_txunlock(table);
00501 
00502     return ret;
00503 }
00504 
00516 void *cp_hashtable_resize_thread(void *tbl)
00517 {
00518     long i, old_size, index;
00519     long new_size;
00520     cp_hashtable_entry **new_table, **old_table;
00521     cp_hashtable_entry **insert, *entry;
00522     cp_hashtable *table = (cp_hashtable *) tbl;
00523 
00524     new_size = table->table_size;
00525     new_table = table->table;
00526 
00527     old_size = table->resize_len;
00528     old_table = table->resize_table;
00529 
00530 #ifdef __TRACE__
00531     DEBUGMSG("resize %d to %d - resize thread starting\n", old_size, new_size);
00532 #endif
00533 
00534     /* copy old table into new table, bucket by bucket */
00535     for (i = 0; i < old_size; i++) 
00536     {
00537 //        if (!(table->mode & COLLECTION_MODE_NOSYNC))
00538         cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE);
00539         entry = old_table[i];
00540         while (entry != NULL) 
00541         {
00542             index = entry->hashcode % new_size;
00543             insert = &new_table[index];
00544             while (*insert != NULL)
00545                 insert = &(*insert)->next;
00546 
00547             *insert = entry;
00548             entry = entry->next;
00549             (*insert)->next = NULL;
00550         }
00551         old_table[i] = NULL;
00552 
00553 //        if (!(table->mode & COLLECTION_MODE_NOSYNC))
00554            cp_hashtable_txunlock(table);
00555     }
00556 
00557     /* cleanup */
00558 //    if (!(table->mode & COLLECTION_MODE_NOSYNC)) 
00559     cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE);
00560     free(table->resize_table); table->resize_table = NULL;
00561     table->resizing = 0;
00562 //    if (!(table->mode & COLLECTION_MODE_NOSYNC)) 
00563 
00564 #ifdef __TRACE__
00565     DEBUGMSG("resize %d to %d - done\n", old_size, new_size);
00566 #endif
00567     cp_hashtable_txunlock(table);
00568 
00569     return NULL;
00570 }
00571 
00572 int cp_hashtable_set_min_size(cp_hashtable *table, int min_size)
00573 {
00574     if (cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE)) return -1;
00575     table->min_size = min_size;
00576     cp_hashtable_txunlock(table);
00577     return 0;
00578 }
00579 
00580 
00581 int cp_hashtable_set_max_fill_factor(cp_hashtable *table, int fill_factor)
00582 {
00583     if (cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE)) return -1;
00584     table->fill_factor_max = fill_factor;
00585     cp_hashtable_txunlock(table);
00586     return 0;
00587 }
00588 
00589 int cp_hashtable_set_min_fill_factor(cp_hashtable *table, int fill_factor)
00590 {
00591     if (cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE)) return -1;
00592     table->fill_factor_min = fill_factor;
00593     cp_hashtable_txunlock(table);
00594     return 0;
00595 }
00596 
00597 
00603 void *cp_hashtable_resize(cp_hashtable *table, long new_size)
00604 {
00605     cp_hashtable_entry **new_table;
00606 
00607     if (table->resizing) return NULL;
00608 
00609     new_table = (cp_hashtable_entry **) malloc(new_size * sizeof(cp_hashtable_entry *));
00610     if (new_table == NULL) 
00611     {
00612         errno = ENOMEM;
00613         return NULL;
00614     }
00615     memset(new_table, 0, new_size * sizeof(cp_hashtable_entry *));
00616 
00617     table->resize_table = table->table;
00618     table->resize_len = table->table_size;
00619     table->table = new_table;
00620     table->table_size = new_size;
00621     table->resizing = 1;
00622 
00623     cp_thread_create(table->resize_thread, NULL, cp_hashtable_resize_thread, table);
00624     cp_thread_detach(table->resize_thread);
00625 
00626     return NULL;
00627 }
00628 
00638 void *cp_hashtable_resize_nosync(cp_hashtable *table, unsigned long new_size)
00639 {
00640     unsigned long old_size;
00641     cp_hashtable_entry **old_table;
00642     cp_hashtable_entry *entry, *next, **insert;
00643     unsigned long i, index;
00644 
00645     old_size = table->table_size;
00646     old_table = table->table;
00647     
00648     table->table_size = cp_hashtable_choose_size(new_size);
00649 
00650 #ifdef __TRACE__
00651     DEBUGMSG("resizing table (nosync): %d to %d\n", old_size, table->table_size);
00652 #endif
00653 
00654     table->table = (cp_hashtable_entry **) malloc(table->table_size * sizeof(cp_hashtable_entry *));
00655     memset(table->table, 0, table->table_size * sizeof(cp_hashtable_entry *));
00656 
00657     if (table->table == NULL) 
00658     {
00659         errno = ENOMEM;
00660         return NULL;
00661     }
00662 
00663     for (i = 0; i < old_size; i++) 
00664     {
00665         entry = old_table[i];
00666         while (entry != NULL) 
00667         {
00668             index = entry->hashcode % table->table_size;
00669             next = entry->next;
00670             entry->next = NULL;
00671             insert = &table->table[index];
00672             while (*insert != NULL) 
00673                 insert = &(*insert)->next;
00674 
00675             *insert = entry;
00676             
00677             entry = next;
00678         }
00679     }
00680 
00681     free(old_table);
00682 
00683     return table;
00684 }
00685  
00697 static cp_hashtable_entry **cp_hashtable_replace_internal(cp_hashtable *table, 
00698                                                           void *key, 
00699                                                           void *value, 
00700                                                           unsigned long code, 
00701                                                           int option,
00702                                                           int resize)
00703 {
00704     cp_hashtable_entry **entry;
00705     unsigned long index;
00706 
00707     index = resize ? code % table->resize_len : code % table->table_size;
00708     
00709     entry = resize ? &table->resize_table[index] : &table->table[index];
00710     while (*entry != NULL) 
00711     {
00712 #if CP_HASHTABLE_MULTIPLE_VALUES
00713         if (!(option & COLLECTION_MODE_MULTIPLE_VALUES) && 
00714             (*table->compare_fn)(key, (*entry)->key) == 0) 
00715 #else
00716         if ((*table->compare_fn)(key, (*entry)->key) == 0) 
00717 #endif
00718         {
00719             if (option & COLLECTION_MODE_DEEP) 
00720             {
00721                 if (table->free_key)
00722                     (*table->free_key)((*entry)->key);
00723                 if (table->free_value)
00724                     (*table->free_value)((*entry)->value);
00725                 (*entry)->key = key;
00726             }
00727         
00728             if (option & COLLECTION_MODE_COPY) 
00729             {
00730                 (*entry)->key = table->copy_key ? (*table->copy_key)(key) : key;
00731                 (*entry)->value = table->copy_value ? (*table->copy_value)(value) : value;
00732             }
00733             else
00734                 (*entry)->value = value;
00735 
00736             (*entry)->hashcode = code;
00737             break;
00738         }
00739 
00740         entry = &(*entry)->next;
00741     }
00742 
00743     return entry;
00744 }
00745 
00746 void *cp_hashtable_put(cp_hashtable *table, void *key, void *value)
00747 {
00748     return cp_hashtable_put_by_option(table, key, value, table->mode);
00749 }
00750 
00751 void *cp_hashtable_put_safe(cp_hashtable *table, void *key, void *value)
00752 {
00753     return cp_hashtable_put_by_option(table, key, value, table->mode | COLLECTION_MODE_DEEP);
00754 }
00755 
00756 void *cp_hashtable_put_copy(cp_hashtable *table, void *key, void *value)
00757 {
00758         return cp_hashtable_put_by_option(table, key, value, table->mode | COLLECTION_MODE_COPY);
00759 }
00760 
00761 
00762 /* actual insertion code */
00763 void *cp_hashtable_put_by_option(cp_hashtable *table, void *key, void *value, int option)
00764 {
00765     unsigned long code;
00766     cp_hashtable_entry **entry; /* defined ** for when initializing a bucket */ 
00767     int syncbit;
00768     void *ret = NULL;
00769 
00770     syncbit = table->mode & COLLECTION_MODE_NOSYNC;
00771     if (cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE)) return NULL;
00772 
00773     if ((option & COLLECTION_MODE_NORESIZE) == 0)
00774     {
00775         if ((table->items * 100) > 
00776             (table->table_size * table->fill_factor_max))
00777         {
00778             int new_size = cp_hashtable_choose_size(table->table_size * 2);
00779             if (syncbit)
00780                 cp_hashtable_resize_nosync(table, new_size);
00781             else
00782                 cp_hashtable_resize(table, new_size);
00783         }
00784     }
00785     
00786     code = abs((*table->hash_fn)(key));
00787 
00788     entry = cp_hashtable_replace_internal(table, key, value, code, option, 0);
00789 
00790     if (*entry == NULL && table->resizing) 
00791     {
00792         cp_hashtable_entry **resize_entry;
00793 
00794         resize_entry = cp_hashtable_replace_internal(table, key, value, code, option, 1);
00795         if (*resize_entry != NULL)  /* prevent write */
00796             entry = resize_entry;
00797 
00798     }
00799         
00800     if (*entry == NULL) 
00801     {
00802         /* no entry found, entry points at lookup location */
00803         *entry = cp_hashtable_create_entry(table, option, key, value, code);
00804         if (*entry) 
00805             table->items++;
00806     }
00807     
00808     if (*entry)
00809         ret = (*entry)->value;
00810 
00811     if (!syncbit) cp_hashtable_txunlock(table);
00812 
00813     return ret;
00814 }
00815 
00829 void *cp_hashtable_remove_internal(cp_hashtable *table, void *key, long code, int mode, int resize)
00830 {
00831     cp_hashtable_entry **entry, *item;
00832     void *value = NULL;
00833 
00834     entry = resize ? &table->resize_table[code % table->resize_len]
00835                    : &table->table[code % table->table_size];
00836 
00837     while (*entry != NULL) 
00838     {
00839         if ((*table->compare_fn)(key, (*entry)->key) == 0) 
00840         {
00841             /* entry now points either to the table->table element or to the  */
00842             /* next pointer in the parent entry                               */
00843             table->items--;
00844             item = *entry;
00845             *entry = item->next;
00846 
00847             value = item->value;
00848             if (mode & COLLECTION_MODE_DEEP) 
00849             {
00850                 if (table->free_key)
00851                     (*table->free_key)(item->key);
00852                 if (table->free_value)
00853                     (*table->free_value)(item->value);
00854             }
00855 
00856             free(item);
00857 
00858 #if CP_HASHTABLE_MULTIPLE_VALUES
00859             if (!(mode & COLLECTION_MODE_MULTIPLE_VALUES)) 
00860 #endif
00861             break; 
00862         }
00863 
00864         entry = &(*entry)->next;
00865     }
00866 
00867     return value;
00868 }
00869 
00881 void *cp_hashtable_remove_by_mode(cp_hashtable *table, void *key, int mode)
00882 {
00883     long code;
00884     void *value = NULL;
00885     int syncbit = table->mode & COLLECTION_MODE_NOSYNC;
00886     if (cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE)) return NULL;
00887 
00888     code = abs((*table->hash_fn)(key));
00889 
00890     value = cp_hashtable_remove_internal(table, key, code, mode, 0);
00891 
00892     if (table->resizing) 
00893     {
00894         void *resize_value;
00895         resize_value = cp_hashtable_remove_internal(table, key, code, mode, 1);
00896         if (value == NULL) value = resize_value;
00897     }
00898 
00899     if ((table->mode & COLLECTION_MODE_NORESIZE) == 0)
00900     {
00901         if (table->table_size > table->min_size &&
00902             ((table->items * 100) < 
00903             (table->table_size * table->fill_factor_min)))
00904         {
00905             int new_size = cp_hashtable_choose_size(table->table_size / 2);
00906             if (syncbit)
00907                 cp_hashtable_resize_nosync(table, new_size);
00908             else
00909                 cp_hashtable_resize(table, new_size);
00910         }
00911     }
00912 
00913     if (!syncbit) cp_hashtable_txunlock(table);
00914 
00915     return value;
00916 }
00917 
00918 int cp_hashtable_remove_all(cp_hashtable *table)
00919 {
00920     long i;
00921     cp_hashtable_entry *entry, *next;
00922     int deepbit = table->mode & COLLECTION_MODE_DEEP;
00923     cp_destructor_fn dk = table->free_key;
00924     cp_destructor_fn dv = table->free_value;
00925 
00926     if (cp_hashtable_txlock(table, COLLECTION_LOCK_WRITE)) return -1;
00927     
00928     for (i = 0; i < table->table_size; i++) 
00929     {
00930         if ((entry = table->table[i]) != NULL) 
00931         {
00932             while (entry != NULL) 
00933             {
00934                 next = entry->next;
00935                 if (deepbit)
00936                 {
00937                     if (dk) (*dk)(entry->key);
00938                     if (dv) (*dv)(entry->value);
00939                 }
00940                 free(entry);
00941                 entry = next;
00942             }
00943         }
00944     }
00945 
00946     memset(table->table, 0, sizeof(cp_hashtable_entry *) * table->table_size);
00947 
00948     if (table->resizing) 
00949     {
00950         for (i = 0; i < table->resize_len; i++) 
00951             if ((entry = table->resize_table[i]) != NULL) 
00952                 while (entry != NULL) 
00953                 {
00954                     next = entry->next;
00955                     if (deepbit)
00956                     {
00957                         if (dk) (*dk)(entry->key);
00958                         if (dv) (*dv)(entry->value);
00959                     }
00960                     free(entry);
00961                     entry = next;
00962                 }
00963         memset(table->resize_table, 0, sizeof(cp_hashtable_entry *) * table->resize_len);
00964     }
00965 
00966     cp_hashtable_txunlock(table);
00967     return 0;
00968 }
00969 
00970 /* remove using current mode settings */
00971 void *cp_hashtable_remove(cp_hashtable *table, void *key)
00972 {
00973     return cp_hashtable_remove_by_mode(table, key, table->mode);
00974 }
00975 
00976 
00983 int cp_hashtable_remove_deep(cp_hashtable *table, void *key)
00984 {
00985     return cp_hashtable_remove_by_mode(table, key
00986               , table->mode | COLLECTION_MODE_DEEP) != NULL;
00987 }
00988 
00989 int cp_hashtable_contains(cp_hashtable *table, void *key)
00990 {
00991     int rc = 0;
00992 
00993     if (table != NULL && key != NULL)
00994     {
00995         long code;
00996         void *val;
00997         int option;
00998         if (cp_hashtable_txlock(table, COLLECTION_LOCK_READ)) return -1;
00999 
01000         option = table->mode & COLLECTION_MODE_MULTIPLE_VALUES;
01001         code = abs((*table->hash_fn)(key));
01002         val = lookup_internal(table, key, code, table->mode, 0);
01003         /* when resizing, search also there */
01004         if (val == NULL && table->resizing) 
01005             val = lookup_internal(table, key, code, table->mode, 1);
01006 
01007         if (val != NULL)
01008         {
01009             rc = 1;
01010             if (option) cp_list_destroy(val);
01011         }
01012 
01013         cp_hashtable_txunlock(table);
01014     }
01015     else
01016         errno = EINVAL; //~~ and set rc = -1?
01017 
01018     return rc;
01019 }
01020 
01021 
01022 void *cp_hashtable_get(cp_hashtable *table, void *key)
01023 {
01024     return cp_hashtable_get_by_option(table, key, table->mode);
01025 }
01026 
01027 void **cp_hashtable_get_keys(cp_hashtable *table)
01028 {
01029     long i, j;
01030     void **keys;
01031     cp_hashtable_entry *entry = NULL;
01032     int rc = 0;
01033 
01034     if (table == NULL)
01035     {
01036         errno = EINVAL;
01037         return NULL;
01038     }
01039 
01040     if (cp_hashtable_txlock(table, COLLECTION_LOCK_READ)) return NULL;
01041 
01042     keys = (void **) calloc(table->items, sizeof(void *));
01043     if (keys == NULL) 
01044     {
01045         rc = ENOMEM;
01046         goto DONE;
01047     }
01048     
01049     for (i = 0, j = 0; i < table->table_size; i++) \
01050     {
01051         entry = table->table[i];
01052         while (entry != NULL) 
01053         {
01054             keys[j++] = entry->key;
01055             entry = entry->next;
01056         }
01057     }
01058 
01059     if (table->resizing) 
01060         for (i = 0; i < table->resize_len; i++) 
01061             entry = table->resize_table[i];
01062             while (entry != NULL) 
01063             {
01064                 keys[j++] = entry->key;
01065                 entry = entry->next;
01066             }
01067             
01068 DONE:
01069     cp_hashtable_txunlock(table);
01070     if (rc) errno = rc;
01071 
01072     return keys;
01073 }
01074     
01075 
01076 unsigned long cp_hashtable_count(cp_hashtable *table)
01077 {
01078     return (table) ? table->items : 0L; 
01079 }
01080 
01081 
01082 void **cp_hashtable_get_values(cp_hashtable *table)
01083 {
01084     long i, j;
01085     void **values;
01086     cp_hashtable_entry *entry;
01087     int rc = 0;
01088 
01089     if (cp_hashtable_txlock(table, COLLECTION_LOCK_READ)) return NULL;
01090 
01091     values = (void **) malloc(table->items * sizeof(void *));
01092     if (values == NULL) 
01093     {
01094         rc = ENOMEM;
01095         goto DONE;
01096     }
01097     
01098     for (i = 0, j = 0; i < table->table_size; i++) 
01099     {
01100         entry = table->table[i];
01101         while (entry != NULL) 
01102         {
01103             values[j++] = entry->value;
01104             entry = entry->next;
01105         }
01106     }        
01107 
01108     if (table->resizing) 
01109     {
01110         for (i = 0; i < table->resize_len; i++) 
01111         {
01112             entry = table->resize_table[i];
01113             while (entry != NULL) 
01114             {
01115                 values[j++] = entry->value;
01116                 entry = entry->next;
01117             }
01118         }
01119     }
01120 
01121 DONE:
01122     cp_hashtable_txunlock(table);
01123     if (rc) errno = rc;
01124 
01125     return values;
01126 }
01127 
01128 
01129 /* ------------------------------------------------------------------------ */
01130 /* ---   hash function implementations for primitive types & strings    --- */
01131 /* ------------------------------------------------------------------------ */
01132 
01133 unsigned long cp_hash_int(void *i)
01134 {
01135     return (long) *((int *) i);
01136 }
01137 
01138 
01139 int cp_hash_compare_int(void *i, void *j)
01140 {
01141     return *((int *) i) - *((int *) j);
01142 }
01143 
01144 unsigned long cp_hash_long(void *l)
01145 {
01146     return *((long *) l);
01147 }
01148 
01149 
01150 int cp_hash_compare_long(void *i, void *j)
01151 {
01152     long diff = *((long *) i) - *((long *) j);
01153     return diff > 0 ? 1 : diff < 0 ? -1 : 0;
01154 }
01155 
01156 unsigned long cp_hash_addr(void *addr)
01157 {
01158     return (unsigned long) addr;
01159 }
01160 
01161 int cp_hash_compare_addr(void *a1, void *a2)
01162 {
01163     return (long) a1 - (long) a2;
01164 }
01165 
01166 unsigned long cp_hash_string(void *str)
01167 {
01168     long res;
01169     char *_str;
01170     
01171     if (str == NULL) return 0; 
01172 
01173     _str = (char *) str;
01174     
01175     for (res = 1; *_str != '\0'; _str++)
01176         res = res * HASH_SEED + *_str;
01177 
01178     return res;
01179 }
01180     
01181 
01182 int cp_hash_compare_string(void *s1, void *s2)
01183 {
01184     if (s1 == NULL && s2 == NULL) return 0;
01185     if (s1 == NULL || s2 == NULL) return -1;
01186     return strcmp((char *) s1, (char *) s2);
01187 }
01188 
01189 #define CP_CHAR_UC(x) ((x) >= 'a' && (x) <= 'z' ? ((x) - 'a' + 'A') : (x))
01190         
01191 unsigned long cp_hash_istring(void *str)
01192 {
01193     long res;
01194     char *_str;
01195     
01196     if (str == NULL) return 0; 
01197 
01198     _str = (char *) str;
01199     
01200     for (res = 1; *_str != '\0'; _str++)
01201         res = res * HASH_SEED + CP_CHAR_UC(*_str);
01202 
01203     return res;
01204 }
01205 
01206 int cp_hash_compare_istring(void *s1, void *s2)
01207 {
01208     if (s1 == NULL && s2 == NULL) return 0;
01209     if (s1 == NULL || s2 == NULL) return -1;
01210     return strcasecmp((char *) s1, (char *) s2);
01211 }
01212 
01213 void *cp_hash_copy_string(void *element)
01214 {
01215     char *src;
01216     char *dst;
01217     size_t len;
01218     
01219     src = (char *) element;
01220     len = strlen(src) + 1;
01221     dst = (char *) malloc(len * sizeof(char));
01222 
01223     if (dst == NULL) return NULL;
01224 
01225 #ifdef CP_HAS_STRLCPY
01226     strlcpy(dst, src, len);
01227 #else
01228     strcpy(dst, src);
01229 #endif /* CP_HAS_STRLCPY */
01230     return dst;
01231 }
01232 
01233 unsigned long cp_hash_float(void *addr)
01234 {
01235     unsigned long *p = (unsigned long *) addr;
01236     return *p;
01237 }
01238 
01239 int cp_hash_compare_float(void *a1, void *a2)
01240 {
01241     float f1 = *(float *) a1;
01242     float f2 = *(float *) a2;
01243     if (f1 > f2) return 1;
01244     if (f1 < f2) return -1;
01245     return 0;
01246 }
01247 
01248 unsigned long cp_hash_double(void *d)
01249 {
01250     unsigned long *p = (unsigned long *) d;
01251     if (sizeof(unsigned long) < sizeof(double))
01252         return p[0] ^ p[1];
01253     return *p;
01254 }
01255 
01256 int cp_hash_compare_double(void *a1, void *a2)
01257 {
01258     double d1 = *(double *) a1;
01259     double d2 = *(double *) a2;
01260     if (d1 > d2) return 1;
01261     if (d1 < d2) return -1;
01262     return 0;
01263 }
01264 

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