HeapStore


1   /**
2    * com.mckoi.store.HeapStore  20 Feb 2003
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.store;
26  
27  import com.mckoi.util.ByteArrayUtil;
28  import java.util.List  ;
29  import java.io.ByteArrayInputStream  ;
30  import java.io.InputStream  ;
31  import java.io.OutputStream  ;
32  import java.io.IOException  ;
33  
34  /**
35   * An implementation of the Store interface that persists information in the
36   * volatile JVM heap memory.  Each Area in the store is represented by a byte[]
37   * array from the Java heap.
38   * <p>
39   * Note that in Java there is no way to cast a reference to a numeric value,
40   * or to cast a numeric value back into a reference.  This means that
41   * Area lookup has to be coordinated via a hashing algorithm over an array.
42   * There would prehaps be a more efficient way to achieve this with JNI but
43   * it would mean we can't be pure Java and it would require locking the address
44   * of objects in the heap.
45   * <p>
46   * Another alternative way of implementing this class would be to use JNI to
47   * access a C style 'malloc' function in the operating system and wrap the
48   * memory with a native Area implementation.
49   *
50   * @author Tobias Downer
51   */
52  
53  public final class HeapStore implements Store {
54  
55    /**
56     * The fixed area element (a 64 byte area).
57     */
58    private HeapAreaElement fixed_area_element;
59  
60    /**
61     * A hash map of area pointer to byte[] array that represents the area.
62     */
63    private HeapAreaElement[] area_map;
64  
65    /**
66     * A unique id key incremented for each new area created.
67     */
68    private long unique_id_key;
69  
70    /**
71     * Creates the HeapStore.
72     */
73    public HeapStore(int hash_size) {
74      area_map = new HeapAreaElement[hash_size];
75      unique_id_key = 0;
76    }
77  
78    /**
79     * Defaults heap size to 257 elements.
80     */
81    public HeapStore() {
82      this(257);
83    }
84  
85    /**
86     * Searches the hash map and returns the area element for the given pointer.
87     */
88    private HeapAreaElement getAreaElement(long pointer) throws IOException   {
89      synchronized (this) {
90        // Find the pointer in the hash
91        int hash_pos = (int) (pointer % area_map.length);
92        HeapAreaElement prev = null;
93        HeapAreaElement element = area_map[hash_pos];
94        // Search for this pointer
95        while (element != null && element.getID() != pointer) {
96          prev = element;
97          element = element.next_hash_element;
98        }
99        // If not found
100       if (element == null) {
101         throw new IOException  ("Pointer " + pointer + " is invalid.");
102       }
103       // Move the element to the start of the list.
104       if (prev != null) {
105         prev.next_hash_element = element.next_hash_element;
106         element.next_hash_element = area_map[hash_pos];
107         area_map[hash_pos] = element;
108       }
109       // Return the element
110       return element;
111     }
112   }
113 
114   /**
115    * Returns a MutableArea object for the fixed position.
116    */
117   private HeapAreaElement getFixedAreaElement() {
118     synchronized (this) {
119       if (fixed_area_element == null) {
120         fixed_area_element = new HeapAreaElement(-1, 64);
121       }
122       return fixed_area_element;
123     }
124   }
125 
126   /**
127    * Returns the HeapAreaElement for the given pointer.
128    */
129   private HeapAreaElement getElement(long pointer) throws IOException   {
130     if (pointer == -1) {
131       return getFixedAreaElement();
132     }
133     else {
134       return getAreaElement(pointer);
135     }
136   }
137 
138   
139   // ---------- Implemented from Store ----------
140 
141   public AreaWriter createArea(long size) throws IOException   {
142     if (size > Integer.MAX_VALUE) {
143       throw new IOException  ("'size' is too large.");
144     }
145     synchronized (this) {
146       // Generate a unique id for this area.
147       long id = unique_id_key;
148       ++unique_id_key;
149 
150       // Create the element.
151       HeapAreaElement element = new HeapAreaElement(id, (int) size);
152       // The position in the hash map
153       int hash_pos = (int) (id % area_map.length);
154       // Add to the chain
155       element.next_hash_element = area_map[hash_pos];
156       // Set the element in the chain
157       area_map[hash_pos] = element;
158       // And return the object
159       return element.getAreaWriter();
160     }
161   }
162 
163   public void deleteArea(long pointer) throws IOException   {
164     synchronized (this) {
165       // Find the pointer in the hash
166       int hash_pos = (int) (pointer % area_map.length);
167       HeapAreaElement prev = null;
168       HeapAreaElement element = area_map[hash_pos];
169       // Search for this pointer
170       while (element != null && element.getID() != pointer) {
171         prev = element;
172         element = element.next_hash_element;
173       }
174       // If not found
175       if (element == null) {
176         throw new IOException  ("Pointer " + pointer + " is invalid.");
177       }
178       // Remove
179       if (prev == null) {
180         area_map[hash_pos] = element.next_hash_element;
181       }
182       else {
183         prev.next_hash_element = element.next_hash_element;
184       }
185       // Garbage collector should do the rest...
186     }
187   }
188 
189   public InputStream   getAreaInputStream(long pointer) throws IOException   {
190     return getElement(pointer).getInputStream();
191   }
192   
193   public Area getArea(long pointer) throws IOException   {
194     return getElement(pointer).getMutableArea();
195   }
196   
197   public MutableArea getMutableArea(long pointer) throws IOException   {
198     return getElement(pointer).getMutableArea();
199   }
200   
201   public void flush() throws IOException   {
202     // Not required
203   }
204 
205   public void synch() throws IOException   {
206     // Not required
207   }
208 
209   public void lockForWrite() {
210     // Not required
211   }
212   
213   public void unlockForWrite() {
214     // Not required
215   }
216 
217   // ---------- Diagnostic ----------
218 
219   public boolean lastCloseClean() {
220     // Close is not possible with a heap store, so always return true
221     return true;
222   }
223 
224   public List   getAllAreas() throws IOException   {
225     throw new RuntimeException  ("PENDING");
226   }
227 
228 
229 
230   // ---------- Inner classes ----------
231 
232   /**
233    * An implementation of Area for a byte[] array from the heap.
234    */
235   private static class HeapArea implements MutableArea {
236 
237     /**
238      * The ID of this area.
239      */
240     private final long id;
241     
242     /**
243      * A pointer to the byte[] array representing the entire area.
244      */
245     private final byte[] heap_area;
246 
247     /**
248      * The start pointer in the heap area.
249      */
250     private final int start_pointer;
251 
252     /**
253      * The current pointer into the area.
254      */
255     private int position;
256 
257     /**
258      * The end pointer of the area.
259      */
260     private final int end_pointer;
261 
262     /**
263      * Constructor.
264      */
265     HeapArea(long id, byte[] heap_area, int offset, int length) {
266       this.id = id;
267       this.heap_area = heap_area;
268       this.start_pointer = offset;
269       this.position = offset;
270       this.end_pointer = offset + length;
271     }
272 
273     private int checkPositionBounds(int diff) throws IOException   {
274       final int new_pos = position + diff;
275       if (new_pos > end_pointer) {
276         throw new IOException  ("Position out of bounds. " +
277                               " start=" + start_pointer +
278                               " end=" + end_pointer +
279                               " pos=" + position +
280                               " new_pos=" + new_pos);
281       }
282       final int old_pos = position;
283       position = new_pos;
284       return old_pos;
285     }
286 
287     public long getID() {
288       return id;
289     }
290     
291     public int position() {
292       return position - start_pointer;
293     }
294 
295     public int capacity() {
296       return end_pointer - start_pointer;
297     }
298 
299     public void position(int position) throws IOException   {
300       int act_position = start_pointer + position;
301       if (act_position >= 0 && act_position < end_pointer) {
302         this.position = act_position;
303         return;
304       }
305       throw new IOException  ("Moved position out of bounds.");
306     }
307 
308     public void copyTo(AreaWriter destination, int size) throws IOException   {
309       final int BUFFER_SIZE = 2048;
310       byte[] buf = new byte[BUFFER_SIZE];
311       int to_copy = Math.min(size, BUFFER_SIZE);
312 
313       while (to_copy > 0) {
314         get(buf, 0, to_copy);
315         destination.put(buf, 0, to_copy);
316         size -= to_copy;
317         to_copy = Math.min(size, BUFFER_SIZE);
318       }
319     }
320 
321     public byte get() throws IOException   {
322       return heap_area[checkPositionBounds(1)];
323     }
324 
325     public void put(byte b) throws IOException   {
326       heap_area[checkPositionBounds(1)] = b;
327     }
328 
329     public void get(byte[] buf, int off, int len) throws IOException   {
330       System.arraycopy(heap_area, checkPositionBounds(len), buf, off, len);
331     }
332 
333     public void put(byte[] buf, int off, int len) throws IOException   {
334       System.arraycopy(buf, off, heap_area, checkPositionBounds(len), len);
335     }
336 
337     public void put(byte[] buf) throws IOException   {
338       put(buf, 0, buf.length);
339     }
340 
341     public short getShort() throws IOException   {
342       short s = ByteArrayUtil.getShort(heap_area, checkPositionBounds(2));
343       return s;
344     }
345 
346     public void putShort(short s) throws IOException   {
347       ByteArrayUtil.setShort(s, heap_area, checkPositionBounds(2));
348     }
349 
350     public int getInt() throws IOException   {
351       int i = ByteArrayUtil.getInt(heap_area, checkPositionBounds(4));
352       return i;
353     }
354 
355     public void putInt(int i) throws IOException   {
356       ByteArrayUtil.setInt(i, heap_area, checkPositionBounds(4));
357     }
358 
359     public long getLong() throws IOException   {
360       long l = ByteArrayUtil.getLong(heap_area, checkPositionBounds(8));
361       return l;
362     }
363 
364     public void putLong(long l) throws IOException   {
365       ByteArrayUtil.setLong(l, heap_area, checkPositionBounds(8));
366     }
367 
368     public char getChar() throws IOException   {
369       char c = ByteArrayUtil.getChar(heap_area, checkPositionBounds(2));
370       return c;
371     }
372 
373     public void putChar(char c) throws IOException   {
374       ByteArrayUtil.setChar(c, heap_area, checkPositionBounds(2));
375     }
376 
377     public void checkOut() {
378       // no-op
379     }
380     
381     public String   toString() {
382       return "[Area start_pointer=" + start_pointer +
383              " end_pointer=" + end_pointer +
384              " position=" + position + "]";
385     }
386 
387   }
388 
389   private static class HeapAreaWriter extends HeapArea
390                                       implements AreaWriter {
391 
392     public HeapAreaWriter(long id, byte[] heap_area, int offset, int length) {
393       super(id, heap_area, offset, length);
394     }
395 
396     public OutputStream   getOutputStream() {
397       return new AbstractStore.AreaOutputStream(this);
398     }
399 
400     public void finish() throws IOException   {
401       // Currently, no-op
402     }
403 
404   }
405   
406   /**
407    * An area allocated from the heap store represented by a volatile byte[]
408    * array.
409    */
410   private static class HeapAreaElement {
411     
412     /**
413      * The id of this heap area (used as the hash key).
414      */
415     private final long heap_id;
416     
417     /**
418      * A byte[] array that represents the volatile heap area.
419      */
420     private final byte[] heap_area;
421     
422     /**
423      * The pointer to the next HeapAreaElement in this hash key.
424      */
425     HeapAreaElement next_hash_element;
426     
427     /**
428      * Constructs the HeapAreaElement.
429      */
430     HeapAreaElement(long heap_id, int area_size) {
431       this.heap_id = heap_id;
432       this.heap_area = new byte[area_size];
433     }
434 
435     /**
436      * Returns the heap id for this element.
437      */
438     long getID() {
439       return heap_id;
440     }
441 
442     /**
443      * Returns a new AreaWriter object for this element.
444      */
445     AreaWriter getAreaWriter() {
446       return new HeapAreaWriter(getID(), heap_area, 0, heap_area.length);
447     }
448 
449     /**
450      * Returns a new MutableArea object for this element.
451      */
452     MutableArea getMutableArea() {
453       return new HeapArea(getID(), heap_area, 0, heap_area.length);
454     }
455 
456     /**
457      * Returns a new InputStream that is used to read from the area.
458      */
459     InputStream   getInputStream() {
460       return new ByteArrayInputStream  (heap_area);
461     }
462 
463   }
464 
465 }
466 
467
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags