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 */
017package org.apache.activemq.store.kahadb.disk.index;
018
019import java.io.IOException;
020import java.io.OutputStream;
021import java.io.PrintWriter;
022import java.util.Iterator;
023import java.util.Map;
024import java.util.concurrent.atomic.AtomicBoolean;
025
026import org.slf4j.Logger;
027import org.slf4j.LoggerFactory;
028import org.apache.activemq.store.kahadb.disk.page.Page;
029import org.apache.activemq.store.kahadb.disk.page.PageFile;
030import org.apache.activemq.store.kahadb.disk.page.Transaction;
031import 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$
059 */
060public 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$
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, null);
233    }
234
235    synchronized public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key initialKey, Key maxKey) throws IOException {
236        return getRoot(tx).iterator(tx, initialKey, maxKey);
237    }
238    
239    synchronized public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException {
240        getRoot(tx).visit(tx, visitor);
241    }
242
243    synchronized public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException {
244        return getRoot(tx).getFirst(tx);
245    }
246
247    synchronized public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException {
248        return getRoot(tx).getLast(tx);
249    }
250
251    ///////////////////////////////////////////////////////////////////
252    // Internal implementation methods
253    ///////////////////////////////////////////////////////////////////
254    
255    private void assertLoaded() throws IllegalStateException {
256        if( !loaded.get() ) {
257            throw new IllegalStateException("The BTreeIndex is not loaded");
258        }
259    }
260
261    ///////////////////////////////////////////////////////////////////
262    // Internal methods made accessible to BTreeNode
263    ///////////////////////////////////////////////////////////////////
264
265    BTreeNode<Key,Value> loadNode(Transaction tx, long pageId, BTreeNode<Key,Value> parent) throws IOException {
266        Page<BTreeNode<Key,Value>> page = tx.load(pageId, marshaller);
267        BTreeNode<Key, Value> node = page.get();
268        node.setPage(page);
269        node.setParent(parent);
270        return node;
271    }
272
273    BTreeNode<Key,Value> createNode(Transaction tx, BTreeNode<Key,Value> parent) throws IOException {
274        Page<BTreeNode<Key,Value>> p = tx.allocate();
275        BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(this);
276        node.setPage(p);
277        node.setParent(parent);
278        node.setEmpty();
279        p.set(node);
280        return node;
281    }
282
283    BTreeNode<Key,Value> createNode(Page<BTreeNode<Key,Value>> p, BTreeNode<Key,Value> parent) throws IOException {
284        BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(this);
285        node.setPage(p);
286        node.setParent(parent);
287        node.setEmpty();
288        p.set(node);
289        return node;
290    }
291    
292    void storeNode(Transaction tx, BTreeNode<Key,Value> node, boolean overflow) throws IOException {
293        tx.store(node.getPage(), marshaller, overflow);
294    }
295        
296   
297    ///////////////////////////////////////////////////////////////////
298    // Property Accessors
299    ///////////////////////////////////////////////////////////////////
300
301    public PageFile getPageFile() {
302        return pageFile;
303    }
304    public long getPageId() {
305        return pageId;
306    }
307
308    public Marshaller<Key> getKeyMarshaller() {
309        return keyMarshaller;
310    }
311    public void setKeyMarshaller(Marshaller<Key> keyMarshaller) {
312        this.keyMarshaller = keyMarshaller;
313    }
314
315    public Marshaller<Value> getValueMarshaller() {
316        return valueMarshaller;
317    }
318    public void setValueMarshaller(Marshaller<Value> valueMarshaller) {
319        this.valueMarshaller = valueMarshaller;
320    }
321
322    public Prefixer<Key> getPrefixer() {
323        return prefixer;
324    }
325    public void setPrefixer(Prefixer<Key> prefixer) {
326        this.prefixer = prefixer;
327    }
328
329    public void setPageFile(PageFile pageFile) {
330        this.pageFile = pageFile;
331    }
332
333    public void setPageId(long pageId) {
334        this.pageId = pageId;
335    }
336
337}