sorted_hash.c

00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <errno.h>
00004 
00005 #include "collection.h"
00006 #include "vector.h"
00007 #include "sorted_hash.h"
00008 
00009 cp_sh_entry *cp_sh_entry_create(void *key, void *value, cp_mempool *pool)
00010 {
00011     cp_sh_entry *node;
00012     
00013     if (pool) 
00014         node = (cp_sh_entry *) cp_mempool_calloc(pool);
00015     else
00016         node = (cp_sh_entry *) calloc(1, sizeof(cp_sh_entry));
00017 
00018     if (node == NULL) return NULL;
00019 
00020     node->key = key;
00021     node->value = value;
00022 
00023     return node;
00024 }
00025     
00026 /* implement COLLECTION_MODE_COPY if set */
00027 static cp_sh_entry *create_sh_entry(cp_sorted_hash *tree, void *key, void *value)
00028 {
00029     if (tree->mode & COLLECTION_MODE_COPY)
00030     {
00031         void *k, *v;
00032         k = tree->key_copy ? (*tree->key_copy)(key) : key;
00033         if (k)
00034         {
00035             v = tree->value_copy ? (*tree->value_copy)(value) : value;
00036             if (v)
00037             {
00038                 if (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES)
00039                 {
00040                     cp_vector *m = cp_vector_create(1);
00041                     if (m == NULL) return NULL;
00042                     cp_vector_add_element(m, v);
00043                     v = m;
00044                 }
00045                 return cp_sh_entry_create(k, v, tree->mempool);
00046             }
00047         }
00048     }
00049     else if (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES)
00050     {
00051         cp_vector *m = cp_vector_create(1);
00052         if (m == NULL) return NULL;
00053         cp_vector_add_element(m, value);
00054         return cp_sh_entry_create(key, m, tree->mempool);
00055     }
00056     else 
00057         return cp_sh_entry_create(key, value, tree->mempool);
00058 
00059     return NULL;
00060 }
00061 
00062 void cp_sorted_hash_destroy_entry_deep(cp_sorted_hash *owner, cp_sh_entry *node)
00063 {
00064     while (node)
00065     {
00066         if (node->right)
00067         {
00068             node = node->right;
00069             node->up->right = NULL;
00070         }
00071         else if (node->left)
00072         {
00073             node = node->left;
00074             node->up->left = NULL;
00075         }
00076         else
00077         {
00078             cp_sh_entry *tmp = node;
00079             if (node->multiple)
00080             {
00081                 cp_sh_entry *m = node->multiple;
00082                 cp_sh_entry *n;
00083                 do
00084                 {
00085                     n = m->multiple;
00086                     cp_sorted_hash_destroy_entry(owner, m);
00087                     m = n;
00088                 } while (m);
00089             }
00090             node = node->up;
00091             cp_sorted_hash_destroy_entry(owner, tmp);
00092         }
00093     }
00094 }
00095 
00096 void cp_sorted_hash_destroy_entry(cp_sorted_hash *tree, cp_sh_entry *node)
00097 {
00098     if (node)
00099     {
00100         if ((tree->mode & COLLECTION_MODE_DEEP))
00101         {
00102             if (tree->key_dtr) (*tree->key_dtr)(node->key);
00103             if (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES)
00104             {
00105                 if (node->value)
00106                     cp_vector_destroy_custom(node->value, tree->value_dtr);
00107             }
00108             else if (tree->value_dtr) 
00109                 (*tree->value_dtr)(node->value);
00110         }
00111         else if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) && node->value)
00112             cp_vector_destroy(node->value);
00113         if (tree->mempool)
00114             cp_mempool_free(tree->mempool, node);
00115         else
00116             free(node);
00117     }
00118 }
00119 
00120 
00121 cp_sorted_hash *cp_sorted_hash_create(cp_hashfunction hash, 
00122                                       cp_compare_fn cmp_key, 
00123                                       cp_mapping_cmp_fn cmp_mapping)
00124 {
00125     cp_sorted_hash *tree = calloc(1, sizeof(cp_sorted_hash));
00126     if (tree == NULL) return NULL;
00127 
00128     tree->size = 11;
00129     tree->table = (cp_sh_entry **) calloc(tree->size, sizeof(cp_sh_entry));
00130     if (tree->table == NULL)
00131     {
00132         free(tree);
00133         return NULL;
00134     }
00135 
00136     tree->mode = COLLECTION_MODE_NOSYNC;
00137     tree->hash = hash;
00138     tree->cmp_key = cmp_key;
00139     tree->cmp_mapping = cmp_mapping;
00140 
00141     return tree;
00142 }
00143 
00144 /*
00145  * complete parameter create function
00146  */
00147 cp_sorted_hash *
00148     cp_sorted_hash_create_by_option(int mode, 
00149                                     unsigned long size_hint,
00150                                     cp_hashfunction hash, 
00151                                     cp_compare_fn cmp_key, 
00152                                     cp_mapping_cmp_fn cmp_mapping, 
00153                                     cp_copy_fn key_copy, 
00154                                     cp_destructor_fn key_dtr,
00155                                     cp_copy_fn val_copy, 
00156                                     cp_destructor_fn val_dtr)
00157 {
00158     cp_sorted_hash *tree = calloc(1, sizeof(cp_sorted_hash));
00159     if (tree == NULL) return NULL;
00160 
00161     tree->size = cp_hashtable_choose_size(size_hint);
00162     tree->table = (cp_sh_entry **) calloc(tree->size, sizeof(cp_sh_entry));
00163     if (tree->table == NULL)
00164     {
00165         free(tree);
00166         return NULL;
00167     }
00168 
00169     tree->mode = COLLECTION_MODE_NOSYNC;
00170     tree->hash = hash;
00171     tree->cmp_key = cmp_key;
00172     tree->cmp_mapping = cmp_mapping;
00173     
00174     tree->mode = mode;
00175     tree->key_copy = key_copy;
00176     tree->key_dtr = key_dtr;
00177     tree->value_copy = val_copy;
00178     tree->value_dtr = val_dtr;
00179 
00180     if (!(mode & COLLECTION_MODE_NOSYNC))
00181     {
00182         tree->lock = malloc(sizeof(cp_lock));
00183         if (tree->lock == NULL) 
00184         {
00185             cp_sorted_hash_destroy(tree);
00186             return NULL;
00187         }
00188         if (cp_lock_init(tree->lock, NULL) != 0)
00189         {
00190             cp_sorted_hash_destroy(tree);
00191             return NULL;
00192         }
00193     }
00194 
00195     return tree;
00196 }
00197 
00198 
00199 void cp_sorted_hash_destroy(cp_sorted_hash *tree)
00200 {
00201     if (tree)
00202     {
00203         cp_sorted_hash_destroy_entry_deep(tree, tree->root);
00204         if (tree->lock)
00205         {
00206             cp_lock_destroy(tree->lock);
00207             free(tree->lock);
00208         }
00209         free(tree->table);
00210         free(tree);
00211     }
00212 }
00213 
00214 void cp_sorted_hash_destroy_custom(cp_sorted_hash *tree, 
00215                               cp_destructor_fn key_dtr,
00216                               cp_destructor_fn val_dtr)
00217 {
00218     tree->mode |= COLLECTION_MODE_DEEP;
00219     tree->key_dtr = key_dtr;
00220     tree->value_dtr = val_dtr;
00221     cp_sorted_hash_destroy(tree);
00222 }
00223 
00224 static int cp_sorted_hash_lock_internal(cp_sorted_hash *tree, int type)
00225 {
00226     int rc;
00227 
00228     switch (type)
00229     {
00230         case COLLECTION_LOCK_READ:
00231             rc = cp_lock_rdlock(tree->lock);
00232             break;
00233 
00234         case COLLECTION_LOCK_WRITE:
00235             rc = cp_lock_wrlock(tree->lock);
00236             break;
00237 
00238         case COLLECTION_LOCK_NONE:
00239             rc = 0;
00240             break;
00241 
00242         default:
00243             rc = EINVAL;
00244             break;
00245     }
00246 
00247     /* api functions may rely on errno to report locking failure */
00248     if (rc) errno = rc;
00249 
00250     return rc;
00251 }
00252 
00253 static int cp_sorted_hash_unlock_internal(cp_sorted_hash *tree)
00254 {
00255     return cp_lock_unlock(tree->lock);
00256 }
00257 
00258 int cp_sorted_hash_txlock(cp_sorted_hash *tree, int type)
00259 {
00260     /* clear errno to allow client code to distinguish between a NULL return
00261      * value indicating the tree doesn't contain the requested value and NULL
00262      * on locking failure in tree operations
00263      */
00264     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00265     if (tree->mode & COLLECTION_MODE_IN_TRANSACTION && 
00266         tree->txtype == COLLECTION_LOCK_WRITE)
00267     {
00268         cp_thread self = cp_thread_self();
00269         if (cp_thread_equal(self, tree->txowner)) return 0;
00270     }
00271     errno = 0;
00272     return cp_sorted_hash_lock_internal(tree, type);
00273 }
00274 
00275 int cp_sorted_hash_txunlock(cp_sorted_hash *tree)
00276 {
00277     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00278     if (tree->mode & COLLECTION_MODE_IN_TRANSACTION && 
00279         tree->txtype == COLLECTION_LOCK_WRITE)
00280     {
00281         cp_thread self = cp_thread_self();
00282         if (cp_thread_equal(self, tree->txowner)) return 0;
00283     }
00284     return cp_sorted_hash_unlock_internal(tree);
00285 }
00286 
00287 /* lock and set the transaction indicators */
00288 int cp_sorted_hash_lock(cp_sorted_hash *tree, int type)
00289 {
00290     int rc;
00291     if ((tree->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00292     if ((rc = cp_sorted_hash_lock_internal(tree, type))) return rc;
00293     tree->txtype = type;
00294     tree->txowner = cp_thread_self();
00295     tree->mode |= COLLECTION_MODE_IN_TRANSACTION;
00296     return 0;
00297 }
00298 
00299 /* unset the transaction indicators and unlock */
00300 int cp_sorted_hash_unlock(cp_sorted_hash *tree)
00301 {
00302     cp_thread self = cp_thread_self();
00303     if (tree->txowner == self)
00304     {
00305         tree->txowner = 0;
00306         tree->txtype = 0;
00307         tree->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00308     }
00309     else if (tree->txtype == COLLECTION_LOCK_WRITE)
00310         return -1;
00311     return cp_sorted_hash_unlock_internal(tree);
00312 }
00313 
00314 /* set mode bits on the tree mode indicator */
00315 int cp_sorted_hash_set_mode(cp_sorted_hash *tree, int mode)
00316 {
00317     int rc;
00318     int nosync; 
00319 
00320     /* can't set NOSYNC in the middle of a transaction */
00321     if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00322         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00323     /* COLLECTION_MODE_MULTIPLE_VALUES must be set at creation time */  
00324     if (mode & COLLECTION_MODE_MULTIPLE_VALUES) return EINVAL;
00325 
00326     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00327     
00328     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00329 
00330     tree->mode |= mode;
00331 
00332     if (!nosync)
00333         cp_sorted_hash_txunlock(tree);
00334 
00335     return 0;
00336 }
00337 
00338 /* unset mode bits on the tree mode indicator. if unsetting 
00339  * COLLECTION_MODE_NOSYNC and the tree was not previously synchronized, the 
00340  * internal synchronization structure is initialized.
00341  */
00342 int cp_sorted_hash_unset_mode(cp_sorted_hash *tree, int mode)
00343 {
00344     int rc;
00345     int nosync;
00346 
00347     /* COLLECTION_MODE_MULTIPLE_VALUES can't be unset */
00348     if (mode & COLLECTION_MODE_MULTIPLE_VALUES) return EINVAL;
00349 
00350     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00351     
00352     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00353 
00354     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00355     if ((mode & COLLECTION_MODE_NOSYNC) && tree->lock == NULL)
00356     {
00357         /* tree can't be locked in this case, no need to unlock on failure */
00358         if ((tree->lock = malloc(sizeof(cp_lock))) == NULL)
00359             return -1;
00360         if (cp_lock_init(tree->lock, NULL))
00361             return -1;
00362     }
00363     
00364     /* unset specified bits */
00365     tree->mode &= tree->mode ^ mode;
00366     if (!nosync)
00367         cp_sorted_hash_txunlock(tree);
00368 
00369     return 0;
00370 }
00371 
00372 int cp_sorted_hash_get_mode(cp_sorted_hash *tree)
00373 {
00374     return tree->mode;
00375 }
00376 
00377 
00378 static cp_sh_entry *sibling(cp_sh_entry *node)
00379 {
00380     return node == node->up->left ? node->up->right : node->up->left;
00381 }
00382 
00383 static int is_right_child(cp_sh_entry *node)
00384 {
00385     return (node->up->right == node);
00386 }
00387 
00388 static int is_left_child(cp_sh_entry *node)
00389 {
00390     return (node->up->left == node);
00391 }
00392 
00393 /*         left rotate
00394  *
00395  *    (P)                (Q)
00396  *   /   \              /   \
00397  *  1    (Q)    ==>   (P)    3
00398  *      /   \        /   \
00399  *     2     3      1     2
00400  *
00401  */
00402 static void left_rotate(cp_sorted_hash *tree, cp_sh_entry *p)
00403 {
00404     cp_sh_entry *q = p->right;
00405     cp_sh_entry **sup;
00406     
00407     if (p->up)
00408         sup = is_left_child(p) ? &(p->up->left) : &(p->up->right);
00409     else
00410         sup = &tree->root;
00411 
00412     p->right = q->left;
00413     if (p->right) p->right->up = p;
00414     q->left = p;
00415     q->up = p->up;
00416     p->up = q;
00417     *sup = q;
00418 }
00419 
00420 /*           right rotate
00421  *  
00422  *       (P)                (Q)
00423  *      /   \              /   \
00424  *    (Q)    3    ==>     1    (P)  
00425  *   /   \                    /   \
00426  *  1     2                  2     3
00427  *
00428  */
00429 static void right_rotate(cp_sorted_hash *tree, cp_sh_entry *p)
00430 {
00431     cp_sh_entry *q = p->left;
00432     cp_sh_entry **sup;
00433     
00434     if (p->up)
00435         sup = is_left_child(p) ? &(p->up->left) : &(p->up->right);
00436     else
00437         sup = &tree->root;
00438 
00439     p->left = q->right;
00440     if (p->left) p->left->up = p;
00441     q->right = p;
00442     q->up = p->up;
00443     p->up = q;
00444     *sup = q;
00445 }
00446 
00447 
00448 /*
00449  * newly entered node is RED; check balance recursively as required 
00450  */
00451 static void rebalance(cp_sorted_hash *tree, cp_sh_entry *node)
00452 {
00453     cp_sh_entry *up = node->up;
00454     if (up == NULL || up->color == RB_BLACK) return;
00455     if (sibling(up) && sibling(up)->color == RB_RED)
00456     {
00457         up->color = RB_BLACK;
00458         sibling(up)->color = RB_BLACK;
00459         if (up->up->up)
00460         {
00461             up->up->color = RB_RED;
00462             rebalance(tree, up->up);
00463         }
00464     }
00465     else
00466     {
00467         if (is_left_child(node) && is_right_child(up))
00468         {
00469             right_rotate(tree, up);
00470             node = node->right;
00471         }
00472         else if (is_right_child(node) && is_left_child(up))
00473         {
00474             left_rotate(tree, up);
00475             node = node->left;
00476         }
00477 
00478         node->up->color = RB_BLACK;
00479         node->up->up->color = RB_RED;
00480 
00481         if (is_left_child(node)) // && is_left_child(node->up)
00482             right_rotate(tree, node->up->up);
00483         else 
00484             left_rotate(tree, node->up->up);
00485     }
00486 }
00487 
00488 /* update_sh_entry - implement COLLECTION_MODE_COPY, COLLECTION_MODE_DEEP and
00489  * COLLECTION_MODE_MULTIPLE_VALUES when inserting a value for an existing key
00490  */
00491 static void *
00492     update_sh_entry(cp_sorted_hash *tree, cp_sh_entry *node, void *key, void *value)
00493 {
00494     void *new_key = key;
00495     void *new_value = value;
00496 
00497     if (tree->mode & COLLECTION_MODE_COPY)
00498     {
00499         if (tree->key_copy) 
00500         {
00501             new_key = (*tree->key_copy)(key);
00502             if (new_key == NULL) return NULL;
00503         }
00504         if (tree->value_copy)
00505         {
00506             new_value = (*tree->value_copy)(value);
00507             if (new_value == NULL) return NULL;
00508         }
00509     }
00510 
00511     if (tree->mode & COLLECTION_MODE_DEEP)
00512     {
00513         if (tree->key_dtr)
00514             (*tree->key_dtr)(node->key);
00515         if (tree->value_dtr && !(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00516             (*tree->value_dtr)(node->value);
00517     }
00518         
00519     node->key = new_key;
00520     if (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES)
00521     {
00522         cp_vector_add_element(node->value, new_value);
00523         return node->value;
00524     }
00525     else
00526         node->value = new_value;
00527 
00528     return new_value;
00529 }
00530 
00531 /*
00532  * cp_sorted_hash_insert iterates through the tree, finds where the new node 
00533  * fits in, puts it there, then calls rebalance. 
00534  *
00535  * If a mapping for the given key already exists it is replaced unless 
00536  * COLLECTION_MODE_MULTIPLE_VALUES is set, is which case a new mapping is 
00537  * added. By default COLLECTION_MODE_MULTIPLE_VALUES is not set.
00538  */
00539 void *cp_sorted_hash_insert(cp_sorted_hash *tree, void *key, void *value)
00540 {
00541     void *res = NULL;
00542     cp_sh_entry *entry, **curr;
00543     void *ikey, *ivalue;
00544     unsigned long index;
00545     
00546     if (cp_sorted_hash_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00547 
00548     if (tree->mode & COLLECTION_MODE_COPY)
00549     {
00550         ikey = tree->key_copy ? (*tree->key_copy)(key) : key;
00551         ivalue = tree->value_copy ? (*tree->value_copy)(value) : value;
00552     }
00553     else
00554     {
00555         ikey = key;
00556         ivalue = value;
00557     }
00558 
00559     entry = cp_sh_entry_create(ikey, ivalue, tree->mempool);
00560     if (entry == NULL) goto INSERT_DONE;
00561 
00562     entry->code = (*tree->hash)(key);
00563     index = entry->code % tree->size;
00564 
00565     curr = &tree->table[index];
00566     while (*curr) 
00567     {
00568         if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) &&
00569             (*tree->cmp_key)(key, (*curr)->key) == 0)
00570         {
00571             if (tree->mode & COLLECTION_MODE_DEEP)
00572             {
00573                 if (tree->key_dtr) (*tree->key_dtr)((*curr)->key);
00574                 if (tree->value_dtr) (*tree->value_dtr)((*curr)->value);
00575             }
00576             (*curr)->key = ikey;
00577             (*curr)->value = ivalue;
00578             cp_sorted_hash_destroy_entry(tree, entry);
00579             break;
00580         }
00581         curr = &(*curr)->bucket;
00582     }
00583 
00584     if (*curr == NULL) *curr = entry;
00585 
00586     if (tree->root == NULL)
00587     {
00588         tree->root = entry;
00589         res = value;
00590         tree->root->color = RB_BLACK;
00591         tree->items++;
00592     }
00593     else
00594     {
00595         int cmp;
00596         cp_sh_entry *prev = NULL;
00597         curr = &tree->root;
00598 
00599         while (*curr)
00600         {
00601             prev = *curr;
00602             if (tree->cmp_mapping)
00603             {
00604                 cmp = (*tree->cmp_mapping)((cp_mapping *) *curr, 
00605                                            (cp_mapping *) entry);
00606             }
00607             else
00608             {
00609                 cmp = (*tree->cmp_key)((*curr)->key, entry->key);
00610             }
00611 
00612             if (cmp < 0)
00613                 curr = &(*curr)->right;
00614             else if (cmp > 0) 
00615                 curr = &(*curr)->left;
00616             else /* replace */
00617             {
00618                 prev = *curr;
00619                 curr = &(*curr)->multiple;
00620                 while (*curr)
00621                 {
00622                     (*curr)->multiple_prev = prev;
00623                     prev = *curr;
00624                     curr = &(*curr)->multiple;
00625                 }
00626                 *curr = entry;
00627                 entry->multiple_prev = NULL;
00628                 res = entry->value;
00629                 tree->items++;
00630                 break;
00631             }
00632         }
00633 
00634         if (*curr == NULL) /* not replacing, create new node */
00635         {
00636             *curr = entry;
00637             if (*curr == NULL) goto INSERT_DONE;
00638             res = (*curr)->value;
00639             tree->items++;
00640             (*curr)->up = prev;
00641             rebalance(tree, *curr);
00642         }
00643     }
00644 
00645 INSERT_DONE:
00646     cp_sorted_hash_txunlock(tree);
00647     return res;
00648 }
00649 
00650 /* cp_sorted_hash_get - return the value mapped to the given key or NULL if none is
00651  * found. If COLLECTION_MODE_MULTIPLE_VALUES is set the returned value is a
00652  * cp_vector object or NULL if no mapping is found. 
00653  */
00654 void *cp_sorted_hash_get(cp_sorted_hash *tree, void *key)
00655 {
00656     int c;
00657     unsigned long index;
00658     cp_sh_entry *curr;
00659     void *value = NULL;
00660     
00661     if (cp_sorted_hash_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00662 
00663     index = (*tree->hash)(key) % tree->size;
00664     curr = tree->table[index];
00665     //~~ handle mutliple values
00666     while (curr)
00667     {
00668         c = tree->cmp_key(curr->key, key);
00669         if (c == 0) 
00670         {
00671             value = curr->value;
00672             break;
00673         }
00674         curr = curr->bucket;
00675     }
00676 
00677     cp_sorted_hash_txunlock(tree);
00678     return value;;
00679 }
00680     
00681 
00682 /* find the value of the closest key by operator. All of this becuase the tree
00683  * isn't threaded.
00684  */
00685 CPROPS_DLL
00686 void *cp_sorted_hash_find(cp_sorted_hash *tree, cp_mapping *mapping, cp_op op)
00687 {
00688     int cmp;
00689     cp_sh_entry **curr;
00690     cp_sh_entry *prev = NULL;
00691     cp_sh_entry *res = NULL;
00692 
00693     if (tree->root == NULL) return NULL;
00694 
00695     if (cp_sorted_hash_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00696 
00697     curr = &tree->root;
00698     while (*curr)
00699     {
00700         prev = *curr;
00701         if (tree->cmp_mapping)
00702         {
00703             cmp = (*tree->cmp_mapping)((cp_mapping *) *curr, mapping);
00704         }
00705         else
00706         {
00707             cmp = (*tree->cmp_key)((*curr)->key, mapping->key);
00708         }
00709 
00710         if (cmp == 0) break;
00711         if (op == CP_OP_NE)
00712         {
00713             res = *curr;
00714             goto FIND_DONE;
00715         }
00716 
00717         if (cmp < 0)
00718             curr = &(*curr)->right;
00719         else 
00720             curr = &(*curr)->left;
00721     }
00722 
00723     if (*curr)
00724     {
00725         if (op == CP_OP_EQ || op == CP_OP_LE || op == CP_OP_GE)
00726         {
00727             res = *curr;
00728             goto FIND_DONE;
00729         }
00730 
00731         if (op == CP_OP_GT)
00732         {
00733             if ((*curr)->right)
00734             {
00735                 curr = &(*curr)->right;
00736                 while ((*curr)->left) curr = &(*curr)->left;
00737                 res = *curr;
00738             }
00739             else
00740             {
00741                 while ((*curr)->up)
00742                 {
00743                     prev = *curr;
00744                     curr = &(*curr)->up;
00745                     if ((*curr)->left == prev)
00746                     {
00747                         res = *curr;
00748                         break;
00749                     }
00750                 }
00751             }
00752         }
00753         else
00754         {
00755             if ((*curr)->left)
00756             {
00757                 curr = &(*curr)->left;
00758                 while ((*curr)->right) curr = &(*curr)->right;
00759                 res = *curr;
00760             }
00761             else
00762             {
00763                 while ((*curr)->up)
00764                 {
00765                     prev = *curr;
00766                     curr = &(*curr)->up;
00767                     if ((*curr)->right == prev)
00768                     {
00769                         res = *curr;
00770                         break;
00771                     }
00772                 }
00773             }
00774         }
00775 
00776         goto FIND_DONE;
00777     }
00778 
00779     /* *curr is NULL */
00780     if (op == CP_OP_EQ) goto FIND_DONE;
00781 
00782     if (op == CP_OP_LT || op == CP_OP_LE)
00783     {
00784         if (curr == &prev->right) 
00785         {
00786             res = prev;
00787             goto FIND_DONE;
00788         }
00789 
00790         while (prev)
00791         {
00792             if (prev->up && prev->up->right == prev)
00793             {
00794                 res = prev->up;
00795                 break;
00796             }
00797             prev = prev->up;
00798         }
00799     } 
00800     else /* op == CP_OP_GE || op == CP_OP_GT */
00801     {
00802         if (curr == &prev->left)
00803         {
00804             res = prev;
00805             goto FIND_DONE;
00806         }
00807 
00808         while (prev)
00809         {
00810             if (prev->up && prev->up->left == prev)
00811             {
00812                 res = prev->up;
00813                 break;
00814             }
00815             prev = prev->up;
00816         }
00817     }
00818 
00819 FIND_DONE:
00820     cp_sorted_hash_txunlock(tree);
00821     return res->value;
00822 }
00823 
00824 int cp_sorted_hash_contains(cp_sorted_hash *tree, void *key)
00825 {
00826     return (cp_sorted_hash_get(tree, key) != NULL);
00827 }
00828 
00829 /* helper function for deletion */
00830 static void swap_node_content(cp_sh_entry *a, cp_sh_entry *b)
00831 {
00832     void *tmpkey, *tmpval;
00833 
00834     tmpkey = a->key;
00835     a->key = b->key;
00836     b->key = tmpkey;
00837     
00838     tmpval = a->value;
00839     a->value = b->value;
00840     b->value = tmpval;
00841 }
00842 
00843 /*
00844  * helper function for cp_sorted_hash_delete to remove nodes with either a left 
00845  * NULL branch or a right NULL branch
00846  */
00847 static void rb_unlink(cp_sorted_hash *tree, cp_sh_entry *node)
00848 {
00849     if (node->multiple) node->multiple->multiple_prev = node->multiple_prev;
00850     if (node->multiple_prev) node->multiple_prev->multiple = node->multiple;
00851 
00852     if (node->left)
00853     {
00854         node->left->up = node->up;
00855         if (node->up)
00856         {
00857             if (is_left_child(node))
00858                 node->up->left = node->left;
00859             else
00860                 node->up->right = node->left;
00861         }
00862         else
00863             tree->root = node->left;
00864     }
00865     else
00866     {
00867         if (node->right) node->right->up = node->up;
00868         if (node->up)
00869         {
00870             if (is_left_child(node))
00871                 node->up->left = node->right;
00872             else
00873                 node->up->right = node->right;
00874         }
00875         else
00876             tree->root = node->right;
00877     }
00878 }
00879 
00880 /* delete_rebalance - perform rebalancing after a deletion */
00881 static void delete_rebalance(cp_sorted_hash *tree, cp_sh_entry *n)
00882 {
00883     if (n->up)
00884     {
00885         cp_sh_entry *sibl = sibling(n);
00886 
00887         if (sibl->color == RB_RED)
00888         {
00889             n->up->color = RB_RED;
00890             sibl->color = RB_BLACK;
00891             if (is_left_child(n))
00892                 left_rotate(tree, n->up);
00893             else
00894                 right_rotate(tree, n->up);
00895             sibl = sibling(n);
00896         }
00897 
00898         if (n->up->color == RB_BLACK &&
00899             sibl->color == RB_BLACK &&
00900             (sibl->left == NULL || sibl->left->color == RB_BLACK) &&
00901             (sibl->right == NULL || sibl->right->color == RB_BLACK))
00902         {
00903             sibl->color = RB_RED;
00904             delete_rebalance(tree, n->up);
00905         }
00906         else
00907         {
00908             if (n->up->color == RB_RED &&
00909                 sibl->color == RB_BLACK &&
00910                 (sibl->left == NULL || sibl->left->color == RB_BLACK) &&
00911                 (sibl->right == NULL || sibl->right->color == RB_BLACK))
00912             {
00913                 sibl->color = RB_RED;
00914                 n->up->color = RB_BLACK;
00915             }
00916             else
00917             {
00918                 if (is_left_child(n) && 
00919                     sibl->color == RB_BLACK &&
00920                     sibl->left && sibl->left->color == RB_RED && 
00921                     (sibl->right == NULL || sibl->right->color == RB_BLACK))
00922                 {
00923                     sibl->color = RB_RED;
00924                     sibl->left->color = RB_BLACK;
00925                     right_rotate(tree, sibl);
00926                     
00927                     sibl = sibling(n);
00928                 }
00929                 else if (is_right_child(n) &&
00930                     sibl->color == RB_BLACK &&
00931                     sibl->right && sibl->right->color == RB_RED &&
00932                     (sibl->left == NULL || sibl->left->color == RB_BLACK))
00933                 {
00934                     sibl->color = RB_RED;
00935                     sibl->right->color = RB_BLACK;
00936                     left_rotate(tree, sibl);
00937 
00938                     sibl = sibling(n);
00939                 }
00940 
00941                 sibl->color = n->up->color;
00942                 n->up->color = RB_BLACK;
00943                 if (is_left_child(n))
00944                 {
00945                     sibl->right->color = RB_BLACK;
00946                     left_rotate(tree, n->up);
00947                 }
00948                 else
00949                 {
00950                     sibl->left->color = RB_BLACK;
00951                     right_rotate(tree, n->up);
00952                 }
00953             }
00954         }
00955     }
00956 }
00957 
00958 /* cp_sorted_hash_delete_impl - delete one node from a red black tree */
00959 void *cp_sorted_hash_delete_impl(cp_sorted_hash *tree, void *key)
00960 {
00961     void *res = NULL;
00962     cp_sh_entry **table_node;
00963     unsigned long index;
00964     cp_sh_entry *node; 
00965 
00966     //~~ handle multiples
00967     index = (*tree->hash)(key) % tree->size;
00968     table_node = &tree->table[index];
00969     while (*table_node && (*tree->cmp_key)((*table_node)->key, key))
00970         table_node = &(*table_node)->bucket;
00971 
00972     node = *table_node;
00973 
00974     if (node) /* may be null if not found */
00975     {
00976         cp_sh_entry *child; 
00977         res = node->value;
00978         tree->items--;
00979 
00980         if (node->right && node->left)
00981         {
00982             cp_sh_entry *surrogate = node;
00983             node = node->right;
00984             while (node->left) node = node->left;
00985             swap_node_content(node, surrogate);
00986         }
00987         child = node->right ? node->right : node->left;
00988 
00989         /* if the node was red - no rebalancing required */
00990         if (node->color == RB_BLACK)
00991         {
00992             if (child)
00993             {
00994                 /* single red child - paint it black */
00995                 if (child->color == RB_RED)
00996                     child->color = RB_BLACK; /* and the balance is restored */
00997                 else
00998                     delete_rebalance(tree, child);
00999             }
01000             else 
01001                 delete_rebalance(tree, node);
01002         }
01003 
01004         *table_node = (*table_node)->bucket;
01005         rb_unlink(tree, node);
01006         cp_sorted_hash_destroy_entry(tree, node);
01007         
01008     }
01009 
01010     return res;
01011 }
01012 
01013 /* cp_sorted_hash_delete - deletes the value mapped to the given key from the 
01014  * tree and returns the value removed. 
01015  */
01016 void *cp_sorted_hash_delete(cp_sorted_hash *tree, void *key)
01017 {
01018     void *res = NULL;
01019 
01020     if (cp_sorted_hash_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
01021 
01022     res = cp_sorted_hash_delete_impl(tree, key);
01023 
01024     cp_sorted_hash_txunlock(tree);
01025     return res;
01026 }
01027 
01028 static int 
01029     rb_scan_pre_order(cp_sh_entry *node, cp_callback_fn callback, void *prm)
01030 {
01031     int rc;
01032     
01033     if (node) 
01034     {
01035         if ((rc = (*callback)(node, prm))) return rc;
01036         if (node->multiple)
01037         {
01038             cp_sh_entry *multiple = node->multiple;
01039             do
01040             {
01041                 if ((rc = (*callback)(multiple, prm))) return rc;
01042                 multiple = multiple->multiple;
01043             } while (multiple);
01044         }
01045         if ((rc = rb_scan_pre_order(node->left, callback, prm))) return rc;
01046         if ((rc = rb_scan_pre_order(node->right, callback, prm))) return rc;
01047     }
01048 
01049     return 0;
01050 }
01051 
01052 int cp_sorted_hash_callback_preorder(cp_sorted_hash *tree, 
01053                                 cp_callback_fn callback, 
01054                                 void *prm)
01055 {
01056     int rc;
01057 
01058     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01059     rc = rb_scan_pre_order(tree->root, callback, prm);
01060     cp_sorted_hash_txunlock(tree);
01061 
01062     return rc;
01063 }
01064 
01065 static int 
01066     rb_scan_in_order(cp_sh_entry *node, cp_callback_fn callback, void *prm)
01067 {
01068     int rc;
01069     
01070     if (node) 
01071     {
01072         if ((rc = rb_scan_in_order(node->left, callback, prm))) return rc;
01073         if ((rc = (*callback)(node, prm))) return rc;
01074         if (node->multiple)
01075         {
01076             cp_sh_entry *multiple = node->multiple;
01077             do
01078             {
01079                 if ((rc = (*callback)(multiple, prm))) return rc;
01080                 multiple = multiple->multiple;
01081             } while (multiple);
01082         }
01083         if ((rc = rb_scan_in_order(node->right, callback, prm))) return rc;
01084     }
01085 
01086     return 0;
01087 }
01088 
01089 int cp_sorted_hash_callback(cp_sorted_hash *tree, 
01090                             cp_callback_fn callback, 
01091                             void *prm)
01092 {
01093     int rc;
01094 
01095     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01096     rc = rb_scan_in_order(tree->root, callback, prm);
01097     cp_sorted_hash_txunlock(tree);
01098 
01099     return rc;
01100 }
01101 
01102 static int 
01103     rb_scan_post_order(cp_sh_entry *node, cp_callback_fn callback, void *prm)
01104 {
01105     int rc;
01106     
01107     if (node) 
01108     {
01109         if ((rc = rb_scan_post_order(node->left, callback, prm))) return rc;
01110         if ((rc = rb_scan_post_order(node->right, callback, prm))) return rc;
01111         if ((rc = (*callback)(node, prm))) return rc;
01112         if (node->multiple)
01113         {
01114             cp_sh_entry *multiple = node->multiple;
01115             do
01116             {
01117                 if ((rc = (*callback)(multiple, prm))) return rc;
01118                 multiple = multiple->multiple;
01119             } while (multiple);
01120         }
01121     }
01122 
01123     return 0;
01124 }
01125 
01126 int cp_sorted_hash_callback_postorder(cp_sorted_hash *tree, 
01127                                  cp_callback_fn callback, 
01128                                  void *prm)
01129 {
01130     int rc;
01131 
01132     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01133     rc = rb_scan_post_order(tree->root, callback, prm);
01134     cp_sorted_hash_txunlock(tree);
01135 
01136     return rc;
01137 }
01138 
01139 int cp_sorted_hash_count(cp_sorted_hash *tree)
01140 {
01141     return tree->items;
01142 }
01143 
01144 
01145 void cp_sh_entry_print(cp_sh_entry *node, int level)
01146 {
01147     int i;
01148     if (node->right) cp_sh_entry_print(node->right, level + 1);
01149     for (i = 0; i < level; i++) printf("  . ");
01150     printf("(%d) [%s => %s]\n", node->color, (char *) node->key, (char *) node->value);
01151     if (node->left) cp_sh_entry_print(node->left, level + 1);
01152 }
01153 
01154 void cp_sh_entry_multi_print(cp_sh_entry *node, int level)
01155 {
01156     int i;
01157     cp_vector *v = node->value;
01158     if (node->right) cp_sh_entry_multi_print(node->right, level + 1);
01159     
01160     for (i = 0; i < level; i++) printf("  . ");
01161     printf("(%d) [%s => ", node->color, (char *) node->key);
01162 
01163     for (i = 0; i < cp_vector_size(v); i++)
01164         printf("%s; ", (char *) cp_vector_element_at(v, i));
01165 
01166     printf("]\n");
01167 
01168     if (node->left) cp_sh_entry_multi_print(node->left, level + 1);
01169 }
01170 
01171 void cp_sorted_hash_dump(cp_sorted_hash *tree)
01172 {
01173     if (tree->root) 
01174     {
01175         if (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES)
01176             cp_sh_entry_multi_print(tree->root, 0);
01177         else
01178             cp_sh_entry_print(tree->root, 0);
01179     }
01180 }
01181 
01182 /* set tree to use given mempool or allocate a new one if pool is NULL */
01183 int cp_sorted_hash_use_mempool(cp_sorted_hash *tree, cp_mempool *pool)
01184 {
01185     int rc = 0;
01186     
01187     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
01188     
01189     if (pool)
01190     {
01191         if (pool->item_size < sizeof(cp_sh_entry))
01192         {
01193             rc = EINVAL;
01194             goto DONE;
01195         }
01196         if (tree->mempool) 
01197         {
01198             if (tree->items) 
01199             {
01200                 rc = ENOTEMPTY;
01201                 goto DONE;
01202             }
01203             cp_mempool_destroy(tree->mempool);
01204         }
01205         cp_mempool_inc_refcount(pool);
01206         tree->mempool = pool;
01207     }
01208     else
01209     {
01210         tree->mempool = 
01211             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
01212                                         sizeof(cp_sh_entry), 0);
01213         if (tree->mempool == NULL) 
01214         {
01215             rc = ENOMEM;
01216             goto DONE;
01217         }
01218     }
01219 
01220 DONE:
01221     cp_sorted_hash_txunlock(tree);
01222     return rc;
01223 }
01224 
01225 
01226 /* set tree to use a shared memory pool */
01227 int cp_sorted_hash_share_mempool(cp_sorted_hash *tree, cp_shared_mempool *pool)
01228 {
01229     int rc;
01230 
01231     if ((rc = cp_sorted_hash_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
01232 
01233     if (tree->mempool)
01234     {
01235         if (tree->items)
01236         {
01237             rc = ENOTEMPTY;
01238             goto DONE;
01239         }
01240 
01241         cp_mempool_destroy(tree->mempool);
01242     }
01243 
01244     tree->mempool = cp_shared_mempool_register(pool, sizeof(cp_sh_entry));
01245     if (tree->mempool == NULL) 
01246     {
01247         rc = ENOMEM;
01248         goto DONE;
01249     }
01250     
01251 DONE:
01252     cp_sorted_hash_txunlock(tree);
01253     return rc;
01254 }
01255 

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