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