001 /**
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.activemq.kaha.impl.container;
018
019 import java.io.IOException;
020 import java.util.ArrayList;
021 import java.util.Collection;
022 import java.util.Iterator;
023 import java.util.List;
024 import java.util.ListIterator;
025
026 import org.apache.activemq.kaha.ContainerId;
027 import org.apache.activemq.kaha.ListContainer;
028 import org.apache.activemq.kaha.Marshaller;
029 import org.apache.activemq.kaha.RuntimeStoreException;
030 import org.apache.activemq.kaha.Store;
031 import org.apache.activemq.kaha.StoreEntry;
032 import org.apache.activemq.kaha.StoreLocation;
033 import org.apache.activemq.kaha.impl.DataManager;
034 import org.apache.activemq.kaha.impl.data.Item;
035 import org.apache.activemq.kaha.impl.index.IndexItem;
036 import org.apache.activemq.kaha.impl.index.IndexManager;
037 import org.slf4j.Logger;
038 import org.slf4j.LoggerFactory;
039
040 /**
041 * Implementation of a ListContainer
042 *
043 *
044 */
045 public class ListContainerImpl extends BaseContainerImpl implements ListContainer {
046
047 private static final Logger LOG = LoggerFactory.getLogger(ListContainerImpl.class);
048 protected Marshaller marshaller = Store.OBJECT_MARSHALLER;
049
050 public ListContainerImpl(ContainerId id, IndexItem root, IndexManager indexManager,
051 DataManager dataManager, boolean persistentIndex) throws IOException {
052 super(id, root, indexManager, dataManager, persistentIndex);
053 }
054
055 /*
056 * (non-Javadoc)
057 *
058 * @see org.apache.activemq.kaha.ListContainer#load()
059 */
060 public synchronized void load() {
061 checkClosed();
062 if (!loaded) {
063 if (!loaded) {
064 loaded = true;
065 try {
066 init();
067 long nextItem = root.getNextItem();
068 while (nextItem != Item.POSITION_NOT_SET) {
069 IndexItem item = indexManager.getIndex(nextItem);
070 indexList.add(item);
071 itemAdded(item, indexList.size() - 1, getValue(item));
072 nextItem = item.getNextItem();
073 }
074 } catch (IOException e) {
075 LOG.error("Failed to load container " + getId(), e);
076 throw new RuntimeStoreException(e);
077 }
078 }
079 }
080 }
081
082 /*
083 * (non-Javadoc)
084 *
085 * @see org.apache.activemq.kaha.ListContainer#unload()
086 */
087 public synchronized void unload() {
088 checkClosed();
089 if (loaded) {
090 loaded = false;
091 indexList.clear();
092
093 }
094 }
095
096 /*
097 * (non-Javadoc)
098 *
099 * @see org.apache.activemq.kaha.ListContainer#setKeyMarshaller(org.apache.activemq.kaha.Marshaller)
100 */
101 public synchronized void setMarshaller(Marshaller marshaller) {
102 checkClosed();
103 this.marshaller = marshaller;
104 }
105
106 public synchronized boolean equals(Object obj) {
107 load();
108 boolean result = false;
109 if (obj != null && obj instanceof List) {
110 List other = (List)obj;
111 result = other.size() == size();
112 if (result) {
113 for (int i = 0; i < indexList.size(); i++) {
114 Object o1 = other.get(i);
115 Object o2 = get(i);
116 result = o1 == o2 || (o1 != null && o2 != null && o1.equals(o2));
117 if (!result) {
118 break;
119 }
120 }
121 }
122 }
123 return result;
124 }
125
126 public int hashCode() {
127 return super.hashCode();
128 }
129
130 /*
131 * (non-Javadoc)
132 *
133 * @see org.apache.activemq.kaha.ListContainer#size()
134 */
135 public synchronized int size() {
136 load();
137 return indexList.size();
138 }
139
140 /*
141 * (non-Javadoc)
142 *
143 * @see org.apache.activemq.kaha.ListContainer#addFirst(java.lang.Object)
144 */
145 public synchronized void addFirst(Object o) {
146 internalAddFirst(o);
147 }
148
149 /*
150 * (non-Javadoc)
151 *
152 * @see org.apache.activemq.kaha.ListContainer#addLast(java.lang.Object)
153 */
154 public synchronized void addLast(Object o) {
155 internalAddLast(o);
156 }
157
158 /*
159 * (non-Javadoc)
160 *
161 * @see org.apache.activemq.kaha.ListContainer#removeFirst()
162 */
163 public synchronized Object removeFirst() {
164 load();
165 Object result = null;
166 IndexItem item = indexList.getFirst();
167 if (item != null) {
168 itemRemoved(0);
169 result = getValue(item);
170 IndexItem prev = root;
171 IndexItem next = indexList.size() > 1 ? (IndexItem)indexList.get(1) : null;
172 indexList.removeFirst();
173
174 delete(item, prev, next);
175 item = null;
176 }
177 return result;
178 }
179
180 /*
181 * (non-Javadoc)
182 *
183 * @see org.apache.activemq.kaha.ListContainer#removeLast()
184 */
185 public synchronized Object removeLast() {
186 load();
187 Object result = null;
188 IndexItem last = indexList.getLast();
189 if (last != null) {
190 itemRemoved(indexList.size() - 1);
191 result = getValue(last);
192 IndexItem prev = indexList.getPrevEntry(last);
193 IndexItem next = null;
194 indexList.removeLast();
195 delete(last, prev, next);
196 }
197 return result;
198 }
199
200 /*
201 * (non-Javadoc)
202 *
203 * @see java.util.List#isEmpty()
204 */
205 public synchronized boolean isEmpty() {
206 load();
207 return indexList.isEmpty();
208 }
209
210 /*
211 * (non-Javadoc)
212 *
213 * @see java.util.List#contains(java.lang.Object)
214 */
215 public synchronized boolean contains(Object o) {
216 load();
217 boolean result = false;
218 if (o != null) {
219 IndexItem next = indexList.getFirst();
220 while (next != null) {
221 Object value = getValue(next);
222 if (value != null && value.equals(o)) {
223 result = true;
224 break;
225 }
226 next = indexList.getNextEntry(next);
227 }
228 }
229 return result;
230 }
231
232 /*
233 * (non-Javadoc)
234 *
235 * @see java.util.List#iterator()
236 */
237 public synchronized Iterator iterator() {
238 load();
239 return listIterator();
240 }
241
242 /*
243 * (non-Javadoc)
244 *
245 * @see java.util.List#toArray()
246 */
247 public synchronized Object[] toArray() {
248 load();
249 List<Object> tmp = new ArrayList<Object>(indexList.size());
250 IndexItem next = indexList.getFirst();
251 while (next != null) {
252 Object value = getValue(next);
253 tmp.add(value);
254 next = indexList.getNextEntry(next);
255 }
256 return tmp.toArray();
257 }
258
259 /*
260 * (non-Javadoc)
261 *
262 * @see java.util.List#toArray(T[])
263 */
264 public synchronized Object[] toArray(Object[] a) {
265 load();
266 List<Object> tmp = new ArrayList<Object>(indexList.size());
267 IndexItem next = indexList.getFirst();
268 while (next != null) {
269 Object value = getValue(next);
270 tmp.add(value);
271 next = indexList.getNextEntry(next);
272 }
273 return tmp.toArray(a);
274 }
275
276 /*
277 * (non-Javadoc)
278 *
279 * @see java.util.List#add(E)
280 */
281 public synchronized boolean add(Object o) {
282 load();
283 addLast(o);
284 return true;
285 }
286
287 /*
288 * (non-Javadoc)
289 *
290 * @see java.util.List#remove(java.lang.Object)
291 */
292 public synchronized boolean remove(Object o) {
293 load();
294 boolean result = false;
295 int pos = 0;
296 IndexItem next = indexList.getFirst();
297 while (next != null) {
298 Object value = getValue(next);
299 if (value != null && value.equals(o)) {
300 remove(next);
301 itemRemoved(pos);
302 result = true;
303 break;
304 }
305 next = indexList.getNextEntry(next);
306 pos++;
307 }
308 return result;
309 }
310
311 protected synchronized void remove(IndexItem item) {
312 IndexItem prev = indexList.getPrevEntry(item);
313 IndexItem next = indexList.getNextEntry(item);
314 indexList.remove(item);
315
316 delete(item, prev, next);
317 }
318
319 /*
320 * (non-Javadoc)
321 *
322 * @see java.util.List#containsAll(java.util.Collection)
323 */
324 public synchronized boolean containsAll(Collection c) {
325 load();
326 for (Iterator i = c.iterator(); i.hasNext();) {
327 Object obj = i.next();
328 if (!contains(obj)) {
329 return false;
330 }
331 }
332 return true;
333 }
334
335 /*
336 * (non-Javadoc)
337 *
338 * @see java.util.List#addAll(java.util.Collection)
339 */
340 public synchronized boolean addAll(Collection c) {
341 load();
342 for (Iterator i = c.iterator(); i.hasNext();) {
343 add(i.next());
344 }
345 return true;
346 }
347
348 /*
349 * (non-Javadoc)
350 *
351 * @see java.util.List#addAll(int, java.util.Collection)
352 */
353 public synchronized boolean addAll(int index, Collection c) {
354 load();
355 boolean result = false;
356 ListIterator e1 = listIterator(index);
357 Iterator e2 = c.iterator();
358 while (e2.hasNext()) {
359 e1.add(e2.next());
360 result = true;
361 }
362 return result;
363 }
364
365 /*
366 * (non-Javadoc)
367 *
368 * @see java.util.List#removeAll(java.util.Collection)
369 */
370 public synchronized boolean removeAll(Collection c) {
371 load();
372 boolean result = true;
373 for (Iterator i = c.iterator(); i.hasNext();) {
374 Object obj = i.next();
375 result &= remove(obj);
376 }
377 return result;
378 }
379
380 /*
381 * (non-Javadoc)
382 *
383 * @see java.util.List#retainAll(java.util.Collection)
384 */
385 public synchronized boolean retainAll(Collection c) {
386 load();
387 List<Object> tmpList = new ArrayList<Object>();
388 IndexItem next = indexList.getFirst();
389 while (next != null) {
390 Object o = getValue(next);
391 if (!c.contains(o)) {
392 tmpList.add(o);
393 }
394 next = indexList.getNextEntry(next);
395 }
396 for (Iterator<Object> i = tmpList.iterator(); i.hasNext();) {
397 remove(i.next());
398 }
399 return !tmpList.isEmpty();
400 }
401
402 /*
403 * (non-Javadoc)
404 *
405 * @see java.util.List#clear()
406 */
407 public synchronized void clear() {
408 checkClosed();
409 super.clear();
410 doClear();
411
412 }
413
414 /*
415 * (non-Javadoc)
416 *
417 * @see java.util.List#get(int)
418 */
419 public synchronized Object get(int index) {
420 load();
421 Object result = null;
422 IndexItem item = indexList.get(index);
423 if (item != null) {
424 result = getValue(item);
425 }
426 return result;
427 }
428
429 /*
430 * (non-Javadoc)
431 *
432 * @see java.util.List#set(int, E)
433 */
434 public synchronized Object set(int index, Object element) {
435 load();
436 Object result = null;
437 IndexItem replace = indexList.isEmpty() ? null : (IndexItem)indexList.get(index);
438 IndexItem prev = (indexList.isEmpty() || (index - 1) < 0) ? null : (IndexItem)indexList
439 .get(index - 1);
440 IndexItem next = (indexList.isEmpty() || (index + 1) >= size()) ? null : (IndexItem)indexList
441 .get(index + 1);
442 result = getValue(replace);
443 indexList.remove(index);
444 delete(replace, prev, next);
445 itemRemoved(index);
446 add(index, element);
447 return result;
448 }
449
450 protected synchronized IndexItem internalSet(int index, Object element) {
451 IndexItem replace = indexList.isEmpty() ? null : (IndexItem)indexList.get(index);
452 IndexItem prev = (indexList.isEmpty() || (index - 1) < 0) ? null : (IndexItem)indexList
453 .get(index - 1);
454 IndexItem next = (indexList.isEmpty() || (index + 1) >= size()) ? null : (IndexItem)indexList
455 .get(index + 1);
456 indexList.remove(index);
457 delete(replace, prev, next);
458 itemRemoved(index);
459 return internalAdd(index, element);
460 }
461
462 /*
463 * (non-Javadoc)
464 *
465 * @see java.util.List#add(int, E)
466 */
467 public synchronized void add(int index, Object element) {
468 load();
469 IndexItem item = insert(index, element);
470 indexList.add(index, item);
471 itemAdded(item, index, element);
472 }
473
474 protected synchronized StoreEntry internalAddLast(Object o) {
475 load();
476 IndexItem item = writeLast(o);
477 indexList.addLast(item);
478 itemAdded(item, indexList.size() - 1, o);
479 return item;
480 }
481
482 protected synchronized StoreEntry internalAddFirst(Object o) {
483 load();
484 IndexItem item = writeFirst(o);
485 indexList.addFirst(item);
486 itemAdded(item, 0, o);
487 return item;
488 }
489
490 protected synchronized IndexItem internalAdd(int index, Object element) {
491 load();
492 IndexItem item = insert(index, element);
493 indexList.add(index, item);
494 itemAdded(item, index, element);
495 return item;
496 }
497
498 protected synchronized StoreEntry internalGet(int index) {
499 load();
500 if (index >= 0 && index < indexList.size()) {
501 return indexList.get(index);
502 }
503 return null;
504 }
505
506 /*
507 * (non-Javadoc)
508 *
509 * @see org.apache.activemq.kaha.ListContainer#doRemove(int)
510 */
511 public synchronized boolean doRemove(int index) {
512 load();
513 boolean result = false;
514 IndexItem item = indexList.get(index);
515 if (item != null) {
516 result = true;
517 IndexItem prev = indexList.getPrevEntry(item);
518 prev = prev != null ? prev : root;
519 IndexItem next = indexList.getNextEntry(prev);
520 indexList.remove(index);
521 itemRemoved(index);
522 delete(item, prev, next);
523 }
524 return result;
525 }
526
527 /*
528 * (non-Javadoc)
529 *
530 * @see java.util.List#remove(int)
531 */
532 public synchronized Object remove(int index) {
533 load();
534 Object result = null;
535 IndexItem item = indexList.get(index);
536 if (item != null) {
537 itemRemoved(index);
538 result = getValue(item);
539 IndexItem prev = indexList.getPrevEntry(item);
540 prev = prev != null ? prev : root;
541 IndexItem next = indexList.getNextEntry(item);
542 indexList.remove(index);
543 delete(item, prev, next);
544 }
545 return result;
546 }
547
548 /*
549 * (non-Javadoc)
550 *
551 * @see java.util.List#indexOf(java.lang.Object)
552 */
553 public synchronized int indexOf(Object o) {
554 load();
555 int result = -1;
556 if (o != null) {
557 int count = 0;
558 IndexItem next = indexList.getFirst();
559 while (next != null) {
560 Object value = getValue(next);
561 if (value != null && value.equals(o)) {
562 result = count;
563 break;
564 }
565 count++;
566 next = indexList.getNextEntry(next);
567 }
568 }
569 return result;
570 }
571
572 /*
573 * (non-Javadoc)
574 *
575 * @see java.util.List#lastIndexOf(java.lang.Object)
576 */
577 public synchronized int lastIndexOf(Object o) {
578 load();
579 int result = -1;
580 if (o != null) {
581 int count = indexList.size() - 1;
582 IndexItem next = indexList.getLast();
583 while (next != null) {
584 Object value = getValue(next);
585 if (value != null && value.equals(o)) {
586 result = count;
587 break;
588 }
589 count--;
590 next = indexList.getPrevEntry(next);
591 }
592 }
593 return result;
594 }
595
596 /*
597 * (non-Javadoc)
598 *
599 * @see java.util.List#listIterator()
600 */
601 public synchronized ListIterator listIterator() {
602 load();
603 return new ContainerListIterator(this, indexList, indexList.getRoot());
604 }
605
606 /*
607 * (non-Javadoc)
608 *
609 * @see java.util.List#listIterator(int)
610 */
611 public synchronized ListIterator listIterator(int index) {
612 load();
613 IndexItem start = (index - 1) > 0 ? indexList.get(index - 1) : indexList.getRoot();
614 return new ContainerListIterator(this, indexList, start);
615 }
616
617 /*
618 * (non-Javadoc)
619 *
620 * @see java.util.List#subList(int, int)
621 */
622 public synchronized List<Object> subList(int fromIndex, int toIndex) {
623 load();
624 List<Object> result = new ArrayList<Object>();
625 int count = fromIndex;
626 IndexItem next = indexList.get(fromIndex);
627 while (next != null && count++ < toIndex) {
628 result.add(getValue(next));
629 next = indexList.getNextEntry(next);
630 }
631 return result;
632 }
633
634 /**
635 * add an Object to the list but get a StoreEntry of its position
636 *
637 * @param object
638 * @return the entry in the Store
639 */
640 public synchronized StoreEntry placeLast(Object object) {
641 StoreEntry item = internalAddLast(object);
642 return item;
643 }
644
645 /**
646 * insert an Object in first position int the list but get a StoreEntry of
647 * its position
648 *
649 * @param object
650 * @return the location in the Store
651 */
652 public synchronized StoreEntry placeFirst(Object object) {
653 StoreEntry item = internalAddFirst(object);
654 return item;
655 }
656
657 /**
658 * @param entry
659 * @param object
660 * @see org.apache.activemq.kaha.ListContainer#update(org.apache.activemq.kaha.StoreEntry,
661 * java.lang.Object)
662 */
663 public synchronized void update(StoreEntry entry, Object object) {
664 try {
665 dataManager.updateItem(entry.getValueDataItem(), marshaller, object);
666 } catch (IOException e) {
667 throw new RuntimeException(e);
668 }
669 }
670
671 /**
672 * Retrieve an Object from the Store by its location
673 *
674 * @param entry
675 * @return the Object at that entry
676 */
677 public synchronized Object get(final StoreEntry entry) {
678 load();
679 StoreEntry entryToUse = refresh(entry);
680 return getValue(entryToUse);
681 }
682
683 /**
684 * remove the Object at the StoreEntry
685 *
686 * @param entry
687 * @return true if successful
688 */
689 public synchronized boolean remove(StoreEntry entry) {
690 IndexItem item = (IndexItem)entry;
691 load();
692 boolean result = false;
693 if (item != null) {
694
695 remove(item);
696 result = true;
697 }
698 return result;
699 }
700
701 /**
702 * Get the StoreEntry for the first item of the list
703 *
704 * @return the first StoreEntry or null if the list is empty
705 */
706 public synchronized StoreEntry getFirst() {
707 load();
708 return indexList.getFirst();
709 }
710
711 /**
712 * Get the StoreEntry for the last item of the list
713 *
714 * @return the last StoreEntry or null if the list is empty
715 */
716 public synchronized StoreEntry getLast() {
717 load();
718 return indexList.getLast();
719 }
720
721 /**
722 * Get the next StoreEntry from the list
723 *
724 * @param entry
725 * @return the next StoreEntry or null
726 */
727 public synchronized StoreEntry getNext(StoreEntry entry) {
728 load();
729 IndexItem item = (IndexItem)entry;
730 return indexList.getNextEntry(item);
731 }
732
733 /**
734 * Get the previous StoreEntry from the list
735 *
736 * @param entry
737 * @return the previous store entry or null
738 */
739 public synchronized StoreEntry getPrevious(StoreEntry entry) {
740 load();
741 IndexItem item = (IndexItem)entry;
742 return indexList.getPrevEntry(item);
743 }
744
745 /**
746 * It's possible that a StoreEntry could be come stale this will return an
747 * upto date entry for the StoreEntry position
748 *
749 * @param entry old entry
750 * @return a refreshed StoreEntry
751 */
752 public synchronized StoreEntry refresh(StoreEntry entry) {
753 load();
754 return indexList.getEntry(entry);
755 }
756
757 protected synchronized IndexItem writeLast(Object value) {
758 IndexItem index = null;
759 try {
760 if (value != null) {
761 StoreLocation data = dataManager.storeDataItem(marshaller, value);
762 index = indexManager.createNewIndex();
763 index.setValueData(data);
764 IndexItem prev = indexList.getLast();
765 prev = prev != null ? prev : root;
766 IndexItem next = indexList.getNextEntry(prev);
767 prev.setNextItem(index.getOffset());
768 index.setPreviousItem(prev.getOffset());
769 updateIndexes(prev);
770 if (next != null) {
771 next.setPreviousItem(index.getOffset());
772 index.setNextItem(next.getOffset());
773 updateIndexes(next);
774 }
775 storeIndex(index);
776 }
777 } catch (IOException e) {
778 LOG.error("Failed to write " + value, e);
779 throw new RuntimeStoreException(e);
780 }
781 return index;
782 }
783
784 protected synchronized IndexItem writeFirst(Object value) {
785 IndexItem index = null;
786 try {
787 if (value != null) {
788 StoreLocation data = dataManager.storeDataItem(marshaller, value);
789 index = indexManager.createNewIndex();
790 index.setValueData(data);
791 IndexItem prev = root;
792 IndexItem next = indexList.getNextEntry(prev);
793 prev.setNextItem(index.getOffset());
794 index.setPreviousItem(prev.getOffset());
795 updateIndexes(prev);
796 if (next != null) {
797 next.setPreviousItem(index.getOffset());
798 index.setNextItem(next.getOffset());
799 updateIndexes(next);
800 }
801 storeIndex(index);
802 }
803 } catch (IOException e) {
804 LOG.error("Failed to write " + value, e);
805 throw new RuntimeStoreException(e);
806 }
807 return index;
808 }
809
810 protected synchronized IndexItem insert(int insertPos, Object value) {
811 IndexItem index = null;
812 try {
813 if (value != null) {
814 StoreLocation data = dataManager.storeDataItem(marshaller, value);
815 index = indexManager.createNewIndex();
816 index.setValueData(data);
817 IndexItem prev = null;
818 IndexItem next = null;
819 if (insertPos <= 0) {
820 prev = root;
821 next = indexList.getNextEntry(root);
822 } else if (insertPos >= indexList.size()) {
823 prev = indexList.getLast();
824 if (prev==null) {
825 prev=root;
826 }
827 next = null;
828 } else {
829 prev = indexList.get(insertPos);
830 prev = prev != null ? prev : root;
831 next = indexList.getNextEntry(prev);
832 }
833 prev.setNextItem(index.getOffset());
834 index.setPreviousItem(prev.getOffset());
835 updateIndexes(prev);
836 if (next != null) {
837 next.setPreviousItem(index.getOffset());
838 index.setNextItem(next.getOffset());
839 updateIndexes(next);
840 }
841 storeIndex(index);
842 indexList.setRoot(root);
843 }
844 } catch (IOException e) {
845 LOG.error("Failed to insert " + value, e);
846 throw new RuntimeStoreException(e);
847 }
848 return index;
849 }
850
851 protected synchronized Object getValue(StoreEntry item) {
852 Object result = null;
853 if (item != null) {
854 try {
855 StoreLocation data = item.getValueDataItem();
856 result = dataManager.readItem(marshaller, data);
857 } catch (IOException e) {
858 LOG.error("Failed to get value for " + item, e);
859 throw new RuntimeStoreException(e);
860 }
861 }
862 return result;
863 }
864
865 /**
866 * @return a string representation of this collection.
867 */
868 public synchronized String toString() {
869 StringBuffer result = new StringBuffer();
870 result.append("[");
871 Iterator i = iterator();
872 boolean hasNext = i.hasNext();
873 while (hasNext) {
874 Object o = i.next();
875 result.append(String.valueOf(o));
876 hasNext = i.hasNext();
877 if (hasNext) {
878 result.append(", ");
879 }
880 }
881 result.append("]");
882 return result.toString();
883 }
884
885 protected synchronized void itemAdded(IndexItem item, int pos, Object value) {
886
887 }
888
889 protected synchronized void itemRemoved(int pos) {
890
891 }
892 }