longloc.java

Java的面向对象数据库系统的源代码

// You can redistribute this software and/or modify it under the terms of
// the Ozone Core License version 1 published by ozone-db.org.
//
// Copyright (C) 2003-@year@, Leo Mekenkamp. All rights reserved.
//
// $Id$

package org.ozoneDB.core.storage.gammaStore;

import java.io.Serializable;

/**
 * <p>Provides a primitive mapping-like meganism in which there is only a key (a
 * primitive <code>long</code> in this case). This key can be put in and
 * retrieved by <code>getKey(long)</code> and <code>putKey(long)</code>. Both
 * methods return a handle, which can be used as a handle or magic cookie, to
 * find the key. Implementing classes can and should provide their own get and
 * put methods for each and every object or primitive that is mapped to the key.
 * </p>
 * <p>Extending classes should extend <code>move(int, int)</code></p>
 *
 * <p>This implementation is very fast when every value passed to <code>putKey(int)</code>
 * is bigger than all previous passed values (O(1)). If not, it is quite slow
 * (max O(size)). Because this class is used to store object ids and cluster ids
 * this means the greatest performance benefits occur in normal 'everyday' use.
 * Only when the database or OS has crashed (powerfailure) and the index has to
 * be rebuild does the speed disadvantage make itself known.</p>
 *
 * @author <a href="mailto:leoATmekenkampD0Tcom">Leo Mekenkamp (mind the anti sp@m)</a>
 * @version $Id$
 */
public class LongLoc implements Serializable {
    
    protected long[] keys;
    private int[] inUse;
    private int capacity;
    private int size;
    private int handleToLast;

    public LongLoc(int capacity, int slack) {
        this.capacity = capacity;
        keys = new long[capacity + slack];
        int inUseSize = keys.length / 32;
        if (keys.length % 32 != 0) {
            inUseSize++;
        }
        inUse = new int[inUseSize];
        handleToLast = -1;
    }
    
    public LongLoc(int capacity, float relSlack) {
        this(capacity, (int) (relSlack * capacity) > 0 ? (int) (relSlack * capacity) : 1);
    }

    /**
     * Returns a handle to the given value. If there is no such value, then
     * the return value is negative. The returned handle is only valid until
     * the next call to <code>putKey(long)</code> or <code>compress()</code>.
     */
    public int getKeyPos(long key) {
        int result = search(key);
        if (!isInUse(result) || key != keys[result]) {
            result = -1;
        }
        return result;
    }
    
    /** Returns the key found at the specified location.
     * @param pos position to get the key from
     * @return key at that location
     * @throws IllegalArgumentException the specified position is not in use
     */
    public long getKey(int pos) {
        if (!isInUse(pos)) {
            throw new IllegalArgumentException("position not in use");
        }
        return keys[pos];
    }
    
    /**
     * Returns a handle to the given key, or, if that key does not exist, to
     * the smallest key larger than specified key. If there is no such value,
     * then the return value is negative. The returned handle is only valid
     * until the next call to <code>putKey(long)</code> or <code>compress()</code>.
     */
    public int getKeyPosOrNearestGreater(long key) {
        int result = -1;
        for(int handle = search(key); handle <= handleToLast; handle++) {
            if (isInUse(handle) && keys[handle] >= key) {
                result = handle;
                break;
            }
        }
        return result;
    }
    
    /**
     * Returns a handle to the given key, or, if that key does not exist, to
     * the largest key smaller than specified key. If there is no such value,
     * then the return value is negative. The returned handle is only valid
     * until the next call to <code>putKey(long)</code> or <code>compress()</code>.
     */
    public int getKeyPosOrNearestSmaller(long key) {
        int result = -1;
        for(int handle = search(key); handle >= 0; handle--) {
            if (isInUse(handle) && keys[handle] <= key) {
                result = handle;
                break;
            }
        }
        return result;
    }
    
    /**
     * Returns a handle to the given value and removes that key. If there is no
     * such key, then the return value is negative. The returned handle is only
     * valid until the next call to <code>putKey(long)</code> or <code>compress()</code>.
     * The returned handle can also never be retrieved again.
     */
    public int removeKey(long key) {
        int result = getKeyPos(key);
        if (result < 0) {
            throw new IllegalArgumentException("key not found");
        }
        setInUse(result, false);
        size--;
        return result;
    }
    
    /**
     * <p>Inserts (or overwrites) a key and returns a handle to it. The returned
     * handle is only valid until the next call to <code>putKey(long)</code> or
     * <code>compress()</code>.</p>
     * <p>This method is highly optimized for keys that are bigger than any
     * other key in this instance; performance is then O(1). When this is not
     * the case, thus the keys are inserted in random fashion (2,7,4,8,9,1 
     * instead of 1,2,4,7,8,9) performance can be up to O(size)</p>
     */
    public int putKey(long key) {
        if (handleToLast == -1 || keys[handleToLast] < key) {
            if (handleToLast == keys.length - 1) {
                compress();
            }
            // since the key is bigger than all others, append to end of array
            if (size >= capacity) {
                throw new IndexOutOfBoundsException("cannot grow any larger");
            }
            handleToLast++;
            keys[handleToLast] = key;
            setInUse(handleToLast, true);
            size++;
            return handleToLast;
        }

        // Ouch, we got a key that is not the largest in this instance; we have
        // to do a (costly) insert. Must do a compress to make sure that keys
        // do not appear twice or more times (one time as inUse and possible 
        // others not inUse...
        compress();
        int result = getKeyPosOrNearestGreater(key);
        if (result >= 0) {
            if (isInUse(result) || keys[result] == key) {
                return result;
            }
        } else {
            result = handleToLast;
        }
        
        if (size >= capacity) {
            throw new IndexOutOfBoundsException("cannot grow any larger");
        }
        
        for (int i = keys.length - 2; i >= result; i--) {
            if (isInUse(i)) {
                // note that handle keys.length - 1 is never in use here, because
                // of the compress() at the start of this method
                move(i, i + 1);
                if (handleToLast <= i) {
                    handleToLast = i + 1;
                }
            }
        }
        keys[result] = key;
        setInUse(result, true);
        size++;
        return result;
    }
    
    /**
     * Returns the handle to the key that is the smallest of all larger keys.
     * Returns < 0 if there is no such key. Note that if handle <0 then the
     * first handle in use is returned (which may of course be < 0 if there is
     * no key in this instance
     */
    public int next(int handle) {
        if (handle >= 0 && !isInUse(handle)) {
            throw new IllegalArgumentException("handle is not in use");
        }
        handle++;
        int result;
        for(result = -1; result < 0 && handle <= handleToLast; handle++) {
            if (isInUse(handle)) {
                result = handle;
            }
        }
        return result;
    }
    
    /**
     * Returns true iff the given handle is in use
     */
    private boolean isInUse(int handle) {
        int pos = handle / 32;
        int mask = 1 << (handle % 32);
        return (inUse[pos] & mask ) != 0;
    }
    
    private void setInUse(int handle, boolean inUse) {
        int pos = handle / 32;
        int mask = 1 << (handle % 32);
        if (inUse) {
            this.inUse[pos] |= mask;
        } else {
            this.inUse[pos] &= ~mask;
        }
    }
    
    /**
     * Searches for the given value. If the value could not be found then one of
     * the handles of the nearest value is returned. Note that the returned
     * handle may not be in use.
     */
    private int search(long key) {
        return (handleToLast < 0) ? 0 : search(key, 0, handleToLast);
    }
    
    /**
     * note: searching beyond high > index is NOT supported and may yield
     * strange results. Search may return a handle to either 1) the specified
     * key, or if that key does not exist: 2) the greatest key smaller
     * than the specified key; or: 3) the smallest key greater than
     * the specified key. Returned handle may be invalid!
     */
    private int search(long key, int low, int high) {
        if (low > high) {
            throw new IllegalArgumentException("low should be <= high; low == " + low + ", high == " + high + ", key == " + key + ", handleToLast == " + handleToLast);
        }
        for(;;) {
            int result = (low + high) / 2;
            if (low >= high || keys[result] == key) {
                return result;
            }
            if (key < keys[result]) {
                high = result - 1;
            } else {
                low = result + 1;
            }
        }
    }
    
    /**
     * Moves all keys to remove unused (deleted) slots.
     */
    private void compress() {
        handleToLast = -1;
        for(int i = 0; i < keys.length; i++) {
            if (isInUse(i)) {
                handleToLast++;
                if (i > handleToLast) {
                    move(i, handleToLast);
                }
            } else {
                // Having a lot of 0s in a row makes for better compression when this
                // instance is serialized and put through a compressing stream.
                keys[i] = 0;
            }
        }
    }
    
    protected void move(int handleFrom, int handleTo) {
        if (!isInUse(handleFrom) || isInUse(handleTo)) {
            throw new IllegalArgumentException("handleFrom must be in use and handleTo must not");
        }
        keys[handleTo] = keys[handleFrom];
        // Having a lot of 0s in a row makes for better compression when this
        // instance is serialized and put through a compressing stream.
        keys[handleFrom] = 0;
        setInUse(handleFrom, false);
        setInUse(handleTo, true);
    }
    
    public String toString() {
        StringBuffer result = new StringBuffer("[handleToLast=");
        result.append(handleToLast).append(";");
        for (int i = 0; i < keys.length; i++) {
            result.append(keys[i]);
            if (!isInUse(i)) {
                result.append("D");
            }
            result.append(",");
        }
        return result.toString();
    }
    
    /**
     * Returns the number of keys in use.
     */
    public int size() {
        return size;
    }
        
// DEBUG code only following
    
//    public static void main(String[] args) {
//        int capacity = 6;
//        int slack = 3;
//        LongLoc l = new LongLoc(capacity, slack);
//        System.out.println(l);
//        for (long i = 0; i < capacity; i++) {
//            int handle = l.putKey(i * 3);
//            System.out.println(l);
//        }
//        l.removeKey(6L);
//        System.out.println(l);
//        System.out.println("find eq or gr 16L: " + l.getKeyOrNearestGreater(16L));
//        System.out.println("find eq or gr 15L: " + l.getKeyOrNearestGreater(15L));
//        System.out.println("find eq or gr 14L: " + l.getKeyOrNearestGreater(14L));
//        System.out.println("find eq or gr 9L: " + l.getKeyOrNearestGreater(9L));
//        System.out.println("find eq or gr 8L: " + l.getKeyOrNearestGreater(8L));
//        System.out.println("find eq or gr 7L: " + l.getKeyOrNearestGreater(7L));
//        System.out.println("find eq or gr 6L: " + l.getKeyOrNearestGreater(6L));
//        System.out.println("find eq or gr 5L: " + l.getKeyOrNearestGreater(5L));
//        System.out.println("find eq or gr 0L: " + l.getKeyOrNearestGreater(0L));
//        System.out.println("find eq or sm 16L: " + l.getKeyOrNearestSmaller(16L));
//        System.out.println("find eq or sm 15L: " + l.getKeyOrNearestSmaller(15L));
//        System.out.println("find eq or sm 14L: " + l.getKeyOrNearestSmaller(14L));
//        System.out.println("find eq or sm 9L: " + l.getKeyOrNearestSmaller(9L));
//        System.out.println("find eq or sm 8L: " + l.getKeyOrNearestSmaller(8L));
//        System.out.println("find eq or sm 7L: " + l.getKeyOrNearestSmaller(7L));
//        System.out.println("find eq or sm 6L: " + l.getKeyOrNearestSmaller(6L));
//        System.out.println("find eq or sm 5L: " + l.getKeyOrNearestSmaller(5L));
//        System.out.println("find eq or sm 0L: " + l.getKeyOrNearestSmaller(0L));
//        l.removeKey(0L);
//        l.removeKey(3L);
//        l.removeKey(12L);
//        System.out.println(l);
//        l.putKey(10L);
//        System.out.println(l);
//        l.putKey(4L);
//        System.out.println(l);
//        l.putKey(6L);
//        System.out.println(l);
//        System.out.println("find 10L: " + l.getKeyOrNearestGreater(10L));
//        l.putKey(5L);
//        System.out.println(l);
//    }
}