nary.c

00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <string.h>
00004 #include <errno.h>
00005 
00006 #include "nary.h"
00007 #include "vector.h"
00008 
00009 static int cp_narytree_txlock(cp_narytree *tree, int type);
00010 static int cp_narytree_txunlock(cp_narytree *tree);
00011 
00012 void cp_narynode_deallocate(cp_narynode *node)
00013 {
00014     if (node)
00015     {
00016         if (node->child) free(node->child);
00017         if (node->value) free(node->value);
00018         if (node->key) free(node->key);
00019         free(node);
00020     }
00021 }
00022 
00023 cp_narynode *cp_narynode_alloc(cp_narytree *tree)
00024 {
00025     cp_narynode *node = calloc(1, sizeof(cp_narynode));
00026     if (node == NULL) goto ALLOC_ERROR;
00027 
00028     node->key = calloc(tree->order - 1, sizeof(void *));
00029     if (node->key == NULL) goto ALLOC_ERROR;
00030     node->value = calloc(tree->order - 1, sizeof(void *));
00031     if (node->value == NULL) goto ALLOC_ERROR;
00032     node->child = calloc(tree->order, sizeof(cp_narynode *));
00033     if (node->child == NULL) goto ALLOC_ERROR;
00034 
00035     return node;
00036     
00037 ALLOC_ERROR:
00038     cp_narynode_deallocate(node);
00039     return NULL;
00040 }
00041 
00042 /* narynode_shift
00043  *
00044  *  +---+---+---+---+---+           +---+---+---+---+---+
00045  *  | A | B | C | D | - |    =>     | A | - | B | C | D |
00046  *  +---+---+---+---+---+           +---+---+---+---+---+
00047  *  
00048  */
00049 static void narynode_shift(cp_narynode *node, int index)
00050 {
00051     int len = node->items - index;
00052     memmove(&node->key[index + 1], &node->key[index], len * sizeof(void *));
00053     memmove(&node->value[index + 1], &node->value[index], len * sizeof(void *));
00054     memmove(&node->child[index + 1], &node->child[index + 0], 
00055             (len + 1) * sizeof(cp_narynode *));
00056 }
00057 
00058 /* narynode_unshift
00059  *
00060  *  +---+---+---+---+---+           +---+---+---+---+---+
00061  *  | A | B | C | D | E |    =>     | A | C | D | E | - |
00062  *  +---+---+---+---+---+           +---+---+---+---+---+
00063  *  
00064  */
00065 static void narynode_unshift(cp_narynode *node, int index)
00066 {
00067     int len = node->items - index - 1;
00068     memmove(&node->key[index], &node->key[index + 1], len * sizeof(void *));
00069     memmove(&node->value[index], &node->value[index + 1], len * sizeof(void *));
00070     memmove(&node->child[index + 1], &node->child[index + 2], 
00071             len * sizeof(cp_narynode *));
00072 }
00073 
00074 static void narytree_split(cp_narytree *tree, 
00075                         cp_narynode *parent,
00076                         cp_narynode *node, 
00077                         void *key, 
00078                         void *value);
00079 
00080 /* On Splitting
00081  * ------------
00082  *
00083  *  if O is the order of the tree (number of children per node), i is the 
00084  *  index where the insertion would occur if the node were not full, find m, 
00085  *  the key to be moved up to the parent node. 
00086  *  
00087  *  let k = (O - 1) / 2 
00088  *
00089  * 
00090  *   O = 2, k = 0             O = 3, k = 1             O = 4, k = 1 
00091  *      +---+                  +---+---+              +---+---+---+ 
00092  *      | 0 |                  | 0 | 1 |              | 0 | 1 | 2 | 
00093  *      +---+                  +---+---+              +---+---+---+ 
00094  *  
00095  *  i = 0   m = 0, i         i = 0   m = 0           i = 0   m = 0, 1  
00096  *  i = 1   m = i, 0         i = 1   m = i           i = 1   m = i, 1 
00097  *                           i = 2   m = 1           i = 2   m = 1, i 
00098  *                                                   i = 3   m = 1, 2 
00099  * 
00100  * 
00101  *       O = 5, k = 2               O = 6, k = 2 
00102  *    +---+---+---+---+         +---+---+---+---+---+ 
00103  *    | 0 | 1 | 2 | 3 |         | 0 | 1 | 2 | 3 | 4 | 
00104  *    +---+---+---+---+         +---+---+---+---+---+ 
00105  * 
00106  *     i = 0   m = 1              i = 0   m = 1, 2 
00107  *     i = 1   m = 1              i = 1   m = 1, 2 
00108  *     i = 2   m = i              i = 2   m = i, 2 
00109  *     i = 3   m = 2              i = 3   m = 2, i 
00110  *     i = 4   m = 2              i = 4   m = 2, 3 
00111  *                                i = 5   m = 2, 3 
00112  *
00113  *
00114  *  It is immediately apparent that for all cases, we may choose
00115  *
00116  *  m = k - 1    i < k     (a)
00117  *      i        i = k     (b)
00118  *      k        i > k     (c)
00119  *
00120  * -------------------------------------------------------------------------
00121  * inner_split copies about half of the existing node's content into a newly
00122  * created node. 
00123  * 
00124  * narytree_split runs after a node has been split. One mapping moves up to the 
00125  * parent node, and a link to the newly created node is added.
00126  */
00127 static void inner_split(cp_narytree *tree, 
00128                         cp_narynode *node, 
00129                         int index, 
00130                         void *key, 
00131                         void *value, 
00132                         cp_narynode *child)
00133     
00134 {
00135     void *swapkey, *swapval;
00136 
00137     int m; /* the index moving up the tree */
00138     int k = (tree->order - 1) / 2; /* minimum fill factor */
00139     int j; /* just a loop counter */
00140     cp_narynode *sibl = cp_narynode_alloc(tree);
00141     sibl->parent = node->parent;
00142     if (index < k) /* case (a) */
00143     {
00144         m = k - 1;
00145         swapkey = node->key[m];
00146         swapval = node->value[m];
00147 
00148         sibl->items = tree->order - k - 1;
00149         memcpy(&sibl->key[0], &node->key[k], 
00150                sibl->items * sizeof(void *));
00151         memcpy(&sibl->value[0], &node->value[k], 
00152                sibl->items * sizeof(void *));
00153         memcpy(&sibl->child[0], &node->child[k], 
00154                (sibl->items + 1) * sizeof(cp_narynode *));
00155         node->items -= sibl->items;
00156         if (index < k - 1)
00157             narynode_shift(node, index);
00158             
00159         node->key[index] = key;
00160         if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00161             node->value[index] = value;
00162         else
00163         {
00164             node->value[index] = cp_vector_create(1);
00165             cp_vector_add_element(node->value[index], value);
00166         }
00167         node->child[index + 1] = child;
00168     }
00169     else if (index == k) /* case (b) */
00170     {
00171         m = index;
00172         swapkey = key;
00173         swapval = value;
00174 
00175         sibl->items = tree->order - k - 1;
00176         memcpy(&sibl->key[0], &node->key[k], 
00177                sibl->items * sizeof(void *));
00178         memcpy(&sibl->value[0], &node->value[k], 
00179                sibl->items * sizeof(void *));
00180         memcpy(&sibl->child[1], &node->child[k + 1], 
00181                sibl->items * sizeof(cp_narynode *));
00182         sibl->child[0] = child;
00183         node->items -= sibl->items;
00184     }
00185     else /* index > k  --  case (c) */
00186     {
00187         int siblindex = index - (k + 1);
00188         m = k;
00189         swapkey = node->key[m];
00190         swapval = node->value[m];
00191 
00192         sibl->items = tree->order - k - 2;
00193 
00194         memcpy(&sibl->key[0], &node->key[k + 1], 
00195                sibl->items * sizeof(void *));
00196         memcpy(&sibl->value[0], &node->value[k + 1],
00197                sibl->items * sizeof(void *));
00198         memcpy(&sibl->child[0], &node->child[k + 1], 
00199                (sibl->items + 1) * sizeof(cp_narynode *));
00200 
00201         if (siblindex < sibl->items)
00202             narynode_shift(sibl, siblindex);
00203 
00204         sibl->key[siblindex] = key;
00205         if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00206             sibl->value[siblindex] = value;
00207         else
00208         {
00209             sibl->value[siblindex] = cp_vector_create(1);
00210             cp_vector_add_element(sibl->value[siblindex], value);
00211         }
00212         sibl->child[siblindex + 1] = child;
00213         sibl->items++;
00214         node->items -= sibl->items;
00215     }
00216     for (j = 0; j <= sibl->items; j++) /* reassign parent */
00217         if (sibl->child[j]) 
00218             sibl->child[j]->parent = sibl;
00219     narytree_split(tree, node->parent, sibl, swapkey, swapval);
00220 }
00221 
00222 /* narytree_split - complete the split operation by adding the given mapping to
00223  * the parent node
00224  */
00225 static void narytree_split(cp_narytree *tree, 
00226                         cp_narynode *parent,
00227                         cp_narynode *node, 
00228                         void *key, 
00229                         void *value)
00230 {
00231     int index = 0;
00232 
00233     /* (1) split at root */
00234     if (parent == NULL)
00235     {
00236         parent = cp_narynode_alloc(tree);
00237         if (parent == NULL) return;
00238         parent->child[0] = tree->root;
00239         tree->root->parent = parent;
00240         parent->child[1] = node;
00241         node->parent = parent;
00242         parent->key[0] = key;
00243         parent->value[0] = value;
00244         parent->items = 1;
00245         tree->root = parent;
00246         return;
00247     }
00248 
00249     //~~ replace with binary search
00250     /* (2) find where new key fits in */
00251     while (index < parent->items && 
00252            (*tree->cmp)(key, parent->key[index]) > 0) index++;
00253 
00254     if (parent->items == tree->order - 1) /* (3) split again */
00255     {
00256         inner_split(tree, parent, index, key, value, node);
00257         return;
00258     }
00259 
00260     /* (4) insert new node */
00261     if (index < parent->items)
00262         narynode_shift(parent, index);
00263     
00264     parent->key[index] = key;
00265     parent->value[index] = value;
00266     parent->child[index + 1] = node;
00267     parent->items++;
00268     node->parent = parent;
00269 }
00270     
00271 /* locate_mapping - run a binary search to find where a new mapping should be 
00272  * put 
00273  */
00274 static cp_narynode *
00275     locate_mapping(cp_narytree *tree, void *key, int *idx, int *exists)
00276 {
00277     cp_narynode *curr = tree->root;
00278     int min, max;
00279     int pos = 0, cmp = 0;
00280 
00281     while (curr)
00282     {
00283         min = -1;
00284         max = curr->items;
00285         while (max > min + 1)
00286         {
00287             pos = (min + max) / 2;
00288             if ((cmp = (*tree->cmp)(key, curr->key[pos])) == 0)
00289             {
00290                 *idx = pos;
00291                 *exists = 1;
00292                 return curr;
00293             }
00294             if (cmp > 0)
00295                 min = pos;
00296             else
00297                 max = pos;
00298         }
00299         if (curr->child[max] == NULL)
00300         {
00301             *idx = max;
00302             *exists = 0;
00303             break;
00304         }
00305         curr = curr->child[max];
00306     }
00307 
00308     return curr;
00309 }
00310 
00311 /* the insert operation is different from the split operation in that ``node''
00312  * is not yet in the tree.
00313  */
00314 void *cp_narynode_insert(cp_narytree *tree, 
00315                          void *key, 
00316                          void *value)
00317 {
00318     int index = 0;
00319     int exists = 0;
00320     cp_narynode *node;
00321     void *res = NULL;
00322 
00323     /* (1) find where new key fits in */
00324     node = locate_mapping(tree, key, &index, &exists);
00325 
00326     if (exists) /* (2) replace */
00327     {
00328         if (tree->mode & COLLECTION_MODE_DEEP)
00329         {
00330             if (tree->key_dtr) (*tree->key_dtr)(node->key[index]);
00331             if (tree->value_dtr && 
00332                 !(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES)) 
00333                 (*tree->value_dtr)(node->value[index]);
00334         }
00335 
00336         /* copying handled by caller (in cp_narytree_insert) */
00337         node->key[index] = key;
00338         if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00339             res = node->value[index] = value;
00340         else
00341             res = cp_vector_add_element(node->value[index], value);
00342 
00343         if (node->items == 0) node->items = 1;
00344         goto INSERT_DONE;
00345     }
00346         
00347     /* inserting in this node */
00348     tree->items++;
00349     if (node->items == tree->order - 1) /* (4) node full, split */
00350     {
00351         inner_split(tree, node, index, key, value, NULL);
00352         goto INSERT_DONE;
00353     }
00354 
00355     /* (3) add to this node */
00356     if (index < node->items) /* shift unless inserting at end */
00357         narynode_shift(node, index);
00358     
00359     /* copying handled by caller (in cp_narytree_insert) */
00360     node->key[index] = key;
00361     if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00362         node->value[index] = value;
00363     else
00364     {
00365         node->value[index] = cp_vector_create(1);
00366         cp_vector_add_element(node->value[index], value);
00367     }
00368     
00369     node->items++;
00370 
00371 INSERT_DONE:
00372     return res;
00373 }
00374 
00375 void cp_narynode_destroy_deep(cp_narynode *node, cp_narytree *tree)
00376 {
00377     int i;
00378     if (node)
00379     {
00380         for (i = 0; i < node->items; i++)
00381         {
00382             if (node->child[i]) cp_narynode_destroy_deep(node->child[i], tree);
00383             if (tree->mode & COLLECTION_MODE_DEEP)
00384             {
00385                 if (tree->key_dtr) (*tree->key_dtr)(node->key[i]);
00386                 if (tree->value_dtr) (*tree->value_dtr)(node->value[i]);
00387             }
00388         }
00389         if (node->child[i]) cp_narynode_destroy_deep(node->child[i], tree);
00390         free(node->key);
00391         free(node->value);
00392         free(node->child);
00393         free(node);
00394     }
00395 }
00396 
00397 
00398 cp_narytree *cp_narytree_create(int order, cp_compare_fn cmp)
00399 {
00400     return cp_narytree_create_by_option(0, order, cmp, NULL, NULL, NULL, NULL);
00401 }
00402 
00403 cp_narytree *cp_narytree_create_by_option(int mode, 
00404                                           int order, 
00405                                           cp_compare_fn cmp, 
00406                                           cp_copy_fn key_copy,
00407                                           cp_destructor_fn key_dtr, 
00408                                           cp_copy_fn value_copy, 
00409                                           cp_destructor_fn value_dtr)
00410 {
00411     cp_narytree *tree = calloc(1, sizeof(cp_narytree));
00412     if (tree == NULL) return NULL;
00413 
00414     tree->mode = mode;
00415 
00416     if (!(mode & COLLECTION_MODE_NOSYNC))
00417     {
00418         tree->lock = (cp_lock *) malloc(sizeof(cp_lock));
00419         if (tree->lock == NULL) goto CREATE_ERR;
00420         if (cp_lock_init(tree->lock, NULL)) goto CREATE_ERR;
00421     }
00422         
00423     tree->order = order;
00424 
00425     tree->cmp = cmp;
00426     tree->key_copy = key_copy;
00427     tree->key_dtr = key_dtr;
00428     tree->value_copy = value_copy;
00429     tree->value_dtr = value_dtr;
00430     
00431     return tree;
00432 
00433 CREATE_ERR:
00434     if (tree->lock) free(tree->lock);
00435     free(tree);
00436     return NULL;
00437 }
00438 
00439 
00440 void cp_narytree_destroy(cp_narytree *tree)
00441 {
00442     if (tree)
00443     {
00444         cp_narynode_destroy_deep(tree->root, tree);
00445         free(tree);
00446     }
00447 }
00448 
00449 void cp_narytree_destroy_custom(cp_narytree *tree, 
00450                                 cp_destructor_fn key_dtr, 
00451                                 cp_destructor_fn value_dtr)
00452 {
00453     tree->key_dtr = key_dtr;
00454     tree->value_dtr = value_dtr;
00455     cp_narytree_destroy(tree);
00456 }
00457 
00458 
00459 void *cp_narytree_insert(cp_narytree *tree, void *key, void *value)
00460 {
00461     void *res;
00462     void *dupkey, *dupval;
00463     
00464     if (cp_narytree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00465 
00466     if (tree->mode & COLLECTION_MODE_COPY)
00467     {
00468         dupkey = tree->key_copy ? (*tree->key_copy)(key) : key;
00469         dupval = tree->value_copy ? (*tree->value_copy)(value) : value;
00470     }
00471     else
00472     {
00473         dupkey = key;
00474         dupval = value;
00475     }
00476 
00477     if (tree->root == NULL)
00478         tree->root = cp_narynode_alloc(tree);
00479 
00480     res = cp_narynode_insert(tree, dupkey, dupval);
00481 
00482     cp_narytree_txunlock(tree);
00483     return res;
00484 }
00485 
00486 static void narynode_unify(cp_narytree *tree, cp_narynode *node);
00487 
00488 /* On Unification
00489  *
00490  * narynode_unify - borrow left
00491  *
00492  *             +---+---+---+---+                      +---+---+---+---+
00493  *             | A | Q | T |   |                      | A | M | T |   |
00494  *             +---+---+---+---+                      +---+---+---+---+
00495  *                /     \               =>               /     \
00496  * +---+---+---+---+  +---+---+---+---+   +---+---+---+---+  +---+---+---+---+
00497  * | E | J | M | - |  | R |   |   |   |   | E | J |   |   |  | Q | R |   |   |
00498  * +---+---+---+---+  +---+---+---+---+   +---+---+---+---+  +---+---+---+---+
00499  *
00500  * narynode_unify - borrow right
00501  *
00502  *             +---+---+---+---+                      +---+---+---+---+
00503  *             | A | J | T |   |                      | A | M | T |   |
00504  *             +---+---+---+---+                      +---+---+---+---+
00505  *                /     \               =>               /     \
00506  * +---+---+---+---+  +---+---+---+---+   +---+---+---+---+  +---+---+---+---+
00507  * | E | - | - | - |  | M | Q | R |   |   | E | J |   |   |  | Q | R |   |   |
00508  * +---+---+---+---+  +---+---+---+---+   +---+---+---+---+  +---+---+---+---+
00509  *
00510  * 
00511  * left_unify 
00512  * 
00513  *               +---+---+---+---+                   +---+---+---+---+
00514  *               | A | J | T |   |                   | A | T |   |   |
00515  *               +---+---+---+---+                   +---+---+---+---+
00516  *                  /     \                   =>        /
00517  *   +---+---+---+---+   +---+---+---+---+            +---+---+---+---+
00518  *   | E | - | - | - |   | M | Q |   |   |            | E | J | M | Q |
00519  *   +---+---+---+---+   +---+---+---+---+            +---+---+---+---+
00520  *
00521  *   if the parent node goes below k = (order - 1) / 2 items, narynode_unify
00522  *   is called on the parent.
00523  */
00524 static void left_unify(cp_narytree *tree, cp_narynode *node, int idx)
00525 {
00526     int i;
00527     cp_narynode *surr = node->parent;
00528     cp_narynode *sibl = surr->child[idx + 1];
00529     
00530     node->key[node->items] = surr->key[idx];
00531     node->value[node->items] = surr->value[idx];
00532 //~~ possible?
00533 //  if (idx + 2 == tree->order)
00534 //      surr->child[idx + 1] = NULL;
00535 //  else
00536     surr->child[idx + 1] = surr->child[idx + 2]; 
00537     narynode_unshift(surr, idx);
00538     surr->items--;
00539     node->items++;
00540     memcpy(&node->key[node->items], &sibl->key[0], 
00541            sibl->items * sizeof(void *));
00542     memcpy(&node->value[node->items], &sibl->value[0], 
00543            sibl->items * sizeof(void *));
00544     for (i = 0; i <= sibl->items; i++) 
00545         if (sibl->child[i]) sibl->child[i]->parent = node;
00546     memcpy(&node->child[node->items], &sibl->child[0], 
00547            (sibl->items + 1) * sizeof(cp_narynode *));
00548     node->items += sibl->items;
00549 
00550     cp_narynode_deallocate(sibl);
00551     narynode_unify(tree, surr);
00552 }
00553 
00554 /* node may have less than k items - if so, unify with other nodes */
00555 static void narynode_unify(cp_narytree *tree, cp_narynode *node)
00556 {
00557     cp_narynode *surr;
00558     int i, k;
00559     int idx = 0; /* prevents gcc warning */
00560 
00561     if (node->parent == NULL) /* root node */
00562     {
00563         if (node->items > 0) return;
00564         if (node->child[0])
00565         {
00566             tree->root = node->child[0];
00567             node->child[0]->parent = NULL;
00568             cp_narynode_deallocate(node);
00569         }
00570         return;
00571     }
00572 
00573     k = (tree->order - 1) / 2;
00574     if (node->items >= k) return; /* narytree condition met - no problem */
00575 
00576     /* try to borrow a mapping from siblings */
00577     surr = node->parent;
00578     for (i = 0; i <= surr->items; i++)
00579         if (surr->child[i] == node)
00580         {
00581             idx = i;
00582             break;
00583         }
00584     /* idx now holds the current node's index in the parent's child[] array */
00585     
00586     if (idx > 0 &&                           /* try borrow from left sibling */
00587         surr->child[idx - 1] && 
00588         surr->child[idx - 1]->items > k) 
00589     {
00590         cp_narynode *sibl = surr->child[idx - 1];
00591         narynode_shift(node, 0);
00592         node->key[0] = surr->key[idx - 1];
00593         node->value[0] = surr->value[idx - 1];
00594         surr->key[idx - 1] = sibl->key[sibl->items - 1];
00595         surr->value[idx - 1] = sibl->value[sibl->items - 1];
00596         node->items++;
00597         node->child[0] = sibl->child[sibl->items];
00598         if (node->child[0]) node->child[0]->parent = node; 
00599         sibl->items--;
00600     }
00601     else if (idx < surr->items &&            /* try borrow from right sibling */
00602              surr->child[idx + 1] && 
00603              surr->child[idx + 1]->items > k) 
00604     {
00605         cp_narynode *sibl = surr->child[idx + 1];
00606         node->key[node->items] = surr->key[idx];
00607         node->value[node->items] = surr->value[idx];
00608         surr->key[idx] = sibl->key[0];
00609         surr->value[idx] = sibl->value[0];
00610         node->items++;
00611         node->child[node->items] = sibl->child[0];
00612         if (node->child[node->items])
00613             node->child[node->items]->parent = node;
00614         sibl->child[0] = sibl->child[1];
00615         narynode_unshift(sibl, 0);
00616         sibl->items--;
00617     }
00618     else                                     /* siblings too small - unify */
00619     {
00620         if (idx > 0 && surr->child[idx - 1])
00621             left_unify(tree, surr->child[idx - 1], idx - 1);
00622         else if (idx < surr->items && surr->child[idx + 1])
00623             left_unify(tree, node, idx);
00624     }
00625 }
00626 
00627 /* find_mapping - performs a binary search on tree nodes to find the mapping 
00628  * for the given key. On average this saves comparisons for tree orders above 
00629  * 8 more or less.
00630  *
00631  * The node containing the mapping is returned and *idx is set to the index
00632  * of the requested mapping. 
00633  */
00634 static cp_narynode *find_mapping(cp_narytree *tree, void *key, int *idx)
00635 {
00636     cp_narynode *curr = tree->root;
00637     int min, max;
00638     int pos = 0, cmp = 0;
00639 
00640     while (curr)
00641     {
00642         min = -1;
00643         max = curr->items;
00644         while (max > min + 1)
00645         {
00646             pos = (min + max) / 2;
00647             if ((cmp = (*tree->cmp)(key, curr->key[pos])) == 0)
00648             {
00649                 *idx = pos;
00650                 return curr;
00651             }
00652             if (cmp > 0)
00653                 min = pos;
00654             else
00655                 max = pos;
00656         }
00657         curr = curr->child[max];
00658     }
00659 
00660     return curr;
00661 }
00662 
00663 void *cp_narytree_get(cp_narytree *tree, void *key)
00664 {
00665     void *res = NULL;
00666     int idx;
00667     cp_narynode *node;
00668 
00669     if (cp_narytree_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00670 
00671     node = find_mapping(tree, key, &idx);
00672     if (node) res = node->value[idx];
00673 
00674     cp_narytree_txunlock(tree);
00675     
00676     return res;
00677 }
00678 
00679 int cp_narytree_contains(cp_narytree *tree, void *key)
00680 {
00681     int x;
00682     int found;
00683 
00684     if (cp_narytree_txlock(tree, COLLECTION_LOCK_READ)) return -1;
00685 
00686     found = (find_mapping(tree, key, &x) != NULL);
00687 
00688     cp_narytree_txunlock(tree);
00689 
00690     return found;
00691 }
00692 
00693 /* cp_narytree_delete
00694  *
00695  * the following cases are handled:
00696  *
00697  * (1) simple case: the node containing the deleted item is a leaf and has 
00698  *     order/2 items or more after the deletion - just remove the mapping.
00699  *
00700  * (2) the node containing the deleted item is not a leaf - replace the item
00701  *     with one from the sub-node
00702  */
00703 void *cp_narytree_delete(cp_narytree *tree, void *key)
00704 {
00705     int i;
00706     cp_narynode *curr;
00707     void *res = NULL;
00708     
00709     if (cp_narytree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00710 
00711     /* find mapping to remove */
00712     curr = find_mapping(tree, key, &i);
00713     if (curr)
00714     {
00715         res = curr->value[i];
00716         if (curr->child[i + 1]) /* not leaf */
00717         {
00718             cp_narynode *leaf = curr->child[i + 1];
00719             while (leaf->child[0])
00720                 leaf = leaf->child[0];
00721             if (tree->mode & COLLECTION_MODE_DEEP)
00722             {
00723                 if (tree->key_dtr) (*tree->key_dtr)(curr->key[i]);
00724                 if (tree->value_dtr) (*tree->value_dtr)(curr->value[i]);
00725             }
00726             curr->key[i] = leaf->key[0];
00727             curr->value[i] = leaf->value[0];
00728             narynode_unshift(leaf, 0);
00729             leaf->items--;
00730             narynode_unify(tree, leaf);
00731         }
00732         else /* leaf-like */
00733         {
00734             if (tree->mode & COLLECTION_MODE_DEEP)
00735             {
00736                 if (tree->key_dtr) (*tree->key_dtr)(curr->key[i]);
00737                 if (tree->value_dtr) (*tree->value_dtr)(curr->value[i]);
00738             }
00739             narynode_unshift(curr, i);
00740             curr->items--;
00741             narynode_unify(tree, curr);
00742         }
00743         tree->items--;
00744     }
00745 
00746     cp_narytree_txunlock(tree);
00747     return res;
00748 }
00749 
00750 static int cp_narytree_lock_internal(cp_narytree *tree, int type)
00751 {
00752     int rc;
00753 
00754     switch (type)
00755     {
00756         case COLLECTION_LOCK_READ:
00757             rc = cp_lock_rdlock(tree->lock);
00758             break;
00759 
00760         case COLLECTION_LOCK_WRITE:
00761             rc = cp_lock_wrlock(tree->lock);
00762             break;
00763 
00764         case COLLECTION_LOCK_NONE:
00765             rc = 0;
00766             break;
00767 
00768         default:
00769             rc = EINVAL;
00770             break;
00771     }
00772 
00773     /* api functions may rely on errno to report locking failure */
00774     if (rc) errno = rc;
00775 
00776     return rc;
00777 }
00778 
00779 static int cp_narytree_unlock_internal(cp_narytree *tree)
00780 {
00781     return cp_lock_unlock(tree->lock);
00782 }
00783 
00784 static int cp_narytree_txlock(cp_narytree *tree, int type)
00785 {
00786     /* clear errno to allow client code to distinguish between a NULL return
00787      * value indicating the tree doesn't contain the requested value and NULL
00788      * on locking failure in tree operations
00789      */
00790     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00791     if (tree->mode & COLLECTION_MODE_IN_TRANSACTION && 
00792         tree->txtype == COLLECTION_LOCK_WRITE)
00793     {
00794         cp_thread self = cp_thread_self();
00795         if (cp_thread_equal(self, tree->txowner)) return 0;
00796     }
00797     errno = 0;
00798     return cp_narytree_lock_internal(tree, type);
00799 }
00800 
00801 static int cp_narytree_txunlock(cp_narytree *tree)
00802 {
00803     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00804     if (tree->mode & COLLECTION_MODE_IN_TRANSACTION && 
00805         tree->txtype == COLLECTION_LOCK_WRITE)
00806     {
00807         cp_thread self = cp_thread_self();
00808         if (cp_thread_equal(self, tree->txowner)) return 0;
00809     }
00810     return cp_narytree_unlock_internal(tree);
00811 }
00812 
00813 /* lock and set the transaction indicators */
00814 int cp_narytree_lock(cp_narytree *tree, int type)
00815 {
00816     int rc;
00817     if ((tree->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00818     if ((rc = cp_narytree_lock_internal(tree, type))) return rc;
00819     tree->txtype = type;
00820     tree->txowner = cp_thread_self();
00821     tree->mode |= COLLECTION_MODE_IN_TRANSACTION;
00822     return 0;
00823 }
00824 
00825 /* unset the transaction indicators and unlock */
00826 int cp_narytree_unlock(cp_narytree *tree)
00827 {
00828     cp_thread self = cp_thread_self();
00829     if (tree->txowner == self)
00830     {
00831         tree->txowner = 0;
00832         tree->txtype = 0;
00833         tree->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00834     }
00835     else if (tree->txtype == COLLECTION_LOCK_WRITE)
00836         return -1;
00837     return cp_narytree_unlock_internal(tree);
00838 }
00839 
00840 /* set mode bits on the tree mode indicator */
00841 int cp_narytree_set_mode(cp_narytree *tree, int mode)
00842 {
00843     int rc;
00844     int nosync; 
00845 
00846     /* can't set NOSYNC in the middle of a transaction */
00847     if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00848         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00849     /* COLLECTION_MODE_MULTIPLE_VALUES must be set at creation time */  
00850     if (mode & COLLECTION_MODE_MULTIPLE_VALUES) return EINVAL;
00851 
00852     if ((rc = cp_narytree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00853     
00854     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00855 
00856     tree->mode |= mode;
00857 
00858     if (!nosync)
00859         cp_narytree_txunlock(tree);
00860 
00861     return 0;
00862 }
00863 
00864 /* unset mode bits on the tree mode indicator. if unsetting 
00865  * COLLECTION_MODE_NOSYNC and the tree was not previously synchronized, the 
00866  * internal synchronization structure is initialized.
00867  */
00868 int cp_narytree_unset_mode(cp_narytree *tree, int mode)
00869 {
00870     int rc;
00871     int nosync;
00872 
00873     /* COLLECTION_MODE_MULTIPLE_VALUES can't be unset */
00874     if (mode & COLLECTION_MODE_MULTIPLE_VALUES) return EINVAL;
00875 
00876     if ((rc = cp_narytree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00877     
00878     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00879 
00880     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00881     if ((mode & COLLECTION_MODE_NOSYNC) && tree->lock == NULL)
00882     {
00883         /* tree can't be locked in this case, no need to unlock on failure */
00884         if ((tree->lock = malloc(sizeof(cp_lock))) == NULL)
00885             return -1;
00886         if (cp_lock_init(tree->lock, NULL))
00887             return -1;
00888     }
00889     
00890     /* unset specified bits */
00891     tree->mode &= tree->mode ^ mode;
00892     if (!nosync)
00893         cp_narytree_txunlock(tree);
00894 
00895     return 0;
00896 }
00897 
00898 int cp_narytree_get_mode(cp_narytree *tree)
00899 {
00900     return tree->mode;
00901 }
00902 
00903 
00904 static int narytree_scan(cp_narynode *node, 
00905                          cp_callback_fn callback, 
00906                          void *prm)
00907 {
00908     int i;
00909     int rc;
00910 
00911     cp_mapping m;
00912     
00913     if (node) 
00914     {
00915         for (i = 0; i < node->items; i++)
00916         {
00917             if ((rc = narytree_scan(node->child[i], callback, prm))) return rc;
00918             m.key = node->key[i];
00919             m.value = node->value[i];
00920             if ((*callback)(&m, prm)) return rc;
00921         }
00922         if ((rc = narytree_scan(node->child[i], callback, prm))) return rc;
00923     }
00924 
00925     return 0;
00926 }
00927 
00928 int cp_narytree_callback(cp_narytree *tree, 
00929                          cp_callback_fn callback, 
00930                          void *prm)
00931 {
00932     int rc;
00933     if ((rc = cp_narytree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
00934     rc = narytree_scan(tree->root, callback, prm);
00935     cp_narytree_txunlock(tree);
00936     return rc;
00937 }
00938 
00939 int cp_narytree_count(cp_narytree *tree)
00940 {
00941     return tree->items;
00942 }
00943 
00944 
00945 void cp_narytree_print_level(cp_narytree *tree, 
00946                           cp_narynode *node, 
00947                           int level, 
00948                           int curr, 
00949                           int *more)
00950 {
00951     int i;
00952     if (node == NULL) return;
00953     
00954     if (curr < level)
00955     {
00956         for (i = 0; i <= node->items; i++)
00957             cp_narytree_print_level(tree, node->child[i], level, curr + 1, more);
00958     }
00959     else
00960     {
00961         printf("(%d) ", node->items);
00962         printf("[%lX;%lX] ", (long) node, (long) node->parent);
00963         for (i = 0; i < tree->order - 1; i++)
00964         {
00965             if (i <= node->items && node->child[i]) printf("<%lX>", (long) node->child[i]);
00966             printf("|%s|", (char *) (i < node->items && node->key[i] ? node->key[i] : "-"));
00967             if (node->child[i]) *more = 1;
00968         }
00969         if (node->child[i]) *more = 1;
00970         if (i == node->items && node->child[i]) printf("<%lX>   ", (long) node->child[i]);
00971     }
00972 }
00973 
00974 void cp_narytree_dump(cp_narytree *tree)
00975 {
00976     int more;
00977     int level = 0;
00978     do
00979     {
00980         more = 0;
00981         cp_narytree_print_level(tree, tree->root, level, 0, &more);
00982         printf("\n");
00983         level++;
00984     } while (more);
00985 }
00986 

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