1 /*******************************************************************************
2 * Copyright (c) 2010 Association for Decentralized Information Management in
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.databoard.accessor.binary;
14 import java.io.IOException;
15 import java.lang.ref.SoftReference;
17 import java.util.TreeMap;
18 import java.util.concurrent.Executor;
20 import org.simantics.databoard.accessor.Accessor;
21 import org.simantics.databoard.accessor.MapAccessor;
22 import org.simantics.databoard.accessor.error.AccessorConstructionException;
23 import org.simantics.databoard.accessor.error.AccessorException;
24 import org.simantics.databoard.accessor.error.ReferenceException;
25 import org.simantics.databoard.accessor.event.Event;
26 import org.simantics.databoard.accessor.event.MapEntryAdded;
27 import org.simantics.databoard.accessor.event.MapEntryRemoved;
28 import org.simantics.databoard.accessor.event.ValueAssigned;
29 import org.simantics.databoard.accessor.file.FileMapAccessor;
30 import org.simantics.databoard.accessor.impl.AccessorParams;
31 import org.simantics.databoard.accessor.impl.ListenerEntry;
32 import org.simantics.databoard.accessor.interestset.InterestSet;
33 import org.simantics.databoard.accessor.interestset.MapInterestSet;
34 import org.simantics.databoard.accessor.reference.ChildReference;
35 import org.simantics.databoard.accessor.reference.KeyReference;
36 import org.simantics.databoard.accessor.reference.LabelReference;
37 import org.simantics.databoard.adapter.AdaptException;
38 import org.simantics.databoard.adapter.Adapter;
39 import org.simantics.databoard.adapter.AdapterConstructionException;
40 import org.simantics.databoard.binding.ArrayBinding;
41 import org.simantics.databoard.binding.Binding;
42 import org.simantics.databoard.binding.MapBinding;
43 import org.simantics.databoard.binding.error.BindingConstructionException;
44 import org.simantics.databoard.binding.error.BindingException;
45 import org.simantics.databoard.binding.mutable.MutableVariant;
46 import org.simantics.databoard.parser.repository.DataTypeSyntaxError;
47 import org.simantics.databoard.parser.repository.DataValueRepository;
48 import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;
49 import org.simantics.databoard.serialization.SerializationException;
50 import org.simantics.databoard.serialization.Serializer;
51 import org.simantics.databoard.serialization.SerializerConstructionException;
52 import org.simantics.databoard.type.Datatype;
53 import org.simantics.databoard.type.MapType;
54 import org.simantics.databoard.util.binary.Blob;
55 import org.simantics.databoard.util.binary.RandomAccessBinary.ByteSide;
58 * BinaryMap is accessor to a map structure in a file or byte memory.
59 * <p> (Fixed sized entries)
60 * If the size of an entry is constant, then the implementation uses binary
61 * search for random access operations O(log(n)).
63 * <p> (Variable sized entries)
64 * If the size is variable, for example the key or value is string, then the
65 * implementation does sequential search for all operations, which is very
66 * slow O(n). To improve performance, an index is built in memory as the file
67 * is read. To conserve memory, the index is held with SoftReference. So,
68 * the performance remains good if lots of operations are done within a short
71 * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
73 public class BinaryMap extends BinaryObject implements MapAccessor, FileMapAccessor {
75 /** Accessors to children */
76 TreeMap<Object, java.lang.ref.Reference<BinaryObject>> children;
83 /** Entry size, constant */
87 boolean indexing = false;
89 public BinaryMap(BinaryObject parent, Blob blob, Datatype type, AccessorParams params) {
90 super(parent, blob, type, params);
91 MapType mt = (MapType) type;
92 kb = params.bindingScheme.getBindingUnchecked( mt.keyType );
93 vb = params.bindingScheme.getBindingUnchecked( mt.valueType );
94 ks = params.serializerScheme.getSerializerUnchecked( kb );
95 vs = params.serializerScheme.getSerializerUnchecked( vb );
96 children = new TreeMap<Object, java.lang.ref.Reference<BinaryObject>>(kb);
98 if (ks.getConstantSize()!=null && vs.getConstantSize()!=null) {
99 constantSize = ks.getConstantSize() + vs.getConstantSize();
100 index = new Constant();
102 index = new Sequential();
106 // Get existing accessor
107 BinaryObject getChild(Object key)
109 java.lang.ref.Reference<BinaryObject> ref = children.get(key);
110 if (ref==null) return null;
111 BinaryObject result = ref.get();
113 children.remove(key);
119 Entry floorChildEntry(Object key) throws IOException, SerializationException, BindingException {
120 if (ks.getConstantSize()==null) return null;
121 BinaryObject sa = getChild(key);
124 if (ks.getConstantSize()==null) return null;
125 long valuePos = sa.b.getStartPositionInSourceBinary();
126 long keyPos = valuePos - ks.getConstantSize();
127 return new Entry(key, keyPos, sa);
129 return lowerChildEntry(key);
132 Entry lowerChildEntry(Object key) throws IOException, SerializationException, BindingException {
133 if (ks.getConstantSize()==null) return null;
134 Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> e = children.lowerEntry(key);
137 BinaryObject sa = e.getValue().get();
139 long valuePos = sa.b.getStartPositionInSourceBinary();
140 long keyPos = valuePos - ks.getConstantSize();
141 return new Entry(key, keyPos, sa);
143 children.remove(e.getKey());
145 e = children.lowerEntry(key);
150 Entry lastChildEntry() throws IOException, SerializationException, BindingException {
151 if (ks.getConstantSize()==null) return null;
152 Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> e = children.lastEntry();
154 Object key = e.getKey();
155 BinaryObject sa = e.getValue().get();
157 long valuePos = sa.b.getStartPositionInSourceBinary();
158 long keyPos = valuePos - ks.getConstantSize();
159 return new Entry(key, keyPos, sa);
161 children.remove(key);
163 e = children.lowerEntry(key);
168 Entry higherChildEntry(Object key) throws IOException, SerializationException, BindingException {
169 if (ks.getConstantSize()==null) return null;
170 Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> e = children.higherEntry(key);
173 BinaryObject sa = e.getValue().get();
175 long valuePos = sa.b.getStartPositionInSourceBinary();
176 long keyPos = valuePos - ks.getConstantSize();
177 return new Entry(key, keyPos, sa);
179 children.remove(key);
181 e = children.higherEntry(key);
186 Entry ceilingChildEntry(Object key) throws IOException, SerializationException, BindingException {
187 if (ks.getConstantSize()==null) return null;
188 BinaryObject sa = getChild(key);
191 long valuePos = sa.b.getStartPositionInSourceBinary();
192 long keyPos = valuePos - ks.getConstantSize();
193 return new Entry(key, keyPos, sa);
195 return higherChildEntry(key);
198 Entry getEntryAt(long pos) throws SerializationException, IOException, BindingException {
199 Object k = getKeyAt(pos);
200 if (k==null) return null;
201 return new Entry(k, pos, getChild(k));
204 Object getKeyAt(long pos) throws SerializationException, IOException, BindingException {
205 if (pos<4L) return null;
206 if (pos>=b.length()) return null;
208 Object k = ks.deserialize(b, null);
213 public MapType type() {
214 return (MapType) type;
218 public void clear() throws AccessorException {
224 } catch (IOException e) {
225 throw new AccessorException( e );
232 public int size() throws AccessorException {
236 if (constantSize != null) return (int) ((b.length()-4) / constantSize);
239 } catch (IOException e) {
240 throw new AccessorException( e );
247 public boolean containsKey(Binding keyBinding, Object key)
248 throws AccessorException {
252 Object lk = adapt(key, keyBinding, kb);
253 Entry e = index.getKey(lk);
255 } catch (AdaptException e) {
256 throw new AccessorException(e);
257 } catch (AdapterConstructionException e) {
258 throw new AccessorException(e);
265 public boolean containsValue(Binding valueBinding, Object value)
266 throws AccessorException {
270 Serializer vs = params.serializerScheme.getSerializer( valueBinding );
272 int count = b.readInt();
273 for (int i=0; i<count; i++) {
275 Object v = vs.deserialize(b, null);
276 if (valueBinding.equals(v, value)) return true;
278 } catch (IOException e) {
279 throw new AccessorException(e);
280 } catch (SerializerConstructionException e) {
281 throw new AccessorException(e);
289 public Object get(Binding keyBinding, Object key, Binding valueBinding)
290 throws AccessorException {
294 Object lk = adapt(key, keyBinding, kb);
295 Entry e = index.getKey(lk);
296 if (e==null) return null;
299 Object value = params.serializerScheme.getSerializer( valueBinding ).deserialize(b, null);
301 } catch (AdaptException e1) {
302 throw new AccessorException(e1);
303 } catch (IOException e) {
304 throw new AccessorException(e);
305 } catch (RuntimeSerializerConstructionException e) {
306 throw new AccessorException(e);
307 } catch (AdapterConstructionException e) {
308 throw new AccessorException(e);
309 } catch (SerializerConstructionException e) {
310 throw new AccessorException(e);
317 public void getAll(Binding keyBinding, Binding valueBinding,
318 Map<Object, Object> to) throws AccessorException {
322 Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
323 Adapter va = params.adapterScheme.getAdapter(vb, valueBinding, true, false);
325 int count = b.readInt();
326 for (int i=0; i<count; i++) {
327 Object k = ks.deserialize(b, null);
328 Object v = vs.deserialize(b, null);
334 } catch (IOException e) {
335 throw new AccessorException(e);
336 } catch (AdapterConstructionException e) {
337 throw new AccessorException(e);
338 } catch (AdaptException e) {
339 throw new AccessorException(e);
347 public void getAll(Binding keyBinding, Binding valueBinding, Object[] keys,
348 Object[] values) throws AccessorException {
352 Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
353 Adapter va = params.adapterScheme.getAdapter(vb, valueBinding, true, false);
355 int count = b.readInt();
356 if (count>keys.length) throw new AccessorException("keys array too short");
357 if (count>values.length) throw new AccessorException("values array too short");
358 for (int i=0; i<count; i++) {
359 Object k = ks.deserialize(b, null);
360 Object v = vs.deserialize(b, null);
367 } catch (IOException e) {
368 throw new AccessorException(e);
369 } catch (AdapterConstructionException e) {
370 throw new AccessorException(e);
371 } catch (AdaptException e) {
372 throw new AccessorException(e);
380 public int count(Binding keyBinding, Object from, boolean fromInclusive,
381 Object end, boolean endInclusive) throws AccessorException {
385 Object lf = params.adapterScheme.adapt(from, keyBinding, kb);
386 Object le = params.adapterScheme.adapt(end, keyBinding, kb);
388 Entry fromEntry = fromInclusive ? index.ceiling(lf) : index.higher(lf);
389 Entry endEntry = endInclusive ? index.floor(le) : index.lower(le);
390 if (endEntry==null || fromEntry == null) return 0;
392 if (fromEntry.pos>endEntry.pos) return 0;
393 if (fromEntry.pos==endEntry.pos) return 1;
395 if (constantSize != null) {
396 return (int) ((endEntry.pos-fromEntry.pos)/constantSize)+1;
400 b.position(fromEntry.pos);
401 while (b.position()<endEntry.pos) {
407 } catch (IOException e) {
408 throw new AccessorException(e);
409 } catch (AdaptException e) {
410 throw new AccessorException(e);
417 public int getEntries(Binding keyBinding, Object from,
418 boolean fromInclusive, Object end, boolean endInclusive,
419 ArrayBinding keyArrayBinding, Object keysArray,
420 ArrayBinding valueArrayBinding, Object valueArray, int limit)
421 throws AccessorException {
425 Object lf = params.adapterScheme.adapt(from, keyBinding, kb);
426 Object le = params.adapterScheme.adapt(end, keyBinding, kb);
428 Entry fromEntry = fromInclusive ? index.ceiling(lf) : index.higher(lf);
429 Entry endEntry = endInclusive ? index.floor(le) : index.lower(le);
430 if (endEntry==null || fromEntry == null) return 0;
432 // Requester's Key & Value Binding
433 Binding rkb = keyArrayBinding.getComponentBinding();
434 Binding rvb = valueArrayBinding.getComponentBinding();
436 // Local Key & Value type & bindings
437 Datatype lkt = type().keyType;
438 Datatype lvt = type().valueType;
440 boolean adaptKey = !rkb.type().equals(lkt);
441 boolean adaptValue = !rvb.type().equals(lvt);
444 Adapter ka = null, va = null;
447 Binding lkb = params.bindingScheme.getBinding( lkt );
448 ka = params.adapterScheme.getAdapter( lkb, rkb, true, false);
449 ks = params.serializerScheme.getSerializer( lkb );
451 ks = params.serializerScheme.getSerializer( rkb );
455 Binding lvb = params.bindingScheme.getBinding( lvt );
456 va = params.adapterScheme.getAdapter( lvb, rvb, true, false);
457 vs = params.serializerScheme.getSerializer( lvb );
459 vs = params.serializerScheme.getSerializer( rvb );
463 int kac = keyArrayBinding.size( keysArray );
464 int vac = valueArrayBinding.size( valueArray );
465 b.position(fromEntry.pos);
466 while (b.position()<=endEntry.pos) {
467 if (limit>=0 && i>=limit) break;
468 Object key = ks.deserialize(b);
469 if (adaptKey) key = ka.adapt(key);
470 Object value = vs.deserialize(b);
471 if (adaptValue) value = va.adapt(value);
473 if (i<kac) keyArrayBinding.set(keysArray, i, key); else keyArrayBinding.add(keysArray, i, key);
474 if (i<vac) valueArrayBinding.set(valueArray, i, value); else valueArrayBinding.add(valueArray, i, value);
479 } catch (IOException e) {
480 throw new AccessorException(e);
481 } catch (AdaptException e) {
482 throw new AccessorException(e);
483 } catch (SerializerConstructionException e) {
484 throw new AccessorException(e);
485 } catch (BindingException e) {
486 throw new AccessorException(e);
487 } catch (BindingConstructionException e) {
488 throw new AccessorException(e);
489 } catch (AdapterConstructionException e) {
490 throw new AccessorException(e);
497 public Object getCeilingKey(Binding keyBinding, Object key)
498 throws AccessorException {
502 Object lk = adapt(key, keyBinding, kb);
503 if (ks.getConstantSize()!=null) {
504 if (getChild(lk)!=null) return key;
506 Entry e = index.ceiling(lk);
507 if (e==null) return null;
508 return adapt(e.key, kb, keyBinding);
509 } catch (AdaptException e1) {
510 throw new AccessorException( e1 );
511 } catch (AdapterConstructionException e) {
512 throw new AccessorException( e );
519 public Object getFirstKey(Binding keyBinding) throws AccessorException {
524 int count = b.readInt();
525 if (count==0) return null;
526 return params.serializerScheme.getSerializer( keyBinding ).deserialize(b);
527 } catch (RuntimeSerializerConstructionException e) {
528 throw new AccessorException(e);
529 } catch (IOException e) {
530 throw new AccessorException(e);
531 } catch (SerializerConstructionException e) {
532 throw new AccessorException(e);
539 public Object getFloorKey(Binding keyBinding, Object key)
540 throws AccessorException {
544 Object lk = adapt(key, keyBinding, kb);
545 if (ks.getConstantSize()!=null) {
546 // See if we get exact match
547 if (getChild(lk)!=null) return key;
549 Entry e = index.floor(lk);
550 if (e==null) return null;
551 return adapt(e.key, kb, keyBinding);
552 } catch (AdaptException e1) {
553 throw new AccessorException( e1 );
554 } catch (AdapterConstructionException e) {
555 throw new AccessorException( e );
562 public Object getHigherKey(Binding keyBinding, Object key)
563 throws AccessorException {
567 Object lk = adapt(key, keyBinding, kb);
568 Entry e = index.higher(lk);
569 if (e==null) return null;
570 return adapt(e.key, kb, keyBinding);
571 } catch (AdaptException e1) {
572 throw new AccessorException( e1 );
573 } catch (AdapterConstructionException e) {
574 throw new AccessorException( e );
581 public Object[] getKeys(Binding keyBinding) throws AccessorException {
585 Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
587 int count = b.readInt();
588 Object[] result = new Object[ count ];
589 for (int i=0; i<count; i++) {
590 Object k = ks.deserialize(b, null);
596 } catch (IOException e) {
597 throw new AccessorException(e);
598 } catch (AdapterConstructionException e) {
599 throw new AccessorException(e);
600 } catch (AdaptException e) {
601 throw new AccessorException(e);
608 public Object getLastKey(Binding keyBinding) throws AccessorException {
612 Entry e = index.last();
613 if (e==null) return null;
614 return adapt(e.key, kb, keyBinding);
615 } catch (AdaptException e1) {
616 throw new AccessorException( e1 );
617 } catch (AdapterConstructionException e) {
618 throw new AccessorException( e );
625 public Object getLowerKey(Binding keyBinding, Object key)
626 throws AccessorException {
630 Object lk = adapt(key, keyBinding, kb);
631 Entry e = index.lower(lk);
632 if (e==null) return null;
633 return adapt(e.key, kb, keyBinding);
634 } catch (AdaptException e1) {
635 throw new AccessorException( e1 );
636 } catch (AdapterConstructionException e) {
637 throw new AccessorException( e );
644 @SuppressWarnings("unchecked")
646 public <T extends Accessor> T getComponent(ChildReference reference)
647 throws AccessorConstructionException {
648 if (reference==null) return (T) this;
650 if (reference instanceof LabelReference) {
651 LabelReference lr = (LabelReference) reference;
653 DataValueRepository rep = new DataValueRepository();
654 kb.parseValue(lr.label, rep);
655 Object value = rep.get( rep.getValueNames().iterator().next() );
657 Accessor result = (T) getValueAccessor(kb, value);
658 if (reference.getChildReference() != null)
659 result = result.getComponent(reference.getChildReference());
661 } catch ( BindingException e1 ) {
662 throw new ReferenceException(e1);
663 } catch ( DataTypeSyntaxError e2 ) {
664 throw new ReferenceException(e2);
667 if (reference instanceof KeyReference) {
668 KeyReference ref = (KeyReference) reference;
669 Accessor result = getValueAccessor(ref.key.getBinding(), ref.key.getValue());
670 if (reference.getChildReference() != null)
671 result = result.getComponent(reference.getChildReference());
673 } throw new ReferenceException(reference.getClass().getName()+" is not a reference of a map");
676 @SuppressWarnings("unchecked")
678 public <T extends Accessor> T getValueAccessor(Binding keyBinding,
679 Object key) throws AccessorConstructionException {
685 Object lk = params.adapterScheme.getAdapter(keyBinding, kb, true, true).adapt(rk);
687 BinaryObject sa = getChild(lk);
688 if (sa!=null) return (T) sa;
690 Entry e = index.getKey(lk);
691 if (e == null) throw new AccessorConstructionException("Map doesn't contain the requested element");
694 if (ks.getConstantSize()!=null) {
695 valuePos = e.pos + ks.getConstantSize();
699 valuePos = b.position();
703 if (vs.getConstantSize()!=null) {
704 valueSize = vs.getConstantSize();
706 b.position(valuePos);
708 valueSize = b.position() - valuePos;
711 // Instantiate correct sub accessor.
712 sa = createSubAccessor(vb.type(), valuePos, valueSize, params);
713 children.put(lk, new SoftReference<BinaryObject>(sa));
715 // Add component interest sets
716 if (listeners!=null) {
717 MutableVariant kv = new MutableVariant(kb, lk);
718 ListenerEntry le = listeners;
720 MapInterestSet is = le.getInterestSet();
722 // Generic element interest
723 InterestSet gis = is.getComponentInterest();
726 ChildReference childPath = ChildReference.concatenate(le.path, new KeyReference(kv) );
727 sa.addListener(le.listener, gis, childPath, le.executor);
728 } catch (AccessorException e1) {
729 throw new AccessorConstructionException(e1);
733 // Specific element interest
734 InterestSet cis = is.getComponentInterest(kv);
737 ChildReference childPath = ChildReference.concatenate(le.path, new KeyReference(kv) );
738 sa.addListener(le.listener, cis, childPath, le.executor );
739 } catch (AccessorException e1) {
740 throw new AccessorConstructionException(e1);
750 } catch (AdaptException e) {
751 throw new AccessorConstructionException(e);
752 } catch (AdapterConstructionException e) {
753 throw new AccessorConstructionException(e);
754 } catch (IOException e) {
755 throw new AccessorConstructionException(e);
756 } catch (AccessorException e) {
757 throw new AccessorConstructionException(e);
764 public Object[] getValues(Binding valueBinding) throws AccessorException {
768 Serializer rvs = params.serializerScheme.getSerializer(valueBinding);
770 int count = b.readInt();
771 Object[] result = new Object[ count ];
772 for (int i=0; i<result.length; i++) {
774 result[i] = rvs.deserialize(b, null);
777 } catch (IOException e) {
778 throw new AccessorException( e );
779 } catch (SerializerConstructionException e) {
780 throw new AccessorException( e );
787 public void setValueNoflush(Binding binding, Object mapValue)
788 throws AccessorException {
790 MapBinding mb = (MapBinding) binding;
791 if (children.isEmpty() && listeners==null) {
795 Serializer s = params.serializerScheme.getSerializer( mb );
796 int size = s.getSize(mapValue, null);
800 s.serialize(b, null, mapValue);
801 } catch (IOException e) {
802 throw new AccessorException( e );
803 } catch (SerializerConstructionException e) {
804 throw new AccessorException( e );
812 int nc = mb.size(mapValue);
813 Object nks[] = new Object[nc];
814 Object nvs[] = new Object[nc];
815 mb.getAll(mapValue, nks, nvs);
816 setAllNoflush(mb.getKeyBinding(), mb.getValueBinding(), nks, nvs);
817 } catch (BindingException e) {
818 throw new AccessorException(e);
828 public void clearNoflush() throws AccessorException {
832 boolean hasListeners = listeners!=null;
833 Object[] keys = hasListeners ? getKeys(kb) : null;
840 // Disconnect sub-accessor
841 for (java.lang.ref.Reference<BinaryObject> ref : children.values()) {
842 BinaryObject sa = ref.get();
843 if (sa==null) continue;
844 sa.invalidatedNotification();
849 ListenerEntry le = listeners;
851 MapInterestSet is = le.getInterestSet();
852 for (Object key : keys) {
853 MutableVariant var = new MutableVariant(kb, key);
854 if (is.inNotificationsOf(var)) {
855 MapEntryRemoved e = new MapEntryRemoved(var);
863 } catch (IOException e) {
864 throw new AccessorException( e );
872 public void putAllNoflush(Binding keyBinding, Binding valueBinding,
873 Map<Object, Object> from) throws AccessorException {
874 int nc = from.size();
875 Object[] nks = new Object[ nc ];
876 Object[] nvs = new Object[ nc ];
878 for (Map.Entry<Object, Object> e : from.entrySet()) {
880 nvs[i] = e.getValue();
883 putAllNoflush(keyBinding, valueBinding, nks, nvs);
887 public void putAllNoflush(Binding kb, Binding vb,
888 Object[] nks, Object[] nvs) throws AccessorException {
890 int newItemsCount = 0;
891 for (int i=0; i<c; i++) {
892 boolean hadPreviousValue = _putNoflush(kb, nks[i], vb, nvs[i]);
893 if (!hadPreviousValue) newItemsCount++;
896 if (newItemsCount>0) {
901 int oldCount = b.readInt();
903 b.writeInt( oldCount + newItemsCount);
904 } catch (IOException e) {
905 throw new AccessorException(e);
913 public void setAllNoflush(Binding kb, Binding vb,
914 Object[] nks, Object[] nvs) throws AccessorException {
918 Serializer ks = params.serializerScheme.getSerializer( kb );
919 Serializer vs = params.serializerScheme.getSerializer( vb );
921 // Generate removed, assigned and added events
922 if (listeners!=null) {
927 // New and Old map lowest Keys
928 Object nk = nks.length>0 ? nks[0] : null;
929 Object ok = b.length()<=4 ? null : ks.deserialize(b, null);
931 while (nk!=null || ok!=null) {
935 } else if (ok==null) {
937 } else c = kb.compare(ok, nk);
939 // old key == new key
940 // Assigned new value
941 MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? nk : kb.clone(nk));
942 ListenerEntry le = listeners;
944 MapInterestSet is = le.getInterestSet();
945 if (is.inNotificationsOf(kv)) {
946 MutableVariant vv = null;
947 if (is.inValuesOf(kv)) {
948 Object nv = vb.isImmutable() ? nvs[ni] : vb.clone(nvs[ni]);
949 vv = new MutableVariant(vb, nv);
951 Event e = new ValueAssigned( new KeyReference( kv ), vv);
958 nk = ni<nks.length ? nks[ni] : null;
961 ok = b.position()<b.length() ? ks.deserialize(b, null) : null;
966 MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? ok : kb.clone(ok));
967 ListenerEntry le = listeners;
969 MapInterestSet is = le.getInterestSet();
970 if (is.inNotificationsOf(kv)) {
971 MapEntryRemoved e = new MapEntryRemoved(kv);
978 ok = b.position()<b.length() ? ks.deserialize(b, null) : null;
983 MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? nk : kb.clone(nk));
985 if (listeners!=null) {
987 ListenerEntry le = listeners;
989 MapInterestSet is = le.getInterestSet();
990 if (is.inNotificationsOf(kv)) {
991 MutableVariant vv = null;
992 if (is.inValuesOf(kv)) {
994 nv = vb.clone( nvs[ni] );
996 vv = new MutableVariant(vb, nv);
998 MapEntryAdded e = new MapEntryAdded(kv, vv);
1007 nk = ni<nks.length ? nks[ni] : null;
1015 if (ks.getConstantSize()!=null) {
1016 size += ((long)nc) * ks.getConstantSize();
1018 for (int i=0; i<nc; i++) size += ks.getSize(nks[i], null);
1021 if (vs.getConstantSize()!=null) {
1022 size += ((long)nc) * vs.getConstantSize();
1024 for (int i=0; i<nc; i++) size += vs.getSize(nvs[i], null);
1029 // Write entry by entry and update positions of children
1032 for (int i=0; i<nc; i++) {
1035 long startPos = b.position();
1036 ks.serialize(b, null, nk);
1037 vs.serialize(b, null, nv);
1038 long endPos = b.position();
1039 long len = endPos - startPos;
1040 Object lk = params.adapterScheme.adapt(nk, kb, this.kb);
1041 BinaryObject sa = getChild(lk);
1042 if (sa!=null) sa.b.setPositionInSource(startPos, len);
1046 } catch (IOException e) {
1047 throw new AccessorException(e);
1048 } catch (AdaptException e) {
1049 throw new AccessorException(e);
1050 } catch (SerializerConstructionException e) {
1051 throw new AccessorException(e);
1059 public void putNoflush(Binding kb, Object key,
1060 Binding vb, Object value) throws AccessorException {
1064 boolean hadPreviousEntry = _putNoflush(kb, key, vb, value);
1066 if (!hadPreviousEntry) {
1068 int oldCount = b.readInt();
1070 b.writeInt( oldCount + 1);
1072 } catch (IOException e) {
1073 throw new AccessorException(e);
1074 } catch (RuntimeSerializerConstructionException e) {
1075 throw new AccessorException(e);
1082 * Put an entry. Does not update size.
1088 * @return true if previous entry existed
1089 * @throws AccessorException
1091 private boolean _putNoflush(Binding kb, Object key,
1092 Binding vb, Object value) throws AccessorException {
1095 Object lk = adapt(key, kb, this.kb);
1096 long insertPos = index.getInsertPos(lk);
1097 Serializer ks = params.serializerScheme.getSerializer( kb );
1098 Serializer vs = params.serializerScheme.getSerializer( vb );
1099 long newSize = ks.getSize(key, null) + vs.getSize(value, null);
1104 long pos = -insertPos;
1106 b.insertBytes(newSize, ByteSide.Neither);
1108 ks.serialize(b, null, key);
1109 vs.serialize(b, null, value);
1112 MutableVariant kv = new MutableVariant(this.kb, lk);
1115 ListenerEntry le = listeners;
1117 MapInterestSet is = le.getInterestSet();
1118 if (is.inNotificationsOf(kv)) {
1120 MutableVariant vv = null;
1121 if (is.inValuesOf(kv)) vv = new MutableVariant(vb, vb.isImmutable() ? value : vb.clone(value));
1123 // Notify about new entry
1124 MapEntryAdded e = new MapEntryAdded(kv, vv);
1131 // Optimization for sequential write
1132 // Create sub accessor for the last entry
1133 if (insertPos==b.length() && constantSize==null) {
1134 BinaryObject sa = getChild(lk);
1136 // Instantiate correct sub accessor.
1138 sa = createSubAccessor(vb.type(), pos, newSize, params);
1139 children.put(lk, new SoftReference<BinaryObject>(sa));
1140 } catch (AccessorConstructionException e1) {
1148 // Replace previous entry
1150 Entry e = new Entry(lk, insertPos, null);
1151 long pos = insertPos;
1152 long oldSize = index.size(e);
1154 if (oldSize<newSize) {
1156 b.insertBytes(newSize - oldSize, ByteSide.Right);
1157 } else if (newSize<oldSize) {
1159 b.removeBytes(oldSize - newSize, ByteSide.Right);
1163 ks.serialize(b, null, key);
1164 vs.serialize(b, null, value);
1167 ListenerEntry le = listeners;
1168 if (listeners!=null) {
1169 MutableVariant kv = new MutableVariant(kb, lk);
1171 MapInterestSet is = le.getInterestSet();
1172 if (is.inNotificationsOf(kv)) {
1174 MutableVariant vv = null;
1175 if (is.inValuesOf(kv)) vv = new MutableVariant(vb, vb.isImmutable() ? value : vb.clone(value));
1177 // Notify about new entry
1178 Event ev = new ValueAssigned( new KeyReference(kv), vv);
1187 // BinaryObject sa = getChild(lk);
1189 // sa.b.setPositionInSource(pos, newSize);
1194 } catch (AdaptException e1) {
1195 throw new AccessorException(e1);
1196 } catch (IOException e) {
1197 throw new AccessorException(e);
1198 } catch (RuntimeSerializerConstructionException e) {
1199 throw new AccessorException(e);
1200 } catch (AdapterConstructionException e) {
1201 throw new AccessorException(e);
1202 } catch (SerializerConstructionException e) {
1203 throw new AccessorException(e);
1211 public void removeNoflush(Binding keyBinding, Object key)
1212 throws AccessorException {
1216 Object lk = params.adapterScheme.getAdapter(keyBinding, kb, true, listeners!=null).adapt(key);
1217 Entry e = index.getKey(lk);
1218 if (e==null) return;
1220 int oldSize = size();
1222 b.writeInt( oldSize - 1 );
1223 long size = index.size(e);
1225 b.removeBytes(size, ByteSide.Right);
1227 // Disconnect sub-accessor
1228 BinaryObject sa = getChild(lk);
1229 // Notify about disconnection of sub-accessor
1231 sa.invalidatedNotification();
1232 children.remove(lk);
1236 if (listeners!=null) {
1237 MutableVariant var = new MutableVariant(kb, lk);
1238 ListenerEntry le = listeners;
1240 MapInterestSet is = le.getInterestSet();
1241 if (is.inNotificationsOf(var)) {
1242 MapEntryRemoved e2 = new MapEntryRemoved(var);
1250 } catch (IOException e) {
1251 throw new AccessorException(e);
1252 } catch (AdaptException e) {
1253 throw new AccessorException(e);
1254 } catch (AdapterConstructionException e) {
1255 throw new AccessorException(e);
1263 public void addListener(Listener listener, InterestSet interestSet,
1264 ChildReference path, Executor executor) throws AccessorException {
1265 super.addListener(listener, interestSet, path, executor);
1266 MapInterestSet is = (MapInterestSet) interestSet;
1268 for (Object key : children.keySet()) {
1269 BinaryObject sa = getChild(key);
1270 if (sa==null) continue;
1272 MutableVariant vkey = new MutableVariant(kb, key);
1273 InterestSet cis = is.getComponentInterest();
1275 ChildReference childPath = ChildReference.concatenate( path, new KeyReference(vkey) );
1276 sa.addListener(listener, cis, childPath, executor);
1278 cis = is.getComponentInterest( vkey );
1280 ChildReference childPath = ChildReference.concatenate( path, new KeyReference(vkey) );
1281 sa.addListener(listener, cis, childPath, executor);
1287 public void removeListener(Listener listener) throws AccessorException {
1288 ListenerEntry e = detachListener(listener);
1289 if (e==null) return;
1290 MapInterestSet is = (MapInterestSet) e.interestSet;
1292 for (Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> entry : children.entrySet()) {
1293 BinaryObject sa = entry.getValue().get();
1294 if (sa==null) continue;
1295 Object key = entry.getKey();
1297 MutableVariant vkey = new MutableVariant(kb, key);
1298 InterestSet cis = is.getComponentInterest();
1300 sa.removeListener(listener);
1302 cis = is.getComponentInterest( vkey );
1304 sa.removeListener(listener);
1311 Event applyLocal(Event e, boolean makeRollback) throws AccessorException {
1312 Event rollback = null;
1314 if (e instanceof ValueAssigned) {
1316 ValueAssigned va = (ValueAssigned) e;
1318 Binding binding = params.bindingScheme.getBinding(type());
1319 rollback = new ValueAssigned(binding, getValue(binding));
1321 setValueNoflush(va.newValue.getBinding(), va.newValue.getValue());
1323 } catch (BindingConstructionException e1) {
1324 throw new AccessorException( e1 );
1326 } else if (e instanceof MapEntryAdded) {
1327 MapEntryAdded ea = (MapEntryAdded) e;
1328 if (ea.key==null) throw new AccessorException("Cannot apply entry added event because key is missing");
1329 if (ea.value==null) throw new AccessorException("Cannot apply entry added event because value is missing");
1330 boolean hadValue = containsKey(ea.key.getBinding(), ea.key.getValue());
1331 if (hadValue) throw new AccessorException("Could not add entry to key that already existed");
1334 rollback = new MapEntryRemoved( ea.key );
1337 putNoflush(ea.key.getBinding(), ea.key.getValue(), ea.value.getBinding(), ea.value.getValue());
1340 } else if (e instanceof MapEntryRemoved) {
1341 MapEntryRemoved er = (MapEntryRemoved) e;
1344 boolean hadValue = containsKey(er.key.getBinding(), er.key.getValue());
1347 Object oldValueObj = get(er.key.getBinding(), er.key.getValue(), vb);
1348 MutableVariant oldKey = er.key;
1349 MutableVariant oldValue = new MutableVariant(vb, oldValueObj);
1350 rollback = new MapEntryAdded(oldKey, oldValue);
1352 rollback = new MapEntryRemoved( er.key.clone() );
1356 removeNoflush( er.key.getBinding(), er.key.getValue() );
1360 throw new AccessorException("Cannot apply "+e.getClass().getName()+" to Map Type");
1367 public void put(Binding keyBinding, Object key, Binding valueBinding,
1368 Object value) throws AccessorException {
1372 putNoflush(keyBinding, key, valueBinding, value);
1374 } catch (IOException e) {
1375 throw new AccessorException(e);
1382 public void putAll(Binding keyBinding, Binding valueBinding,
1383 Map<Object, Object> from) throws AccessorException {
1387 putAllNoflush(keyBinding, valueBinding, from);
1389 } catch (IOException e) {
1390 throw new AccessorException(e);
1397 public void putAll(Binding keyBinding, Binding valueBinding, Object[] keys,
1398 Object[] values) throws AccessorException {
1402 putAllNoflush(keyBinding, valueBinding, keys, values);
1404 } catch (IOException e) {
1405 throw new AccessorException(e);
1412 public void remove(Binding keyBinding, Object key) throws AccessorException {
1416 removeNoflush(keyBinding, key);
1418 } catch (IOException e) {
1419 throw new AccessorException(e);
1426 /** Interface for a search structure */
1427 abstract class Index {
1431 * @return if >0 position of existing entry of same key, <0 insertion position
1432 * @throws AccessorException
1434 abstract long getInsertPos(Object key) throws AccessorException;
1436 abstract Entry getKey(Object key) throws AccessorException;
1437 abstract Entry floor(Object key) throws AccessorException;
1438 abstract Entry ceiling(Object key) throws AccessorException;
1439 abstract Entry higher(Object key) throws AccessorException;
1440 abstract Entry lower(Object key) throws AccessorException;
1441 abstract long size(Entry e) throws AccessorException;
1443 Entry first() throws AccessorException {
1446 int count = b.readInt();
1447 if (count==0) return null;
1448 Object k = ks.deserialize(b);
1449 java.lang.ref.Reference<BinaryObject> ref = children.get(k);
1450 BinaryObject sa = ref == null ? null : ref.get();
1451 return new Entry(k, 4, sa);
1452 } catch (IOException e) {
1453 throw new AccessorException(e);
1457 abstract Entry last() throws AccessorException;
1461 static class Entry {
1462 // Optional child accessor
1463 BinaryObject accessor;
1466 public Entry(Object key, long pos, BinaryObject accessor) {
1467 this.key = key; this.pos = pos; this.accessor = accessor;
1471 /** Entries are indexed a table */
1472 // class Table implements Index {
1475 /** Entry size is constant, binary Search */
1476 class Constant extends Index {
1478 Entry last() throws AccessorException {
1480 if (b.length()<=4) return null;
1481 long pos = b.length() - constantSize;
1483 Object key = ks.deserialize(b);
1484 return new Entry(key, pos, null);
1485 } catch (IOException e) {
1486 throw new AccessorException(e);
1492 long getInsertPos(Object key) throws AccessorException {
1494 int count = count();
1495 if (count==0) return -4L;
1497 // Check if it is the last entry
1498 long pos = b.length() - constantSize;
1500 Object lastKey = ks.deserialize(b);
1501 int c = kb.compare(lastKey, key);
1502 if (c<0) return -b.length();
1503 if (c==0) return pos;
1505 // We can narrow down the search to region between two existing children
1506 Entry fc = floorChildEntry(key);
1507 Entry cc = ceilingChildEntry(key);
1509 int fromIndex = fc == null ? 0 : indexOf(fc);
1510 int toIndex = cc == null ? count : indexOf(cc)+1;
1513 int r = binarySearch(fromIndex, toIndex, key);
1514 if (r>=0) return getPos(r);
1516 if (r==count) return -b.length();
1518 } catch (IOException e) {
1519 throw new AccessorException(e);
1520 } catch (BindingException e) {
1521 throw new AccessorException(e);
1525 int indexOf(Entry e) {
1526 return (int) ((e.pos - 4L) / constantSize);
1528 int indexOf(long pos) {
1529 return (int) ((pos - 4L) / constantSize);
1536 * @param toIndex exclusive
1539 * @throws AccessorException
1541 int binarySearch(int fromIndex, int toIndex, Object key) throws AccessorException {
1542 int low = fromIndex;
1543 int high = toIndex - 1;
1545 while (low <= high) {
1546 int mid = (low + high) >>> 1;
1547 Object midVal = getKey(mid);
1548 int cmp = kb.compare(midVal, key);
1555 return mid; // key found
1557 return -(low + 1); // key not found.
1561 public Entry getKey(Object key) throws AccessorException {
1562 BinaryObject sa = getChild(key);
1563 if (sa!=null) return new Entry(key, sa.b.getStartPositionInSourceBinary(), sa);
1564 long pos = getInsertPos(key);
1565 if (pos<0) return null;
1566 return new Entry(key, pos, null);
1570 public long size(Entry e) {
1571 return constantSize;
1574 Object getKey(int index) throws AccessorException {
1576 long pos = 4L + ((long)index) * constantSize;
1578 return ks.deserialize(b);
1579 } catch (IOException e) {
1580 throw new AccessorException(e);
1584 Entry getEntry(int index) throws AccessorException {
1586 long pos = 4L + ((long)index) * constantSize;
1588 Object key = ks.deserialize(b);
1589 return new Entry(key, pos, null);
1590 } catch (IOException e) {
1591 throw new AccessorException(e);
1595 long getPos(int index) {
1596 return 4L + ((long)index) * constantSize;
1599 int count() throws IOException {
1600 return (int) ((b.length()-4) / constantSize);
1604 Entry ceiling(Object key) throws AccessorException {
1606 long pos = getInsertPos(key);
1608 if (pos>0) return new Entry(key, pos, getChild(key));
1610 int index = indexOf(pos);
1611 if (index>=count()) return null;
1612 key = getKeyAt(pos);
1613 return new Entry(key, pos, null);
1614 } catch (IOException e) {
1615 throw new AccessorException(e);
1616 } catch (BindingException e) {
1617 throw new AccessorException(e);
1622 Entry higher(Object key) throws AccessorException {
1624 long pos = getInsertPos(key);
1628 int index = indexOf(pos)+1;
1629 if (index>=count()) return null;
1630 pos = getPos(index);
1631 key = getKeyAt(pos);
1632 return new Entry(key, pos, null);
1634 // Insert here match
1635 int index = indexOf(-pos);
1636 if (index>=count()) return null;
1637 pos = getPos(index);
1638 key = getKeyAt(pos);
1639 return new Entry(key, pos, null);
1641 } catch (IOException e) {
1642 throw new AccessorException(e);
1643 } catch (BindingException e) {
1644 throw new AccessorException(e);
1650 Entry lower(Object key) throws AccessorException {
1652 long pos = getInsertPos(key);
1655 int index = indexOf(pos)-1;
1656 if (index<0) return null;
1657 pos = getPos(index);
1658 key = getKeyAt(pos);
1659 return new Entry(key, pos, null);
1661 int index = indexOf(-pos)-1;
1662 if (index<0) return null;
1663 pos = getPos(index);
1664 key = getKeyAt(pos);
1665 return new Entry(key, pos, null);
1667 } catch (IOException e) {
1668 throw new AccessorException(e);
1669 } catch (BindingException e) {
1670 throw new AccessorException(e);
1675 Entry floor(Object key) throws AccessorException {
1677 long pos = getInsertPos(key);
1679 if (pos>0) return new Entry(key, pos, getChild(key));
1680 int index = indexOf(-pos)-1;
1681 if (index<0) return null;
1682 pos = getPos(index);
1683 key = getKeyAt(pos);
1684 return new Entry(key, pos, null);
1685 } catch (IOException e) {
1686 throw new AccessorException(e);
1687 } catch (BindingException e) {
1688 throw new AccessorException(e);
1694 /** Variable size enetry, Sequential search */
1695 class Sequential extends Index {
1700 * @return if >0 position of existing entry of same key, <0 insertion position
1701 * @throws AccessorException
1704 long getInsertPos(Object key) throws AccessorException {
1706 Entry start = floorChildEntry(key);
1708 if (start !=null && kb.equals(key, start.key)) {
1712 long len = b.length();
1713 long pos = start==null ? 4L : start.pos;
1715 while (b.position()<len) {
1717 Object k = ks.deserialize(b, null);
1718 int c = kb.compare(key, k);
1719 if (c==0) return pos;
1720 if (c<0) return -pos;
1724 } catch (IOException e) {
1725 throw new AccessorException(e);
1726 } catch (BindingException e) {
1727 throw new AccessorException(e);
1732 Entry getKey(Object key) throws AccessorException {
1733 BinaryObject sa = getChild(key);
1734 if (sa!=null) return new Entry(key, sa.b.getStartPositionInSourceBinary(), sa);
1736 long pos = getInsertPos(key);
1737 if (pos<0) return null;
1738 return new Entry(key, pos, null);
1742 Entry last() throws AccessorException {
1744 Entry e = lastChildEntry();
1745 long startPos = e!=null ? e.pos : 4L;
1746 b.position(startPos);
1747 Entry result = e!=null ? new Entry(e.key, e.pos, e.accessor) : new Entry(null, 0, null);
1748 while (b.position() < b.length()) {
1749 result.key = ks.deserialize(b, null);
1750 result.pos = b.position();
1752 long valueLen = b.position() - result.pos;
1753 result.accessor = createSubAccessor(vb.type(), result.pos, valueLen, params);
1754 children.put(result.key, new SoftReference<BinaryObject>( result.accessor ));
1756 return (result.key == null) ? null : result;
1757 } catch (IOException e) {
1758 throw new AccessorException(e);
1759 } catch (BindingException e) {
1760 throw new AccessorException(e);
1761 } catch (AccessorConstructionException e) {
1762 throw new AccessorException(e);
1767 long size(Entry e) throws AccessorException {
1770 if (ks.getConstantSize()!=null) {
1771 keyLen = ks.getConstantSize();
1775 keyLen = b.position() - e.pos;
1779 if (e.accessor!=null) {
1780 valueLen = e.accessor.b.length();
1781 } else if (vs.getConstantSize()!=null) {
1782 valueLen = vs.getConstantSize();
1784 long pos = e.pos + keyLen;
1787 valueLen = b.position() - pos;
1789 return keyLen + valueLen;
1790 } catch (IOException e1) {
1791 throw new AccessorException(e1);
1796 Entry ceiling(Object key) throws AccessorException {
1798 long pos = getInsertPos(key);
1800 if (pos>0) return new Entry(key, pos, getChild(key));
1802 return getEntryAt(pos);
1803 } catch (IOException e) {
1804 throw new AccessorException(e);
1805 } catch (BindingException e) {
1806 throw new AccessorException(e);
1811 Entry higher(Object key) throws AccessorException {
1813 long pos = getInsertPos(key);
1816 if (pos>=b.length()) return null;
1820 return getEntryAt(b.position());
1823 return getEntryAt(pos);
1824 } catch (IOException e) {
1825 throw new AccessorException(e);
1826 } catch (BindingException e) {
1827 throw new AccessorException(e);
1832 Entry lower(Object key) throws AccessorException {
1834 Entry start = lowerChildEntry(key);
1835 long len = b.length();
1836 long pos = start==null ? 4L : start.pos;
1839 Object prevK = null;
1841 while (b.position()<len) {
1845 k = ks.deserialize(b, null);
1846 long valuePos = b.position();
1848 // Compare current key with search key
1849 int c = kb.compare(key, k);
1851 if (prevK==null) return null;
1852 return new Entry(prevK, prevPos, null);
1855 long valueLen = b.position() - valuePos;
1856 assert(valueLen>=0);
1857 java.lang.ref.Reference<BinaryObject> ref = children.get(k);
1858 BinaryObject sa = ref!=null?ref.get():null;
1860 sa = createSubAccessor(vb.type(), valuePos, valueLen, params);
1861 children.put(k, new SoftReference<BinaryObject>(sa));
1864 // There was no match, return the last entry
1865 return new Entry(k, pos, null);
1866 } catch (IOException e) {
1867 throw new AccessorException(e);
1868 } catch (BindingException e) {
1869 throw new AccessorException(e);
1870 } catch (AccessorConstructionException e) {
1871 throw new AccessorException(e);
1876 Entry floor(Object key) throws AccessorException {
1878 Entry start = floorChildEntry(key);
1880 if (start !=null && kb.equals(key, start.key)) {
1884 long len = b.length();
1885 long pos = start==null ? 4L : start.pos;
1888 Object prevK = null;
1889 BinaryObject prevAccessor = null;
1891 while (b.position()<len) {
1895 k = ks.deserialize(b, null);
1896 long valuePos = b.position();
1898 int c = kb.compare(key, k);
1901 if (prevK==null) return null;
1902 return new Entry(prevK, prevPos, prevAccessor);
1905 long valueLen = valuePos - pos;
1906 java.lang.ref.Reference<BinaryObject> ref = children.get(k);
1907 BinaryObject sa = ref!=null?ref.get():null;
1909 prevAccessor = createSubAccessor(vb.type(), valuePos, valueLen, params);
1910 children.put(k, new SoftReference<BinaryObject>(prevAccessor));
1914 return new Entry(k, pos, prevAccessor);
1917 return new Entry(k, pos, prevAccessor);
1918 } catch (IOException e) {
1919 throw new AccessorException(e);
1920 } catch (BindingException e) {
1921 throw new AccessorException(e);
1922 } catch (AccessorConstructionException e) {
1923 throw new AccessorException(e);