VariableSizeDataStore


1   /**
2    * com.mckoi.database.VariableSizeDataStore  25 Jun 2000
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 com.mckoi.debug.*;
28  import com.mckoi.util.ByteArrayUtil;
29  import com.mckoi.util.UserTerminal;
30  import java.io.*;
31  import java.util.zip.*;
32  
33  /**
34   * Provides a mechanism for storing variable length data in a file which can
35   * quickly be indexed via a reference number.  The store maintains a master
36   * index file that contains a reference to all individual data records stored
37   * in the system.  The data file contains all the data that has been stored.
38   * <p>
39   * This file format is not intended to be a fully fledged file system.  For
40   * example, we can not easily change the size of a data entry.  To change the
41   * record, we must delete it then add a new.
42   * <p>
43   * This system uses two files.  One file is the index, and the second file
44   * stores the data.  The index file contains sectors as follows:
45   * <p><pre>
46   *   4 (int) : index  - The sector index of the data in the data file.
47   *   4 (int) : length - Length of the data that was stored.
48   *   4 (int) : status - 32 status bits.
49   * </pre>
50   * <p>
51   * This employs a simple compression scheme when writing out data that would
52   * span more than one sector.  It tries compressing the field.  If the field
53   * can be compressed into less sectors than if left uncompressed, then the
54   * compressed field is put into the data store.
55   *
56   * @author Tobias Downer
57   */
58  
59  public class VariableSizeDataStore {
60  
61    /**
62     * Set to true to enable compressed writes.
63     */
64    private final static boolean COMPRESSED_WRITE_ENABLED = true;
65  
66    /**
67     * The size of elements of each allocation sector.
68     */
69    private final static int INDEX_SECTOR_SIZE = (4 * 3);
70  
71  
72    /**
73     * A DebugLogger object used to log error messages to.
74     */
75    private final DebugLogger debug;
76  
77    /**
78     * The index data allocation file.
79     */
80    private FixedSizeDataStore allocation_store;
81  
82    /**
83     * The actual data file.
84     */
85    private FixedSizeDataStore data_store;
86  
87    /**
88     * A buffer to store the index key.
89     */
90    private byte[] index_key;
91  
92    /**
93     * A Deflater and Inflater used to compress and uncompress the size of data
94     * fields put into the store.
95     */
96    private Deflater deflater;
97    private Inflater inflater;
98    private byte[] compress_buffer;
99  
100 
101 
102 
103   /**
104    * Constructs the variable size store.
105    */
106   public VariableSizeDataStore(File name, int sector_size,
107                                DebugLogger logger) {
108     this.debug = logger;
109     index_key = new byte[INDEX_SECTOR_SIZE];
110 
111     // We create two files, name + ".axi" and name + ".dss"
112     // The .axi file is the allocation index.  The .dss is the data sector
113     // storage.
114     String   path = name.getPath();
115     allocation_store = new FixedSizeDataStore(new File(path + ".axi"),
116                                               INDEX_SECTOR_SIZE, debug);
117     data_store = new FixedSizeDataStore(new File(path + ".dss"),
118                                         sector_size, debug);
119   }
120 
121   public VariableSizeDataStore(File name, DebugLogger logger) {
122     this(name, -1, logger);
123   }
124 
125 
126 
127 
128 
129   // ---------- Private methods ----------
130 
131 
132 
133 
134 
135   // ---------- Public methods ----------
136 
137   /**
138    * Synchronizes all the data in memory with the hard copy on disk.
139    */
140   public void synch() throws IOException {
141     allocation_store.synch();
142     data_store.synch();
143   }
144 
145   /**
146    * Hard synchronizes the data from memory into the hard copy on disk.  This
147    * is guarenteed to ensure the image on the disk will match the image in
148    * memory.
149    */
150   public void hardSynch() throws IOException {
151     allocation_store.hardSynch();
152     data_store.hardSynch();
153   }
154 
155   /**
156    * Returns true if we are locked.
157    */
158   public boolean locked() {
159     return allocation_store.locked();
160   }
161 
162   /**
163    * Locks the store so that not deleted elements may be overwritten.
164    */
165   public void lock() {
166     allocation_store.lock();
167     data_store.lock();
168   }
169 
170   /**
171    * Unlocks the store so that deleted elements can be reclaimed again.
172    */
173   public void unlock() {
174     data_store.unlock();
175     allocation_store.unlock();
176   }
177 
178 
179   /**
180    * Returns true if the given record is marked as deleted or not.
181    */
182   public boolean recordDeleted(int record_index) throws IOException {
183     return allocation_store.isSectorDeleted(record_index);
184   }
185 
186   /**
187    * Returns the number of records that are being used.
188    */
189   public int usedRecordCount() {
190     return allocation_store.getSectorUseCount();
191   }
192 
193   /**
194    * Returns the total number of records that are in the store (including
195    * deleted records.
196    */
197   public int rawRecordCount() throws IOException {
198     return allocation_store.rawSectorCount();
199   }
200 
201   /**
202    * Returns true if the data store exists.
203    */
204   public boolean exists() throws IOException {
205     return allocation_store.exists() && data_store.exists();
206   }
207 
208   /**
209    * Returns true if the store was openned in read only mode.
210    */
211   public boolean isReadOnly() {
212     return data_store.isReadOnly();
213   }
214 
215   /**
216    * Opens the data store.  The data store can be opened in 'read only' mode.
217    * Returns 'true' if the open procedure should repair itself (dirty open)
218    * or false if the file was cleanly closed down.
219    * <p>
220    * It is not possible to open a damaged store in read only mode.
221    *
222    * @param read_only if true, then the database is opened in read only mode,
223    *   otherwise it is opened in read/write mode.
224    */
225   public boolean open(boolean read_only) throws IOException {
226     boolean r1 = allocation_store.open(read_only);
227     boolean r2 = data_store.open(read_only);
228     return r1 | r2;
229   }
230 
231   /**
232    * Closes the data store.
233    */
234   public void close() throws IOException {
235     allocation_store.close();
236     data_store.close();
237   }
238 
239   /**
240    * Deletes the store from the file system.  Must be called after a 'close'.
241    */
242   public void delete() {
243     allocation_store.delete();
244     data_store.delete();
245   }
246 
247   /**
248    * Attempts to fix a corrupt VariableSizeDataStore object.
249    * <p>
250    * The store should be open before this method is called.
251    */
252   public void fix(UserTerminal terminal) throws IOException {
253     terminal.println("+ Fixing variable data store.");
254     // First fix the allocation store and data store.
255     allocation_store.fix(terminal);
256     data_store.fix(terminal);
257 
258     terminal.println("- Repairing references.");
259     // Now look for bad references on this layer.  What we do here is we check
260     // that each allocation record references a valid chain in the data
261     // store.  If it doesn't then we delete it.
262     int sector_count = allocation_store.rawSectorCount();
263     int data_sector_count = data_store.rawSectorCount();
264     terminal.println("- Sector count: " + sector_count);
265     // For each allocation entry trace its chain and mark each sector as
266     // taken.
267     int bad_record_count = 0;
268     int deleted_record_count = 0;
269     for (int i = 0; i < sector_count; ++i) {
270       if (!allocation_store.isSectorDeleted(i)) {
271         allocation_store.getSector(i, index_key);
272         int sector_head = ByteArrayUtil.getInt(index_key, 0);
273         int length = ByteArrayUtil.getInt(index_key, 4);
274         // Is the sector head pointing to a valid record?
275         if (sector_head < 0 || sector_head >= data_sector_count ||
276             length <= 0) {
277           ++bad_record_count;
278           // Mark this allocation entry as deleted.
279           allocation_store.deleteAcross(i);
280           ++deleted_record_count;
281         }
282         else {
283           int[] chain_span = data_store.getSectorChain(sector_head, length);
284         }
285       }
286       else {
287         ++deleted_record_count;
288       }
289     }
290     // Print statistics,
291     terminal.println("- Fixed " + bad_record_count + " bad chains.");
292 
293   }
294 
295   /**
296    * Copies this data store to the given path.  The store must be open when
297    * this is called.
298    */
299   public void copyTo(File path) throws IOException {
300     allocation_store.copyTo(path);
301     data_store.copyTo(path);
302   }
303 
304   /**
305    * Updates the 32-bit type_key int of a record.  Bit 1-8 are reserved for
306    * this data store, and are used to indicate such things as whether the
307    * record chain is compressed or not.  The rest of the bits can be used
308    * for any purpose.  It is recommended bits 8 through 16 are used for
309    * user-definable information.
310    */
311   public int writeRecordType(int record_index, int type_key)
312                                                        throws IOException {
313     // Read it in first,
314     // The index of the record to retrieve.
315     allocation_store.getSector(record_index, index_key);
316     // Any special keys regarding how the info was stored
317     int cur_type_key = ByteArrayUtil.getInt(index_key, 8);
318     // Record this.
319     final int old_type_key = cur_type_key;
320     // Merge type key
321     type_key = (type_key & 0x0FFFFFFF0) | (cur_type_key & 0x0F);
322     ByteArrayUtil.setInt(type_key, index_key, 8);
323     // And overwrite the sector
324     allocation_store.overwriteSector(record_index, index_key);
325 
326     // Return the type key as it was before the change.
327     return old_type_key;
328   }
329 
330   /**
331    * Reads the 32-bit type_key int for the given record.  The 'type_key'
332    * contains various bit flags set for the record.
333    */
334   public int readRecordType(int record_index) throws IOException {
335     // Read it in first,
336     // The index of the record to retrieve.
337     allocation_store.getSector(record_index, index_key);
338     // Any special keys regarding how the info was stored
339     int cur_type_key = ByteArrayUtil.getInt(index_key, 8);
340 
341     // Return the type key for this record.
342     return cur_type_key;
343   }
344 
345   /**
346    * Writes a variable length byte[] array to the first available index.
347    * Returns the index reference for this element.
348    */
349   public int write(byte[] buf, int offset, int length) throws IOException {
350 
351     // If the length of the record to add is bigger than a sector then try
352     // and compress it.
353     int sector_size = data_store.getSectorSize();
354     boolean use_compressed_form = false;
355 
356     int compress_size = -1;
357     if (COMPRESSED_WRITE_ENABLED) {
358       if (length > sector_size) {
359         int orig_span = data_store.calculateSectorSpan(length);
360 
361         if (deflater == null) {
362           deflater = new Deflater();
363         }
364         deflater.setInput(buf, offset, length);
365         deflater.finish();
366 
367         if (compress_buffer == null || compress_buffer.length < length + 4) {
368           compress_buffer = new byte[length + 4];
369         }
370         compress_size = deflater.deflate(compress_buffer) + 4;
371         deflater.reset();
372 
373         int new_span = data_store.calculateSectorSpan(compress_size);
374         if (new_span < orig_span) {
375           // Put the length of the original buffer on the end of the compressed
376           // data.
377           ByteArrayUtil.setInt(length, compress_buffer, compress_size - 4);
378           use_compressed_form = true;
379         }
380 
381       }
382     }
383 
384     // Write the data to the data file,
385     int v;
386     int real_length;
387     int type_key = 0;
388     if (use_compressed_form) {
389       v = data_store.writeAcross(compress_buffer, 0, compress_size);
390       real_length = compress_size;
391       // Indicate this run is compressed.
392       type_key = type_key | 0x0001;
393     }
394     else {
395       v = data_store.writeAcross(buf, offset, length);
396       real_length = length;
397     }
398     // Create a new index key,
399     // The first index
400     ByteArrayUtil.setInt(v, index_key, 0);
401     ByteArrayUtil.setInt(real_length, index_key, 4);
402     ByteArrayUtil.setInt(type_key, index_key, 8);
403 
404     // Add to the allocation store last.
405     return allocation_store.addSector(index_key);
406   }
407 
408   /**
409    * Reads a variable length byte[] array from the given index position.
410    * This will read the first n bytes from the element, upto the maximum that
411    * was stored.  It returns the number of bytes that were read.
412    */
413   public int read(int record, byte[] buf, int offset, int length)
414                                                           throws IOException {
415 
416     // The index of the record to retrieve.
417     allocation_store.getSector(record, index_key);
418     // Get the head of the chain,
419     int chain_head = ByteArrayUtil.getInt(index_key, 0);
420     // The length of data that was stored.
421     int data_length = ByteArrayUtil.getInt(index_key, 4);
422     // Any special keys regarding how the info was stored
423     int type_key = ByteArrayUtil.getInt(index_key, 8);
424 
425     // If it's compressed, read in the compressed data to the buffer.
426     if ((type_key & 0x0001) != 0) {
427       if (compress_buffer == null || compress_buffer.length < data_length) {
428         compress_buffer = new byte[data_length];
429       }
430       data_store.readAcross(chain_head, compress_buffer, 0, data_length);
431 
432       // Then extract as much as we can into the input buffer.
433       if (inflater == null) {
434         inflater = new Inflater();
435       }
436       inflater.reset();
437       inflater.setInput(compress_buffer, 0, data_length);
438       int inflate_count;
439       try {
440         inflate_count = inflater.inflate(buf, offset, length);
441       }
442       catch (DataFormatException e) {
443         e.printStackTrace();
444         debug.writeException(e);
445         throw new Error  (e.getMessage());
446       }
447 
448       return inflate_count;
449     }
450     else {
451       // Not compressed...
452       // The amount we are reading,
453       int read_amount = Math.min(length, data_length);
454       // Read it in,
455       data_store.readAcross(chain_head, buf, offset, read_amount);
456 
457       return read_amount;
458     }
459 
460   }
461 
462   /**
463    * Reads in a complete record and puts it into the returned byte[] array.
464    */
465   public byte[] readRecord(int record) throws IOException {
466     // The index of the record to retrieve.
467     allocation_store.getSector(record, index_key);
468     // Get the head of the chain,
469     int chain_head = ByteArrayUtil.getInt(index_key, 0);
470     // The length of data that was stored.
471     int data_length = ByteArrayUtil.getInt(index_key, 4);
472     // Any special keys regarding how the info was stored
473     int type_key = ByteArrayUtil.getInt(index_key, 8);
474 
475     // If it's compressed, read in the compressed data to the buffer.
476     if ((type_key & 0x0001) != 0) {
477       if (compress_buffer == null || compress_buffer.length < data_length) {
478         compress_buffer = new byte[data_length];
479       }
480       data_store.readAcross(chain_head, compress_buffer, 0, data_length);
481 
482       // Then extract as much as we can into the input buffer.
483       if (inflater == null) {
484         inflater = new Inflater();
485       }
486       // Get the size of the uncompressed form...
487       int uncompressed_size =
488                        ByteArrayUtil.getInt(compress_buffer, data_length - 4);
489 
490       byte[] buf = new byte[uncompressed_size];
491 
492       inflater.reset();
493       inflater.setInput(compress_buffer, 0, data_length - 4);
494       int inflate_count;
495       try {
496         inflate_count = inflater.inflate(buf);
497       }
498       catch (DataFormatException e) {
499         e.printStackTrace();
500         debug.writeException(e);
501         throw new Error  (e.getMessage());
502       }
503 
504       if (inflate_count != buf.length) {
505         throw new Error  ("Inflate size != buf.length (" +
506                         inflate_count + " != " + buf.length + ")");
507       }
508 
509       return buf;
510     }
511     else {
512       // Not compressed...
513       // Allocate the buffer store.
514       byte[] buf = new byte[data_length];
515       // Read it in,
516       data_store.readAcross(chain_head, buf, 0, data_length);
517 
518       return buf;
519     }
520 
521   }
522 
523   /**
524    * Deletes the data at the given index position.
525    */
526   public int delete(int record) throws IOException {
527     // The index of the record to delete,
528     allocation_store.getSector(record, index_key);
529     // Get the head of the chain to delete.
530     int chain_head = ByteArrayUtil.getInt(index_key, 0);
531 
532     // Delete the allocation index,
533     allocation_store.deleteSector(record);
534     // Delete the data chain,
535     data_store.deleteAcross(chain_head);
536 
537     return record;
538   }
539 
540   private OutputStream sector_output_stream = null;
541 
542   /**
543    * Returns an OutputStream object that can be used to write data into the
544    * store.  When the 'completeWriteStream' method is called, the records in
545    * this store are updated appropriately for the data written in, and a
546    * record index is returned.
547    * <p>
548    * NOTE: Only one open stream may be active at a time.  While this stream
549    *   is open this VariableSizeDataStore object may not be used in any other
550    *   way.
551    */
552   public OutputStream getRecordOutputStream() throws IOException {
553     if (sector_output_stream == null) {
554       sector_output_stream = data_store.getSectorOutputStream();
555       return sector_output_stream;
556     }
557     else {
558       throw new Error  ("More than one record output stream opened.");
559     }
560   }
561 
562   /**
563    * Updates the record allocation table with the data in the output stream
564    * returned by 'getRecordOutputStream'.  Returns an index for how to
565    * reference this data later.
566    * <p>
567    * After this method is called it is safe again to use this
568    * VariableSizeDataStore object.
569    */
570   public int completeRecordStreamWrite() throws IOException {
571     if (sector_output_stream != null) {
572       int v = data_store.getSectorOfLastOutputStream();
573       int real_length = data_store.getLengthOfLastOutputStream();
574       int type_key = 0;
575       // Create a new index key,
576       // The first index
577       ByteArrayUtil.setInt(v, index_key, 0);
578       ByteArrayUtil.setInt(real_length, index_key, 4);
579       ByteArrayUtil.setInt(type_key, index_key, 8);
580 
581       sector_output_stream = null;
582       data_store.wipeLastOutputStream();
583 
584       // Add to the allocation store last.
585       return allocation_store.addSector(index_key);
586     }
587     else {
588       throw new Error  ("Output stream not available.");
589     }
590   }
591 
592   /**
593    * Returns an InputStream that is used to read a record in this store with
594    * the given index.
595    * <p>
596    * NOTE: This can not handle compressed records.
597    * <p>
598    * NOTE: This does not detect the end of stream (reading past the end of the
599    *   record will return undefined data).
600    */
601   public InputStream getRecordInputStream(int record) throws IOException {
602     // The index of the record to read,
603     allocation_store.getSector(record, index_key);
604     // Get the head of the chain to read.
605     int chain_head = ByteArrayUtil.getInt(index_key, 0);
606 
607     // Open the input stream.
608     return data_store.getSectorInputStream(chain_head);
609   }
610 
611 
612 
613   /**
614    * Returns the size (in bytes) of the sectors used to store information in
615    * the data file.
616    */
617   public int sectorSize() throws IOException {
618     return data_store.getSectorSize();
619   }
620 
621   /**
622    * Returns the size of the given record number (compressed size if
623    * applicable).
624    */
625   public int recordSize(int record) throws IOException {
626     // The index of the record to retrieve.
627     allocation_store.getSector(record, index_key);
628     // Return the size of the record
629     return ByteArrayUtil.getInt(index_key, 4);
630   }
631 
632   /**
633    * Returns true if the given record is compressed.
634    */
635   public boolean isCompressed(int record) throws IOException {
636     // The index of the record.
637     allocation_store.getSector(record, index_key);
638     // Return true if the compressed bit is set.
639     return (ByteArrayUtil.getInt(index_key, 8) & 0x0001) != 0;
640   }
641 
642   /**
643    * Returns the number of sectors the given record takes up in the data
644    * store.
645    */
646   public int recordSectorCount(int record) throws IOException {
647     // Returns the number of sectors a record of this size will span using
648     // the current sector size.
649     return data_store.calculateSectorSpan(recordSize(record));
650   }
651 
652   /**
653    * Returns the size of the data file that keeps all the data in this
654    * store.  This is the file size of the data store.
655    */
656   public long totalStoreSize() {
657     return data_store.totalSize();
658   }
659 
660   /**
661    * Writes reserved information to the variable data store.  You may only
662    * write upto 128 bytes to the reserved data buffer.
663    */
664   public void writeReservedBuffer(byte[] info, int offset, int length,
665                                   int res_offset) throws IOException {
666     allocation_store.writeReservedBuffer(info, offset, length, res_offset);
667   }
668 
669   public void writeReservedBuffer(byte[] info, int offset, int length)
670                                                            throws IOException {
671     allocation_store.writeReservedBuffer(info, offset, length);
672   }
673 
674   /**
675    * Reads reserved information from the variable data store.  You may only
676    * read upto 128 bytes from the reserved data buffer.
677    */
678   public void readReservedBuffer(byte[] info, int offset, int length)
679                                                            throws IOException {
680     allocation_store.readReservedBuffer(info, offset, length);
681   }
682 
683 
684   // ---------- Static methods ----------
685 
686   /**
687    * Convenience for checking if a given data store exists or not.  Returns
688    * true if it exists.
689    */
690   public static boolean exists(File path, String   name) throws IOException {
691     File af = new File(path, name + ".axi");
692     File df = new File(path, name + ".dss");
693 
694     return (af.exists() & df.exists());
695   }
696 
697   /**
698    * Convenience for deleting a VariableSizeDataStore store.
699    */
700   public static boolean delete(File path, String   name) throws IOException {
701     File af = new File(path, name + ".axi");
702     File df = new File(path, name + ".dss");
703 
704     return (af.delete() & df.delete());
705   }
706 
707   /**
708    * Convenience for renaming a VariableSizeDataStore store to another name.
709    */
710   public static boolean rename(File path_source, String   name_source,
711                          File path_dest, String   name_dest) throws IOException {
712     File afs = new File(path_source, name_source + ".axi");
713     File dfs = new File(path_source, name_source + ".dss");
714     File afd = new File(path_dest, name_dest + ".axi");
715     File dfd = new File(path_dest, name_dest + ".dss");
716 
717     return (afs.renameTo(afd) & dfs.renameTo(dfd));
718   }
719 
720 
721 
722   // ---------- Testing methods ----------
723 
724   public int writeString(String   str) throws IOException {
725     byte[] bts = str.getBytes();
726     return write(bts, 0, bts.length);
727   }
728 
729   public String   readString(int record) throws IOException {
730     byte[] buffer = new byte[65536];
731     int read_in = read(record, buffer, 0, 65536);
732     return new String  (buffer, 0, read_in);
733   }
734 
735 }
736
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags