1/* DBKBTreeNode.m 2 * 3 * Copyright (C) 2005-2012 Free Software Foundation, Inc. 4 * 5 * Author: Enrico Sersale <enrico@imago.ro> 6 * Date: June 2005 7 * 8 * This file is part of the GNUstep GWorkspace application 9 * 10 * This program is free software; you can redistribute it and/or modify 11 * it under the terms of the GNU General Public License as published by 12 * the Free Software Foundation; either version 2 of the License, or 13 * (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111 USA. 23 */ 24 25#import "DBKBTreeNode.h" 26#import "DBKBTree.h" 27 28@implementation DBKBTreeNode 29 30- (void)dealloc 31{ 32 RELEASE (offset); 33 RELEASE (keys); 34 RELEASE (subnodes); 35 36 [super dealloc]; 37} 38 39- (id)initInTree:(DBKBTree *)atree 40 withParent:(DBKBTreeNode *)pnode 41 atOffset:(NSNumber *)ofst 42{ 43 self = [super init]; 44 45 if (self) { 46 tree = atree; 47 parent = pnode; 48 ASSIGN (offset, ofst); 49 50 order = [tree order]; 51 minkeys = order - 1; 52 maxkeys = order * 2 - 1; 53 54 keys = [NSMutableArray new]; 55 subnodes = [NSMutableArray new]; 56 57 loaded = NO; 58 59 ulen = sizeof(unsigned); 60 llen = sizeof(unsigned long); 61 } 62 63 return self; 64} 65 66- (NSUInteger)hash 67{ 68 return [offset hash]; 69} 70 71- (BOOL)isEqual:(id)other 72{ 73 if (other == self) { 74 return YES; 75 } 76 if ([other isKindOfClass: [DBKBTreeNode class]]) { 77 return [offset isEqual: [other offset]]; 78 } 79 return NO; 80} 81 82- (BOOL)isLoaded 83{ 84 return loaded; 85} 86 87- (void)setLoaded 88{ 89 loaded = YES; 90} 91 92- (void)loadNodeData 93{ 94 [self setNodeData: [tree dataForNode: self]]; 95} 96 97- (BOOL)unload 98{ 99 [keys removeAllObjects]; 100 [subnodes removeAllObjects]; 101 loaded = NO; 102 return YES; 103} 104 105- (void)setNodeData:(NSData *)ndata 106{ 107 CREATE_AUTORELEASE_POOL (pool); 108 NSRange range; 109 unsigned datalen; 110 unsigned offscount; 111 NSArray *array; 112 NSUInteger i; 113 114 array = [tree keysFromData: ndata withLength: &datalen]; 115 [keys addObjectsFromArray: array]; 116 117 range = NSMakeRange(datalen, ulen); 118 [ndata getBytes: &offscount range: range]; 119 120 range.location += ulen; 121 range.length = llen; 122 123 for (i = 0; i < offscount; i++) { 124 unsigned long offs; 125 NSNumber *offsnum; 126 DBKBTreeNode *node; 127 128 [ndata getBytes: &offs range: range]; 129 offsnum = [NSNumber numberWithUnsignedLong: offs]; 130 131 node = [[DBKBTreeNode alloc] initInTree: tree 132 withParent: self 133 atOffset: offsnum]; 134 135 [subnodes addObject: node]; 136 RELEASE (node); 137 range.location += llen; 138 } 139 140 loaded = YES; 141 142 RELEASE (pool); 143} 144 145- (NSData *)nodeData 146{ 147 NSMutableData *nodeData = [NSMutableData dataWithCapacity: 1]; 148 NSUInteger subcount; 149 NSUInteger i; 150 151 [nodeData appendData: [tree dataFromKeys: keys]]; 152 153 subcount = [subnodes count]; 154 [nodeData appendData: [NSData dataWithBytes: &subcount length: ulen]]; 155 156 for (i = 0; i < subcount; i++) { 157 NSNumber *offsnum = [[subnodes objectAtIndex: i] offset]; 158 unsigned long offs = [offsnum unsignedLongValue]; 159 160 [nodeData appendData: [NSData dataWithBytes: &offs length: llen]]; 161 } 162 163 return nodeData; 164} 165 166- (void)save 167{ 168 [tree addUnsavedNode: self]; 169} 170 171- (NSNumber *)offset 172{ 173 return offset; 174} 175 176- (void)setOffset:(NSNumber *)ofst 177{ 178 ASSIGN (offset, ofst); 179} 180 181- (DBKBTreeNode *)parent 182{ 183 return parent; 184} 185 186- (void)setParent:(DBKBTreeNode *)anode 187{ 188 parent = anode; 189} 190 191- (void)insertKey:(id)key 192 atIndex:(NSUInteger)index 193{ 194 [keys insertObject: key atIndex: index]; 195 [self save]; 196} 197 198- (BOOL)insertKey:(id)key 199{ 200 CREATE_AUTORELEASE_POOL(arp); 201 unsigned count = [keys count]; 202 int ins = 0; 203 204 if (count) { 205 NSUInteger first = 0; 206 NSUInteger last = count; 207 NSUInteger pos = 0; 208 id k; 209 NSComparisonResult result; 210 211 while (1) { 212 if (first == last) { 213 ins = first; 214 break; 215 } 216 217 pos = (first + last) / 2; 218 k = [keys objectAtIndex: pos]; 219 result = [tree compareNodeKey: k withKey: key]; 220 221 if (result == NSOrderedSame) { 222 /* the key exists */ 223 RELEASE (arp); 224 return NO; 225 226 } else if (result == NSOrderedAscending) { 227 first = pos + 1; 228 } else { 229 last = pos; 230 } 231 } 232 } 233 234 [keys insertObject: key atIndex: ins]; 235 [self save]; 236 237 RELEASE (arp); 238 239 return YES; 240} 241 242- (NSUInteger)indexForKey:(id)key 243 existing:(BOOL *)exists 244{ 245 CREATE_AUTORELEASE_POOL(arp); 246 NSUInteger count = [keys count]; 247 NSUInteger ins = 0; 248 249 if (count) { 250 NSUInteger first = 0; 251 NSUInteger last = count; 252 NSUInteger pos = 0; 253 id k; 254 NSComparisonResult result; 255 256 while (1) { 257 if (first == last) { 258 ins = first; 259 break; 260 } 261 262 pos = (first + last) / 2; 263 k = [keys objectAtIndex: pos]; 264 result = [tree compareNodeKey: k withKey: key]; 265 266 if (result == NSOrderedSame) { 267 *exists = YES; 268 RELEASE (arp); 269 return pos; 270 271 } else if (result == NSOrderedAscending) { 272 first = pos + 1; 273 } else { 274 last = pos; 275 } 276 } 277 } 278 279 *exists = NO; 280 RELEASE (arp); 281 282 return ins; 283} 284 285- (NSUInteger)indexOfKey:(id)key 286{ 287 return [keys indexOfObject: key]; 288} 289 290- (id)keyAtIndex:(NSUInteger)index 291{ 292 return [keys objectAtIndex: index]; 293} 294 295- (void)setKeys:(NSArray *)newkeys 296{ 297 [keys removeAllObjects]; 298 [keys addObjectsFromArray: newkeys]; 299 [self save]; 300} 301 302- (void)addKey:(id)key 303{ 304 [keys addObject: key]; 305 [self save]; 306} 307 308- (void)removeKey:(id)key 309{ 310 [keys removeObject: key]; 311 [self save]; 312} 313 314- (void)removeKeyAtIndex:(NSUInteger)index 315{ 316 [keys removeObjectAtIndex: index]; 317 [self save]; 318} 319 320- (void)replaceKeyAtIndex:(NSUInteger)index 321 withKey:(id)key 322{ 323 [keys replaceObjectAtIndex: index withObject: key]; 324 [self save]; 325} 326 327- (void)replaceKey:(id)key 328 withKey:(id)newkey 329{ 330 NSUInteger index = [self indexOfKey: key]; 331 332 if (index != NSNotFound) { 333 [keys replaceObjectAtIndex: index withObject: newkey]; 334 [self save]; 335 } 336} 337 338- (NSArray *)keys 339{ 340 return keys; 341} 342 343- (id)minKeyInSubnode:(DBKBTreeNode **)node 344{ 345 if (loaded == NO) { 346 [self loadNodeData]; 347 } 348 349 *node = self; 350 351 while ([*node isLeaf] == NO) { 352 *node = [[*node subnodes] objectAtIndex: 0]; 353 if ([*node isLoaded] == NO) { 354 [*node loadNodeData]; 355 } 356 } 357 358 if ([*node isLoaded] == NO) { 359 [*node loadNodeData]; 360 } 361 362 return [[*node keys] objectAtIndex: 0]; 363} 364 365- (id)maxKeyInSubnode:(DBKBTreeNode **)node 366{ 367 NSArray *nodes; 368 NSArray *ndkeys; 369 370 if (loaded == NO) { 371 [self loadNodeData]; 372 } 373 374 *node = self; 375 nodes = [*node subnodes]; 376 377 while ([*node isLeaf] == NO) { 378 *node = [nodes objectAtIndex: ([nodes count] -1)]; 379 if ([*node isLoaded] == NO) { 380 [*node loadNodeData]; 381 } 382 nodes = [*node subnodes]; 383 } 384 385 if ([*node isLoaded] == NO) { 386 [*node loadNodeData]; 387 } 388 389 ndkeys = [*node keys]; 390 391 return [ndkeys objectAtIndex: ([ndkeys count] -1)]; 392} 393 394- (id)successorKeyInNode:(DBKBTreeNode **)node 395 forKey:(id)key 396{ 397 NSUInteger index; 398 399 if (loaded == NO) { 400 [self loadNodeData]; 401 } 402 403 index = [self indexOfKey: key]; 404 405 if (index != NSNotFound) { 406 return [self successorKeyInNode: node forKeyAtIndex: index]; 407 } 408 409 return nil; 410} 411 412- (id)successorKeyInNode:(DBKBTreeNode **)node 413 forKeyAtIndex:(NSUInteger)index 414{ 415 DBKBTreeNode *nextNode = nil; 416 DBKBTreeNode *nextParent = nil; 417 id key = nil; 418 NSUInteger pos; 419 420 if (loaded == NO) { 421 [self loadNodeData]; 422 } 423 424 if ([self isLeaf] == NO) { 425 if ([subnodes count] > index) { 426 nextNode = [subnodes objectAtIndex: (index + 1)]; 427 428 if ([nextNode isLoaded] == NO) { 429 [nextNode loadNodeData]; 430 } 431 432 key = [nextNode minKeyInSubnode: &nextNode]; 433 } 434 435 } else { 436 if (index < ([keys count] - 1)) { 437 nextNode = self; 438 key = [keys objectAtIndex: (index + 1)]; 439 440 } else { 441 if ([parent isLastSubnode: self]) { 442 nextParent = parent; 443 nextNode = self; 444 445 while (nextParent) { 446 if ([nextParent isLastSubnode: nextNode]) { 447 nextNode = nextParent; 448 nextParent = [nextNode parent]; 449 } else { 450 pos = [nextParent indexOfSubnode: nextNode]; 451 nextNode = nextParent; 452 key = [[nextNode keys] objectAtIndex: pos]; 453 break; 454 } 455 } 456 457 } else { 458 nextNode = parent; 459 pos = [nextNode indexOfSubnode: self]; 460 key = [[nextNode keys] objectAtIndex: pos]; 461 } 462 } 463 } 464 465 *node = nextNode; 466 467 return key; 468} 469 470- (id)predecessorKeyInNode:(DBKBTreeNode **)node 471 forKey:(id)key 472{ 473 NSUInteger index; 474 475 if (loaded == NO) { 476 [self loadNodeData]; 477 } 478 479 index = [self indexOfKey: key]; 480 481 if (index != NSNotFound) { 482 return [self predecessorKeyInNode: node forKeyAtIndex: index]; 483 } 484 485 return nil; 486} 487 488- (id)predecessorKeyInNode:(DBKBTreeNode **)node 489 forKeyAtIndex:(NSUInteger)index 490{ 491 DBKBTreeNode *nextNode = nil; 492 DBKBTreeNode *nextParent = nil; 493 id key = nil; 494 NSUInteger pos; 495 496 if (loaded == NO) { 497 [self loadNodeData]; 498 } 499 500 if ([self isLeaf] == NO) { 501 if (index < [subnodes count]) { 502 nextNode = [subnodes objectAtIndex: index]; 503 504 if ([nextNode isLoaded] == NO) { 505 [nextNode loadNodeData]; 506 } 507 508 key = [nextNode maxKeyInSubnode: &nextNode]; 509 } 510 511 } else { 512 if (index > 0) { 513 nextNode = self; 514 key = [keys objectAtIndex: (index - 1)]; 515 516 } else { 517 if ([parent isFirstSubnode: self]) { 518 nextParent = parent; 519 nextNode = self; 520 521 while (nextParent) { 522 if ([nextParent isFirstSubnode: nextNode]) { 523 nextNode = nextParent; 524 nextParent = [nextNode parent]; 525 } else { 526 pos = [nextParent indexOfSubnode: nextNode]; 527 nextNode = nextParent; 528 key = [[nextNode keys] objectAtIndex: (pos - 1)]; 529 break; 530 } 531 } 532 533 } else { 534 nextNode = parent; 535 pos = [nextNode indexOfSubnode: self]; 536 key = [[nextNode keys] objectAtIndex: (pos - 1)]; 537 } 538 } 539 } 540 541 *node = nextNode; 542 543 return key; 544} 545 546- (void)insertSubnode:(DBKBTreeNode *)node 547 atIndex:(NSUInteger)index 548{ 549 [node setParent: self]; 550 [subnodes insertObject: node atIndex: index]; 551 [self save]; 552} 553 554- (void)addSubnode:(DBKBTreeNode *)node 555{ 556 [node setParent: self]; 557 [subnodes addObject: node]; 558 [self save]; 559} 560 561- (void)removeSubnode:(DBKBTreeNode *)node 562{ 563 [subnodes removeObject: node]; 564 [self save]; 565} 566 567- (void)removeSubnodeAtIndex:(NSUInteger)index 568{ 569 [subnodes removeObjectAtIndex: index]; 570 [self save]; 571} 572 573- (void)replaceSubnodeAtIndex:(NSUInteger)index 574 withNode:(DBKBTreeNode *)node 575{ 576 [node setParent: self]; 577 [subnodes replaceObjectAtIndex: index withObject: node]; 578 [self save]; 579} 580 581- (NSUInteger)indexOfSubnode:(DBKBTreeNode *)node 582{ 583 return [subnodes indexOfObject: node]; 584} 585 586- (DBKBTreeNode *)subnodeAtIndex:(NSUInteger)index 587{ 588 return [subnodes objectAtIndex: index]; 589} 590 591- (BOOL)isFirstSubnode:(DBKBTreeNode *)node 592{ 593 NSUInteger index = [self indexOfSubnode: node]; 594 return ((index != NSNotFound) && (index == 0)); 595} 596 597- (BOOL)isLastSubnode:(DBKBTreeNode *)node 598{ 599 NSUInteger index = [self indexOfSubnode: node]; 600 return ((index != NSNotFound) && (index == ([subnodes count] - 1))); 601} 602 603- (void)setSubnodes:(NSArray *)nodes 604{ 605 NSUInteger i; 606 607 [subnodes removeAllObjects]; 608 609 for (i = 0; i < [nodes count]; i++) { 610 [self addSubnode: [nodes objectAtIndex: i]]; 611 } 612 613 [self save]; 614} 615 616- (NSArray *)subnodes 617{ 618 return subnodes; 619} 620 621- (DBKBTreeNode *)leftSibling 622{ 623 if (parent) { 624 NSUInteger index = [parent indexOfSubnode: self]; 625 626 if (index > 0) { 627 return [[parent subnodes] objectAtIndex: (index - 1)]; 628 } 629 } 630 631 return nil; 632} 633 634- (DBKBTreeNode *)rightSibling 635{ 636 if (parent) { 637 NSArray *pnodes = [parent subnodes]; 638 NSUInteger index = [parent indexOfSubnode: self]; 639 640 if (index < ([pnodes count] - 1)) { 641 return [pnodes objectAtIndex: (index + 1)]; 642 } 643 } 644 645 return nil; 646} 647 648- (void)splitSubnodeAtIndex:(NSUInteger)index 649{ 650 DBKBTreeNode *subnode; 651 DBKBTreeNode *newnode; 652 NSArray *subkeys; 653 NSArray *akeys; 654 id key; 655 NSArray *bkeys; 656 CREATE_AUTORELEASE_POOL(arp); 657 658 subnode = [subnodes objectAtIndex: index]; 659 660 if ([subnode isLoaded] == NO) { 661 [subnode loadNodeData]; 662 } 663 664 newnode = [[DBKBTreeNode alloc] initInTree: tree 665 withParent: self 666 atOffset: [tree offsetForNewNode]]; 667 [newnode setLoaded]; 668 669 subkeys = [subnode keys]; 670 akeys = [subkeys subarrayWithRange: NSMakeRange(0, order - 1)]; 671 key = [subkeys objectAtIndex: order - 1]; 672 bkeys = [subkeys subarrayWithRange: NSMakeRange(order, order - 1)]; 673 674 RETAIN (key); 675 [subnode setKeys: akeys]; 676 [newnode setKeys: bkeys]; 677 678 if ([subnode isLeaf] == NO) { 679 NSArray *nodes = [subnode subnodes]; 680 NSArray *anodes = [nodes subarrayWithRange: NSMakeRange(0, order)]; 681 NSArray *bnodes = [nodes subarrayWithRange: NSMakeRange(order, order)]; 682 683 [subnode setSubnodes: anodes]; 684 [newnode setSubnodes: bnodes]; 685 } 686 687 [self insertSubnode: newnode atIndex: index + 1]; 688 [self insertKey: key atIndex: index]; 689 690 [subnode save]; 691 [newnode save]; 692 [self save]; 693 694 RELEASE (key); 695 RELEASE (newnode); 696 RELEASE (arp); 697} 698 699- (BOOL)mergeWithBestSibling 700{ 701 if (parent) { 702 CREATE_AUTORELEASE_POOL(arp); 703 DBKBTreeNode *lftnd; 704 unsigned lcount = 0; 705 DBKBTreeNode *rgtnd; 706 unsigned rcount = 0; 707 DBKBTreeNode *node; 708 NSArray *ndkeys; 709 NSUInteger index; 710 NSUInteger i; 711 712 lftnd = [self leftSibling]; 713 714 if (lftnd) { 715 if ([lftnd isLoaded] == NO) { 716 [lftnd loadNodeData]; 717 } 718 lcount = [[lftnd keys] count]; 719 } 720 721 rgtnd = [self rightSibling]; 722 723 if (rgtnd) { 724 if ([rgtnd isLoaded] == NO) { 725 [rgtnd loadNodeData]; 726 } 727 rcount = [[rgtnd keys] count]; 728 } 729 730 node = (lcount > rcount) ? lftnd : rgtnd; 731 ndkeys = [node keys]; 732 733 index = [parent indexOfSubnode: self]; 734 735 if (node == rgtnd) { 736 [self addKey: [[parent keys] objectAtIndex: index]]; 737 } else { 738 index--; 739 [self insertKey: [[parent keys] objectAtIndex: index] atIndex: 0]; 740 } 741 742 if (node == rgtnd) 743 { 744 for (i = 0; i < [ndkeys count]; i++) 745 [self addKey: [ndkeys objectAtIndex: i]]; 746 } 747 else 748 { 749 for (i = [ndkeys count]; i > 0; i--) 750 [self insertKey: [ndkeys objectAtIndex: i-1] atIndex: 0]; 751 } 752 753 if ([self isLeaf] == NO) 754 { 755 NSArray *ndnodes = [node subnodes]; 756 757 if (node == rgtnd) 758 { 759 for (i = 0; i < [ndnodes count]; i++) 760 [self addSubnode: [ndnodes objectAtIndex: i]]; 761 } 762 else 763 { 764 for (i = [ndnodes count]; i > 0; i--) 765 [self insertSubnode: [ndnodes objectAtIndex: i-1] atIndex: 0]; 766 } 767 } 768 769 [parent removeKeyAtIndex: index]; 770 [tree nodeWillFreeOffset: [node offset]]; 771 [parent removeSubnode: node]; 772 773 [parent save]; 774 [self save]; 775 776 RELEASE (arp); 777 778 return YES; 779 } 780 781 return NO; 782} 783 784- (void)borrowFromRightSibling:(DBKBTreeNode *)sibling 785{ 786 CREATE_AUTORELEASE_POOL(arp); 787 NSUInteger index = [parent indexOfSubnode: self]; 788 789 if ([sibling isLoaded] == NO) { 790 [sibling loadNodeData]; 791 } 792 793 [self addKey: [[parent keys] objectAtIndex: index]]; 794 795 if ([sibling isLeaf] == NO) { 796 [self addSubnode: [[sibling subnodes] objectAtIndex: 0]]; 797 [sibling removeSubnodeAtIndex: 0]; 798 } 799 800 [parent replaceKeyAtIndex: index 801 withKey: [[sibling keys] objectAtIndex: 0]]; 802 803 [sibling removeKeyAtIndex: 0]; 804 805 [self save]; 806 [sibling save]; 807 [parent save]; 808 809 RELEASE (arp); 810} 811 812- (void)borrowFromLeftSibling:(DBKBTreeNode *)sibling 813{ 814 CREATE_AUTORELEASE_POOL(arp); 815 NSUInteger index; 816 NSArray *lftkeys; 817 unsigned lftkcount; 818 819 if ([sibling isLoaded] == NO) { 820 [sibling loadNodeData]; 821 } 822 823 index = [parent indexOfSubnode: sibling]; 824 lftkeys = [sibling keys]; 825 lftkcount = [lftkeys count]; 826 827 [self insertKey: [[parent keys] objectAtIndex: index] atIndex: 0]; 828 829 if ([sibling isLeaf] == NO) { 830 NSArray *lftnodes = [sibling subnodes]; 831 unsigned lftncount = [lftnodes count]; 832 833 [self insertSubnode: [lftnodes objectAtIndex: (lftncount - 1)] 834 atIndex: 0]; 835 [sibling removeSubnodeAtIndex: (lftncount - 1)]; 836 } 837 838 [parent replaceKeyAtIndex: index 839 withKey: [lftkeys objectAtIndex: (lftkcount - 1)]]; 840 841 [sibling removeKeyAtIndex: (lftkcount - 1)]; 842 843 [self save]; 844 [sibling save]; 845 [parent save]; 846 847 RELEASE (arp); 848} 849 850- (void)setRoot 851{ 852 parent = nil; 853} 854 855- (BOOL)isRoot 856{ 857 return (parent == nil); 858} 859 860- (BOOL)isLeaf 861{ 862 return ([subnodes count] == 0); 863} 864 865@end 866 867