FixedRecordList


1   /**
2    * com.mckoi.database.FixedRecordList  11 Sep 2002
3    *
4    * Mckoi SQL Database ( http://www.mckoi.com/database )
5    * Copyright (C) 2000, 2001, 2002  Diehl and Associates, Inc.
6    *
7    * This program is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * Version 2 as published by the Free Software Foundation.
10   *
11   * This program is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License Version 2 for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * Version 2 along with this program; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19   *
20   * Change Log:
21   * 
22   * 
23   */
24  
25  package com.mckoi.database;
26  
27  import java.util.ArrayList  ;
28  import java.io.IOException  ;
29  import com.mckoi.store.Store;
30  import com.mckoi.store.AreaWriter;
31  import com.mckoi.store.MutableArea;
32  import com.mckoi.store.Area;
33  
34  /**
35   * A structure that provides a fast way to read and write fixed sized nodes in
36   * a Store object.  Each node in the list is of fixed size.
37   * <p>
38   * This structure can locate a node in the list very quickly.  However, the
39   * structure can not be mutated.  For example, deleting node '4' will make the
40   * node available for recycling but will not shift any nodes after 4 in the
41   * list up by one.
42   * <p>
43   * Once a node is allocated from the list its position will not change.
44   * <p>
45   * This structure does not provide versioning features.
46   * <p>
47   * The structure is composed of two element types - the header and the list
48   * block elements.  The header is resembled by the following diagram;
49   * <p>
50   *      LIST BLOCK HEADER
51   *   +-------------------------------+
52   *   | 4 MAGIC                       |
53   *   | 4 list block count            |
54   *   | 8 (reserved for delete chain) |
55   *   | 8 pointer to list block 0     |
56   *   | 8 pointer to list block 1     |
57   *   .  ... etc ...                  .
58   *   | 8 pointer to list block 63    |
59   *   +-------------------------------+
60   * </pre>
61   * <p>
62   * The first list block element is 32 entries in size, the second list block is
63   * 64 entries in size, etc.  Each entry of the list block element is of fixed
64   * size.
65   * <p>
66   * This class is NOT thread safe.
67   *
68   * @author Tobias Downer
69   */
70  
71  public class FixedRecordList {
72  
73    /**
74     * The magic value for fixed record list structures.
75     */
76    private final static int MAGIC = 0x087131AA;
77    
78    /**
79     * The backing Store object that persistantly stores the structure.
80     */
81    private final Store store;
82  
83    /**
84     * The fixed size of the elements in the list.
85     */
86    private final int element_size;
87    
88  
89    /**
90     * A pointer to the list header area.
91     */
92    private long list_header_p;
93    
94    /**
95     * The header for the list blocks.
96     */
97    private MutableArea list_header_area;
98    
99    /**
100    * The number of blocks in the list block.
101    */
102   private int list_block_count;
103 
104   /**
105    * Pointers to the blocks in the list block.
106    */
107   private long[] list_block_element;
108   private MutableArea[] list_block_area;
109 
110    
111   /**
112    * Constructs the structure.
113    */
114   public FixedRecordList(Store store, int element_size) {
115     this.store = store;
116     this.element_size = element_size;
117     list_block_element = new long[64];
118     list_block_area = new MutableArea[64];
119   }
120   
121   /**
122    * Creates the structure in the store, and returns a pointer to the structure.
123    */
124   public long create() throws IOException   {
125     // Allocate space for the list header (8 + 8 + (64 * 8))
126     AreaWriter writer = store.createArea(528);
127     list_header_p = writer.getID();
128     writer.putInt(MAGIC);
129     writer.finish();
130 
131     list_header_area = store.getMutableArea(list_header_p);
132     list_block_count = 0;
133     updateListHeaderArea();
134 
135     return list_header_p;
136   }
137 
138   /**
139    * Initializes the structure from the store.
140    */
141   public void init(long list_pointer) throws IOException   {
142     list_header_p = list_pointer;
143     list_header_area = store.getMutableArea(list_header_p);
144 
145     int magic = list_header_area.getInt();          // MAGIC
146     if (magic != MAGIC) {
147       throw new IOException  ("Incorrect magic for list block. [magic=" +
148                             magic + "]");
149     }
150     this.list_block_count = list_header_area.getInt();
151     list_header_area.getLong();
152     for (int i = 0; i < list_block_count; ++i) {
153       long block_pointer = list_header_area.getLong();
154       list_block_element[i] = block_pointer;
155       list_block_area[i] = store.getMutableArea(block_pointer);
156     }
157   }
158 
159   /**
160    * Adds to the given ArrayList all the areas in the store that are used by
161    * this structure (as Long).
162    */
163   public void addAllAreasUsed(ArrayList   list) throws IOException   {
164     list.add(new Long  (list_header_p));
165     for (int i = 0; i < list_block_count; ++i) {
166       list.add(new Long  (list_block_element[i]));
167     }
168   }
169 
170   /**
171    * Returns the 8 byte long that is reserved for storing the delete chain
172    * (if there is one).
173    */
174   public long getReservedLong() throws IOException   {
175     list_header_area.position(8);
176     return list_header_area.getLong();
177   }
178 
179   /**
180    * Sets the 8 byte long that is reserved for storing the delete chain
181    * (if there is one).
182    */
183   public void setReservedLong(long v) throws IOException   {
184     list_header_area.position(8);
185     list_header_area.putLong(v);
186     list_header_area.checkOut();
187   }
188 
189   /**
190    * Updates the list header area from the information store within the
191    * state of this object.  This should only be called when a new block is
192    * added to the list block, or the store is created.
193    */
194   private void updateListHeaderArea() throws IOException   {
195     list_header_area.position(4);
196     list_header_area.putInt(list_block_count);
197     list_header_area.position(16);
198     for (int i = 0; i < list_block_count; ++i) {
199       list_header_area.putLong(list_block_element[i]);
200     }
201     list_header_area.checkOut();
202   }
203 
204   /**
205    * Returns an Area object from the list block area with the position over
206    * the record entry requested.  Note that the Area object can only be safely
207    * used if there is a guarentee that no other access to this object while the
208    * area object is accessed.
209    */
210   public MutableArea positionOnNode(final long record_number)
211                                                           throws IOException   {
212     // What block is this record in?
213     int bit = 0;
214     long work = record_number + 32;
215     while (work != 0) {
216       work = work >> 1;
217       ++bit;
218     }
219     long start_val = (1 << (bit - 1)) - 32;
220     int block_offset = bit - 6;
221     long record_offset = record_number - start_val;
222     
223     // Get the pointer to the block that contains this record status
224     MutableArea block_area = list_block_area[block_offset];
225 //    long tempv = (record_offset * element_size);
226 //    int position_to = (int) tempv;
227 //    if (tempv == 1) {
228 //      ++tempv;
229 //    }
230 //    block_area.position(position_to);
231     block_area.position((int) (record_offset * element_size));
232 
233     return block_area;
234   }
235 
236   /**
237    * Returns the number of block elements in this list structure.  This will
238    * return a number between 0 and 63 (inclusive).
239    */
240   public int listBlockCount() {
241     return list_block_count;
242   }
243 
244   /**
245    * Returns the total number of nodes that are currently addressable by this
246    * list structure.  For example, if the list contains 0 blocks then there are
247    * no addressable nodes.  If it contains 1 block, there are 32 addressable
248    * nodes.  If it contains 2 blocks, there are 64 + 32 = 96 nodes.  3 blocks =
249    * 128 + 64 + 32 = 224 nodes.
250    */
251   public long addressableNodeCount() {
252     return listBlockFirstPosition(list_block_count);
253   }
254 
255   /**
256    * Returns the number of nodes that can be stored in the given block, where
257    * block 0 is the first block (32 addressable nodes).
258    */
259   public long listBlockNodeCount(int block_number) {
260     return 32L << block_number;
261   }
262 
263   /**
264    * Returns the index of the first node in the given block number.  For
265    * example, this first node of block 0 is 0, the first node of block 1 is
266    * 32, the first node of block 2 is 96, etc.
267    */
268   public long listBlockFirstPosition(int block_number) {
269     long start_index = 0;
270     int i = block_number;
271     long diff = 32;
272     while (i > 0) {
273       start_index = start_index + diff;
274       diff = diff << 1;
275       --i;
276     }
277     return start_index;
278   }
279 
280   /**
281    * Increases the size of the list structure so it may accomodate more record
282    * entries.  This simply adds a new block for more nodes.
283    */
284   public void increaseSize() throws IOException   {
285     // The size of the block
286     long size_of_block = 32L << list_block_count;
287     // Allocate the new block in the store
288     AreaWriter writer = store.createArea(size_of_block * element_size);
289     long nblock_p = writer.getID();
290     writer.finish();
291     MutableArea nblock_area = store.getMutableArea(nblock_p);
292     // Update the block list
293     list_block_element[list_block_count] = nblock_p;
294     list_block_area[list_block_count] = nblock_area;
295     ++list_block_count;
296     // Update the list header,
297     updateListHeaderArea();
298   }
299 
300   /**
301    * Decreases the size of the list structure.  This should be used with care
302    * because it deletes all nodes in the last block.
303    */
304   public void decreaseSize() throws IOException   {
305     --list_block_count;
306     // Free the top block
307     store.deleteArea(list_block_element[list_block_count]);
308     // Help the GC
309     list_block_area[list_block_count] = null;
310     list_block_element[list_block_count] = 0;
311     // Update the list header.
312     updateListHeaderArea();
313   }
314 
315 }
316 
317
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags