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 < 0 || index >= 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 < 0 || index > 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 < 0 || index >= 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 }