Home » activemq-parent-5.3.1-source-release » org.apache.kahadb.index » [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.kahadb.index;
   18   
   19   import java.io.IOException;
   20   import java.io.OutputStream;
   21   import java.io.PrintWriter;
   22   import java.util.Iterator;
   23   import java.util.Map;
   24   import java.util.concurrent.atomic.AtomicBoolean;
   25   
   26   import org.apache.commons.logging.Log;
   27   import org.apache.commons.logging.LogFactory;
   28   import org.apache.kahadb.page.Page;
   29   import org.apache.kahadb.page.PageFile;
   30   import org.apache.kahadb.page.Transaction;
   31   import org.apache.kahadb.util.Marshaller;
   32   
   33   /**
   34    * BTreeIndex represents a Variable Magnitude B+Tree in a Page File.
   35    * A BTree is a bit flexible in that it can be used for set or
   36    * map-based indexing.  Leaf nodes are linked together for faster
   37    * iteration of the values. 
   38    *
   39    * <br>
   40    * The Variable Magnitude attribute means that the BTree attempts
   41    * to store as many values and pointers on one page as is possible.
   42    * 
   43    * <br>
   44    * The implementation can optionally a be Simple-Prefix B+Tree.
   45    * 
   46    * <br>
   47    * For those who don't know how a Simple-Prefix B+Tree works, the primary
   48    * distinction is that instead of promoting actual keys to branch pages,
   49    * when leaves are split, a shortest-possible separator is generated at
   50    * the pivot.  That separator is what is promoted to the parent branch
   51    * (and continuing up the list).  As a result, actual keys and pointers
   52    * can only be found at the leaf level.  This also affords the index the
   53    * ability to ignore costly merging and redistribution of pages when
   54    * deletions occur.  Deletions only affect leaf pages in this
   55    * implementation, and so it is entirely possible for a leaf page to be
   56    * completely empty after all of its keys have been removed.
   57    *
   58    * @version $Revision: 902999 $, $Date: 2010-01-25 22:22:44 +0000 (Mon, 25 Jan 2010) $
   59    */
   60   public class BTreeIndex<Key,Value> implements Index<Key,Value> {
   61   
   62       private static final Log LOG = LogFactory.getLog(BTreeIndex.class);
   63   
   64       /**
   65        * Interface used to determine the simple prefix of two keys.
   66        *
   67        * @version $Revision: 902999 $, $Date: 2010-01-25 22:22:44 +0000 (Mon, 25 Jan 2010) $
   68        */
   69       static public interface Prefixer<Key> {
   70           
   71           /**
   72            * This methods should return shortest prefix of value2 where the following still holds:<br/>
   73            * value1 <= prefix <= value2.<br/><br/>
   74            * 
   75            * When this method is called, the following is guaranteed:<br/>
   76            * value1 < value2<br/><br/>
   77            * 
   78            * 
   79            * @param value1
   80            * @param value2
   81            * @return
   82            */
   83           public Key getSimplePrefix(Key value1, Key value2);
   84       }
   85       
   86       /**
   87        * StringPrefixer is a Prefixer implementation that works on strings.
   88        */
   89       static public class StringPrefixer implements Prefixer<String> {
   90           
   91           /**
   92            * Example:
   93            * If value1 is "Hello World"
   94            * and value 2 is "Help Me"
   95            * then the result will be: "Help"
   96            * 
   97            * @see  Prefixer#getSimplePrefix
   98            */
   99           public String getSimplePrefix(String value1, String value2) {
  100               char[] c1 = value1.toCharArray();
  101               char[] c2 = value2.toCharArray();
  102               int n = Math.min(c1.length, c2.length);
  103               int i =0;
  104               while (i < n) {
  105                   if (c1[i] != c2[i]) {
  106                       return value2.substring(0,i+1);
  107                   }
  108                   i++;
  109               }
  110               
  111               if( n == c2.length ) {
  112                   return value2;
  113               }
  114               return value2.substring(0,n);
  115           }
  116       }    
  117   
  118       private PageFile pageFile;
  119       private long pageId;
  120       private AtomicBoolean loaded = new AtomicBoolean();
  121       
  122       private final BTreeNode.Marshaller<Key, Value> marshaller = new BTreeNode.Marshaller<Key, Value>(this);
  123       private Marshaller<Key> keyMarshaller;
  124       private Marshaller<Value> valueMarshaller;
  125       private Prefixer<Key> prefixer;
  126   
  127       public BTreeIndex() {
  128       }
  129   
  130       public BTreeIndex(long rootPageId) {
  131           this.pageId = rootPageId;
  132       }
  133       
  134       @SuppressWarnings("unchecked")
  135       public BTreeIndex(Page page) {
  136           this(page.getPageId());
  137       }
  138       
  139       public BTreeIndex(PageFile pageFile, long rootPageId) {
  140           this.pageFile = pageFile;
  141           this.pageId = rootPageId;
  142       }
  143   
  144       @SuppressWarnings("unchecked")
  145       public BTreeIndex(PageFile pageFile, Page page) {
  146           this(pageFile, page.getPageId());
  147       }
  148   
  149       synchronized public void load(Transaction tx) throws IOException {
  150           if (loaded.compareAndSet(false, true)) {
  151               LOG.debug("loading");
  152               if( keyMarshaller == null ) {
  153                   throw new IllegalArgumentException("The key marshaller must be set before loading the BTreeIndex");
  154               }
  155               if( valueMarshaller == null ) {
  156                   throw new IllegalArgumentException("The value marshaller must be set before loading the BTreeIndex");
  157               }
  158               
  159               final Page<BTreeNode<Key,Value>> p = tx.load(pageId, null);
  160               if( p.getType() == Page.PAGE_FREE_TYPE ) {
  161                    // Need to initialize it..
  162                   BTreeNode<Key, Value> root = createNode(p, null);
  163                   storeNode(tx, root, true);
  164               }
  165           }
  166       }
  167       
  168       synchronized public void unload(Transaction tx) {
  169           if (loaded.compareAndSet(true, false)) {
  170           }    
  171       }
  172       
  173       private BTreeNode<Key,Value> getRoot(Transaction tx) throws IOException {
  174           return loadNode(tx, pageId, null);
  175       }
  176       
  177       synchronized public boolean containsKey(Transaction tx, Key key) throws IOException {
  178           assertLoaded();
  179           return getRoot(tx).contains(tx, key);
  180       }
  181   
  182       synchronized public Value get(Transaction tx, Key key) throws IOException {
  183           assertLoaded();
  184           return getRoot(tx).get(tx, key);
  185       }
  186   
  187       synchronized public Value put(Transaction tx, Key key, Value value) throws IOException {
  188           assertLoaded();
  189           return getRoot(tx).put(tx, key, value);
  190       }
  191   
  192       synchronized public Value remove(Transaction tx, Key key) throws IOException {
  193           assertLoaded();
  194           return getRoot(tx).remove(tx, key);
  195       }
  196       
  197       public boolean isTransient() {
  198           return false;
  199       }
  200   
  201       synchronized public void clear(Transaction tx) throws IOException {
  202           getRoot(tx).clear(tx);
  203       }
  204   
  205       synchronized public int getMinLeafDepth(Transaction tx) throws IOException {
  206           return getRoot(tx).getMinLeafDepth(tx, 0);
  207       }
  208   
  209       synchronized public int getMaxLeafDepth(Transaction tx) throws IOException {
  210           return getRoot(tx).getMaxLeafDepth(tx, 0);
  211       }
  212   
  213       synchronized public void printStructure(Transaction tx, PrintWriter out) throws IOException {
  214           getRoot(tx).printStructure(tx, out, "");
  215       }
  216       
  217       synchronized public void printStructure(Transaction tx, OutputStream out) throws IOException {
  218           PrintWriter pw = new PrintWriter(out,false);
  219           getRoot(tx).printStructure(tx, pw, "");
  220           pw.flush();
  221       }
  222   
  223       synchronized public boolean isEmpty(final Transaction tx) throws IOException {
  224           return getRoot(tx).isEmpty(tx);
  225       }
  226   
  227       synchronized public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException {
  228           return getRoot(tx).iterator(tx);
  229       }
  230       
  231       synchronized public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key initialKey) throws IOException {
  232           return getRoot(tx).iterator(tx, initialKey);
  233       }
  234       
  235       synchronized public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException {
  236           getRoot(tx).visit(tx, visitor);
  237       }
  238   
  239       synchronized public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException {
  240           return getRoot(tx).getFirst(tx);
  241       }
  242   
  243       synchronized public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException {
  244           return getRoot(tx).getLast(tx);
  245       }
  246   
  247       ///////////////////////////////////////////////////////////////////
  248       // Internal implementation methods
  249       ///////////////////////////////////////////////////////////////////
  250       
  251       private void assertLoaded() throws IllegalStateException {
  252           if( !loaded.get() ) {
  253               throw new IllegalStateException("The BTreeIndex is not loaded");
  254           }
  255       }
  256   
  257       ///////////////////////////////////////////////////////////////////
  258       // Internal methods made accessible to BTreeNode
  259       ///////////////////////////////////////////////////////////////////
  260   
  261       BTreeNode<Key,Value> loadNode(Transaction tx, long pageId, BTreeNode<Key,Value> parent) throws IOException {
  262           Page<BTreeNode<Key,Value>> page = tx.load(pageId, marshaller);
  263           BTreeNode<Key, Value> node = page.get();
  264           node.setPage(page);
  265           node.setParent(parent);
  266           return node;
  267       }
  268   
  269       BTreeNode<Key,Value> createNode(Transaction tx, BTreeNode<Key,Value> parent) throws IOException {
  270           Page<BTreeNode<Key,Value>> p = tx.allocate();
  271           BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(this);
  272           node.setPage(p);
  273           node.setParent(parent);
  274           node.setEmpty();
  275           p.set(node);
  276           return node;
  277       }
  278   
  279       BTreeNode<Key,Value> createNode(Page<BTreeNode<Key,Value>> p, BTreeNode<Key,Value> parent) throws IOException {
  280           BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(this);
  281           node.setPage(p);
  282           node.setParent(parent);
  283           node.setEmpty();
  284           p.set(node);
  285           return node;
  286       }
  287       
  288       void storeNode(Transaction tx, BTreeNode<Key,Value> node, boolean overflow) throws IOException {
  289           tx.store(node.getPage(), marshaller, overflow);
  290       }
  291           
  292      
  293       ///////////////////////////////////////////////////////////////////
  294       // Property Accessors
  295       ///////////////////////////////////////////////////////////////////
  296   
  297       public PageFile getPageFile() {
  298           return pageFile;
  299       }
  300       public long getPageId() {
  301           return pageId;
  302       }
  303   
  304       public Marshaller<Key> getKeyMarshaller() {
  305           return keyMarshaller;
  306       }
  307       public void setKeyMarshaller(Marshaller<Key> keyMarshaller) {
  308           this.keyMarshaller = keyMarshaller;
  309       }
  310   
  311       public Marshaller<Value> getValueMarshaller() {
  312           return valueMarshaller;
  313       }
  314       public void setValueMarshaller(Marshaller<Value> valueMarshaller) {
  315           this.valueMarshaller = valueMarshaller;
  316       }
  317   
  318       public Prefixer<Key> getPrefixer() {
  319           return prefixer;
  320       }
  321       public void setPrefixer(Prefixer<Key> prefixer) {
  322           this.prefixer = prefixer;
  323       }
  324   
  325       public void setPageFile(PageFile pageFile) {
  326           this.pageFile = pageFile;
  327       }
  328   
  329       public void setPageId(long pageId) {
  330           this.pageId = pageId;
  331       }
  332   
  333   }

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