jdbm.java

jdbm NMS

// Developed by Kinva Network Inc. 2000


// Source File Name:   jdbm.java

package com.kinva.util.jdbm;

import java.io.*;
import java.util.Enumeration;

// Referenced classes of package com.kinva.util.jdbm:
//            FastByteArrayOutputStream, LRUEntry, LRUList, jdbmBucket, 
//            jdbmBucketElement, jdbmEnumerator

public class jdbm
{

    protected final void trace(String s)
    {
    }

    private static final int hash(byte abyte0[])
    {
        int i = 0x238f13af * abyte0.length;
        for(int j = 0; j < abyte0.length; j++)
            i = i + (abyte0[j] << (j * 5) % 24) & 0x7fffffff;

        return 0x41c64e6b * i + 12345 & 0x7fffffff;
    }

    private void splitBucket(int i, jdbmBucket jdbmbucket)
        throws IOException
    {
        Object obj = null;
        trace("split bucket: " + jdbmbucket.fileptr);
        for(; jdbmbucket.count == bucket_elems; jdbmbucket = lookupBucket(i))
        {
            list.removeBucket(jdbmbucket);
            loaded_buckets--;
            markAvailable(jdbmbucket.fileptr, block_size);
            int j = allocateSpace(block_size);
            int k = allocateSpace(block_size);
            jdbmBucket jdbmbucket2 = new jdbmBucket(this, j, -1);
            jdbmBucket jdbmbucket3 = new jdbmBucket(this, k, -1);
            list.addEntry(jdbmbucket2);
            list.addEntry(jdbmbucket3);
            trace("splited b0=" + j);
            trace("splited b1=" + k);
            loaded_buckets += 2;
            int l = jdbmbucket.bits + 1;
            jdbmbucket2.bits = l;
            jdbmbucket3.bits = l;
            if(dir_bits == jdbmbucket.bits)
            {
                dir_size <<= 1;
                dir_adr = allocateSpace(dir_size * 4);
                int ai[] = new int[dir_size];
                for(int j1 = 0; j1 < dir_size / 2; j1++)
                {
                    ai[2 * j1] = diridx[j1];
                    ai[2 * j1 + 1] = diridx[j1];
                }

                diridx = ai;
                dir_bits = l;
                dir_changed = true;
            }
            for(int i1 = 0; i1 < bucket_elems; i1++)
            {
                jdbmBucketElement jdbmbucketelement = jdbmbucket.elements[i1];
                int l1 = jdbmbucketelement.hashval >> 31 - l & 0x1;
                int j2 = jdbmbucketelement.hashval % bucket_elems;
                jdbmBucket jdbmbucket1;
                for(jdbmbucket1 = l1 != 0 ? jdbmbucket3 : jdbmbucket2; jdbmbucket1.elements[j2].hashval != -1; j2 = (j2 + 1) % bucket_elems);
                jdbmbucket1.elements[j2] = jdbmbucketelement;
                jdbmbucket1.count++;
            }

            jdbmbucket3.avail_count = jdbmbucket.avail_count;
            jdbmbucket3.avail_size = jdbmbucket.avail_size;
            jdbmbucket3.avail_ptr = jdbmbucket.avail_ptr;
            int k1 = i >>> 31 - dir_bits;
            int i2 = k1 >> dir_bits - l | 0x1;
            int k2 = i2 + 1 << dir_bits - l;
            i2 <<= dir_bits - l;
            int l2 = i2 - (k2 - i2);
            trace("updating dir from " + l2 + " to " + i2);
            for(int i3 = l2; i3 < i2; i3++)
                diridx[i3] = j;

            trace("updating dir from " + i2 + " to " + k2);
            for(int j3 = i2; j3 < k2; j3++)
                diridx[j3] = k;

            jdbmbucket2.modified = true;
            jdbmbucket3.modified = true;
            dir_changed = true;
            saveBucket(jdbmbucket2);
            saveBucket(jdbmbucket3);
        }

    }

    private void saveHeader(DataOutputStream dataoutputstream)
        throws IOException
    {
        dataoutputstream.writeInt(block_size);
        dataoutputstream.writeInt(dir_bits);
        dataoutputstream.writeInt(dir_size);
        dataoutputstream.writeInt(dir_adr);
        dataoutputstream.writeInt(cache_size);
        dataoutputstream.writeInt(bucket_elems);
        dataoutputstream.writeInt(next_block);
        dataoutputstream.writeInt(avail_length);
        dataoutputstream.writeInt(avail_count);
        for(int i = 0; i < avail_length; i++)
        {
            dataoutputstream.writeInt(avail_size[i]);
            dataoutputstream.writeInt(avail_ptr[i]);
        }

    }

    private void restoreHeader(DataInputStream datainputstream)
        throws IOException
    {
        block_size = datainputstream.readInt();
        dir_bits = datainputstream.readInt();
        dir_size = datainputstream.readInt();
        dir_adr = datainputstream.readInt();
        cache_size = datainputstream.readInt();
        bucket_elems = datainputstream.readInt();
        next_block = datainputstream.readInt();
        avail_length = datainputstream.readInt();
        avail_count = datainputstream.readInt();
        avail_size = new int[avail_length];
        avail_ptr = new int[avail_length];
        for(int i = 0; i < avail_length; i++)
        {
            avail_size[i] = datainputstream.readInt();
            avail_ptr[i] = datainputstream.readInt();
        }

    }

    public void printHeader(PrintStream printstream)
    {
        printstream.println("Options for " + file.getAbsolutePath() + ":");
        printstream.println("\tblock_size   = " + block_size);
        printstream.println("\tdir_bits     = " + dir_bits);
        printstream.println("\tdir_size     = " + dir_size);
        printstream.println("\tdir_adr      = " + dir_adr);
        printstream.println("\tcache_size   = " + cache_size);
        printstream.println("\tdir_size     = " + (1 << dir_bits));
        printstream.println("\tbucket_elems = " + bucket_elems);
        printstream.println("\tnext_block   = " + next_block);
        printstream.println("\tavail_count  = " + avail_count);
        printstream.println("\tavail_length = " + avail_length);
    }

    public void printAvail(PrintStream printstream)
    {
        printstream.println("avail_count=" + avail_count + "/" + avail_size.length);
        for(int i = 0; i < avail_count; i++)
            printstream.println("\tsize=" + avail_size[i] + " ,ptr=" + avail_ptr[i]);

    }

    void saveBucket(jdbmBucket jdbmbucket)
        throws IOException
    {
        DataOutputStream dataoutputstream = new DataOutputStream(new FastByteArrayOutputStream(buffer));
        jdbmbucket.save(dataoutputstream);
        fd.seek(jdbmbucket.fileptr);
        fd.write(buffer);
    }

    private void saveDirectory(DataOutputStream dataoutputstream)
        throws IOException
    {
        for(int i = 0; i < diridx.length; i++)
            dataoutputstream.writeInt(diridx[i]);

    }

    private void restoreDirectory(DataInputStream datainputstream)
        throws IOException
    {
        diridx = new int[dir_size];
        for(int i = 0; i < diridx.length; i++)
            diridx[i] = datainputstream.readInt();

    }

    void markAvailable(int i, int j)
    {
        if(avail_count + 1 >= avail_size.length)
            return;
        header_changed = true;
        for(int k = 0; k < avail_count; k++)
            if(avail_size[k] >= j)
            {
                System.arraycopy(avail_size, k, avail_size, k + 1, avail_count - k);
                System.arraycopy(avail_ptr, k, avail_ptr, k + 1, avail_count - k);
                avail_count++;
                avail_size[k] = j;
                avail_ptr[k] = i;
                return;
            }

        avail_size[avail_count] = j;
        avail_ptr[avail_count] = i;
        avail_count++;
    }

    final void removeAvailable(int i)
    {
        header_changed = true;
        avail_count--;
        if(i == avail_count)
        {
            return;
        } else
        {
            System.arraycopy(avail_size, i + 1, avail_size, i, avail_count - i);
            System.arraycopy(avail_ptr, i + 1, avail_ptr, i, avail_count - i);
            return;
        }
    }

    int fixAvailable(int i, int j)
    {
        header_changed = true;
        int k = avail_ptr[i];
        int l = avail_size[i] -= j;
        int i1 = avail_ptr[i] += j;
        removeAvailable(i);
        if(l <= 8)
        {
            return k;
        } else
        {
            markAvailable(i1, l);
            return k;
        }
    }

    protected int allocateSpace(int i)
    {
        header_changed = true;
        trace("allocateSpace: avail_count=" + avail_count);
        for(int j = 0; j < avail_count; j++)
            if(avail_size[j] >= i)
                return fixAvailable(j, i);

        int k = next_block++;
        int l = k * block_size;
        int i1;
        while((i1 = (next_block - k) * block_size) < i) 
            next_block++;
        int j1 = i1 - i;
        if(j1 >= 8)
            markAvailable(l + i, j1);
        return l;
    }

    protected int write(jdbmBucket jdbmbucket, byte abyte0[], byte abyte1[])
        throws IOException
    {
        int i = abyte0.length + abyte1.length;
        int j = jdbmbucket.allocateSpace(i);
        if(j < 0)
            j = allocateSpace(i);
        trace("write: @" + j);
        fd.seek(j);
        fd.write(abyte0);
        fd.write(abyte1);
        return j;
    }

    byte[] readKey(jdbmBucketElement jdbmbucketelement)
        throws IOException
    {
        trace("read: @" + jdbmbucketelement.fileptr);
        byte abyte0[] = new byte[jdbmbucketelement.key_size];
        fd.seek(jdbmbucketelement.fileptr);
        if(fd.read(abyte0) != jdbmbucketelement.key_size)
            throw new RuntimeException("invalid key read.");
        else
            return abyte0;
    }

    byte[] readData(jdbmBucketElement jdbmbucketelement)
        throws IOException
    {
        byte abyte0[] = new byte[jdbmbucketelement.data_size];
        fd.seek(jdbmbucketelement.fileptr + jdbmbucketelement.key_size);
        if(fd.read(abyte0) != jdbmbucketelement.data_size)
            throw new RuntimeException("invalid data read.");
        else
            return abyte0;
    }

    protected synchronized jdbmBucket unloadBucket()
        throws IOException
    {
        LRUEntry lruentry = list.getLRU();
        if(lruentry == null)
            return null;
        jdbmBucket jdbmbucket = lruentry.bucket;
        if(jdbmbucket.modified)
            saveBucket(jdbmbucket);
        loaded_buckets--;
        return jdbmbucket;
    }

    protected synchronized LRUEntry loadBucket(int i)
        throws IOException
    {
        jdbmBucket jdbmbucket = null;
        if(loaded_buckets >= cache_size)
        {
            trace("*** removing bucket from cache !");
            jdbmbucket = unloadBucket();
        } else
        {
            trace("*** filling cache.");
            loaded_buckets++;
            jdbmbucket = new jdbmBucket(this, i, -1);
        }
        fd.seek(i);
        if(fd.read(buffer, 0, buffer.length) != buffer.length)
        {
            throw new IOException("invalid read length.");
        } else
        {
            jdbmBucket.restore(new DataInputStream(new ByteArrayInputStream(buffer)), i, jdbmbucket);
            return list.addEntry(jdbmbucket);
        }
    }

    private synchronized jdbmBucket lookupBucket(int i)
        throws IOException
    {
        int j = i >>> 31 - dir_bits;
        int k = diridx[j];
        int _tmp = k / block_size;
        LRUEntry lruentry = list.lookupBucket(k);
        if(lruentry == null)
            lruentry = loadBucket(k);
        list.notifyUses(lruentry);
        return lruentry.bucket;
    }

    public void store(byte abyte0[], byte abyte1[], int i)
        throws IOException
    {
        int j = hash(abyte0);
        jdbmBucket jdbmbucket = lookupBucket(j);
        jdbmBucketElement jdbmbucketelement = jdbmbucket.lookup(abyte0, j);
        if(jdbmbucketelement != null)
            if(i == 1)
                jdbmbucket.delete(jdbmbucketelement);
            else
                return;
        if(jdbmbucket.count == bucket_elems)
        {
            splitBucket(j, jdbmbucket);
            jdbmbucket = lookupBucket(j);
        }
        jdbmbucket.add(j, abyte0, abyte1);
    }

    public byte[] lookup(byte abyte0[])
        throws IOException