diff options
Diffstat (limited to 'src/main/java/io/trygvis')
-rw-r--r-- | src/main/java/io/trygvis/btree/Bits.java | 11 | ||||
-rw-r--r-- | src/main/java/io/trygvis/btree/BtreeFile.java | 63 | ||||
-rw-r--r-- | src/main/java/io/trygvis/btree/BtreeMap.java | 97 | ||||
-rw-r--r-- | src/main/java/io/trygvis/btree/HeapFile.java | 2 | ||||
-rw-r--r-- | src/main/java/io/trygvis/btree/HeapPage.java | 18 |
5 files changed, 189 insertions, 2 deletions
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() { |