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    }