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


1 /**
2  * com.mckoi.database.IndexSetStore 03 Sep 2002
3  *
4  * Mckoi SQL Database ( http://www.mckoi.com/database )
5  * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * Version 2 as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License Version 2 for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * Version 2 along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Change Log:
21  *
22  *
23  */
24
25 package com.mckoi.database;
26
27 import java.io.IOException ;
28 import java.io.OutputStream ;
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.IntegerVector;
39 import com.mckoi.util.UserTerminal;
40 import com.mckoi.util.Cache;
41 import com.mckoi.store.Store;
42 import com.mckoi.store.Area;
43 import com.mckoi.store.MutableArea;
44 import com.mckoi.store.AreaWriter;
45 import com.mckoi.debug.*;
46
47 /**
48  * A class that manages the storage of a set of transactional index lists in a
49  * way that is fast to modify. This class has a number of objectives;
50  * <p>
51  * <ul>
52  * <li>To prevent corruption as best as possible.</li>
53  * <li>To be able to modify lists of integers very fast and persistantly.</li>
54  * <li>To have size optimization features such as defragmentation.</li>
55  * <li>To provide very fast searches on sorted lists (caching features).</li>
56  * <li>To be able to map a list to an IntegerListInterface interface.</li>
57  * </ul>
58  * <p>
59  * This object uses a com.mckoi.store.Store instance as its backing medium.
60  * <p>
61  * This store manages three types of areas; 'Index header', 'Index block' and
62  * 'Index element'.
63  * <p>
64  * Index header: This area type contains an entry for each index being stored.
65  * The Index header contains a pointer to an 'Index block' area for each index.
66  * The pointer to the 'Index block' in this area changes whenever an index
67  * changes, or when new indexes are added or deleted from the store.
68  * <p>
69  * Index block: This area contains a number of pointers to Index element blocks.
70  * The number of entries depends on the number of indices in the list. Each
71  * entry contains the size of the block, the first and last entry of the block,
72  * and a pointer to the element block itself. If an element of the index
73  * changes or elements are removed or deleted, this block does NOT change.
74  * This should be considered an immutable area.
75  * <p>
76  * Index element: This area simply contains the actual values in a block of the
77  * index. An Index element area does not change and should be considered an
78  * immutable area.
79  *
80  * @author Tobias Downer
81  */
82
83 final class IndexSetStore {
84
85   /**
86    * The magic value that we use to mark the start area.
87    */
88   private static final int MAGIC = 0x0CA90291;
89   
90   
91   /**
92    * A DebugLogger object used to log debug messages to.
93    */
94   private final DebugLogger debug;
95
96   /**
97    * The TransactionSystem for this index set.
98    */
99   private final TransactionSystem system;
100   
101   /**
102    * The Store that contains all the data of the index store.
103    */
104   private Store store;
105
106   /**
107    * The starting header of this index set. This is a very small area that
108    * simply contains a magic value and a pointer to the index header. This
109    * is the only MutableArea object that is required by the index set.
110    */
111   private MutableArea start_area;
112   
113   /**
114    * The index header area. The index header area contains an entry for each
115    * index being stored. Each entry is 16 bytes in size and has a 16 byte
116    * header.
117    * <p>
118    * HEADER: ( version (int), reserved (int), index count (long) ) <br>
119    * ENTRY: ( type (int), block_size (int), index block pointer (long) )
120    */
121   private long index_header_p;
122   private Area index_header_area;
123   
124   /**
125    * The index blocks - one for each index being stored. An index block area
126    * contains an entry for each index element in an index. Each entry is 28
127    * bytes in size and the area has a 16 byte header.
128    * <p>
129    * HEADER: ( version (int), reserved (int), index size (long) ) <br>
130    * ENTRY: ( first entry (long), last entry (long),
131    * index element pointer (long), type/element size (int) )
132    * <p>
133    * type/element size contains the number of elements in the block, and the
134    * block compaction factor. For example, type 1 means the block contains
135    * short sized index values, 2 is int sized index values, and 3 is long
136    * sized index values.
137    */
138   private IndexBlock[] index_blocks;
139
140   
141
142   /**
143    * Constructs the IndexSetStore over the given Store object.
144    */
145   public IndexSetStore(Store store, final TransactionSystem system) {
146     this.store = store;
147     this.system = system;
148     this.debug = system.Debug();
149   }
150
151
152   /**
153    * Delete all areas specified in the list (as a list of Long).
154    */
155   private synchronized void deleteAllAreas(ArrayList list) {
156
157     if (store != null) {
158
159       try {
160         store.lockForWrite();
161
162         int sz = list.size();
163         for (int i = 0; i < sz; ++i) {
164           long id = ((Long ) list.get(i)).longValue();
165           store.deleteArea(id);
166         }
167
168       }
169       catch (IOException e) {
170         debug.write(Lvl.ERROR, this, "Error when freeing old index block.");
171         debug.writeException(e);
172       }
173       finally {
174         store.unlockForWrite();
175       }
176
177     }
178   }
179   
180   
181   // ---------- Private methods ----------
182
183   /**
184    * Creates a new blank index block in the store and returns a pointer to the
185    * area.
186    */
187   private long createBlankIndexBlock() throws IOException {
188     // Allocate the area
189 AreaWriter a = store.createArea(16);
190     long index_block_p = a.getID();
191     // Setup the header
192 a.putInt(1); // version
193 a.putInt(0); // reserved
194 a.putLong(0); // block entries
195 a.finish();
196
197     return index_block_p;
198   }
199
200   // ---------- Public methods ----------
201
202   /**
203    * Creates a new black index set store and returns a pointer to a static
204    * area that is later used to reference this index set in this store.
205    * Remember to synch after this is called.
206    */
207   public synchronized long create() throws IOException {
208
209     // Create an empty index header area
210 AreaWriter a = store.createArea(16);
211     index_header_p = a.getID();
212     a.putInt(1); // version
213 a.putInt(0); // reserved
214 a.putLong(0); // number of indexes in the set
215 a.finish();
216
217     // Set up the local Area object for the index header
218 index_header_area = store.getArea(index_header_p);
219
220     index_blocks = new IndexBlock[0];
221
222     // Allocate the starting header
223 AreaWriter start_a = store.createArea(32);
224     long start_p = start_a.getID();
225     // The magic
226 start_a.putInt(MAGIC);
227     // The version
228 start_a.putInt(1);
229     // Pointer to the index header
230 start_a.putLong(index_header_p);
231     start_a.finish();
232
233     // Set the 'start_area' value.
234 start_area = store.getMutableArea(start_p);
235
236     return start_p;
237   }
238
239   /**
240    * Initializes this index set. This must be called during general
241    * initialization of the table object.
242    */
243   public synchronized void init(long start_p) throws IOException {
244
245     // Set up the start area
246 start_area = store.getMutableArea(start_p);
247
248     int magic = start_area.getInt();
249     if (magic != MAGIC) {
250       throw new IOException ("Magic value for index set does not match.");
251     }
252     int version = start_area.getInt();
253     if (version != 1) {
254       throw new IOException ("Unknown version for index set.");
255     }
256
257     // Setup the index_header area
258 index_header_p = start_area.getLong();
259     index_header_area = store.getArea(index_header_p);
260     
261     // Read the index header area
262 version = index_header_area.getInt(); // version
263 if (version != 1) {
264       throw new IOException ("Incorrect version");
265     }
266     int reserved = index_header_area.getInt(); // reserved
267 int index_count = (int) index_header_area.getLong();
268     index_blocks = new IndexBlock[index_count];
269
270     // Initialize each index block
271 for (int i = 0; i < index_count; ++i) {
272       int type = index_header_area.getInt();
273       int block_size = index_header_area.getInt();
274       long index_block_p = index_header_area.getLong();
275       if (type == 1) {
276         index_blocks[i] = new IndexBlock(i, block_size, index_block_p);
277         index_blocks[i].addReference();
278       }
279       else {
280         throw new IOException ("Do not understand index type: " + type);
281       }
282     }
283
284   }
285
286   /**
287    * Closes this index set (cleans up).
288    */
289   public synchronized void close() {
290     if (store != null) {
291       for (int i = 0; i < index_blocks.length; ++i) {
292         index_blocks[i].removeReference();
293       }
294       store = null;
295       index_blocks = null;
296     }
297   }
298
299   /**
300    * Overwrites all existing index information in this store and sets it to a
301    * copy of the given IndexSet object. The 'source_index' must be a snapshot
302    * as returned by the getSnapshotIndexSet method but not necessarily
303    * generated from this index set.
304    * <p>
305    * This will create a new structure within this store that contains the copied
306    * index data. This overwrites any existing data in this store so care should
307    * be used when using this method.
308    * <p>
309    * This method is an optimized method of copying all the index data in an
310    * index set and only requires a small buffer in memory. The index data
311    * in 'index_set' is not altered in any way by using this.
312    */
313   public synchronized void copyAllFrom(IndexSet index_set) throws IOException {
314
315     // Assert that IndexSetStore is initialized
316 if (index_blocks == null) {
317       throw new RuntimeException (
318                   "Can't copy because this IndexSetStore is not initialized.");
319     }
320
321     // Drop any indexes in this index store.
322 for (int i = 0; i < index_blocks.length; ++i) {
323       commitDropIndex(i);
324     }
325
326     if (index_set instanceof SnapshotIndexSet) {
327       // Cast to SnapshotIndexSet
328 SnapshotIndexSet s_index_set = (SnapshotIndexSet) index_set;
329
330       // The number of IndexBlock items to copy.
331 int index_count = s_index_set.snapshot_index_blocks.length;
332     
333       // Record the old index_header_p
334 long old_index_header_p = index_header_p;
335     
336       // Create the header in this store
337 AreaWriter a = store.createArea(16 + (16 * index_count));
338       index_header_p = a.getID();
339       a.putInt(1); // version
340 a.putInt(0); // reserved
341 a.putLong(index_count); // number of indexes in the set
342
343       // Fill in the information from the index_set
344 for (int i = 0; i < index_count; ++i) {
345         IndexBlock source_block = s_index_set.snapshot_index_blocks[i];
346
347         long index_block_p = source_block.copyTo(store);
348
349         a.putInt(1); // NOTE: Only support for block type 1
350 a.putInt(source_block.getBlockSize());
351         a.putLong(index_block_p);
352       }
353
354       // The header area has now been initialized.
355 a.finish();
356       
357       // Modify the start area header to point to this new structure.
358 start_area.position(8);
359       start_area.putLong(index_header_p);
360       // Check out the change
361 start_area.checkOut();
362
363       // Free space associated with the old header_p
364 store.deleteArea(old_index_header_p);
365     }
366     else {
367       throw new RuntimeException ("Can not copy non-IndexSetStore IndexSet");
368     }
369
370     // Re-initialize the index
371 init(start_area.getID());
372   }
373   
374   /**
375    * Adds to the given ArrayList all the areas in the store that are used by
376    * this structure (as Long).
377    */
378   public void addAllAreasUsed(ArrayList list) throws IOException {
379     list.add(new Long (start_area.getID()));
380     list.add(new Long (index_header_p));
381     for (int i = 0; i < index_blocks.length; ++i) {
382       IndexBlock block = index_blocks[i];
383       list.add(new Long (block.getPointer()));
384       long[] block_pointers = block.getAllBlockPointers();
385       for (int n = 0; n < block_pointers.length; ++n) {
386         list.add(new Long (block_pointers[n]));
387       }
388     }
389   }
390   
391   /**
392    * Adds a number of blank index tables to the index store. For example,
393    * we may want this store to contain 16 index lists.
394    * <p>
395    * NOTE: This doesn't write the updated information to the file. You must
396    * call 'flush' to write the information to the store.
397    */
398   public synchronized void addIndexLists(int count, int type, int block_size)
399                                                            throws IOException {
400
401     try {
402       store.lockForWrite();
403
404       // Allocate a new area for the list
405 int new_size = 16 + ((index_blocks.length + count) * 16);
406       AreaWriter new_index_area = store.createArea(new_size);
407       long new_index_p = new_index_area.getID();
408       IndexBlock[] new_index_blocks =
409                                 new IndexBlock[(index_blocks.length + count)];
410     
411       // Copy the existing area
412 index_header_area.position(0);
413       int version = index_header_area.getInt();
414       int reserved = index_header_area.getInt();
415       long icount = index_header_area.getLong();
416       new_index_area.putInt(version);
417       new_index_area.putInt(reserved);
418       new_index_area.putLong(icount + count);
419     
420       for (int i = 0; i < index_blocks.length; ++i) {
421         int itype = index_header_area.getInt();
422         int iblock_size = index_header_area.getInt();
423         long index_block_p = index_header_area.getLong();
424       
425         new_index_area.putInt(itype);
426         new_index_area.putInt(iblock_size);
427         new_index_area.putLong(index_block_p);
428       
429         new_index_blocks[i] = index_blocks[i];
430       }
431
432       // Add the new entries
433 for (int i = 0; i < count; ++i) {
434         long new_blank_block_p = createBlankIndexBlock();
435         
436         new_index_area.putInt(type);
437         new_index_area.putInt(block_size);
438         new_index_area.putLong(new_blank_block_p);
439         
440         IndexBlock i_block = new IndexBlock(index_blocks.length + i,
441                                             block_size, new_blank_block_p);
442         i_block.addReference();
443         new_index_blocks[index_blocks.length + i] = i_block;
444                     
445       }
446   
447       // Finished initializing the index.
448 new_index_area.finish();
449       
450       // The old index header pointer
451 long old_index_header_p = index_header_p;
452       
453       // Update the state of this object,
454 index_header_p = new_index_p;
455       index_header_area = store.getArea(new_index_p);
456       index_blocks = new_index_blocks;
457       
458       // Update the start pointer
459 start_area.position(8);
460       start_area.putLong(new_index_p);
461       start_area.checkOut();
462   
463       // Free the old header
464 store.deleteArea(old_index_header_p);
465
466     }
467     finally {
468       store.unlockForWrite();
469     }
470     
471   }
472
473   /**
474    * Returns a current snapshot of the current indexes that are committed in
475    * this store. The returned object can be used to create mutable
476    * IntegerListInterface objects. The created index lists are isolated from
477    * changes made to the rest of the indexes after this method returns.
478    * <p>
479    * A transaction must grab an IndexSet object when it opens.
480    * <p>
481    * NOTE: We MUST guarentee that the IndexSet is disposed when the
482    * transaction finishes.
483    */
484   public synchronized IndexSet getSnapshotIndexSet() {
485     // Clone the blocks list. This represents the current snapshot of the
486 // index state.
487 IndexBlock[] snapshot_index_blocks = (IndexBlock[]) index_blocks.clone();
488
489     // Add this as the reference
490 for (int i = 0; i < snapshot_index_blocks.length; ++i) {
491       snapshot_index_blocks[i].addReference();
492     }
493
494     return new SnapshotIndexSet(snapshot_index_blocks);
495   }
496
497   /**
498    * Commits the index header with the current values set in 'index_blocks'.
499    */
500   private synchronized void commitIndexHeader() throws IOException {
501     
502     // Make a new index header area for the changed set.
503 AreaWriter a = store.createArea(16 + (index_blocks.length * 16));
504     long a_p = a.getID();
505
506     a.putInt(1); // version
507 a.putInt(0); // reserved
508 a.putLong(index_blocks.length); // count
509
510     for (int i = 0; i < index_blocks.length; ++i) {
511       IndexBlock ind_block = index_blocks[i];
512       a.putInt(1);
513       a.putInt(ind_block.getBlockSize());
514       a.putLong(ind_block.getPointer());
515     }
516
517     // Finish creating the updated header
518 a.finish();
519   
520     // The old index header pointer
521 long old_index_header_p = index_header_p;
522   
523     // Set the new index header
524 index_header_p = a_p;
525     index_header_area = store.getArea(index_header_p);
526   
527     // Write the change to 'start_p'
528 start_area.position(8);
529     start_area.putLong(index_header_p);
530     start_area.checkOut();
531
532     // Free the old header index
533 store.deleteArea(old_index_header_p);
534
535   }
536   
537   /**
538    * Commits changes made to a snapshop of an IndexSet as being permanent
539    * changes to the state of the index store. This will generate an error if
540    * the given IndexSet is not the last set returned from the
541    * 'getSnapshotIndexSet' method.
542    * <p>
543    * For this to be used, during the transaction commit function a
544    * 'getSnapshopIndexSet' must be obtained, changes made to it from info in
545    * the journal, then a call to this method. There must be a guarentee that
546    * 'getSnapshotIndexSet' is not called again during this process.
547    * <p>
548    * NOTE: We must be guarenteed that when this method is called no other
549    * calls to other methods in this object can be called.
550    */
551   public void commitIndexSet(IndexSet index_set) {
552
553     ArrayList removed_blocks = new ArrayList ();
554
555     synchronized(this) {
556
557       SnapshotIndexSet s_index_set = (SnapshotIndexSet) index_set;
558       IndexIntegerList[] lists = s_index_set.getAllLists();
559
560       try {
561
562         try {
563           store.lockForWrite();
564
565           // For each IndexIntegerList in the index set,
566 for (int n = 0; n < lists.length; ++n) {
567             // Get the list
568 IndexIntegerList list = (IndexIntegerList) lists[n];
569             int index_num = list.getIndexNumber();
570             // The IndexBlock we are changing
571 IndexBlock cur_index_block = index_blocks[index_num];
572             // Get all the blocks in the list
573 MappedListBlock[] blocks = list.getAllBlocks();
574
575             // Make up a new block list for this index set.
576 AreaWriter a = store.createArea(16 + (blocks.length * 28));
577             long block_p = a.getID();
578             a.putInt(1); // version
579 a.putInt(0); // reserved
580 a.putLong(blocks.length); // block count
581 for (int i = 0; i < blocks.length; ++i) {
582               MappedListBlock b = blocks[i];
583
584               long bottom_int = 0;
585               long top_int = 0;
586               int block_size = b.size();
587               if (block_size > 0) {
588                 bottom_int = b.bottomInt();
589                 top_int = b.topInt();
590               }
591               long b_p = b.getBlockPointer();
592               // Is the block new or was it changed?
593 if (b_p == -1 || b.hasChanged()) {
594                 // If this isn't -1 then put this sector on the list of
595 // sectors to delete during GC.
596 if (b_p != -1) {
597                   cur_index_block.addDeletedArea(b_p);
598                 }
599                 // This is a new block or a block that's been changed
600 // Write the block to the file system
601 b_p = b.writeToStore();
602               }
603               a.putLong(bottom_int);
604               a.putLong(top_int);
605               a.putLong(b_p);
606               a.putInt(block_size | (((int) b.getCompactType()) << 24));
607
608             }
609
610             // Finish initializing the area
611 a.finish();
612
613             // Add the deleted blocks
614 MappedListBlock[] deleted_blocks = list.getDeletedBlocks();
615             for (int i = 0; i < deleted_blocks.length; ++i) {
616               long del_block_p = deleted_blocks[i].getBlockPointer();
617               if (del_block_p != -1) {
618                 cur_index_block.addDeletedArea(del_block_p);
619               }
620             }
621
622             // Mark the current block as deleted
623 cur_index_block.markAsDeleted();
624
625             // Now create a new IndexBlock object
626 IndexBlock new_index_block =
627                new IndexBlock(index_num, cur_index_block.getBlockSize(), block_p);
628             new_index_block.setParentIndexBlock(cur_index_block);
629
630             // Add reference to the new one
631 new_index_block.addReference();
632             // Update the index_blocks list
633 index_blocks[index_num] = new_index_block;
634
635             // We remove this later.
636 removed_blocks.add(cur_index_block);
637
638           }
639
640           // Commit the new index header (index_blocks)
641 commitIndexHeader();
642
643         }
644         finally {
645           store.unlockForWrite();
646         }
647
648         // Commit finished.
649
650       }
651       catch (IOException e) {
652         debug.writeException(e);
653         throw new Error ("IO Error: " + e.getMessage());
654       }
655
656     } // synchronized
657
658     // Remove all the references for the changed blocks,
659 int sz = removed_blocks.size();
660     for (int i = 0; i < sz; ++i) {
661       IndexBlock block = (IndexBlock) removed_blocks.get(i);
662       block.removeReference();
663     }
664
665   }
666
667   /**
668    * Commits a change that drops an index from the index set. This must be
669    * called from within the conglomerate commit. The actual implementation of
670    * this overwrites the index with with a 0 length index. This is also useful
671    * if you want to reindex a column.
672    */
673   public synchronized void commitDropIndex(int index_num) throws IOException {
674     // The IndexBlock we are dropping
675 IndexBlock cur_index_block = index_blocks[index_num];
676     int block_size = cur_index_block.getBlockSize();
677
678     try {
679       store.lockForWrite();
680     
681       // Add all the elements to the deleted areas in the block
682 long[] all_block_pointers = cur_index_block.getAllBlockPointers();
683       for (int i = 0; i < all_block_pointers.length; ++i) {
684         cur_index_block.addDeletedArea(all_block_pointers[i]);
685       }
686
687       // Mark the current block as deleted
688 cur_index_block.markAsDeleted();
689
690       // Make up a new blank block list for this index set.
691 long block_p = createBlankIndexBlock();
692     
693       // Now create a new IndexBlock object
694 IndexBlock new_index_block = new IndexBlock(index_num, block_size, block_p);
695              
696       // Add reference to the new one
697 new_index_block.addReference();
698       // Remove reference to the old
699 cur_index_block.removeReference();
700       // Update the index_blocks list
701 index_blocks[index_num] = new_index_block;
702
703       // Commit the new index header (index_blocks)
704 commitIndexHeader();
705
706     }
707     finally {
708       store.unlockForWrite();
709     }
710
711   }
712
713
714
715
716   // ---------- Inner classes ----------
717
718
719   /**
720    * A convenience static empty integer list array.
721    */
722   private static IndexIntegerList[] EMPTY_INTEGER_LISTS =
723                                                   new IndexIntegerList[0];
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738   /**
739    * The implementation of IndexSet which represents a mutable snapshot of
740    * the indices stored in this set.
741    */
742   private class SnapshotIndexSet implements IndexSet {
743
744     /**
745      * The list of IndexBlock object that represent the view of the index set
746      * when the view was created.
747      */
748     private IndexBlock[] snapshot_index_blocks;
749
750     /**
751      * The list of IndexIntegerList objects that have been returned via the
752      * 'getIndex(n)' method.
753      */
754     private ArrayList integer_lists;
755
756     /**
757      * Set to true when this object is disposed.
758      */
759     private boolean disposed;
760
761
762     /**
763      * Constructor.
764      */
765     public SnapshotIndexSet(IndexBlock[] blocks) {
766
767       this.snapshot_index_blocks = blocks;
768
769       // Not disposed.
770 disposed = false;
771
772     }
773
774     /**
775      * Returns all the lists that have been created by calls to
776      * 'getIndex'
777      */
778     public IndexIntegerList[] getAllLists() {
779       if (integer_lists == null) {
780         return EMPTY_INTEGER_LISTS;
781       }
782       else {
783         return (IndexIntegerList[]) integer_lists.toArray(
784                                 new IndexIntegerList[integer_lists.size()]);
785       }
786     }
787     
788     // ---------- Implemented from IndexSet ----------
789
790     public IntegerListInterface getIndex(int n) {
791       // Create if not exist.
792 if (integer_lists == null) {
793         integer_lists = new ArrayList ();
794       }
795       else {
796         // If this list has already been created, return it
797 for (int o = 0; o < integer_lists.size(); ++o) {
798           IndexIntegerList i_list = (IndexIntegerList) integer_lists.get(o);
799           if (i_list.getIndexNumber() == n) {
800             return i_list;
801 // throw new Error(
802 // "IntegerListInterface already created for this n.");
803 }
804         }
805       }
806
807       try {
808
809         IndexIntegerList ilist =
810                            snapshot_index_blocks[n].createIndexIntegerList();
811         integer_lists.add(ilist);
812         return ilist;
813
814       }
815       catch (IOException e) {
816         debug.writeException(e);
817         throw new RuntimeException ("IO Error: " + e.getMessage());
818       }
819
820     }
821     
822     public void dispose() {
823       if (!disposed) {
824         
825         if (integer_lists != null) {
826           for (int i = 0; i < integer_lists.size(); ++i) {
827             IndexIntegerList ilist = (IndexIntegerList) integer_lists.get(i);
828             ilist.dispose();
829           }
830           integer_lists = null;
831         }
832
833         // Release reference to the index_blocks;
834 for (int i = 0; i < snapshot_index_blocks.length; ++i) {
835           IndexBlock iblock = snapshot_index_blocks[i];
836           iblock.removeReference();
837         }
838         snapshot_index_blocks = null;
839
840         disposed = true;
841       }
842     }
843
844     public void finalize() {
845       try {
846         if (!disposed) {
847           dispose();
848         }
849       }
850       catch (Throwable e) {
851         debug.write(Lvl.ERROR, this, "Finalize error: " + e.getMessage());
852         debug.writeException(e);
853       }
854     }
855
856   }
857
858   /**
859    * An IntegerListBlockInterface implementation that maps a block of a list
860    * to an underlying file system representation.
861    */
862   private final class MappedListBlock extends IntArrayListBlock {
863
864     /**
865      * The first entry in the block.
866      */
867     private long first_entry;
868
869     /**
870      * The last entry in the block.
871      */
872     private long last_entry;
873
874     /**
875      * A pointer to the area where this block can be found.
876      */
877     private long block_p;
878
879     /**
880      * Lock object.
881      */
882     private Object lock = new Object ();
883
884     /**
885      * Set to true if the loaded block is mutable.
886      */
887     private boolean mutable_block;
888
889     /**
890      * How this block is compacted in the store. If this is 1 the elements are
891      * stored as shorts, if it is 2 - ints, and if it is 3 - longs.
892      */
893     private byte compact_type;
894
895     /**
896      * The maximum size of the block.
897      */
898     private final int max_block_size;
899     
900     /**
901      * Constructor.
902      */
903     public MappedListBlock(long first_e, long last_e,
904                            long mapped_p, int size, byte compact_type,
905                            int max_block_size) {
906       this.first_entry = first_e;
907       this.last_entry = last_e;
908       this.block_p = mapped_p;
909       this.compact_type = compact_type;
910       this.max_block_size = max_block_size;
911       count = size;
912       array = null;
913     }
914
915     /**
916      * Creates an empty block.
917      */
918     public MappedListBlock(int block_size_in) {
919       super(block_size_in);
920       this.block_p = -1;
921       this.max_block_size = block_size_in;
922     }
923
924     /**
925      * Returns a pointer to the area that contains this block.
926      */
927     public long getBlockPointer() {
928       return block_p;
929     }
930
931     /**
932      * Returns the compact type of this block.
933      */
934     public byte getCompactType() {
935       return compact_type;
936     }
937
938     /**
939      * Copies the index data in this block to a new block in the given store
940      * and returns a pointer to the new block.
941      */
942     public long copyTo(Store dest_store) throws IOException {
943       // The number of bytes per entry
944 int entry_size = compact_type;
945       // The total size of the entry.
946 int area_size = (count * entry_size);
947
948       // Allocate the destination area
949 AreaWriter dest = dest_store.createArea(area_size);
950       long dest_block_p = dest.getID();
951       store.getArea(block_p).copyTo(dest, area_size);
952       dest.finish();
953       
954       return dest_block_p;
955     }
956
957     /**
958      * Writes this block to a new sector in the index file and updates the
959      * information in this object accordingly.
960      * <p>
961      * Returns the sector the block was written to.
962      */
963     public long writeToStore() throws IOException {
964       // Convert the int[] array to a byte[] array.
965
966       // First determine how we compact this int array into a byte array. If
967 // all the values are < 32768 then we store as shorts
968 long largest_val = 0;
969       for (int i = 0; i < count; ++i) {
970         long v = (long) array[i];
971         if (Math.abs(v) > Math.abs(largest_val)) {
972           largest_val = v;
973         }
974       }
975       
976       long lv = largest_val;
977       if (lv >> 7 == 0 || lv >> 7 == -1) {
978         compact_type = 1;
979       }
980       else if (lv >> 15 == 0 || lv >> 15 == -1) {
981         compact_type = 2;
982       }
983       else if (lv >> 23 == 0 || lv >> 23 == -1) {
984         compact_type = 3;
985       }
986       // NOTE: in the future we'll want to determine if we are going to store
987 // as an int or long array.
988 else {
989         compact_type = 4;
990       }
991
992       // The number of bytes per entry
993 int entry_size = compact_type;
994       // The total size of the entry.
995 int area_size = (count * entry_size);
996
997       // Allocate an array to buffer the block to
998 byte[] arr = new byte[area_size];
999       // Fill the array
1000 int p = 0;
1001      for (int i = 0; i < count; ++i) {
1002        int v = array[i];
1003        for (int n = entry_size - 1; n >= 0; --n) {
1004          arr[p] = (byte) ((v >>> (n * 8)) & 0x0FF);
1005          ++p;
1006        }
1007      }
1008      
1009      // Create an area to store this
1010 AreaWriter a = store.createArea(area_size);
1011      block_p = a.getID();
1012      // Write to the area
1013 a.put(arr, 0, area_size);
1014      // And finish the area initialization
1015 a.finish();
1016      
1017      // Once written, the block is invalidated
1018 lock = null;
1019
1020      return block_p;
1021    }
1022
1023    /**
1024     * Overwritten from IntArrayListBlock, this returns the int[] array that
1025     * contains the contents of the block. In this implementation, we
1026     * determine if the array has been read from the index file. If it
1027     * hasn't we read it in, otherwise we use the version in memory.
1028     */
1029    public int[] getArray(boolean immutable) {
1030      // We must synchronize this entire block because otherwise we could
1031 // return a partially loaded array.
1032 synchronized (lock) {
1033
1034        if (array != null) {
1035          prepareMutate(immutable);
1036          return array;
1037        }
1038
1039        // Create the int array
1040 array = new int[max_block_size];
1041
1042        // The number of bytes per entry
1043 int entry_size = compact_type;
1044        // The total size of the entry.
1045 int area_size = (count * entry_size);
1046
1047        // Read in the byte array
1048 byte[] buf = new byte[area_size];
1049        try {
1050          store.getArea(block_p).get(buf, 0, area_size);
1051        }
1052        catch (IOException e) {
1053          debug.write(Lvl.ERROR, this, "block_p = " + block_p);
1054          debug.writeException(e);
1055          throw new Error ("IO Error: " + e.getMessage());
1056        }
1057
1058        // Uncompact it into the int array
1059 int p = 0;
1060        for (int i = 0; i < count; ++i) {
1061          int v = (((int) buf[p]) << ((entry_size - 1) * 8));
1062          ++p;
1063          for (int n = entry_size - 2; n >= 0; --n) {
1064            v = v | ((((int) buf[p]) & 0x0FF) << (n * 8));
1065            ++p;
1066          }
1067          array[i] = v;
1068        }
1069
1070        mutable_block = false;
1071        prepareMutate(immutable);
1072        return array;
1073
1074      }
1075
1076    }
1077
1078    /**
1079     * Overwritten from IntArrayListBlock, returns the capacity of the block.
1080     */
1081    public int getArrayLength() {
1082      return max_block_size;
1083    }
1084
1085    /**
1086     * Makes the block mutable if it is immutable. We must be synchronized on
1087     * 'lock' before this method is called.
1088     */
1089    private void prepareMutate(boolean immutable) {
1090      // If list is to be mutable
1091 if (!immutable && !mutable_block) {
1092        array = (int[]) array.clone();
1093        mutable_block = true;
1094      }
1095    }
1096
1097    /**
1098     * Overwritten from IntArrayListBlock, returns the last entry of the block.
1099     */
1100    public int topInt() {
1101      if (count == 0) {
1102        throw new Error ("No first int in block.");
1103      }
1104
1105      synchronized (lock) {
1106        if (array == null) {
1107          return (int) last_entry;
1108        }
1109        else {
1110          return array[count - 1];
1111        }
1112      }
1113    }
1114
1115    /**
1116     * Overwritten from IntArrayListBlock, returns the first entry of the
1117     * block.
1118     */
1119    public int bottomInt() {
1120      if (count == 0) {
1121        throw new Error ("No first int in block.");
1122      }
1123
1124      synchronized (lock) {
1125        if (array == null) {
1126          return (int) first_entry;
1127        }
1128        else {
1129          return array[0];
1130        }
1131      }
1132    }
1133
1134  }
1135
1136
1137
1138
1139  /**
1140   * The IntegerListInterface implementation that is used to represent a
1141   * mutable snapshop of the indices at a given point in time.
1142   */
1143  private final class IndexIntegerList extends AbstractBlockIntegerList {
1144
1145    /**
1146     * The number of the index in the store that this list represents.
1147     */
1148    private int index_num;
1149
1150    /**
1151     * The maximum block size.
1152     */
1153    private int max_block_size;
1154    
1155    /**
1156     * Set to true when disposed.
1157     */
1158    private boolean disposed = false;
1159
1160    /**
1161     * The mapped elements that were deleted.
1162     */
1163    private ArrayList deleted_blocks = new ArrayList ();
1164
1165
1166    /**
1167     * Constructs the list with the given set of blocks.
1168     */
1169    public IndexIntegerList(int index_num, int max_block_size,
1170                            MappedListBlock[] blocks) {
1171      super(blocks);
1172      this.index_num = index_num;
1173      this.max_block_size = max_block_size;
1174    }
1175
1176    /**
1177     * Creates a new block for the list.
1178     */
1179    protected IntegerListBlockInterface newListBlock() {
1180      if (!disposed) {
1181        return new MappedListBlock(max_block_size);
1182      }
1183      throw new Error ("Integer list has been disposed.");
1184    }
1185
1186    /**
1187     * We must maintain a list of deleted blocks.
1188     */
1189    protected void deleteListBlock(IntegerListBlockInterface list_block) {
1190      deleted_blocks.add(list_block);
1191    }
1192
1193    /**
1194     * Returns the index number of this list.
1195     */
1196    public int getIndexNumber() {
1197      return index_num;
1198    }
1199
1200    /**
1201     * Returns the array of all MappedListBlock that are in this list.
1202     */
1203    public MappedListBlock[] getAllBlocks() {
1204      return (MappedListBlock[])
1205                 block_list.toArray(new MappedListBlock[block_list.size()]);
1206    }
1207
1208    /**
1209     * Returns the array of all MappedListBlock that were deleted from this
1210     * list.
1211     */
1212    public MappedListBlock[] getDeletedBlocks() {
1213      return (MappedListBlock[])
1214         deleted_blocks.toArray(new MappedListBlock[deleted_blocks.size()]);
1215    }
1216
1217
1218    public void dispose() {
1219      disposed = true;
1220      block_list = null;
1221    }
1222
1223  }
1224
1225  /**
1226   * Represents a single 'Index block' area in the store.
1227   * <p>
1228   * An index block area contains an entry for each index element in an index.
1229   * Each entry is 28 bytes in size and the area has a 16 byte header.
1230   * <p>
1231   * HEADER: ( version (int), reserved (int), index size (long) ) <br>
1232   * ENTRY: ( first entry (long), last entry (long),
1233   * index element pointer (long), type/element size (int) )
1234   * <p>
1235   * type/element size contains the number of elements in the block, and the
1236   * block compaction factor. For example, type 1 means the block contains
1237   * short sized index values, 2 is int sized index values, and 3 is long
1238   * sized index values.
1239   */
1240  private class IndexBlock {
1241
1242    /**
1243     * The number of references to this object. When this reaches 0, it is
1244     * safe to free any resources that this block deleted.
1245     */
1246    private int reference_count;
1247
1248    /**
1249     * The index of this block in the index set.
1250     */
1251    private int index_num;
1252
1253    /**
1254     * A pointer that references the area in the store.
1255     */
1256    private final long index_block_p;
1257
1258    /**
1259     * The total number of entries in the index block.
1260     */
1261    private long block_entries;
1262
1263    /**
1264     * The block size of elements in this block.
1265     */
1266    private final int block_size;
1267
1268    /**
1269     * The list of deleted areas that can safely be disposed when this object
1270     * is disposed.
1271     */
1272    private ArrayList deleted_areas;
1273
1274    /**
1275     * True if this block is marked as deleted.
1276     */
1277    private boolean deleted = false;
1278
1279    /**
1280     * Set to true when this index block is freed from the index store.
1281     */
1282    private boolean freed = false;
1283
1284    /**
1285     * The parent IndexBlock. This block is a child modification of the parent.
1286     */
1287    private IndexBlock parent_block;
1288    
1289    /**
1290     * Constructs the IndexBlock.
1291     */
1292    IndexBlock(int index_num, int block_size, long index_block_p)
1293                                                         throws IOException {
1294      this.index_num = index_num;
1295      this.block_size = block_size;
1296      this.index_block_p = index_block_p;
1297
1298      // Read the index count
1299 Area index_block_area = store.getArea(index_block_p);
1300      index_block_area.position(8);
1301      block_entries = index_block_area.getLong();
1302      
1303      reference_count = 0;
1304      
1305    }
1306
1307    /**
1308     * Sets the parent IndexBlock, the index that this index block succeeded.
1309     */
1310    void setParentIndexBlock(IndexBlock parent) {
1311      this.parent_block = parent;
1312    }
1313
1314    /**
1315     * Returns a list of pointers to all mapped blocks.
1316     */
1317    long[] getAllBlockPointers() throws IOException {
1318      // Create an area for the index block pointer
1319 Area index_block_area = store.getArea(index_block_p);
1320      
1321      // First create the list of block entries for this list
1322 long[] blocks = new long[(int) block_entries];
1323      if (block_entries != 0) {
1324        index_block_area.position(16);
1325        for (int i = 0; i < block_entries; ++i) {
1326          // NOTE: We cast to 'int' here because of internal limitations.
1327 index_block_area.getLong();
1328          index_block_area.getLong();
1329          long element_p = index_block_area.getLong();
1330          index_block_area.getInt();
1331        
1332          blocks[i] = element_p;
1333        }
1334      }
1335      
1336      return blocks;
1337    }
1338
1339    /**
1340     * Creates and returns an array of all the MappedListBlock objects that make
1341     * up this view of the index integer list.
1342     */
1343    private MappedListBlock[] createMappedListBlocks() throws IOException {
1344      // Create an area for the index block pointer
1345 Area index_block_area = store.getArea(index_block_p);
1346      // First create the list of block entries for this list
1347 MappedListBlock[] blocks = new MappedListBlock[(int) block_entries];
1348      if (block_entries != 0) {
1349        index_block_area.position(16);
1350        for (int i = 0; i < block_entries; ++i) {
1351          // NOTE: We cast to 'int' here because of internal limitations.
1352 long first_entry = index_block_area.getLong();
1353          long last_entry = index_block_area.getLong();
1354          long element_p = index_block_area.getLong();
1355          int type_size = index_block_area.getInt();
1356
1357          // size is the first 24 bits (max size = 16MB)
1358 int element_count = type_size & 0x0FFF;
1359          byte type = (byte) ((type_size >>> 24) & 0x0F);
1360        
1361          blocks[i] = new MappedListBlock(first_entry, last_entry, element_p,
1362                                          element_count, type, block_size);
1363        }
1364      }
1365      return blocks;
1366    }
1367
1368    /**
1369     * Creates and returns a mutable IndexIntegerList object based on this
1370     * view of the index.
1371     */
1372    IndexIntegerList createIndexIntegerList() throws IOException {
1373      // Create the MappedListBlock objects for this view
1374 MappedListBlock[] blocks = createMappedListBlocks();
1375      // And return the IndexIntegerList
1376 return new IndexIntegerList(index_num, block_size, blocks);
1377    }
1378
1379    /**
1380     * Copies this index block to the given Store and returns a pointer to the
1381     * block within the store.
1382     */
1383    long copyTo(Store dest_store) throws IOException {
1384      // Create the MappedListBlock object list for this view
1385 MappedListBlock[] blocks = createMappedListBlocks();
1386      try {
1387        dest_store.lockForWrite();
1388        // Create the header area in the store for this block
1389 AreaWriter a = dest_store.createArea(16 + (blocks.length * 28));
1390        long block_p = a.getID();
1391
1392        a.putInt(1); // version
1393 a.putInt(0); // reserved
1394 a.putLong(blocks.length); // block count
1395 for (int i = 0; i < blocks.length; ++i) {
1396          MappedListBlock entry = blocks[i];
1397          long b_p = entry.copyTo(dest_store);
1398          int block_size = entry.size();
1399          a.putLong(entry.first_entry);
1400          a.putLong(entry.last_entry);
1401          a.putLong(b_p);
1402          a.putInt(block_size | (((int) entry.getCompactType()) << 24));
1403        }
1404
1405        // Now finish the area initialization
1406 a.finish();
1407
1408        // Return pointer to the new area in dest_store.
1409 return block_p;
1410
1411      }
1412      finally {
1413        dest_store.unlockForWrite();
1414      }
1415
1416    }
1417
1418    /**
1419     * Recursively calls through the block hierarchy and deletes and blocks
1420     * that can be deleted.
1421     */
1422    private boolean deleteBlockChain() {
1423      boolean parent_deleted = true;
1424      if (parent_block != null) {
1425        parent_deleted = parent_block.deleteBlockChain();
1426        if (parent_deleted) {
1427          parent_block = null;
1428        }
1429      }
1430
1431      // If the parent is deleted,
1432 if (parent_deleted) {
1433        // Can we delete this block?
1434 if (reference_count <= 0) {
1435          if (deleted && deleted_areas != null) {
1436            deleteAllAreas(deleted_areas);
1437          }
1438          deleted_areas = null;
1439        }
1440        else {
1441          // We can't delete this block so return false
1442 return false;
1443        }
1444      }
1445
1446      return parent_deleted;
1447    }
1448
1449    /**
1450     * Adds a reference to this object.
1451     */
1452    public synchronized void addReference() {
1453      if (freed) {
1454        throw new RuntimeException ("Assertion failed: Block was freed.");
1455      }
1456      ++reference_count;
1457    }
1458
1459    /**
1460     * Removes a reference to this object.
1461     */
1462    public void removeReference() {
1463      boolean pending_delete = false;
1464      synchronized(this) {
1465        --reference_count;
1466        if (reference_count <= 0) {
1467          if (freed) {
1468            throw new RuntimeException (
1469                  "Assertion failed: remove reference called too many times.");
1470          }
1471          if (!deleted && deleted_areas != null) {
1472            throw new RuntimeException (
1473                  "Assertion failed: !deleted and deleted_areas != null");
1474          }
1475          freed = true;
1476          if (deleted) {
1477            addDeletedArea(index_block_p);
1478            // Delete these areas
1479 pending_delete = true;
1480          }
1481        }
1482      } // synchronized(this)
1483 if (pending_delete) {
1484        synchronized(IndexSetStore.this) {
1485          deleteBlockChain();
1486        }
1487      }
1488    }
1489
1490    /**
1491     * Returns the number of references to this object.
1492     */
1493    public synchronized int getReferenceCount() {
1494      return reference_count;
1495    }
1496
1497    /**
1498     * Returns the block size that has been set on this list.
1499     */
1500    public int getBlockSize() {
1501      return block_size;
1502    }
1503
1504    /**
1505     * Returns the pointer to this index block in the store.
1506     */
1507    public long getPointer() {
1508      return index_block_p;
1509    }
1510
1511    /**
1512     * Marks this block as deleted.
1513     */
1514    public synchronized void markAsDeleted() {
1515      deleted = true;
1516    }
1517
1518    /**
1519     * Adds to the list of deleted areas in this block.
1520     */
1521    public synchronized void addDeletedArea(long pointer) {
1522      if (deleted_areas == null) {
1523        deleted_areas = new ArrayList ();
1524      }
1525
1526      deleted_areas.add(new Long (pointer));
1527      
1528    }
1529
1530  }
1531  
1532}
1533
1534

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags