/*******************************************************************************
* Copyright (c) 2010 Association for Decentralized Information Management in
* Industry THTH ry.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* VTT Technical Research Centre of Finland - initial API and implementation
*******************************************************************************/
package org.simantics.databoard.accessor.binary;
import java.io.IOException;
import java.lang.ref.SoftReference;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.Executor;
import org.simantics.databoard.accessor.Accessor;
import org.simantics.databoard.accessor.MapAccessor;
import org.simantics.databoard.accessor.error.AccessorConstructionException;
import org.simantics.databoard.accessor.error.AccessorException;
import org.simantics.databoard.accessor.error.ReferenceException;
import org.simantics.databoard.accessor.event.Event;
import org.simantics.databoard.accessor.event.MapEntryAdded;
import org.simantics.databoard.accessor.event.MapEntryRemoved;
import org.simantics.databoard.accessor.event.ValueAssigned;
import org.simantics.databoard.accessor.file.FileMapAccessor;
import org.simantics.databoard.accessor.impl.AccessorParams;
import org.simantics.databoard.accessor.impl.ListenerEntry;
import org.simantics.databoard.accessor.interestset.InterestSet;
import org.simantics.databoard.accessor.interestset.MapInterestSet;
import org.simantics.databoard.accessor.reference.ChildReference;
import org.simantics.databoard.accessor.reference.KeyReference;
import org.simantics.databoard.accessor.reference.LabelReference;
import org.simantics.databoard.adapter.AdaptException;
import org.simantics.databoard.adapter.Adapter;
import org.simantics.databoard.adapter.AdapterConstructionException;
import org.simantics.databoard.binding.ArrayBinding;
import org.simantics.databoard.binding.Binding;
import org.simantics.databoard.binding.MapBinding;
import org.simantics.databoard.binding.error.BindingConstructionException;
import org.simantics.databoard.binding.error.BindingException;
import org.simantics.databoard.binding.mutable.MutableVariant;
import org.simantics.databoard.parser.repository.DataTypeSyntaxError;
import org.simantics.databoard.parser.repository.DataValueRepository;
import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;
import org.simantics.databoard.serialization.SerializationException;
import org.simantics.databoard.serialization.Serializer;
import org.simantics.databoard.serialization.SerializerConstructionException;
import org.simantics.databoard.type.Datatype;
import org.simantics.databoard.type.MapType;
import org.simantics.databoard.util.binary.Blob;
import org.simantics.databoard.util.binary.RandomAccessBinary.ByteSide;
/**
* BinaryMap is accessor to a map structure in a file or byte memory.
*
(Fixed sized entries)
* If the size of an entry is constant, then the implementation uses binary
* search for random access operations O(log(n)).
*
*
(Variable sized entries)
* If the size is variable, for example the key or value is string, then the
* implementation does sequential search for all operations, which is very
* slow O(n). To improve performance, an index is built in memory as the file
* is read. To conserve memory, the index is held with SoftReference. So,
* the performance remains good if lots of operations are done within a short
* time period.
*
* @author Toni Kalajainen
*/
public class BinaryMap extends BinaryObject implements MapAccessor, FileMapAccessor {
/** Accessors to children */
TreeMap> children;
Binding kb;
Binding vb;
Serializer ks;
Serializer vs;
/** Entry size, constant */
Integer constantSize;
Index index;
boolean indexing = false;
public BinaryMap(BinaryObject parent, Blob blob, Datatype type, AccessorParams params) {
super(parent, blob, type, params);
MapType mt = (MapType) type;
kb = params.bindingScheme.getBindingUnchecked( mt.keyType );
vb = params.bindingScheme.getBindingUnchecked( mt.valueType );
ks = params.serializerScheme.getSerializerUnchecked( kb );
vs = params.serializerScheme.getSerializerUnchecked( vb );
children = new TreeMap>(kb);
if (ks.getConstantSize()!=null && vs.getConstantSize()!=null) {
constantSize = ks.getConstantSize() + vs.getConstantSize();
index = new Constant();
} else {
index = new Sequential();
}
}
// Get existing accessor
BinaryObject getChild(Object key)
{
java.lang.ref.Reference ref = children.get(key);
if (ref==null) return null;
BinaryObject result = ref.get();
if (result==null) {
children.remove(key);
return null;
}
return result;
}
Entry floorChildEntry(Object key) throws IOException, SerializationException, BindingException {
if (ks.getConstantSize()==null) return null;
BinaryObject sa = getChild(key);
// Exact match
if (sa!=null) {
if (ks.getConstantSize()==null) return null;
long valuePos = sa.b.getStartPositionInSourceBinary();
long keyPos = valuePos - ks.getConstantSize();
return new Entry(key, keyPos, sa);
}
return lowerChildEntry(key);
}
Entry lowerChildEntry(Object key) throws IOException, SerializationException, BindingException {
if (ks.getConstantSize()==null) return null;
Map.Entry> e = children.lowerEntry(key);
while (e != null) {
key = e.getKey();
BinaryObject sa = e.getValue().get();
if (sa!=null) {
long valuePos = sa.b.getStartPositionInSourceBinary();
long keyPos = valuePos - ks.getConstantSize();
return new Entry(key, keyPos, sa);
} else {
children.remove(e.getKey());
}
e = children.lowerEntry(key);
}
return null;
}
Entry lastChildEntry() throws IOException, SerializationException, BindingException {
if (ks.getConstantSize()==null) return null;
Map.Entry> e = children.lastEntry();
while (e != null) {
Object key = e.getKey();
BinaryObject sa = e.getValue().get();
if (sa!=null) {
long valuePos = sa.b.getStartPositionInSourceBinary();
long keyPos = valuePos - ks.getConstantSize();
return new Entry(key, keyPos, sa);
} else {
children.remove(key);
}
e = children.lowerEntry(key);
}
return null;
}
Entry higherChildEntry(Object key) throws IOException, SerializationException, BindingException {
if (ks.getConstantSize()==null) return null;
Map.Entry> e = children.higherEntry(key);
while (e != null) {
key = e.getKey();
BinaryObject sa = e.getValue().get();
if (sa!=null) {
long valuePos = sa.b.getStartPositionInSourceBinary();
long keyPos = valuePos - ks.getConstantSize();
return new Entry(key, keyPos, sa);
} else {
children.remove(key);
}
e = children.higherEntry(key);
}
return null;
}
Entry ceilingChildEntry(Object key) throws IOException, SerializationException, BindingException {
if (ks.getConstantSize()==null) return null;
BinaryObject sa = getChild(key);
// Exact match
if (sa!=null) {
long valuePos = sa.b.getStartPositionInSourceBinary();
long keyPos = valuePos - ks.getConstantSize();
return new Entry(key, keyPos, sa);
}
return higherChildEntry(key);
}
Entry getEntryAt(long pos) throws SerializationException, IOException, BindingException {
Object k = getKeyAt(pos);
if (k==null) return null;
return new Entry(k, pos, getChild(k));
}
Object getKeyAt(long pos) throws SerializationException, IOException, BindingException {
if (pos<4L) return null;
if (pos>=b.length()) return null;
b.position(pos);
Object k = ks.deserialize(b, null);
return k;
}
@Override
public MapType type() {
return (MapType) type;
}
@Override
public void clear() throws AccessorException {
assert b.isOpen();
writeLock();
try {
clearNoflush();
b.flush();
} catch (IOException e) {
throw new AccessorException( e );
} finally {
writeUnlock();
}
}
@Override
public int size() throws AccessorException {
assert b.isOpen();
readLock();
try {
if (constantSize != null) return (int) ((b.length()-4) / constantSize);
b.position(0L);
return b.readInt();
} catch (IOException e) {
throw new AccessorException( e );
} finally {
readUnlock();
}
}
@Override
public boolean containsKey(Binding keyBinding, Object key)
throws AccessorException {
assert b.isOpen();
readLock();
try {
Object lk = adapt(key, keyBinding, kb);
Entry e = index.getKey(lk);
return e != null;
} catch (AdaptException e) {
throw new AccessorException(e);
} catch (AdapterConstructionException e) {
throw new AccessorException(e);
} finally {
readUnlock();
}
}
@Override
public boolean containsValue(Binding valueBinding, Object value)
throws AccessorException {
assert b.isOpen();
readLock();
try {
Serializer vs = params.serializerScheme.getSerializer( valueBinding );
b.position(0L);
int count = b.readInt();
for (int i=0; i to) throws AccessorException {
assert b.isOpen();
readLock();
try {
Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
Adapter va = params.adapterScheme.getAdapter(vb, valueBinding, true, false);
b.position(0L);
int count = b.readInt();
for (int i=0; ikeys.length) throw new AccessorException("keys array too short");
if (count>values.length) throw new AccessorException("values array too short");
for (int i=0; iendEntry.pos) return 0;
if (fromEntry.pos==endEntry.pos) return 1;
if (constantSize != null) {
return (int) ((endEntry.pos-fromEntry.pos)/constantSize)+1;
}
int result = 1;
b.position(fromEntry.pos);
while (b.position()=0 && i>=limit) break;
Object key = ks.deserialize(b);
if (adaptKey) key = ka.adapt(key);
Object value = vs.deserialize(b);
if (adaptValue) value = va.adapt(value);
if (i T getComponent(ChildReference reference)
throws AccessorConstructionException {
if (reference==null) return (T) this;
if (reference instanceof LabelReference) {
LabelReference lr = (LabelReference) reference;
try {
DataValueRepository rep = new DataValueRepository();
kb.parseValue(lr.label, rep);
Object value = rep.get( rep.getValueNames().iterator().next() );
Accessor result = (T) getValueAccessor(kb, value);
if (reference.getChildReference() != null)
result = result.getComponent(reference.getChildReference());
return (T) result;
} catch ( BindingException e1 ) {
throw new ReferenceException(e1);
} catch ( DataTypeSyntaxError e2 ) {
throw new ReferenceException(e2);
}
} else
if (reference instanceof KeyReference) {
KeyReference ref = (KeyReference) reference;
Accessor result = getValueAccessor(ref.key.getBinding(), ref.key.getValue());
if (reference.getChildReference() != null)
result = result.getComponent(reference.getChildReference());
return (T) result;
} throw new ReferenceException(reference.getClass().getName()+" is not a reference of a map");
}
@SuppressWarnings("unchecked")
@Override
public T getValueAccessor(Binding keyBinding,
Object key) throws AccessorConstructionException {
assert b.isOpen();
readLock();
try {
Object rk = key;
Object lk = params.adapterScheme.getAdapter(keyBinding, kb, true, true).adapt(rk);
BinaryObject sa = getChild(lk);
if (sa!=null) return (T) sa;
Entry e = index.getKey(lk);
if (e == null) throw new AccessorConstructionException("Map doesn't contain the requested element");
long valuePos;
if (ks.getConstantSize()!=null) {
valuePos = e.pos + ks.getConstantSize();
} else {
b.position(e.pos);
ks.skip(b, null);
valuePos = b.position();
}
long valueSize;
if (vs.getConstantSize()!=null) {
valueSize = vs.getConstantSize();
} else {
b.position(valuePos);
vs.skip(b, null);
valueSize = b.position() - valuePos;
}
// Instantiate correct sub accessor.
sa = createSubAccessor(vb.type(), valuePos, valueSize, params);
children.put(lk, new SoftReference(sa));
// Add component interest sets
if (listeners!=null) {
MutableVariant kv = new MutableVariant(kb, lk);
ListenerEntry le = listeners;
while (le!=null) {
MapInterestSet is = le.getInterestSet();
// Generic element interest
InterestSet gis = is.getComponentInterest();
if (gis != null) {
try {
ChildReference childPath = ChildReference.concatenate(le.path, new KeyReference(kv) );
sa.addListener(le.listener, gis, childPath, le.executor);
} catch (AccessorException e1) {
throw new AccessorConstructionException(e1);
}
}
// Specific element interest
InterestSet cis = is.getComponentInterest(kv);
if (cis != null) {
try {
ChildReference childPath = ChildReference.concatenate(le.path, new KeyReference(kv) );
sa.addListener(le.listener, cis, childPath, le.executor );
} catch (AccessorException e1) {
throw new AccessorConstructionException(e1);
}
}
// Next listener
le = le.next;
}
}
return (T) sa;
} catch (AdaptException e) {
throw new AccessorConstructionException(e);
} catch (AdapterConstructionException e) {
throw new AccessorConstructionException(e);
} catch (IOException e) {
throw new AccessorConstructionException(e);
} catch (AccessorException e) {
throw new AccessorConstructionException(e);
} finally {
readUnlock();
}
}
@Override
public Object[] getValues(Binding valueBinding) throws AccessorException {
assert b.isOpen();
readLock();
try {
Serializer rvs = params.serializerScheme.getSerializer(valueBinding);
b.position(0L);
int count = b.readInt();
Object[] result = new Object[ count ];
for (int i=0; i ref : children.values()) {
BinaryObject sa = ref.get();
if (sa==null) continue;
sa.invalidatedNotification();
}
children.clear();
// Notify Listeners
ListenerEntry le = listeners;
while (le!=null) {
MapInterestSet is = le.getInterestSet();
for (Object key : keys) {
MutableVariant var = new MutableVariant(kb, key);
if (is.inNotificationsOf(var)) {
MapEntryRemoved e = new MapEntryRemoved(var);
emitEvent(le, e);
}
}
le = le.next;
}
} catch (IOException e) {
throw new AccessorException( e );
} finally {
writeUnlock();
}
}
@Override
public void putAllNoflush(Binding keyBinding, Binding valueBinding,
Map from) throws AccessorException {
int nc = from.size();
Object[] nks = new Object[ nc ];
Object[] nvs = new Object[ nc ];
int i=0;
for (Map.Entry e : from.entrySet()) {
nks[i] = e.getKey();
nvs[i] = e.getValue();
i++;
}
putAllNoflush(keyBinding, valueBinding, nks, nvs);
}
@Override
public void putAllNoflush(Binding kb, Binding vb,
Object[] nks, Object[] nvs) throws AccessorException {
int c = nks.length;
int newItemsCount = 0;
for (int i=0; i0) {
assert b.isOpen();
writeLock();
try {
b.position(0L);
int oldCount = b.readInt();
b.position(0L);
b.writeInt( oldCount + newItemsCount);
} catch (IOException e) {
throw new AccessorException(e);
} finally {
writeUnlock();
}
}
}
public void setAllNoflush(Binding kb, Binding vb,
Object[] nks, Object[] nvs) throws AccessorException {
assert b.isOpen();
writeLock();
try {
Serializer ks = params.serializerScheme.getSerializer( kb );
Serializer vs = params.serializerScheme.getSerializer( vb );
int nc = nks.length;
// Generate removed, assigned and added events
if (listeners!=null) {
b.position(4L);
int ni = 0;
// New and Old map lowest Keys
Object nk = nks.length>0 ? nks[0] : null;
Object ok = b.length()<=4 ? null : ks.deserialize(b, null);
while (nk!=null || ok!=null) {
int c = 0;
if (nk==null) {
c = -1;
} else if (ok==null) {
c= 1;
} else c = kb.compare(ok, nk);
if (c==0) {
// old key == new key
// Assigned new value
MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? nk : kb.clone(nk));
ListenerEntry le = listeners;
while (le!=null) {
MapInterestSet is = le.getInterestSet();
if (is.inNotificationsOf(kv)) {
MutableVariant vv = null;
if (is.inValuesOf(kv)) {
Object nv = vb.isImmutable() ? nvs[ni] : vb.clone(nvs[ni]);
vv = new MutableVariant(vb, nv);
}
Event e = new ValueAssigned( new KeyReference( kv ), vv);
emitEvent(le, e);
}
le = le.next;
}
// Move new pointer
ni++;
nk = ni0) {
// new key < old key
MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? nk : kb.clone(nk));
if (listeners!=null) {
Object nv = null;
ListenerEntry le = listeners;
while (le!=null) {
MapInterestSet is = le.getInterestSet();
if (is.inNotificationsOf(kv)) {
MutableVariant vv = null;
if (is.inValuesOf(kv)) {
if (nv==null) {
nv = vb.clone( nvs[ni] );
}
vv = new MutableVariant(vb, nv);
}
MapEntryAdded e = new MapEntryAdded(kv, vv);
emitEvent(le, e);
}
le = le.next;
}
}
// Move new pointer
ni++;
nk = ni(sa));
} catch (AccessorConstructionException e1) {
}
}
}
return false;
}
// Replace previous entry
// Write
Entry e = new Entry(lk, insertPos, null);
long pos = insertPos;
long oldSize = index.size(e);
if (oldSize> entry : children.entrySet()) {
BinaryObject sa = entry.getValue().get();
if (sa==null) continue;
Object key = entry.getKey();
MutableVariant vkey = new MutableVariant(kb, key);
InterestSet cis = is.getComponentInterest();
if (cis!=null) {
sa.removeListener(listener);
}
cis = is.getComponentInterest( vkey );
if (cis!=null) {
sa.removeListener(listener);
}
}
}
@Override
Event applyLocal(Event e, boolean makeRollback) throws AccessorException {
Event rollback = null;
if (e instanceof ValueAssigned) {
try {
ValueAssigned va = (ValueAssigned) e;
if (makeRollback) {
Binding binding = params.bindingScheme.getBinding(type());
rollback = new ValueAssigned(binding, getValue(binding));
}
setValueNoflush(va.newValue.getBinding(), va.newValue.getValue());
return rollback;
} catch (BindingConstructionException e1) {
throw new AccessorException( e1 );
}
} else if (e instanceof MapEntryAdded) {
MapEntryAdded ea = (MapEntryAdded) e;
if (ea.key==null) throw new AccessorException("Cannot apply entry added event because key is missing");
if (ea.value==null) throw new AccessorException("Cannot apply entry added event because value is missing");
boolean hadValue = containsKey(ea.key.getBinding(), ea.key.getValue());
if (hadValue) throw new AccessorException("Could not add entry to key that already existed");
if (makeRollback) {
rollback = new MapEntryRemoved( ea.key );
}
putNoflush(ea.key.getBinding(), ea.key.getValue(), ea.value.getBinding(), ea.value.getValue());
return rollback;
} else if (e instanceof MapEntryRemoved) {
MapEntryRemoved er = (MapEntryRemoved) e;
if (makeRollback) {
boolean hadValue = containsKey(er.key.getBinding(), er.key.getValue());
if (hadValue) {
Object oldValueObj = get(er.key.getBinding(), er.key.getValue(), vb);
MutableVariant oldKey = er.key;
MutableVariant oldValue = new MutableVariant(vb, oldValueObj);
rollback = new MapEntryAdded(oldKey, oldValue);
} else {
rollback = new MapEntryRemoved( er.key.clone() );
}
}
removeNoflush( er.key.getBinding(), er.key.getValue() );
return rollback;
} else {
throw new AccessorException("Cannot apply "+e.getClass().getName()+" to Map Type");
}
}
@Override
public void put(Binding keyBinding, Object key, Binding valueBinding,
Object value) throws AccessorException {
assert b.isOpen();
writeLock();
try {
putNoflush(keyBinding, key, valueBinding, value);
b.flush();
} catch (IOException e) {
throw new AccessorException(e);
} finally {
writeUnlock();
}
}
@Override
public void putAll(Binding keyBinding, Binding valueBinding,
Map from) throws AccessorException {
assert b.isOpen();
writeLock();
try {
putAllNoflush(keyBinding, valueBinding, from);
b.flush();
} catch (IOException e) {
throw new AccessorException(e);
} finally {
writeUnlock();
}
}
@Override
public void putAll(Binding keyBinding, Binding valueBinding, Object[] keys,
Object[] values) throws AccessorException {
assert b.isOpen();
writeLock();
try {
putAllNoflush(keyBinding, valueBinding, keys, values);
b.flush();
} catch (IOException e) {
throw new AccessorException(e);
} finally {
writeUnlock();
}
}
@Override
public void remove(Binding keyBinding, Object key) throws AccessorException {
assert b.isOpen();
writeLock();
try {
removeNoflush(keyBinding, key);
b.flush();
} catch (IOException e) {
throw new AccessorException(e);
} finally {
writeUnlock();
}
}
/** Interface for a search structure */
abstract class Index {
/**
* Get insert pos
* @param key
* @return if >0 position of existing entry of same key, <0 insertion position
* @throws AccessorException
*/
abstract long getInsertPos(Object key) throws AccessorException;
abstract Entry getKey(Object key) throws AccessorException;
abstract Entry floor(Object key) throws AccessorException;
abstract Entry ceiling(Object key) throws AccessorException;
abstract Entry higher(Object key) throws AccessorException;
abstract Entry lower(Object key) throws AccessorException;
abstract long size(Entry e) throws AccessorException;
Entry first() throws AccessorException {
try {
b.position(0L);
int count = b.readInt();
if (count==0) return null;
Object k = ks.deserialize(b);
java.lang.ref.Reference ref = children.get(k);
BinaryObject sa = ref == null ? null : ref.get();
return new Entry(k, 4, sa);
} catch (IOException e) {
throw new AccessorException(e);
}
}
abstract Entry last() throws AccessorException;
}
static class Entry {
// Optional child accessor
BinaryObject accessor;
Object key;
long pos;
public Entry(Object key, long pos, BinaryObject accessor) {
this.key = key; this.pos = pos; this.accessor = accessor;
}
}
/** Entries are indexed a table */
// class Table implements Index {
// }
/** Entry size is constant, binary Search */
class Constant extends Index {
Entry last() throws AccessorException {
try {
if (b.length()<=4) return null;
long pos = b.length() - constantSize;
b.position( pos );
Object key = ks.deserialize(b);
return new Entry(key, pos, null);
} catch (IOException e) {
throw new AccessorException(e);
}
}
@Override
long getInsertPos(Object key) throws AccessorException {
try {
int count = count();
if (count==0) return -4L;
// Check if it is the last entry
long pos = b.length() - constantSize;
b.position( pos );
Object lastKey = ks.deserialize(b);
int c = kb.compare(lastKey, key);
if (c<0) return -b.length();
if (c==0) return pos;
// We can narrow down the search to region between two existing children
Entry fc = floorChildEntry(key);
Entry cc = ceilingChildEntry(key);
int fromIndex = fc == null ? 0 : indexOf(fc);
int toIndex = cc == null ? count : indexOf(cc)+1;
// Do binary search
int r = binarySearch(fromIndex, toIndex, key);
if (r>=0) return getPos(r);
r=-(r+1);
if (r==count) return -b.length();
return -getPos(r);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
int indexOf(Entry e) {
return (int) ((e.pos - 4L) / constantSize);
}
int indexOf(long pos) {
return (int) ((pos - 4L) / constantSize);
}
/**
*
* @param fromIndex
* @param toIndex exclusive
* @param key
* @return
* @throws AccessorException
*/
int binarySearch(int fromIndex, int toIndex, Object key) throws AccessorException {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
Object midVal = getKey(mid);
int cmp = kb.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
@Override
public Entry getKey(Object key) throws AccessorException {
BinaryObject sa = getChild(key);
if (sa!=null) return new Entry(key, sa.b.getStartPositionInSourceBinary(), sa);
long pos = getInsertPos(key);
if (pos<0) return null;
return new Entry(key, pos, null);
}
@Override
public long size(Entry e) {
return constantSize;
}
Object getKey(int index) throws AccessorException {
try {
long pos = 4L + ((long)index) * constantSize;
b.position(pos);
return ks.deserialize(b);
} catch (IOException e) {
throw new AccessorException(e);
}
}
Entry getEntry(int index) throws AccessorException {
try {
long pos = 4L + ((long)index) * constantSize;
b.position(pos);
Object key = ks.deserialize(b);
return new Entry(key, pos, null);
} catch (IOException e) {
throw new AccessorException(e);
}
}
long getPos(int index) {
return 4L + ((long)index) * constantSize;
}
int count() throws IOException {
return (int) ((b.length()-4) / constantSize);
}
@Override
Entry ceiling(Object key) throws AccessorException {
try {
long pos = getInsertPos(key);
// Exact match
if (pos>0) return new Entry(key, pos, getChild(key));
pos = -pos;
int index = indexOf(pos);
if (index>=count()) return null;
key = getKeyAt(pos);
return new Entry(key, pos, null);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
@Override
Entry higher(Object key) throws AccessorException {
try {
long pos = getInsertPos(key);
if (pos>0) {
// Exact match
int index = indexOf(pos)+1;
if (index>=count()) return null;
pos = getPos(index);
key = getKeyAt(pos);
return new Entry(key, pos, null);
} else {
// Insert here match
int index = indexOf(-pos);
if (index>=count()) return null;
pos = getPos(index);
key = getKeyAt(pos);
return new Entry(key, pos, null);
}
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
@Override
Entry lower(Object key) throws AccessorException {
try {
long pos = getInsertPos(key);
// Exact match
if (pos>0) {
int index = indexOf(pos)-1;
if (index<0) return null;
pos = getPos(index);
key = getKeyAt(pos);
return new Entry(key, pos, null);
} else {
int index = indexOf(-pos)-1;
if (index<0) return null;
pos = getPos(index);
key = getKeyAt(pos);
return new Entry(key, pos, null);
}
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
@Override
Entry floor(Object key) throws AccessorException {
try {
long pos = getInsertPos(key);
// Exact match
if (pos>0) return new Entry(key, pos, getChild(key));
int index = indexOf(-pos)-1;
if (index<0) return null;
pos = getPos(index);
key = getKeyAt(pos);
return new Entry(key, pos, null);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
}
/** Variable size enetry, Sequential search */
class Sequential extends Index {
/**
* Get insert pos
* @param key
* @return if >0 position of existing entry of same key, <0 insertion position
* @throws AccessorException
*/
@Override
long getInsertPos(Object key) throws AccessorException {
try {
Entry start = floorChildEntry(key);
// Exact match
if (start !=null && kb.equals(key, start.key)) {
return start.pos;
}
long len = b.length();
long pos = start==null ? 4L : start.pos;
b.position(pos);
while (b.position()( result.accessor ));
}
return (result.key == null) ? null : result;
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
} catch (AccessorConstructionException e) {
throw new AccessorException(e);
}
}
@Override
long size(Entry e) throws AccessorException {
try {
long keyLen;
if (ks.getConstantSize()!=null) {
keyLen = ks.getConstantSize();
} else {
b.position(e.pos);
ks.skip(b, null);
keyLen = b.position() - e.pos;
}
long valueLen;
if (e.accessor!=null) {
valueLen = e.accessor.b.length();
} else if (vs.getConstantSize()!=null) {
valueLen = vs.getConstantSize();
} else {
long pos = e.pos + keyLen;
b.position(pos);
vs.skip(b, null);
valueLen = b.position() - pos;
}
return keyLen + valueLen;
} catch (IOException e1) {
throw new AccessorException(e1);
}
}
@Override
Entry ceiling(Object key) throws AccessorException {
try {
long pos = getInsertPos(key);
// Exact match
if (pos>0) return new Entry(key, pos, getChild(key));
pos = -pos;
return getEntryAt(pos);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
@Override
Entry higher(Object key) throws AccessorException {
try {
long pos = getInsertPos(key);
// Exact match
if (pos>0) {
if (pos>=b.length()) return null;
b.position(pos);
ks.skip(b, null);
vs.skip(b, null);
return getEntryAt(b.position());
}
pos = -pos;
return getEntryAt(pos);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
}
}
@Override
Entry lower(Object key) throws AccessorException {
try {
Entry start = lowerChildEntry(key);
long len = b.length();
long pos = start==null ? 4L : start.pos;
long prevPos = 0;
Object k = null;
Object prevK = null;
b.position(pos);
while (b.position()=0);
java.lang.ref.Reference ref = children.get(k);
BinaryObject sa = ref!=null?ref.get():null;
if (sa==null) {
sa = createSubAccessor(vb.type(), valuePos, valueLen, params);
children.put(k, new SoftReference(sa));
}
}
// There was no match, return the last entry
return new Entry(k, pos, null);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
} catch (AccessorConstructionException e) {
throw new AccessorException(e);
}
}
@Override
Entry floor(Object key) throws AccessorException {
try {
Entry start = floorChildEntry(key);
// Exact match
if (start !=null && kb.equals(key, start.key)) {
return start;
}
long len = b.length();
long pos = start==null ? 4L : start.pos;
long prevPos = 0;
Object k = null;
Object prevK = null;
BinaryObject prevAccessor = null;
b.position(pos);
while (b.position() ref = children.get(k);
BinaryObject sa = ref!=null?ref.get():null;
if (sa==null) {
prevAccessor = createSubAccessor(vb.type(), valuePos, valueLen, params);
children.put(k, new SoftReference(prevAccessor));
}
// Exact match
if (c==0) {
return new Entry(k, pos, prevAccessor);
}
}
return new Entry(k, pos, prevAccessor);
} catch (IOException e) {
throw new AccessorException(e);
} catch (BindingException e) {
throw new AccessorException(e);
} catch (AccessorConstructionException e) {
throw new AccessorException(e);
}
}
}
}