/*
* IndexDirect.java - Joris van Rantwijk
* in2026 Inleiding databeheer
*
* Indexdirecte bestandsorganisatie.
*/
import java.io.RandomAccessFile;
import java.io.IOException;
/*
* Er wordt gebruik gemaakt van aparte files voor de index en de records.
* De indexfile bestaat uit een vast aantal pagina's. Per pagina is er een
* vast aantal (sleutel, adres) paren, waarbij het adres verwijst naar het
* record met die sleutel (dense-indexing).
* De toegang tot de index gaat via statische hashing; er is geen
* voorziening voor overloop. Vrije posities in de indexfile worden
* gemarkeerd door een ongeldige sleutelwaarde (-1).
*
* De recordfile bevat een opeenvolging van individuele records (b=1). Vrije
* posities in de recordfile (ontstaan door het verwijderen van records)
* worden bijgehouden in een aparte file. Deze derde file bevat een
* opsomming van adressen van vrije posities in de recordfile. Wanneer een
* positie weer in gebruik wordt genomen, moet het adres uit de file
* verwijderd worden. Dit gebeurt door het te vervangen door een ongeldig
* adres (-1).
*/
//===========================================================================
// Class IndexDirect
// Implementatie van een indexdirecte bestandsorganisatie
//===========================================================================
public class IndexDirect extends BestandsOrganisatie
{
// De gebruikte files.
private RandomAccessFile ifile;
private RandomAccessFile rfile;
private RandomAccessFile vfile;
// Aantal pagina's in de indexfile.
// Dit is het aantal mogelijke waarden van de hashfunctie.
private final static int MAXHASH = 100;
// De omvang van een pagina in bytes.
private final static int PAGESIZE = 1024;
// Het aantal entries per pagina van de indexfile.
// Per entry worden twee integers (sleutel en adres) opgeslagen.
// Hiervoor zijn 2 * 4 = 8 bytes nodig.
private int indexEntriesPerPage = PAGESIZE / 8;
// Construeer een IndexDirect class.
// Gebruik de gegeven filenaam, en het gegeven recordtype.
//-----------------------------------------------------------------------
public IndexDirect(String filenaam, Class recordType) throws IOException
{
this.recordType = recordType;
this.recordLen = Record.newRecord(recordType).getRecordlen();
// Open de benodigde files. Als de files nog niet bestaan,
// worden er automatisch lege files aangemaakt.
ifile = new RandomAccessFile(filenaam + "i", "rw");
rfile = new RandomAccessFile(filenaam + "r", "rw");
vfile = new RandomAccessFile(filenaam + "v", "rw");
// Controleer de lengte van de indexfile.
// Als dit de eerste keer is dat deze files geopend worden
// (dwz de database bestond nog niet), moet een reeks lege
// pagina's in de indexfile worden geschreven.
if (ifile.length() == 0) {
for (int i = 0; i < MAXHASH; i++) {
ifile.seek(i * PAGESIZE);
for (int j = 0; j < indexEntriesPerPage; j++) {
// Schrijf een ongeldige sleutel en ongeldig adres.
ifile.writeInt(-1);
ifile.writeInt(-1);
}
}
}
}
// Sluit het bestand.
//-----------------------------------------------------------------------
public void close() throws IOException
{
// Sluit alle files.
ifile.close();
rfile.close();
vfile.close();
}
// Bereken de hashwaarde van de gegeven sleutel.
//-----------------------------------------------------------------------
private static int hash(int key)
{
return (key % MAXHASH);
}
// Voeg het record r toe.
//-----------------------------------------------------------------------
public void insert(Record r) throws Exception, IOException
{
int h;
int i, k, p;
int key, address;
// Bereken de hashwaarde van de sleutel.
h = hash(r.key);
// Zoek in de bijbehorende indexpagina naar een vrije positie.
// Controleer tegelijkertijd of het record nog niet aanwezig is.
ifile.seek(h * PAGESIZE);
diskaccess++;
k = -1;
for (i = 0; i < indexEntriesPerPage; i++) {
// Lees een (sleutel, adres) paar.
key = ifile.readInt();
address = ifile.readInt();
if (key == -1 && k == -1) {
// Vrije positie gevonden; onthoud dit in k.
k = i;
}
if (key == r.key) {
// Record met zelfde sleutel gevonden; geef een exceptie.
throw new Exception("Record bestaat al");
}
}
if (k == -1) {
// Er is geen ruimte in de indexpagina.
// We hebben geen voorziening voor overloop dus ...
throw new Exception("Indexpagina vol");
}
// Zoek een plekje in de recordfile voor het nieuwe record.
// Doorloop eerst de vfile om een vrije positie te zoeken.
p = -1;
vfile.seek(0);
for (i = 0; i < vfile.length() / 4; i++) {
p = vfile.readInt();
if (p != -1) break;
}
if (p != -1) {
// Vrije positie gevonden.
// Verwijder deze vrije positie uit de vfile.
vfile.seek(i * 4);
vfile.writeInt(-1);
} else {
// Geen vrije positie gevonden.
// Voeg dan het record toe aan het eind van de recordfile.
p = (int) (rfile.length() / recordLen);
}
// Schrijf het nieuwe record in de recordfile.
rfile.seek(p * recordLen);
r.write(rfile);
diskaccess++;
// Voeg de sleutel en het adres van het nieuwe record toe aan de
// index. Gebruik daarvoor de vrije indexpositie in k.
ifile.seek(h * PAGESIZE + k * 8);
ifile.writeInt(r.key);
ifile.writeInt(p);
diskaccess++;
}
// Vervang een bestaand record door r.
//-----------------------------------------------------------------------
public void update(Record r) throws Exception, IOException
{
int h, i;
int key, address;
// Bereken de hashwaarde van de sleutel.
h = hash(r.key);
// Zoek in de bijbehorende indexpagina naar het record.
ifile.seek(h * PAGESIZE);
diskaccess++;
for (i = 0; i < indexEntriesPerPage; i++) {
// Lees een (sleutel, adres) paar.
key = ifile.readInt();
address = ifile.readInt();
if (key == r.key) {
// We hebben het adres van het record gevonden.
// Schrijf nu in het recordfile het nieuwe record
// over het oude heen.
rfile.seek(address * recordLen);
r.write(rfile);
diskaccess++;
// Klaar met de update operatie.
return;
}
}
// Het record bestaat niet; geef een exceptie.
throw new Exception("Record niet gevonden");
}
// Zoek het record met de sleutel key.
//-----------------------------------------------------------------------
public Record retrieve(int key) throws IOException
{
Record r = Record.newRecord(recordType);
int h, i;
int k, address;
// Bereken de hashwaarde van de sleutel.
h = hash(key);
// Zoek in de bijbehorende indexpagina naar het record.
ifile.seek(h * PAGESIZE);
diskaccess++;
for (i = 0; i < indexEntriesPerPage; i++) {
// Lees een (sleutel, adres) paar.
k = ifile.readInt();
address = ifile.readInt();
if (k == key) {
// We hebben het adres van het record gevonden.
// Lees het record uit het recordfile.
rfile.seek(address * recordLen);
r.read(rfile);
diskaccess++;
// Geef het record terug.
return r;
}
}
// Het record bestaat niet; geef null terug.
return null;
}
// Verwijder het record met de sleutel <key>.
//-----------------------------------------------------------------------
public void delete(int key) throws Exception, IOException
{
Record tr;
int h, i;
int p, k, address;
// Bereken de hashwaarde van de sleutel.
h = hash(key);
// Zoek in de bijbehorende indexpagina naar het record.
k = -1;
address = -1;
ifile.seek(h * PAGESIZE);
diskaccess++;
for (i = 0; i < indexEntriesPerPage; i++) {
// Lees een (sleutel, adres) paar.
k = ifile.readInt();
address = ifile.readInt();
if (k == key) break;
}
if (k != key) {
// Het record is niet gevonden; geef een exceptie.
throw new Exception("Record niet gevonden");
}
// We hebben de indexentry van het record gevonden.
// Verwijder het record uit de index.
ifile.seek(h * PAGESIZE + i * 8);
ifile.writeInt(-1);
ifile.writeInt(-1);
diskaccess++;
// Verwijder het record uit de recordfile door er een record
// met een ongeldig adres overheen te schrijven.
tr = Record.newRecord(recordType);
rfile.seek(address * recordLen);
tr.write(rfile);
diskaccess++;
// Neem de vrijgekomen positie in de recordfile op in de lijst van
// vrije recordposities. Zoek hiervoor een plekje in de vfile.
vfile.seek(0);
for (i = 0; i < vfile.length() / 4; i++) {
p = vfile.readInt();
if (p == -1) {
// Vrije plek in de vfile gevonden.
// Schrijf hier straks het adres.
vfile.seek(i * 4);
break;
}
}
// Schrijf het adres naar de vfile.
vfile.writeInt(address);
}
}
//===========================================================================
// End
//===========================================================================