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.index;
018    
019    import java.io.IOException;
020    import org.apache.activemq.kaha.StoreEntry;
021    
022    /**
023     * A linked list used by IndexItems
024     * 
025     * 
026     */
027    public class DiskIndexLinkedList implements IndexLinkedList {
028        protected IndexManager indexManager;
029        protected transient IndexItem root;
030        protected transient IndexItem last;
031        protected transient int size;
032    
033        /**
034         * Constructs an empty list.
035         */
036        public DiskIndexLinkedList(IndexManager im, IndexItem header) {
037            this.indexManager = im;
038            this.root = header;
039        }
040    
041        public synchronized IndexItem getRoot() {
042            return root;
043        }
044    
045        public void setRoot(IndexItem e) {
046            this.root = e;
047        }
048    
049        /**
050         * Returns the first element in this list.
051         * 
052         * @return the first element in this list.
053         */
054        public synchronized IndexItem getFirst() {
055            if (size == 0) {
056                return null;
057            }
058            return getNextEntry(root);
059        }
060    
061        /**
062         * Returns the last element in this list.
063         * 
064         * @return the last element in this list.
065         */
066        public synchronized IndexItem getLast() {
067            if (size == 0) {
068                return null;
069            }
070            if (last != null) {
071                last.next = null;
072                last.setNextItem(IndexItem.POSITION_NOT_SET);
073            }
074            return last;
075        }
076    
077        /**
078         * Removes and returns the first element from this list.
079         * 
080         * @return the first element from this list.
081         */
082        public synchronized StoreEntry removeFirst() {
083            if (size == 0) {
084                return null;
085            }
086            IndexItem result = getNextEntry(root);
087            remove(result);
088            return result;
089        }
090    
091        /**
092         * Removes and returns the last element from this list.
093         * 
094         * @return the last element from this list.
095         */
096        public synchronized Object removeLast() {
097            if (size == 0) {
098                return null;
099            }
100            StoreEntry result = last;
101            remove(last);
102            return result;
103        }
104    
105        /**
106         * Inserts the given element at the beginning of this list.
107         * 
108         * @param o the element to be inserted at the beginning of this list.
109         */
110        public synchronized void addFirst(IndexItem item) {
111            if (size == 0) {
112                last = item;
113            }
114            size++;
115        }
116    
117        /**
118         * Appends the given element to the end of this list. (Identical in function
119         * to the <tt>add</tt> method; included only for consistency.)
120         * 
121         * @param o the element to be inserted at the end of this list.
122         */
123        public synchronized void addLast(IndexItem item) {
124            size++;
125            last = item;
126        }
127    
128        /**
129         * Returns the number of elements in this list.
130         * 
131         * @return the number of elements in this list.
132         */
133        public synchronized int size() {
134            return size;
135        }
136    
137        /**
138         * is the list empty?
139         * 
140         * @return true if there are no elements in the list
141         */
142        public synchronized boolean isEmpty() {
143            return size == 0;
144        }
145    
146        /**
147         * Appends the specified element to the end of this list.
148         * 
149         * @param o element to be appended to this list.
150         * @return <tt>true</tt> (as per the general contract of
151         *         <tt>Collection.add</tt>).
152         */
153        public synchronized boolean add(IndexItem item) {
154            addLast(item);
155            return true;
156        }
157    
158        /**
159         * Removes all of the elements from this list.
160         */
161        public synchronized void clear() {
162            last = null;
163            size = 0;
164        }
165    
166        // Positional Access Operations
167        /**
168         * Returns the element at the specified position in this list.
169         * 
170         * @param index index of element to return.
171         * @return the element at the specified position in this list.
172         * @throws IndexOutOfBoundsException if the specified index is is out of
173         *                 range (<tt>index &lt; 0 || index &gt;= size()</tt>).
174         */
175        public synchronized IndexItem get(int index) {
176            return entry(index);
177        }
178    
179        /**
180         * Inserts the specified element at the specified position in this list.
181         * Shifts the element currently at that position (if any) and any subsequent
182         * elements to the right (adds one to their indices).
183         * 
184         * @param index index at which the specified element is to be inserted.
185         * @param element element to be inserted.
186         * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
187         */
188        public synchronized void add(int index, IndexItem element) {
189            if (index == size) {
190                last = element;
191            }
192            size++;
193        }
194    
195        /**
196         * Removes the element at the specified position in this list. Shifts any
197         * subsequent elements to the left (subtracts one from their indices).
198         * Returns the element that was removed from the list.
199         * 
200         * @param index the index of the element to removed.
201         * @return the element previously at the specified position.
202         * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
203         */
204        public synchronized Object remove(int index) {
205            IndexItem e = entry(index);
206            remove(e);
207            return e;
208        }
209    
210        /**
211         * Return the indexed entry.
212         */
213        private IndexItem entry(int index) {
214            if (index < 0 || index >= size) {
215                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
216            }
217            IndexItem e = root;
218    
219            for (int i = 0; i <= index; i++) {
220                e = getNextEntry(e);
221            }
222            if (e != null && last != null && last.equals(e)) {
223                last = e;
224            }
225            return e;
226        }
227    
228        // Search Operations
229        /**
230         * Returns the index in this list of the first occurrence of the specified
231         * element, or -1 if the List does not contain this element. More formally,
232         * returns the lowest index i such that
233         * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if there
234         * is no such index.
235         * 
236         * @param o element to search for.
237         * @return the index in this list of the first occurrence of the specified
238         *         element, or -1 if the list does not contain this element.
239         */
240        public synchronized int indexOf(StoreEntry o) {
241            int index = 0;
242            if (size > 0) {
243                for (IndexItem e = getNextEntry(root); e != null; e = getNextEntry(e)) {
244                    if (o.equals(e)) {
245                        return index;
246                    }
247                    index++;
248                }
249            }
250            return -1;
251        }
252    
253        /**
254         * Retrieve the next entry after this entry
255         * 
256         * @param entry
257         * @return next entry
258         */
259        public synchronized IndexItem getNextEntry(IndexItem current) {
260                    IndexItem result = null;
261                    if (current != null) {
262                            current = (IndexItem) refreshEntry(current);
263                            if (current.getNextItem() >= 0) {
264                                    try {
265                                            result = indexManager.getIndex(current.getNextItem());
266                                    } catch (IOException e) {
267                                            throw new RuntimeException("Failed to get next index from "
268                                                            + indexManager + " for " + current, e);
269                                    }
270                            }
271                    }
272                    // essential last get's updated consistently
273                    if (result != null && last != null && last.equals(result)) {
274                            last=result;
275                    }
276                    return result;
277            }
278    
279        /**
280             * Retrive the prev entry after this entry
281             * 
282             * @param entry
283             * @return prev entry
284             */
285        public synchronized IndexItem getPrevEntry(IndexItem current) {
286                    IndexItem result = null;
287                    if (current != null) {
288                            if (current.getPreviousItem() >= 0) {
289                                    current = (IndexItem) refreshEntry(current);
290                                    try {
291                                            result = indexManager.getIndex(current.getPreviousItem());
292                                    } catch (IOException e) {
293                                            throw new RuntimeException(
294                                                            "Failed to  get current index for " + current, e);
295                                    }
296                            }
297                    }
298                    // essential root get's updated consistently
299                    if (result != null && root != null && root.equals(result)) {
300                            return null;
301                    }
302                    return result;
303            }
304    
305        public synchronized StoreEntry getEntry(StoreEntry current) {
306            StoreEntry result = null;
307            if (current != null && current.getOffset() >= 0) {
308                try {
309                    result = indexManager.getIndex(current.getOffset());
310                } catch (IOException e) {
311                    throw new RuntimeException("Failed to index", e);
312                }
313            }
314            // essential root get's updated consistently
315            if (result != null && root != null && root.equals(result)) {
316                return root;
317            }
318            return result;
319        }
320    
321        /**
322         * Update the indexes of a StoreEntry
323         * 
324         * @param current
325         */
326        public synchronized StoreEntry refreshEntry(StoreEntry current) {
327            StoreEntry result = null;
328            if (current != null && current.getOffset() >= 0) {
329                try {
330                    result = indexManager.refreshIndex((IndexItem)current);
331                } catch (IOException e) {
332                    throw new RuntimeException("Failed to index", e);
333                }
334            }
335            // essential root get's updated consistently
336            if (result != null && root != null && root.equals(result)) {
337                return root;
338            }
339            return result;
340        }
341    
342        public synchronized void remove(IndexItem e) {
343            if (e==null || e == root || e.equals(root)) {
344                return;
345            }
346            if (e == last || e.equals(last)) {
347                if (size > 1) {
348                    last = (IndexItem)refreshEntry(last);
349                    last = getPrevEntry(last);
350                } else {
351                    last = null;
352                }
353            }
354            size--;
355        }
356    }