o Initial import of a heap file manager.

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;
+    }
+}