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
00043
00044
00045
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
00059
00060
00061
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
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
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;
00138 int k = (tree->order - 1) / 2;
00139 int j;
00140 cp_narynode *sibl = cp_narynode_alloc(tree);
00141 sibl->parent = node->parent;
00142 if (index < k)
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)
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
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++)
00217 if (sibl->child[j])
00218 sibl->child[j]->parent = sibl;
00219 narytree_split(tree, node->parent, sibl, swapkey, swapval);
00220 }
00221
00222
00223
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
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
00250
00251 while (index < parent->items &&
00252 (*tree->cmp)(key, parent->key[index]) > 0) index++;
00253
00254 if (parent->items == tree->order - 1)
00255 {
00256 inner_split(tree, parent, index, key, value, node);
00257 return;
00258 }
00259
00260
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
00272
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
00312
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
00324 node = locate_mapping(tree, key, &index, &exists);
00325
00326 if (exists)
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
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
00348 tree->items++;
00349 if (node->items == tree->order - 1)
00350 {
00351 inner_split(tree, node, index, key, value, NULL);
00352 goto INSERT_DONE;
00353 }
00354
00355
00356 if (index < node->items)
00357 narynode_shift(node, index);
00358
00359
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
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
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
00533
00534
00535
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
00555 static void narynode_unify(cp_narytree *tree, cp_narynode *node)
00556 {
00557 cp_narynode *surr;
00558 int i, k;
00559 int idx = 0;
00560
00561 if (node->parent == NULL)
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;
00575
00576
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
00585
00586 if (idx > 0 &&
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 &&
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
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
00628
00629
00630
00631
00632
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
00694
00695
00696
00697
00698
00699
00700
00701
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
00712 curr = find_mapping(tree, key, &i);
00713 if (curr)
00714 {
00715 res = curr->value[i];
00716 if (curr->child[i + 1])
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
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
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
00787
00788
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
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
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
00841 int cp_narytree_set_mode(cp_narytree *tree, int mode)
00842 {
00843 int rc;
00844 int nosync;
00845
00846
00847 if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) &&
00848 (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00849
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
00865
00866
00867
00868 int cp_narytree_unset_mode(cp_narytree *tree, int mode)
00869 {
00870 int rc;
00871 int nosync;
00872
00873
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
00881 if ((mode & COLLECTION_MODE_NOSYNC) && tree->lock == NULL)
00882 {
00883
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
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