/*
* ExtendibleHash.java - Joris van Rantwijk
* in2026 Inleiding databeheer
*
* Extendible hashing.
*/
import java.io.RandomAccessFile;
import java.io.IOException;
/*
* We gebruiken aparte files voor de index (of directory) en de records.
*
* De index wordt opgeslagen in een indexfile. Aan het begin van de file
* staat een integer die de globale diepte (d) aangeeft. Daarna volgen de
* entries van de index. Per entry worden twee integers opgeslagen: een
* pointer naar de bijbehorende pagina in de recordfile, en de locale
* diepte van de betreffende pagina (d'). Hiervoor zijn per entry
* 2 * 4 = 8 bytes nodig.
* We wijken hier dus af van de beschrijving in het dictaat, waar de locale
* diepte in de recordpagina wordt opgeslagen.
*
* De recordfile is ingedeeld in pagina's. In elke pagina is ruimte voor
* een vast aantal records (bucketsize). Vrije posities binnen een pagina
* worden gemarkeerd door een record met een ongeldige sleutel (-1).
*
* Wanneer een record moet worden toegevoegd aan een volle pagina,
* wordt page splitting toegepast (zonodig meerdere keren). Soms moet
* dan ook de globale diepte worden vergroot, en de index verdubbeld.
*
* Na het verwijderen van records is het soms mogelijk om pagina's weer
* samen te voegen. We doen dit alleen als beide pagina's voor meer dan
* de helft leeg zijn. Door de recombinatie komt er een pagina in de
* recordfile vrij. In de vfile bewaren we een opsomming van al deze
* vrije pagina's; bij het page splitten kan zo'n vrije pagina weer
* in gebruik worden genomen.
* Als voor alle records de locale diepte kleiner is dan de globale diepte,
* is het in principe mogelijk om ook de globale diepte te verkleinen en de
* index te halveren. Deze operatie is hier niet geimplementeerd, omdat
* het waarschijnlijk niet vaak nodig zal zijn, en omdat het in Java erg
* moeilijk is om een diskfile te verkleinen.
*/
//===========================================================================
// Class ExtendibleHash
// Implementatie van extendible hashing
//===========================================================================
public class ExtendibleHash extends BestandsOrganisatie
{
// De gebruikte files.
private RandomAccessFile ifile;
private RandomAccessFile rfile;
private RandomAccessFile vfile;
// De omvang van een pagina van de recordfile in bytes.
private final static int PAGESIZE = 1024;
// Het maximale aantal records per pagina.
private int bucketsize;
// Globale diepte van de index.
// Deze wordt in het geheugen bewaard om het zoeken te versnellen.
private int globalDepth;
// Construeer een ExtendibleHash class.
// Gebruik de gegeven filenaam, en het gegeven recordtype.
//-----------------------------------------------------------------------
public ExtendibleHash(String filenaam, Class recordType)
throws IOException
{
this.recordType = recordType;
this.recordLen = Record.newRecord(recordType).getRecordlen();
// Bereken de bucketsize (het aantal records dat in een pagina past).
bucketsize = PAGESIZE / recordLen;
// 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.
if (ifile.length() == 0) {
// De file bevat nog geen gegevens. Initialiseer de file
// door een index met diepte 0, en een lege recordpagina
// aan te maken.
globalDepth = 0;
// Schrijf globale diepte
ifile.writeInt(globalDepth);
// Schrijf eerste entry: adres = 0, d' = 0.
ifile.writeInt(0);
ifile.writeInt(0);
diskaccess++;
// Schrijf een lege pagina naar de recordfile.
Record r = Record.newRecord(recordType);
for (int i = 0; i < bucketsize; i++)
r.write(rfile);
diskaccess++;
} else {
// Lees alvast de globale diepte uit de indexfile.
globalDepth = ifile.readInt();
}
}
// 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 int hash(int key)
{
// Per hashwaarde mogen er hoogstens <bucketsize> synoniemen
// optreden. Om dit te garanderen gebruiken we een lineaire
// hashfunctie waarbij we de sleutelwaarde delen door <bucketsize>.
return (key / bucketsize);
}
// Geef een getal dat bestaat uit de b meest significante bits van hv.
//-----------------------------------------------------------------------
private static int getBits(int hv, int b)
{
return (hv >>> (31 - b));
}
// Splits de recordpagina met adres addr.
// Eventueel kan dit leiden tot een verdubbeling van de index.
//-----------------------------------------------------------------------
private void splitPage(int hv, int addr, int localDepth)
throws IOException
{
Record r[], tr;
int h, addr2;
int ta, tld;
int i, k;
// Alloceer een array van records om de huidige inhoud van de pagina
// in het geheugen op te slaan.
r = new Record[bucketsize];
for (i = 0; i < bucketsize; i++)
r[i] = Record.newRecord(recordType);
tr = Record.newRecord(recordType);
// Zoek een positie in de recordfile voor de nieuwe pagina.
// Doorloop eerst de vfile om een vrije positie te zoeken.
addr2 = -1;
vfile.seek(0);
for (i = 0; i < vfile.length() / 4; i++) {
addr2 = vfile.readInt();
if (addr2 != -1) break;
}
diskaccess++;
if (addr2 != -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 de pagina toe aan het eind van de file.
addr2 = (int) ((rfile.length() + PAGESIZE - 1) / PAGESIZE);
}
// Lees de oude pagina in het geheugen.
rfile.seek(addr * PAGESIZE);
for (i = 0; i < bucketsize; i++)
r[i].read(rfile);
diskaccess++;
// Verdeel de records over de twee pagina's.
// In de oude pagina komen de records met volgende hv-bit = 0.
k = 0;
rfile.seek(addr * PAGESIZE);
for (i = 0; i < bucketsize; i++)
if ((getBits(hash(r[i].key), localDepth + 1) & 1) == 0) {
r[i].write(rfile);
k++;
}
// Vul de pagina aan met ongeldige records.
while (k < bucketsize) {
tr.write(rfile);
k++;
}
diskaccess++;
// In de nieuwe pagina komen de records met volgende hv-bit = 1.
k = 0;
rfile.seek(addr2 * PAGESIZE);
for (i = 0; i < bucketsize; i++)
if ((getBits(hash(r[i].key), localDepth + 1) & 1) == 1) {
r[i].write(rfile);
k++;
}
// Vul de pagina aan met ongeldige records.
while (k < bucketsize) {
tr.write(rfile);
k++;
}
diskaccess++;
if (localDepth >= globalDepth) {
// De globale diepte is te klein.
// Verhoog de globale diepte en verdubbel de index.
// De index bevat 2 ^ globalDepth entries.
k = 1 << globalDepth;
// Loop van achter naar voren door de index en verdubbel
// alle entries.
for (i = k - 1; i >= 0; i--) {
ifile.seek(4 + i * 8);
ta = ifile.readInt();
tld = ifile.readInt();
ifile.seek(4 + 2 * i * 8);
ifile.writeInt(ta);
ifile.writeInt(tld);
ifile.writeInt(ta);
ifile.writeInt(tld);
}
// Verhoog de globale diepte en schrijf deze naar de ifile.
globalDepth++;
ifile.seek(0);
ifile.writeInt(globalDepth);
diskaccess++;
}
// Van alle indexentries die naar de oude pagina wijzen,
// moet de helft naar de nieuwe pagina worden gezet.
// Ook moet in alle entries de localDepth worden aangepast.
// Bereken de eerste entry die naar de oude pagina wijst.
h = getBits(hv, localDepth);
h = h << (globalDepth - localDepth);
// Er zijn 2^(globalDepth - localDepth) entries die naar de oude
// pagina wijzen. Update van de eerste helft alleen de localDepth.
k = 1 << (globalDepth - localDepth - 1);
ifile.seek(4 + h * 8);
diskaccess++;
for (i = 0; i < k; i++) {
ifile.writeInt(addr);
ifile.writeInt(localDepth + 1);
}
// Laat de tweede helft van de entries naar de nieuwe pagina wijzen,
// en update ook de localDepth.
for (i = 0; i < k; i++) {
ifile.writeInt(addr2);
ifile.writeInt(localDepth + 1);
}
}
// Probeer de pagina met index h samen te voegen met een andere pagina.
//-----------------------------------------------------------------------
private void tryJoinPage(int h) throws IOException
{
Record r[], r2[], tr;
int addr, addr2, localDepth, localDepth2;
int h2, fp, fp2;
int i, k;
/*
* We noemen twee pagina's "vriendjes", wanneer ze dezelfde locale diepte
* hebben, en de eerste (d' - 1) bits van de hv gelijk zijn. Dit wil zeggen
* dat ze ooit door pagesplitting uit dezelfde pagina zijn ontstaan.
* Niet elke pagina heeft een vriendje.
* Pagina's worden alleen samengevoegd als ze vriendjes zijn, en beiden
* voor meer dan de helft leeg zijn.
*/
// Alloceer array's van records om de inhoud van de pagina's in
// op te slaan.
r = new Record[bucketsize];
for (i = 0; i < bucketsize; i++)
r[i] = Record.newRecord(recordType);
r2 = new Record[bucketsize];
for (i = 0; i < bucketsize; i++)
r2[i] = Record.newRecord(recordType);
tr = Record.newRecord(recordType);
// Lees het adres en de locale diepte van de pagina.
ifile.seek(4 + h * 8);
addr = ifile.readInt();
localDepth = ifile.readInt();
diskaccess++;
// Als de locale diepte == 0, kan er niet samengevoegd worden.
if (localDepth == 0) return;
// Bereken de index van de eerste entry die naar deze pagina wijst.
h = (h >>> (globalDepth - localDepth)) << (globalDepth - localDepth);
// Bereken de index van de eerste entry die naar het vriendje wijst.
h2 = h ^ (1 << (globalDepth - localDepth));
// Lees het adres en de globale diepte van het (mogelijke) vriendje.
ifile.seek(4 + h2 * 8);
addr2 = ifile.readInt();
localDepth2 = ifile.readInt();
diskaccess++;
// Controleer of de pagina's echt bevriend zijn, dwz. of ze
// dezelfde locale diepte hebben.
if (localDepth != localDepth2) {
// De pagina's zijn niet bevriend; we kunnen ze niet samenvoegen.
return;
}
// Lees beide pagina's in het geheugen en tel het aantal vrije
// posities.
fp = 0;
rfile.seek(addr * PAGESIZE);
for (i = 0; i < bucketsize; i++) {
r[i].read(rfile);
if (r[i].key == -1) fp++;
}
diskaccess++;
fp2 = 0;
rfile.seek(addr2 * PAGESIZE);
for (i = 0; i < bucketsize; i++) {
r2[i].read(rfile);
if (r2[i].key == -1) fp2++;
}
diskaccess++;
// Controleer of beide pagina's voor meer dan de helft leeg zijn.
if (2 * fp <= bucketsize || 2 * fp2 <= bucketsize) return;
// Voeg de pagina's samen.
// Schrijf de records uit beide pagina's naar de eerste pagina,
// en vul de pagina aan met ongeldige records.
k = 0;
rfile.seek(addr * PAGESIZE);
for (i = 0; i < bucketsize; i++)
if (r[i].key != -1) {
r[i].write(rfile);
k++;
}
for (i = 0; i < bucketsize; i++)
if (r2[i].key != -1) {
r2[i].write(rfile);
k++;
}
while (k < bucketsize) {
tr.write(rfile);
k++;
}
diskaccess++;
// Schrijf ongeldige records naar de tweede pagina.
rfile.seek(addr2 * PAGESIZE);
for (k = 0; k < bucketsize; k++)
tr.write(rfile);
diskaccess++;
// Neem de tweede pagina op in de lijst van vrije pagina's.
// Zoek hiervoor een plekje in de vfile.
vfile.seek(0);
for (i = 0; i < vfile.length() / 4; i++) {
k = vfile.readInt();
if (k == -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(addr2);
diskaccess++;
// Update de index. Samen hadden de twee pagina's
// 2^(globalDepth - localDepth + 1) entries in de index.
// Deze moeten allemaal naar dezelfde pagina gaan wijzen en een
// kleinere localDepth krijgen.
k = 1 << (globalDepth - localDepth + 1);
if (h2 < h) h = h2;
ifile.seek(4 + 8 * h);
diskaccess++;
for (i = 0; i < k; i++) {
ifile.writeInt(addr);
ifile.writeInt(localDepth - 1);
}
}
// Voeg het record r toe.
//-----------------------------------------------------------------------
public void insert(Record r) throws Exception, IOException
{
Record tr = Record.newRecord(recordType);
int hv, h;
int addr, localDepth;
int i, k;
// Bereken de hashwaarde van de sleutel.
hv = hash(r.key);
do {
// In de index gebruiken we slechts globalDepth bits.
h = getBits(hv, globalDepth);
// Lees de bijbehorende index entry
ifile.seek(4 + h * 8);
addr = ifile.readInt();
localDepth = ifile.readInt();
diskaccess++;
// Zoek in de bijbehorende recordpagina naar een vrije positie.
// Controleer tegelijkertijd of het record nog niet bestaat.
rfile.seek(addr * PAGESIZE);
diskaccess++;
k = -1;
for (i = 0; i < bucketsize; i++) {
// Lees een record uit de pagina.
tr.read(rfile);
if (tr.key == -1 && k == -1) {
// Vrije positie gevonden; onthoud dit in k.
k = i;
}
if (tr.key == r.key) {
// Record met dezelfde sleutel gevonden; geef exceptie.
throw new Exception("Record bestaat al");
}
}
if (k == -1) {
// Er is geen vrije ruimte in de pagina; roep de functie
// splitPage aan om de pagina te splitsen en de index
// aan te passen.
splitPage(hv, addr, localDepth);
}
// Als k == -1, probeer dan na het splitsen van de pagina
// opnieuw een vrije positie voor het record te vinden.
} while (k == -1);
// We hebben een vrije positie in de recordpagina.
// Schrijf op die plaats het nieuwe record.
rfile.seek(addr * PAGESIZE + k * recordLen);
r.write(rfile);
diskaccess++;
}
// Vervang een bestaand record door r.
//-----------------------------------------------------------------------
public void update(Record r) throws Exception, IOException
{
Record tr = Record.newRecord(recordType);
int hv, h;
int addr, localDepth;
int i, k, p;
// Bereken de hashwaarde van de sleutel.
hv = hash(r.key);
// In de index gebruiken we slechts globalDepth bits.
h = getBits(hv, globalDepth);
// Lees de bijbehorende index entry
ifile.seek(4 + h * 8);
addr = ifile.readInt();
localDepth = ifile.readInt();
diskaccess++;
// Zoek in de bijbehorende recordpagina naar het record r.
rfile.seek(addr * PAGESIZE);
diskaccess++;
for (i = 0; i < bucketsize; i++) {
// Lees een record uit de pagina.
tr.read(rfile);
if (tr.key == r.key) {
// We hebben het oude record gevonden.
// Schrijf het nieuwe record er overheen.
rfile.seek(addr * PAGESIZE + i * 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 hv, h;
int addr, localDepth;
int i, k, p;
// Bereken de hashwaarde van de sleutel.
hv = hash(key);
// In de index gebruiken we slechts globalDepth bits.
h = getBits(hv, globalDepth);
// Lees de bijbehorende index entry
ifile.seek(4 + h * 8);
addr = ifile.readInt();
localDepth = ifile.readInt();
diskaccess++;
// Zoek in de bijbehorende recordpagina naar het record.
rfile.seek(addr * PAGESIZE);
diskaccess++;
for (i = 0; i < bucketsize; i++) {
// Lees een record uit de pagina.
r.read(rfile);
if (r.key == key) {
// We hebben het juiste record gevonden.
// 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 = Record.newRecord(recordType);
int hv, h;
int addr, localDepth;
int i, k, p;
// Bereken de hashwaarde van de sleutel.
hv = hash(key);
// In de index gebruiken we slechts globalDepth bits.
h = getBits(hv, globalDepth);
// Lees de bijbehorende index entry
ifile.seek(4 + h * 8);
addr = ifile.readInt();
localDepth = ifile.readInt();
diskaccess++;
// Zoek in de bijbehorende recordpagina naar het record r.
rfile.seek(addr * PAGESIZE);
diskaccess++;
for (i = 0; i < bucketsize; i++) {
// Lees een record uit de pagina.
tr.read(rfile);
if (tr.key == key) {
// We hebben het juiste record gevonden.
// Verwijder het door de sleutelwaarde ongeldig te maken.
tr.key = -1;
rfile.seek(addr * PAGESIZE + i * recordLen);
tr.write(rfile);
diskaccess++;
// Probeer de pagina samen te voegen.
tryJoinPage(h);
// Klaar met de delete operatie.
return;
}
}
// Het record bestaat niet; geef een exceptie.
throw new Exception("Record niet gevonden");
}
}
//===========================================================================
// End
//===========================================================================