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 org.apache.activemq.kaha.StoreEntry; 020 021/** 022 * A linked list used by IndexItems 023 * 024 * 025 */ 026public final class VMIndexLinkedList implements Cloneable, IndexLinkedList { 027 private transient IndexItem root; 028 private transient int size; 029 030 /** 031 * Constructs an empty list. 032 * @param header 033 */ 034 public VMIndexLinkedList(IndexItem header) { 035 this.root = header; 036 this.root.next=this.root.prev=this.root; 037 } 038 039 public void setRoot(IndexItem newRoot) { 040 this.root=newRoot; 041 } 042 043 public synchronized IndexItem getRoot() { 044 return root; 045 } 046 047 /* 048 * (non-Javadoc) 049 * 050 * @see org.apache.activemq.kaha.impl.IndexLinkedList#getFirst() 051 */ 052 public synchronized IndexItem getFirst() { 053 if (size == 0) { 054 return null; 055 } 056 return root.next; 057 } 058 059 /* 060 * (non-Javadoc) 061 * 062 * @see org.apache.activemq.kaha.impl.IndexLinkedList#getLast() 063 */ 064 public synchronized IndexItem getLast() { 065 if (size == 0) { 066 return null; 067 } 068 return root.prev; 069 } 070 071 /* 072 * (non-Javadoc) 073 * 074 * @see org.apache.activemq.kaha.impl.IndexLinkedList#removeFirst() 075 */ 076 public synchronized StoreEntry removeFirst() { 077 if (size == 0) { 078 return null; 079 } 080 StoreEntry result = root.next; 081 remove(root.next); 082 return result; 083 } 084 085 /* 086 * (non-Javadoc) 087 * 088 * @see org.apache.activemq.kaha.impl.IndexLinkedList#removeLast() 089 */ 090 public synchronized Object removeLast() { 091 if (size == 0) { 092 return null; 093 } 094 StoreEntry result = root.prev; 095 remove(root.prev); 096 return result; 097 } 098 099 /* 100 * (non-Javadoc) 101 * 102 * @see org.apache.activemq.kaha.impl.IndexLinkedList#addFirst(org.apache.activemq.kaha.impl.IndexItem) 103 */ 104 public synchronized void addFirst(IndexItem item) { 105 addBefore(item, root.next); 106 } 107 108 /* 109 * (non-Javadoc) 110 * 111 * @see org.apache.activemq.kaha.impl.IndexLinkedList#addLast(org.apache.activemq.kaha.impl.IndexItem) 112 */ 113 public synchronized void addLast(IndexItem item) { 114 addBefore(item, root); 115 } 116 117 /* 118 * (non-Javadoc) 119 * 120 * @see org.apache.activemq.kaha.impl.IndexLinkedList#size() 121 */ 122 public synchronized int size() { 123 return size; 124 } 125 126 /* 127 * (non-Javadoc) 128 * 129 * @see org.apache.activemq.kaha.impl.IndexLinkedList#isEmpty() 130 */ 131 public synchronized boolean isEmpty() { 132 return size == 0; 133 } 134 135 /* 136 * (non-Javadoc) 137 * 138 * @see org.apache.activemq.kaha.impl.IndexLinkedList#add(org.apache.activemq.kaha.impl.IndexItem) 139 */ 140 public synchronized boolean add(IndexItem item) { 141 addBefore(item, root); 142 return true; 143 } 144 145 /* 146 * (non-Javadoc) 147 * 148 * @see org.apache.activemq.kaha.impl.IndexLinkedList#clear() 149 */ 150 public synchronized void clear() { 151 root.next=root.prev=root; 152 size = 0; 153 } 154 155 // Positional Access Operations 156 /* 157 * (non-Javadoc) 158 * 159 * @see org.apache.activemq.kaha.impl.IndexLinkedList#get(int) 160 */ 161 public synchronized IndexItem get(int index) { 162 return entry(index); 163 } 164 165 /* 166 * (non-Javadoc) 167 * 168 * @see org.apache.activemq.kaha.impl.IndexLinkedList#add(int, 169 * org.apache.activemq.kaha.impl.IndexItem) 170 */ 171 public synchronized void add(int index, IndexItem element) { 172 addBefore(element, index == size ? root : entry(index)); 173 } 174 175 /* 176 * (non-Javadoc) 177 * 178 * @see org.apache.activemq.kaha.impl.IndexLinkedList#remove(int) 179 */ 180 public synchronized Object remove(int index) { 181 IndexItem e = entry(index); 182 remove(e); 183 return e; 184 } 185 186 /** 187 * Return the indexed entry. 188 */ 189 private IndexItem entry(int index) { 190 if (index < 0 || index >= size) { 191 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); 192 } 193 IndexItem e = root; 194 if (index < size / 2) { 195 for (int i = 0; i <= index; i++) { 196 e = e.next; 197 } 198 } else { 199 for (int i = size; i > index; i--) { 200 e = e.prev; 201 } 202 } 203 return e; 204 } 205 206 // Search Operations 207 /* 208 * (non-Javadoc) 209 * 210 * @see org.apache.activemq.kaha.impl.IndexLinkedList#indexOf(org.apache.activemq.kaha.impl.IndexItem) 211 */ 212 public synchronized int indexOf(StoreEntry o) { 213 int index = 0; 214 for (IndexItem e = root.next; e != root; e = e.next) { 215 if (o == e) { 216 return index; 217 } 218 index++; 219 } 220 return -1; 221 } 222 223 /* 224 * (non-Javadoc) 225 * 226 * @see org.apache.activemq.kaha.impl.IndexLinkedList#getNextEntry(org.apache.activemq.kaha.impl.IndexItem) 227 */ 228 public synchronized IndexItem getNextEntry(IndexItem entry) { 229 return entry.next != root ? entry.next : null; 230 } 231 232 /* 233 * (non-Javadoc) 234 * 235 * @see org.apache.activemq.kaha.impl.IndexLinkedList#getPrevEntry(org.apache.activemq.kaha.impl.IndexItem) 236 */ 237 public synchronized IndexItem getPrevEntry(IndexItem entry) { 238 return entry.prev != root ? entry.prev : null; 239 } 240 241 /* 242 * (non-Javadoc) 243 * 244 * @see org.apache.activemq.kaha.impl.IndexLinkedList#addBefore(org.apache.activemq.kaha.impl.IndexItem, 245 * org.apache.activemq.kaha.impl.IndexItem) 246 */ 247 public synchronized void addBefore(IndexItem insert, IndexItem e) { 248 insert.next = e; 249 insert.prev = e.prev; 250 insert.prev.next = insert; 251 insert.next.prev = insert; 252 size++; 253 } 254 255 /* 256 * (non-Javadoc) 257 * 258 * @see org.apache.activemq.kaha.impl.IndexLinkedList#remove(org.apache.activemq.kaha.impl.IndexItem) 259 */ 260 public synchronized void remove(IndexItem e) { 261 if (e == root || e.equals(root)) { 262 return; 263 } 264 265 e.prev.next = e.next; 266 e.next.prev = e.prev; 267 size--; 268 } 269 270 /** 271 * @return clone 272 */ 273 public synchronized Object clone() { 274 IndexLinkedList clone = new VMIndexLinkedList(this.root); 275 for (IndexItem e = root.next; e != root; e = e.next) { 276 clone.add(e); 277 } 278 return clone; 279 } 280 281 public synchronized StoreEntry getEntry(StoreEntry current) { 282 return current; 283 } 284 285 /** 286 * Update the indexes of a StoreEntry 287 * 288 * @param current 289 */ 290 public synchronized StoreEntry refreshEntry(StoreEntry current) { 291 return current; 292 } 293}