001: /*
002:
003: Derby - Class org.apache.derbyTesting.functionTests.tests.store.TestDiskHashtable
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to You under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derbyTesting.functionTests.tests.store;
023:
024: import java.sql.Connection;
025: import java.sql.ResultSet;
026: import java.sql.SQLException;
027: import java.sql.Statement;
028:
029: import java.util.BitSet;
030: import java.util.Enumeration;
031: import java.util.HashMap;
032: import java.util.Vector;
033:
034: import org.apache.derby.iapi.error.PublicAPI;
035: import org.apache.derby.iapi.error.StandardException;
036: import org.apache.derby.iapi.sql.conn.ConnectionUtil;
037: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
038: import org.apache.derby.iapi.store.access.DiskHashtable;
039: import org.apache.derby.iapi.store.access.KeyHasher;
040: import org.apache.derby.iapi.store.access.TransactionController;
041: import org.apache.derby.iapi.types.DataValueDescriptor;
042: import org.apache.derby.iapi.types.Orderable;
043: import org.apache.derby.iapi.types.SQLInteger;
044: import org.apache.derby.iapi.types.SQLLongint;
045: import org.apache.derby.iapi.types.SQLVarchar;
046: import org.apache.derby.tools.ij;
047: import org.apache.derbyTesting.functionTests.util.TestUtil;
048:
049: /**
050: * This program tests the org.apache.derby.iapi.store.access.DiskHashtable class.
051: * The unit test interface is not used because that is undocumented and very difficult to decipher.
052: * Furthermore it is difficult to diagnose problems when using the unit test interface.
053: *
054: * Created: Wed Feb 09 15:44:12 2005
055: *
056: * @author <a href="mailto:klebanof@us.ibm.com">Jack Klebanoff</a>
057: * @version 1.0
058: */
059: public class TestDiskHashtable {
060: private TransactionController tc;
061: private int failed = 0;
062:
063: public static void main(String args[]) {
064: int failed = 1;
065:
066: REPORT("Test DiskHashtable starting");
067: try {
068: // use the ij utility to read the property file and
069: // make the initial connection.
070: ij.getPropertyArg(args);
071: Connection conn = ij.startJBMS();
072: Statement stmt = conn.createStatement();
073: stmt
074: .execute("CREATE FUNCTION testDiskHashtable() returns INTEGER EXTERNAL NAME 'org.apache.derbyTesting.functionTests.tests.store.TestDiskHashtable.runTests' LANGUAGE JAVA PARAMETER STYLE JAVA");
075: ResultSet rs = stmt
076: .executeQuery("values( testDiskHashtable())");
077: if (rs.next())
078: failed = rs.getInt(1);
079: stmt.close();
080: conn.close();
081: } catch (SQLException e) {
082: TestUtil.dumpSQLExceptions(e);
083: failed = 1;
084: } catch (Throwable t) {
085: REPORT("FAIL -- unexpected exception:" + t.toString());
086: failed = 1;
087: }
088: REPORT((failed == 0) ? "OK" : "FAILED");
089: System.exit((failed == 0) ? 0 : 1);
090: }
091:
092: private void REPORT_FAILURE(String msg) {
093: failed = 1;
094: REPORT(msg);
095: }
096:
097: private static void REPORT(String msg) {
098: System.out.println(msg);
099: }
100:
101: public static int runTests() throws SQLException {
102: TestDiskHashtable tester = new TestDiskHashtable();
103: return tester.doIt();
104: }
105:
106: private TestDiskHashtable() throws SQLException {
107: LanguageConnectionContext lcc = ConnectionUtil.getCurrentLCC();
108: if (lcc == null)
109: throw new SQLException("Cannot get the LCC");
110: tc = lcc.getTransactionExecute();
111: }
112:
113: private int doIt() throws SQLException {
114: try {
115:
116: REPORT("Starting single key, keep duplicates test");
117: testOneVariant(tc, false, singleKeyTemplate, singleKeyCols,
118: singleKeyRows);
119: REPORT("Starting single key, remove duplicates test");
120: testOneVariant(tc, true, singleKeyTemplate, singleKeyCols,
121: singleKeyRows);
122: REPORT("Starting multiple key, keep duplicates test");
123: testOneVariant(tc, false, multiKeyTemplate, multiKeyCols,
124: multiKeyRows);
125: REPORT("Starting multiple key, remove duplicates test");
126: testOneVariant(tc, true, multiKeyTemplate, multiKeyCols,
127: multiKeyRows);
128:
129: tc.commit();
130: } catch (StandardException se) {
131: throw PublicAPI.wrapStandardException(se);
132: }
133: return failed;
134: } // end of doIt
135:
136: private static final DataValueDescriptor[] singleKeyTemplate = {
137: new SQLInteger(), new SQLVarchar() };
138: private static final int[] singleKeyCols = { 0 };
139: private static final DataValueDescriptor[][] singleKeyRows = {
140: { new SQLInteger(1), new SQLVarchar("abcd") },
141: { new SQLInteger(2), new SQLVarchar("abcd") },
142: { new SQLInteger(3), new SQLVarchar("e") },
143: { new SQLInteger(1), new SQLVarchar("zz") } };
144:
145: private static final DataValueDescriptor[] multiKeyTemplate = {
146: new SQLLongint(), new SQLVarchar(), new SQLInteger() };
147: private static final int[] multiKeyCols = { 1, 0 };
148: private static final DataValueDescriptor[][] multiKeyRows = {
149: { new SQLLongint(1), new SQLVarchar("aa"),
150: multiKeyTemplate[2].getNewNull() },
151: { new SQLLongint(2), new SQLVarchar("aa"),
152: new SQLInteger(1) },
153: { new SQLLongint(2), new SQLVarchar("aa"),
154: new SQLInteger(2) },
155: { new SQLLongint(2), new SQLVarchar("b"), new SQLInteger(1) } };
156:
157: private static final int LOTS_OF_ROWS_COUNT = 50000;
158:
159: private void testOneVariant(TransactionController tc,
160: boolean removeDups, DataValueDescriptor[] template,
161: int[] keyCols, DataValueDescriptor[][] rows)
162: throws StandardException {
163: DiskHashtable dht = new DiskHashtable(tc, template, keyCols,
164: removeDups, false);
165: boolean[] isDuplicate = new boolean[rows.length];
166: boolean[] found = new boolean[rows.length];
167: HashMap simpleHash = new HashMap(rows.length);
168:
169: testElements(removeDups, dht, keyCols, 0, rows, simpleHash,
170: isDuplicate, found);
171:
172: for (int i = 0; i < rows.length; i++) {
173: Object key = KeyHasher.buildHashKey(rows[i], keyCols);
174: Vector al = (Vector) simpleHash.get(key);
175: isDuplicate[i] = (al != null);
176: if (al == null) {
177: al = new Vector(4);
178: simpleHash.put(key, al);
179: }
180: if ((!removeDups) || !isDuplicate[i])
181: al.add(rows[i]);
182:
183: if (dht.put(key, rows[i]) != (removeDups ? (!isDuplicate[i])
184: : true))
185: REPORT_FAILURE(" put returned wrong value on row " + i);
186:
187: for (int j = 0; j <= i; j++) {
188: key = KeyHasher.buildHashKey(rows[j], keyCols);
189: if (!rowsEqual(dht.get(key), simpleHash.get(key)))
190: REPORT_FAILURE(" get returned wrong value on key "
191: + j);
192: }
193:
194: testElements(removeDups, dht, keyCols, i + 1, rows,
195: simpleHash, isDuplicate, found);
196: }
197: // Remove them
198: for (int i = 0; i < rows.length; i++) {
199: Object key = KeyHasher.buildHashKey(rows[i], keyCols);
200: if (!rowsEqual(dht.remove(key), simpleHash.get(key)))
201: REPORT_FAILURE(" remove returned wrong value on key "
202: + i);
203: simpleHash.remove(key);
204: if (dht.get(key) != null)
205: REPORT_FAILURE(" remove did not delete key " + i);
206: }
207: testElements(removeDups, dht, keyCols, 0, rows, simpleHash,
208: isDuplicate, found);
209:
210: testLargeTable(dht, keyCols, rows[0]);
211: dht.close();
212: } // end of testOneVariant
213:
214: private void testLargeTable(DiskHashtable dht, int[] keyCols,
215: DataValueDescriptor[] aRow) throws StandardException {
216: // Add a lot of elements
217: // If there are two or more key columns then we will vary the first two key columns, using an approximately
218: // square matrix of integer key values. Because the hash generator is commutative key (i,j) hashes into the
219: // same bucket as key (j,i), testing the case where different keys hash into the same bucket.
220: int key1Count = (keyCols.length > 1) ? ((int) Math.round(Math
221: .sqrt((double) LOTS_OF_ROWS_COUNT))) : 1;
222: int key0Count = (LOTS_OF_ROWS_COUNT + key1Count - 1)
223: / key1Count;
224:
225: DataValueDescriptor[] row = new DataValueDescriptor[aRow.length];
226: for (int i = 0; i < row.length; i++)
227: row[i] = aRow[i].getClone();
228:
229: for (int key0Idx = 0; key0Idx < key0Count; key0Idx++) {
230: row[keyCols[0]].setValue(key0Idx);
231: for (int key1Idx = 0; key1Idx < key1Count; key1Idx++) {
232: if (keyCols.length > 1)
233: row[keyCols[1]].setValue(key1Idx);
234: Object key = KeyHasher.buildHashKey(row, keyCols);
235: if (!dht.put(key, row)) {
236: REPORT_FAILURE(" put returned wrong value for key("
237: + key0Idx + "," + key1Idx + ")");
238: key0Idx = key0Count;
239: break;
240: }
241: }
242: }
243: for (int key0Idx = 0; key0Idx < key0Count; key0Idx++) {
244: row[keyCols[0]].setValue(key0Idx);
245: for (int key1Idx = 0; key1Idx < key1Count; key1Idx++) {
246: if (keyCols.length > 1)
247: row[keyCols[1]].setValue(key1Idx);
248: Object key = KeyHasher.buildHashKey(row, keyCols);
249: if (!rowsEqual(dht.get(key), row)) {
250: REPORT_FAILURE(" large table get returned wrong value for key("
251: + key0Idx + "," + key1Idx + ")");
252: key0Idx = key0Count;
253: break;
254: }
255: }
256: }
257: BitSet found = new BitSet(key0Count * key1Count);
258: Enumeration elements = dht.elements();
259: while (elements.hasMoreElements()) {
260: Object el = elements.nextElement();
261: if (!(el instanceof DataValueDescriptor[])) {
262: REPORT_FAILURE(" large table enumeration returned wrong element type");
263: break;
264: }
265: DataValueDescriptor[] fetchedRow = (DataValueDescriptor[]) el;
266:
267: int i = fetchedRow[keyCols[0]].getInt() * key1Count;
268: if (keyCols.length > 1)
269: i += fetchedRow[keyCols[1]].getInt();
270: if (i >= key0Count * key1Count) {
271: REPORT_FAILURE(" large table enumeration returned invalid element");
272: break;
273: }
274:
275: if (found.get(i)) {
276: REPORT_FAILURE(" large table enumeration returned same element twice");
277: break;
278: }
279: found.set(i);
280: }
281: for (int i = key0Count * key1Count - 1; i >= 0; i--) {
282: if (!found.get(i)) {
283: REPORT_FAILURE(" large table enumeration missed at least one element");
284: break;
285: }
286: }
287: } // end of testLargeTable
288:
289: private void testElements(boolean removeDups, DiskHashtable dht,
290: int[] keyCols, int rowCount, DataValueDescriptor[][] rows,
291: HashMap simpleHash, boolean[] isDuplicate, boolean[] found)
292: throws StandardException {
293: for (int i = 0; i < rowCount; i++)
294: found[i] = false;
295:
296: for (Enumeration e = dht.elements(); e.hasMoreElements();) {
297: Object el = e.nextElement();
298: if (el == null) {
299: REPORT_FAILURE(" table enumeration returned a null element");
300: return;
301: }
302: if (el instanceof DataValueDescriptor[])
303: checkElement((DataValueDescriptor[]) el, rowCount,
304: rows, found);
305: else if (el instanceof Vector) {
306: Vector v = (Vector) el;
307: for (int i = 0; i < v.size(); i++)
308: checkElement((DataValueDescriptor[]) v.get(i),
309: rowCount, rows, found);
310: } else if (el == null) {
311: REPORT_FAILURE(" table enumeration returned an incorrect element type");
312: return;
313: }
314: }
315: for (int i = 0; i < rowCount; i++) {
316: if ((removeDups && isDuplicate[i])) {
317: if (found[i]) {
318: REPORT_FAILURE(" table enumeration did not remove duplicates");
319: return;
320: }
321: } else if (!found[i]) {
322: REPORT_FAILURE(" table enumeration missed at least one element");
323: return;
324: }
325: }
326: } // end of testElements
327:
328: private void checkElement(DataValueDescriptor[] fetchedRow,
329: int rowCount, DataValueDescriptor[][] rows, boolean[] found)
330: throws StandardException {
331: for (int i = 0; i < rowCount; i++) {
332: if (rowsEqual(fetchedRow, rows[i])) {
333: if (found[i]) {
334: REPORT_FAILURE(" table enumeration returned the same element twice");
335: return;
336: }
337: found[i] = true;
338: return;
339: }
340: }
341: REPORT_FAILURE(" table enumeration returned an incorrect element");
342: } // end of checkElement
343:
344: private boolean rowsEqual(Object r1, Object r2)
345: throws StandardException {
346: if (r1 == null)
347: return r2 == null;
348:
349: if (r1 instanceof DataValueDescriptor[]) {
350: DataValueDescriptor[] row1 = (DataValueDescriptor[]) r1;
351: DataValueDescriptor[] row2;
352:
353: if (r2 instanceof Vector) {
354: Vector v2 = (Vector) r2;
355: if (v2.size() != 1)
356: return false;
357: row2 = (DataValueDescriptor[]) v2.elementAt(0);
358: } else if (r2 instanceof DataValueDescriptor[])
359: row2 = (DataValueDescriptor[]) r2;
360: else
361: return false;
362:
363: if (row1.length != row2.length)
364: return false;
365: for (int i = 0; i < row1.length; i++) {
366: if (!row1[i].compare(Orderable.ORDER_OP_EQUALS,
367: row2[i], true, true))
368: return false;
369: }
370: return true;
371: }
372: if (r1 instanceof Vector) {
373: if (!(r2 instanceof Vector))
374: return false;
375: Vector v1 = (Vector) r1;
376: Vector v2 = (Vector) r2;
377: if (v1.size() != v2.size())
378: return false;
379: for (int i = v1.size() - 1; i >= 0; i--) {
380: if (!rowsEqual(v1.elementAt(i), v2.elementAt(i)))
381: return false;
382: }
383: return true;
384: }
385: // What is it then?
386: return r1.equals(r2);
387: } // end of rowsEqual
388: }
|