DiskHashtable


1   /*
2   
3      Derby - Class org.apache.derby.iapi.store.access.DiskHashtable
4   
5      Licensed to the Apache Software Foundation (ASF) under one or more
6      contributor license agreements.  See the NOTICE file distributed with
7      this work for additional information regarding copyright ownership.
8      The ASF licenses this file to you under the Apache License, Version 2.0
9      (the "License"); you may not use this file except in compliance with
10     the License.  You may obtain a copy of the License at
11  
12        http://www.apache.org/licenses/LICENSE-2.0
13  
14     Unless required by applicable law or agreed to in writing, software
15     distributed under the License is distributed on an "AS IS" BASIS,
16     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17     See the License for the specific language governing permissions and
18     limitations under the License.
19  
20   */
21  
22  package org.apache.derby.iapi.store.access;
23  
24  import java.util.Enumeration  ;
25  import java.util.NoSuchElementException  ;
26  import java.util.Properties  ;
27  import java.util.Vector  ;
28  import org.apache.derby.iapi.error.StandardException;
29  import org.apache.derby.iapi.services.io.FormatableBitSet;
30  import org.apache.derby.iapi.types.DataValueDescriptor;
31  import org.apache.derby.iapi.types.SQLInteger;
32  import org.apache.derby.impl.store.access.heap.HeapRowLocation;
33  import org.apache.derby.iapi.types.RowLocation;
34  import org.apache.derby.iapi.services.context.ContextService;
35  import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
36  
37  /**
38   * This class is used by BackingStoreHashtable when the BackingStoreHashtable must spill to disk.
39   * It implements the methods of a hash table: put, get, remove, elements, however it is not implemented
40   * as a hash table. In order to minimize the amount of unique code it is implemented using a Btree and a heap
41   * conglomerate. The Btree indexes the hash code of the row key. The actual key may be too long for
42   * our Btree implementation.
43   *
44   * Created: Fri Jan 28 13:58:03 2005
45   *
46   * @author <a HREF="mailto:klebanof@us.ibm.com">Jack Klebanoff</a>
47   * @version 1.0
48   */
49  
50  public class DiskHashtable 
51  {
52      private final long rowConglomerateId;
53      private ConglomerateController rowConglomerate;
54      private final long btreeConglomerateId;
55      private ConglomerateController btreeConglomerate;
56      private final DataValueDescriptor[] btreeRow;
57      private final int[] key_column_numbers;
58      private final boolean remove_duplicates;
59      private final TransactionController tc;
60      private final DataValueDescriptor[] row;
61      private final DataValueDescriptor[] scanKey = { new SQLInteger()};
62      private int size;
63      private boolean keepStatistics;
64  
65      /**
66       * Creates a new <code>DiskHashtable</code> instance.
67       *
68       * @param tc
69       * @param template An array of DataValueDescriptors that serves as a template for the rows.
70       * @param key_column_numbers The indexes of the key columns (0 based)
71       * @param remove_duplicates If true then rows with duplicate keys are removed
72       * @param keepAfterCommit If true then the hash table is kept after a commit
73       */
74      public DiskHashtable( TransactionController tc,
75                            DataValueDescriptor[] template,
76                            int[] key_column_numbers,
77                            boolean remove_duplicates,
78                            boolean keepAfterCommit)
79          throws StandardException
80      {
81          this.tc = tc;
82          this.key_column_numbers = key_column_numbers;
83          this.remove_duplicates = remove_duplicates;
84          LanguageConnectionContext lcc = (LanguageConnectionContext)
85                  ContextService.getContextOrNull(LanguageConnectionContext.CONTEXT_ID);
86          keepStatistics = (lcc != null) && lcc.getRunTimeStatisticsMode();
87          row = new DataValueDescriptor[ template.length];
88          for( int i = 0; i < row.length; i++)
89              row[i] = template[i].getNewNull();
90          int tempFlags = keepAfterCommit ? (TransactionController.IS_TEMPORARY | TransactionController.IS_KEPT)
91            : TransactionController.IS_TEMPORARY;
92          
93          rowConglomerateId = tc.createConglomerate( "heap",
94                                                     template,
95                                                     (ColumnOrdering[]) null,
96                                                     (Properties  ) null,
97                                                     tempFlags);
98          rowConglomerate = tc.openConglomerate( rowConglomerateId,
99                                                 keepAfterCommit,
100                                                TransactionController.OPENMODE_FORUPDATE,
101                                                TransactionController.MODE_TABLE,
102                                                TransactionController.ISOLATION_NOLOCK /* Single thread only */ );
103 
104         btreeRow = new DataValueDescriptor[] { new SQLInteger(), rowConglomerate.newRowLocationTemplate()};
105         Properties   btreeProps = new Properties  ();
106         btreeProps.put( "baseConglomerateId", String.valueOf( rowConglomerateId));
107         btreeProps.put( "rowLocationColumn", "1");
108         btreeProps.put( "allowDuplicates", "false"); // Because the row location is part of the key
109         btreeProps.put( "nKeyFields", "2"); // Include the row location column
110         btreeProps.put( "nUniqueColumns", "2"); // Include the row location column
111         btreeProps.put( "maintainParentLinks", "false");
112         btreeConglomerateId = tc.createConglomerate( "BTREE",
113                                                      btreeRow,
114                                                      (ColumnOrdering[]) null,
115                                                      btreeProps,
116                                                      tempFlags);
117 
118         btreeConglomerate = tc.openConglomerate( btreeConglomerateId,
119                                                  keepAfterCommit,
120                                                  TransactionController.OPENMODE_FORUPDATE,
121                                                  TransactionController.MODE_TABLE,
122                                                  TransactionController.ISOLATION_NOLOCK /* Single thread only */ );
123     } // end of constructor
124 
125     public void close() throws StandardException
126     {
127         btreeConglomerate.close();
128         rowConglomerate.close();
129         tc.dropConglomerate( btreeConglomerateId);
130         tc.dropConglomerate( rowConglomerateId);
131     } // end of close
132     
133     /**
134      * Put a new row in the overflow structure.
135      *
136      * @param row The row to be inserted.
137      *
138      * @return true if the row was added,
139      *         false if it was not added (because it was a duplicate and we are eliminating duplicates).
140      *
141      * @exception StandardException standard error policy
142      */
143     public boolean put( Object   key, Object  [] row)
144         throws StandardException
145     {
146         boolean isDuplicate = false;
147         if( remove_duplicates || keepStatistics)
148         {
149             // Go to the work of finding out whether it is a duplicate
150             isDuplicate = (getRemove( key, false, true) != null);
151             if( remove_duplicates && isDuplicate)
152                 return false;
153         }
154         rowConglomerate.insertAndFetchLocation( (DataValueDescriptor[]) row, (RowLocation) btreeRow[1]);
155         btreeRow[0].setValue( key.hashCode());
156         btreeConglomerate.insert( btreeRow);
157         if( keepStatistics && !isDuplicate)
158             size++;
159         return true;
160     } // end of put
161 
162     /**
163      * Get a row from the overflow structure.
164      *
165      * @param key If the rows only have one key column then the key value. If there is more than one
166      *            key column then a KeyHasher
167      *
168      * @return null if there is no corresponding row,
169      *         the row (DataValueDescriptor[]) if there is exactly one row with the key
170      *         a Vector of all the rows with the key if there is more than one.
171      *
172      * @exception StandardException
173      */
174     public Object   get( Object   key)
175         throws StandardException
176     {
177         return getRemove( key, false, false);
178     }
179 
180     private Object   getRemove( Object   key, boolean remove, boolean existenceOnly)
181         throws StandardException
182     {
183         int hashCode = key.hashCode();
184         int rowCount = 0;
185         Object   retValue = null;
186 
187         scanKey[0].setValue( hashCode);
188         ScanController scan = tc.openScan( btreeConglomerateId,
189                                            false, // do not hold
190                                            remove ? TransactionController.OPENMODE_FORUPDATE : 0,
191                                            TransactionController.MODE_TABLE,
192                                            TransactionController.ISOLATION_READ_UNCOMMITTED,
193                                            null, // Scan all the columns
194                                            scanKey,
195                                            ScanController.GE,
196                                            (Qualifier[][]) null,
197                                            scanKey,
198                                            ScanController.GT);
199         try
200         {
201             while( scan.fetchNext( btreeRow))
202             {
203                 if( rowConglomerate.fetch( (RowLocation) btreeRow[1], row, (FormatableBitSet) null /* all columns */)
204                     && rowMatches( row, key))
205                 {
206                     if( existenceOnly)
207                         return this;
208 
209                     rowCount++;
210                     if( rowCount == 1) 
211                     {
212                         retValue = BackingStoreHashtable.shallowCloneRow( row);                        
213                     } 
214                     else 
215                     {
216                         Vector   v;
217                         if( rowCount == 2)
218                         {
219                             v = new Vector  ( 2);
220                             v.add( retValue);
221                             retValue = v;
222                         }
223                         else
224                         {
225                             v = (Vector  ) retValue;
226                         }
227                         v.add( BackingStoreHashtable.shallowCloneRow( row));
228                     }
229                     if( remove)
230                     {
231                         rowConglomerate.delete( (RowLocation) btreeRow[1]);
232                         scan.delete();
233                         size--;
234                     }
235                     if( remove_duplicates)
236                         // This must be the only row with the key
237                         return retValue;
238                 }
239             }
240         }
241         finally
242         {
243             scan.close();
244         }
245         return retValue;
246     } // end of getRemove
247 
248 
249     private boolean rowMatches( DataValueDescriptor[] row,
250                                 Object   key)
251     {
252         if( key_column_numbers.length == 1)
253             return row[ key_column_numbers[0]].equals( key);
254 
255         KeyHasher kh = (KeyHasher) key;
256         for( int i = 0; i < key_column_numbers.length; i++)
257         {
258             if( ! row[ key_column_numbers[i]].equals( kh.getObject(i)))
259                 return false;
260         }
261         return true;
262     } // end of rowMatches
263 
264     /**
265      * remove all rows with a given key from the hash table.
266      *
267      * @param key          The key of the rows to remove.
268      *
269      * @return The removed row(s).
270      *
271      * @exception  StandardException  Standard exception policy.
272      **/
273     public Object   remove( Object   key)
274         throws StandardException
275     {
276         return getRemove( key, true, false);
277     } // end of remove
278 
279     /**
280      * @return The number of rows in the hash table
281      */
282     public int size()
283     {
284         return size;
285     }
286     
287     /**
288      * Return an Enumeration that can be used to scan entire table.
289      * <p>
290      * RESOLVE - is it worth it to support this routine?
291      *
292      * @return The Enumeration.
293      *
294      * @exception  StandardException  Standard exception policy.
295      **/
296     public Enumeration   elements()
297         throws StandardException
298     {
299         return new ElementEnum();
300     }
301 
302     private class ElementEnum implements Enumeration  
303     {
304         private ScanController scan;
305         private boolean hasMore;
306 
307         ElementEnum()
308         {
309             try
310             {
311                 scan = tc.openScan( rowConglomerateId,
312                                     false, // do not hold
313                                     0, // read only
314                                     TransactionController.MODE_TABLE,
315                                     TransactionController.ISOLATION_NOLOCK,
316                                     (FormatableBitSet) null, // all columns
317                                     (DataValueDescriptor[]) null, // no start key
318                                     0, // no start key operator
319                                     (Qualifier[][]) null,
320                                     (DataValueDescriptor[]) null, // no stop key
321                                     0 /* no stop key operator */);
322                 hasMore = scan.next();
323                 if( ! hasMore)
324                 {
325                     scan.close();
326                     scan = null;
327                 }
328             }
329             catch( StandardException se)
330             {
331                 hasMore = false;
332                 if( scan != null)
333                 {
334                     try
335                     {
336                         scan.close();
337                     }
338                     catch( StandardException se1){};
339                     scan = null;
340                 }
341             }
342         } // end of constructor
343 
344         public boolean hasMoreElements()
345         {
346             return hasMore;
347         }
348 
349         public Object   nextElement()
350         {
351             if( ! hasMore)
352                 throw new NoSuchElementException  ();
353             try
354             {
355                 scan.fetch( row);
356                 Object   retValue =  BackingStoreHashtable.shallowCloneRow( row);
357                 hasMore = scan.next();
358                 if( ! hasMore)
359                 {
360                     scan.close();
361                     scan = null;
362                 }
363 
364                 return retValue;
365             }
366             catch( StandardException se)
367             {
368                 if( scan != null)
369                 {
370                     try
371                     {
372                         scan.close();
373                     }
374                     catch( StandardException se1){};
375                     scan = null;
376                 }
377                 throw new NoSuchElementException  ();
378             }
379         } // end of nextElement
380     } // end of class ElementEnum
381 }
382
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags