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.activemq.kaha.impl.index.tree;
18
19 import java.io.DataInput;
20 import java.io.DataOutput;
21 import java.io.IOException;
22 import java.util.ArrayList;
23 import java.util.HashSet;
24 import java.util.List;
25 import java.util.Set;
26
27 import org.apache.activemq.kaha.Marshaller;
28 import org.apache.commons.logging.Log;
29 import org.apache.commons.logging.LogFactory;
30
31 /**
32 * Page in a BTree
33 *
34 * @version $Revision: 1.1.1.1 $
35 */
36 class TreePage {
37
38 static final int PAGE_HEADER_SIZE = 18;
39 private static final transient Log LOG = LogFactory.getLog(TreePage.class);
40
41 static enum Flavour {
42 LESS, MORE
43 }
44
45 private TreeIndex tree;
46 private int maximumEntries;
47 private long id;
48 private long parentId = TreeEntry.NOT_SET;
49 private boolean leaf = true;
50 private List<TreeEntry> treeEntries;
51 /*
52 * for persistence only
53 */
54 private long nextFreePageId = TreeEntry.NOT_SET;
55 private boolean active = true;
56
57 /**
58 * Constructor
59 *
60 * @param tree
61 * @param id
62 * @param parentId
63 * @param maximumEntries
64 */
65 TreePage(TreeIndex tree, long id, long parentId, int maximumEntries) {
66 this(maximumEntries);
67 this.tree = tree;
68 this.id = id;
69 this.parentId = parentId;
70 }
71
72 /**
73 * Constructor
74 *
75 * @param maximumEntries
76 */
77 public TreePage(int maximumEntries) {
78 this.maximumEntries = maximumEntries;
79 this.treeEntries = new ArrayList<TreeEntry>(maximumEntries);
80 }
81
82 public String toString() {
83 return "TreePage[" + getId() + "]parent=" + getParentId();
84 }
85
86 public boolean equals(Object o) {
87 boolean result = false;
88 if (o instanceof TreePage) {
89 TreePage other = (TreePage)o;
90 result = other.id == id;
91 }
92 return result;
93 }
94
95 public int hashCode() {
96 return (int)id;
97 }
98
99 boolean isActive() {
100 return this.active;
101 }
102
103 void setActive(boolean active) {
104 this.active = active;
105 }
106
107 long getNextFreePageId() {
108 return this.nextFreePageId;
109 }
110
111 void setNextFreePageId(long nextPageId) {
112 this.nextFreePageId = nextPageId;
113 }
114
115 long getId() {
116 return id;
117 }
118
119 void setId(long id) {
120 this.id = id;
121 }
122
123 void write(Marshaller keyMarshaller, DataOutput dataOut) throws IOException {
124 writeHeader(dataOut);
125 dataOut.writeInt(treeEntries.size());
126 for (TreeEntry entry : treeEntries) {
127 entry.write(keyMarshaller, dataOut);
128 }
129 }
130
131 void read(Marshaller keyMarshaller, DataInput dataIn) throws IOException {
132 readHeader(dataIn);
133 int size = dataIn.readInt();
134 treeEntries.clear();
135 for (int i = 0; i < size; i++) {
136 TreeEntry entry = new TreeEntry();
137 entry.read(keyMarshaller, dataIn);
138 treeEntries.add(entry);
139 }
140 }
141
142 void readHeader(DataInput dataIn) throws IOException {
143 active = dataIn.readBoolean();
144 leaf = dataIn.readBoolean();
145 setParentId(dataIn.readLong());
146 nextFreePageId = dataIn.readLong();
147 }
148
149 void writeHeader(DataOutput dataOut) throws IOException {
150 dataOut.writeBoolean(isActive());
151 dataOut.writeBoolean(isLeaf());
152 dataOut.writeLong(getParentId());
153 dataOut.writeLong(nextFreePageId);
154 }
155
156 boolean isEmpty() {
157 return treeEntries.isEmpty();
158 }
159
160 boolean isFull() {
161 return treeEntries.size() >= maximumEntries;
162 }
163
164 boolean isRoot() {
165 return getParentId() < 0;
166 }
167
168 boolean isLeaf() {
169 if (treeEntries.isEmpty()) {
170 leaf = true;
171 }
172 return leaf;
173 }
174
175 boolean isUnderflowed() {
176 return treeEntries.size() < (maximumEntries / 2);
177 }
178
179 boolean isOverflowed() {
180 return treeEntries.size() > maximumEntries;
181 }
182
183 void setLeaf(boolean newValue) {
184 this.leaf = newValue;
185 }
186
187 TreePage getParent() throws IOException {
188 return tree.lookupPage(parentId);
189 }
190
191 long getParentId() {
192 return parentId;
193 }
194
195 void setParentId(long newId) throws IOException {
196 if (newId == this.id) {
197 throw new IllegalStateException("Cannot set page as a child of itself " + this
198 + " trying to set parentId = " + newId);
199 }
200 this.parentId = newId;
201 tree.writePage(this);
202 }
203
204 List<TreeEntry> getEntries() {
205 return treeEntries;
206 }
207
208 void setEntries(List<TreeEntry> newEntries) {
209 this.treeEntries = newEntries;
210 }
211
212 int getMaximumEntries() {
213 return this.maximumEntries;
214 }
215
216 void setMaximumEntries(int maximumEntries) {
217 this.maximumEntries = maximumEntries;
218 }
219
220 int size() {
221 return treeEntries.size();
222 }
223
224 TreeIndex getTree() {
225 return this.tree;
226 }
227
228 void setTree(TreeIndex tree) {
229 this.tree = tree;
230 }
231
232 void reset() throws IOException {
233 treeEntries.clear();
234 setParentId(TreeEntry.NOT_SET);
235 setNextFreePageId(TreeEntry.NOT_SET);
236 setLeaf(true);
237 }
238
239 public TreeEntry find(TreeEntry key) throws IOException {
240 int low = 0;
241 int high = size() - 1;
242 long pageId = -1;
243 while (low <= high) {
244 int mid = (low + high) >> 1;
245 TreeEntry te = getTreeEntry(mid);
246 int cmp = te.compareTo(key);
247 if (cmp == 0) {
248 return te;
249 } else if (cmp < 0) {
250 low = mid + 1;
251 pageId = te.getNextPageId();
252 } else {
253 high = mid - 1;
254 pageId = te.getPrevPageId();
255 }
256 }
257 TreePage page = tree.lookupPage(pageId);
258 if (page != null) {
259 return page.find(key);
260 }
261 return null;
262 }
263
264 TreeEntry put(TreeEntry newEntry) throws IOException {
265 TreeEntry result = null;
266 if (isRoot()) {
267 if (isEmpty()) {
268 insertTreeEntry(0, newEntry);
269 } else {
270 result = doInsert(null, newEntry);
271 }
272 } else {
273 throw new IllegalStateException("insert() should not be called on non root page - " + this);
274 }
275 return result;
276 }
277
278 TreeEntry remove(TreeEntry entry) throws IOException {
279 TreeEntry result = null;
280 if (isRoot()) {
281 if (!isEmpty()) {
282 result = doRemove(entry);
283 }
284 } else {
285 throw new IllegalStateException("remove() should not be called on non root page");
286 }
287 return result;
288 }
289
290 private TreeEntry doInsert(Flavour flavour, TreeEntry newEntry) throws IOException {
291 TreeEntry result = null;
292 TreePageEntry closest = findClosestEntry(newEntry);
293 if (closest != null) {
294 TreeEntry closestEntry = closest.getTreeEntry();
295 TreePage closestPage = closest.getTreePage();
296 int cmp = closestEntry.compareTo(newEntry);
297 if (cmp == 0) {
298 // we actually just need to pass back the value
299 long oldValue = closestEntry.getIndexOffset();
300 closestEntry.setIndexOffset(newEntry.getIndexOffset());
301 newEntry.setIndexOffset(oldValue);
302 result = newEntry;
303 save();
304 } else if (closestPage != null) {
305 result = closestPage.doInsert(closest.getFlavour(), newEntry);
306 } else {
307 if (!isFull()) {
308 insertTreeEntry(closest.getIndex(), newEntry);
309 save();
310 } else {
311 doOverflow(flavour, newEntry);
312 }
313 }
314 } else {
315 if (!isFull()) {
316 doInsertEntry(newEntry);
317 save();
318 } else {
319 // need to insert the new entry and propogate up the hightest
320 // value
321 doOverflow(flavour, newEntry);
322 }
323 }
324 return result;
325 }
326
327 private TreePage doOverflow(Flavour flavour, TreeEntry newEntry) throws IOException {
328 TreePage result = this;
329 TreeEntry theEntry = newEntry;
330 if (!isFull()) {
331 doInsertEntry(newEntry);
332 save();
333 } else {
334 if (!isRoot() && flavour != null) {
335 // we aren't the root, but to ensure the correct distribution we
336 // need to
337 // insert the new entry and take a node of the end of the page
338 // and pass that up the tree to find a home
339 doInsertEntry(newEntry);
340 if (flavour == Flavour.LESS) {
341 theEntry = removeTreeEntry(0);
342 theEntry.reset();
343 theEntry.setNextPageId(getId());
344 } else {
345 theEntry = removeTreeEntry(size() - 1);
346 theEntry.reset();
347 theEntry.setPrevPageId(getId());
348 }
349 save();
350
351 result = getParent().doOverflow(flavour, theEntry);
352 if (!theEntry.equals(newEntry)) {
353 // the newEntry stayed here
354 result = this;
355 }
356 } else {
357 // so we are the root and need to split
358 doInsertEntry(newEntry);
359 int midIndex = size() / 2;
360 TreeEntry midEntry = removeTreeEntry(midIndex);
361 List<TreeEntry> subList = getSubList(midIndex, size());
362 removeAllTreeEntries(subList);
363 TreePage newRoot = tree.createRoot();
364 newRoot.setLeaf(false);
365 this.setParentId(newRoot.getId());
366 save(); // we are no longer root - need to save - we maybe
367 // looked up v. soon!
368 TreePage rightPage = tree.createPage(newRoot.getId());
369 rightPage.setEntries(subList);
370 rightPage.checkLeaf();
371 resetParentId(rightPage.getId(), rightPage.getEntries());
372 midEntry.setNextPageId(rightPage.getId());
373 midEntry.setPrevPageId(this.getId());
374 newRoot.insertTreeEntry(0, midEntry);
375 resetParentId(newRoot.getId(), newRoot.getEntries());
376 save();
377 rightPage.save();
378 newRoot.save();
379 }
380 }
381 return result;
382 }
383
384 private TreeEntry doRemove(TreeEntry entry) throws IOException {
385 TreeEntry result = null;
386 TreePageEntry closest = findClosestEntry(entry);
387 if (closest != null) {
388 TreeEntry closestEntry = closest.getTreeEntry();
389 if (closestEntry != null) {
390 TreePage closestPage = closest.getTreePage();
391 int cmp = closestEntry.compareTo(entry);
392 if (cmp == 0) {
393 result = closest.getTreeEntry();
394 int index = closest.getIndex();
395 removeTreeEntry(index);
396 save();
397 // ensure we don't loose children
398 doUnderflow(result, index);
399 } else if (closestPage != null) {
400 closestPage.doRemove(entry);
401 }
402 }
403 }
404 return result;
405 }
406
407 /**
408 * @return true if the page is removed
409 * @throws IOException
410 */
411 private boolean doUnderflow() throws IOException {
412 boolean result = false;
413 boolean working = true;
414 while (working && isUnderflowed() && !isEmpty() && !isLeaf()) {
415 int lastIndex = size() - 1;
416 TreeEntry entry = getTreeEntry(lastIndex);
417 working = doUnderflow(entry, lastIndex);
418 }
419 if (isUnderflowed() && isLeaf()) {
420 result = doUnderflowLeaf();
421 }
422 return result;
423 }
424
425 private boolean doUnderflow(TreeEntry entry, int index) throws IOException {
426 boolean result = false;
427 // pull an entry up from a leaf to fill the empty space
428 if (entry.getNextPageId() != TreeEntry.NOT_SET) {
429 TreePage page = tree.lookupPage(entry.getNextPageId());
430 if (page != null && !page.isEmpty()) {
431 TreeEntry replacement = page.removeTreeEntry(0);
432 TreeEntry copy = replacement.copy();
433 checkParentIdForRemovedPageEntry(copy, page.getId(), getId());
434 if (!page.isEmpty()) {
435 copy.setNextPageId(page.getId());
436 page.setParentId(this.id);
437 } else {
438 page.setLeaf(true);
439 }
440 int replacementIndex = doInsertEntry(copy);
441 if (page.doUnderflow()) {
442 // page removed so update our replacement
443 resetPageReference(replacementIndex, copy.getNextPageId());
444 copy.setNextPageId(TreeEntry.NOT_SET);
445 } else {
446 page.save();
447 }
448 save();
449 result = true;
450 }
451 }
452 // ensure we don't loose previous bit of the tree
453 if (entry.getPrevPageId() != TreeEntry.NOT_SET) {
454 TreeEntry prevEntry = (index > 0) ? getTreeEntry(index - 1) : null;
455 if (prevEntry == null || prevEntry.getNextPageId() != entry.getPrevPageId()) {
456 TreePage page = tree.lookupPage(entry.getPrevPageId());
457 if (page != null && !page.isEmpty()) {
458 TreeEntry replacement = page.removeTreeEntry(page.getEntries().size() - 1);
459 TreeEntry copy = replacement.copy();
460 // check children pages of the replacement point to the
461 // correct place
462 checkParentIdForRemovedPageEntry(copy, page.getId(), getId());
463 if (!page.isEmpty()) {
464 copy.setPrevPageId(page.getId());
465 } else {
466 page.setLeaf(true);
467 }
468 insertTreeEntry(index, copy);
469 // if we overflow - the page the replacement ends up on
470 TreePage landed = null;
471 TreeEntry removed = null;
472 if (isOverflowed()) {
473 TreePage parent = getParent();
474 if (parent != null) {
475 removed = getTreeEntry(0);
476 Flavour flavour = getFlavour(parent, removed);
477 if (flavour == Flavour.LESS) {
478 removed = removeTreeEntry(0);
479 landed = parent.doOverflow(flavour, removed);
480 } else {
481 removed = removeTreeEntry(size() - 1);
482 landed = parent.doOverflow(Flavour.MORE, removed);
483 }
484 }
485 }
486 if (page.doUnderflow()) {
487 if (landed == null || landed.equals(this)) {
488 landed = this;
489 }
490
491 resetPageReference(copy.getNextPageId());
492 landed.resetPageReference(copy.getNextPageId());
493 copy.setPrevPageId(TreeEntry.NOT_SET);
494 landed.save();
495 } else {
496 page.save();
497 }
498 save();
499 result = true;
500 }
501 // now we need to check we haven't overflowed this page
502 }
503 }
504 if (!result) {
505 save();
506 }
507 // now see if we need to save this page
508 result |= doUnderflowLeaf();
509 save();
510 return result;
511 }
512
513 private boolean doUnderflowLeaf() throws IOException {
514 boolean result = false;
515 // if we have unerflowed - and we are a leaf - push entries further up
516 // the tree
517 // and delete ourselves
518 if (isUnderflowed() && isLeaf()) {
519 List<TreeEntry> list = new ArrayList<TreeEntry>(treeEntries);
520 treeEntries.clear();
521 for (TreeEntry entry : list) {
522 // need to check for each iteration - we might get promoted to
523 // root
524 TreePage parent = getParent();
525 if (parent != null) {
526 Flavour flavour = getFlavour(parent, entry);
527 TreePage landedOn = parent.doOverflow(flavour, entry);
528 checkParentIdForRemovedPageEntry(entry, getId(), landedOn.getId());
529 }
530 }
531 TreePage parent = getParent();
532 if (parent != null) {
533 parent.checkLeaf();
534 parent.removePageId(getId());
535 parent.doUnderflow();
536 parent.save();
537 tree.releasePage(this);
538 result = true;
539 }
540 }
541 return result;
542 }
543
544 private Flavour getFlavour(TreePage page, TreeEntry entry) {
545 Flavour result = null;
546 if (page != null && !page.getEntries().isEmpty()) {
547 TreeEntry last = page.getEntries().get(page.getEntries().size() - 1);
548 if (last.compareTo(entry) > 0) {
549 result = Flavour.MORE;
550 } else {
551 result = Flavour.LESS;
552 }
553 }
554 return result;
555 }
556
557 private void checkLeaf() {
558 boolean result = false;
559 for (TreeEntry entry : treeEntries) {
560 if (entry.hasChildPagesReferences()) {
561 result = true;
562 break;
563 }
564 }
565 setLeaf(!result);
566 }
567
568 private void checkParentIdForRemovedPageEntry(TreeEntry entry, long oldPageId, long newPageId)
569 throws IOException {
570 TreePage page = tree.lookupPage(entry.getPrevPageId());
571 if (page != null && page.getParentId() == oldPageId) {
572 page.setParentId(newPageId);
573 page.save();
574 }
575 page = tree.lookupPage(entry.getNextPageId());
576 if (page != null && page.getParentId() == oldPageId) {
577 page.setParentId(newPageId);
578 page.save();
579 }
580 }
581
582 private void removePageId(long pageId) {
583 for (TreeEntry entry : treeEntries) {
584 if (entry.getNextPageId() == pageId) {
585 entry.setNextPageId(TreeEntry.NOT_SET);
586 }
587 if (entry.getPrevPageId() == pageId) {
588 entry.setPrevPageId(TreeEntry.NOT_SET);
589 }
590 }
591 }
592
593 private TreePageEntry findClosestEntry(TreeEntry key) throws IOException {
594 TreePageEntry result = null;
595 TreeEntry treeEntry = null;
596 Flavour flavour = null;
597 long pageId = -1;
598 int low = 0;
599 int high = size() - 1;
600 int mid = low;
601 while (low <= high) {
602 mid = (low + high) >> 1;
603 treeEntry = getTreeEntry(mid);
604 int cmp = treeEntry.compareTo(key);
605 if (cmp < 0) {
606 low = mid + 1;
607 pageId = treeEntry.getNextPageId();
608 flavour = Flavour.LESS;
609 } else if (cmp > 0) {
610 high = mid - 1;
611 pageId = treeEntry.getPrevPageId();
612 flavour = Flavour.MORE;
613 } else {
614 // got exact match
615 low = mid;
616 break;
617 }
618 }
619 if (treeEntry != null) {
620 TreePage treePage = tree.lookupPage(pageId);
621 result = new TreePageEntry(treeEntry, treePage, flavour, low);
622 }
623 return result;
624 }
625
626 private int doInsertEntry(TreeEntry newEntry) throws IOException {
627 int low = 0;
628 int high = size() - 1;
629 while (low <= high) {
630 int mid = (low + high) >> 1;
631 TreeEntry midVal = getTreeEntry(mid);
632 int cmp = midVal.compareTo(newEntry);
633 if (cmp < 0) {
634 low = mid + 1;
635 } else if (cmp > 0) {
636 high = mid - 1;
637 }
638 }
639 insertTreeEntry(low, newEntry);
640 return low;
641 }
642
643 private void insertTreeEntry(int index, TreeEntry entry) throws IOException {
644 int p = index - 1;
645 int n = index;
646 TreeEntry prevEntry = (p >= 0 && p < treeEntries.size()) ? treeEntries.get(p) : null;
647 TreeEntry nextEntry = (n >= 0 && n < treeEntries.size()) ? treeEntries.get(n) : null;
648 if (prevEntry != null) {
649 if (prevEntry.getNextPageId() == entry.getNextPageId()) {
650 prevEntry.setNextPageId(TreeEntry.NOT_SET);
651 }
652 if (entry.getPrevPageId() == TreeEntry.NOT_SET) {
653 entry.setPrevPageId(prevEntry.getNextPageId());
654 }
655 }
656 if (nextEntry != null) {
657 if (nextEntry.getPrevPageId() == entry.getPrevPageId()) {
658 nextEntry.setPrevPageId(TreeEntry.NOT_SET);
659 }
660 if (entry.getNextPageId() == TreeEntry.NOT_SET) {
661 entry.setNextPageId(nextEntry.getPrevPageId());
662 }
663 }
664 addTreeEntry(index, entry);
665 }
666
667 private void resetPageReference(int index, long pageId) {
668 int p = index - 1;
669 int n = index;
670 TreeEntry prevEntry = (p >= 0 && p < treeEntries.size()) ? treeEntries.get(p) : null;
671 TreeEntry nextEntry = (n >= 0 && n < treeEntries.size()) ? treeEntries.get(n) : null;
672 if (prevEntry != null) {
673 if (prevEntry.getNextPageId() == pageId) {
674 prevEntry.setNextPageId(TreeEntry.NOT_SET);
675 }
676 }
677 if (nextEntry != null) {
678 if (nextEntry.getPrevPageId() == pageId) {
679 nextEntry.setPrevPageId(TreeEntry.NOT_SET);
680 }
681 }
682 }
683
684 private boolean resetPageReference(long pageId) {
685 boolean updated = false;
686 for (TreeEntry entry : treeEntries) {
687 if (entry.getPrevPageId() == pageId) {
688 entry.setPrevPageId(TreeEntry.NOT_SET);
689 updated = true;
690 }
691 if (entry.getNextPageId() == pageId) {
692 entry.setNextPageId(TreeEntry.NOT_SET);
693 updated = true;
694 }
695 }
696 return updated;
697 }
698
699 private void resetParentId(long newParentId, List<TreeEntry> entries) throws IOException {
700 Set<Long> set = new HashSet<Long>();
701 for (TreeEntry entry : entries) {
702 if (entry != null) {
703 set.add(entry.getPrevPageId());
704 set.add(entry.getNextPageId());
705 }
706 }
707 for (Long pageId : set) {
708 TreePage page = tree.lookupPage(pageId);
709 if (page != null) {
710 page.setParentId(newParentId);
711 }
712 }
713 }
714
715 private void addTreeEntry(int index, TreeEntry entry) throws IOException {
716 treeEntries.add(index, entry);
717 }
718
719 private TreeEntry removeTreeEntry(int index) throws IOException {
720 TreeEntry result = treeEntries.remove(index);
721 return result;
722 }
723
724 private void removeAllTreeEntries(List<TreeEntry> c) {
725 treeEntries.removeAll(c);
726 }
727
728 private List<TreeEntry> getSubList(int from, int to) {
729 return new ArrayList<TreeEntry>(treeEntries.subList(from, to));
730 }
731
732 private TreeEntry getTreeEntry(int index) {
733 TreeEntry result = treeEntries.get(index);
734 return result;
735 }
736
737 void saveHeader() throws IOException {
738 tree.writePage(this);
739 }
740
741 void save() throws IOException {
742 tree.writeFullPage(this);
743 }
744
745 protected void dump() throws IOException {
746 LOG.info(this);
747 Set<Long> set = new HashSet<Long>();
748 for (TreeEntry entry : treeEntries) {
749 if (entry != null) {
750 LOG.info(entry);
751 set.add(entry.getPrevPageId());
752 set.add(entry.getNextPageId());
753 }
754 }
755 for (Long pageId : set) {
756 TreePage page = tree.lookupPage(pageId);
757 if (page != null) {
758 page.dump();
759 }
760 }
761 }
762 }