DiskIndexLinkedList


1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one or more
4    * contributor license agreements.  See the NOTICE file distributed with
5    * this work for additional information regarding copyright ownership.
6    * The ASF licenses this file to You under the Apache License, Version 2.0
7    * (the "License"); you may not use this file except in compliance with
8    * the License.  You may obtain a copy of the License at
9    *
10   * http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.activemq.kaha.impl.index;
19  
20  import java.io.IOException  ;
21  import org.apache.activemq.kaha.StoreEntry;
22  /**
23   * A linked list used by IndexItems
24   * 
25   * @version $Revision: 513455 $
26   */
27  public  class DiskIndexLinkedList implements IndexLinkedList{
28      protected IndexManager indexManager;
29      protected transient IndexItem root;
30      protected transient IndexItem last;
31      protected transient int size=0;
32  
33      /**
34       * Constructs an empty list.
35       */
36      public  DiskIndexLinkedList(IndexManager im,IndexItem header){
37          this.indexManager=im;
38          this.root=header;
39      }
40  
41      public synchronized IndexItem getRoot(){
42          return root;
43      }
44  
45      void setRoot(IndexItem e){
46          this.root=e;
47      }
48  
49      /**
50       * Returns the first element in this list.
51       * 
52       * @return the first element in this list.
53       */
54      public synchronized IndexItem getFirst(){
55          if(size==0)
56              return null;
57          return getNextEntry(root);
58      }
59  
60      /**
61       * Returns the last element in this list.
62       * 
63       * @return the last element in this list.
64       */
65      public synchronized IndexItem getLast(){
66          if(size==0)
67              return null;
68          if(last!=null){
69              last.next=null;
70              last.setNextItem(IndexItem.POSITION_NOT_SET);
71          }
72          return last;
73      }
74  
75      /**
76       * Removes and returns the first element from this list.
77       * 
78       * @return the first element from this list.
79       */
80      public synchronized StoreEntry removeFirst(){
81          if(size==0){
82              return null;
83          }
84          IndexItem result=getNextEntry(root);
85          remove(result);
86          return result;
87      }
88  
89      /**
90       * Removes and returns the last element from this list.
91       * 
92       * @return the last element from this list.
93       */
94      public synchronized Object   removeLast(){
95          if(size==0)
96              return null;
97          StoreEntry result=last;
98          remove(last);
99          return result;
100     }
101 
102     /**
103      * Inserts the given element at the beginning of this list.
104      * 
105      * @param o the element to be inserted at the beginning of this list.
106      */
107     public synchronized void addFirst(IndexItem item){
108         if(size==0){
109             last=item;
110         }
111         size++;
112     }
113 
114     /**
115      * Appends the given element to the end of this list. (Identical in function to the <tt>add</tt> method; included
116      * only for consistency.)
117      * 
118      * @param o the element to be inserted at the end of this list.
119      */
120     public synchronized void addLast(IndexItem item){
121         size++;
122         last=item;
123     }
124 
125     /**
126      * Returns the number of elements in this list.
127      * 
128      * @return the number of elements in this list.
129      */
130     public synchronized int size(){
131         return size;
132     }
133 
134     /**
135      * is the list empty?
136      * 
137      * @return true if there are no elements in the list
138      */
139     public synchronized boolean isEmpty(){
140         return size==0;
141     }
142 
143     /**
144      * Appends the specified element to the end of this list.
145      * 
146      * @param o element to be appended to this list.
147      * @return <tt>true</tt> (as per the general contract of <tt>Collection.add</tt>).
148      */
149     public synchronized boolean add(IndexItem item){
150         addLast(item);
151         return true;
152     }
153 
154     /**
155      * Removes all of the elements from this list.
156      */
157     public synchronized void clear(){
158         last=null;
159         size=0;
160     }
161 
162     // Positional Access Operations
163     /**
164      * Returns the element at the specified position in this list.
165      * 
166      * @param index index of element to return.
167      * @return the element at the specified position in this list.
168      * 
169      * @throws IndexOutOfBoundsException if the specified index is is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
170      */
171     public synchronized IndexItem get(int index){
172         return entry(index);
173     }
174 
175     /**
176      * Inserts the specified element at the specified position in this list. Shifts the element currently at that
177      * position (if any) and any subsequent elements to the right (adds one to their indices).
178      * 
179      * @param index index at which the specified element is to be inserted.
180      * @param element element to be inserted.
181      * 
182      * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
183      */
184     public synchronized void add(int index,IndexItem element){
185         if(index==size-1){
186             last=element;
187         }
188         size++;
189     }
190 
191     /**
192      * Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts
193      * one from their indices). Returns the element that was removed from the list.
194      * 
195      * @param index the index of the element to removed.
196      * @return the element previously at the specified position.
197      * 
198      * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
199      */
200     public synchronized Object   remove(int index){
201         IndexItem e=entry(index);
202         remove(e);
203         return e;
204     }
205 
206     /**
207      * Return the indexed entry.
208      */
209     private IndexItem entry(int index){
210         if(index<0||index>=size)
211             throw new IndexOutOfBoundsException  ("Index: "+index+", Size: "+size);
212         IndexItem e=root;
213         
214         for(int i=0;i<=index;i++)
215             e=getNextEntry(e);
216         if(e != null &&last!=null && last.equals(e)){
217             last = e;
218          }
219         return e;
220     }
221 
222     // Search Operations
223     /**
224      * Returns the index in this list of the first occurrence of the specified element, or -1 if the List does not
225      * contain this element. More formally, returns the lowest index i such that
226      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if there is no such index.
227      * 
228      * @param o element to search for.
229      * @return the index in this list of the first occurrence of the specified element, or -1 if the list does not
230      *         contain this element.
231      */
232     public synchronized int indexOf(StoreEntry o){
233         int index=0;
234         if(size>0){
235             for(IndexItem e=getNextEntry(root);e!=null;e=getNextEntry(e)){
236                 if(o.equals(e)){
237                     return index;
238                 }
239                 index++;
240             }
241         }
242         return -1;
243     }
244 
245     /**
246      * Retrieve the next entry after this entry
247      * 
248      * @param entry
249      * @return next entry
250      */
251     public synchronized IndexItem getNextEntry(IndexItem current){
252         IndexItem result=null;
253         if(current!=null&&current.getNextItem()>=0){
254             try{
255                 result=indexManager.getIndex(current.getNextItem());
256             }catch(IOException   e){
257                 throw new RuntimeException  ("Failed to get next index from " + indexManager + " for " + current,e);
258             }
259         }
260         //      essential last get's updated consistently
261         if(result != null &&last!=null && last.equals(result)){
262            result = last;
263         }
264         return result;
265     }
266 
267     /**
268      * Retrive the prev entry after this entry
269      * 
270      * @param entry
271      * @return prev entry
272      */
273     public synchronized IndexItem getPrevEntry(IndexItem current){
274         IndexItem result=null;
275         if(current!=null&&current.getPreviousItem()>=0){
276             try{
277                 result=indexManager.getIndex(current.getPreviousItem());
278             }catch(IOException   e){
279                 throw new RuntimeException  ("Failed to  get current index for "+current,e);
280             }
281         }
282         // essential root get's updated consistently
283         if(result!=null&&root!=null&&root.equals(result)){
284             return root;
285         }
286         return result;
287     }
288     
289    public synchronized  StoreEntry getEntry(StoreEntry current){
290         StoreEntry result=null;
291         if(current != null && current.getOffset() >= 0){
292             try{
293                 result=indexManager.getIndex(current.getOffset());
294             }catch(IOException   e){
295                 throw new RuntimeException  ("Failed to index",e);
296             }
297         }
298         //essential root get's updated consistently
299         if(result != null &&root!=null && root.equals(result)){
300            return root;
301         }
302         return result;
303     }
304    
305    /**
306     * Update the indexes of a StoreEntry
307     * @param current
308     */
309    public synchronized StoreEntry refreshEntry(StoreEntry current){
310        StoreEntry result=null;
311        if(current != null && current.getOffset() >= 0){
312            try{
313                result=indexManager.refreshIndex((IndexItem)current);
314            }catch(IOException   e){
315                throw new RuntimeException  ("Failed to index",e);
316            }
317        }
318        //essential root get's updated consistently
319        if(result != null &&root!=null && root.equals(result)){
320           return root;
321        }
322        return result;
323    }
324 
325     public synchronized void remove(IndexItem e){
326         if(e==root||e.equals(root))
327             return;
328         if(e==last||e.equals(last)){
329             if(size>1){
330                 last = (IndexItem)refreshEntry(last);
331                 last=getPrevEntry(last);
332             }else{
333                 last=null;
334             }
335         }
336         size--;
337     }
338 }
339
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags