aboutsummaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'src/main')
-rw-r--r--src/main/java/io/trygvis/btree/Bits.java11
-rw-r--r--src/main/java/io/trygvis/btree/BtreeFile.java63
-rw-r--r--src/main/java/io/trygvis/btree/BtreeMap.java97
-rw-r--r--src/main/java/io/trygvis/btree/HeapFile.java2
-rw-r--r--src/main/java/io/trygvis/btree/HeapPage.java18
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() {