AbstractStore


1   /**
2    * com.mckoi.store.AbstractStore  30 Aug 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.store;
26  
27  import java.util.Arrays  ;
28  import java.util.Collections  ;
29  import java.util.List  ;
30  import java.util.ArrayList  ;
31  import java.util.HashMap  ;
32  import java.io.*;
33  import com.mckoi.util.ByteArrayUtil;
34  import com.mckoi.util.UserTerminal;
35  
36  /**
37   * Provides an abstract implementation of Store.  This implements a bin based
38   * best-fit recycling algorithm.  The store manages a structure that points to
39   * bins of freed space of specific sizes.  When an allocation is requested the
40   * structure is searched for the first bin that contains an area that best fits
41   * the size requested.
42   * <p>
43   * Provided the derived class supports safe atomic IO operations, this store
44   * is designed for robustness to the level that at no point is the store left
45   * in a unworkable (corrupt) state.
46   *
47   * @author Tobias Downer
48   */
49  
50  public abstract class AbstractStore implements Store {
51  
52    /**
53     * The free bin list contains 128 entries pointing to the first available
54     * block in the bin.  If the list item contains -1 then there are no free
55     * blocks in the bin.
56     */
57    protected long[] free_bin_list;
58  
59    
60    /**
61     * A pointer to the wilderness area (the last deleted area in the store),
62     * or -1 if there is no wilderness area.
63     */
64    protected long wilderness_pointer;
65  
66    /**
67     * True if this is read-only.
68     */
69    protected boolean read_only;
70  
71    /**
72     * The total amount of allocated space within this store since the store
73     * was openned.  Note that this could be a negative amount if more space
74     * was freed than allocated.
75     */
76    protected long total_allocated_space;
77  
78    /**
79     * True if the store was opened dirtily (was not previously closed cleanly).
80     */
81    private boolean dirty_open;
82    
83    // ---------- Statics ----------
84  
85    /**
86     * The offset into the file that the data areas start.
87     */
88    protected static final long DATA_AREA_OFFSET = 256 + 1024 + 32;
89  
90    /**
91     * The offset into the file of the 64 byte fixed area.
92     */
93    protected static final long FIXED_AREA_OFFSET = 128;
94    
95    /**
96     * The offset into the file that the bin area starts.
97     */
98    protected static final long BIN_AREA_OFFSET = 256;
99  
100   /**
101    * The magic value.
102    */
103   protected static final int MAGIC = 0x0AEAE91;
104 
105   
106   /**
107    * Constructs the store.
108    */
109   protected AbstractStore(boolean read_only) {
110     free_bin_list = new long[BIN_ENTRIES + 1];
111     for (int i = 0; i < BIN_ENTRIES + 1; ++i) {
112       free_bin_list[i] = (long) -1;
113     }
114     wilderness_pointer = -1;
115     this.read_only = read_only;
116   }
117 
118   /**
119    * Initializes the store to an empty state.
120    */
121   private synchronized void initializeToEmpty() throws IOException {
122     setDataAreaSize(DATA_AREA_OFFSET);
123     // New file so write out the initial file area,
124     ByteArrayOutputStream bout =
125                            new ByteArrayOutputStream((int) BIN_AREA_OFFSET);
126     DataOutputStream out = new DataOutputStream(bout);
127     // The file MAGIC
128     out.writeInt(MAGIC);   // 0
129     // The file version
130     out.writeInt(1);       // 4
131     // The number of areas (chunks) in the file (currently unused)
132     out.writeLong(-1);     // 8
133     // File open/close status byte
134     out.writeByte(0);      // 16
135 
136     out.flush();
137     byte[] buf = new byte[(int) DATA_AREA_OFFSET];
138     byte[] buf2 = bout.toByteArray();
139     System.arraycopy(buf2, 0, buf, 0, buf2.length);;
140     for (int i = (int) BIN_AREA_OFFSET; i < (int) DATA_AREA_OFFSET; ++i) {
141       buf[i] = (byte) 255;
142     }
143     
144     writeByteArrayToPT(0, buf, 0, buf.length);
145   }
146   
147   
148   /**
149    * Opens the data store.  Returns true if the store did not close cleanly.
150    */
151   public synchronized boolean open() throws IOException {
152     internalOpen(read_only);
153 
154     // If it's small, initialize to empty
155     if (endOfDataAreaPointer() < DATA_AREA_OFFSET) {
156       initializeToEmpty();
157     }
158     
159     byte[] read_buf = new byte[(int) BIN_AREA_OFFSET];
160     readByteArrayFrom(0, read_buf, 0, read_buf.length);
161     ByteArrayInputStream b_in = new ByteArrayInputStream(read_buf);
162     DataInputStream din = new DataInputStream(b_in);
163     
164     int magic = din.readInt();
165     if (magic != MAGIC) {
166       throw new IOException("Format invalid: Magic value is not as expected.");
167     }
168     int version = din.readInt();
169     if (version != 1) {
170       throw new IOException("Format invalid: unrecognised version.");
171     }
172     din.readLong();  // ignore
173     byte status = din.readByte();
174     dirty_open = false;
175     if (status == 1) {
176       // This means the store wasn't closed cleanly.
177       dirty_open = true;
178     }
179 
180     // Read the bins
181     readBins();
182 
183     // Mark the file as open
184     if (!read_only) {
185       writeByteToPT(16, 1);
186     }
187 
188     long file_length = endOfDataAreaPointer();
189     if (file_length <= 8) {
190       throw new IOException("Format invalid: File size is too small.");
191     }
192     
193     // Set the wilderness pointer.
194     if (file_length == DATA_AREA_OFFSET) {
195       wilderness_pointer = -1;
196     }
197     else {
198       readByteArrayFrom(file_length - 8, read_buf, 0, 8);
199       long last_boundary = ByteArrayUtil.getLong(read_buf, 0);
200       long last_area_pointer = file_length - last_boundary;
201 
202       if (last_area_pointer < DATA_AREA_OFFSET) {
203         System.out.println("last_boundary = " + last_boundary);
204         System.out.println("last_area_pointer = " + last_area_pointer);
205         throw new IOException(
206                "File corrupt: last_area_pointer is before data part of file.");
207       }
208       if (last_area_pointer > file_length - 8) {
209         throw new IOException(
210                "File corrupt: last_area_pointer at the end of the file.");
211       }
212 
213       readByteArrayFrom(last_area_pointer, read_buf, 0, 8);
214       long last_area_header = ByteArrayUtil.getLong(read_buf, 0);
215       // If this is a freed block, then set this are the wilderness pointer.
216       if ((last_area_header & 0x08000000000000000L) != 0) {
217         wilderness_pointer = last_area_pointer;
218       }
219       else {
220         wilderness_pointer = -1;
221       }
222     }
223 
224     return dirty_open;
225   }
226   
227   /**
228    * Closes the store.
229    */
230   public synchronized void close() throws IOException {
231 
232     // Mark the file as closed
233     if (!read_only) {
234       writeByteToPT(16, 0);
235     }
236 
237     internalClose();
238   }
239 
240   /**
241    * Returns true if the given area size is valid.  Currently the criteria
242    * for a valid boundary size is (size >= 24) and (size % 8 == 0) and
243    * (size < 200 gigabytes)
244    */
245   protected static boolean isValidBoundarySize(long size) {
246     long MAX_AREA_SIZE = (long) Integer.MAX_VALUE * 200;
247     size = size & 0x07FFFFFFFFFFFFFFFL;
248     return ((size < MAX_AREA_SIZE) && (size >= 24) && ((size & 0x07) == 0));
249   }
250 
251   /**
252    * Reads an 8 byte long at the given position in the data area.
253    */
254   private byte[] buf = new byte[8];
255   private long readLongAt(long position) throws IOException {
256     readByteArrayFrom(position, buf, 0, 8);
257     return ByteArrayUtil.getLong(buf, 0);
258   }
259   
260   /**
261    * Performs a repair scan from the given pointer.  This is a recursive
262    * algorithm that looks for at most 'n' number of repairs before giving
263    * up.  Returns false if a repair path could not be found.
264    */
265   private boolean repairScan(final ArrayList   areas_to_fix,
266                              final long pointer, final long end_pointer,
267                              final boolean scan_forward,
268                              final int max_repairs) throws IOException {
269     // Recurse end conditions;
270     // If the end is reached, success!
271     if (pointer == end_pointer) {
272       return true;
273     }
274     // If max repairs exhausted, failure!
275     if (pointer > end_pointer || max_repairs <= 0) {
276       return false;
277     }
278 
279     long pointer_to_head = scan_forward ? pointer : end_pointer - 8;
280                            
281     // Does the pointer at least look right?
282     long first_header = readLongAt(pointer_to_head) & 0x07FFFFFFFFFFFFFFFL;
283     // If it's a valid boundary size, and the header points inside the
284     // end boundary
285     long max_bound_size = end_pointer - pointer;
286     if (isValidBoundarySize(first_header) && first_header <= max_bound_size) {
287 
288       long pointer_to_tail = scan_forward ? (pointer + first_header) - 8 :
289                                             end_pointer - first_header;
290 
291       // If the end doesn't look okay,
292       long end_area_pointer = pointer_to_tail;
293       long end_header = readLongAt(end_area_pointer) & 0x07FFFFFFFFFFFFFFFL;
294       boolean valid_end_header = (first_header == end_header);
295      
296       long scan_area_p1 = scan_forward ? (pointer + first_header) : pointer;
297       long scan_area_p2 = scan_forward ? end_pointer : (end_pointer - first_header);
298       
299       if (!valid_end_header) {
300         // First and ends are invalid, so lets first assume we make the end
301         // valid and recurse,
302         long area_p = scan_forward ? pointer_to_head : pointer_to_tail;
303         areas_to_fix.add(new Long  (area_p));
304         areas_to_fix.add(new Long  (first_header));
305 
306         boolean b = repairScan(areas_to_fix, scan_area_p1, scan_area_p2,
307                                true, max_repairs - 1);
308         // If success
309         if (b) {
310           return true;
311         }
312 
313         // If failure, take that repair off the top
314         areas_to_fix.remove(areas_to_fix.size() - 1);
315         areas_to_fix.remove(areas_to_fix.size() - 1);
316         // And keep searching
317       }
318       else {
319         // Looks okay, so keep going,
320         
321         // This really does the same thing as recursing through the scan area
322         // however, we have to reduce the stack usage for large files which
323         // makes this iterative solution necessary.  Basically, this looks for
324         // the first broken area and reverts back to applying the recursive
325         // algorithm on it.
326         boolean something_broken = false;
327         long previous1_scan_area_p1 = scan_area_p1;
328         long previous2_scan_area_p1 = scan_area_p1;
329         long previous3_scan_area_p1 = scan_area_p1;
330 
331         while (scan_area_p1 < scan_area_p2 && !something_broken) {
332           // Assume something broken,
333           something_broken = true;
334           
335           // Does the pointer at least look right?
336           long scanning_header =
337                               readLongAt(scan_area_p1) & 0x07FFFFFFFFFFFFFFFL;
338           long scan_max_bound_size = scan_area_p2 - scan_area_p1;
339           if (isValidBoundarySize(scanning_header) &&
340               scanning_header <= scan_max_bound_size) {
341             long scan_end_header =
342                             readLongAt((scan_area_p1 + scanning_header) - 8)
343                             & 0x07FFFFFFFFFFFFFFFL;
344             if (scan_end_header == scanning_header) {
345               // Cycle the scanned areas
346               previous3_scan_area_p1 = previous2_scan_area_p1;
347               previous2_scan_area_p1 = previous1_scan_area_p1;
348               previous1_scan_area_p1 = scan_area_p1;
349 
350               scan_area_p1 = (scan_area_p1 + scanning_header);
351               // Enough evidence that area is not broken, so continue scan
352               something_broken = false;
353             }
354           }
355         }
356         if (something_broken) {
357           // Back track to the last 3 scanned areas and perform a repair on
358           // this area.  This allows for the scan to have more choices on
359           // repair paths.
360           scan_area_p1 = previous3_scan_area_p1;
361         }
362 
363         // The recursive scan on the (potentially) broken area.
364         boolean b = repairScan(areas_to_fix, scan_area_p1, scan_area_p2,
365                                true, max_repairs);
366         if (b) {
367           // Repair succeeded!
368           return b;
369         }
370         
371         // Repair didn't succeed so keep searching.
372       }
373     }
374 
375     // Try reversing the scan and see if that comes up with something valid.
376     if (scan_forward) {
377       boolean b = repairScan(areas_to_fix, pointer, end_pointer,
378                              false, max_repairs);
379       // Success
380       if (b) {
381         return b;
382       }
383       
384     }
385     else {
386       return false;
387     }
388 
389     // We guarenteed to be scan forward if we get here....
390 
391     // Facts: we know that the start and end pointers are invalid....
392     
393     // Search forward for something that looks like a boundary.  If we don't
394     // find it, search backwards for something that looks like a boundary.
395     
396     final long max_size = end_pointer - pointer;
397     for (long i = 16; i < max_size; i += 8) {
398       
399       long v = readLongAt(pointer + i) & 0x07FFFFFFFFFFFFFFFL;
400       if (v == i + 8) {
401         // This looks like a boundary, so try this...
402         areas_to_fix.add(new Long  (pointer));
403         areas_to_fix.add(new Long  (i + 8));
404         boolean b = repairScan(areas_to_fix, pointer + i + 8, end_pointer,
405                                true, max_repairs - 1);
406         if (b) {
407           return true;
408         }
409         areas_to_fix.remove(areas_to_fix.size() - 1);
410         areas_to_fix.remove(areas_to_fix.size() - 1);
411       }
412       
413     }
414 
415     // Scan backwards....
416     for (long i = max_size - 8 - 16; i >= 0; i -= 8) {
417       
418       long v = readLongAt(pointer + i) & 0x07FFFFFFFFFFFFFFFL;
419       if (v == (max_size - i)) {
420         // This looks like a boundary, so try this...
421         areas_to_fix.add(new Long  (pointer + i));
422         areas_to_fix.add(new Long  ((max_size - i)));
423         boolean b = repairScan(areas_to_fix, pointer, pointer + i,
424                                true, max_repairs - 1);
425         if (b) {
426           return true;
427         }
428         areas_to_fix.remove(areas_to_fix.size() - 1);
429         areas_to_fix.remove(areas_to_fix.size() - 1);
430       }
431       
432     }
433     
434     // No luck, so simply set this as a final big area and return true.
435     // NOTE: There are other tests possible here but I think what we have will
436     //   find fixes for 99% of corruption cases.
437     areas_to_fix.add(new Long  (pointer));
438     areas_to_fix.add(new Long  (end_pointer - pointer));
439 
440     return true;
441     
442   }
443   
444   /**
445    * Opens/scans the store looking for any errors with the layout.  If a
446    * problem with the store is detected, it attempts to fix it.
447    */
448   public synchronized void openScanAndFix(UserTerminal terminal)
449                                                          throws IOException {
450 
451     internalOpen(read_only);
452                                                            
453     terminal.println("- Store: " + toString());
454 
455     // If it's small, initialize to empty
456     if (endOfDataAreaPointer() < DATA_AREA_OFFSET) {
457       terminal.println("+ Store too small - initializing to empty.");
458       initializeToEmpty();
459       return;
460     }
461     
462     byte[] read_buf = new byte[(int) BIN_AREA_OFFSET];
463     readByteArrayFrom(0, read_buf, 0, read_buf.length);
464     ByteArrayInputStream b_in = new ByteArrayInputStream(read_buf);
465     DataInputStream din = new DataInputStream(b_in);
466     
467     int magic = din.readInt();
468     if (magic != MAGIC) {
469       terminal.println("! Store magic value not present - not fixable.");
470       return;
471     }
472     int version = din.readInt();
473     if (version != 1) {
474       terminal.println("! Store version is invalid - not fixable.");
475       return;
476     }
477     
478     // Check the size
479     long end_of_data_area = endOfDataAreaPointer();
480     if (end_of_data_area < DATA_AREA_OFFSET + 16) {
481       // Store size is too small.  There's nothing to be lost be simply
482       // reinitializing it to a blank state.
483       terminal.println(
484                 "! Store is too small, reinitializing store to blank state.");
485       initializeToEmpty();
486       return;
487     }
488 
489     // Do a recursive scan over the store.
490     ArrayList   repairs = new ArrayList  ();
491     boolean b = repairScan(repairs, DATA_AREA_OFFSET, endOfDataAreaPointer(),
492                            true, 20);
493 
494     if (b) {
495       if (repairs.size() == 0) {
496         terminal.println("- Store areas are intact.");
497       }
498       else {
499         terminal.println("+ " + (repairs.size() / 2) + " area repairs:");
500         for (int i = 0; i < repairs.size(); i += 2) {
501           terminal.println("  Area pointer: " + repairs.get(i));
502           terminal.println("  Area size: " + repairs.get(i + 1));
503           long pointer = ((Long  ) repairs.get(i)).longValue();
504           long size = ((Long  ) repairs.get(i + 1)).longValue();
505           coalescArea(pointer, size);
506         }
507       }
508     }
509     else {
510       terminal.println("- Store is not repairable!");
511     }
512 
513     // Rebuild the free bins,
514     free_bin_list = new long[BIN_ENTRIES + 1];
515     for (int i = 0; i < BIN_ENTRIES + 1; ++i) {
516       free_bin_list[i] = (long) -1;
517     }
518     
519     terminal.println("+ Rebuilding free bins.");
520     long[] header = new long[2];
521     // Scan for all free areas in the store.
522     long pointer = DATA_AREA_OFFSET;
523     while (pointer < end_of_data_area) {
524       getAreaHeader(pointer, header);
525       long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
526       boolean is_free = ((header[0] & 0x08000000000000000L) != 0);
527 
528       if (is_free) {
529         addToBinChain(pointer, area_size);
530       }
531 
532       pointer += area_size;
533     }
534 
535     // Update all the bins
536     writeAllBins();
537 
538     terminal.println("- Store repair complete.");
539     
540     // Open the store for real,
541     open();
542 
543   }
544 
545   /**
546    * Performs an extensive lookup on all the tables in this store and sets a
547    * number of properties in the given HashMap
548    * (property name(String) -> property description(Object)).  This should be
549    * used for store diagnostics.
550    * <p>
551    * Assume the store is open.
552    */
553   public synchronized void statsScan(HashMap   properties) throws IOException {
554 
555     long free_areas = 0;
556     long free_total = 0;
557     long allocated_areas = 0;
558     long allocated_total = 0;
559 
560     final long end_of_data_area = endOfDataAreaPointer();
561     
562     long[] header = new long[2];
563     // The first header
564     long pointer = DATA_AREA_OFFSET;
565     while (pointer < end_of_data_area) {
566       getAreaHeader(pointer, header);
567       long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
568 
569       if ((header[0] & 0x08000000000000000L) != 0) {
570         ++free_areas;
571         free_total += area_size;
572       }
573       else {
574         ++allocated_areas;
575         allocated_total += area_size;
576       }
577 
578       pointer += area_size;
579     }
580 
581     if (wilderness_pointer != -1) {
582       getAreaHeader(wilderness_pointer, header);
583       long wilderness_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
584       properties.put("AbstractStore.wilderness_size",
585                      new Long  (wilderness_size));
586     }
587     
588     properties.put("AbstractStore.end_of_data_area",
589                    new Long  (end_of_data_area));
590     properties.put("AbstractStore.free_areas",
591                    new Long  (free_areas));
592     properties.put("AbstractStore.free_total",
593                    new Long  (free_total));
594     properties.put("AbstractStore.allocated_areas",
595                    new Long  (allocated_areas));
596     properties.put("AbstractStore.allocated_total",
597                    new Long  (allocated_total));
598     
599     
600   }
601 
602   /**
603    * Returns a List of Long objects that contain a complete list of all areas
604    * in the store.  This is useful for checking if a given pointer is valid
605    * or not.  The returned list is sorted from start area to end area.
606    */
607   public List   getAllAreas() throws IOException {
608     ArrayList   list = new ArrayList  ();
609     final long end_of_data_area = endOfDataAreaPointer();
610     long[] header = new long[2];
611     // The first header
612     long pointer = DATA_AREA_OFFSET;
613     while (pointer < end_of_data_area) {
614       getAreaHeader(pointer, header);
615       long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
616       if ((header[0] & 0x08000000000000000L) == 0) {
617         list.add(new Long  (pointer));
618       }
619       pointer += area_size;
620     }
621     return list;
622   }
623   
624   /**
625    * Scans the area list, and any areas that aren't deleted and aren't found
626    * in the given ArrayList are returned as leaked areas.  This is a useful
627    * method for finding any leaks in the store.
628    */
629   public ArrayList   findAllocatedAreasNotIn(ArrayList   list) throws IOException {
630 
631     // Sort the list
632     Collections.sort(list);
633 
634     // The list of leaked areas
635     ArrayList   leaked_areas = new ArrayList  ();
636     
637     int list_index = 0;
638 
639     // What area are we looking for?
640     long looking_for = Long.MAX_VALUE;
641     if (list_index < list.size()) {
642       looking_for = ((Long  ) list.get(list_index)).longValue();
643       ++list_index;
644     }
645     
646     final long end_of_data_area = endOfDataAreaPointer();
647     long[] header = new long[2];
648 
649     long pointer = DATA_AREA_OFFSET;
650     while (pointer < end_of_data_area) {
651       getAreaHeader(pointer, header);
652       long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
653       boolean area_free = (header[0] & 0x08000000000000000L) != 0;
654 
655       if (pointer == looking_for) {
656         if (area_free) {
657           throw new IOException("Area (pointer = " + pointer +
658                                 ") is not allocated!");
659         }
660         // Update the 'looking_for' pointer
661         if (list_index < list.size()) {
662           looking_for = ((Long  ) list.get(list_index)).longValue();
663           ++list_index;
664         }
665         else {
666           looking_for = Long.MAX_VALUE;
667         }
668       }
669       else if (pointer > looking_for) {
670         throw new IOException("Area (pointer = " + looking_for +
671                               ") wasn't found in store!");
672       }
673       else {
674         // An area that isn't in the list
675         if (!area_free) {
676           // This is a leaked area.
677           // It isn't free and it isn't in the list
678           leaked_areas.add(new Long  (pointer));
679         }
680       }
681       
682       pointer += area_size;
683     }
684 
685     return leaked_areas;
686 
687   }
688 
689   /**
690    * Returns the total allocated space since the file was openned.
691    */
692   public synchronized long totalAllocatedSinceStart() {
693     return total_allocated_space;
694   }
695   
696   /**
697    * Returns the bin index that would be the minimum size to store the given
698    * object.
699    */
700   private int minimumBinSizeIndex(long size) {
701     int i = Arrays.binarySearch(BIN_SIZES, (int) size);
702     if (i < 0) {
703       i = -(i + 1);
704     }
705     return i;
706   }
707 
708   /**
709    * Internally opens the backing area.  If 'read_only' is true then the
710    * store is openned in read only mode.
711    */
712   protected abstract void internalOpen(boolean read_only) throws IOException;
713   
714   /**
715    * Internally closes the backing area.
716    */
717   protected abstract void internalClose() throws IOException;
718 
719   /**
720    * Reads a byte from the given position in the file.
721    */
722   protected abstract int readByteFrom(long position) throws IOException;
723 
724   /**
725    * Reads a byte array from the given position in the file.  Returns the
726    * number of bytes read.
727    */
728   protected abstract int readByteArrayFrom(long position,
729                              byte[] buf, int off, int len) throws IOException;
730 
731   /**
732    * Writes a byte to the given position in the file.
733    */
734   protected abstract void writeByteTo(long position, int b) throws IOException;
735 
736   /**
737    * Writes a byte array to the given position in the file.
738    */
739   protected abstract void writeByteArrayTo(long position,
740                               byte[] buf, int off, int len) throws IOException;
741 
742   /**
743    * Returns a pointer to the end of the current data area.
744    */
745   protected abstract long endOfDataAreaPointer() throws IOException;
746 
747   /**
748    * Sets the size of the data area.
749    */
750   protected abstract void setDataAreaSize(long length) throws IOException;
751   
752   
753 
754 
755   /**
756    * WriteByteTo pass-through method.
757    */
758   private final void writeByteToPT(long position, int b) throws IOException {
759     writeByteTo(position, b);
760   }
761 
762   /**
763    * WriteByteArrayTo pass-through method.
764    */
765   private final void writeByteArrayToPT(long position,
766                             byte[] buf, int off, int len) throws IOException {
767     writeByteArrayTo(position, buf, off, len);
768   }
769 
770                               
771   // ----------
772   
773   /**
774    * Checks the pointer is valid.
775    */
776   protected void checkPointer(long pointer) throws IOException {
777     if (pointer < DATA_AREA_OFFSET || pointer >= endOfDataAreaPointer()) {
778       throw new IOException("Pointer out of range: " + DATA_AREA_OFFSET +
779                             " > " + pointer + " > " + endOfDataAreaPointer());
780     }
781   }
782 
783   /**
784    * A buffered work area we work with when reading/writing bin pointers from
785    * the file header.
786    */
787   private final byte[] bin_area = new byte[128 * 8];
788 
789   /**
790    * Reads the bins from the header information in the file.
791    */
792   protected void readBins() throws IOException {
793     readByteArrayFrom(BIN_AREA_OFFSET,
794                       bin_area, 0, 128 * 8);
795     ByteArrayInputStream bin = new ByteArrayInputStream(bin_area);
796     DataInputStream in = new DataInputStream(bin);
797     for (int i = 0; i < 128; ++i) {
798       free_bin_list[i] = in.readLong();
799     }
800   }
801   
802   /**
803    * Updates all bins to the data area header area.
804    */
805   protected void writeAllBins() throws IOException {
806     int p = 0;
807     for (int i = 0; i < 128; ++i, p += 8) {
808       long val = free_bin_list[i];
809       ByteArrayUtil.setLong(val, bin_area, p);
810     }
811     writeByteArrayToPT(BIN_AREA_OFFSET, bin_area, 0, 128 * 8);
812   }
813 
814   /**
815    * Updates the given bin index to the data area header area.
816    */
817   protected void writeBinIndex(int index) throws IOException {
818     int p = index * 8;
819     long val = free_bin_list[index];
820     ByteArrayUtil.setLong(val, bin_area, p);
821     writeByteArrayToPT(BIN_AREA_OFFSET + p, bin_area, p, 8);
822   }
823 
824   protected final byte[] header_buf = new byte[16];
825   
826   /**
827    * Sets the 'header' array with information from the header of the given
828    * pointer.
829    */
830   protected void getAreaHeader(long pointer, long[] header) throws IOException {
831     readByteArrayFrom(pointer, header_buf, 0, 16);
832     header[0] = ByteArrayUtil.getLong(header_buf, 0);
833     header[1] = ByteArrayUtil.getLong(header_buf, 8);
834   }
835 
836   /**
837    * Sets the 'header' array with information from the previous header to the
838    * given pointer, and returns a pointer to the previous area.
839    */
840   protected long getPreviousAreaHeader(long pointer, long[] header)
841                                                           throws IOException {
842     // If the pointer is the start of the file area
843     if (pointer == DATA_AREA_OFFSET) {
844       // Return a 0 sized block
845       header[0] = 0;
846       return -1;
847     }
848     else {
849       readByteArrayFrom(pointer - 8, header_buf, 0, 8);
850       long sz = ByteArrayUtil.getLong(header_buf, 0);
851       sz = sz & 0x07FFFFFFFFFFFFFFFL;
852       long previous_pointer = pointer - sz;
853       readByteArrayFrom(previous_pointer, header_buf, 0, 8);
854       header[0] = ByteArrayUtil.getLong(header_buf, 0);
855       return previous_pointer;
856     }
857   }
858 
859   /**
860    * Sets the 'header' array with information from the next header to the
861    * given pointer, and returns a pointer to the next area.
862    */
863   protected long getNextAreaHeader(long pointer, long[] header)
864                                                           throws IOException {
865     readByteArrayFrom(pointer, header_buf, 0, 8);
866     long sz = ByteArrayUtil.getLong(header_buf, 0);
867     sz = sz & 0x07FFFFFFFFFFFFFFFL;
868     long next_pointer = pointer + sz;
869 
870     if (next_pointer >= endOfDataAreaPointer()) {
871       // Return a 0 sized block
872       header[0] = 0;
873       return -1;
874     }
875 
876     readByteArrayFrom(next_pointer, header_buf, 0, 8);
877     header[0] = ByteArrayUtil.getLong(header_buf, 0);
878     return next_pointer;
879   }
880 
881   /**
882    * Rebounds the given area with the given header information.  If
883    * 'write_headers' is true, the header (header[0]) is changed.  Note that this
884    * shouldn't be used to change the size of a chunk.
885    */
886   protected void reboundArea(long pointer, long[] header,
887                              boolean write_headers) throws IOException {
888     if (write_headers) {
889       ByteArrayUtil.setLong(header[0], header_buf, 0);
890       ByteArrayUtil.setLong(header[1], header_buf, 8);
891       writeByteArrayToPT(pointer, header_buf, 0, 16);
892     }
893     else {
894       ByteArrayUtil.setLong(header[1], header_buf, 8);
895       writeByteArrayToPT(pointer + 8, header_buf, 8, 8);
896     }
897   }
898 
899   /**
900    * Coalesc one or more areas into a larger area.  This alters the boundary
901    * of the area to encompass the given size.
902    */
903   protected void coalescArea(long pointer, long size) throws IOException {
904     
905     ByteArrayUtil.setLong(size, header_buf, 0);
906 
907     // ISSUE: Boundary alteration is a moment when corruption could occur.
908     //   There are two seeks and writes here and when we are setting the
909     //   end points, there is a risk of failure.
910 
911     writeByteArrayToPT(pointer, header_buf, 0, 8);
912     writeByteArrayToPT((pointer + size) - 8, header_buf, 0, 8);
913   }
914 
915   /**
916    * Expands the data area by at least the minimum size given.  Returns the
917    * actual size the data area was expanded by.
918    */
919   protected long expandDataArea(long minimum_size) throws IOException {
920     long end_of_data_area = endOfDataAreaPointer();
921 
922     // Round all sizes up to the nearest 8
923     // We grow only by a small amount if the area is small, and a large amount
924     // if the area is large.
925     long over_grow = end_of_data_area / 64;
926     long d = (over_grow & 0x07L);
927     if (d != 0) {
928       over_grow = over_grow + (8 - d);
929     }
930     over_grow  = Math.min(over_grow, 262144L);
931     if (over_grow < 1024) {
932       over_grow = 1024;
933     }
934     
935     long grow_by = minimum_size + over_grow;
936     long new_file_length = end_of_data_area + grow_by;
937     setDataAreaSize(new_file_length);
938     return grow_by;
939   }
940 
941   /**
942    * Splits an area pointed to by 'pointer' at a new boundary point.
943    */
944   protected void splitArea(long pointer, long new_boundary) throws IOException {
945     // Split the area pointed to by the pointer.
946     readByteArrayFrom(pointer, header_buf, 0, 8);
947     long cur_size = ByteArrayUtil.getLong(header_buf, 0) & 0x07FFFFFFFFFFFFFFFL;
948     long left_size = new_boundary;
949     long right_size = cur_size - new_boundary;
950 
951     if (right_size < 0) {
952       throw new Error  ("right_size < 0");
953     }
954     
955     ByteArrayUtil.setLong(left_size, header_buf, 0);
956     ByteArrayUtil.setLong(right_size, header_buf, 8);
957 
958     // ISSUE: Boundary alteration is a moment when corruption could occur.
959     //   There are three seeks and writes here and when we are setting the
960     //   end points, there is a risk of failure.
961     
962     // First set the boundary
963     writeByteArrayToPT((pointer + new_boundary) - 8, header_buf, 0, 16);
964     // Now set the end points
965     writeByteArrayToPT(pointer, header_buf, 0, 8);
966     writeByteArrayToPT((pointer + cur_size) - 8, header_buf, 8, 8);
967   }
968 
969 
970 
971 
972   private long[] header_info  = new long[2];
973   private long[] header_info2 = new long[2];
974 
975 
976   /**
977    * Adds the given area to the bin represented by the bin_chain_index.
978    */
979   private void addToBinChain(long pointer, long size) throws IOException {
980 
981     checkPointer(pointer);
982     
983     // What bin would this area fit into?
984     int bin_chain_index = minimumBinSizeIndex(size);
985 
986 //    System.out.println("+ Adding to bin chain: " + pointer + " size: " + size);
987 //    System.out.println("+ Adding to index: " + bin_chain_index);
988     
989     long cur_pointer = free_bin_list[bin_chain_index];
990     if (cur_pointer == -1) {
991       // If the bin chain has no elements,
992       header_info[0] = (size | 0x08000000000000000L);
993       header_info[1] = -1;
994       reboundArea(pointer, header_info, true);
995       free_bin_list[bin_chain_index] = pointer;
996       writeBinIndex(bin_chain_index);
997     }
998     else {
999       boolean inserted = false;
1000      long last_pointer = -1;
1001      int searches = 0;
1002      while (cur_pointer != -1 && inserted == false) {
1003        // Get the current pointer
1004        getAreaHeader(cur_pointer, header_info);
1005
1006        long header = header_info[0];
1007        long next = header_info[1];
1008        // Assert - the header must have deleted flag
1009        if ((header & 0x08000000000000000L) == 0) {
1010          throw new Error  ("Assert failed - area not marked as deleted.  " +
1011                          "pos = " + cur_pointer +
1012                          " this = " + toString());
1013        }
1014        long area_size = header ^ 0x08000000000000000L;
1015        if (area_size >= size || searches >= 12) {
1016          // Insert if the area size is >= than the size we are adding.
1017          // Set the previous header to point to this
1018          long previous = last_pointer;
1019
1020          // Set up the deleted area
1021          header_info[0] = (size | 0x08000000000000000L);
1022          header_info[1] = cur_pointer;
1023          reboundArea(pointer, header_info, true);
1024
1025          if (last_pointer != -1) {
1026            // Set the previous in the chain to point to the deleted area
1027            getAreaHeader(previous, header_info);
1028            header_info[1] = pointer;
1029            reboundArea(previous, header_info, false);
1030          }
1031          else {
1032            // Otherwise set the head bin item
1033            free_bin_list[bin_chain_index] = pointer;
1034            writeBinIndex(bin_chain_index);
1035          }
1036          
1037          inserted = true;
1038        }
1039        last_pointer = cur_pointer;
1040        cur_pointer = next;
1041        ++searches;
1042      }
1043      
1044      // If we reach the end and we haven't inserted,
1045      if (!inserted) {
1046        // Set the new deleted area.
1047        header_info[0] = (size | 0x08000000000000000L);
1048        header_info[1] = -1;
1049        reboundArea(pointer, header_info, true);
1050        
1051        // Set the previous entry to this
1052        getAreaHeader(last_pointer, header_info);
1053        header_info[1] = pointer;
1054        reboundArea(last_pointer, header_info, false);
1055
1056      }
1057      
1058    }
1059    
1060  }
1061
1062  /**
1063   * Removes the given area from the bin chain.  This requires a search of the
1064   * bin chain for the given size.
1065   */
1066  private void removeFromBinChain(long pointer, long size) throws IOException {
1067    // What bin index should we be looking in?
1068    int bin_chain_index = minimumBinSizeIndex(size);
1069    
1070//    System.out.println("- Removing from bin chain " + pointer + " size " + size);
1071//    System.out.println("- Removing from index " + bin_chain_index);
1072    
1073    long previous_pointer = -1;
1074    long cur_pointer = free_bin_list[bin_chain_index];
1075    // Search this bin for the pointer
1076    // NOTE: This is an iterative search through the bin chain
1077    while (pointer != cur_pointer) {
1078      if (cur_pointer == -1) {
1079        throw new IOException("Area not found in bin chain!  " +
1080                              "pos = " + pointer + " store = " + toString());
1081      }
1082      // Move to the next in the chain
1083      getAreaHeader(cur_pointer, header_info);
1084      previous_pointer = cur_pointer;
1085      cur_pointer = header_info[1];
1086    }
1087
1088    // Found the pointer, so remove it,
1089    if (previous_pointer == -1) {
1090      getAreaHeader(pointer, header_info);
1091      free_bin_list[bin_chain_index] = header_info[1];
1092      writeBinIndex(bin_chain_index);
1093    }
1094    else {
1095      getAreaHeader(previous_pointer, header_info2);
1096      getAreaHeader(pointer, header_info);
1097      header_info2[1] = header_info[1];
1098      reboundArea(previous_pointer, header_info2, false);
1099    }
1100    
1101  }
1102  
1103  /**
1104   * Crops the area to the given size.  This is used after an area is pulled
1105   * from a bin.  This method decides if it's worth reusing any space left over
1106   * and the end of the area.
1107   */
1108  private void cropArea(long pointer, long allocated_size) throws IOException {
1109    // Get the header info
1110    getAreaHeader(pointer, header_info);
1111    long header = header_info[0];
1112    // Can we recycle the difference in area size?
1113    final long free_area_size = header;
1114    // The difference between the size of the free area and the size
1115    // of the allocated area?
1116    final long size_difference = free_area_size - allocated_size;
1117    // If the difference is greater than 512 bytes, add the excess space to
1118    // a free bin.
1119    boolean is_wilderness = (pointer == wilderness_pointer);
1120    if ((is_wilderness && size_difference >= 32) || size_difference >= 512) {
1121      // Split the area into two areas.
1122      splitArea(pointer, allocated_size);
1123
1124      long left_over_pointer = pointer + allocated_size;
1125      // Add this area to the bin chain
1126      addToBinChain(left_over_pointer, size_difference);
1127
1128      // If pointer is the wilderness area, set this as the new wilderness
1129      if (is_wilderness ||
1130          (left_over_pointer + size_difference) >= endOfDataAreaPointer()) {
1131        wilderness_pointer = left_over_pointer;
1132      }
1133
1134    }
1135    else {
1136      // If pointer is the wilderness area, set wilderness to -1
1137      if (is_wilderness) {
1138        wilderness_pointer = -1;
1139      }
1140    }
1141  }
1142
1143  /**
1144   * Allocates a block of memory from the backing area of the given size and
1145   * returns a pointer to that area.
1146   */
1147  private long alloc(long size) throws IOException {
1148
1149    // Negative allocations are not allowed
1150    if (size < 0) {
1151      throw new IOException("Negative size allocation");
1152    }
1153
1154    // Add 16 bytes for headers
1155    size = size + 16;
1156    // If size < 32, make size = 32
1157    if (size < 32) {
1158      size = 32;
1159    }
1160
1161    // Round all sizes up to the nearest 8
1162    long d = size & 0x07L;
1163    if (d != 0) {
1164      size = size + (8 - d);
1165    }
1166
1167    final long real_alloc_size = size;
1168    
1169    // Search the free bin list for the first bin that matches the given size.
1170    int bin_chain_index;
1171    if (size > MAX_BIN_SIZE) {
1172      bin_chain_index = BIN_ENTRIES;
1173    }
1174    else {
1175      int i = minimumBinSizeIndex(size);
1176      bin_chain_index = i;
1177    }
1178
1179    // Search the bins until we find the first area that is the nearest fit to
1180    // the size requested.
1181    int found_bin_index = -1;
1182    long previous_pointer = -1;
1183    boolean first = true;
1184    for (int i = bin_chain_index;
1185         i < BIN_ENTRIES + 1 && found_bin_index == -1; ++i) {
1186      long cur_pointer = free_bin_list[i];
1187      if (cur_pointer != -1) {
1188        if (!first) {
1189          // Pick this..
1190          found_bin_index = i;
1191          previous_pointer = -1;
1192        }
1193        // Search this bin for the first that's big enough.
1194        // We only search the first 12 entries in the bin before giving up.
1195        else {
1196          long last_pointer = -1;
1197          int searches = 0;
1198          while (cur_pointer != -1 &&
1199                 found_bin_index == -1 &&
1200                 searches < 12) {
1201            getAreaHeader(cur_pointer, header_info);
1202            long area_size = (header_info[0] & 0x07FFFFFFFFFFFFFFFL);
1203            // Is this area is greater or equal than the required size
1204            // and is not the wilderness area, pick it.
1205            if (cur_pointer != wilderness_pointer && area_size >= size) {
1206              found_bin_index = i;
1207              previous_pointer = last_pointer;
1208            }
1209            // Go to next in chain.
1210            last_pointer = cur_pointer;
1211            cur_pointer = header_info[1];
1212            ++searches;
1213          }
1214        }
1215        
1216      }
1217      first = false;
1218    }
1219    
1220    // If no area can be recycled,
1221    if (found_bin_index == -1) {
1222      
1223      // Allocate a new area of the given size.
1224      // If there is a wilderness, grow the wilderness area to the new size,
1225      long working_pointer;
1226      long size_to_grow;
1227      long current_area_size;
1228      if (wilderness_pointer != -1) {
1229        working_pointer = wilderness_pointer;
1230        getAreaHeader(wilderness_pointer, header_info);
1231        long wilderness_size = (header_info[0] & 0x07FFFFFFFFFFFFFFFL);
1232        // Remove this from the bins
1233        removeFromBinChain(working_pointer, wilderness_size);
1234        // For safety, we set wilderness_pointer to -1
1235        wilderness_pointer = -1;
1236        size_to_grow = size - wilderness_size;
1237        current_area_size = wilderness_size;
1238      }
1239      else {
1240        // wilderness_pointer == -1 so add to the end of the data area.
1241        working_pointer = endOfDataAreaPointer();
1242        size_to_grow = size;
1243        current_area_size = 0;
1244      }
1245      
1246      long expanded_size = 0;
1247      if (size_to_grow > 0) {
1248        // Expand the data area to the new size.
1249        expanded_size = expandDataArea(size_to_grow);
1250      }
1251      // Coalesc the new area to the given size
1252      coalescArea(working_pointer, current_area_size + expanded_size);
1253      // crop the area
1254      cropArea(working_pointer, size);
1255
1256      // Add to the total allocated space
1257      total_allocated_space += real_alloc_size;
1258
1259      return working_pointer;
1260    }
1261    else {
1262      
1263      // An area is taken from the bins,
1264      long free_area_pointer;
1265      // Remove this area from the bin chain and possibly add any excess space
1266      // left over to a new bin.
1267      if (previous_pointer == -1) {
1268        free_area_pointer = free_bin_list[found_bin_index];
1269        getAreaHeader(free_area_pointer, header_info);
1270        free_bin_list[found_bin_index] = header_info[1];
1271        writeBinIndex(found_bin_index);
1272      }
1273      else {
1274        getAreaHeader(previous_pointer, header_info2);
1275        free_area_pointer = header_info2[1];
1276        getAreaHeader(free_area_pointer, header_info);
1277        header_info2[1] = header_info[1];
1278        reboundArea(previous_pointer, header_info2, false);
1279      }
1280
1281      // Reset the header of the recycled area.
1282      header_info[0] = (header_info[0] & 0x07FFFFFFFFFFFFFFFL);
1283      reboundArea(free_area_pointer, header_info, true);
1284
1285      // Crop the area to the given size.
1286      cropArea(free_area_pointer, size);
1287      
1288      // Add to the total allocated space
1289      total_allocated_space += real_alloc_size;
1290
1291      return free_area_pointer;
1292    }
1293
1294  }
1295
1296  /**
1297   * Frees a previously allocated area in the store.
1298   */
1299  private void free(long pointer) throws IOException {
1300    
1301    // Get the area header
1302    getAreaHeader(pointer, header_info);
1303
1304    if ((header_info[0] & 0x08000000000000000L) != 0) {
1305      throw new IOException("Area already marked as unallocated.");
1306    }
1307    
1308    // If (pointer + size) reaches the end of the header area, set this as the
1309    // wilderness.
1310    boolean set_as_wilderness =
1311                        ((pointer + header_info[0]) >= endOfDataAreaPointer());
1312    
1313    long r_pointer = pointer;
1314    final long freeing_area_size = header_info[0];
1315    long r_size = freeing_area_size;
1316    
1317    // Can this area coalesc?
1318    long left_pointer = getPreviousAreaHeader(pointer, header_info2);
1319    boolean coalesc = false;
1320    if ((header_info2[0] & 0x08000000000000000L) != 0) {
1321      // Yes, we can coalesc left
1322      long area_size = (header_info2[0] & 0x07FFFFFFFFFFFFFFFL);
1323
1324      r_pointer = left_pointer;
1325      r_size = r_size + area_size;
1326      // Remove left area from the bin
1327      removeFromBinChain(left_pointer, area_size);
1328      coalesc = true;
1329      
1330    }
1331
1332    if (!set_as_wilderness) {
1333      long right_pointer = getNextAreaHeader(pointer, header_info2);
1334      if ((header_info2[0] & 0x08000000000000000L) != 0) {
1335        // Yes, we can coalesc right
1336        long area_size = (header_info2[0] & 0x07FFFFFFFFFFFFFFFL);
1337
1338        r_size = r_size + area_size;
1339        // Remove right from the bin
1340        removeFromBinChain(right_pointer, area_size);
1341        set_as_wilderness = (right_pointer == wilderness_pointer);
1342        coalesc = true;
1343        
1344      }
1345    }
1346
1347    // If we are coalescing parent areas
1348    if (coalesc) {
1349      coalescArea(r_pointer, r_size);
1350    }
1351    
1352    // Add this new area to the bin chain,
1353    addToBinChain(r_pointer, r_size);
1354    
1355    // Do we set this as the wilderness?
1356    if (set_as_wilderness) {
1357      wilderness_pointer = r_pointer;
1358    }
1359
1360    total_allocated_space -= freeing_area_size;
1361    
1362  }
1363
1364  /**
1365   * Convenience for finding the size of an area.  If the area is deleted
1366   * throws an exception.
1367   */
1368  private long getAreaSize(final long pointer) throws IOException {
1369    final byte[] buf = new byte[8];
1370    readByteArrayFrom(pointer, buf, 0, 8);
1371    final long v = ByteArrayUtil.getLong(buf, 0);
1372    if ((v & 0x08000000000000000L) != 0) {
1373      throw new IOException("Area is deleted.");
1374    }
1375    return v - 16;
1376  }
1377
1378  
1379  // ---------- Implemented from Store ----------
1380
1381  public synchronized AreaWriter createArea(long size) throws IOException {
1382    long pointer = alloc(size);
1383    return new StoreAreaWriter(pointer, size);
1384  }
1385
1386  public synchronized void deleteArea(long id) throws IOException {
1387    free(id);
1388  }
1389
1390  public InputStream getAreaInputStream(long id) throws IOException {
1391    if (id == -1) {
1392      return new StoreAreaInputStream(FIXED_AREA_OFFSET, 64);
1393    }
1394    else {
1395      return new StoreAreaInputStream(id + 8, getAreaSize(id));
1396    }
1397  }
1398
1399  public Area getArea(long id) throws IOException {
1400    // If this is the fixed area
1401    if (id == -1) {
1402      return new StoreArea(id, FIXED_AREA_OFFSET, 64);
1403    }
1404    // Otherwise must be a regular area
1405    else {
1406      return new StoreArea(id, id);
1407    }
1408  }
1409
1410  public MutableArea getMutableArea(long id) throws IOException {
1411    // If this is the fixed area
1412    if (id == -1) {
1413      return new StoreMutableArea(id, FIXED_AREA_OFFSET, 64);
1414    }
1415    // Otherwise must be a regular area
1416    else {
1417      return new StoreMutableArea(id, id);
1418    }
1419  }
1420
1421  public boolean lastCloseClean() {
1422    return !dirty_open;
1423  }
1424  
1425  // ---------- Inner classes ----------
1426
1427  private class StoreAreaInputStream extends InputStream {
1428    
1429    private long pointer;
1430    private long end_pointer;
1431    private long mark;
1432    
1433    public StoreAreaInputStream(long pointer, long max_size) {
1434      this.pointer = pointer;
1435      this.end_pointer = pointer + max_size;
1436      this.mark = -1;
1437    }
1438    
1439    public int read() throws IOException {
1440      if (pointer >= end_pointer) {
1441        return -1;
1442      }
1443      int b = readByteFrom(pointer);
1444      ++pointer;
1445      return b;
1446    }
1447
1448    public int read(byte[] buf) throws IOException {
1449      return read(buf, 0, buf.length);
1450    }
1451    
1452    public int read(byte[] buf, int off, int len) throws IOException {
1453      // Is the end of the stream reached?
1454      if (pointer >= end_pointer) {
1455        return -1;
1456      }
1457      // How much can we read?
1458      int read_count = Math.min(len, (int) (end_pointer - pointer));
1459      int act_read_count;
1460      act_read_count = readByteArrayFrom(pointer, buf, off, read_count);
1461      if (act_read_count != read_count) {
1462        throw new IOException("act_read_count != read_count");
1463      }
1464      pointer += read_count;
1465      return read_count;
1466    }
1467
1468    public long skip(long skip) throws IOException {
1469      long to_skip = Math.min(end_pointer - pointer, skip);
1470      pointer += to_skip;
1471      return to_skip;
1472    }
1473
1474    public int available() throws IOException {
1475      return (int) (end_pointer - pointer);
1476    }
1477    
1478    public void close() throws IOException {
1479      // Do nothing
1480    }
1481    
1482    public void mark(int read_limit) {
1483      mark = pointer;
1484    }
1485    
1486    public void reset() throws IOException {
1487      pointer = mark;
1488    }
1489    
1490    public boolean markSupported() {
1491      return true;
1492    }
1493    
1494  }
1495  
1496
1497  
1498  private class StoreArea implements Area {
1499
1500    protected static final int BUFFER_SIZE = 8;
1501
1502    protected final long id;
1503    protected final long start_pointer;
1504    protected final long end_pointer;
1505    protected long position;
1506    // A small buffer used when accessing the underlying data
1507    protected final byte[] buffer = new byte[BUFFER_SIZE];
1508
1509    public StoreArea(final long id, final long pointer) throws IOException {
1510      // Check the pointer is within the bounds of the data area of the file
1511      checkPointer(pointer);
1512
1513      readByteArrayFrom(pointer, buffer, 0, 8);
1514      final long v = ByteArrayUtil.getLong(buffer, 0);
1515      if ((v & 0x08000000000000000L) != 0) {
1516        throw new IOException("Store being constructed on deleted area.");
1517      }
1518
1519      final long max_size = v - 16;
1520      this.id = id;
1521      this.start_pointer = pointer + 8;
1522      this.position = start_pointer;
1523      this.end_pointer = start_pointer + max_size;
1524    }
1525
1526    public StoreArea(final long id, final long pointer, final long fixed_size)
1527                                                          throws IOException {
1528      // Check the pointer is valid
1529      if (pointer != FIXED_AREA_OFFSET) {
1530        checkPointer(pointer);
1531      }
1532
1533      this.id = id;
1534      this.start_pointer = pointer;
1535      this.position = start_pointer;
1536      this.end_pointer = start_pointer + fixed_size;
1537    }
1538    
1539    protected long checkPositionBounds(int diff) throws IOException {
1540      long new_pos = position + diff;
1541      if (new_pos > end_pointer) {
1542        throw new IOException("Position out of bounds. " +
1543                              " start=" + start_pointer +
1544                              " end=" + end_pointer +
1545                              " pos=" + position +
1546                              " new_pos=" + new_pos);
1547      }
1548      long old_pos = position;
1549      position = new_pos;
1550      return old_pos;
1551    }
1552
1553    public long getID() {
1554      return id;
1555    }
1556
1557    public int position() {
1558      return (int) (position - start_pointer);
1559    }
1560    
1561    public int capacity() {
1562      return (int) (end_pointer - start_pointer);
1563    }
1564    
1565    public void position(int position) throws IOException {
1566      long act_position = start_pointer + position;
1567      if (act_position >= 0 && act_position < end_pointer) {
1568        this.position = act_position;
1569        return;
1570      }
1571      throw new IOException("Moved position out of bounds.");
1572    }
1573
1574    public void copyTo(AreaWriter destination_writer,
1575                       int size) throws IOException {
1576      // NOTE: Assuming 'destination' is a StoreArea, the temporary buffer
1577      // could be optimized away to a direct System.arraycopy.  However, this
1578      // function would need to be written as a lower level IO function.
1579      final int BUFFER_SIZE = 2048;
1580      byte[] buf = new byte[BUFFER_SIZE];
1581      int to_copy = Math.min(size, BUFFER_SIZE);
1582
1583      while (to_copy > 0) {
1584        get(buf, 0, to_copy);
1585        destination_writer.put(buf, 0, to_copy);
1586        size -= to_copy;
1587        to_copy = Math.min(size, BUFFER_SIZE);
1588      }
1589    }
1590    
1591    public byte get() throws IOException {
1592      return (byte) readByteFrom(checkPositionBounds(1));
1593    }
1594    
1595    public void get(byte[] buf, int off, int len) throws IOException {
1596      readByteArrayFrom(checkPositionBounds(len), buf, off, len);
1597    }
1598    
1599    public short getShort() throws IOException {
1600      readByteArrayFrom(checkPositionBounds(2), buffer, 0, 2);
1601      return ByteArrayUtil.getShort(buffer, 0);
1602    }
1603    
1604    public int getInt() throws IOException {
1605      readByteArrayFrom(checkPositionBounds(4), buffer, 0, 4);
1606      return ByteArrayUtil.getInt(buffer, 0);
1607    }
1608    
1609    public long getLong() throws IOException {
1610      readByteArrayFrom(checkPositionBounds(8), buffer, 0, 8);
1611      return ByteArrayUtil.getLong(buffer, 0);
1612    }
1613    
1614    public char getChar() throws IOException {
1615      readByteArrayFrom(checkPositionBounds(2), buffer, 0, 2);
1616      return ByteArrayUtil.getChar(buffer, 0);
1617    }
1618
1619
1620
1621    public String   toString() {
1622      return "[Area start_pointer=" + start_pointer +
1623             " end_pointer=" + end_pointer +
1624             " position=" + position + "]";
1625    }
1626    
1627  }
1628
1629
1630  
1631
1632  private class StoreMutableArea extends StoreArea implements MutableArea {
1633
1634    public StoreMutableArea(final long id, final long pointer)
1635                                                         throws IOException {
1636      super(id, pointer);
1637    }
1638
1639    public StoreMutableArea(final long id, final long pointer,
1640                            final long fixed_size) throws IOException {
1641      super(id, pointer, fixed_size);
1642    }
1643    
1644    public void checkOut() throws IOException {
1645      // Currently, no-op
1646    }
1647    
1648    public void put(byte b) throws IOException {
1649      writeByteToPT(checkPositionBounds(1), b);
1650    }
1651
1652    public void put(byte[] buf, int off, int len) throws IOException {
1653      writeByteArrayToPT(checkPositionBounds(len), buf, off, len);
1654    }
1655
1656    public void put(byte[] buf) throws IOException {
1657      put(buf, 0, buf.length);
1658    }
1659
1660    public void putShort(short s) throws IOException {
1661      ByteArrayUtil.setShort(s, buffer, 0);
1662      writeByteArrayToPT(checkPositionBounds(2), buffer, 0, 2);
1663    }
1664
1665    public void putInt(int i) throws IOException {
1666      ByteArrayUtil.setInt(i, buffer, 0);
1667      writeByteArrayToPT(checkPositionBounds(4), buffer, 0, 4);
1668    }
1669    
1670    public void putLong(long l) throws IOException {
1671      ByteArrayUtil.setLong(l, buffer, 0);
1672      writeByteArrayToPT(checkPositionBounds(8), buffer, 0, 8);
1673    }
1674
1675    public void putChar(char c) throws IOException {
1676      ByteArrayUtil.setChar(c, buffer, 0);
1677      writeByteArrayToPT(checkPositionBounds(2), buffer, 0, 2);
1678    }
1679    
1680    
1681    public String   toString() {
1682      return "[MutableArea start_pointer=" + start_pointer +
1683             " end_pointer=" + end_pointer +
1684             " position=" + position + "]";
1685    }
1686    
1687  }
1688
1689
1690
1691  /**
1692   * A simple OutputStream implementation that is on top of an AreaWriter
1693   * object.
1694   */
1695  static class AreaOutputStream extends OutputStream {
1696
1697    private final AreaWriter writer;
1698
1699    public AreaOutputStream(AreaWriter writer) {
1700      this.writer = writer;
1701    }
1702
1703    public void write(int b) throws IOException {
1704      writer.put((byte) b);
1705    }
1706
1707    public void write(byte[] buf) throws IOException {
1708      writer.put(buf, 0, buf.length);
1709    }
1710
1711    public void write(byte[] buf, int off, int len) throws IOException {
1712      writer.put(buf, off, len);
1713    }
1714
1715    public void flush() throws IOException {
1716      // do nothing
1717    }
1718
1719    public void close() throws IOException {
1720      // do nothing
1721    }
1722
1723  }
1724
1725
1726
1727  private class StoreAreaWriter extends StoreMutableArea implements AreaWriter {
1728
1729    public StoreAreaWriter(final long pointer, final long fixed_size)
1730                                                           throws IOException {
1731      super(pointer, pointer + 8, fixed_size);
1732    }
1733
1734    public OutputStream getOutputStream() {
1735      return new AreaOutputStream(this);
1736    }
1737
1738    public void finish() throws IOException {
1739      // Currently, no-op
1740    }
1741
1742  }
1743
1744
1745
1746
1747  
1748  // ---------- Static methods ----------
1749  
1750  /**
1751   * The default bin sizes in bytes.  The minimum size of a bin is 32 and the
1752   * maximum size is 2252832.
1753   */
1754  private final static int[] BIN_SIZES =
1755    { 32, 64, 96, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480,
1756      512, 544, 576, 608, 640, 672, 704, 736, 768, 800, 832, 864, 896, 928,
1757      960, 992, 1024, 1056, 1088, 1120, 1152, 1184, 1216, 1248, 1280, 1312,
1758      1344, 1376, 1408, 1440, 1472, 1504, 1536, 1568, 1600, 1632, 1664, 1696,
1759      1728, 1760, 1792, 1824, 1856, 1888, 1920, 1952, 1984, 2016, 2048, 2080,
1760      2144, 2208, 2272, 2336, 2400, 2464, 2528, 2592, 2656, 2720, 2784, 2848,
1761      2912, 2976, 3040, 3104, 3168, 3232, 3296, 3360, 3424, 3488, 3552, 3616,
1762      3680, 3744, 3808, 3872, 3936, 4000, 4064, 4128, 4384, 4640, 4896, 5152,
1763      5408, 5664, 5920, 6176, 6432, 6688, 6944, 7200, 7456, 7712, 7968, 8224,
1764      10272, 12320, 14368, 16416, 18464, 20512, 22560, 24608, 57376, 90144,
1765      122912, 155680, 1204256, 2252832
1766    };
1767
1768  protected final static int BIN_ENTRIES = BIN_SIZES.length;
1769  private final static int MAX_BIN_SIZE = BIN_SIZES[BIN_ENTRIES - 1];
1770
1771}
1772
1773
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags