Subversion Repositories Code-Repo

Rev

Rev 96 | Blame | Compare with Previous | Last modification | View Log | RSS feed

import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.RandomAccessFile;

public class LRUBuffer {
        
        private int blockSize = 0;
        
        private int cacheHit = 0;
        private int cacheMiss = 0;
        private int diskReads = 0;
        private int diskWrites = 0;
        
        private String dataFile;
        private String statFile;
        
        private BufferBlock bufferHead;
        
        private RandomAccessFile file;
        
        public LRUBuffer(String datafile, String statfile, int size, int blocksize) {
                this.dataFile = datafile;
                this.statFile = statfile;
                this.blockSize = blocksize;
                
                // Allocates a new doubly linked list of BufferBlocks
                // The buffer will have at least one block
                bufferHead = new BufferBlock(blockSize);
                BufferBlock cur = bufferHead;
                for (int i = 0; i < size-1; i++) {
                        BufferBlock newBlock = new BufferBlock(blockSize);
                        cur.setNext(newBlock);
                        newBlock.setPrev(cur);
                        cur = newBlock;
                }
                
                // Open access to the datafile
                try {
                        file = new RandomAccessFile(dataFile, "rw");
                        file.setLength(0);
                } catch (FileNotFoundException e) {
                        e.printStackTrace();
                } catch (IOException e) {
                        e.printStackTrace();
                }
        }
        
        /** Recursive function to copy length number of bytes from file at startAddress
         * to offset position in out
         * 
         * @param out Destination array to copy bytes to
         * @param offset Offset of position to write to in the destination array
         * @param startAddress Starting address on disk to copy bytes from
         * @param length Number of bytes to copy to the destination array
         * @return
         */
        public boolean getBytes(byte[] out, int offset, long startAddress, int length) {
                BufferBlock cur = bufferHead;
                
                // If the requested length doesnt extends to the next block
                if (startAddress % blockSize + length < blockSize) {
                        // Check if address is already in a buffer block
                        while (cur != null && cur.getStartAddress() != -1) {
                                if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) {
                                        // Address is in block
                                        cacheHit++;
                                        // Bring current block to front of list
                                        bringToFront(cur);
                                        // Get data
                                        cur.getBytes(out, offset, (int)startAddress % blockSize, length);
                                        return true;
                                }
                                cur = cur.getNext();
                        }
                        
                        // Address is not in buffer, read new block from disk
                        cacheMiss++;
                        cur = readFromDisk(startAddress);
                        insertToFront(cur);
                        // Get data from block
                        cur.getBytes(out, offset, (int)startAddress % blockSize, length);
                        return true;
                // If the requested length extends to the next block
                } else {
                        int bytesToRead = 0;
                        // Check if address is already in a buffer block
                        while (cur != null && cur.getStartAddress() != -1) {
                                if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) {
                                        // Address is in block
                                        cacheHit++;
                                        // Bring current block to front of list
                                        bringToFront(cur);
                                        // Read in from address to end of block
                                        bytesToRead = blockSize - (int)startAddress % blockSize;
                                        cur.getBytes(out, offset, (int)startAddress % blockSize, bytesToRead);
                                        offset += bytesToRead;
                                        // Get data from the next consecutive block
                                        getBytes(out, offset, startAddress + bytesToRead, length - bytesToRead);
                                        return true;
                                }
                                cur = cur.getNext();
                        }
                        
                        // Address is not in buffer, read new block from disk
                        cacheMiss++;
                        cur = readFromDisk(startAddress);
                        insertToFront(cur);
                        // Read in from address to end of block
                        bytesToRead = blockSize - (int)startAddress % blockSize;
                        cur.getBytes(out, offset, (int)startAddress % blockSize, bytesToRead);
                        offset += bytesToRead;
                        // Get data from the next consecutive block
                        getBytes(out, offset, startAddress + bytesToRead, length - bytesToRead);
                        return true;
                }
        }
        
        /** Recursive function to copy length number of bytes from in to file at startAddress
         * 
         * @param in Input array to copy bytes from
         * @param startAddress Starting address on disk to copy bytes to
         * @param length Number of bytes to copy from in to disk
         * @return
         */
        public boolean putBytes(byte[] in, int offset, long startAddress, int length) {
                BufferBlock cur = bufferHead;
                
                // If the requested length doesnt extends to the next block
                if (startAddress % blockSize + length <= blockSize) {
                        // Check if address is already in a buffer block
                        while (cur != null && cur.getStartAddress() != -1) {
                                if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) {
                                        // Address is in block
                                        cacheHit++;
                                        // Bring current block to front of list
                                        bringToFront(cur);
                                        // Put data into block
                                        cur.setBytes(in, offset, (int)startAddress % blockSize, length);
                                        cur.setDirtyBit(true);
                                        return true;
                                }
                                cur = cur.getNext();
                        }
                        
                        // Address is not in buffer, read new block from disk
                        cacheMiss++;
                        cur = readFromDisk(startAddress);
                        insertToFront(cur);
                        // Put data into block
                        cur.setBytes(in, offset, (int)startAddress % blockSize, length);
                        cur.setDirtyBit(true);
                        return true;
                // If the requested length extends to the next block
                } else {
                        int bytesToWrite = 0;
                        // Check if address is already in a buffer block
                        while (cur != null && cur.getStartAddress() != -1) {
                                if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) {
                                        // Address is in block
                                        cacheHit++;
                                        // Bring current block to front of list
                                        bringToFront(cur);
                                        // Put in data until end of block
                                        bytesToWrite = blockSize - (int)startAddress % blockSize;
                                        cur.setBytes(in, offset, (int)startAddress % blockSize, bytesToWrite);
                                        cur.setDirtyBit(true);
                                        startAddress += bytesToWrite;
                                        // Put remaining data into the next consecutive block
                                        putBytes(in, offset + bytesToWrite, startAddress, length - bytesToWrite);
                                        return true;
                                }
                                cur = cur.getNext();
                        }
                        
                        // Address is not in buffer, read new block from disk
                        cacheMiss++;
                        cur = readFromDisk(startAddress);
                        insertToFront(cur);
                        // Put in data until end of block
                        bytesToWrite = blockSize - (int)startAddress % blockSize;
                        cur.setBytes(in, offset, (int)startAddress % blockSize, bytesToWrite);
                        cur.setDirtyBit(true);
                        startAddress += bytesToWrite;
                        // Put remaining data into the next consecutive block
                        putBytes(in, offset + bytesToWrite, startAddress, length - bytesToWrite);
                        return true;
                }
        }
        
        /** Brings a block currently in the list to the front of the list */
        private void bringToFront(BufferBlock block) {
                // If block is already in front, return
                if (block == bufferHead)
                        return;
                
                if (block.getPrev() != null)
                        block.getPrev().setNext(block.getNext());
                if (block.getNext() != null)
                        block.getNext().setPrev(block.getPrev());
                block.setPrev(null);
                bufferHead.setPrev(block);
                block.setNext(bufferHead);
                bufferHead = block;
        }
        
        /** Inserts a new block into the front of the list */
        private void insertToFront(BufferBlock block) {
                // Set head as current block
                block.setPrev(null);
                bufferHead.setPrev(block);
                block.setNext(bufferHead);
                bufferHead = block;
                // Write last block in list to disk if dirty bit is set
                // Last block is also removed
                BufferBlock cur = bufferHead;
                while (cur.getNext() != null) {
                        cur = cur.getNext();
                }
                cur.getPrev().setNext(null);
                if (cur.isDirtyBit()) {
                        writeToDisk(cur);
                }
        }

        /** Reads a new block from disk given an address */
        private BufferBlock readFromDisk(long address) {
                diskReads++;
                byte[] data = new byte[blockSize];
                long offset = address / blockSize;
                offset = offset * blockSize;
                try {
                        file.seek(offset);
                        file.read(data);
                } catch (IOException e) {
                        e.printStackTrace();
                }
                
                // Pass read block into a new block
                BufferBlock newBlock = new BufferBlock(blockSize);
                newBlock.setBytes(data, 0, 0, blockSize);
                newBlock.setStartAddress(offset);
                
                return newBlock;
        }
        
        /** Writes the specified block to disk */
        private void writeToDisk(BufferBlock block) {
                diskWrites++;
                byte[] data = new byte[blockSize];
                block.getBytes(data, 0, 0, blockSize);
                try {
                        file.seek(block.getStartAddress());
                        file.write(data);
                } catch (IOException e) {
                        e.printStackTrace();
                }
        }
        
        /** Flush the buffer by writing all blocks in buffer to disk */
        public void flushBuffer() {
                BufferBlock cur = bufferHead;
                while (cur != null) {
                        if (cur.isDirtyBit()) {
                                writeToDisk(cur);
                        }
                        cur = cur.getNext();
                }
                
                try {
                        file.close();
                } catch (IOException e) {
                        e.printStackTrace();
                }
        }
        
        /** Write stats to stat file */
        public void writeStats(long time) {
                try {
                        BufferedWriter out = new BufferedWriter(new FileWriter(statFile, true));
                        StringBuilder str = new StringBuilder();
                        str.append("Datafile: " + dataFile + " | ");
                        str.append("Cache Hits: " + cacheHit + " | ");
                        str.append("Cache Misses: " + cacheMiss + " | ");
                        str.append("Disk Reads: " + diskReads + " | ");
                        str.append("Disk Writes: " + diskWrites + " | ");
                        str.append("Time to Sort: " + time + "\n");
                        out.write(str.toString());
                        out.close();
                } catch (IOException e) {
                        e.printStackTrace();
                }
        }
        
        public void printBlockIDs() {
                BufferBlock cur = bufferHead;
                System.out.print("Buffer Pool Blocks: ");
                while (cur != null && cur.getStartAddress() != -1) {
//                      System.out.print(cur.getStartAddress() + " ; ");
                        System.out.print(cur.getStartAddress() / blockSize + " ; ");
                        cur = cur.getNext();
                }
                System.out.print("\n");
        }
}