001: package com.quadcap.sql;
002:
003: /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.io.ByteArrayOutputStream;
042: import java.io.IOException;
043: import java.io.OutputStream;
044:
045: import java.sql.SQLException;
046:
047: import com.quadcap.sql.io.ObjectOutputStream;
048:
049: import com.quadcap.sql.file.ByteUtil;
050: import com.quadcap.sql.file.SubPageManager;
051:
052: import com.quadcap.sql.index.Comparator;
053:
054: import com.quadcap.sql.types.KeyStream;
055: import com.quadcap.sql.types.Type;
056: import com.quadcap.sql.types.Value;
057: import com.quadcap.sql.types.ValueInteger;
058:
059: import com.quadcap.util.Debug;
060: import com.quadcap.util.Util;
061:
062: /**
063: * Micro-optimized (-;) key serialization and comparison. This class
064: * is designed to eliminate copies and allocations during key comparison
065: * and serialization operations.
066: *
067: * @author Stan Bailes
068: */
069: public class Key extends Comparator {
070: //#ifdef DEBUG
071: static final boolean paranoid = false;
072: //#endif
073:
074: boolean[] asc;
075:
076: public Key(int cnt) {
077: asc = new boolean[cnt];
078: for (int i = 0; i < cnt; i++)
079: asc[i] = true;
080: }
081:
082: public Key(boolean[] asc) {
083: this .asc = asc;
084: }
085:
086: public static byte[] makeKey(Tuple tuple, Row row, int[] map,
087: long rowNum, boolean doRowNum) throws SQLException {
088: //#ifdef DEBUG
089: if (false) {
090: StringBuffer sb = new StringBuffer("makeKey(");
091: sb.append(row.toString());
092: sb.append(" (" + ((Object) row).toString());
093: sb.append(", [");
094: for (int i = 0; i < map.length; i++) {
095: if (i > 0)
096: sb.append(',');
097: sb.append(map[i]);
098: }
099: sb.append("], ");
100: sb.append(SubPageManager.toString(rowNum));
101: sb.append(", ");
102: sb.append(doRowNum);
103: sb.append(")");
104: sb.append("\nFROM:\n");
105: sb.append(Util.stackTrace());
106: Debug.println(sb.toString());
107: }
108: //#endif
109: try {
110: ByteArrayOutputStream bos = new ByteArrayOutputStream();
111: KeyStream out = new KeyStream(bos, Database.isCaseSensitive);
112: //#ifdef DEBUG
113: int cnt = 0;
114: //#endif
115: if (map != null) {
116: //#ifdef DEBUG
117: cnt = map.length;
118: //#endif
119: for (int i = 0; i < map.length; i++) {
120: int col = map[i];
121: Value v = row.item(col);
122: if (tuple != null) {
123: Column c = tuple.getColumn(col);
124: Type t = c.getType();
125: v = c.getType().convert(v);
126: }
127: v.serializeKey(out);
128: }
129: } else {
130: //#ifdef DEBUG
131: cnt = row.size();
132: //#endif
133: for (int i = 1; i <= row.size(); i++) {
134: Value v = row.item(i);
135: v.serializeKey(out);
136: }
137: }
138: if (doRowNum) {
139: out.writeLong(rowNum);
140: //#ifdef DEBUG
141: cnt++;
142: //#endif
143: }
144: byte[] ret = bos.toByteArray();
145: //#ifdef DEBUG
146: if (paranoid) {
147: Key k = new Key(cnt);
148: k.checkKey(ret, 0, ret.length);
149: }
150: //#endif
151: return ret;
152: } catch (IOException e) {
153: throw DbException.wrapThrowable(e);
154: }
155: }
156:
157: public static byte[] makeKey(Row row) throws SQLException {
158: return makeKey(null, row, null, 0, false);
159: }
160:
161: /**
162: * Null comparison for GROUP BY
163: */
164: public boolean compareNulls(byte[] a, byte[] b) {
165: // XXX hack
166: return compare(a, b) == 0;
167: }
168:
169: public static final int COMPOUND = KeyStream.COMPOUND;
170: public static final int INTEGER = KeyStream.INTEGER;
171: public static final int STRING = KeyStream.STRING;
172: public static final int NULL = KeyStream.NULL;
173:
174: public int compare(byte[] a, byte[] b) {
175: return compare(a, 0, a.length, b, 0, b.length);
176: }
177:
178: //#ifdef DEBUG
179: public final int compare(byte[] a, int aoff, int alen, byte[] b,
180: int boff, int blen) {
181: try {
182: if (paranoid) {
183: checkKey(a, aoff, alen);
184: checkKey(b, boff, blen);
185: }
186: int ret = compare2(a, aoff, alen, b, boff, blen);
187: if (Trace.bit(6)) {
188: Debug.println("Compare " + asc.length + " fields, ret="
189: + ret + ": " + toString(a, aoff, alen) + "("
190: + Util.hexBytes(a, aoff, alen) + ") " + " vs "
191: + toString(b, boff, blen) + "("
192: + Util.hexBytes(b, boff, blen) + ") ");
193: //Debug.println(Util.stackTrace());
194: }
195: return ret;
196: } catch (RuntimeException t) {
197: Debug.print(t);
198: Debug.println("asc.len = " + asc.length);
199: Debug.println("a = " + toString(a, aoff, alen));
200: Debug.println("a = " + Util.hexBytes(a, aoff, alen));
201: Debug.println("b = " + toString(b, boff, blen));
202: Debug.println("b = " + Util.hexBytes(b, boff, blen));
203: throw t;
204: }
205: }
206:
207: public void checkKey(byte[] buf, int off, int len) {
208: if (getKeyLen(buf, off) != len) {
209: Debug.println(Util.strBytes(buf, off, len));
210: Debug.println(toString(buf, off, len));
211: throw new RuntimeException("bad key len: "
212: + getKeyLen(buf, off) + " vs " + len);
213: }
214: }
215:
216: final int compare2
217: //#else
218: //- public final int compare
219: //#endif
220: (byte[] a, int aoff, int alen, byte[] b, int boff, int blen) {
221: int i = 0;
222: int askip = 0;
223: int bskip = 0;
224: int scalar = 0;
225: while (i < asc.length) {
226: int ac = a[aoff++] & 0xff;
227: int bc = b[boff++] & 0xff;
228: final int atype = ac & 3;
229: final int btype = bc & 3;
230: int al = (ac >> 2) & 0x1f;
231: int bl = (bc >> 2) & 0x1f;
232: if ((ac & 0x80) != 0) {
233: al <<= 8;
234: al |= (a[aoff++] & 0xff);
235: }
236: if ((bc & 0x80) != 0) {
237: bl <<= 8;
238: bl |= (b[boff++] & 0xff);
239: }
240: //Debug.println("Field " + i + ": " + atype + " - " + btype);
241: //Debug.println("ac/al = " + ac + "/" + al + ", bc/bl = " + bc + "/" + bl);
242: switch ((atype << 2) | btype) {
243: case (COMPOUND << 2) | COMPOUND:
244: askip = al;
245: bskip = bl;
246: break;
247: case (INTEGER << 2) | INTEGER:
248: int signMask = 0xffffffff;
249: if (al > bl) {
250: int ab = a[aoff++];
251: if (ab != 0)
252: return (ab < 0 ? -1 : 1) * (asc[i] ? 1 : -1);
253: while (--al > bl) {
254: if (a[aoff++] != 0) {
255: return asc[i] ? 1 : -1;
256: }
257: }
258: signMask = 0xff;
259: }
260:
261: if (bl > al) {
262: int bb = b[boff++];
263: if (bb != 0)
264: return (bb < 0 ? 1 : -1) * (asc[i] ? 1 : -1);
265: while (--bl > al) {
266: if (b[boff++] != 0) {
267: return asc[i] ? -1 : 1;
268: }
269: }
270: signMask = 0xff;
271: }
272:
273: int neg = (a[aoff] < 0) ? -1 : 1;
274: int rneg = 1;
275: while (al-- > 0) {
276: int ab = a[aoff++] & signMask;
277: int bb = b[boff++] & signMask;
278: if (ab != bb) {
279: int xa = a[aoff - 1];
280: return (ab < bb ? 1 : -1) * (asc[i] ? -1 : 1)
281: * rneg;
282: }
283: rneg = neg;
284: signMask = 0xff;
285: }
286: break;
287: case (STRING << 2) | STRING:
288: while (al > 0 && bl > 0) {
289: int ab = a[aoff++] & 0xff;
290: int bb = b[boff++] & 0xff;
291: if (ab != bb) {
292: return (ab < bb ? 1 : -1) * (asc[i] ? -1 : 1);
293: }
294: al--;
295: bl--;
296: }
297: while (al-- > 0) {
298: if (a[aoff++] != 0)
299: return asc[i] ? 1 : -1;
300: }
301: while (bl-- > 0) {
302: if (b[boff++] != 0)
303: return asc[i] ? -1 : 1;
304: }
305: break;
306: case (NULL << 2) | NULL:
307: // length == 0: first null, otherwise last null
308: if (al == 0) {
309: if (bl != 0)
310: return -1;
311: } else {
312: if (bl == 0)
313: return 1;
314: }
315: break;
316: case (NULL << 2) | COMPOUND:
317: case (NULL << 2) | INTEGER:
318: case (NULL << 2) | STRING:
319: return al == 0 ? -1 : 1;
320: case (COMPOUND << 2) | NULL:
321: case (INTEGER << 2) | NULL:
322: case (STRING << 2) | NULL:
323: return bl == 0 ? 1 : -1;
324:
325: case (COMPOUND << 2) | INTEGER:
326: askip = al;
327: bskip = 1;
328: boff--;
329: break;
330: case (INTEGER << 2) | COMPOUND:
331: bskip = bl;
332: askip = 1;
333: aoff--;
334: break;
335:
336: case (STRING << 2) | INTEGER:
337: return 1;
338: case (INTEGER << 2) | STRING:
339: return -1;
340:
341: default:
342: throw new RuntimeException("Cardinality error");
343: }
344: askip--;
345: bskip--;
346: if (askip < 0) {
347: if (bskip < 0) {
348: // end of both compound fields
349: i++;
350: } else {
351: // end of a, more fields left in b
352: while (bskip-- >= 0) {
353: bc = b[boff++] & 0xff;
354: bl = (bc >> 2) & 0x1f;
355: if ((bc & 0x80) != 0) {
356: bc <<= 8;
357: bc |= (b[boff++] & 0xff);
358: }
359: for (int j = 0; j < bl; j++) {
360: if (b[boff++] != 0)
361: return -1;
362: }
363: i++;
364: }
365: }
366: } else {
367: if (bskip < 0) {
368: // end of b, more fields left in a
369: while (askip-- >= 0) {
370: ac = a[aoff++] & 0xff;
371: al = (ac >> 2) & 0x1f;
372: if ((ac & 0x80) != 0) {
373: ac <<= 8;
374: ac |= (a[aoff++] & 0xff);
375: }
376: for (int j = 0; j < al; j++) {
377: if (a[aoff++] != 0)
378: return 1;
379: }
380: i++;
381: }
382: } else {
383: // next compound field
384: }
385: }
386: }
387: return 0;
388: }
389:
390: public int getKeyLen(byte[] a, int aoff) {
391: int start = aoff;
392: int i = 0;
393: int skip = 0;
394: while (i < asc.length) {
395: int ac = a[aoff++] & 0xff;
396: final int atype = ac & 3;
397: int al = (ac >> 2) & 0x1f;
398: if ((ac & 0x80) != 0) {
399: al <<= 8;
400: al |= (a[aoff++] & 0xff);
401: }
402: switch (atype) {
403: case NULL:
404: break;
405: case INTEGER:
406: case STRING:
407: aoff += al;
408: break;
409: case COMPOUND:
410: skip = al;
411: break;
412: }
413: skip--;
414: if (skip < 0)
415: i++;
416: }
417: return aoff - start;
418: }
419:
420: //#ifdef DEBUG
421: public static String toStringHelper(byte[] key) {
422: return toStringHelper(key, 0, key.length);
423: }
424:
425: public String toString(byte[] key, int off, int xlen) {
426: return toStringHelper(key, off, xlen);
427: }
428:
429: public static String toStringHelper(byte[] key, int off, int xlen) {
430: StringBuffer sb = new StringBuffer();
431: int lim = off + xlen;
432: String delim = "";
433: String sdelim = "";
434: int clen = -1;
435: while (off < lim) {
436: clen--;
437: sb.append(delim);
438: sb.append(sdelim);
439: if (clen > 0)
440: sdelim = ",";
441: delim = ", ";
442: int c = key[off++] & 0xff;
443: int type = c & 3;
444: int len = (c >> 2) & 0x1f;
445: if ((c & 0x80) != 0) {
446: len <<= 8;
447: len |= key[off++];
448: }
449: //Debug.println("TYPE: " + type + ", off = " + off +
450: // ", len = " + len);
451: switch (type) {
452: case COMPOUND:
453: sb.append("{");
454: sdelim = "";
455: clen = len;
456: break;
457: case INTEGER:
458: sb.append("I(");
459: sb.append(Util.hexBytes(key, off, len));
460: sb.append(")");
461: off += len;
462: break;
463: case STRING:
464: sb.append("S(");
465: //sb.append(Util.hexBytes(key, off, len));
466: try {
467: sb.append(new String(key, off, len));
468: } catch (Throwable t) {
469: sb.append("key[" + off + ":" + len + "]:*****("
470: + new String(key) + ")");
471: }
472: sb.append(")");
473: off += len;
474: break;
475: case NULL:
476: sb.append("NULL");
477: break;
478: }
479: if (clen == 0) {
480: sb.append("}");
481: sdelim = "";
482: }
483: }
484: return sb.toString();
485: }
486:
487: public static void test1() throws IOException {
488: com.quadcap.sql.file.BlockFile f = new com.quadcap.sql.file.BlockFile(
489: "test1.bf", "rw", new java.util.Properties(), 4096, 256);
490: long root = f.newPage();
491: Key key = new Key(1);
492: com.quadcap.sql.index.Btree tree = new com.quadcap.sql.index.Btree(
493: f, key, root, true);
494: byte[] vk = new byte[5];
495: for (int i = 0; i < 40000; i++) {
496: byte[] r = makeRandomKey();
497: ByteUtil.putInt(vk, 0, i);
498: tree.set(r, vk);
499: if ((i % 1000) == 0)
500: System.out.print(".");
501: }
502: }
503:
504: static java.util.Random random = new java.util.Random(666);
505:
506: public static byte[] makeRandomKey() throws IOException {
507: ByteArrayOutputStream bos = new ByteArrayOutputStream();
508: KeyStream k = new KeyStream(bos, true);
509: StringBuffer sb = new StringBuffer();
510: int lim = 40 + random.nextInt(50);
511: for (int i = 0; i < lim; i++) {
512: sb.append((char) random.nextInt(255));
513: }
514: k.writeChars(sb.toString());
515: return bos.toByteArray();
516: }
517:
518: public static void main(String[] args) {
519: try {
520: test1();
521: } catch (Exception e) {
522: Debug.print(e);
523: }
524: }
525: //#endif
526: }
|