|
1 package com.quadcap.sql;
2
3
40
41 import java.io.ByteArrayOutputStream  ;
42 import java.io.IOException ;
43 import java.io.OutputStream ;
44
45 import java.sql.SQLException ;
46
47 import com.quadcap.sql.io.ObjectOutputStream;
48
49 import com.quadcap.sql.file.ByteUtil;
50 import com.quadcap.sql.file.SubPageManager;
51
52 import com.quadcap.sql.index.Comparator;
53
54 import com.quadcap.sql.types.KeyStream;
55 import com.quadcap.sql.types.Type;
56 import com.quadcap.sql.types.Value;
57 import com.quadcap.sql.types.ValueInteger;
58
59 import com.quadcap.util.Debug;
60 import com.quadcap.util.Util;
61
62
69 public class Key extends Comparator {
70 static final boolean paranoid = false;
72
74 boolean[] asc;
75
76 public Key(int cnt) {
77 asc = new boolean[cnt];
78 for (int i = 0; i < cnt; i++) asc[i] = true;
79 }
80
81 public Key(boolean[] asc) {
82 this.asc = asc;
83 }
84
85 public static byte[] makeKey(Tuple tuple, Row row, int[] map, long rowNum,
86 boolean doRowNum)
87 throws SQLException
88 {
89 if (false) {
91 StringBuffer sb = new StringBuffer ("makeKey(");
92 sb.append(row.toString());
93 sb.append(" (" + ((Object )row).toString());
94 sb.append(", [");
95 for (int i = 0; i < map.length; i++) {
96 if (i>0) sb.append(',');
97 sb.append(map[i]);
98 }
99 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 try {
110 ByteArrayOutputStream bos = new ByteArrayOutputStream ();
111 KeyStream out = new KeyStream(bos, Database.isCaseSensitive);
112 int cnt = 0;
114 if (map != null) {
116 cnt = map.length;
118 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 cnt = row.size();
132 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 cnt++;
142 }
144 byte[] ret = bos.toByteArray();
145 if (paranoid) {
147 Key k = new Key(cnt);
148 k.checkKey(ret, 0, ret.length);
149 }
150 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
164 public boolean compareNulls(byte[] a, byte[] b) {
165 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 public final int compare(byte[] a, int aoff, int alen,
180 byte[] b, 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=" + ret + ": " +
189 toString(a, aoff, alen) +
190 "(" + Util.hexBytes(a, aoff, alen) + ") " +
191 " vs " +
192 toString(b, boff, blen) +
193 "(" + Util.hexBytes(b, boff, blen) + ") ");
194 }
196 return ret;
197 } catch (RuntimeException t) {
198 Debug.print(t);
199 Debug.println("asc.len = " + asc.length);
200 Debug.println("a = " + toString(a, aoff, alen));
201 Debug.println("a = " + Util.hexBytes(a, aoff, alen));
202 Debug.println("b = " + toString(b, boff, blen));
203 Debug.println("b = " + Util.hexBytes(b, boff, blen));
204 throw t;
205 }
206 }
207
208 public void checkKey(byte[] buf, int off, int len) {
209 if (getKeyLen(buf, off) != len) {
210 Debug.println(Util.strBytes(buf, off, len));
211 Debug.println(toString(buf, off, len));
212 throw new RuntimeException ("bad key len: " +
213 getKeyLen(buf, off) + " vs " +
214 len);
215 }
216 }
217
218 final int compare2
219 (byte[] a, int aoff, int alen,
223 byte[] b, int boff, int blen)
224 {
225 int i = 0;
226 int askip = 0;
227 int bskip = 0;
228 int scalar = 0;
229 while (i < asc.length) {
230 int ac = a[aoff++] & 0xff;
231 int bc = b[boff++] & 0xff;
232 final int atype = ac & 3;
233 final int btype = bc & 3;
234 int al = (ac >> 2) & 0x1f;
235 int bl = (bc >> 2) & 0x1f;
236 if ((ac & 0x80) != 0) {
237 al <<= 8;
238 al |= (a[aoff++] & 0xff);
239 }
240 if ((bc & 0x80) != 0) {
241 bl <<= 8;
242 bl |= (b[boff++] & 0xff);
243 }
244 switch ((atype << 2) | btype) {
247 case (COMPOUND << 2) | COMPOUND:
248 askip = al;
249 bskip = bl;
250 break;
251 case (INTEGER << 2) | INTEGER:
252 int signMask = 0xffffffff;
253 if (al > bl) {
254 int ab = a[aoff++];
255 if (ab != 0) return (ab < 0 ? -1 : 1) * (asc[i] ? 1 : -1);
256 while (--al > bl) {
257 if (a[aoff++] != 0) {
258 return asc[i] ? 1 : -1;
259 }
260 }
261 signMask = 0xff;
262 }
263
264 if (bl > al) {
265 int bb = b[boff++];
266 if (bb != 0) return (bb < 0 ? 1 : -1) * (asc[i] ? 1 : -1);
267 while (--bl > al) {
268 if (b[boff++] != 0) {
269 return asc[i] ? -1 : 1;
270 }
271 }
272 signMask = 0xff;
273 }
274
275 int neg = (a[aoff] < 0) ? -1 : 1;
276 int rneg = 1;
277 while (al-- > 0) {
278 int ab = a[aoff++] & signMask;
279 int bb = b[boff++] & signMask;
280 if (ab != bb) {
281 int xa = a[aoff-1];
282 return (ab < bb ? 1 : -1) * (asc[i] ? -1 : 1) * rneg;
283 }
284 rneg = neg;
285 signMask = 0xff;
286 }
287 break;
288 case (STRING << 2) | STRING:
289 while (al > 0 && bl > 0) {
290 int ab = a[aoff++] & 0xff;
291 int bb = b[boff++] & 0xff;
292 if (ab != bb) {
293 return (ab < bb ? 1 : -1) * (asc[i] ? -1 : 1);
294 }
295 al--;
296 bl--;
297 }
298 while (al-- > 0) {
299 if (a[aoff++] != 0) return asc[i] ? 1 : -1;
300 }
301 while (bl-- > 0) {
302 if (b[boff++] != 0) return asc[i] ? -1 : 1;
303 }
304 break;
305 case (NULL << 2) | NULL:
306 if (al == 0) {
308 if (bl != 0) return -1;
309 } else {
310 if (bl == 0) return 1;
311 }
312 break;
313 case (NULL << 2) | COMPOUND:
314 case (NULL << 2) | INTEGER:
315 case (NULL << 2) | STRING:
316 return al == 0 ? -1 : 1;
317 case (COMPOUND << 2) | NULL:
318 case (INTEGER << 2) | NULL:
319 case (STRING << 2) | NULL:
320 return bl == 0 ? 1 : -1;
321
322 case (COMPOUND << 2) | INTEGER:
323 askip = al;
324 bskip = 1;
325 boff--;
326 break;
327 case (INTEGER << 2) | COMPOUND:
328 bskip = bl;
329 askip = 1;
330 aoff--;
331 break;
332
333 case (STRING << 2) | INTEGER:
334 return 1;
335 case (INTEGER << 2) | STRING:
336 return -1;
337
338 default:
339 throw new RuntimeException ("Cardinality error");
340 }
341 askip--;
342 bskip--;
343 if (askip < 0) {
344 if (bskip < 0) {
345 i++;
347 } else {
348 while (bskip-- >= 0) {
350 bc = b[boff++] & 0xff;
351 bl = (bc >> 2) & 0x1f;
352 if ((bc & 0x80) != 0) {
353 bc <<= 8;
354 bc |= (b[boff++] & 0xff);
355 }
356 for (int j = 0; j < bl; j++) {
357 if (b[boff++] != 0) return -1;
358 }
359 i++;
360 }
361 }
362 } else {
363 if (bskip < 0) {
364 while (askip-- >= 0) {
366 ac = a[aoff++] & 0xff;
367 al = (ac >> 2) & 0x1f;
368 if ((ac & 0x80) != 0) {
369 ac <<= 8;
370 ac |= (a[aoff++] & 0xff);
371 }
372 for (int j = 0; j < al; j++) {
373 if (a[aoff++] != 0) return 1;
374 }
375 i++;
376 }
377 } else {
378 }
380 }
381 }
382 return 0;
383 }
384
385 public int getKeyLen(byte[] a, int aoff) {
386 int start = aoff;
387 int i = 0;
388 int skip = 0;
389 while (i < asc.length) {
390 int ac = a[aoff++] & 0xff;
391 final int atype = ac & 3;
392 int al = (ac >> 2) & 0x1f;
393 if ((ac & 0x80) != 0) {
394 al <<= 8;
395 al |= (a[aoff++] & 0xff);
396 }
397 switch (atype) {
398 case NULL:
399 break;
400 case INTEGER:
401 case STRING:
402 aoff += al;
403 break;
404 case COMPOUND:
405 skip = al;
406 break;
407 }
408 skip--;
409 if (skip < 0) i++;
410 }
411 return aoff - start;
412 }
413
414 public static String toStringHelper(byte[] key) {
416 return toStringHelper(key, 0, key.length);
417 }
418
419 public String toString(byte[] key, int off, int xlen) {
420 return toStringHelper(key, off, xlen);
421 }
422
423 public static String toStringHelper(byte[] key, int off, int xlen) {
424 StringBuffer sb = new StringBuffer ();
425 int lim = off + xlen;
426 String delim = "";
427 String sdelim = "";
428 int clen = -1;
429 while (off < lim) {
430 clen--;
431 sb.append(delim);
432 sb.append(sdelim);
433 if (clen > 0) sdelim =",";
434 delim = ", ";
435 int c = key[off++] & 0xff;
436 int type = c & 3;
437 int len = (c >> 2) & 0x1f;
438 if ((c & 0x80) != 0) {
439 len <<= 8;
440 len |= key[off++];
441 }
442 switch (type) {
445 case COMPOUND:
446 sb.append("{");
447 sdelim = "";
448 clen = len;
449 break;
450 case INTEGER:
451 sb.append("I(");
452 sb.append(Util.hexBytes(key, off, len));
453 sb.append(")");
454 off += len;
455 break;
456 case STRING:
457 sb.append("S(");
458 try {
460 sb.append(new String (key, off, len));
461 } catch (Throwable t) {
462 sb.append("key[" + off + ":" + len + "]:*****(" + new String (key) + ")");
463 }
464 sb.append(")");
465 off += len;
466 break;
467 case NULL:
468 sb.append("NULL");
469 break;
470 }
471 if (clen == 0) {
472 sb.append("}");
473 sdelim = "";
474 }
475 }
476 return sb.toString();
477 }
478
479 public static void test1() throws IOException {
480 com.quadcap.sql.file.BlockFile f =
481 new com.quadcap.sql.file.BlockFile("test1.bf", "rw",
482 new java.util.Properties (),
483 4096, 256);
484 long root = f.newPage();
485 Key key = new Key(1);
486 com.quadcap.sql.index.Btree tree = new com.quadcap.sql.index.Btree(f, key, root, true);
487 byte[] vk = new byte[5];
488 for (int i = 0; i < 40000; i++) {
489 byte[] r = makeRandomKey();
490 ByteUtil.putInt(vk, 0, i);
491 tree.set(r, vk);
492 if ((i % 1000) == 0) System.out.print(".");
493 }
494 }
495
496 static java.util.Random random = new java.util.Random (666);
497
498 public static byte[] makeRandomKey() throws IOException {
499 ByteArrayOutputStream bos = new ByteArrayOutputStream ();
500 KeyStream k = new KeyStream(bos, true);
501 StringBuffer sb = new StringBuffer ();
502 int lim = 40 + random.nextInt(50);
503 for (int i = 0; i < lim; i++) {
504 sb.append((char)random.nextInt(255));
505 }
506 k.writeChars(sb.toString());
507 return bos.toByteArray();
508 }
509
510 public static void main(String [] args) {
511 try {
512 test1();
513 } catch (Exception e) {
514 Debug.print(e);
515 }
516 }
517 }
519 |
Popular Tags |
Java API By Example, From Geeks To Geeks.