aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTrygve Laugstøl <trygvis@inamo.no>2013-09-15 00:21:21 +0200
committerTrygve Laugstøl <trygvis@inamo.no>2013-09-15 00:21:21 +0200
commitb1271a305e0a3bb07cf6cafaea25a539ffd9ab5e (patch)
tree697c47fb630ad317d45fd8f952613360ebee5db7
downloadbtree-b1271a305e0a3bb07cf6cafaea25a539ffd9ab5e.tar.gz
btree-b1271a305e0a3bb07cf6cafaea25a539ffd9ab5e.tar.bz2
btree-b1271a305e0a3bb07cf6cafaea25a539ffd9ab5e.tar.xz
btree-b1271a305e0a3bb07cf6cafaea25a539ffd9ab5e.zip
o Initial import of a heap file manager.
-rw-r--r--README.md35
-rw-r--r--pom.xml19
-rw-r--r--src/main/java/io/trygvis/btree/HeapFile.java58
-rw-r--r--src/main/java/io/trygvis/btree/HeapPage.java123
-rw-r--r--src/test/java/io/trygvis/btree/HeapFileTest.java27
-rw-r--r--src/test/java/io/trygvis/btree/HeapPageTest.java70
6 files changed, 332 insertions, 0 deletions
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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+
+ <groupId>io.trygvis.btree</groupId>
+ <artifactId>btree</artifactId>
+ <version>1.0-SNAPSHOT</version>
+
+ <dependencies>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.11</version>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
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<ByteBuffer> bufferIterator() {
+ return new Iterable<ByteBuffer>() {
+ @Override
+ public Iterator<ByteBuffer> iterator() {
+ return new Iterator<ByteBuffer>() {
+ 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<ByteBuffer> 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;
+ }
+}