File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\DataUtils.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.mvstore;
8
9 import java.io.EOFException;
10 import java.io.IOException;
11 import java.io.OutputStream;
12 import java.nio.ByteBuffer;
13 import java.nio.channels.FileChannel;
14 import java.util.ArrayList;
15 import java.util.Collections;
16 import java.util.HashMap;
17 import org.h2.util.New;
18
19 /**
20 * Utility methods
21 */
22 public class DataUtils {
23
24 /**
25 * The type for leaf page.
26 */
27 public static final int PAGE_TYPE_LEAF = 0;
28
29 /**
30 * The type for node page.
31 */
32 public static final int PAGE_TYPE_NODE = 1;
33
34 /**
35 * The bit mask for compressed pages.
36 */
37 public static final int PAGE_COMPRESSED = 2;
38
39 /**
40 * The maximum length of a variable size int.
41 */
42 public static final int MAX_VAR_INT_LEN = 5;
43
44 /**
45 * The maximum length of a variable size long.
46 */
47 public static final int MAX_VAR_LONG_LEN = 10;
48
49 /**
50 * The maximum integer that needs less space when using variable size
51 * encoding (only 3 bytes instead of 4).
52 */
53 public static final int COMPRESSED_VAR_INT_MAX = 0x1fffff;
54
55 /**
56 * The maximum long that needs less space when using variable size
57 * encoding (only 7 bytes instead of 8).
58 */
59 public static final long COMPRESSED_VAR_LONG_MAX = 0x1ffffffffffffL;
60
61 /**
62 * The estimated number of bytes used per page object.
63 */
64 public static final int PAGE_MEMORY = 128;
65
66 /**
67 * The estimated number of bytes used per child entry.
68 */
69 public static final int PAGE_MEMORY_CHILD = 16;
70
71 /**
72 * Get the length of the variable size int.
73 *
74 * @param x the value
75 * @return the length in bytes
76 */
77 public static int getVarIntLen(int x) {
78 if ((x & (-1 << 7)) == 0) {
79 return 1;
80 } else if ((x & (-1 << 14)) == 0) {
81 return 2;
82 } else if ((x & (-1 << 21)) == 0) {
83 return 3;
84 } else if ((x & (-1 << 28)) == 0) {
85 return 4;
86 }
87 return 5;
88 }
89
90 /**
91 * Get the length of the variable size long.
92 *
93 * @param x the value
94 * @return the length in bytes
95 */
96 public static int getVarLongLen(long x) {
97 int i = 1;
98 while (true) {
99 x >>>= 7;
100 if (x == 0) {
101 return i;
102 }
103 i++;
104 }
105 }
106
107 /**
108 * Read a variable size int.
109 *
110 * @param buff the source buffer
111 * @return the value
112 */
113 public static int readVarInt(ByteBuffer buff) {
114 int b = buff.get();
115 if (b >= 0) {
116 return b;
117 }
118 // a separate function so that this one can be inlined
119 return readVarIntRest(buff, b);
120 }
121
122 private static int readVarIntRest(ByteBuffer buff, int b) {
123 int x = b & 0x7f;
124 b = buff.get();
125 if (b >= 0) {
126 return x | (b << 7);
127 }
128 x |= (b & 0x7f) << 7;
129 b = buff.get();
130 if (b >= 0) {
131 return x | (b << 14);
132 }
133 x |= (b & 0x7f) << 14;
134 b = buff.get();
135 if (b >= 0) {
136 return x | b << 21;
137 }
138 x |= ((b & 0x7f) << 21) | (buff.get() << 28);
139 return x;
140 }
141
142 /**
143 * Read a variable size long.
144 *
145 * @param buff the source buffer
146 * @return the value
147 */
148 public static long readVarLong(ByteBuffer buff) {
149 long x = buff.get();
150 if (x >= 0) {
151 return x;
152 }
153 x &= 0x7f;
154 for (int s = 7; s < 64; s += 7) {
155 long b = buff.get();
156 x |= (b & 0x7f) << s;
157 if (b >= 0) {
158 break;
159 }
160 }
161 return x;
162 }
163
164 /**
165 * Write a variable size int.
166 *
167 * @param out the output stream
168 * @param x the value
169 */
170 public static void writeVarInt(OutputStream out, int x) throws IOException {
171 while ((x & ~0x7f) != 0) {
172 out.write((byte) (0x80 | (x & 0x7f)));
173 x >>>= 7;
174 }
175 out.write((byte) x);
176 }
177
178 /**
179 * Write a variable size int.
180 *
181 * @param buff the source buffer
182 * @param x the value
183 */
184 public static void writeVarInt(ByteBuffer buff, int x) {
185 while ((x & ~0x7f) != 0) {
186 buff.put((byte) (0x80 | (x & 0x7f)));
187 x >>>= 7;
188 }
189 buff.put((byte) x);
190 }
191
192 /**
193 * Write characters from a string (without the length).
194 *
195 * @param buff the target buffer
196 * @param s the string
197 * @param len the number of characters
198 */
199 public static void writeStringData(ByteBuffer buff, String s, int len) {
200 for (int i = 0; i < len; i++) {
201 int c = s.charAt(i);
202 if (c < 0x80) {
203 buff.put((byte) c);
204 } else if (c >= 0x800) {
205 buff.put((byte) (0xe0 | (c >> 12)));
206 buff.put((byte) (((c >> 6) & 0x3f)));
207 buff.put((byte) (c & 0x3f));
208 } else {
209 buff.put((byte) (0xc0 | (c >> 6)));
210 buff.put((byte) (c & 0x3f));
211 }
212 }
213 }
214
215 /**
216 * Read a string.
217 *
218 * @param buff the source buffer
219 * @param len the number of characters
220 * @return the value
221 */
222 public static String readString(ByteBuffer buff, int len) {
223 char[] chars = new char[len];
224 for (int i = 0; i < len; i++) {
225 int x = buff.get() & 0xff;
226 if (x < 0x80) {
227 chars[i] = (char) x;
228 } else if (x >= 0xe0) {
229 chars[i] = (char) (((x & 0xf) << 12) + ((buff.get() & 0x3f) << 6) + (buff.get() & 0x3f));
230 } else {
231 chars[i] = (char) (((x & 0x1f) << 6) + (buff.get() & 0x3f));
232 }
233 }
234 return new String(chars);
235 }
236
237 /**
238 * Write a variable size long.
239 *
240 * @param buff the target buffer
241 * @param x the value
242 */
243 public static void writeVarLong(ByteBuffer buff, long x) {
244 while ((x & ~0x7f) != 0) {
245 buff.put((byte) (0x80 | (x & 0x7f)));
246 x >>>= 7;
247 }
248 buff.put((byte) x);
249 }
250
251 /**
252 * Write a variable size long.
253 *
254 * @param out the output stream
255 * @param x the value
256 */
257 public static void writeVarLong(OutputStream out, long x) throws IOException {
258 while ((x & ~0x7f) != 0) {
259 out.write((byte) (0x80 | (x & 0x7f)));
260 x >>>= 7;
261 }
262 out.write((byte) x);
263 }
264
265 /**
266 * Copy the elements of an array, with a gap.
267 *
268 * @param src the source array
269 * @param dst the target array
270 * @param oldSize the size of the old array
271 * @param gapIndex the index of the gap
272 */
273 public static void copyWithGap(Object src, Object dst, int oldSize, int gapIndex) {
274 if (gapIndex > 0) {
275 System.arraycopy(src, 0, dst, 0, gapIndex);
276 }
277 if (gapIndex < oldSize) {
278 System.arraycopy(src, gapIndex, dst, gapIndex + 1, oldSize - gapIndex);
279 }
280 }
281
282 /**
283 * Copy the elements of an array, and remove one element.
284 *
285 * @param src the source array
286 * @param dst the target array
287 * @param oldSize the size of the old array
288 * @param removeIndex the index of the entry to remove
289 */
290 public static void copyExcept(Object src, Object dst, int oldSize, int removeIndex) {
291 if (removeIndex > 0 && oldSize > 0) {
292 System.arraycopy(src, 0, dst, 0, removeIndex);
293 }
294 if (removeIndex < oldSize) {
295 System.arraycopy(src, removeIndex + 1, dst, removeIndex, oldSize - removeIndex - 1);
296 }
297 }
298
299 /**
300 * Read from a file channel until the buffer is full, or end-of-file
301 * has been reached. The buffer is rewind at the end.
302 *
303 * @param file the file channel
304 * @param pos the absolute position within the file
305 * @param dst the byte buffer
306 */
307 public static void readFully(FileChannel file, long pos, ByteBuffer dst) throws IOException {
308 do {
309 int len = file.read(dst, pos);
310 if (len < 0) {
311 throw new EOFException();
312 }
313 pos += len;
314 } while (dst.remaining() > 0);
315 dst.rewind();
316 }
317
318 /**
319 * Write to a file channel.
320 *
321 * @param file the file channel
322 * @param pos the absolute position within the file
323 * @param src the source buffer
324 */
325 public static void writeFully(FileChannel file, long pos, ByteBuffer src) throws IOException {
326 int off = 0;
327 do {
328 int len = file.write(src, pos + off);
329 off += len;
330 } while (src.remaining() > 0);
331 }
332
333
334 /**
335 * Convert the length to a length code 0..31. 31 means more than 1 MB.
336 *
337 * @param len the length
338 * @return the length code
339 */
340 public static int encodeLength(int len) {
341 if (len <= 32) {
342 return 0;
343 }
344 int x = len;
345 int shift = 0;
346 while (x > 3) {
347 shift++;
348 x = (x >> 1) + (x & 1);
349 }
350 shift = Math.max(0, shift - 4);
351 int code = (shift << 1) + (x & 1);
352 return Math.min(31, code);
353 }
354
355 /**
356 * Get the chunk id from the position.
357 *
358 * @param pos the position
359 * @return the chunk id
360 */
361 public static int getPageChunkId(long pos) {
362 return (int) (pos >>> 38);
363 }
364
365 /**
366 * Get the maximum length for the given code.
367 * For the code 31, Integer.MAX_VALUE is returned.
368 *
369 * @param pos the position
370 * @return the maximum length
371 */
372 public static int getPageMaxLength(long pos) {
373 int code = (int) ((pos >> 1) & 31);
374 if (code == 31) {
375 return Integer.MAX_VALUE;
376 }
377 return (2 + (code & 1)) << ((code >> 1) + 4);
378 }
379
380 /**
381 * Get the offset from the position.
382 *
383 * @param pos the position
384 * @return the offset
385 */
386 public static int getPageOffset(long pos) {
387 return (int) (pos >> 6);
388 }
389
390 /**
391 * Get the page type from the position.
392 *
393 * @param pos the position
394 * @return the page type (PAGE_TYPE_NODE or PAGE_TYPE_LEAF)
395 */
396 public static int getPageType(long pos) {
397 return ((int) pos) & 1;
398 }
399
400 /**
401 * Get the position of this page. The following information is encoded in
402 * the position: the chunk id, the offset, the maximum length, and the type
403 * (node or leaf).
404 *
405 * @param chunkId the chunk id
406 * @param offset the offset
407 * @param length the length
408 * @param type the page type (1 for node, 0 for leaf)
409 * @return the position
410 */
411 public static long getPagePos(int chunkId, int offset, int length, int type) {
412 long pos = (long) chunkId << 38;
413 pos |= (long) offset << 6;
414 pos |= encodeLength(length) << 1;
415 pos |= type;
416 return pos;
417 }
418
419 /**
420 * Calculate a check value for the given integer. A check value is mean to
421 * verify the data is consistent with a high probability, but not meant to
422 * protect against media failure or deliberate changes.
423 *
424 * @param x the value
425 * @return the check value
426 */
427 public static short getCheckValue(int x) {
428 return (short) ((x >> 16) ^ x);
429 }
430
431 /**
432 * Append a map to the string builder, sorted by key.
433 *
434 * @param buff the target buffer
435 * @param map the map
436 * @return the string builder
437 */
438 public static StringBuilder appendMap(StringBuilder buff, HashMap<String, ?> map) {
439 ArrayList<String> list = New.arrayList(map.keySet());
440 Collections.sort(list);
441 for (String k : list) {
442 appendMap(buff, k, map.get(k));
443 }
444 return buff;
445 }
446
447 /**
448 * Append a key-value pair to the string builder. Keys may not contain a
449 * colon. Values that contain a comma or a double quote are enclosed in
450 * double quotes, with special characters escaped using a backslash.
451 *
452 * @param buff the target buffer
453 * @param key the key
454 * @param value the value
455 */
456 public static void appendMap(StringBuilder buff, String key, Object value) {
457 if (buff.length() > 0) {
458 buff.append(',');
459 }
460 buff.append(key).append(':');
461 String v = value.toString();
462 if (v.indexOf(',') < 0 && v.indexOf('\"') < 0) {
463 buff.append(value);
464 } else {
465 buff.append('\"');
466 for (int i = 0, size = v.length(); i < size; i++) {
467 char c = v.charAt(i);
468 if (c == '\"') {
469 buff.append('\\');
470 }
471 buff.append(c);
472 }
473 buff.append('\"');
474 }
475 }
476
477 /**
478 * Parse a key-value pair list.
479 *
480 * @param s the list
481 * @return the map
482 */
483 public static HashMap<String, String> parseMap(String s) {
484 HashMap<String, String> map = New.hashMap();
485 for (int i = 0, size = s.length(); i < size;) {
486 int startKey = i;
487 i = s.indexOf(':', i);
488 String key = s.substring(startKey, i++);
489 StringBuilder buff = new StringBuilder();
490 while (i < size) {
491 char c = s.charAt(i++);
492 if (c == ',') {
493 break;
494 } else if (c == '\"') {
495 while (i < size) {
496 c = s.charAt(i++);
497 if (c == '\\') {
498 c = s.charAt(i++);
499 } else if (c == '\"') {
500 break;
501 }
502 buff.append(c);
503 }
504 } else {
505 buff.append(c);
506 }
507 }
508 map.put(key, buff.toString());
509 }
510 return map;
511 }
512
513 /**
514 * Calculate the Fletcher32 checksum.
515 *
516 * @param bytes the bytes
517 * @param length the message length (must be a multiple of 2)
518 * @return the checksum
519 */
520 public static int getFletcher32(byte[] bytes, int length) {
521 int s1 = 0xffff, s2 = 0xffff;
522 for (int i = 0; i < length;) {
523 for (int end = Math.min(i + 718, length); i < end;) {
524 int x = ((bytes[i++] & 0xff) << 8) | (bytes[i++] & 0xff);
525 s2 += s1 += x;
526 }
527 s1 = (s1 & 0xffff) + (s1 >>> 16);
528 s2 = (s2 & 0xffff) + (s2 >>> 16);
529 }
530 s1 = (s1 & 0xffff) + (s1 >>> 16);
531 s2 = (s2 & 0xffff) + (s2 >>> 16);
532 return (s2 << 16) | s1;
533 }
534
535 }
536