From 67c42358e2940a166649b95a871ae7e47fb3ef17 Mon Sep 17 00:00:00 2001 From: Trygve Laugstøl Date: Fri, 27 Sep 2013 21:47:01 +0200 Subject: wip --- 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 ++++- 5 files changed, 189 insertions(+), 2 deletions(-) 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 (limited to 'src/main/java/io/trygvis') 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() { -- cgit v1.2.3