From b1271a305e0a3bb07cf6cafaea25a539ffd9ab5e Mon Sep 17 00:00:00 2001 From: Trygve Laugstøl Date: Sun, 15 Sep 2013 00:21:21 +0200 Subject: o Initial import of a heap file manager. --- README.md | 35 +++++++ pom.xml | 19 ++++ src/main/java/io/trygvis/btree/HeapFile.java | 58 +++++++++++ src/main/java/io/trygvis/btree/HeapPage.java | 123 +++++++++++++++++++++++ src/test/java/io/trygvis/btree/HeapFileTest.java | 27 +++++ src/test/java/io/trygvis/btree/HeapPageTest.java | 70 +++++++++++++ 6 files changed, 332 insertions(+) create mode 100644 README.md create mode 100644 pom.xml create mode 100644 src/main/java/io/trygvis/btree/HeapFile.java create mode 100644 src/main/java/io/trygvis/btree/HeapPage.java create mode 100644 src/test/java/io/trygvis/btree/HeapFileTest.java create mode 100644 src/test/java/io/trygvis/btree/HeapPageTest.java diff --git a/README.md b/README.md new file mode 100644 index 0000000..6c93395 --- /dev/null +++ b/README.md @@ -0,0 +1,35 @@ +Heap File +========= + +Page Header +----------- + + * int freePosition + +Item Header +----------- + + * int size + +A heap page looks like this: + + |-------------| + | Page Header | + |-------------| + | | + | free space | + | | + |-------------| <-- freePosition + | Item #2 | + | data | + |-------------| + | Item #2 | + | header | + |-------------| + | Item #1 | + | data | + |-------------| + | Item #1 | + | header | + |-------------| + diff --git a/pom.xml b/pom.xml new file mode 100644 index 0000000..c444f96 --- /dev/null +++ b/pom.xml @@ -0,0 +1,19 @@ + + + 4.0.0 + + io.trygvis.btree + btree + 1.0-SNAPSHOT + + + + junit + junit + 4.11 + test + + + diff --git a/src/main/java/io/trygvis/btree/HeapFile.java b/src/main/java/io/trygvis/btree/HeapFile.java new file mode 100644 index 0000000..7a960c8 --- /dev/null +++ b/src/main/java/io/trygvis/btree/HeapFile.java @@ -0,0 +1,58 @@ +package io.trygvis.btree; + +import java.io.Closeable; +import java.io.File; +import java.io.IOException; +import java.io.RandomAccessFile; +import java.nio.ByteBuffer; +import java.nio.channels.FileChannel; + +import static io.trygvis.btree.HeapPage.blankHeapPage; +import static java.nio.ByteBuffer.allocateDirect; + +public class HeapFile implements Closeable { + private final int PAGE_SIZE; + + private final RandomAccessFile file; + private final FileChannel channel; + + public HeapFile(int PAGE_SIZE, File file) throws IOException { + this.PAGE_SIZE = PAGE_SIZE; + this.file = new RandomAccessFile(file, "rw"); + + channel = this.file.getChannel(); + } + + @Override + public void close() throws IOException { + channel.force(true); + file.close(); + } + + public HeapPage loadPage(int page) throws IOException { + ByteBuffer buffer = allocateDirect(PAGE_SIZE); + + channel.read(buffer, page * PAGE_SIZE); + + return HeapPage.heapPageFromBytes(page, buffer); + } + + public void writePage(HeapPage page) throws IOException { + long position; + if (page.pageNumber == -1) { + position = file.length(); + } else { + position = page.pageNumber * PAGE_SIZE; + } + channel.write(page.bytes, position); + channel.force(true); + } + + public long pageCount() throws IOException { + return file.length() / PAGE_SIZE; + } + + public HeapPage blankPage() { + return blankHeapPage(allocateDirect(PAGE_SIZE)); + } +} diff --git a/src/main/java/io/trygvis/btree/HeapPage.java b/src/main/java/io/trygvis/btree/HeapPage.java new file mode 100644 index 0000000..499a244 --- /dev/null +++ b/src/main/java/io/trygvis/btree/HeapPage.java @@ -0,0 +1,123 @@ +package io.trygvis.btree; + +import java.nio.ByteBuffer; +import java.util.Iterator; +import java.util.NoSuchElementException; + +public class HeapPage { + public static final int headerSize = 4; + public static final int FREE_POSITION_INDEX = 0; + + public static final int itemSize = 4; + + // The page number in a heap file + final long pageNumber; + final ByteBuffer bytes; + int freePosition; + + private HeapPage(long pageNumber, ByteBuffer bytes, int freePosition) { + this.pageNumber = pageNumber; + this.bytes = bytes; + this.freePosition = freePosition; + } + + public static HeapPage heapPageFromBytes(int pageNumber, ByteBuffer bytes) { + int freePosition = bytes.getInt(); + return new HeapPage(pageNumber, bytes, freePosition); + } + + public static HeapPage blankHeapPage(ByteBuffer bytes) { + return new HeapPage(-1, bytes, bytes.capacity()); + } + + public void append(byte[] item) { +// System.out.println("io.trygvis.btree.HeapPage.append"); + + int bytesFree = bytesFree(); + int bytesRequested = item.length; + + if (bytesRequested > bytesFree) { + throw new PageOverflowException(bytesFree, bytesRequested); + } + + freePosition -= itemSize; + bytes.position(freePosition); + bytes.putInt(item.length); + freePosition -= bytesRequested; + bytes.position(freePosition); + bytes.put(item); + + bytes.putInt(FREE_POSITION_INDEX, freePosition); + } + + public int bytesFree() { + return freePosition - headerSize; + } + + public Iterable bufferIterator() { + return new Iterable() { + @Override + public Iterator iterator() { + return new Iterator() { + private int position; + + private ByteBuffer next; + + { + position = bytes.capacity(); + next = findNext(); + } + + private ByteBuffer findNext() { + if (position == headerSize) { + return null; + } + + int size = bytes.getInt(position - itemSize); + + if (size == 0) { + return null; + } + + position -= itemSize + size; + ByteBuffer copy = bytes.duplicate(); + copy.position(position); + copy.limit(position + size); + return copy.slice(); + } + + public boolean hasNext() { + return next != null; + } + + @Override + public ByteBuffer next() { + if (next == null) { + throw new NoSuchElementException(); + } + + ByteBuffer n = next; + next = findNext(); + return n; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + }; + } + + public static class PageOverflowException extends RuntimeException { + public final int bytesFree; + public final int bytesRequested; + + public PageOverflowException(int bytesFree, int bytesRequested) { + super("Not enough room on page, bytes free=" + bytesFree + ", requested = " + bytesRequested); + this.bytesFree = bytesFree; + this.bytesRequested = bytesRequested; + } + } +} diff --git a/src/test/java/io/trygvis/btree/HeapFileTest.java b/src/test/java/io/trygvis/btree/HeapFileTest.java new file mode 100644 index 0000000..a9105bb --- /dev/null +++ b/src/test/java/io/trygvis/btree/HeapFileTest.java @@ -0,0 +1,27 @@ +package io.trygvis.btree; + +import org.junit.Test; + +import java.io.File; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +public class HeapFileTest { + + @Test + public void testBasic() throws Exception { + int pageSize = 128; + File f = new File("target/heap"); + if (f.exists()) { + assertTrue(f.delete()); + } + + HeapFile file = new HeapFile(pageSize, f); + + assertEquals(0, file.pageCount()); + HeapPage page = file.blankPage(); + file.writePage(page); + assertEquals(1, file.pageCount()); + } +} diff --git a/src/test/java/io/trygvis/btree/HeapPageTest.java b/src/test/java/io/trygvis/btree/HeapPageTest.java new file mode 100644 index 0000000..e845a16 --- /dev/null +++ b/src/test/java/io/trygvis/btree/HeapPageTest.java @@ -0,0 +1,70 @@ +package io.trygvis.btree; + +import org.junit.Test; + +import java.nio.ByteBuffer; +import java.util.Iterator; + +import static io.trygvis.btree.HeapPage.*; +import static org.junit.Assert.*; + +public class HeapPageTest { + + int pageSize = 128; + + @Test + public void testBasic() { + ByteBuffer buffer = ByteBuffer.allocate(pageSize); + + HeapPage page = HeapPage.blankHeapPage(buffer); + assertEquals(pageSize - headerSize, page.bytesFree()); + + int itemCount = 6; + byte[] object = new byte[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf}; + + for (int i = 0; i < itemCount; i++) { + page.append(object); + assertEquals("i=" + i, pageSize - headerSize - (object.length + itemSize) * (i + 1), page.bytesFree()); + } + + try { + page.append(object); + fail("Expected PageOverflowException"); + } catch (PageOverflowException e) { + assertEquals(pageSize - headerSize - itemCount * (object.length + itemSize), e.bytesFree); + assertEquals(object.length, e.bytesRequested); + } + + { + ByteBuffer expectedBuffer = ByteBuffer.allocate(pageSize); + int position = pageSize - itemCount * (object.length + itemSize); + expectedBuffer.putInt(position); + expectedBuffer.position(position); + for (int i = 0; i < itemCount; i++) { + expectedBuffer.put(object); + expectedBuffer.putInt(object.length); + } + assertEquals(pageSize, expectedBuffer.position()); + + byte[] expectedArray = expectedBuffer.array(); + byte[] actualArray = buffer.array(); + assertArrayEquals(expectedArray, actualArray); + } + + { + Iterator it = page.bufferIterator().iterator(); + for (int i = 0; i < itemCount; i++) { + assertTrue(it.hasNext()); + ByteBuffer bb = it.next(); + assertArrayEquals(object, toArray(bb)); + } + assertFalse(it.hasNext()); + } + } + + private byte[] toArray(ByteBuffer bb) { + byte[] bytes = new byte[bb.limit()]; + bb.get(bytes); + return bytes; + } +} -- cgit v1.2.3