Home » activemq-parent-5.3.1-source-release » org.apache » activemq » kaha » impl » index » tree » [javadoc | source]

    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   }

Home » activemq-parent-5.3.1-source-release » org.apache » activemq » kaha » impl » index » tree » [javadoc | source]