001    /**
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.activemq.store.kahadb.disk.index;
018    
019    import java.io.IOException;
020    import java.io.OutputStream;
021    import java.io.PrintWriter;
022    import java.util.Iterator;
023    import java.util.Map;
024    import java.util.concurrent.atomic.AtomicBoolean;
025    
026    import org.slf4j.Logger;
027    import org.slf4j.LoggerFactory;
028    import org.apache.activemq.store.kahadb.disk.page.Page;
029    import org.apache.activemq.store.kahadb.disk.page.PageFile;
030    import org.apache.activemq.store.kahadb.disk.page.Transaction;
031    import org.apache.activemq.store.kahadb.disk.util.Marshaller;
032    
033    /**
034     * BTreeIndex represents a Variable Magnitude B+Tree in a Page File.
035     * A BTree is a bit flexible in that it can be used for set or
036     * map-based indexing.  Leaf nodes are linked together for faster
037     * iteration of the values. 
038     *
039     * <br>
040     * The Variable Magnitude attribute means that the BTree attempts
041     * to store as many values and pointers on one page as is possible.
042     * 
043     * <br>
044     * The implementation can optionally a be Simple-Prefix B+Tree.
045     * 
046     * <br>
047     * For those who don't know how a Simple-Prefix B+Tree works, the primary
048     * distinction is that instead of promoting actual keys to branch pages,
049     * when leaves are split, a shortest-possible separator is generated at
050     * the pivot.  That separator is what is promoted to the parent branch
051     * (and continuing up the list).  As a result, actual keys and pointers
052     * can only be found at the leaf level.  This also affords the index the
053     * ability to ignore costly merging and redistribution of pages when
054     * deletions occur.  Deletions only affect leaf pages in this
055     * implementation, and so it is entirely possible for a leaf page to be
056     * completely empty after all of its keys have been removed.
057     *
058     * , $Date: 2012-11-07 16:00:07 +0000 (Wed, 07 Nov 2012) $
059     */
060    public class BTreeIndex<Key,Value> implements Index<Key,Value> {
061    
062        private static final Logger LOG = LoggerFactory.getLogger(BTreeIndex.class);
063    
064        /**
065         * Interface used to determine the simple prefix of two keys.
066         *
067         * , $Date: 2012-11-07 16:00:07 +0000 (Wed, 07 Nov 2012) $
068         */
069        static public interface Prefixer<Key> {
070            
071            /**
072             * This methods should return shortest prefix of value2 where the following still holds:<br/>
073             * value1 <= prefix <= value2.<br/><br/>
074             * 
075             * When this method is called, the following is guaranteed:<br/>
076             * value1 < value2<br/><br/>
077             * 
078             * 
079             * @param value1
080             * @param value2
081             * @return
082             */
083            public Key getSimplePrefix(Key value1, Key value2);
084        }
085        
086        /**
087         * StringPrefixer is a Prefixer implementation that works on strings.
088         */
089        static public class StringPrefixer implements Prefixer<String> {
090            
091            /**
092             * Example:
093             * If value1 is "Hello World"
094             * and value 2 is "Help Me"
095             * then the result will be: "Help"
096             * 
097             * @see  Prefixer#getSimplePrefix
098             */
099            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    }