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 */
017package org.apache.activemq.kaha.impl.container;
018
019import java.io.IOException;
020import java.util.ArrayList;
021import java.util.Collection;
022import java.util.Iterator;
023import java.util.List;
024import java.util.ListIterator;
025
026import org.apache.activemq.kaha.ContainerId;
027import org.apache.activemq.kaha.ListContainer;
028import org.apache.activemq.kaha.Marshaller;
029import org.apache.activemq.kaha.RuntimeStoreException;
030import org.apache.activemq.kaha.Store;
031import org.apache.activemq.kaha.StoreEntry;
032import org.apache.activemq.kaha.StoreLocation;
033import org.apache.activemq.kaha.impl.DataManager;
034import org.apache.activemq.kaha.impl.data.Item;
035import org.apache.activemq.kaha.impl.index.IndexItem;
036import org.apache.activemq.kaha.impl.index.IndexManager;
037import org.slf4j.Logger;
038import org.slf4j.LoggerFactory;
039
040/**
041 * Implementation of a ListContainer
042 * 
043 * 
044 */
045public 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}