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.File;
   20   import java.io.IOException;
   21   import java.io.RandomAccessFile;
   22   import java.util.concurrent.atomic.AtomicBoolean;
   23   import org.apache.activemq.kaha.Marshaller;
   24   import org.apache.activemq.kaha.StoreEntry;
   25   import org.apache.activemq.kaha.impl.index.Index;
   26   import org.apache.activemq.kaha.impl.index.IndexManager;
   27   import org.apache.activemq.util.DataByteArrayInputStream;
   28   import org.apache.activemq.util.DataByteArrayOutputStream;
   29   import org.apache.activemq.util.IOHelper;
   30   import org.apache.activemq.util.LRUCache;
   31   import org.apache.commons.logging.Log;
   32   import org.apache.commons.logging.LogFactory;
   33   
   34   /**
   35    * BTree implementation
   36    * 
   37    * @version $Revision: 1.1.1.1 $
   38    */
   39   public class TreeIndex implements Index {
   40   
   41       private static final String NAME_PREFIX = "tree-index-";
   42       private static final int DEFAULT_PAGE_SIZE;
   43       private static final int DEFAULT_KEY_SIZE;
   44       private static final Log LOG = LogFactory.getLog(TreeIndex.class);
   45       private final String name;
   46       private File directory;
   47       private File file;
   48       private RandomAccessFile indexFile;
   49       private IndexManager indexManager;
   50       private int pageSize = DEFAULT_PAGE_SIZE;
   51       private int keySize = DEFAULT_KEY_SIZE;
   52       private int keysPerPage = pageSize / keySize;
   53       private TreePage root;
   54       private LRUCache<Long, TreePage> pageCache;
   55       private DataByteArrayInputStream dataIn;
   56       private DataByteArrayOutputStream dataOut;
   57       private byte[] readBuffer;
   58       private Marshaller keyMarshaller;
   59       private long length;
   60       private TreePage firstFree;
   61       private TreePage lastFree;
   62       private AtomicBoolean loaded = new AtomicBoolean();
   63       private boolean enablePageCaching = true;
   64       private int pageCacheSize = 10;
   65   
   66       /**
   67        * Constructor
   68        * 
   69        * @param directory
   70        * @param name
   71        * @param indexManager
   72        * @throws IOException
   73        */
   74       public TreeIndex(File directory, String name, IndexManager indexManager) throws IOException {
   75           this.directory = directory;
   76           this.name = name;
   77           this.indexManager = indexManager;
   78           pageCache = new LRUCache<Long, TreePage>(pageCacheSize, pageCacheSize, 0.75f, true);
   79           openIndexFile();
   80       }
   81   
   82       /**
   83        * Set the marshaller for key objects
   84        * 
   85        * @param marshaller
   86        */
   87       public void setKeyMarshaller(Marshaller marshaller) {
   88           this.keyMarshaller = marshaller;
   89       }
   90   
   91       /**
   92        * @return the keySize
   93        */
   94       public int getKeySize() {
   95           return this.keySize;
   96       }
   97   
   98       /**
   99        * @param keySize the keySize to set
  100        */
  101       public void setKeySize(int keySize) {
  102           this.keySize = keySize;
  103           if (loaded.get()) {
  104               throw new RuntimeException("Pages already loaded - can't reset key size");
  105           }
  106       }
  107   
  108       /**
  109        * @return the pageSize
  110        */
  111       public int getPageSize() {
  112           return this.pageSize;
  113       }
  114   
  115       /**
  116        * @param pageSize the pageSize to set
  117        */
  118       public void setPageSize(int pageSize) {
  119           if (loaded.get() && pageSize != this.pageSize) {
  120               throw new RuntimeException("Pages already loaded - can't reset page size");
  121           }
  122           this.pageSize = pageSize;
  123       }
  124   
  125       public boolean isTransient() {
  126           return false;
  127       }
  128   
  129       /**
  130        * @return the enablePageCaching
  131        */
  132       public boolean isEnablePageCaching() {
  133           return this.enablePageCaching;
  134       }
  135   
  136       /**
  137        * @param enablePageCaching the enablePageCaching to set
  138        */
  139       public void setEnablePageCaching(boolean enablePageCaching) {
  140           this.enablePageCaching = enablePageCaching;
  141       }
  142   
  143       /**
  144        * @return the pageCacheSize
  145        */
  146       public int getPageCacheSize() {
  147           return this.pageCacheSize;
  148       }
  149   
  150       /**
  151        * @param pageCacheSize the pageCacheSize to set
  152        */
  153       public void setPageCacheSize(int pageCacheSize) {
  154           this.pageCacheSize = pageCacheSize;
  155           pageCache.setMaxCacheSize(pageCacheSize);
  156       }
  157   
  158       public void load() {
  159           if (loaded.compareAndSet(false, true)) {
  160               keysPerPage = pageSize / keySize;
  161               dataIn = new DataByteArrayInputStream();
  162               dataOut = new DataByteArrayOutputStream(pageSize);
  163               readBuffer = new byte[pageSize];
  164               try {
  165                   openIndexFile();
  166                   long offset = 0;
  167                   while ((offset + pageSize) <= indexFile.length()) {
  168                       indexFile.seek(offset);
  169                       indexFile.readFully(readBuffer, 0, TreePage.PAGE_HEADER_SIZE);
  170                       dataIn.restart(readBuffer);
  171                       TreePage page = new TreePage(keysPerPage);
  172                       page.setTree(this);
  173                       page.setId(offset);
  174                       page.readHeader(dataIn);
  175                       if (!page.isActive()) {
  176                           if (lastFree != null) {
  177                               lastFree.setNextFreePageId(offset);
  178                               indexFile.seek(lastFree.getId());
  179                               dataOut.reset();
  180                               lastFree.writeHeader(dataOut);
  181                               indexFile.write(dataOut.getData(), 0, TreePage.PAGE_HEADER_SIZE);
  182                               lastFree = page;
  183                           } else {
  184                               lastFree = page;
  185                               firstFree = page;
  186                           }
  187                       } else if (root == null && page.isRoot()) {
  188                           root = getFullPage(offset);
  189                       }
  190                       offset += pageSize;
  191                   }
  192                   length = offset;
  193                   if (root == null) {
  194                       root = createRoot();
  195                   }
  196               } catch (IOException e) {
  197                   LOG.error("Failed to load index ", e);
  198                   throw new RuntimeException(e);
  199               }
  200           }
  201       }
  202   
  203       public void unload() throws IOException {
  204           if (loaded.compareAndSet(true, false)) {
  205               if (indexFile != null) {
  206                   indexFile.close();
  207                   indexFile = null;
  208                   pageCache.clear();
  209                   root = null;
  210                   firstFree = null;
  211                   lastFree = null;
  212               }
  213           }
  214       }
  215   
  216       public void store(Object key, StoreEntry value) throws IOException {
  217           TreeEntry entry = new TreeEntry();
  218           entry.setKey((Comparable)key);
  219           entry.setIndexOffset(value.getOffset());
  220           root.put(entry);
  221       }
  222   
  223       public StoreEntry get(Object key) throws IOException {
  224           TreeEntry entry = new TreeEntry();
  225           entry.setKey((Comparable)key);
  226           TreeEntry result = root.find(entry);
  227           return result != null ? indexManager.getIndex(result.getIndexOffset()) : null;
  228       }
  229   
  230       public StoreEntry remove(Object key) throws IOException {
  231           TreeEntry entry = new TreeEntry();
  232           entry.setKey((Comparable)key);
  233           TreeEntry result = root.remove(entry);
  234           return result != null ? indexManager.getIndex(result.getIndexOffset()) : null;
  235       }
  236   
  237       public boolean containsKey(Object key) throws IOException {
  238           TreeEntry entry = new TreeEntry();
  239           entry.setKey((Comparable)key);
  240           return root.find(entry) != null;
  241       }
  242   
  243       public void clear() throws IOException {
  244           unload();
  245           delete();
  246           openIndexFile();
  247           load();
  248       }
  249   
  250       public void delete() throws IOException {
  251           unload();
  252           if (file.exists()) {
  253               boolean result = file.delete();
  254           }
  255           length = 0;
  256       }
  257   
  258       /**
  259        * @return the root
  260        */
  261       TreePage getRoot() {
  262           return this.root;
  263       }
  264   
  265       TreePage lookupPage(long pageId) throws IOException {
  266           TreePage result = null;
  267           if (pageId >= 0) {
  268               if (root != null && root.getId() == pageId) {
  269                   result = root;
  270               } else {
  271                   result = getFromCache(pageId);
  272               }
  273               if (result == null) {
  274                   result = getFullPage(pageId);
  275                   if (result != null) {
  276                       if (result.isActive()) {
  277                           addToCache(result);
  278                       } else {
  279                           throw new IllegalStateException("Trying to access an inactive page: " + pageId + " root is " + root);
  280                       }
  281                   }
  282               }
  283           }
  284           return result;
  285       }
  286   
  287       TreePage createRoot() throws IOException {
  288           TreePage result = createPage(-1);
  289           root = result;
  290           return result;
  291       }
  292   
  293       TreePage createPage(long parentId) throws IOException {
  294           TreePage result = getNextFreePage();
  295           if (result == null) {
  296               // allocate one
  297               result = new TreePage(keysPerPage);
  298               result.setId(length);
  299               result.setTree(this);
  300               result.setParentId(parentId);
  301               writePage(result);
  302               length += pageSize;
  303               indexFile.seek(length);
  304               indexFile.write(TreeEntry.NOT_SET);
  305           }
  306           addToCache(result);
  307           return result;
  308       }
  309   
  310       void releasePage(TreePage page) throws IOException {
  311           removeFromCache(page);
  312           page.reset();
  313           page.setActive(false);
  314           if (lastFree == null) {
  315               firstFree = page;
  316               lastFree = page;
  317           } else {
  318               lastFree.setNextFreePageId(page.getId());
  319               writePage(lastFree);
  320           }
  321           writePage(page);
  322       }
  323   
  324       private TreePage getNextFreePage() throws IOException {
  325           TreePage result = null;
  326           if (firstFree != null) {
  327               if (firstFree.equals(lastFree)) {
  328                   result = firstFree;
  329                   firstFree = null;
  330                   lastFree = null;
  331               } else {
  332                   result = firstFree;
  333                   firstFree = getPage(firstFree.getNextFreePageId());
  334                   if (firstFree == null) {
  335                       lastFree = null;
  336                   }
  337               }
  338               result.setActive(true);
  339               result.reset();
  340               result.saveHeader();
  341           }
  342           return result;
  343       }
  344   
  345       void writeFullPage(TreePage page) throws IOException {
  346           dataOut.reset();
  347           page.write(keyMarshaller, dataOut);
  348           if (dataOut.size() > pageSize) {
  349               throw new IOException("Page Size overflow: pageSize is " + pageSize + " trying to write " + dataOut.size());
  350           }
  351           indexFile.seek(page.getId());
  352           indexFile.write(dataOut.getData(), 0, dataOut.size());
  353       }
  354   
  355       void writePage(TreePage page) throws IOException {
  356           dataOut.reset();
  357           page.writeHeader(dataOut);
  358           indexFile.seek(page.getId());
  359           indexFile.write(dataOut.getData(), 0, TreePage.PAGE_HEADER_SIZE);
  360       }
  361   
  362       TreePage getFullPage(long id) throws IOException {
  363           indexFile.seek(id);
  364           indexFile.readFully(readBuffer, 0, pageSize);
  365           dataIn.restart(readBuffer);
  366           TreePage page = new TreePage(keysPerPage);
  367           page.setId(id);
  368           page.setTree(this);
  369           page.read(keyMarshaller, dataIn);
  370           return page;
  371       }
  372   
  373       TreePage getPage(long id) throws IOException {
  374           indexFile.seek(id);
  375           indexFile.readFully(readBuffer, 0, TreePage.PAGE_HEADER_SIZE);
  376           dataIn.restart(readBuffer);
  377           TreePage page = new TreePage(keysPerPage);
  378           page.setId(id);
  379           page.setTree(this);
  380           page.readHeader(dataIn);
  381           return page;
  382       }
  383   
  384       private TreePage getFromCache(long pageId) {
  385           TreePage result = null;
  386           if (enablePageCaching) {
  387               result = pageCache.get(pageId);
  388           }
  389           return result;
  390       }
  391   
  392       private void addToCache(TreePage page) {
  393           if (enablePageCaching) {
  394               pageCache.put(page.getId(), page);
  395           }
  396       }
  397   
  398       private void removeFromCache(TreePage page) {
  399           if (enablePageCaching) {
  400               pageCache.remove(page.getId());
  401           }
  402       }
  403   
  404       protected void openIndexFile() throws IOException {
  405           if (indexFile == null) {
  406               file = new File(directory, NAME_PREFIX + IOHelper.toFileSystemSafeName(name));
  407               IOHelper.mkdirs(file.getParentFile());
  408               indexFile = new RandomAccessFile(file, "rw");
  409           }
  410       }
  411   
  412       static {
  413           DEFAULT_PAGE_SIZE = Integer.parseInt(System.getProperty("defaultPageSize", "16384"));
  414           DEFAULT_KEY_SIZE = Integer.parseInt(System.getProperty("defaultKeySize", "96"));
  415       }
  416   
  417       public int getSize() {
  418           return 0;
  419       }
  420   }

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