| ArrayFreeSpaceList.java |
/* Copyright (C) 2009 CSE,IIT Bombay http://www.cse.iitb.ac.in
This file is part of the ConStore open source storage facility for concept-nets.
ConStore is free software and distributed under the
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License;
you can copy, distribute and transmit the work
with the work attribution in the manner specified by the author or licensor.
You may not use this work for commercial purposes and may not alter,
transform, or build upon this work.
Please refer the legal code of the license, available at
http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode
ConStore is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. */
package iitb.con.util;
import iitb.con.io.BufferedFileAdapter;
import iitb.con.io.IOAdapter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.LongBuffer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* ArrayFreeSpaceList is the list which maintains the information about the free blocks in a file. <p>
* The format of the list is : {[Start Location], [End Location]} <br>
* where the start location and end location indicates the block start and end in the file.
*
* @author Prathab K
*
*/
public class ArrayFreeSpaceList implements FreeSpaceList{
/** Location list maintains the start and end location */
private List<Entry> locationList;
/** free block size list */
private List<Long> sizeList;
/** Free space list file handle */
private IOAdapter freeSpaceListFile;
/**
* Reads and initializes the information about the free blocks space
* @param fileName free space list file name
* @param mode opening mode (r, rw)
* @throws FileNotFoundException if file not found
* @throws IOException if file operation fails
*/
public ArrayFreeSpaceList(String fileName, String mode)
throws FileNotFoundException, IOException
{
File file = new File(fileName);
int length = (int)file.length();
freeSpaceListFile = new BufferedFileAdapter(fileName, mode, length);
locationList = new ArrayList<Entry>();
sizeList = new ArrayList<Long>();
read(length);
}
/**
* Reads the information of free blocks.
* It decodes the blocks start and end location information from the file
* and computes its size. Then initializes the location and size list respectively.
* @param length file length to be read
* @throws IOException if file operation fails
*/
private void read(int length) throws IOException{
ByteBuffer buffer = freeSpaceListFile.readIntoBuffer(0);
buffer.rewind();
LongBuffer longBuf = buffer.asLongBuffer();
while (longBuf.hasRemaining()) {
long sloc = longBuf.get();
long eloc = longBuf.get();
Entry e = new Entry(sloc, eloc);
locationList.add(e);
sizeList.add(eloc - sloc + 1);
//TODO: throw proper exception for invalid data format
}
}
/**
* Returns the free block location
* @param size request block size
* @return free block location
*/
public long getFreeBlock(long size){
int index = Collections.binarySearch(sizeList, size);
if(index >= 0) { //for exact match
Entry e = locationList.get(index);
remove(index);
return e.startLocation;
}else {
int nextIndex = - (index + 1);
if(nextIndex < sizeList.size()) {
Entry e = locationList.get(nextIndex);
long loc = e.startLocation;
e.startLocation = e.startLocation + size;
update(nextIndex, e, (e.endLocation - e.startLocation + 1));
return loc;
}else {
//TODO: throw exception
}
}
return 0;
}
/**
* Updates the entry in the location and size list
* @param index index in the list
* @param e {@link Entry}
* @param size free block size
*/
private void update(int index, Entry e, long size) {
locationList.set(index, e);
sizeList.set(index, size);
}
/**
* Inserts the entry in the location and size list
* @param e {@link Entry}
*/
private void insert(Entry e) {
long size = e.endLocation - e.startLocation + 1;
int index = Collections.binarySearch(sizeList, size); //TODO: check for Zero
int nextIndex = -1;
if(index < 0)
nextIndex = - (index + 1);
else
nextIndex = index;
locationList.add(nextIndex, e);
sizeList.add(nextIndex, size);
}
/**
* Removes the entry in the location and size list
*@param index index in the list
*/
private void remove(int index) {
sizeList.remove(index);
locationList.remove(index);
}
/**
* Frees the specified block in the file
* @param location block location
* @param size block size
* @return <tt>true</tt> on success
*/
public boolean freeTheBlock(long location, long size) {
Entry e = new Entry(location, location + size - 1);
insert(e);
return true;
}
/**
* Class Entry is used to hold the start and end location of a block in a file.
*
* @author Prathab K
*
*/
private static class Entry implements Comparable<Entry> {
/** Block start location */
long startLocation;
/** Block end location */
long endLocation;
Entry(long startLocation, long endLocation) {
this.startLocation = startLocation;
this.endLocation = endLocation;
}
public int compareTo(Entry e) {
if(this.startLocation > e.startLocation)
return 1;
else if(this.startLocation < e.startLocation)
return -1;
else
return 0;
}
}
/**
* Commits the changes to the free space list file
* @throws IOException if file operation fails
*/
public void commit() throws IOException {
coalesceFreeSpace();
ByteBuffer bbuf = ByteBuffer.allocate(locationList.size() * 16);
for(Entry e : locationList) {
bbuf.putLong(e.startLocation);
bbuf.putLong(e.endLocation);
}
freeSpaceListFile.write(bbuf, 0);
}
/**
* Coalesces the free blocks.
* The locationList is sorted and all the free blocks
* are coalesced in single iteration
*
*/
private void coalesceFreeSpace() {
Collections.sort(locationList);
int length = locationList.size();
int index = 0;
List<Entry> tempLocationList = new ArrayList<Entry>();
List<Long> tempSizeList = new ArrayList<Long>();
if(length > 1) {
Entry first = locationList.get(0);
Entry e = new Entry(first.startLocation, first.endLocation);
long size = sizeList.get(0);
for(int i = 1; i < length; i++) {
Entry next = locationList.get(i);
if(e.endLocation == (next.startLocation - 1)) {
e.endLocation = next.endLocation;
size += (next.endLocation = next.startLocation) + 1;
} else {
tempLocationList.add(index, e);
tempSizeList.add(index, new Long(size));
index++;
e = new Entry(next.startLocation, next.endLocation);
size = sizeList.get(i);
}
}
tempLocationList.add(index, e);
tempSizeList.add(index, new Long(size));
locationList.clear();
sizeList.clear();
locationList = tempLocationList;
sizeList = tempSizeList;
}
}
/**
* Closes the free space list file
* @throws IOException if file operation fails
*/
public void close() throws IOException {
freeSpaceListFile.close();
}
/**
* Dumps the free space list contents
*/
public void dumpFreeSpaceList(){
int i = 0;
for(Entry e : locationList) {
System.out.println(e.startLocation + "-" + e.endLocation + " = " + sizeList.get(i++));
}
}
}