ozone core API

org.ozoneDB.core.storage.gammaStore
Class LongLoc

java.lang.Object
  extended byorg.ozoneDB.core.storage.gammaStore.LongLoc
All Implemented Interfaces:
java.io.Serializable

public class LongLoc
extends java.lang.Object
implements java.io.Serializable

Provides a primitive mapping-like meganism in which there is only a key (a primitive long in this case). This key can be put in and retrieved by getKey(long) and putKey(long). 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.

Extending classes should extend move(int, int)

This implementation is very fast when every value passed to putKey(int) 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.

Version:
$Id$
Author:
Leo Mekenkamp (mind the anti sp@m)
See Also:
Serialized Form

Field Summary
private  int capacity
           
private  int handleToLast
           
private  int[] inUse
           
protected  long[] keys
           
private  int size
           
 
Constructor Summary
LongLoc(int capacity, float relSlack)
           
LongLoc(int capacity, int slack)
           
 
Method Summary
private  void compress()
          Moves all keys to remove unused (deleted) slots.
 long getKey(int pos)
          Returns the key found at the specified location.
 int getKeyPos(long key)
          Returns a handle to the given value.
 int getKeyPosOrNearestGreater(long key)
          Returns a handle to the given key, or, if that key does not exist, to the smallest key larger than specified key.
 int getKeyPosOrNearestSmaller(long key)
          Returns a handle to the given key, or, if that key does not exist, to the largest key smaller than specified key.
private  boolean isInUse(int handle)
          Returns true iff the given handle is in use
protected  void move(int handleFrom, int handleTo)
           
 int next(int handle)
          Returns the handle to the key that is the smallest of all larger keys.
 int putKey(long key)
          Inserts (or overwrites) a key and returns a handle to it.
 int removeKey(long key)
          Returns a handle to the given value and removes that key.
private  int search(long key)
          Searches for the given value.
private  int search(long key, int low, int high)
          note: searching beyond high > index is NOT supported and may yield strange results.
private  void setInUse(int handle, boolean inUse)
           
 int size()
          Returns the number of keys in use.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

keys

protected long[] keys

inUse

private int[] inUse

capacity

private int capacity

size

private int size

handleToLast

private int handleToLast
Constructor Detail

LongLoc

public LongLoc(int capacity,
               int slack)

LongLoc

public LongLoc(int capacity,
               float relSlack)
Method Detail

getKeyPos

public int getKeyPos(long key)
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 putKey(long) or compress().


getKey

public long getKey(int pos)
Returns the key found at the specified location.

Parameters:
pos - position to get the key from
Returns:
key at that location
Throws:
java.lang.IllegalArgumentException - the specified position is not in use

getKeyPosOrNearestGreater

public int getKeyPosOrNearestGreater(long key)
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 putKey(long) or compress().


getKeyPosOrNearestSmaller

public int getKeyPosOrNearestSmaller(long key)
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 putKey(long) or compress().


removeKey

public int removeKey(long key)
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 putKey(long) or compress(). The returned handle can also never be retrieved again.


putKey

public int putKey(long key)

Inserts (or overwrites) a key and returns a handle to it. The returned handle is only valid until the next call to putKey(long) or compress().

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)


next

public int next(int handle)
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


isInUse

private boolean isInUse(int handle)
Returns true iff the given handle is in use


setInUse

private void setInUse(int handle,
                      boolean inUse)

search

private int search(long key)
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.


search

private int search(long key,
                   int low,
                   int high)
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!


compress

private void compress()
Moves all keys to remove unused (deleted) slots.


move

protected void move(int handleFrom,
                    int handleTo)

toString

public java.lang.String toString()

size

public int size()
Returns the number of keys in use.


ozone core API

Copyright (C) The Ozone Database Project - www.ozone-db.org. All rights reserved.