1 | package com.hammurapi.store; |
2 | |
3 | import java.lang.reflect.InvocationHandler; |
4 | import java.lang.reflect.Method; |
5 | import java.lang.reflect.Proxy; |
6 | import java.util.ArrayList; |
7 | import java.util.Collection; |
8 | import java.util.Collections; |
9 | import java.util.Comparator; |
10 | import java.util.Iterator; |
11 | import java.util.LinkedList; |
12 | import java.util.List; |
13 | import java.util.Map; |
14 | import java.util.concurrent.ExecutorService; |
15 | import java.util.concurrent.atomic.AtomicBoolean; |
16 | import java.util.concurrent.atomic.AtomicInteger; |
17 | import java.util.concurrent.locks.Lock; |
18 | |
19 | import com.hammurapi.extract.Extractor; |
20 | import com.hammurapi.extract.Predicate; |
21 | import com.hammurapi.store.Store.Handle; |
22 | |
23 | public abstract class AbstractIndex<T, PK, V, S extends Store<T,PK,S>> implements OrderedIndex<T, PK, V, S> { |
24 | |
25 | private Predicate<T, S> predicate; |
26 | private Extractor<T, V, S> extractor; |
27 | protected Index.Type type; |
28 | protected boolean ordered; |
29 | protected Comparator<V> comparator; |
30 | protected AbstractStore<T, PK, S> store; |
31 | protected AtomicBoolean isCorrupt = new AtomicBoolean(false); |
32 | |
33 | protected AbstractIndex( |
34 | Predicate<T, S> predicate, |
35 | Extractor<T, V, S> extractor, |
36 | Index.Type type, |
37 | boolean ordered, |
38 | Comparator<V> comparator, |
39 | AbstractStore<T,PK,S> store) { |
40 | this.predicate = predicate; |
41 | this.extractor = extractor; |
42 | this.type = type; |
43 | this.ordered = ordered; |
44 | this.comparator = comparator; |
45 | this.store = store; |
46 | } |
47 | |
48 | /** |
49 | * @return Index unique store. If index is ordered, the index store |
50 | * shall be of type SortedMap. |
51 | */ |
52 | protected abstract Map<V, Handle<T,PK,S>> getIndexUniqueStore(); |
53 | |
54 | /** |
55 | * @return Index multi-store. If index is ordered, the index store |
56 | * shall be of type SortedMap. |
57 | */ |
58 | protected abstract Map<V, Collection<Handle<T,PK,S>>> getIndexMultiStore(); |
59 | |
60 | protected abstract Lock readLock(); |
61 | |
62 | protected abstract Lock writeLock(); |
63 | |
64 | /** |
65 | * Upgrades index type. |
66 | * @param type Asynchronous and lazy indices can be |
67 | * upgraded to synchronous. All index types can be upgraded |
68 | * to unique if current index data does not contain duplicates. |
69 | * @param ordered unordered index can be upgraded to ordered. |
70 | */ |
71 | public abstract void upgrade(Index.Type type, boolean ordered, Comparator<V> comparator); |
72 | |
73 | Collection<Handle<T,PK,S>> getHandles() { |
74 | checkCorrupt(); |
75 | applyUpdates(); |
76 | try { |
77 | Collection<Handle<T,PK,S>> ret = new LinkedList<Handle<T,PK,S>>(); |
78 | if (isUnique()) { |
79 | for (Handle<T,PK,S> h: getIndexUniqueStore().values()) { |
80 | if (h.isValid()) { |
81 | ret.add(h); |
82 | } |
83 | } |
84 | } else { |
85 | for (Collection<Handle<T,PK,S>> ch: getIndexMultiStore().values()) { |
86 | for (Handle<T,PK,S> h: ch) { |
87 | if (h.isValid()) { |
88 | ret.add(h); |
89 | } |
90 | } |
91 | } |
92 | } |
93 | return ret; |
94 | } finally { |
95 | readLock().unlock(); |
96 | } |
97 | } |
98 | |
99 | @Override |
100 | public Iterator<T> iterator() { |
101 | checkCorrupt(); |
102 | getStore().readLock().lock(); |
103 | try { |
104 | applyUpdates(); |
105 | try { |
106 | Collection<T> ret = new LinkedList<T>(); |
107 | if (isUnique()) { |
108 | for (Handle<T,PK,S> h: getIndexUniqueStore().values()) { |
109 | if (h.isValid()) { |
110 | ret.add(h.get()); |
111 | } |
112 | } |
113 | } else { |
114 | for (Collection<Handle<T,PK,S>> ch: getIndexMultiStore().values()) { |
115 | for (Handle<T,PK,S> h: ch) { |
116 | if (h.isValid()) { |
117 | ret.add(h.get()); |
118 | } |
119 | } |
120 | } |
121 | } |
122 | return ret.iterator(); |
123 | } finally { |
124 | readLock().unlock(); |
125 | } |
126 | } finally { |
127 | getStore().readLock().unlock(); |
128 | } |
129 | } |
130 | |
131 | @SuppressWarnings("unchecked") |
132 | @Override |
133 | public S getStore() { |
134 | return (S) store; |
135 | } |
136 | |
137 | @Override |
138 | public Predicate<T, S> getPredicate() { |
139 | return predicate; |
140 | } |
141 | |
142 | @Override |
143 | public Extractor<T, V, S> getExtractor() { |
144 | return extractor; |
145 | } |
146 | |
147 | @Override |
148 | public boolean isUnique() { |
149 | return Type.UNIQUE.equals(type); |
150 | } |
151 | |
152 | @Override |
153 | public boolean isOrdered() { |
154 | return ordered; |
155 | } |
156 | |
157 | @Override |
158 | public Comparator<V> getComparator() { |
159 | return comparator; |
160 | } |
161 | |
162 | private Comparator<V> naturalComparator = new NaturalComparator<V>(); |
163 | |
164 | protected abstract Collection<UpdateEntry> getPendingUpdates(); |
165 | |
166 | /** |
167 | * Updates index |
168 | * @param changed Changed/added handle. |
169 | * @param isNew If true, then handle was added, updated otherwise. |
170 | */ |
171 | public void update(Handle<T,PK,S> changed, boolean isNew) { |
172 | checkCorrupt(); |
173 | switch (type) { |
174 | case UNIQUE: |
175 | case SYNCHRONOUS: |
176 | writeLock().lock(); |
177 | try { |
178 | applyUpdate(changed, isNew); |
179 | } finally { |
180 | writeLock().unlock(); |
181 | } |
182 | break; |
183 | case ASYNCHRONOUS: |
184 | writeLock().lock(); |
185 | try { |
186 | getPendingUpdates().add(new UpdateEntry(changed, isNew)); |
187 | getExecutorService().submit(applyUpdatesTask); |
188 | } finally { |
189 | writeLock().unlock(); |
190 | } |
191 | break; |
192 | case LAZY: |
193 | writeLock().lock(); |
194 | try { |
195 | getPendingUpdates().add(new UpdateEntry(changed, isNew)); |
196 | } finally { |
197 | writeLock().unlock(); |
198 | } |
199 | break; |
200 | } |
201 | } |
202 | |
203 | protected class UpdateEntry { |
204 | Handle<T,PK,S> handle; |
205 | boolean isNew; |
206 | |
207 | public UpdateEntry(Handle<T, PK, S> handle, boolean isNew) { |
208 | super(); |
209 | this.handle = handle; |
210 | this.isNew = isNew; |
211 | } |
212 | |
213 | @Override |
214 | public int hashCode() { |
215 | final int prime = 31; |
216 | int result = 1; |
217 | result = prime * result + ((handle == null) ? 0 : handle.hashCode()); |
218 | result = prime * result + (isNew ? 1231 : 1237); |
219 | return result; |
220 | } |
221 | |
222 | @Override |
223 | public boolean equals(Object obj) { |
224 | if (this == obj) |
225 | return true; |
226 | if (obj == null) |
227 | return false; |
228 | if (getClass() != obj.getClass()) |
229 | return false; |
230 | UpdateEntry other = (UpdateEntry) obj; |
231 | if (handle == null) { |
232 | if (other.handle != null) |
233 | return false; |
234 | } else if (!handle.equals(other.handle)) |
235 | return false; |
236 | if (isNew != other.isNew) |
237 | return false; |
238 | return true; |
239 | } |
240 | |
241 | } |
242 | |
243 | protected abstract ExecutorService getExecutorService(); |
244 | |
245 | protected void checkCorrupt() { |
246 | if (isCorrupt.get()) { |
247 | throw new StoreException("Index is corrupt"); |
248 | } |
249 | } |
250 | |
251 | boolean isCorrupt() { |
252 | return isCorrupt.get(); |
253 | } |
254 | |
255 | protected Runnable applyUpdatesTask = new Runnable() { |
256 | |
257 | public void run() { |
258 | writeLock().lock(); |
259 | try { |
260 | Iterator<UpdateEntry> hit = getPendingUpdates().iterator(); |
261 | while (hit.hasNext()) { |
262 | UpdateEntry updateEntry = hit.next(); |
263 | applyUpdate(updateEntry.handle, updateEntry.isNew); |
264 | hit.remove(); |
265 | } |
266 | } catch (Exception e) { |
267 | isCorrupt.set(true); |
268 | handleAsynchException(e); |
269 | } finally { |
270 | writeLock().unlock(); |
271 | } |
272 | }; |
273 | }; |
274 | |
275 | |
276 | /** |
277 | * Applies pending updates, if any. This method acquires |
278 | * index write lock. If update operation is successful, |
279 | * then this method downgrades the lock to read lock. |
280 | * In the case of exception, write lock is released and |
281 | * read lock is not acquired. |
282 | */ |
283 | private void applyUpdates() { |
284 | writeLock().lock(); |
285 | try { |
286 | Iterator<UpdateEntry> hit = getPendingUpdates().iterator(); |
287 | while (hit.hasNext()) { |
288 | UpdateEntry updateEntry = hit.next(); |
289 | applyUpdate(updateEntry.handle, updateEntry.isNew); |
290 | hit.remove(); |
291 | } |
292 | readLock().lock(); |
293 | } finally { |
294 | writeLock().unlock(); |
295 | } |
296 | } |
297 | |
298 | private AtomicInteger granularity = new AtomicInteger(); |
299 | |
300 | /** |
301 | * This method is invoked within write lock, no need |
302 | * to acquire own lock. |
303 | * @param changed |
304 | */ |
305 | protected void applyUpdate(Handle<T,PK,S> changed, boolean isNew) { |
306 | if (isUnique()) { |
307 | Map<V, Handle<T, PK, S>> is = getIndexUniqueStore(); |
308 | if (!isNew) { |
309 | is.values().remove(changed); |
310 | } |
311 | if (predicate==null || changed.extract(predicate)) { |
312 | V key = extractor==null ? (V) changed.get() : changed.extract(extractor); |
313 | if (is.containsKey(key)) { |
314 | throw new StoreException("Violation of unique index: "+this); |
315 | } |
316 | is.put(key, changed); |
317 | } |
318 | granularity.set(is.size()); |
319 | } else { |
320 | Map<V, Collection<Handle<T, PK, S>>> is = getIndexMultiStore(); |
321 | if (!isNew) { |
322 | Iterator<Collection<Handle<T, PK, S>>> vit = is.values().iterator(); |
323 | while (vit.hasNext()) { |
324 | Collection<Handle<T, PK, S>> nextBucket = vit.next(); |
325 | if (nextBucket.remove(changed)) {; |
326 | if (nextBucket.isEmpty()) { |
327 | vit.remove(); |
328 | } |
329 | } |
330 | } |
331 | } |
332 | |
333 | if (predicate==null || changed.extract(predicate)) { |
334 | V key = extractor==null ? (V) changed.get() : changed.extract(extractor); |
335 | Collection<Handle<T, PK, S>> bucket = is.get(key); |
336 | if (bucket == null) { |
337 | bucket = new LinkedList<Store.Handle<T,PK,S>>(); |
338 | is.put(key, bucket); |
339 | } |
340 | bucket.add(changed); |
341 | } |
342 | |
343 | granularity.set(getIndexMultiStore().size()); |
344 | } |
345 | |
346 | } |
347 | |
348 | public int getGranularity() { |
349 | return granularity.get(); |
350 | } |
351 | |
352 | /** |
353 | * Handles exceptions thrown in asynchronous applyUpdates(). |
354 | * @param e |
355 | */ |
356 | protected abstract void handleAsynchException(Exception e); |
357 | |
358 | /** |
359 | * Removes invalid handles from index store. This method |
360 | * operates under store's write lock, so it is not necessary |
361 | * to acquire own lock. |
362 | */ |
363 | // TODO - invoke from store cleanup asynchronously. |
364 | public void cleanup() { |
365 | if (isUnique()) { |
366 | Iterator<Handle<T, PK, S>> hit = getIndexUniqueStore().values().iterator(); |
367 | while (hit.hasNext()) { |
368 | if (!hit.next().isValid()) { |
369 | hit.remove(); |
370 | } |
371 | } |
372 | } else { |
373 | Iterator<Collection<Handle<T, PK, S>>> chit = getIndexMultiStore().values().iterator(); |
374 | while (chit.hasNext()) { |
375 | Collection<Handle<T, PK, S>> ch = chit.next(); |
376 | Iterator<Handle<T, PK, S>> hit = ch.iterator(); |
377 | while (hit.hasNext()) { |
378 | if (!hit.next().isValid()) { |
379 | hit.remove(); |
380 | } |
381 | } |
382 | if (ch.isEmpty()) { |
383 | chit.remove(); |
384 | } |
385 | } |
386 | } |
387 | } |
388 | |
389 | private Iterable<T> findMulti(V value) { |
390 | checkCorrupt(); |
391 | applyUpdates(); |
392 | try { |
393 | if (isUnique()) { // For upgraded |
394 | Handle<T, PK, S> ret = getIndexUniqueStore().get(value); |
395 | if (ret==null || !ret.isValid()) { |
396 | return Collections.emptyList(); |
397 | } |
398 | return Collections.singleton(ret.get()); |
399 | } |
400 | |
401 | Collection<Handle<T, PK, S>> bucket = getIndexMultiStore().get(value); |
402 | if (bucket==null) { |
403 | return Collections.emptyList(); |
404 | } |
405 | Collection<T> ret = new ArrayList<T>(); |
406 | for (Handle<T,PK,S> h: bucket) { |
407 | if (h.isValid()) { |
408 | ret.add(h.get()); |
409 | } |
410 | } |
411 | return ret; |
412 | } finally { |
413 | readLock().unlock(); |
414 | } |
415 | } |
416 | |
417 | private T findUnique(V value) { |
418 | checkCorrupt(); |
419 | applyUpdates(); |
420 | try { |
421 | Handle<T, PK, S> ret = getIndexUniqueStore().get(value); |
422 | return ret!=null && ret.isValid() ? ret.get() : null; |
423 | } finally { |
424 | readLock().unlock(); |
425 | } |
426 | } |
427 | |
428 | public Iterable<T> find(V from, V to, boolean fromInclusive, boolean toInclusive) { |
429 | checkCorrupt(); |
430 | applyUpdates(); |
431 | try { |
432 | Collection<T> ret = new LinkedList<T>(); |
433 | // Step 1 - key set to array. |
434 | Collection<V> keys = isUnique() ? getIndexUniqueStore().keySet() : getIndexMultiStore().keySet(); |
435 | List<V> keyList = keys instanceof List ? (List<V>) keys : new ArrayList<V>(keys); |
436 | Comparator<V> theComparator = getComparator()==null ? naturalComparator : getComparator(); |
437 | int fromIdx = Collections.binarySearch(keyList, from, theComparator); |
438 | if (fromIdx<0) { |
439 | // -Insertion point - 1 |
440 | // Inclusiveness doesn't matter |
441 | fromIdx = -fromIdx - 1; |
442 | } else { |
443 | if (!fromInclusive) { |
444 | ++fromIdx; |
445 | } |
446 | } |
447 | |
448 | int toIdx = Collections.binarySearch(keyList, to, theComparator); |
449 | if (toIdx<0) { |
450 | // -Insertion point - 1 |
451 | // Inclusiveness doesn't matter |
452 | toIdx = -toIdx - 1; |
453 | } else { |
454 | if (!toInclusive) { |
455 | --toIdx; |
456 | } |
457 | } |
458 | |
459 | for (int i=fromIdx; i<=toIdx; ++i) { |
460 | V currentKey = keyList.get(i); |
461 | |
462 | if (isUnique()) { |
463 | Handle<T, PK, S> handle = getIndexUniqueStore().get(currentKey); |
464 | if (handle.isValid()) { |
465 | ret.add(handle.get()); |
466 | } |
467 | } else { |
468 | for (Handle<T,PK,S> h: getIndexMultiStore().get(currentKey)) { |
469 | if (h.isValid()) { |
470 | ret.add(h.get()); |
471 | } |
472 | } |
473 | } |
474 | } |
475 | return ret; |
476 | } finally { |
477 | readLock().unlock(); |
478 | } |
479 | } |
480 | |
481 | private InvocationHandler invocationHandler = new InvocationHandler() { |
482 | |
483 | @SuppressWarnings("unchecked") |
484 | @Override |
485 | public Object invoke(Object proxy, Method method, Object[] args) throws Throwable { |
486 | if (method.getName().equals("find") && method.getParameterTypes().length==1) { |
487 | if (UniqueIndex.class.equals(method.getDeclaringClass())) { |
488 | return findUnique((V) args[0]); |
489 | } |
490 | return findMulti((V) args[0]); |
491 | } |
492 | return method.invoke(AbstractIndex.this, args); |
493 | } |
494 | }; |
495 | |
496 | /** |
497 | * @return proxy which implements interfaces appropriate for the index type. |
498 | */ |
499 | @SuppressWarnings("unchecked") |
500 | public Index<T,PK,V,S> createProxy() { |
501 | if (isUnique()) { |
502 | if (isOrdered()) { |
503 | return (Index<T, PK, V, S>) Proxy.newProxyInstance(this.getClass().getClassLoader(), new Class[] {OrderedIndex.class, UniqueIndex.class}, invocationHandler); |
504 | } else { |
505 | return (Index<T, PK, V, S>) Proxy.newProxyInstance(this.getClass().getClassLoader(), new Class[] {UniqueIndex.class}, invocationHandler); |
506 | } |
507 | } else { |
508 | if (isOrdered()) { |
509 | return (Index<T, PK, V, S>) Proxy.newProxyInstance(this.getClass().getClassLoader(), new Class[] {OrderedIndex.class, MultiIndex.class}, invocationHandler); |
510 | } else { |
511 | return (Index<T, PK, V, S>) Proxy.newProxyInstance(this.getClass().getClassLoader(), new Class[] {MultiIndex.class}, invocationHandler); |
512 | } |
513 | } |
514 | } |
515 | |
516 | @Override |
517 | public String toString() { |
518 | return "AbstractIndex [predicate=" + predicate + ", extractor=" |
519 | + extractor + ", type=" + type + ", ordered=" + ordered |
520 | + ", comparator=" + comparator + ", isCorrupt=" + isCorrupt |
521 | + "]"; |
522 | } |
523 | |
524 | |
525 | |
526 | } |