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