1 /**
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.kahadb.index;
18
19 import java.io.DataInput;
20 import java.io.DataOutput;
21 import java.io.IOException;
22 import java.io.PrintWriter;
23 import java.util.Arrays;
24 import java.util.Iterator;
25 import java.util.Map;
26 import java.util.NoSuchElementException;
27 import java.util.Map.Entry;
28
29 import org.apache.kahadb.index.BTreeIndex.Prefixer;
30 import org.apache.kahadb.page.Page;
31 import org.apache.kahadb.page.Transaction;
32 import org.apache.kahadb.util.VariableMarshaller;
33
34
35 /**
36 * The BTreeNode class represents a node in the BTree object graph. It is stored in
37 * one Page of a PageFile.
38 */
39 public final class BTreeNode<Key,Value> {
40
41 // The index that this node is part of.
42 private final BTreeIndex<Key,Value> index;
43 // The parent node or null if this is the root node of the BTree
44 private BTreeNode<Key,Value> parent;
45 // The page associated with this node
46 private Page<BTreeNode<Key,Value>> page;
47
48 // Order list of keys in the node
49 private Key[] keys;
50 // Values associated with the Keys. Null if this is a branch node.
51 private Value[] values;
52 // nodeId pointers to children BTreeNodes. Null if this is a leaf node.
53 private long[] children;
54 // The next leaf node after this one. Used for fast iteration of the entries.
55 private long next = -1;
56
57 private final class KeyValueEntry implements Map.Entry<Key, Value> {
58 private final Key key;
59 private final Value value;
60
61 public KeyValueEntry(Key key, Value value) {
62 this.key = key;
63 this.value = value;
64 }
65
66 public Key getKey() {
67 return key;
68 }
69
70 public Value getValue() {
71 return value;
72 }
73
74 public Value setValue(Value value) {
75 throw new UnsupportedOperationException();
76 }
77
78 }
79
80 private final class BTreeIterator implements Iterator<Map.Entry<Key, Value>> {
81
82 private final Transaction tx;
83 BTreeNode<Key,Value> current;
84 int nextIndex;
85 Map.Entry<Key,Value> nextEntry;
86
87 private BTreeIterator(Transaction tx, BTreeNode<Key,Value> current, int nextIndex) {
88 this.tx = tx;
89 this.current = current;
90 this.nextIndex=nextIndex;
91 }
92
93 synchronized private void findNextPage() {
94 if( nextEntry!=null ) {
95 return;
96 }
97
98 try {
99 while( current!=null ) {
100 if( nextIndex >= current.keys.length ) {
101 // we need to roll to the next leaf..
102 if( current.next >= 0 ) {
103 current = index.loadNode(tx, current.next, null);
104 nextIndex=0;
105 } else {
106 break;
107 }
108 } else {
109 nextEntry = new KeyValueEntry(current.keys[nextIndex], current.values[nextIndex]);
110 nextIndex++;
111 break;
112 }
113
114 }
115 } catch (IOException e) {
116 }
117 }
118
119 public boolean hasNext() {
120 findNextPage();
121 return nextEntry !=null;
122 }
123
124 public Entry<Key, Value> next() {
125 findNextPage();
126 if( nextEntry !=null ) {
127 Entry<Key, Value> lastEntry = nextEntry;
128 nextEntry=null;
129 return lastEntry;
130 } else {
131 throw new NoSuchElementException();
132 }
133 }
134
135 public void remove() {
136 throw new UnsupportedOperationException();
137 }
138 }
139
140 /**
141 * The Marshaller is used to store and load the data in the BTreeNode into a Page.
142 *
143 * @param <Key>
144 * @param <Value>
145 */
146 static public class Marshaller<Key,Value> extends VariableMarshaller<BTreeNode<Key,Value>> {
147 private final BTreeIndex<Key,Value> index;
148
149 public Marshaller(BTreeIndex<Key,Value> index) {
150 this.index = index;
151 }
152
153 public void writePayload(BTreeNode<Key,Value> node, DataOutput os) throws IOException {
154 // Write the keys
155 short count = (short)node.keys.length; // cast may truncate value...
156 if( count != node.keys.length ) {
157 throw new IOException("Too many keys");
158 }
159
160 os.writeShort(count);
161 for (int i = 0; i < node.keys.length; i++) {
162 index.getKeyMarshaller().writePayload(node.keys[i], os);
163 }
164
165 if( node.isBranch() ) {
166 // If this is a branch...
167 os.writeBoolean(true);
168 for (int i = 0; i < count+1; i++) {
169 os.writeLong(node.children[i]);
170 }
171
172 } else {
173 // If this is a leaf
174 os.writeBoolean(false);
175 for (int i = 0; i < count; i++) {
176 index.getValueMarshaller().writePayload(node.values[i], os);
177 }
178 os.writeLong(node.next);
179 }
180 }
181
182 @SuppressWarnings("unchecked")
183 public BTreeNode<Key,Value> readPayload(DataInput is) throws IOException {
184 BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(index);
185 int count = is.readShort();
186
187 node.keys = (Key[])new Object[count];
188 for (int i = 0; i < count; i++) {
189 node.keys[i] = index.getKeyMarshaller().readPayload(is);
190 }
191
192 if( is.readBoolean() ) {
193 node.children = new long[count+1];
194 for (int i = 0; i < count+1; i++) {
195 node.children[i] = is.readLong();
196 }
197 } else {
198 node.values = (Value[])new Object[count];
199 for (int i = 0; i < count; i++) {
200 node.values[i] = index.getValueMarshaller().readPayload(is);
201 }
202 node.next = is.readLong();
203 }
204 return node;
205 }
206 }
207
208 public BTreeNode(BTreeIndex<Key,Value> index) {
209 this.index = index;
210 }
211
212 public void setEmpty() {
213 setLeafData(createKeyArray(0), createValueArray(0));
214 }
215
216
217 /**
218 * Internal (to the BTreeNode) method. Because this method is called only by
219 * BTreeNode itself, no synchronization done inside of this method.
220 * @throws IOException
221 */
222 private BTreeNode<Key,Value> getChild(Transaction tx, int idx) throws IOException {
223 if (isBranch() && idx >= 0 && idx < children.length) {
224 BTreeNode<Key, Value> result = this.index.loadNode(tx, children[idx], this);
225 return result;
226 } else {
227 return null;
228 }
229 }
230
231 public Value remove(Transaction tx, Key key) throws IOException {
232
233 if(isBranch()) {
234 int idx = Arrays.binarySearch(keys, key);
235 idx = idx < 0 ? -(idx + 1) : idx + 1;
236 BTreeNode<Key, Value> child = getChild(tx, idx);
237 if( child.getPageId() == index.getPageId() ) {
238 throw new IOException("BTree corrupted: Cylce detected.");
239 }
240 Value rc = child.remove(tx, key);
241
242 // child node is now empty.. remove it from the branch node.
243 if( child.keys.length == 0 ) {
244
245 // If the child node is a branch, promote
246 if( child.isBranch() ) {
247 // This is cause branches are never really empty.. they just go down to 1 child..
248 children[idx] = child.children[0];
249 } else {
250
251 // The child was a leaf. Then we need to actually remove it from this branch node..
252
253 // We need to update the previous child's next pointer to skip over the child being removed....
254 if( idx > 0 && children.length > 1) {
255 BTreeNode<Key, Value> previousChild = getChild(tx, idx-1);
256 previousChild.next = child.next;
257 index.storeNode(tx, previousChild, true);
258 }
259
260 if( idx < children.length-1 ) {
261 // Delete it and key to the right.
262 setBranchData(arrayDelete(keys, idx), arrayDelete(children, idx));
263 } else {
264 // It was the last child.. Then delete it and key to the left
265 setBranchData(arrayDelete(keys, idx-1), arrayDelete(children, idx));
266 }
267
268 // If we are the root node, and only have 1 child left. Then
269 // make the root be the leaf node.
270 if( children.length == 1 && parent==null ) {
271 child = getChild(tx, 0);
272 keys = child.keys;
273 children = child.children;
274 values = child.values;
275 // free up the page..
276 tx.free(child.getPage());
277 }
278
279 }
280 index.storeNode(tx, this, true);
281 }
282
283 return rc;
284 } else {
285 int idx = Arrays.binarySearch(keys, key);
286 if (idx < 0) {
287 return null;
288 } else {
289 Value oldValue = values[idx];
290 setLeafData(arrayDelete(keys, idx), arrayDelete(values, idx));
291
292 if( keys.length==0 && parent!=null) {
293 tx.free(getPage());
294 } else {
295 index.storeNode(tx, this, true);
296 }
297
298 return oldValue;
299 }
300 }
301 }
302
303 public Value put(Transaction tx, Key key, Value value) throws IOException {
304 if (key == null) {
305 throw new IllegalArgumentException("Key cannot be null");
306 }
307
308 if( isBranch() ) {
309 return getLeafNode(tx, this, key).put(tx, key, value);
310 } else {
311 int idx = Arrays.binarySearch(keys, key);
312
313 Value oldValue=null;
314 if (idx >= 0) {
315 // Key was found... Overwrite
316 oldValue = values[idx];
317 values[idx] = value;
318 setLeafData(keys, values);
319 } else {
320 // Key was not found, Insert it
321 idx = -(idx + 1);
322 setLeafData(arrayInsert(keys, key, idx), arrayInsert(values, value, idx));
323 }
324
325 try {
326 index.storeNode(tx, this, allowOverflow());
327 } catch ( Transaction.PageOverflowIOException e ) {
328 // If we get an overflow
329 split(tx);
330 }
331
332 return oldValue;
333 }
334 }
335
336 private void promoteValue(Transaction tx, Key key, long nodeId) throws IOException {
337
338 int idx = Arrays.binarySearch(keys, key);
339 idx = idx < 0 ? -(idx + 1) : idx + 1;
340 setBranchData(arrayInsert(keys, key, idx), arrayInsert(children, nodeId, idx + 1));
341
342 try {
343 index.storeNode(tx, this, allowOverflow());
344 } catch ( Transaction.PageOverflowIOException e ) {
345 split(tx);
346 }
347
348 }
349
350 /**
351 * Internal to the BTreeNode method
352 */
353 private void split(Transaction tx) throws IOException {
354 Key[] leftKeys;
355 Key[] rightKeys;
356 Value[] leftValues=null;
357 Value[] rightValues=null;
358 long[] leftChildren=null;
359 long[] rightChildren=null;
360 Key separator;
361
362 int vc = keys.length;
363 int pivot = vc / 2;
364
365 // Split the node into two nodes
366 if( isBranch() ) {
367
368 leftKeys = createKeyArray(pivot);
369 leftChildren = new long[leftKeys.length + 1];
370 rightKeys = createKeyArray(vc - (pivot + 1));
371 rightChildren = new long[rightKeys.length + 1];
372
373 System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
374 System.arraycopy(children, 0, leftChildren, 0, leftChildren.length);
375 System.arraycopy(keys, leftKeys.length + 1, rightKeys, 0, rightKeys.length);
376 System.arraycopy(children, leftChildren.length, rightChildren, 0, rightChildren.length);
377
378 // Is it a Simple Prefix BTree??
379 Prefixer<Key> prefixer = index.getPrefixer();
380 if(prefixer!=null) {
381 separator = prefixer.getSimplePrefix(leftKeys[leftKeys.length - 1], rightKeys[0]);
382 } else {
383 separator = keys[leftKeys.length];
384 }
385
386
387 } else {
388
389 leftKeys = createKeyArray(pivot);
390 leftValues = createValueArray(leftKeys.length);
391 rightKeys = createKeyArray(vc - pivot);
392 rightValues = createValueArray(rightKeys.length);
393
394 System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
395 System.arraycopy(values, 0, leftValues, 0, leftValues.length);
396 System.arraycopy(keys, leftKeys.length, rightKeys, 0, rightKeys.length);
397 System.arraycopy(values, leftValues.length, rightValues, 0, rightValues.length);
398
399 // separator = getSeparator(leftVals[leftVals.length - 1],
400 // rightVals[0]);
401 separator = rightKeys[0];
402
403 }
404
405 // Promote the pivot to the parent branch
406 if (parent == null) {
407
408 // This can only happen if this is the root
409 BTreeNode<Key,Value> rNode = this.index.createNode(tx, this);
410 BTreeNode<Key,Value> lNode = this.index.createNode(tx, this);
411
412 if( isBranch() ) {
413 rNode.setBranchData(rightKeys, rightChildren);
414 lNode.setBranchData(leftKeys, leftChildren);
415 } else {
416 rNode.setLeafData(rightKeys, rightValues);
417 lNode.setLeafData(leftKeys, leftValues);
418 lNode.setNext(rNode.getPageId());
419 }
420
421 Key[] v = createKeyArray(1);
422 v[0]=separator;
423 setBranchData(v, new long[] { lNode.getPageId(), rNode.getPageId() });
424
425 index.storeNode(tx, this, true);
426 index.storeNode(tx, rNode, true);
427 index.storeNode(tx, lNode, true);
428
429 } else {
430 BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
431
432 if( isBranch() ) {
433 setBranchData(leftKeys, leftChildren);
434 rNode.setBranchData(rightKeys, rightChildren);
435 } else {
436 rNode.setNext(next);
437 next = rNode.getPageId();
438 setLeafData(leftKeys, leftValues);
439 rNode.setLeafData(rightKeys, rightValues);
440 }
441
442 index.storeNode(tx, this, true);
443 index.storeNode(tx, rNode, true);
444 parent.promoteValue(tx, separator, rNode.getPageId());
445 }
446 }
447
448 public void printStructure(Transaction tx, PrintWriter out, String prefix) throws IOException {
449 if( prefix.length()>0 && parent == null ) {
450 throw new IllegalStateException("Cycle back to root node detected.");
451 }
452
453 if( isBranch() ) {
454 for(int i=0 ; i < children.length; i++) {
455 BTreeNode<Key, Value> child = getChild(tx, i);
456 if( i == children.length-1) {
457 out.println(prefix+"\\- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":""));
458 child.printStructure(tx, out, prefix+" ");
459 } else {
460 out.println(prefix+"|- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")+" : "+keys[i]);
461 child.printStructure(tx, out, prefix+" ");
462 }
463 }
464 }
465 }
466
467
468 public int getMinLeafDepth(Transaction tx, int depth) throws IOException {
469 depth++;
470 if( isBranch() ) {
471 int min = Integer.MAX_VALUE;
472 for(int i=0 ; i < children.length; i++) {
473 min = Math.min(min, getChild(tx, i).getMinLeafDepth(tx, depth));
474 }
475 return min;
476 } else {
477 // print(depth*2, "- "+page.getPageId());
478 return depth;
479 }
480 }
481
482 public int getMaxLeafDepth(Transaction tx, int depth) throws IOException {
483 depth++;
484 if( isBranch() ) {
485 int v = 0;
486 for(int i=0 ; i < children.length; i++) {
487 v = Math.max(v, getChild(tx, i).getMaxLeafDepth(tx, depth));
488 }
489 depth = v;
490 }
491 return depth;
492 }
493
494 public Value get(Transaction tx, Key key) throws IOException {
495 if (key == null) {
496 throw new IllegalArgumentException("Key cannot be null");
497 }
498 if( isBranch() ) {
499 return getLeafNode(tx, this, key).get(tx, key);
500 } else {
501 int idx = Arrays.binarySearch(keys, key);
502 if (idx < 0) {
503 return null;
504 } else {
505 return values[idx];
506 }
507 }
508 }
509
510 public boolean isEmpty(final Transaction tx) throws IOException {
511 return keys.length==0;
512 }
513
514 public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException {
515 if (visitor == null) {
516 throw new IllegalArgumentException("Visitor cannot be null");
517 }
518 if( isBranch() ) {
519 for(int i=0; i < this.children.length; i++) {
520 Key key1 = null;
521 if( i!=0 ) {
522 key1 = keys[i-1];
523 }
524 Key key2 = null;
525 if( i!=this.children.length-1 ) {
526 key2 = keys[i];
527 }
528 if( visitor.isInterestedInKeysBetween(key1, key2) ) {
529 BTreeNode<Key, Value> child = getChild(tx, i);
530 child.visit(tx, visitor);
531 }
532 }
533 } else {
534 visitor.visit(Arrays.asList(keys), Arrays.asList(values));
535 }
536 }
537
538 public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException {
539 BTreeNode<Key, Value> node = this;
540 while( node .isBranch() ) {
541 node = node.getChild(tx, 0);
542 }
543 if( node.values.length>0 ) {
544 return new KeyValueEntry(node.keys[0], node.values[0]);
545 } else {
546 return null;
547 }
548 }
549
550 public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException {
551 BTreeNode<Key, Value> node = this;
552 while( node.isBranch() ) {
553 node = node.getChild(tx, node.children.length-1);
554 }
555 if( node.values.length>0 ) {
556 int idx = node.values.length-1;
557 return new KeyValueEntry(node.keys[idx], node.values[idx]);
558 } else {
559 return null;
560 }
561 }
562
563 public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws IOException {
564 BTreeNode<Key, Value> node = this;
565 while( node .isBranch() ) {
566 node = node.getChild(tx, 0);
567 }
568 return node;
569 }
570
571 public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key startKey) throws IOException {
572 if (startKey == null) {
573 return iterator(tx);
574 }
575 if( isBranch() ) {
576 return getLeafNode(tx, this, startKey).iterator(tx, startKey);
577 } else {
578 int idx = Arrays.binarySearch(keys, startKey);
579 if (idx < 0) {
580 idx = -(idx + 1);
581 }
582 return new BTreeIterator(tx, this, idx);
583 }
584 }
585
586 public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException {
587 return new BTreeIterator(tx, getFirstLeafNode(tx), 0);
588 }
589
590 public void clear(Transaction tx) throws IOException {
591 if( isBranch() ) {
592 for (int i = 0; i < children.length; i++) {
593 BTreeNode<Key, Value> node = index.loadNode(tx, children[i], this);
594 node.clear(tx);
595 tx.free(node.getPage());
596 }
597 }
598 // Reset the root node to be a leaf.
599 if( parent == null ) {
600 setLeafData(createKeyArray(0), createValueArray(0));
601 next=-1;
602 index.storeNode(tx, this, true);
603 }
604 }
605
606
607 private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
608 BTreeNode<Key, Value> current = node;
609 while( true ) {
610 if( current.isBranch() ) {
611 int idx = Arrays.binarySearch(current.keys, key);
612 idx = idx < 0 ? -(idx + 1) : idx + 1;
613 BTreeNode<Key, Value> child = current.getChild(tx, idx);
614
615 // A little cycle detection for sanity's sake
616 if( child == node ) {
617 throw new IOException("BTree corrupted: Cylce detected.");
618 }
619
620 current = child;
621 } else {
622 break;
623 }
624 }
625 return current;
626 }
627
628 public boolean contains(Transaction tx, Key key) throws IOException {
629 if (key == null) {
630 throw new IllegalArgumentException("Key cannot be null");
631 }
632
633 if( isBranch() ) {
634 return getLeafNode(tx, this, key).contains(tx, key);
635 } else {
636 int idx = Arrays.binarySearch(keys, key);
637 if (idx < 0) {
638 return false;
639 } else {
640 return true;
641 }
642 }
643 }
644
645 ///////////////////////////////////////////////////////////////////
646 // Implementation methods
647 ///////////////////////////////////////////////////////////////////
648
649
650 private boolean allowOverflow() {
651 // Only allow page overflow if there are <= 3 keys in the node. Otherwise a split will occur on overflow
652 return this.keys.length<=3;
653 }
654
655
656 private void setLeafData(Key[] keys, Value[] values) {
657 this.keys = keys;
658 this.values = values;
659 this.children = null;
660 }
661
662 private void setBranchData(Key[] keys, long[] nodeIds) {
663 this.keys = keys;
664 this.children = nodeIds;
665 this.values = null;
666 }
667
668 @SuppressWarnings("unchecked")
669 private Key[] createKeyArray(int size) {
670 return (Key[])new Object[size];
671 }
672
673 @SuppressWarnings("unchecked")
674 private Value[] createValueArray(int size) {
675 return (Value[])new Object[size];
676 }
677
678 @SuppressWarnings("unchecked")
679 static private <T> T[] arrayDelete(T[] vals, int idx) {
680 T[] newVals = (T[])new Object[vals.length - 1];
681 if (idx > 0) {
682 System.arraycopy(vals, 0, newVals, 0, idx);
683 }
684 if (idx < newVals.length) {
685 System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
686 }
687 return newVals;
688 }
689
690 static private long[] arrayDelete(long[] vals, int idx) {
691 long[] newVals = new long[vals.length - 1];
692 if (idx > 0) {
693 System.arraycopy(vals, 0, newVals, 0, idx);
694 }
695 if (idx < newVals.length) {
696 System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
697 }
698 return newVals;
699 }
700
701 @SuppressWarnings("unchecked")
702 static private <T> T[] arrayInsert(T[] vals, T val, int idx) {
703 T[] newVals = (T[])new Object[vals.length + 1];
704 if (idx > 0) {
705 System.arraycopy(vals, 0, newVals, 0, idx);
706 }
707 newVals[idx] = val;
708 if (idx < vals.length) {
709 System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
710 }
711 return newVals;
712 }
713
714
715 static private long[] arrayInsert(long[] vals, long val, int idx) {
716
717 long[] newVals = new long[vals.length + 1];
718 if (idx > 0) {
719 System.arraycopy(vals, 0, newVals, 0, idx);
720 }
721 newVals[idx] = val;
722 if (idx < vals.length) {
723 System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
724 }
725 return newVals;
726 }
727
728 ///////////////////////////////////////////////////////////////////
729 // Property Accessors
730 ///////////////////////////////////////////////////////////////////
731 private boolean isBranch() {
732 return children!=null;
733 }
734
735 public long getPageId() {
736 return page.getPageId();
737 }
738
739 public BTreeNode<Key, Value> getParent() {
740 return parent;
741 }
742
743 public void setParent(BTreeNode<Key, Value> parent) {
744 this.parent = parent;
745 }
746
747 public Page<BTreeNode<Key, Value>> getPage() {
748 return page;
749 }
750
751 public void setPage(Page<BTreeNode<Key, Value>> page) {
752 this.page = page;
753 }
754
755 public long getNext() {
756 return next;
757 }
758
759 public void setNext(long next) {
760 this.next = next;
761 }
762
763 @Override
764 public String toString() {
765 return "[BTreeNode "+(isBranch()?"branch":"leaf")+": "+Arrays.asList(keys)+"]";
766 }
767
768 }
769
770