From 67c42358e2940a166649b95a871ae7e47fb3ef17 Mon Sep 17 00:00:00 2001 From: Trygve Laugstøl Date: Fri, 27 Sep 2013 21:47:01 +0200 Subject: wip --- .gitignore | 3 + README.md | 17 +++++ pom.xml | 6 +- src/main/java/io/trygvis/btree/Bits.java | 11 +++ src/main/java/io/trygvis/btree/BtreeFile.java | 63 +++++++++++++++ src/main/java/io/trygvis/btree/BtreeMap.java | 97 ++++++++++++++++++++++++ src/main/java/io/trygvis/btree/HeapFile.java | 2 +- src/main/java/io/trygvis/btree/HeapPage.java | 18 ++++- src/test/java/io/trygvis/btree/BtreeMapTest.java | 45 +++++++++++ src/test/java/io/trygvis/btree/HeapPageTest.java | 51 ++++++++----- src/test/java/io/trygvis/btree/HeapTest.java | 26 ++++++- 11 files changed, 317 insertions(+), 22 deletions(-) create mode 100644 .gitignore create mode 100644 src/main/java/io/trygvis/btree/Bits.java create mode 100644 src/main/java/io/trygvis/btree/BtreeFile.java create mode 100644 src/main/java/io/trygvis/btree/BtreeMap.java create mode 100644 src/test/java/io/trygvis/btree/BtreeMapTest.java 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"> 4.0.0 - + + io.trygvis + trygvis-parent + 1 + io.trygvis.btree btree 1.0-SNAPSHOT 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 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 implements Map, Closeable { + + public static interface Serializer { + byte[] toBytes(A a); + + A fromBytes(byte[] bytes); + } + + private final BtreeFile tree; + private final Serializer kSerializer; + private final Serializer vSerializer; + + public BtreeMap(BtreeFile tree, Serializer kSerializer, Serializer 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 m) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + throw new UnsupportedOperationException(); + } + + @Override + public Set keySet() { + throw new UnsupportedOperationException(); + } + + @Override + public Collection values() { + throw new UnsupportedOperationException(); + } + + @Override + public Set> 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 bufferIterator() { + public Iterable items() { return new Iterable() { @Override public Iterator 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 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 { + @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 { + @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 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 it = page.bufferIterator().iterator(); - for (int i = 0; i < itemCount; i++) { + Iterator 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 persons = new ArrayList(); + 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", -- cgit v1.2.3