Repository navigation
Expand file tree
/
Copy pathBind.java
More file actions
615 lines (575 loc) · 25.2 KB
/
Copy pathBind.java
File metadata and controls
615 lines (575 loc) · 25.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
/*
* Copyright (c) 2012 Jan Kotek
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.mapdb;
import java.util.Collections;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
/**
* Binding is simple yet powerful way to keep secondary collection synchronized with primary collection.
* Primary collection provides notification on updates and secondary collection is modified accordingly.
* This way MapDB provides secondary indexes, values and keys. It also supports less usual scenarios such
* as histograms, inverse lookup index (on maps), group counters and so on.
*
* There are two things to keep on mind when using binding:
*
* * Binding is not persistent, so it needs to be restored every time store is reopened.
* If you modify primary collection before binding is restored, secondary collection does not get updated and becomes
* inconsistent.
*
* * If secondary collection is empty, binding will recreate its content based on primary collection.
* If there is even single item on secondary collection, binding assumes it is consistent and leaves it as its.
*
* Any thread-safe collection can be used as secondary (not just collections provided by MapDB).
* This gives great flexibility for modeling
* and scaling your data. For example primary data can be stored in durable DB with transactions and large secondary
* indexes may be stored in other faster non-durable DB. Or primary collection may be stored on disk and smaller
* secondary index (such as category counters) can be stored in memory for faster lookups. Also you may use
* ordinary `java.util.*` collections (if they are thread safe) to get additional speed.
*
* There are many [code examples](https://github.com/jankotek/MapDB/tree/master/src/test/java/examples)
* how Collection Binding can be used.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
*
* @author Jan Kotek
*/
public final class Bind {
private Bind(){}
/**
* Listener called when `Map` is modified.
* @param <K> key type in map
* @param <V> value type in map
*/
public interface MapListener<K,V>{
/**
* Callback method called after `Map` was modified.
* It is called on insert, update or delete.
*
* MapDB collections do not support null keys or values.
* Null parameter may be than used to indicate operation:
*
*
*
* @param key key in map
* @param oldVal old value in map (if any, null on inserts)
* @param newVal new value in map (if any, null on deletes)
*/
void update(K key, V oldVal, V newVal);
}
/**
* Primary Maps must provide notifications when it is modified.
* So Primary Maps must implement this interface to allow registering callback listeners.
*
* @param <K> key type in map
* @param <V> value type in map
*/
public interface MapWithModificationListener<K,V> extends Map<K,V> {
/**
* Add new modification listener notified when Map has been updated
* @param listener callback interface notified when map changes
*/
public void modificationListenerAdd(MapListener<K, V> listener);
/**
* Remove registered notification listener
*
* @param listener callback interface notified when map changes
*/
public void modificationListenerRemove(MapListener<K, V> listener);
/**
*
* @return size of map, but in 64bit long which does not overflow at 2e9 items.
*/
public long sizeLong();
}
/**
* Binds {@link Atomic.Long} to Primary Map so the Atomic.Long contains size of Map.
* `Atomic.Long` is incremented on each insert and decremented on each entry removal.
* MapDB collections usually do not keep their size, but require complete traversal to count items.
*
* If `Atomic.Long` has zero value, it will be updated with value from `map.size()` and than
* bind to map.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
*
* NOTE: {@link BTreeMap} and {@link HTreeMap} already supports this directly as optional parameter named `counter`.
* In that case all calls to `Map.size()` are forwarded to underlying counter. Check parameters at
* {@link DB#createHashMap(String)} and
* {@link DB#createTreeMap(String)}
*
*
* @param map primary map whose size needs to be tracked
* @param sizeCounter number updated when Map Entry is added or removed.
*/
public static <K,V> void size(MapWithModificationListener<K,V> map, final Atomic.Long sizeCounter){
//set initial value first if necessary
if(sizeCounter.get() == 0){
long size = map.sizeLong();
if(sizeCounter.get()!=size)
sizeCounter.set(size);
}
map.modificationListenerAdd(new MapListener<K, V>() {
@Override
public void update(K key, V oldVal, V newVal) {
if (oldVal == null && newVal != null) {
sizeCounter.incrementAndGet();
} else if (oldVal != null && newVal == null) {
sizeCounter.decrementAndGet();
}
//update does not change collection size
}
});
}
/**
* Binds Secondary Map so that it contains Key from Primary Map and custom Value.
* Secondary Value is updated every time Primary Map is modified.
*
* If Secondary Map is empty its content will be recreated from Primary Map.
* This binding is not persistent. You need to restore it every time store is reopened.
*
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
* Type params:
*
* * `<K>` - key type in primary and Secondary Map
* * `<V>` - value type in Primary Map
* * `<V2>` - value type in Secondary Map
* .
* @param map Primary Map
* @param secondary Secondary Map with custom
* @param fun function which calculates secondary value from primary key and value
*/
public static <K,V, V2> void secondaryValue(MapWithModificationListener<K, V> map,
final Map<K, V2> secondary,
final Fun.Function2<V2, K, V> fun){
//fill if empty
if(secondary.isEmpty()){
for(Map.Entry<K,V> e:map.entrySet())
secondary.put(e.getKey(), fun.run(e.getKey(),e.getValue()));
}
//hook listener
map.modificationListenerAdd(new MapListener<K, V>() {
@Override
public void update(K key, V oldVal, V newVal) {
if (newVal == null) {
//removal
secondary.remove(key);
} else {
secondary.put(key, fun.run(key, newVal));
}
}
});
}
/**
* Binds Secondary Map so that it contains Key from Primary Map and custom Value.
* Secondary Value is updated every time Primary Map is modified.
*
* If Secondary Map is empty its content will be recreated from Primary Map.
* This binding is not persistent. You need to restore it every time store is reopened.
*
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
* Type params:
*
* * `<K>` - key type in primary and Secondary Map
* * `<V>` - value type in Primary Map
* * `<V2>` - value type in Secondary Map
* .
* @param map Primary Map
* @param secondary Secondary Map with custom
* @param fun function which calculates secondary values from primary key and value
*/
public static <K,V, V2> void secondaryValues(MapWithModificationListener<K, V> map,
final Set<Fun.Tuple2<K, V2>> secondary,
final Fun.Function2<V2[], K, V> fun){
//fill if empty
if(secondary.isEmpty()){
for(Map.Entry<K,V> e:map.entrySet()){
V2[] v = fun.run(e.getKey(),e.getValue());
if(v!=null)
for(V2 v2:v)
secondary.add(Fun.t2(e.getKey(), v2));
}
}
//hook listener
map.modificationListenerAdd(new MapListener<K, V>() {
@Override
public void update(K key, V oldVal, V newVal) {
if (newVal == null) {
//removal
V2[] v = fun.run(key, oldVal);
if (v != null)
for (V2 v2 : v)
secondary.remove(Fun.t2(key, v2));
} else if (oldVal == null) {
//insert
V2[] v = fun.run(key, newVal);
if (v != null)
for (V2 v2 : v)
secondary.add(Fun.t2(key, v2));
} else {
//update, must remove old key and insert new
V2[] oldv = fun.run(key, oldVal);
V2[] newv = fun.run(key, newVal);
if (oldv == null) {
//insert new
if (newv != null)
for (V2 v : newv)
secondary.add(Fun.t2(key, v));
return;
}
if (newv == null) {
//remove old
for (V2 v : oldv)
secondary.remove(Fun.t2(key, v));
return;
}
Set<V2> hashes = new HashSet<V2>();
Collections.addAll(hashes, oldv);
//add new non existing items
for (V2 v : newv) {
if (!hashes.contains(v)) {
secondary.add(Fun.t2(key, v));
}
}
//remove items which are in old, but not in new
for (V2 v : newv) {
hashes.remove(v);
}
for (V2 v : hashes) {
secondary.remove(Fun.t2(key, v));
}
}
}
});
}
/**
* Binds Secondary Set so it contains Secondary Key (Index). Usefull if you need
* to lookup Keys from Primary Map by custom criteria. Other use is for reverse lookup
*
* To lookup keys in Secondary Set use {@link Fun#filter(java.util.NavigableSet, Object)}
*
* If Secondary Set is empty its content will be recreated from Primary Map.
* This binding is not persistent. You need to restore it every time store is reopened.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
* Type params:
*
* * `<K>` - Key in Primary Map
* * `<V>` - Value in Primary Map
* * `<K2>` - Secondary
*
* @param map primary map
* @param secondary secondary set
* @param fun function which calculates Secondary Key from Primary Key and Value
*/
public static <K,V, K2> void secondaryKey(MapWithModificationListener<K, V> map,
final Set<Fun.Tuple2<K2, K>> secondary,
final Fun.Function2<K2, K, V> fun){
//fill if empty
if(secondary.isEmpty()){
for(Map.Entry<K,V> e:map.entrySet()){
secondary.add(Fun.t2(fun.run(e.getKey(),e.getValue()), e.getKey()));
}
}
//hook listener
map.modificationListenerAdd(new MapListener<K, V>() {
@Override
public void update(K key, V oldVal, V newVal) {
if (newVal == null) {
//removal
secondary.remove(Fun.t2(fun.run(key, oldVal), key));
} else if (oldVal == null) {
//insert
secondary.add(Fun.t2(fun.run(key, newVal), key));
} else {
//update, must remove old key and insert new
K2 oldKey = fun.run(key, oldVal);
K2 newKey = fun.run(key, newVal);
if (oldKey == newKey || oldKey.equals(newKey)) return;
secondary.remove(Fun.t2(oldKey, key));
secondary.add(Fun.t2(newKey, key));
}
}
});
}
/**
* Binds Secondary Set so it contains Secondary Key (Index). Usefull if you need
* to lookup Keys from Primary Map by custom criteria. Other use is for reverse lookup
*
* If Secondary Set is empty its content will be recreated from Primary Map.
* This binding is not persistent. You need to restore it every time store is reopened.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
* Type params:
*
* * `<K>` - Key in Primary Map
* * `<V>` - Value in Primary Map
* * `<K2>` - Secondary
*
* @param map primary map
* @param secondary secondary set
* @param fun function which calculates Secondary Key from Primary Key and Value
*/
public static <K,V, K2> void secondaryKey(MapWithModificationListener<K, V> map,
final Map<K2, K> secondary,
final Fun.Function2<K2, K, V> fun){
//fill if empty
if(secondary.isEmpty()){
for(Map.Entry<K,V> e:map.entrySet()){
secondary.put(fun.run(e.getKey(), e.getValue()), e.getKey());
}
}
//hook listener
map.modificationListenerAdd(new MapListener<K, V>() {
@Override
public void update(K key, V oldVal, V newVal) {
if (newVal == null) {
//removal
secondary.remove(fun.run(key, oldVal));
} else if (oldVal == null) {
//insert
secondary.put(fun.run(key, newVal), key);
} else {
//update, must remove old key and insert new
K2 oldKey = fun.run(key, oldVal);
K2 newKey = fun.run(key, newVal);
if (oldKey == newKey || oldKey.equals(newKey)) return;
secondary.remove(oldKey);
secondary.put(newKey, key);
}
}
});
}
/**
* Binds Secondary Set so it contains Secondary Key (Index). Useful if you need
* to lookup Keys from Primary Map by custom criteria. Other use is for reverse lookup
*
* To lookup keys in Secondary Set use {@link Fun#filter(java.util.NavigableSet, Object)}}
*
*
* If Secondary Set is empty its content will be recreated from Primary Map.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
*
* Type params:
*
* * `<K>` - Key in Primary Map
* * `<V>` - Value in Primary Map
* * `<K2>` - Secondary
*
* @param map primary map
* @param secondary secondary set
* @param fun function which calculates Secondary Keys from Primary Key and Value
*/
public static <K,V, K2> void secondaryKeys(MapWithModificationListener<K, V> map,
final Set<Fun.Tuple2<K2, K>> secondary,
final Fun.Function2<K2[], K, V> fun){
//fill if empty
if(secondary.isEmpty()){
for(Map.Entry<K,V> e:map.entrySet()){
K2[] k2 = fun.run(e.getKey(), e.getValue());
if(k2 != null)
for(K2 k22 :k2)
secondary.add(Fun.t2(k22, e.getKey()));
}
}
//hook listener
map.modificationListenerAdd(new MapListener<K, V>() {
@Override
public void update(K key, V oldVal, V newVal) {
if (newVal == null) {
//removal
K2[] k2 = fun.run(key, oldVal);
if (k2 != null)
for (K2 k22 : k2)
secondary.remove(Fun.t2(k22, key));
} else if (oldVal == null) {
//insert
K2[] k2 = fun.run(key, newVal);
if (k2 != null)
for (K2 k22 : k2)
secondary.add(Fun.t2(k22, key));
} else {
//update, must remove old key and insert new
K2[] oldk = fun.run(key, oldVal);
K2[] newk = fun.run(key, newVal);
if (oldk == null) {
//insert new
if (newk != null)
for (K2 k22 : newk)
secondary.add(Fun.t2(k22, key));
return;
}
if (newk == null) {
//remove old
for (K2 k22 : oldk)
secondary.remove(Fun.t2(k22, key));
return;
}
Set<K2> hashes = new HashSet<K2>();
Collections.addAll(hashes, oldk);
//add new non existing items
for (K2 k2 : newk) {
if (!hashes.contains(k2)) {
secondary.add(Fun.t2(k2, key));
}
}
//remove items which are in old, but not in new
for (K2 k2 : newk) {
hashes.remove(k2);
}
for (K2 k2 : hashes) {
secondary.remove(Fun.t2(k2, key));
}
}
}
});
}
/**
* Binds Secondary Set so it contains inverse mapping to Primary Map: Primary Value will become Secondary Key.
* This is useful for creating bi-directional Maps.
*
* To lookup keys in Secondary Set use {@link Fun#filter(java.util.NavigableSet, Object)}
*
* If Secondary Set is empty its content will be recreated from Primary Map.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
* Type params:
*
* * `<K>` - Key in Primary Map and Second Value in Secondary Set
* * `<V>` - Value in Primary Map and Primary Value in Secondary Set
*
* @param primary Primary Map for which inverse mapping will be created
* @param inverse Secondary Set which will contain inverse mapping
*/
public static <K,V> void mapInverse(MapWithModificationListener<K,V> primary,
Set<Fun.Tuple2<V, K>> inverse) {
Bind.secondaryKey(primary,inverse, new Fun.Function2<V, K,V>(){
@Override public V run(K key, V value) {
return value;
}
});
}
/**
* Binds Secondary Set so it contains inverse mapping to Primary Map: Primary Value will become Secondary Key.
* This is useful for creating bi-directional Maps.
*
* In this case some data may be lost, if there are duplicated primary values.
* It is recommended to use multimap: `NavigableSet<Fun.Tuple2<V,K>>` which
* handles value duplicities. Use @{link Bind.mapInverse(MapWithModificationListener<K,V>Set<Fun.Tuple2<V, K>>}
*
* If Secondary Set is empty its content will be recreated from Primary Map.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
* Type params:
*
* * `<K>` - Key in Primary Map and Second Value in Secondary Set
* * `<V>` - Value in Primary Map and Primary Value in Secondary Set
*
* @param primary Primary Map for which inverse mapping will be created
* @param inverse Secondary Set which will contain inverse mapping
*/
public static <K,V> void mapInverse(MapWithModificationListener<K,V> primary,
Map<V, K> inverse) {
Bind.secondaryKey(primary,inverse, new Fun.Function2<V, K,V>(){
@Override public V run(K key, V value) {
return value;
}
});
}
/**
* Binds Secondary Map so it it creates [histogram](http://en.wikipedia.org/wiki/Histogram) from
* data in Primary Map. Histogram keeps count how many items are in each category.
* This method takes function which defines in what category each Primary Map entry is in.
*
*
* If Secondary Map is empty its content will be recreated from Primary Map.
*
* NOTE: Binding just installs Modification Listener on primary collection. Binding itself is not persistent
* and has to be restored after primary collection is loaded. Data contained in secondary collection are persistent.
*
*
* Type params:
*
* * `<K>` - Key type in primary map
* * `<V>` - Value type in primary map
* * `<C>` - Category type
*
* @param primary Primary Map to create histogram for
* @param histogram Secondary Map to create histogram for, key is Category, value is number of items in category
* @param entryToCategory returns Category in which entry from Primary Map belongs to.
*/
public static <K,V,C> void histogram(MapWithModificationListener<K,V> primary, final ConcurrentMap<C,Long> histogram,
final Fun.Function2<C, K, V> entryToCategory){
MapListener<K,V> listener = new MapListener<K, V>() {
@Override public void update(K key, V oldVal, V newVal) {
if(newVal == null){
//removal
C category = entryToCategory.run(key,oldVal);
incrementHistogram(category, -1);
}else if(oldVal==null){
//insert
C category = entryToCategory.run(key,newVal);
incrementHistogram(category, 1);
}else{
//update, must remove old key and insert new
C oldCat = entryToCategory.run(key, oldVal);
C newCat = entryToCategory.run(key, newVal);
if(oldCat == newCat || oldCat.equals(newCat)) return;
incrementHistogram(oldCat,-1);
incrementHistogram(oldCat,1);
}
}
/** atomically update counter in histogram*/
private void incrementHistogram(C category, long i) {
for(;;){
Long oldCount = histogram.get(category);
if(oldCount == null){
//insert new count
if(histogram.putIfAbsent(category,i) == null)
return;
}else{
//increase existing count
Long newCount = oldCount+i;
if(histogram.replace(category,oldCount, newCount))
return;
}
}
}
};
primary.modificationListenerAdd(listener);
}
}