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.index;
018
019import java.io.IOException;
020import org.apache.activemq.kaha.StoreEntry;
021
022/**
023 * A linked list used by IndexItems
024 * 
025 * 
026 */
027public 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}