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 * @version $Revision: 636078 $ 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 }