de.bsvrz.ars.ars.persistence.index
Class ATimeMonotoneIndex

java.lang.Object
  extended by de.bsvrz.ars.ars.persistence.index.ATimeMonotoneIndex
Direct Known Subclasses:
DIdxATimeMonotoneIndex

public class ATimeMonotoneIndex
extends Object

Diese Klasse implementiert einen monoton steigenden Index. Jeder Eintrag des Index besteht aus Datenindex-Minimum, Datenindex-Maximum, Archivzeit-Minimum, Archivzeit-Maximum, Datenzeit-Minimum, Datenzeit-Maximum und der Container-ID. In dieser Klasse ist gefordert, dass die Archivzeit monoton und die ContainerID streng monoton ueber alle Eintraege hinweg steigend sind. Datenindex und Datenzeit duerfen Rueckspruenge aufweisen (benoetigt fuer nachgeforderte Datensaetze). Daher kann diese Klasse nur nach Archivzeit suchen.

Zudem muss in jedem Eintrag das Maximum groesser oder gleich dem Minimum sein.

Wenn die Zahl der Einträge die Pufferkapazität im Speicher übersteigt, werden die Einträge in die Indexdatei geschrieben. Je größer die Pufferkapazität im Speicher, umso schneller ist die Suche, weil keine Plattenzugriffe notwendig sind. Die Suche nach ContainerIDs ist als Binärsuche implementiert, die automatisch im Speicher und in der Datei sucht.

Author:
beck et al. projects GmbH, Phil Schrettenbrunner, Alexander Schmidt

Nested Class Summary
protected static class ATimeMonotoneIndex.IndexStartmode
           
static class ATimeMonotoneIndex.Key
           
 
Field Summary
static ATimeMonotoneIndex.IndexStartmode APPEND_REUSE_LAST
           
protected static ATimeMonotoneIndex.Key AT
           
private  byte[] byteArray
           
protected static ATimeMonotoneIndex.Key DI
           
protected static ATimeMonotoneIndex.Key DT
           
static int ENTRY_LEN
           
static ATimeMonotoneIndex.IndexStartmode ERASE_OLD
           
static String IDX_FILENAME
          Der Dateiname, unter dem alle Indices dieser Art gespeichert werden (der Speicherort wird später bestimmt).
private  boolean ignoreLastFileEntry
           
private static boolean MAX
           
private static boolean MIN
           
static int NO_VALUE
           
private  boolean noActualEntry
           
private  int rbFstEnt
           
private  int rbFstUnsaved
           
private  int rbLstEnt
           
 
Constructor Summary
ATimeMonotoneIndex(int size)
          Erzeugt einen neuen monoton steigenden Index.
ATimeMonotoneIndex(int size, String basePath, ATimeMonotoneIndex.IndexStartmode startmode)
          Erzeugt einen neuen monoton steigenden Index.
 
Method Summary
 void add(String basePath, long dIMin, long dIMax, long aTMin, long aTMax, long dTMin, long dTMax, long cID)
          Fügt einen neuen Eintrag in den Buffer ein.
private  IndexResult binaryFileSearch(String basePath, byte[] tmpBuf, ATimeMonotoneIndex.Key cmpKey, long minKey, long maxKey)
          Führt eine binärSuche in der IndexDatei durch.
private  int binaryMemSearch(ATimeMonotoneIndex.Key cmpKey, long key)
          Sucht im Speicher nach dem ersten Eintrag, der auf den übergebenen Key passt.
 int capacity()
           
private  void checkFileLength(File indexFile, long fileLength)
           
 void checkForAdd(String basePath, long dIMin, long dIMax, long aTMin, long aTMax, long dTMin, long dTMax, long cID)
          Prüft, ob dem Index ein neuer Eintrag hinzugefügt werden könnte.
private  File checkIndexFile(String basePath)
          Prüft grundlegende Eigenschaften einer Indexdatei.
 void closeIndex(String basePath)
          Schließt den Index und speichert alle geänderten Daten auf Platte.
private  void closeRandomAccessFile(RandomAccessFile indexFile)
          Schließt die Indexdatei.
private  int compare(ATimeMonotoneIndex.Key cmpKey, int index, long key)
          Vergleicht den Eintrag an der gegebenen Position im Index mit dem gegebenen Schlüssel.
private  int countMatchingEntries(int startAt, int numOfEntries, ATimeMonotoneIndex.Key cmpKey, long key)
          Sucht den Puffer beginnend bei startAt in Richtung neuesten Eintrag nach Einträgen ab, die zum Vergleichswert passen.
 int entries()
           
private  void flush(String basePath)
          Speichert den aktuellen Buffer in die Datei.
 long getAbsoluteATMin(String basePath)
          Liefert den kleinsten Archivzeit-Minwert, der jemals in diesem Index gespeichert wird.
private  long getCID(int pos)
           
protected  IndexResult getContainerID(String basePath, byte[] temp, ATimeMonotoneIndex.Key cmpKey, long minKey, long maxKey)
          Liefert die IDs der Container, bei denen der gesuchte Key zwischen Anfang und Ende liegt.
 IndexResult getContainerIDByATime(String basePath, byte[] temp, long minATime, long maxATime)
          Liefert die IDs der Container, deren Archivzeitspanne sich mit der angegebenen Spanne ueberschneidet.
 long getCurrentATMax()
           
 long getCurrentATMin()
           
 long getCurrentCID()
           
 long getCurrentDIMax()
           
 long getCurrentDIMin()
           
 long getCurrentDTMax()
           
 long getCurrentDTMin()
           
private  long getEntry(ATimeMonotoneIndex.Key entrKey, boolean min, int pos)
          Liefert den Key1 (Min) an der angegebenen Indexposition.
protected  IndexResult getMinEntry(String basePath)
          Liefert den kleinsten Eintrag bei Sortierung nach Archivzeit.
private  int rb2pos(int rbPos)
          Rechnet eine absolute Position im Feld (gezählt in Einträgen) in eine Ringpuffer-Position um (0 = neuester Eintrag).
private  void readFile(String basePath)
          Füllt den Buffer so weit es geht mit den Daten aus der Indexdatei.
private  int readSearchChunk(RandomAccessFile raf, int chunkNo, byte[] buf, int bufSize)
          Liest einen Chunk zum Suchen in den Speicher.
 void resize(int newSize, String basePath)
          Verändert die Größe des RingBuffers.
private  void reuseIndexFromFile(String basePath)
          Füllt den Buffer so weit es geht mit den Daten aus der Indexdatei.
private  void setEntry(int pos, long dIMin, long dIMax, long aTMin, long aTMax, long dTMin, long dTMax, long cID)
          Setzt einen Eintrag an der angegebenen Indexposition.
private  int stepRB(int rbPos)
          Führt einen Schritt im Ringpuffer aus (und bricht dabei an der Feldgrenze um).
 String toString()
           
 void updateMax(long dIMax, long aTMax, long dTMax)
          Aktualisiert die Maximumwerte des aktuellsten Eintrages.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

APPEND_REUSE_LAST

public static final ATimeMonotoneIndex.IndexStartmode APPEND_REUSE_LAST

ERASE_OLD

public static final ATimeMonotoneIndex.IndexStartmode ERASE_OLD

NO_VALUE

public static final int NO_VALUE
See Also:
Constant Field Values

IDX_FILENAME

public static final String IDX_FILENAME
Der Dateiname, unter dem alle Indices dieser Art gespeichert werden (der Speicherort wird später bestimmt).

See Also:
Constant Field Values

DI

protected static final ATimeMonotoneIndex.Key DI

AT

protected static final ATimeMonotoneIndex.Key AT

DT

protected static final ATimeMonotoneIndex.Key DT

MIN

private static final boolean MIN
See Also:
Constant Field Values

MAX

private static final boolean MAX
See Also:
Constant Field Values

ENTRY_LEN

public static final int ENTRY_LEN
See Also:
Constant Field Values

byteArray

private byte[] byteArray

rbFstEnt

private int rbFstEnt

rbLstEnt

private int rbLstEnt

rbFstUnsaved

private int rbFstUnsaved

ignoreLastFileEntry

private boolean ignoreLastFileEntry

noActualEntry

private boolean noActualEntry
Constructor Detail

ATimeMonotoneIndex

public ATimeMonotoneIndex(int size,
                          String basePath,
                          ATimeMonotoneIndex.IndexStartmode startmode)
                   throws IndexException
Erzeugt einen neuen monoton steigenden Index.

Bei startmode==APPEND_REUSE_LAST wird der Ringpuffer mit den aktuellsten Daten aus einer vorhandenen Indexdate gefüllt. Zusätzlich wird der letzte Eintrag in der Indexdatei zum currentEntry. Damit kann ein Container fortgesetzt und der Key2 weiter aktualisiert werden.

Bei startmode==CREATE_NEW wird ein leerer Index erzeugt und die bisherige Indexdatei (sofern vorhanden) geloescht.

Parameters:
size - Größe des Buffers (Anzahl der Einträge)
basePath - Verzeichnis der Indexdatei
startmode - ATimeMonotoneIndex.IndexStartmode.ERASE_OLD: alte Indexdatei loeschen, ATimeMonotoneIndex.IndexStartmode.APPEND_REUSE_LAST: anfuegen, letzten Eintrag weiterverwenden
Throws:
IndexException

ATimeMonotoneIndex

public ATimeMonotoneIndex(int size)
Erzeugt einen neuen monoton steigenden Index. Neue Eintraege werden an eine bestehende Indexdatei angefuegt, wenn diese bereits existiert. Existiert keine Indexdatei, wird eine erzeugt. Initial werden keine Daten eingelesen; es findet kein Plattenzugriff statt.

Parameters:
size - Größe des Buffers (Anzahl der Einträge). Wird mindestens auf 1 gesetzt.
Method Detail

resize

public void resize(int newSize,
                   String basePath)
            throws IndexException
Verändert die Größe des RingBuffers. Beim Verkleinern werden nicht gespeicherte Einträge auf Platte geschrieben

Parameters:
newSize -
basePath -
Throws:
IndexException

reuseIndexFromFile

private void reuseIndexFromFile(String basePath)
                         throws IndexException,
                                CorruptIndexException
Füllt den Buffer so weit es geht mit den Daten aus der Indexdatei. Dabei wird nur der neuste Teil geladen, wenn die Datei mehr Daten hält als in den Buffer passen. Der letzte Eintrag wird weiterverwendet und deswegen aus der Indexdatei gelöscht.

Parameters:
basePath - Verzeichnis der Indexdatei
Throws:
IndexException - Wenn es Probleme mit dem Einlesen der Datei gibt.
CorruptIndexException - Wenn die Eingelesene Indexdatei beschädigt ist.

readFile

private void readFile(String basePath)
               throws IndexException
Füllt den Buffer so weit es geht mit den Daten aus der Indexdatei.

Parameters:
basePath - Verzeichnis der Indexdatei
Throws:
IndexException - Wenn es Probleme mit dem Einlesen der Datei gibt.

getCID

private long getCID(int pos)
Parameters:
pos - Indexposition (0 = neuester Eintrag, gezaehlt in Eintraegen)
Returns:
Container-ID an der angegebenen Indexposition

getEntry

private long getEntry(ATimeMonotoneIndex.Key entrKey,
                      boolean min,
                      int pos)
Liefert den Key1 (Min) an der angegebenen Indexposition.

Parameters:
entrKey -
min -
pos - Indexposition (0 = neuester Eintrag, gezaehlt in Eintraegen)
Returns:
Key1 der Indexposition

setEntry

private void setEntry(int pos,
                      long dIMin,
                      long dIMax,
                      long aTMin,
                      long aTMax,
                      long dTMin,
                      long dTMax,
                      long cID)
               throws IndexException
Setzt einen Eintrag an der angegebenen Indexposition.

Parameters:
pos - Indexposition (0 = neuester Eintrag, gezaehlt in Eintraegen)
dIMin - zu setzendes Datenindex-Minimum
dIMax - zu setzendes Datenindex-Maximum
aTMin - zu setzendes Archivzeit-Minimum
aTMax - zu setzendes Archivzeit-Maximum
dTMin - zu setzendes Datenzeit-Minimum
dTMax - zu setzendes Datenzeit-Maximum
cID - zu setzende Container-ID
Throws:
IndexException

updateMax

public void updateMax(long dIMax,
                      long aTMax,
                      long dTMax)
               throws IndexException
Aktualisiert die Maximumwerte des aktuellsten Eintrages. Die Minimumwerte und die Container-ID bleiben unverändert.

Parameters:
dIMax - zu setzendes Datenindex-Maximum
aTMax - zu setzendes Archivzeit-Maximum
dTMax - zu setzendes Datenzeit-Maximum
Throws:
IndexException

getCurrentCID

public long getCurrentCID()
Returns:
ContainerID des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

getCurrentDIMin

public long getCurrentDIMin()
Returns:
Minimum des Datenindex des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

getCurrentDIMax

public long getCurrentDIMax()
Returns:
Maximum des Datenindex des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

getCurrentATMin

public long getCurrentATMin()
Returns:
Minimum der Archivzeit des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

getCurrentATMax

public long getCurrentATMax()
Returns:
Maximum der Archivzeit des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

getCurrentDTMin

public long getCurrentDTMin()
Returns:
Minimum der Datenzeit des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

getCurrentDTMax

public long getCurrentDTMax()
Returns:
Maximum der Datenzeit des aktuellen Eintrags oder -1 falls kein Eintrag vorhanden ist

add

public void add(String basePath,
                long dIMin,
                long dIMax,
                long aTMin,
                long aTMax,
                long dTMin,
                long dTMax,
                long cID)
         throws IndexException
Fügt einen neuen Eintrag in den Buffer ein. Bei Bedarf wird der Puffer auf Platte geschrieben.

Parameters:
basePath - Verzeichnis der Indexdatei
dIMin - Min-Wert des Datenindex
dIMax - Max-Wert des Datenindex
aTMin - Min-Wert der Archivzeit
aTMax - Max-Wert der Archivzeit
dTMin - Min-Wert der Datenzeit
dTMax - Max-Wert der Datenzeit
cID - Container-ID des Neueintrags
Throws:
IndexException

checkForAdd

public void checkForAdd(String basePath,
                        long dIMin,
                        long dIMax,
                        long aTMin,
                        long aTMax,
                        long dTMin,
                        long dTMax,
                        long cID)
                 throws IndexException
Prüft, ob dem Index ein neuer Eintrag hinzugefügt werden könnte.

Parameters:
basePath - Verzeichnis der Indexdatei
dIMin - Min-Wert des Datenindex
dIMax - Max-Wert des Datenindex
aTMin - Min-Wert der Archivzeit
aTMax - Max-Wert der Archivzeit
dTMin - Min-Wert der Datenzeit
dTMax - Max-Wert der Datenzeit
cID - Container-ID des Neueintrags
Throws:
IndexException

stepRB

private int stepRB(int rbPos)
Führt einen Schritt im Ringpuffer aus (und bricht dabei an der Feldgrenze um).

Parameters:
rbPos - Absolute Position im Feld (gezählt in Einträgen).
Returns:
Nächste absolute Position im Feld (gezählt in Einträgen).

rb2pos

private int rb2pos(int rbPos)
Rechnet eine absolute Position im Feld (gezählt in Einträgen) in eine Ringpuffer-Position um (0 = neuester Eintrag).

Parameters:
rbPos - absolute Position im Feld (gezählt in Einträgen).
Returns:
Ringpuffer-Position (0 = neuester Eintrag)

getContainerID

protected IndexResult getContainerID(String basePath,
                                     byte[] temp,
                                     ATimeMonotoneIndex.Key cmpKey,
                                     long minKey,
                                     long maxKey)
                              throws IndexException
Liefert die IDs der Container, bei denen der gesuchte Key zwischen Anfang und Ende liegt.

Parameters:
basePath - Verzeichnis der Indexdatei
temp - Speicherbereich, der als Puffer dient, wenn auf die Datei zurückgegriffen werden muss.
cmpKey -
minKey -
maxKey -
Returns:
Liste von ContainerIDs mit Min/Max-Werten von DI, AT, DT
Throws:
IndexException

getContainerIDByATime

public IndexResult getContainerIDByATime(String basePath,
                                         byte[] temp,
                                         long minATime,
                                         long maxATime)
                                  throws IndexException
Liefert die IDs der Container, deren Archivzeitspanne sich mit der angegebenen Spanne ueberschneidet.

Parameters:
basePath - Verzeichnis der Indexdatei
temp - Speicherbereich, der als Puffer dient, wenn auf die Datei zurückgegriffen werden muss.
minATime - Beginn der Zeitspanne
maxATime - Ende der Zeitspanne
Returns:
Liste von ContainerIDs mit Min/Max-Werten von DI, AT, DT
Throws:
IndexException

getAbsoluteATMin

public long getAbsoluteATMin(String basePath)
                      throws IndexException
Liefert den kleinsten Archivzeit-Minwert, der jemals in diesem Index gespeichert wird.

Parameters:
basePath - Verzeichnis, in dem die Index-Datei liegt
Returns:
Kleinster Archivzeitwert
Throws:
IndexException - Bei Zugriffsproblemen mit der IndexDatei

getMinEntry

protected IndexResult getMinEntry(String basePath)
                           throws IndexException
Liefert den kleinsten Eintrag bei Sortierung nach Archivzeit.

Parameters:
basePath - Verzeichnis, in dem die Index-Datei liegt
Returns:
Kleinster Eintrag oder -1 falls keiner vorhanden
Throws:
IndexException - Bei Zugriffsproblemen mit der IndexDatei

countMatchingEntries

private int countMatchingEntries(int startAt,
                                 int numOfEntries,
                                 ATimeMonotoneIndex.Key cmpKey,
                                 long key)
                          throws IndexException
Sucht den Puffer beginnend bei startAt in Richtung neuesten Eintrag nach Einträgen ab, die zum Vergleichswert passen.

Parameters:
startAt - Startposition
numOfEntries - Maximal zu durchsuchende Zahl von Einträgen
cmpKey - Vergleichswert des Eintrags
key - Vergleichsschluessel
Returns:
Anzahl der passenden Einträge
Throws:
IndexException

capacity

public int capacity()
Returns:
Liefert die Zahl der Einträge, die im Speicher gehalten werden können.

entries

public int entries()
Returns:
Anzahl der Einträge, die aktuell im Speicher gehalten werden.

binaryMemSearch

private int binaryMemSearch(ATimeMonotoneIndex.Key cmpKey,
                            long key)
                     throws IndexException
Sucht im Speicher nach dem ersten Eintrag, der auf den übergebenen Key passt. Dies ist der älteste Eintrag, bei dem Key gleich oder zwischen Key1 und Key2 ist. Liegt Key zwischen zwei Einträgen, wird der ältere genommen.

Parameters:
cmpKey - Vergleichswert des Eintrags
key - Startschlüssel
Returns:
Position des gefundenen Eintrags
Throws:
IndexException

compare

private int compare(ATimeMonotoneIndex.Key cmpKey,
                    int index,
                    long key)
             throws IndexException
Vergleicht den Eintrag an der gegebenen Position im Index mit dem gegebenen Schlüssel.

Parameters:
cmpKey - Vergleichswert des Eintrags
index - Position im Index (0 = neueste)
key - Vergleichsschlüssel
Returns:
-1 falls key < Key1(index); 1 falls key > Key2(index); 0 sonst
Throws:
IndexException

binaryFileSearch

private IndexResult binaryFileSearch(String basePath,
                                     byte[] tmpBuf,
                                     ATimeMonotoneIndex.Key cmpKey,
                                     long minKey,
                                     long maxKey)
                              throws IndexException
Führt eine binärSuche in der IndexDatei durch. Dabei wird die IndexDatei in kleine Teile zerlegt, die dann in den übergebenen temporären Buffer eingelesen und mit dem gesuchten Wert verglichen werden.

Parameters:
basePath - Verzeichnis der Indexdatei
tmpBuf - Ein temporäres Array, das als Buffer verwendet wird.
minKey - Schlüssel, der gesucht wird
Returns:
Ein Array mit den gesuchten Werten
Throws:
IndexException - Wenn es Probleme mit der IndexDatei gibt.

readSearchChunk

private int readSearchChunk(RandomAccessFile raf,
                            int chunkNo,
                            byte[] buf,
                            int bufSize)
                     throws IOException
Liest einen Chunk zum Suchen in den Speicher. Falls der letzte Eintrag wegen Startmode==ATimeMonotoneIndex.IndexStartmode.APPEND_REUSE_LAST weiterverwendet wird, wird der letzte Dateieintrag ignoriert.

Parameters:
raf - Indexdatei
chunkNo - Nummer des Chunks, beginnend bei 0
buf - Speicherbereich
bufSize - Größe des Speicherbereichs in Byte (ist stets durch entryLen() teilbar)
Returns:
Anzahl der eingelesenen Einträge.
Throws:
IOException

checkIndexFile

private File checkIndexFile(String basePath)
                     throws IndexException
Prüft grundlegende Eigenschaften einer Indexdatei.

Parameters:
basePath - Verzeichnis der Indexdatei
Returns:
Indexdatei
Throws:
IndexException

checkFileLength

private void checkFileLength(File indexFile,
                             long fileLength)
                      throws CorruptIndexException
Throws:
CorruptIndexException

flush

private void flush(String basePath)
            throws IndexException
Speichert den aktuellen Buffer in die Datei. Dabei werden nur die noch nicht gespeicherten Daten an die Daten in der Datei angehängt. Falls der Index mit ATimeMonotoneIndex.IndexStartmode.APPEND_REUSE_LAST gestartet wurde, wird beim ersten Flushen der letzte Dateieintrag ueberschrieben.

Parameters:
basePath - Verzeichnis der Indexdatei
Throws:
IndexException - Wenn es Probleme mit der IndexDatei gibt

closeIndex

public void closeIndex(String basePath)
                throws IndexException
Schließt den Index und speichert alle geänderten Daten auf Platte. Nach dem Aufruf von darf die Index-Instanz nicht mehr verwendet werden.

Parameters:
basePath - Verzeichnis, in dem die Index-Datei liegt
Throws:
IndexException

closeRandomAccessFile

private void closeRandomAccessFile(RandomAccessFile indexFile)
                            throws IndexException
Schließt die Indexdatei.

Parameters:
indexFile - Indexdatei
Throws:
IndexException

toString

public String toString()
Overrides:
toString in class Object