/*
* StaticHash.java - Joris van Rantwijk
* in2026 Inleiding databeheer
*
* Bestandsorganisatie:
* Statische hashing via rest bij deling.
* Overloop in een apart bestand.
*/
import java.io.RandomAccessFile;
import java.io.IOException;
/*
* Er wordt gebruik gemaakt van aparte files voor het primaire adresgebied
* en de overloop. De primaire file bestaat uit een vast aantal pagina's.
* In elke pagina kunnen maximaal <bucket size> records zijn opgeslagen.
* In geval van overloop bevat de bucket een verwijzing naar een overloopketen.
* Vrije plaatsen worden gemarkeerd door een record met sleutelwaarde -1.
*
* De overloop file heeft bucket size 1. Dit wil zeggen dat het bestaat
* uit ketens van individuele records.
* De vrije posities in de overloop file worden bijgehouden in een aparte
* keten. Een verwijzing naar de eerste vrije positie in de overloopfile,
* wordt opgeslagen in een derde bestand.
*/
//===========================================================================
// Class StaticHash
// Implementatie van statische hashing
//===========================================================================
public class StaticHash extends BestandsOrganisatie
{
// De gebruikte files.
private RandomAccessFile pfile;
private RandomAccessFile ofile;
private RandomAccessFile vfile;
// Het aantal buckets in het primaire gebied.
// Dit is het aantal mogelijke waarden van de hashfunctie.
private final static int MAXHASH = 10;
// De omvang van een pagina in bytes.
private final static int PAGESIZE = 512;
// De bucketsize in het primaire adresgebied.
private int bucketsize;
// Verwijzing naar de keten van vrije posities in de overloopfile.
// Deze verwijzing wordt opgeslagen in de vfile.
private int freepos;
// Construeer een StaticHash class.
// Gebruik de gegeven filenaam, en het gegeven recordtype.
//-----------------------------------------------------------------------
public StaticHash(String filenaam, Class recordType) throws IOException
{
this.recordType = recordType;
this.recordLen = Record.newRecord(recordType).getRecordlen();
// Bereken de bucketsize (= aantal records per bucket)
// Pagesize min 4 bytes voor verwijzing, delen door record lengte.
bucketsize = (PAGESIZE - 4) / recordLen;
// Open de benodigde files
pfile = new RandomAccessFile(filenaam + "p", "rw");
ofile = new RandomAccessFile(filenaam + "o", "rw");
vfile = new RandomAccessFile(filenaam + "v", "rw");
// Controleer de lengte van de primaire file.
// 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 primaire file worden geschreven.
if (pfile.length() == 0) {
Bucket b = new Bucket(bucketsize, recordType);
for (int i = 0; i < MAXHASH; i++) {
pfile.seek(i * PAGESIZE);
b.write(pfile);
}
}
// Lees de verwijzing naar de lijst van vrije overloopposities.
if (vfile.length() == 0)
freepos = -1;
else
freepos = vfile.readInt();
}
// Sluit het bestand.
//-----------------------------------------------------------------------
public void close() throws IOException
{
// Schrijf de (mogelijk) gewijzigde verwijzing naar de vrije posities.
vfile.seek(0);
vfile.writeInt(freepos);
// Sluit alle files.
pfile.close();
ofile.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
{
Bucket b, ob;
int h;
int i, k;
// Controleer eerst of het record al bestaat.
if (retrieve(r.key) != null)
throw new Exception("Record bestaat al");
// Bucket b wordt gebruikt voor de primaire file.
// Bucket ob wordt gebruikt voor de overloopfile.
b = new Bucket(bucketsize, recordType);
ob = new Bucket(1, recordType);
// Bereken de hashwaarde van de sleutel.
h = hash(r.key);
// Lees de bijbehorende pagina.
pfile.seek(h * PAGESIZE);
b.read(pfile);
diskaccess++;
// Kijk of er vrije ruimte is in de bucket.
for (i = 0; i < bucketsize; i++)
if (b.record[i].key == -1) {
// Er is een vrije positie in de bucket.
// Het nieuwe record kan hier worden geplaatst.
b.record[i] = r;
// Schrijf de pagina terug naar de file.
pfile.seek(h * PAGESIZE);
b.write(pfile);
diskaccess++;
// Klaar met de insert operatie
return;
}
// Er is geen ruimte voor het nieuwe record.
// Het record moet dus in de overloopketen worden geplaatst.
// Gebruik een vrije positie in de overloopfile.
if (freepos != -1) {
k = freepos;
// Laat freepos naar het volgende vrije record wijzen.
ofile.seek(freepos * (recordLen + 4));
ob.read(ofile);
diskaccess++;
freepos = ob.ref;
} else {
// Als er geen vrije positie is, moet er een record
// worden toegevoegd aan het eind van het overloopbestand.
k = (int) (ofile.length() / (recordLen + 4));
}
// Plaats het nieuwe record in de overloop bucket.
ob.record[0] = r;
// Laat het nieuwe record doorverwijzen naar de oude overloopketen.
ob.ref = b.ref;
// Schrijf het record naar de ofile.
ofile.seek(k * (recordLen + 4));
ob.write(ofile);
diskaccess++;
// Laat de bucket in de primaire file verwijzen naar het
// nieuwe overlooprecord.
b.ref = k;
// Schrijf de bucket naar de pfile.
pfile.seek(h * PAGESIZE);
b.write(pfile);
diskaccess++;
}
// Vervang een bestaand record door r.
//-----------------------------------------------------------------------
public void update(Record r) throws Exception, IOException
{
Bucket b, ob;
int h;
int i, k;
// Bucket b wordt gebruikt voor de primaire file.
// Bucket ob wordt gebruikt voor de overloopfile.
b = new Bucket(bucketsize, recordType);
ob = new Bucket(1, recordType);
// Bereken de hashwaarde van de sleutel.
h = hash(r.key);
// Lees de bijbehorende pagina.
pfile.seek(h * PAGESIZE);
b.read(pfile);
diskaccess++;
// Kijk of het gezochte record in de bucket staat.
for (i = 0; i < bucketsize; i++)
if (b.record[i].key == r.key) {
// Record gevonden, vervang het door r.
b.record[i] = r;
// Schrijf de bucket naar de file.
pfile.seek(h * PAGESIZE);
b.write(pfile);
diskaccess++;
// Klaar met de update operatie.
return;
}
// Het record is niet gevonden in de bucket.
// Loop door de (eventuele) overloopketen.
k = b.ref;
while (k != -1) {
ofile.seek(k * (recordLen + 4));
ob.read(ofile);
diskaccess++;
if (ob.record[0].key == r.key) {
// Record gevonden, vervang het door r.
ob.record[0] = r;
// Schrijf de bucket naar de file.
ofile.seek(k * (recordLen + 4));
ob.write(ofile);
diskaccess++;
// Klaar met de update operatie.
return;
}
k = ob.ref;
}
// 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
{
Bucket b, ob;
int h;
int i, k;
// Bucket b wordt gebruikt voor de primaire file.
// Bucket ob wordt gebruikt voor de overloopfile.
b = new Bucket(bucketsize, recordType);
ob = new Bucket(1, recordType);
// Bereken de hashwaarde van de sleutel.
h = hash(key);
// Lees de bijbehorende pagina.
pfile.seek(h * PAGESIZE);
b.read(pfile);
diskaccess++;
// Kijk of het gezochte record in de bucket staat.
for (i = 0; i < bucketsize; i++)
if (b.record[i].key == key) {
// Record gevonden.
return b.record[i];
}
// Het record is niet gevonden in de bucket.
// Loop door de (eventuele) overloopketen.
k = b.ref;
while (k != -1) {
ofile.seek(k * (recordLen + 4));
ob.read(ofile);
diskaccess++;
if (ob.record[0].key == key) {
// Record gevonden.
return ob.record[0];
}
k = ob.ref;
}
// Het record bestaat niet.
return null;
}
// Verwijder het record met de sleutel <key>.
//-----------------------------------------------------------------------
public void delete(int key) throws Exception, IOException
{
Bucket b, ob;
int h;
int i, k, p;
// Bucket b wordt gebruikt voor de primaire file.
// Bucket ob wordt gebruikt voor de overloopfile.
b = new Bucket(bucketsize, recordType);
ob = new Bucket(1, recordType);
// Bereken de hashwaarde van de sleutel.
h = hash(key);
// Lees de bijbehorende pagina.
pfile.seek(h * PAGESIZE);
b.read(pfile);
diskaccess++;
// Kijk of het gezochte record in de bucket staat.
for (i = 0; i < bucketsize; i++)
if (b.record[i].key == key) {
// Record gevonden.
// Verwijder het record uit de bucket.
b.record[i].key = -1;
pfile.seek(h * PAGESIZE);
b.write(pfile);
diskaccess++;
// Klaar met de delete operatie.
return;
}
// Het record is niet gevonden in de bucket.
// Loop door de (eventuele) overloopketen.
// k wijst naar het record dat nu onderzocht wordt,
// i wijst naar het vorige record in de keten.
i = -1;
k = b.ref;
while (k != -1) {
ofile.seek(k * (recordLen + 4));
ob.read(ofile);
diskaccess++;
if (ob.record[0].key == key) {
// Record gevonden.
// Plaats het overlooprecord in de keten van vrije records.
p = ob.ref;
ob.record[0].key = -1;
ob.ref = freepos;
ofile.seek(k * (recordLen + 4));
ob.write(ofile);
diskaccess++;
freepos = k;
// Verwijder het record uit de overloopketen door de vorige
// verwijzing aan te passen.
if (i == -1) {
// Het verwijderde record was het eerste record in de
// overloopketen. De verwijzing in de primaire file
// moet dus aangepast worden.
b = new Bucket(bucketsize, recordType);
pfile.seek(h * PAGESIZE);
b.read(pfile);
diskaccess++;
b.ref = p;
pfile.seek(h * PAGESIZE);
b.write(pfile);
diskaccess++;
} else {
// De verwijzing in het vorige record in de keten
// moet aangepast worden.
ofile.seek(i * (recordLen + 4));
ob.read(ofile);
diskaccess++;
ob.ref = p;
ofile.seek(i * (recordLen + 4));
ob.write(ofile);
diskaccess++;
}
// Klaar met de delete operatie.
return;
}
// Ga naar het volgende record in de keten.
i = k;
k = ob.ref;
}
// Het record bestaat niet, geef een exceptie.
throw new Exception("Record niet gevonden");
}
}
//===========================================================================
// End
//===========================================================================