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