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}