Java > Open Source Codes > com > mckoi > database > IndexStore


1 /**
2  * com.mckoi.database.IndexStore 19 Sep 2001
3  *
4  * Mckoi SQL Database ( http://www.mckoi.com/database )
5  * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * Version 2 as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License Version 2 for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * Version 2 along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Change Log:
21  *
22  *
23  */
24
25 package com.mckoi.database;
26
27 import java.io.IOException ;
28 import java.io.File ;
29 import java.io.DataOutputStream ;
30 import java.io.ByteArrayOutputStream ;
31 import java.util.ArrayList ;
32 import com.mckoi.util.IntegerListInterface;
33 import com.mckoi.util.AbstractBlockIntegerList;
34 import com.mckoi.util.BlockIntegerList;
35 import com.mckoi.util.BlockIntegerList.IntArrayListBlock;
36 import com.mckoi.util.IntegerListBlockInterface;
37 import com.mckoi.util.IntegerIterator;
38 import com.mckoi.util.IndexComparator;
39 import com.mckoi.util.ByteBuffer;
40 import com.mckoi.util.ByteArrayUtil;
41 import com.mckoi.util.IntegerVector;
42 import com.mckoi.util.UserTerminal;
43 import com.mckoi.util.Cache;
44 import com.mckoi.debug.*;
45
46 /**
47  * A class that manages the storage of a set of transactional index lists in a
48  * way that is fast to modify. This class has a number of objectives;
49  * <p>
50  * <ul>
51  * <li>To prevent corruption as best as possible.</li>
52  * <li>To be able to modify lists of integers very fast and persistantly.</li>
53  * <li>To have size optimization features such as defragmentation.</li>
54  * <li>To provide very fast searches on sorted lists (caching features).</li>
55  * <li>To be able to map a list to an IntegerListInterface interface.</li>
56  * </ul>
57  * <p>
58  * None intuitively, this object also handles unique ids.
59  *
60  * @author Tobias Downer
61  */
62
63 public final class IndexStore {
64
65   /**
66    * A DebugLogger object used to log debug messages to.
67    */
68   private DebugLogger debug;
69
70   /**
71    * The name of the index store file.
72    */
73   private File file;
74
75   /**
76    * The size of a 'block' element of index information in a list. This has
77    * a direct relation to the size of the sectors in the store. This value
78    * can be tuned for specific tables. For example, a table that will only
79    * ever contain a few items can save disk space by having a smaller block
80    * size.
81    */
82   private int block_size;
83
84   /**
85    * The FixedSizeDataStore that contains all the data of the index store.
86    */
87   private FixedSizeDataStore index_store;
88
89   /**
90    * The list of table sector entries that are currently committed. Each
91    * entry of this list points to a table index list. The list is formatted
92    * as follows;
93    * <p><pre>
94    * 0 (byte) - the type of block.
95    * 1 (int) - the number of blocks in this list.
96    * 5 (int) - the sector of column status information or -1 if
97    * no stats available.
98    * 9 to (n * (4 + 4 + 4 + 2))
99    * - the sector (int), the first and last entry of the
100    * block and the number of indices in the block
101    * (short) of each block in this list.
102    * 9 + (n * (4 + 4 + 4 + 2)) .... [ next block ] ....
103    * </pre>
104    */
105   private ByteBuffer index_table_list;
106   private byte[] index_table_list_buf;
107
108   /**
109    * The start sector where the block allocation information is currently
110    * stored.
111    */
112   private int allocation_sector;
113
114   /**
115    * The current of the allocation information.
116    */
117   private int allocation_length;
118
119   /**
120    * The list of SnapshotIndexSet objects returned via the
121    * 'getSnapshotIndexSet' method. This can be inspected to find all sectors
122    * currently being used to store index information.
123    */
124   private ArrayList memory_index_set_list;
125
126   /**
127    * The list of SnapshotIndexSet objects that have been deleted and are
128    * ready for garbage collection.
129    */
130   private ArrayList index_set_garbage;
131
132
133   /**
134    * Unique id field that contains a unique number that can be incremented
135    * atomically.
136    */
137   private long unique_id;
138
139   /**
140    * A cache of int[] array blocks that are accessed by this store.
141    */
142   private Cache sector_cache;
143 // private long cache_hit = 0, cache_miss = 0, cache_access = 0;
144
145   /**
146    * Constructs the IndexStore.
147    *
148    * @param file_name the path to the file of the index store in the file
149    * system.
150    */
151   public IndexStore(File file_name, DebugLogger logger) {
152     this.debug = logger;
153     this.file = file_name;
154     this.memory_index_set_list = new ArrayList ();
155     this.index_set_garbage = new ArrayList ();
156     this.sector_cache = new Cache(47, 47, 10);
157   }
158
159   // ---------- Private methods ----------
160
161   /**
162    * Reads the index table allocation list in to the ByteBuffer object. The
163    * position of the table allocation list can be determined by looking in the
164    * reserved area of the index file.
165    */
166   private synchronized void readIndexTableList() throws IOException {
167     // Read the reserved area for the sector of the allocation information
168 byte[] buf = new byte[32];
169     index_store.readReservedBuffer(buf, 0, 32);
170     allocation_sector = ByteArrayUtil.getInt(buf, 0);
171     allocation_length = ByteArrayUtil.getInt(buf, 4);
172     unique_id = ByteArrayUtil.getLong(buf, 8);
173     // Read the entire allocation information into the ByteBuffer
174 buf = new byte[allocation_length];
175     index_store.readAcross(allocation_sector, buf, 0, allocation_length);
176     index_table_list_buf = new byte[allocation_length];
177     index_table_list = new ByteBuffer(index_table_list_buf);
178     index_table_list.put(buf);
179   }
180
181   /**
182    * Initializes the index store to a blank state.
183    */
184   private synchronized void initBlank() throws IOException {
185     // Write the blank allocation area first
186 allocation_length = 0;
187     byte[] buf = new byte[allocation_length];
188     allocation_sector = index_store.writeAcross(buf, 0, buf.length);
189     // Write the reserved area
190 buf = new byte[32];
191     ByteArrayUtil.setInt(allocation_sector, buf, 0);
192     ByteArrayUtil.setInt(allocation_length, buf, 4);
193     ByteArrayUtil.setLong(1, buf, 8);
194     index_store.writeReservedBuffer(buf, 0, 32);
195   }
196
197
198
199
200
201
202
203
204
205
206   // ---------- Public methods ----------
207
208   /**
209    * Returns true if the index store file exists.
210    */
211   public synchronized boolean exists() throws IOException {
212     return file.exists();
213   }
214
215   /**
216    * Creates a new black index store and returns leaving the newly created
217    * store in an open state. This method initializes the various data in
218    * the index store for a blank set of index tables. Must call the 'init'
219    * method after this is called.
220    * <p>
221    * @param block_size the number of ints stored in each block. This
222    * can be optimized for specific use. Must be between 0 and 32768.
223    */
224   public synchronized void create(int block_size) throws IOException {
225     // Make sure index store is closed
226 if (index_store != null && !index_store.isClosed()) {
227       throw new Error ("Index store is already open.");
228     }
229
230     if (block_size > 32767) {
231       throw new Error ("block_size must be less than 32768");
232     }
233     if (exists()) {
234       throw new IOException ("Index store file '" + file +
235                             "' already exists.");
236     }
237
238     // 'unique_id' now starts at 1 as requested
239 unique_id = 1;
240
241     // Set the block size
242 this.block_size = block_size;
243     // Calculate the size of a sector. The sector size is block_size * 4
244 int sector_size = block_size * 4;
245     // NOTE: We don't cache access because the IndexStore manages caching
246 this.index_store = new FixedSizeDataStore(file, sector_size, false, debug);
247
248     // Create the index store file
249 index_store.open(false);
250
251     // Initialize the index store with blank information.
252 initBlank();
253
254   }
255
256   /**
257    * Opens this index store. If 'read_only' is set to true then the store
258    * is opened in read only mode.
259    * <p>
260    * Returns true if opening the store was dirty (was not closed properly) and
261    * may need repair.
262    * <p>
263    * If the index store does not exist before this method is called then it
264    * is created.
265    */
266   public synchronized boolean open(boolean read_only) throws IOException {
267     // Make sure index store is closed
268 if (index_store != null && !index_store.isClosed()) {
269       throw new Error ("Index store is already open.");
270     }
271
272     if (index_store == null) {
273       // NOTE: We don't cache access because the IndexStore manages caching
274 this.index_store = new FixedSizeDataStore(file, -1, false, debug);
275     }
276
277     // Open the index store file
278 boolean dirty_open = index_store.open(read_only);
279
280     // What's the sector size?
281 int sector_size = index_store.getSectorSize();
282     // Assert that sector_size is divisible by 4
283 if (sector_size % 4 != 0) {
284       throw new Error ("Assert failed, sector size must be divisible by 4");
285     }
286     // The block size
287 this.block_size = sector_size / 4;
288
289     return dirty_open;
290   }
291
292   /**
293    * Initializes the IndexStore. Must be called after it is opened for
294    * normal use, however it should not be called if we are fixing or repairing
295    * the store.
296    */
297   public synchronized void init() throws IOException {
298     // Read the index store and set up this store with the information.
299 readIndexTableList();
300   }
301
302   /**
303    * Performs checks to determine that the index store
304    * is stable. If an IndexStore is not stable and can not be fixed
305    * cleanly then it deletes all information in the store and returns false
306    * indicating the index information must be rebuilt.
307    * <p>
308    * Assumes the index store has been opened previous to calling this.
309    * <p>
310    * Returns true if the IndexStore is stable.
311    */
312   public synchronized boolean fix(UserTerminal terminal) throws IOException {
313
314     // Open the index store file
315 index_store.fix(terminal);
316
317     // Read the index store and set up this store with the information.
318 readIndexTableList();
319
320     // The number of sectors (used and deleted) in the store.
321 int raw_sector_count = index_store.rawSectorCount();
322
323     // Check that at least the reserved area is stable
324 try {
325       // Read the reserved area for the sector of the allocation information
326 byte[] buf = new byte[32];
327       index_store.readReservedBuffer(buf, 0, 32);
328     }
329     catch (IOException e) {
330       terminal.println("! Index store is irrepairable - " +
331                        "reserved area is missing.");
332       // An IOException here means the table file is lost because we've lost
333 // the unique sequence key for the table.
334 throw new IOException ("Irrepairable index store.");
335     }
336
337     try {
338       readIndexTableList();
339
340       // A running count of all index items in all lists
341 long used_block_count = 0;
342       // A running count of all block sizes
343 long total_block_count = 0;
344
345       // Contains a list of all the sectors referenced
346 BlockIntegerList sector_list = new BlockIntegerList();
347
348       // Set to the start of the buffer
349 index_table_list.position(0);
350
351       // Look at all the information in index_table_list and make sure it
352 // is correct.
353 while (index_table_list.position() < index_table_list.limit()) {
354         byte type = index_table_list.getByte();
355         int block_count = index_table_list.getInt();
356         int stat_sector = index_table_list.getInt();
357
358         if (stat_sector != -1) {
359           boolean b = sector_list.uniqueInsertSort(stat_sector);
360           if (b == false) {
361             terminal.println("! Index store is not stable - " +
362                              "double reference to stat_sector.");
363             return false;
364           }
365
366           // Check this sector exists and is not deleted.
367 if (stat_sector < 0 || stat_sector >= raw_sector_count ||
368               index_store.isSectorDeleted(stat_sector)) {
369             terminal.println("! Index store is not stable - " +
370                              "referenced sector is deleted.");
371             return false;
372           }
373
374         }
375
376         for (int i = 0; i < block_count; ++i) {
377           int first_entry = index_table_list.getInt();
378           int last_entry = index_table_list.getInt();
379           int block_sector = index_table_list.getInt();
380           short int_count = index_table_list.getShort();
381
382           // Update statistics
383 used_block_count += int_count;
384           total_block_count += block_size;
385
386           // Block sector not double referenced?
387 boolean b = sector_list.uniqueInsertSort(block_sector);
388           if (b == false) {
389             terminal.println("! Index store is not stable - " +
390                              "double reference to block sector.");
391             return false;
392           }
393
394           // Block sector is present and not deleted.
395 if (block_sector < 0 || block_sector >= raw_sector_count ||
396               index_store.isSectorDeleted(block_sector)) {
397             terminal.println("! Index store is not stable - " +
398                              "referenced sector is deleted.");
399             return false;
400           }
401
402           // Read the block
403 byte[] block_contents = index_store.getSector(block_sector);
404           // Check the first and last entry are the same as in the header.
405 if (int_count > 0) {
406             if (ByteArrayUtil.getInt(block_contents, 0) != first_entry ||
407                 ByteArrayUtil.getInt(block_contents, (int_count - 1) * 4) !=
408                                                            last_entry) {
409               terminal.println("! A block of an index list does not " +
410                                "correctly correspond to its header info.");
411               return false;
412             }
413           }
414
415         } // For each block in a list
416
417       } // while (position < limit)
418
419       // Everything is good
420 terminal.println("- Index store is stable.");
421       // The total count of all index entries in the store
422 terminal.println("- Total used block count = " + used_block_count);
423       // The total space available in the store
424 terminal.println("- Total available block count = " + total_block_count);
425       // Calculate utilization
426 if (total_block_count != 0) {
427         double utilization = ((float) used_block_count /
428                               (float) total_block_count) * 100f;
429         terminal.println("- Index store utilization = " + utilization + "%");
430       }
431
432       return true;
433     }
434     catch (IOException e) {
435       terminal.println("! IO Error scanning index store: " + e.getMessage());
436       return false;
437     }
438
439   }
440
441   /**
442    * Returns true if this store is read only.
443    */
444   public synchronized boolean isReadOnly() {
445     return index_store.isReadOnly();
446   }
447
448   /**
449    * Deletes the store. Must have been closed before this is called.
450    */
451   public synchronized void delete() {
452     index_store.delete();
453   }
454
455   /**
456    * Copies the persistant part of this to another store. Must be open
457    * when this is called.
458    */
459   public synchronized void copyTo(File path) throws IOException {
460     index_store.copyTo(path);
461   }
462
463   /**
464    * Cleanly closes the index store.
465    */
466   public synchronized void close() throws IOException {
467     index_store.close();
468     sector_cache = null;
469     memory_index_set_list = null;
470     index_set_garbage = null;
471   }
472
473   /**
474    * Flushes all information in this index store to the file representing this
475    * store in the file system. This is called to persistantly update the
476    * state of the index store.
477    */
478   public synchronized void flush() throws IOException {
479     // Grab hold of the old allocation information
480 int old_sector = allocation_sector;
481     int old_length = allocation_length;
482     // Write the index_table_list to the store
483 allocation_length = index_table_list_buf.length;
484     allocation_sector =
485         index_store.writeAcross(index_table_list_buf, 0, allocation_length);
486
487     // Write to the reserved area thus 'committing' the changes
488 ByteArrayUtil.setInt(allocation_sector, flush_buffer, 0);
489     ByteArrayUtil.setInt(allocation_length, flush_buffer, 4);
490     ByteArrayUtil.setLong(unique_id, flush_buffer, 8);
491     index_store.writeReservedBuffer(flush_buffer, 0, 32);
492
493     // Delete the old allocation information
494 index_store.deleteAcross(old_sector);
495   }
496
497   private byte[] flush_buffer = new byte[32];
498
499   /**
500    * Performs a hard synchronization of this index store. This will force the
501    * OS to synchronize the contents of the data store.
502    * <p>
503    * For this to be useful, 'flush' should be called before a hardSynch.
504    */
505   public synchronized void hardSynch() throws IOException {
506     index_store.hardSynch();
507   }
508
509   /**
510    * The current unique id.
511    */
512   long currentUniqueID() {
513     return unique_id - 1;
514   }
515   
516   /**
517    * Atomically returns the next 'unique_id' value from this file.
518    */
519   long nextUniqueID() {
520     return unique_id++;
521   }
522
523   /**
524    * Sets the unique id for this store. This must only be used under
525    * extraordinary circumstances, such as restoring from a backup, or
526    * converting from one file to another.
527    */
528   void setUniqueID(long value) {
529     unique_id = value + 1;
530   }
531
532   /**
533    * Returns the block size of this store.
534    */
535   int getBlockSize() {
536     return block_size;
537   }
538
539
540   /**
541    * Adds a number of blank index tables to the index store. For example,
542    * we may want this store to contain 16 index lists.
543    * <p>
544    * NOTE: This doesn't write the updated information to the file. You must
545    * call 'flush' to write the information to the store.
546    */
547   public synchronized void addIndexLists(int count, byte type) {
548
549     int add_size = count * (1 + 4 + 4);
550     ByteBuffer old_buffer = index_table_list;
551
552     // Create a new buffer
553 index_table_list_buf = new byte[old_buffer.limit() + add_size];
554     index_table_list = new ByteBuffer(index_table_list_buf);
555     // Put the old buffer in to the new buffer
556 old_buffer.position(0);
557     index_table_list.put(old_buffer);
558     // For each new list
559 for (int i = 0; i < count; ++i) {
560       // The type of the block
561 index_table_list.putByte(type);
562       // The number of blocks in the table list
563 index_table_list.putInt(0);
564       // The sector of statistics information (defaults to -1)
565 index_table_list.putInt(-1);
566     }
567   }
568
569   /**
570    * Adds a SnapshotIndexSet to the list of sets that this store has
571    * dispatched.
572    */
573   private synchronized void addIndexSetToList(IndexSet index_set) {
574     memory_index_set_list.add(index_set);
575   }
576
577   /**
578    * Removes a SnapshotIndexSet from the list of sets that this store
579    * is managing.
580    * <p>
581    * NOTE: This may be called by the finalizer of the IndexSet object if the
582    * index_set is not disposed.
583    */
584   private synchronized void removeIndexSetFromList(IndexSet index_set) {
585     // If the store is closed, just return.
586 if (index_set_garbage == null) {
587       return;
588     }
589
590     SnapshotIndexSet s_index_set = (SnapshotIndexSet) index_set;
591     // Remove from the set list
592 boolean b = memory_index_set_list.remove(index_set);
593     if (!b) {
594       throw new Error ("IndexSet was not in the list!");
595     }
596
597     // Add to the list of garbage if it has deleted sectors
598 if (s_index_set.hasDeletedSectors()) {
599       index_set_garbage.add(index_set);
600
601       // Do a garbage collection cycle. The lowest id that's currently open.
602 long lowest_id = -1; //Integer.MAX_VALUE;
603 if (memory_index_set_list.size() > 0) {
604         lowest_id = ((SnapshotIndexSet) memory_index_set_list.get(0)).getID();
605       }
606
607       // Delete all sectors in the garbage list that have an id lower than
608 // this.
609 boolean deleted;
610       do {
611         SnapshotIndexSet set = (SnapshotIndexSet) index_set_garbage.get(0);
612         deleted = set.getID() < lowest_id;
613         if (deleted) {
614           // The list of sectors to delete
615 IntegerVector to_delete = set.allDeletedSectors();
616
617           // For each sector to delete
618 final int sz = to_delete.size();
619           int n = 0;
620           try {
621             for (n = 0; n < sz; ++n) {
622               int sector = to_delete.intAt(n);
623               index_store.deleteSector(sector);
624             }
625
626           }
627           catch (IOException e) {
628             debug.write(Lvl.ERROR, this,
629                       "Error deleting index " + n + " of list " + to_delete);
630             debug.writeException(e);
631             throw new Error ("IO Error: " + e.getMessage());
632           }
633           index_set_garbage.remove(0);
634
635         } // if (deleted)
636
637       } while (deleted && index_set_garbage.size() > 0);
638
639     }
640
641   }
642
643   /**
644    * Returns a current snapshot of the current indexes that are committed in
645    * this store. The returned object can be used to create mutable
646    * IntegerListInterface objects. The created index lists are isolated from
647    * changes made to the rest of the indexes after this method returns.
648    * <p>
649    * A transaction must grab an IndexSet object when it opens.
650    * <p>
651    * NOTE: We MUST guarentee that the IndexSet is disposed when the
652    * transaction finishes.
653    */
654   public synchronized IndexSet getSnapshotIndexSet() {
655     // We must guarentee that we can't generate SnapshotIndexSet
656 // concurrently because it maintains its own ID key system.
657 IndexSet index_set =
658                new SnapshotIndexSet(index_table_list_buf, allocation_length);
659     addIndexSetToList(index_set);
660     return index_set;
661   }
662
663   /**
664    * Commits changes made to a snapshop of an IndexSet as being permanent
665    * changes to the state of the index store. This will generate an error if
666    * the given IndexSet is not the last set returned from the
667    * 'getSnapshotIndexSet' method.
668    * <p>
669    * For this to be used, during the transaction commit function a
670    * 'getSnapshopIndexSet' must be obtained, changes made to it from info in
671    * the journal, then a call to this method. There must be a guarentee that
672    * 'getSnapshotIndexSet' is not called again during this process.
673    * <p>
674    * NOTE: This doesn't write the updated information to the file. You must
675    * call 'flush' to write the information to the store.
676    * <p>
677    * NOTE: We must be guarenteed that when this method is called no other
678    * calls to other methods in this object can be called.
679    */
680   public synchronized void commitIndexSet(IndexSet index_set) {
681
682     // index_set must be the last in the list of memory_index_set_list
683 if (memory_index_set_list.get(memory_index_set_list.size() - 1) !=
684         index_set) {
685       throw new Error ("Can not commit IndexSet because it is not current.");
686     }
687
688     SnapshotIndexSet iset = (SnapshotIndexSet) index_set;
689
690     byte[] new_buffer = iset.commit();
691     index_table_list_buf = new_buffer;
692     index_table_list =
693         new ByteBuffer(index_table_list_buf, 0, index_table_list_buf.length);
694
695   }
696
697   /**
698    * Returns a string that contains diagnostic information.
699    */
700   public synchronized String statusString() throws IOException {
701     return index_store.statusString();
702   }
703
704
705
706
707   // ---------- Inner classes ----------
708
709   /**
710    * A unique key that is incremented each time a new IndexSet object is
711    * created.
712    */
713   private long SET_ID_KEY = 0;
714
715   /**
716    * A convenience static empty integer list array.
717    */
718   private static IndexIntegerList[] EMPTY_INTEGER_LISTS =
719                                                   new IndexIntegerList[0];
720
721
722   /**
723    * The implementation of IndexSet which represents a mutable snapshot of
724    * the indices stored in this set.
725    */
726   private class SnapshotIndexSet implements IndexSet {
727
728     /**
729      * A unique id given to this index set.
730      */
731     private long set_id;
732
733     /**
734      * A snapshot of the allocation table.
735      */
736     private ByteBuffer buf;
737
738     /**
739      * The length of the allocation table.
740      */
741     private int buf_length;
742
743     /**
744      * The list of IndexIntegerList objects that have been returned via the
745      * 'getIndex(n)' method.
746      */
747     private ArrayList integer_lists;
748
749     /**
750      * The sectors that are to be deleted when a garbage collection cycle
751      * occurs.
752      */
753     private IntegerVector deleted_sectors;
754
755
756
757     /**
758      * Constructor.
759      */
760     public SnapshotIndexSet(byte[] in_buf, int length) {
761
762       this.set_id = SET_ID_KEY;
763       ++SET_ID_KEY;
764
765       // Wrap around a new ByteBuffer but we DON'T make a copy of the byte
766 // array itself. We must be careful that the underlying byte[] array
767 // is protected from modifications (it's immutable).
768 this.buf = new ByteBuffer(in_buf);
769       this.buf_length = length;
770
771     }
772
773     /**
774      * Returns all the lists that have been created by calls to
775      * 'getIndex'
776      */
777     public IndexIntegerList[] getAllLists() {
778       if (integer_lists == null) {
779         return EMPTY_INTEGER_LISTS;
780       }
781       else {
782         return (IndexIntegerList[]) integer_lists.toArray(
783                                 new IndexIntegerList[integer_lists.size()]);
784       }
785     }
786
787     /**
788      * Returns the ByteBuffer for the snapshot of this store when it was
789      * created.
790      */
791     private ByteBuffer getByteBuffer() {
792       return buf;
793     }
794
795     /**
796      * Returns the unique id associated with this index store.
797      */
798     long getID() {
799       return set_id;
800     }
801
802     /**
803      * Returns true if this store has deleted items.
804      */
805     boolean hasDeletedSectors() {
806       return (deleted_sectors != null && deleted_sectors.size() > 0);
807     }
808
809     /**
810      * Returns the sectors that were deleted when this store committed.
811      */
812     IntegerVector allDeletedSectors() {
813       return deleted_sectors;
814     }
815
816     /**
817      * Creates a new buffer for an index store if it is committed. This
818      * also sets up the 'deleted_sectors' list which is a list of records
819      * deleted when this store commits.
820      */
821     byte[] commit() {
822
823       if (deleted_sectors != null) {
824         throw new Error ("'deleted_sectors' contains sectors to delete.");
825       }
826
827       deleted_sectors = new IntegerVector();
828
829       // Look for any indices that have changed in the IndexSet.
830 IndexIntegerList[] lists = getAllLists();
831
832       // Make all the lists immutable.
833 int sz = lists.length;
834       for (int i = 0; i < sz; ++i) {
835         lists[i].setImmutable();
836       }
837
838       // The new buffer we are making
839 ByteArrayOutputStream bout = new ByteArrayOutputStream ();
840       DataOutputStream dout = new DataOutputStream (bout);
841
842       // The original snapshot buffer
843 ByteBuffer snapshot_buf = getByteBuffer();
844
845       synchronized (snapshot_buf) {
846         int buf_size = snapshot_buf.limit();
847         snapshot_buf.position(0);
848
849         try {
850
851           int index_num = 0;
852           while (snapshot_buf.position() < buf_size) {
853             // Read the information for this block
854 byte list_type = snapshot_buf.getByte();
855             int blocks_count = snapshot_buf.getInt();
856             int stat_sector = snapshot_buf.getInt();
857             byte[] buf = new byte[blocks_count * ( 4 + 4 + 4 + 2 )];
858             snapshot_buf.get(buf, 0, buf.length);
859
860 // System.out.println("blocks_count = " + blocks_count);
861 // System.out.println("blocks_capacity = " + blocks_capacity);
862
863             // Is this index in the list of tables that changed?
864 IndexIntegerList list = null;
865             for (int i = 0; i < sz && list == null; ++i) {
866               if (lists[i].getIndexNumber() == index_num) {
867                 // Found this number
868 list = lists[i];
869               }
870             }
871
872             // We found the list in the set
873 if (list != null) {
874
875               // The blocks that were deleted (if any).
876 MappedListBlock[] deleted_blocks = list.getDeletedBlocks();
877               for (int n = 0; n < deleted_blocks.length; ++n) {
878                 // Put all deleted blocks on the list to GC
879 MappedListBlock block = (MappedListBlock) deleted_blocks[n];
880                 // Make sure the block is mapped to a sector
881 int sector = block.getIndexSector();
882                 if (sector != -1) {
883                   deleted_sectors.addInt(sector);
884                 }
885               }
886
887               // So we need to construct a new set.
888 // The blocks in the list,
889 MappedListBlock[] blocks = list.getAllBlocks();
890               blocks_count = blocks.length;
891               dout.writeByte(list_type);
892               dout.writeInt(blocks_count);
893               dout.writeInt(stat_sector);
894               // For each block
895 for (int n = 0; n < blocks_count; ++n) {
896                 MappedListBlock block = blocks[n];
897                 int bottom_int = 0;
898                 int top_int = 0;
899                 short block_size = (short) block.size();
900                 if (block_size > 0) {
901                   bottom_int = block.bottomInt();
902                   top_int = block.topInt();
903                 }
904                 int block_sector = block.getIndexSector();
905                 // Is the block new or was it changed?
906 if (block_sector == -1 || block.hasChanged()) {
907                   // If this isn't -1 then put this sector on the list of
908 // sectors to delete during GC.
909 if (block_sector != -1) {
910                     deleted_sectors.addInt(block_sector);
911                   }
912                   // This is a new block or a block that's been changed
913 // Write the block to the file system
914 block_sector = block.writeToStore();
915                 }
916                 // Write the sector
917 dout.writeInt(bottom_int);
918                 dout.writeInt(top_int);
919                 dout.writeInt(block_sector);
920                 dout.writeShort(block_size);
921               }
922
923             }
924             // We didn't find the list
925 else {
926
927               // So what we do is copy the contents of the buffer
928 dout.writeByte(list_type);
929               dout.writeInt(blocks_count);
930               dout.writeInt(stat_sector);
931               dout.write(buf, 0, buf.length);
932
933             }
934
935             ++index_num;
936           }
937
938           // Flush the stream (strictly not necessary).
939 dout.flush();
940
941         }
942         catch (IOException e) {
943           debug.writeException(e);
944           throw new Error (e.getMessage());
945         }
946
947       } // synchronized (snapshot_buf)
948
949       // The finished array
950 byte[] arr = bout.toByteArray();
951
952       // return the new buffer.
953 return arr;
954
955     }
956
957
958
959
960
961
962
963
964     // ---------- Implemented from IndexSet ----------
965
966     public IntegerListInterface getIndex(int n) {
967       int original_n = n;
968       // Synchronize 'buf' for safe access.
969 synchronized(buf) {
970
971         // Create if not exist.
972 if (integer_lists == null) {
973           integer_lists = new ArrayList ();
974         }
975         else {
976           // Assertion: If the list already contains this value throw an error.
977 for (int o = 0; o < integer_lists.size(); ++o) {
978             if (((IndexIntegerList) integer_lists.get(o)).getIndexNumber() ==
979                 original_n) {
980               throw new Error (
981                           "IntegerListInterface already created for this n.");
982             }
983           }
984         }
985
986         buf.position(0);
987         while (n > 0) {
988           byte list_type = buf.getByte(); // Ignore
989 int offset = buf.getInt();
990           int stat_sector = buf.getInt(); // Ignore
991 buf.position(buf.position() + (offset * (4 + 4 + 4 + 2)));
992           --n;
993         }
994         int list_type = buf.getByte();
995         int list_size = buf.getInt();
996         int list_stat_sector = buf.getInt();
997
998         // sector_list is an ordered list of all sectors of blocks in the index
999 // list.
1000 // Read in each sector and construct a MappedListBlock for each one.
1001 MappedListBlock[] list_blocks = new MappedListBlock[list_size];
1002
1003        for (int i = 0; i < list_size; ++i) {
1004          int first_entry = buf.getInt();
1005          int last_entry = buf.getInt();
1006          int block_sector = buf.getInt();
1007          short block_size = buf.getShort();
1008
1009          list_blocks[i] = new MappedListBlock(
1010                          first_entry, last_entry, block_sector, block_size);
1011
1012        }
1013
1014        // Create and return the mapped index integer list.
1015 IndexIntegerList ilist = new IndexIntegerList(original_n, list_blocks);
1016        integer_lists.add(ilist);
1017        return ilist;
1018
1019      } // synchronized(buf)
1020
1021    }
1022
1023    public void dispose() {
1024      // Dispose all the integer lists created by this object.
1025 synchronized (buf) {
1026        if (integer_lists != null) {
1027          for (int i = 0; i < integer_lists.size(); ++i) {
1028            IndexIntegerList ilist = (IndexIntegerList) integer_lists.get(i);
1029            ilist.dispose();
1030          }
1031          integer_lists = null;
1032        }
1033      }
1034      buf = null;
1035      removeIndexSetFromList(this);
1036    }
1037
1038    public void finalize() {
1039      if (buf != null) {
1040        debug.write(Lvl.WARNING, this, "IndexStore was not disposed!");
1041        // We remove it manually from the index set list
1042 removeIndexSetFromList(this);
1043// debug.writeException(DEBUG_CONSTRUCTOR);
1044 }
1045    }
1046
1047  }
1048
1049  /**
1050   * An IntegerListBlockInterface implementation that maps a block of a list
1051   * to an underlying file system representation.
1052   */
1053  private final class MappedListBlock extends IntArrayListBlock {
1054
1055    /**
1056     * The first entry in the block.
1057     */
1058    private int first_entry;
1059
1060    /**
1061     * The last entry in the block.
1062     */
1063    private int last_entry;
1064
1065    /**
1066     * The sector in the index file that this block can be found.
1067     */
1068    private int index_sector;
1069
1070    /**
1071     * Lock object.
1072     */
1073    private Object lock = new Object ();
1074
1075    /**
1076     * Set to true if the loaded block is mutable.
1077     */
1078    private boolean mutable_block;
1079
1080    /**
1081     * Constructor.
1082     */
1083    public MappedListBlock(int first_int, int last_int,
1084                           int mapped_sector, int size) {
1085      this.first_entry = first_int;
1086      this.last_entry = last_int;
1087      this.index_sector = mapped_sector;
1088      count = size;
1089      array = null;
1090    }
1091
1092    /**
1093     * Creates an empty block.
1094     */
1095    public MappedListBlock(int block_size_in) {
1096      super(block_size_in);
1097      this.index_sector = -1;
1098    }
1099
1100    /**
1101     * Returns the sector in the file of this block.
1102     */
1103    public int getIndexSector() {
1104      return index_sector;
1105    }
1106
1107    /**
1108     * Writes this block to a new sector in the index file and updates the
1109     * information in this object accordingly.
1110     * <p>
1111     * Returns the sector the block was written to.
1112     */
1113    public int writeToStore() throws IOException {
1114      // Convert the int[] array to a byte[] array.
1115 int block_count = block_size;
1116      byte[] arr = new byte[block_count * 4];
1117      int p = 0;
1118      for (int i = 0; i < block_count; ++i) {
1119        int v = array[i];
1120        ByteArrayUtil.setInt(v, arr, p);
1121        p += 4;
1122      }
1123
1124      // Write the sector to the store
1125 synchronized (IndexStore.this) {
1126        index_sector = index_store.addSector(arr, 0, arr.length);
1127      }
1128
1129      // Write this sector to the cache
1130 synchronized (sector_cache) {
1131        sector_cache.put(new Integer (index_sector), array);
1132      }
1133
1134      // Once written, the block is invalidated
1135 lock = null;
1136
1137      return index_sector;
1138    }
1139
1140    /**
1141     * Overwritten from IntArrayListBlock, this returns the int[] array that
1142     * contains the contents of the block. In this implementation, we
1143     * determine if the array has been read from the index file. If it
1144     * hasn't we read it in, otherwise we use the version in memory.
1145     */
1146    public int[] getArray(boolean immutable) {
1147      // We must synchronize this entire block because otherwise we could
1148 // return a partially loaded array.
1149 synchronized (lock) {
1150
1151        if (array != null) {
1152          prepareMutate(immutable);
1153          return array;
1154        }
1155
1156        // Pull this from a cache
1157 Object elem;
1158        synchronized (sector_cache) {
1159          elem = sector_cache.get(new Integer (index_sector));
1160        }
1161        if (elem != null) {
1162          array = (int[]) elem;
1163          mutable_block = false;
1164          prepareMutate(immutable);
1165          return array;
1166        }
1167
1168        int block_count = block_size;
1169        // Read the sector from the index file.
1170 array = new int[block_count];
1171        synchronized (IndexStore.this) {
1172          try {
1173            array = index_store.getSectorAsIntArray(index_sector, array);
1174          }
1175          catch (IOException e) {
1176            debug.writeException(e);
1177            throw new Error ("IO Error: " + e.getMessage());
1178          }
1179        }
1180        // Put in the cache
1181 synchronized (sector_cache) {
1182          sector_cache.put(new Integer (index_sector), (int[]) array);
1183        }
1184        mutable_block = false;
1185        prepareMutate(immutable);
1186        return array;
1187
1188      }
1189
1190    }
1191
1192    /**
1193     * Overwritten from IntArrayListBlock, returns the capacity of the block.
1194     */
1195    public int getArrayLength() {
1196      return block_size;
1197    }
1198
1199    /**
1200     * Makes the block mutable if it is immutable. We must be synchronized on
1201     * 'lock' before this method is called.
1202     */
1203    private void prepareMutate(boolean immutable) {
1204      // If list is to be mutable
1205 if (!immutable && !mutable_block) {
1206        array = (int[]) array.clone();
1207        mutable_block = true;
1208      }
1209    }
1210
1211    /**
1212     * Overwritten from IntArrayListBlock, returns the last entry of the block.
1213     */
1214    public int topInt() {
1215      if (count == 0) {
1216        throw new Error ("No first int in block.");
1217      }
1218
1219      synchronized (lock) {
1220        if (array == null) {
1221          return last_entry;
1222        }
1223        else {
1224          return array[count - 1];
1225        }
1226      }
1227    }
1228
1229    /**
1230     * Overwritten from IntArrayListBlock, returns the first entry of the
1231     * block.
1232     */
1233    public int bottomInt() {
1234      if (count == 0) {
1235        throw new Error ("No first int in block.");
1236      }
1237
1238      synchronized (lock) {
1239        if (array == null) {
1240          return first_entry;
1241        }
1242        else {
1243          return array[0];
1244        }
1245      }
1246    }
1247
1248  }
1249
1250  /**
1251   * The IntegerListInterface implementation that is used to represent a
1252   * mutable snapshop of the indices at a given point in time.
1253   */
1254  private final class IndexIntegerList extends AbstractBlockIntegerList {
1255
1256    /**
1257     * The number of the index in the store that this list represents.
1258     */
1259    private int index_num;
1260
1261    /**
1262     * Set to true when disposed.
1263     */
1264    private boolean disposed = false;
1265
1266    /**
1267     * The mapped elements that were deleted.
1268     */
1269    private ArrayList deleted_blocks = new ArrayList ();
1270
1271
1272    /**
1273     * Constructs the list with the given set of blocks.
1274     */
1275    public IndexIntegerList(int index_num, MappedListBlock[] blocks) {
1276      super(blocks);
1277      this.index_num = index_num;
1278    }
1279
1280    /**
1281     * Creates a new block for the list.
1282     */
1283    protected IntegerListBlockInterface newListBlock() {
1284      if (!disposed) {
1285        return new MappedListBlock(block_size);
1286      }
1287      throw new Error ("Integer list has been disposed.");
1288    }
1289
1290    /**
1291     * We must maintain a list of deleted blocks.
1292     */
1293    protected void deleteListBlock(IntegerListBlockInterface list_block) {
1294      deleted_blocks.add(list_block);
1295    }
1296
1297    /**
1298     * Returns the index number of this list.
1299     */
1300    public int getIndexNumber() {
1301      return index_num;
1302    }
1303
1304    /**
1305     * Returns the array of all MappedListBlock that are in this list.
1306     */
1307    public MappedListBlock[] getAllBlocks() {
1308      return (MappedListBlock[])
1309                 block_list.toArray(new MappedListBlock[block_list.size()]);
1310    }
1311
1312    /**
1313     * Returns the array of all MappedListBlock that were deleted from this
1314     * list.
1315     */
1316    public MappedListBlock[] getDeletedBlocks() {
1317      return (MappedListBlock[])
1318         deleted_blocks.toArray(new MappedListBlock[deleted_blocks.size()]);
1319    }
1320
1321
1322    public void dispose() {
1323      disposed = true;
1324      block_list = null;
1325    }
1326
1327  }
1328
1329}
1330

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags