wipHEADmaster

11 files changed, 317 insertions, 22 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..5231862
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+.idea
+*.iml
+target
diff --git a/README.md b/README.md
index 6c93395..9062054 100644
--- a/README.md
+++ b/README.md
@@ -33,3 +33,20 @@ A heap page looks like this:
     |   header    |
     |-------------|
 
+BTree File
+==========
+
+BTree Item
+----------
+
+* `bytes[] key`
+* `int pageNo` - the page in the heap that contains the value.
+
+A heap page can contain many items so the heap page has to be scanned.
+
+
+Example BTree page
+------------------
+
+    [1, #], [7, #], [9, #]
+
diff --git a/pom.xml b/pom.xml
index c444f96..e7c9048 100644
--- a/pom.xml
+++ b/pom.xml
@@ -3,7 +3,11 @@
          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>
-
+  <parent>
+    <groupId>io.trygvis</groupId>
+    <artifactId>trygvis-parent</artifactId>
+    <version>1</version>
+  </parent>
   <groupId>io.trygvis.btree</groupId>
   <artifactId>btree</artifactId>
   <version>1.0-SNAPSHOT</version>
diff --git a/src/main/java/io/trygvis/btree/Bits.java b/src/main/java/io/trygvis/btree/Bits.java
new file mode 100644
index 0000000..c38e865
--- /dev/null
+++ b/src/main/java/io/trygvis/btree/Bits.java
@@ -0,0 +1,11 @@
+package io.trygvis.btree;
+
+public class Bits {
+    public static byte[] toBytes(int i) {
+        return new byte[]{(byte) (i >> 24), (byte) (i >> 16), (byte) (i >> 8), (byte) i};
+    }
+
+    public static int intFromBytes(byte[] bytes) {
+        return (bytes[0] << 24) + (bytes[1] << 16) + (bytes[2] << 8) + bytes[2];
+    }
+}
diff --git a/src/main/java/io/trygvis/btree/BtreeFile.java b/src/main/java/io/trygvis/btree/BtreeFile.java
new file mode 100644
index 0000000..7300b5e
--- /dev/null
+++ b/src/main/java/io/trygvis/btree/BtreeFile.java
@@ -0,0 +1,63 @@
+package io.trygvis.btree;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.Iterator;
+
+public class BtreeFile implements Closeable {
+    private final HeapFile heap;
+    private final int keySize;
+    private final int itemsPerPage;
+
+    public BtreeFile(HeapFile heap, int keySize) throws IOException {
+        this.heap = heap;
+        this.keySize = keySize;
+        itemsPerPage = heap.PAGE_SIZE / keySize;
+
+        // Make sure we always have a page #0.
+        if (heap.pageCount() == 0) {
+            HeapPage root = heap.blankPage();
+            heap.writePage(root);
+        }
+    }
+
+    public void add(byte[] key, byte[] value) throws IOException {
+        HeapPage page = heap.loadPage(0);
+
+        ByteBuffer k = ByteBuffer.wrap(key);
+        ByteBuffer current;
+        ByteBuffer smaller;
+
+        Iterator<ByteBuffer> it = page.items().iterator();
+
+        int position = 0;
+
+        while(it.hasNext()) {
+            current = it.next();
+
+            int diff = k.compareTo(current);
+
+            if(diff < 0) {
+                break;
+            }
+        }
+
+//        page.prepend();
+    }
+
+    @Override
+    public void close() throws IOException {
+        heap.close();
+    }
+
+    public static class BtreeItem {
+        private final byte[] from;
+        private final int page;
+
+        public BtreeItem(byte[] from, int page) {
+            this.from = from;
+            this.page = page;
+        }
+    }
+}
diff --git a/src/main/java/io/trygvis/btree/BtreeMap.java b/src/main/java/io/trygvis/btree/BtreeMap.java
new file mode 100644
index 0000000..06c348f
--- /dev/null
+++ b/src/main/java/io/trygvis/btree/BtreeMap.java
@@ -0,0 +1,97 @@
+package io.trygvis.btree;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+
+public class BtreeMap<K, V> implements Map<K, V>, Closeable {
+
+    public static interface Serializer<A> {
+        byte[] toBytes(A a);
+
+        A fromBytes(byte[] bytes);
+    }
+
+    private final BtreeFile tree;
+    private final Serializer<K> kSerializer;
+    private final Serializer<V> vSerializer;
+
+    public BtreeMap(BtreeFile tree, Serializer<K> kSerializer, Serializer<V> vSerializer) {
+        this.tree = tree;
+        this.kSerializer = kSerializer;
+        this.vSerializer = vSerializer;
+    }
+
+    @Override
+    public void close() throws IOException {
+        tree.close();
+    }
+
+    @Override
+    public int size() {
+        return 0;
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return size() == 0;
+    }
+
+    @Override
+    public boolean containsKey(Object key) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean containsValue(Object value) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public V get(Object key) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public V put(K key, V value) {
+        try {
+            tree.add(kSerializer.toBytes(key), vSerializer.toBytes(value));
+
+            return null;
+        } catch (IOException e) {
+            throw new RuntimeException(e);
+        }
+    }
+
+    @Override
+    public V remove(Object key) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void putAll(Map<? extends K, ? extends V> m) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void clear() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Set<K> keySet() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Collection<V> values() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Set<Entry<K, V>> entrySet() {
+        throw new UnsupportedOperationException();
+    }
+}
diff --git a/src/main/java/io/trygvis/btree/HeapFile.java b/src/main/java/io/trygvis/btree/HeapFile.java
index 6bd0451..83b2f48 100644
--- a/src/main/java/io/trygvis/btree/HeapFile.java
+++ b/src/main/java/io/trygvis/btree/HeapFile.java
@@ -11,7 +11,7 @@ import static io.trygvis.btree.HeapPage.blankHeapPage;
 import static java.nio.ByteBuffer.allocateDirect;
 
 public class HeapFile implements Closeable {
-    private final int PAGE_SIZE;
+    public final int PAGE_SIZE;
 
     private final RandomAccessFile file;
     private final FileChannel channel;
diff --git a/src/main/java/io/trygvis/btree/HeapPage.java b/src/main/java/io/trygvis/btree/HeapPage.java
index a931260..32ba0ef 100644
--- a/src/main/java/io/trygvis/btree/HeapPage.java
+++ b/src/main/java/io/trygvis/btree/HeapPage.java
@@ -53,11 +53,27 @@ public class HeapPage {
         bytes.putInt(FREE_POSITION_INDEX, freePosition);
     }
 
+    public void prepend(byte[] item) {
+        int bytesFree = bytesFree();
+        int bytesRequested = item.length;
+
+        if (bytesRequested > bytesFree) {
+            throw new PageOverflowException(bytesFree, bytesRequested);
+        }
+
+        byte[] array = bytes.array();
+        int offset = bytes.arrayOffset();
+
+        System.arraycopy(array, offset, array, offset + bytesRequested, bytesRequested);
+
+        freePosition -= itemSize;
+    }
+
     public int bytesFree() {
         return freePosition - headerSize;
     }
 
-    public Iterable<ByteBuffer> bufferIterator() {
+    public Iterable<ByteBuffer> items() {
         return new Iterable<ByteBuffer>() {
             @Override
             public Iterator<ByteBuffer> iterator() {
diff --git a/src/test/java/io/trygvis/btree/BtreeMapTest.java b/src/test/java/io/trygvis/btree/BtreeMapTest.java
new file mode 100644
index 0000000..3c771a8
--- /dev/null
+++ b/src/test/java/io/trygvis/btree/BtreeMapTest.java
@@ -0,0 +1,45 @@
+package io.trygvis.btree;
+
+import org.junit.Test;
+
+import java.io.File;
+import java.nio.ByteBuffer;
+
+import static io.trygvis.btree.Bits.intFromBytes;
+import static io.trygvis.btree.HeapTest.Person.randomPerson;
+import static io.trygvis.btree.TestUtils.deleteFile;
+
+public class BtreeMapTest {
+
+    @Test
+    public void testBasic() throws Exception {
+        File f = new File("target/btreemap");
+        BtreeMap<Integer, HeapTest.Person> map = new BtreeMap<>(new BtreeFile(new HeapFile(128, deleteFile(f)), 4), new IntegerSerializer(), new PersonSerializer());
+
+        map.put(1, randomPerson());
+    }
+
+    private static class IntegerSerializer implements BtreeMap.Serializer<Integer> {
+        @Override
+        public byte[] toBytes(Integer integer) {
+            return Bits.toBytes(integer);
+        }
+
+        @Override
+        public Integer fromBytes(byte[] bytes) {
+            return intFromBytes(bytes);
+        }
+    }
+
+    private static class PersonSerializer implements BtreeMap.Serializer<HeapTest.Person> {
+        @Override
+        public byte[] toBytes(HeapTest.Person person) {
+            return person.toBytes();
+        }
+
+        @Override
+        public HeapTest.Person fromBytes(byte[] bytes) {
+            return HeapTest.Person.fromBytes(ByteBuffer.wrap(bytes));
+        }
+    }
+}
diff --git a/src/test/java/io/trygvis/btree/HeapPageTest.java b/src/test/java/io/trygvis/btree/HeapPageTest.java
index e845a16..b158880 100644
--- a/src/test/java/io/trygvis/btree/HeapPageTest.java
+++ b/src/test/java/io/trygvis/btree/HeapPageTest.java
@@ -3,7 +3,9 @@ package io.trygvis.btree;
 import org.junit.Test;
 
 import java.nio.ByteBuffer;
+import java.util.ArrayList;
 import java.util.Iterator;
+import java.util.List;
 
 import static io.trygvis.btree.HeapPage.*;
 import static org.junit.Assert.*;
@@ -19,30 +21,43 @@ public class HeapPageTest {
         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};
+        List<byte[]> objects = new ArrayList<>();
+        byte[] appendObject = new byte[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf};
+        int objectSize = 16;
 
-        for (int i = 0; i < itemCount; i++) {
-            page.append(object);
-            assertEquals("i=" + i, pageSize - headerSize - (object.length + itemSize) * (i + 1), page.bytesFree());
+        for (int i = 0; i < 5; i++) {
+            page.append(appendObject);
+            objects.add(appendObject);
+            assertEquals("i=" + i, pageSize - headerSize - (appendObject.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);
+        byte[] prependObject = new byte[]{0xf, 0xe, 0xd, 0xc, 0xb, 0xa, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+        page.prepend(prependObject);
+        objects.add(0, prependObject);
+
+//        try {
+//            page.append(object);
+//            fail("Expected PageOverflowException");
+//        } catch (PageOverflowException e) {
+//            assertEquals(pageSize - headerSize - objects.size() * (object.length + objects.size()), e.bytesFree);
+//            assertEquals(object.length, e.bytesRequested);
+//        }
+
+        for (byte[] object : objects) {
+            for (byte b : object) {
+                System.out.print(Integer.toHexString(b));
+            }
+            System.out.println();
         }
 
         {
             ByteBuffer expectedBuffer = ByteBuffer.allocate(pageSize);
-            int position = pageSize - itemCount * (object.length + itemSize);
+            int position = pageSize - objects.size() * (objectSize + itemSize);
             expectedBuffer.putInt(position);
             expectedBuffer.position(position);
-            for (int i = 0; i < itemCount; i++) {
-                expectedBuffer.put(object);
-                expectedBuffer.putInt(object.length);
+            for (byte[] o : objects) {
+                expectedBuffer.put(o);
+                expectedBuffer.putInt(objectSize);
             }
             assertEquals(pageSize, expectedBuffer.position());
 
@@ -52,11 +67,11 @@ public class HeapPageTest {
         }
 
         {
-            Iterator<ByteBuffer> it = page.bufferIterator().iterator();
-            for (int i = 0; i < itemCount; i++) {
+            Iterator<ByteBuffer> it = page.items().iterator();
+            for (byte[] o : objects) {
                 assertTrue(it.hasNext());
                 ByteBuffer bb = it.next();
-                assertArrayEquals(object, toArray(bb));
+                assertArrayEquals(o, toArray(bb));
             }
             assertFalse(it.hasNext());
         }
diff --git a/src/test/java/io/trygvis/btree/HeapTest.java b/src/test/java/io/trygvis/btree/HeapTest.java
index 1d724f4..48a1463 100644
--- a/src/test/java/io/trygvis/btree/HeapTest.java
+++ b/src/test/java/io/trygvis/btree/HeapTest.java
@@ -4,6 +4,8 @@ import org.junit.Test;
 
 import java.io.File;
 import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Random;
 
 import static io.trygvis.btree.HeapTest.Person.randomPerson;
@@ -14,6 +16,8 @@ public class HeapTest {
 
     @Test
     public void testHeap() throws Exception {
+        List<Person> persons = new ArrayList<Person>();
+
         File f = new File("target/heapTest");
 
         HeapFile file = new HeapFile(128, deleteFile(f));
@@ -23,6 +27,7 @@ public class HeapTest {
         int pageNo = 0;
         for (int i = 0; i < 10; i++) {
             Person p = randomPerson();
+            persons.add(p);
 
             byte[] bytes = p.toBytes();
 
@@ -47,13 +52,15 @@ public class HeapTest {
 
         System.out.println("file.pageCount() = " + file.pageCount());
 
+        int counter = 0;
         for (int i = 0; i < file.pageCount(); i++) {
             System.out.println("page #" + i);
             page = file.loadPage(i);
 
-            for (ByteBuffer buffer : page.bufferIterator()) {
+            for (ByteBuffer buffer : page.items()) {
                 Person p = Person.fromBytes(buffer);
                 System.out.println("p = " + p);
+                assertEquals(persons.get(counter++), p);
             }
         }
     }
@@ -91,6 +98,23 @@ public class HeapTest {
                     '}';
         }
 
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (!(o instanceof Person)) return false;
+
+            Person person = (Person) o;
+
+            return age == person.age && name.equals(person.name);
+        }
+
+        @Override
+        public int hashCode() {
+            int result = name.hashCode();
+            result = 31 * result + age;
+            return result;
+        }
+
         private final static Random r = new Random(0);
         private final static String[] names = new String[]{
                 "Lukas", "Emil", "Mathias", "Jonas", "Aleksander", "William", "Oskar", "Magnus", "Markus", "Oliver",