File: btree.c

package info (click to toggle)
libmysofa 0.6~dfsg0-3
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 14,384 kB
  • sloc: ansic: 5,482; sh: 18; makefile: 13
file content (365 lines) | stat: -rw-r--r-- 11,914 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
/*

  Copyright 2016 Christian Hoene, Symonics GmbH
 
*/

#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "reader.h"

/*
 *
 00000370  42 54 4c 46 00 08 00 5b  01 00 00 00 2d 00 00 07  |BTLF...[....-...|
 00000380  00 00 00 f8 ea 72 15 00  c9 03 00 00 00 26 00 00  |.....r.......&..|
 00000390  14 00 00 00 32 32 7c 17  00 22 02 00 00 00 32 00  |....22|.."....2.|
 000003a0  00 0b 00 00 00 07 ef 9c  26 00 bb 01 00 00 00 46  |........&......F|
 000003b0  00 00 09 00 00 00 e5 f6  ba 26 00 45 03 00 00 00  |.........&.E....|
 000003c0  34 00 00 11 00 00 00 f6  71 f0 2e 00 a3 02 00 00  |4.......q.......|
 000003d0  00 3e 00 00 0d 00 00 00  61 36 dc 36 00 79 03 00  |.>......a6.6.y..|
 000003e0  00 00 35 00 00 12 00 00  00 97 1b 4e 45 00 88 01  |..5........NE...|
 000003f0  00 00 00 33 00 00 08 00  00 00 56 d7 d0 47 00 ae  |...3......V..G..|
 00000400  03 00 00 00 1b 00 00 13  00 00 00 2f 03 50 5a 00  |.........../.PZ.|
 00000410  22 01 00 00 00 39 00 00  06 00 00 00 b7 88 37 66  |"....9........7f|
 00000420  00 01 03 00 00 00 28 00  00 0f 00 00 00 dc aa 47  |......(........G|
 00000430  66 00 16 04 00 00 00 2c  00 00 15 00 00 00 6b 54  |f......,......kT|
 00000440  7d 77 00 fd 00 00 00 00  25 00 00 05 00 00 00 7d  |}w......%......}|
 00000450  0c 8c 9e 00 29 03 00 00  00 1c 00 00 10 00 00 00  |....)...........|
 00000460  4c f3 0e a0 00 16 00 00  00 00 25 00 00 00 00 00  |L.........%.....|
 00000470  00 e7 30 2d ab 00 01 02  00 00 00 21 00 00 0a 00  |..0-.......!....|
 00000480  00 00 35 b5 69 b0 00 e1  02 00 00 00 20 00 00 0e  |..5.i....... ...|
 00000490  00 00 00 2b c5 8b c4 00  3b 00 00 00 00 20 00 00  |...+....;.... ..|
 000004a0  01 00 00 00 09 a0 74 cc  00 93 00 00 00 00 2f 00  |......t......./.|
 000004b0  00 03 00 00 00 3f 48 ef  d6 00 5b 00 00 00 00 38  |.....?H...[....8|
 000004c0  00 00 02 00 00 00 f1 7e  7d dd 00 54 02 00 00 00  |.......~}..T....|
 000004d0  4f 00 00 0c 00 00 00 48  35 ff f5 00 c2 00 00 00  |O......H5.......|
 000004e0  00 3b 00 00 04 00 00 00  ad 61 4e ff 63 42 f7 73  |.;.......aN.cB.s|
 000004f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 *

 00000570  42 54 4c 46 00 09 00 16  00 00 00 00 25 00 00 00  |BTLF........%...|
 00000580  00 00 00 00 3b 00 00 00  00 20 00 00 01 00 00 00  |....;.... ......|
 00000590  00 5b 00 00 00 00 38 00  00 02 00 00 00 00 93 00  |.[....8.........|
 000005a0  00 00 00 2f 00 00 03 00  00 00 00 c2 00 00 00 00  |.../............|
 000005b0  3b 00 00 04 00 00 00 00  fd 00 00 00 00 25 00 00  |;............%..|
 000005c0  05 00 00 00 00 22 01 00  00 00 39 00 00 06 00 00  |....."....9.....|
 000005d0  00 00 5b 01 00 00 00 2d  00 00 07 00 00 00 00 88  |..[....-........|
 000005e0  01 00 00 00 33 00 00 08  00 00 00 00 bb 01 00 00  |....3...........|
 000005f0  00 46 00 00 09 00 00 00  00 01 02 00 00 00 21 00  |.F............!.|
 00000600  00 0a 00 00 00 00 22 02  00 00 00 32 00 00 0b 00  |......"....2....|
 00000610  00 00 00 54 02 00 00 00  4f 00 00 0c 00 00 00 00  |...T....O.......|
 00000620  a3 02 00 00 00 3e 00 00  0d 00 00 00 00 e1 02 00  |.....>..........|
 00000630  00 00 20 00 00 0e 00 00  00 00 01 03 00 00 00 28  |.. ............(|
 00000640  00 00 0f 00 00 00 00 29  03 00 00 00 1c 00 00 10  |.......)........|
 00000650  00 00 00 00 45 03 00 00  00 34 00 00 11 00 00 00  |....E....4......|
 00000660  00 79 03 00 00 00 35 00  00 12 00 00 00 00 ae 03  |.y....5.........|
 00000670  00 00 00 1b 00 00 13 00  00 00 00 c9 03 00 00 00  |................|
 00000680  26 00 00 14 00 00 00 00  16 04 00 00 00 2c 00 00  |&............,..|
 00000690  15 00 00 00 d3 c7 19 a0  00 00 00 00 00 00 00 00  |................|
 000006a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

*/

static int readBTLF(struct READER *reader, struct BTREE *btree,
		    int number_of_records, union RECORD *records) {

	int i;

	uint8_t type, message_flags;
	uint32_t creation_order, hash_of_name;
	uint64_t heap_id;

	char buf[4];

	UNUSED(heap_id);
	UNUSED(hash_of_name);
	UNUSED(creation_order);
	UNUSED(message_flags);

	/* read signature */
	if (fread(buf, 1, 4, reader->fhd) != 4 || strncmp(buf, "BTLF", 4)) {
		log("cannot read signature of BTLF\n");
		return MYSOFA_INVALID_FORMAT;
	} log("%08lX %.4s\n", (uint64_t )ftell(reader->fhd) - 4, buf);

	if (fgetc(reader->fhd) != 0) {
		log("object BTLF must have version 0\n");
		return MYSOFA_INVALID_FORMAT;
	}

	type = (uint8_t)fgetc(reader->fhd);

	for (i = 0; i < number_of_records; i++) {

		switch (type) {
		case 5:
			records->type5.hash_of_name = (uint32_t)readValue(reader, 4);
			records->type5.heap_id = readValue(reader, 7);
			log(" type5 %08X %14lX\n", records->type5.hash_of_name,
			    records->type5.heap_id);
			records++;
			break;

		case 6:
			/*creation_order = */readValue(reader, 8);
			/*heap_id = */readValue(reader, 7);
			break;

		case 8:
			/*heap_id = */readValue(reader, 8);
			/*message_flags = */fgetc(reader->fhd);
			/*creation_order = */readValue(reader, 4);
			/*hash_of_name = */readValue(reader, 4);
			break;

		case 9:
			/*heap_id = */readValue(reader, 8);
			/*message_flags = */fgetc(reader->fhd);
			/*creation_order = */readValue(reader, 4);
			break;

		default:
			log("object BTLF has unknown type %d\n", type);
			return MYSOFA_INVALID_FORMAT;
		}
	}

/*	fseeko(reader->fhd, bthd->root_node_address + bthd->node_size, SEEK_SET); skip checksum */

	return MYSOFA_OK;
}

/*  III.A.2. Disk Format: Level 1A2 - Version 2 B-trees

    000002d0  32 1d 42 54 48 44 00 08  00 02 00 00 11 00 00 00  |2.BTHD..........|
    000002e0  64 28 70 03 00 00 00 00  00 00 16 00 16 00 00 00  |d(p.............|
    000002f0  00 00 00 00 30 12 d9 6e  42 54 48 44 00 09 00 02  |....0..nBTHD....|
    00000300  00 00 0d 00 00 00 64 28  70 05 00 00 00 00 00 00  |......d(p.......|
    00000310  16 00 16 00 00 00 00 00  00 00 e2 0d 76 5c 46 53  |............v\FS|

*/

int btreeRead(struct READER *reader, struct BTREE *btree) {
	char buf[4];

	/* read signature */
	if (fread(buf, 1, 4, reader->fhd) != 4 || strncmp(buf, "BTHD", 4)) {
		log("cannot read signature of BTHD\n");
		return MYSOFA_INVALID_FORMAT;
	} log("%08lX %.4s\n", (uint64_t )ftell(reader->fhd) - 4, buf);

	if (fgetc(reader->fhd) != 0) {
		log("object BTHD must have version 0\n");
		return MYSOFA_INVALID_FORMAT;
	}

	btree->type = (uint8_t)fgetc(reader->fhd);
	btree->node_size = (uint32_t)readValue(reader, 4);
	btree->record_size = (uint16_t)readValue(reader, 2);
	btree->depth = (uint16_t)readValue(reader, 2);

	btree->split_percent = (uint8_t)fgetc(reader->fhd);
	btree->merge_percent = (uint8_t)fgetc(reader->fhd);
	btree->root_node_address = (uint64_t)readValue(reader,
					     reader->superblock.size_of_offsets);
	btree->number_of_records = (uint16_t)readValue(reader, 2);
	if(btree->number_of_records>0x1000)
			return MYSOFA_UNSUPPORTED_FORMAT;
	btree->total_number = (uint64_t)readValue(reader, reader->superblock.size_of_lengths);

	/*	fseek(reader->fhd, 4, SEEK_CUR);  skip checksum */

	if(btree->total_number > 0x10000000)
		return MYSOFA_NO_MEMORY;
	btree->records = malloc(sizeof(btree->records[0]) * btree->total_number);
	if (!btree->records)
		return MYSOFA_NO_MEMORY;
	memset(btree->records, 0, sizeof(btree->records[0]) * btree->total_number);

	/* read records */
	if(fseek(reader->fhd, btree->root_node_address, SEEK_SET)<0)
		return errno;
	return readBTLF(reader, btree, btree->number_of_records, btree->records);
}

void btreeFree(struct BTREE *btree) {
	free(btree->records);
}

/*  III.A.1. Disk Format: Level 1A1 - Version 1 B-trees
 *
 */

int treeRead(struct READER *reader, struct DATAOBJECT *data) {

	int i, j, err, olen, elements, size, x, y, z, b, e, dy, dz, sx, sy, sz, dzy,
		szy;
	char *input, *output;

	uint8_t node_type, node_level;
	uint16_t entries_used;
	uint32_t size_of_chunk;
	uint32_t filter_mask;
	uint64_t address_of_left_sibling, address_of_right_sibling, start[4],
		child_pointer, key, store;

	char buf[4];

	UNUSED(node_level);
	UNUSED(address_of_right_sibling);
	UNUSED(address_of_left_sibling);
	UNUSED(key);

	if (data->ds.dimensionality > 3) {
		log("TREE dimensions > 3");
		return MYSOFA_INVALID_FORMAT;
	}

	/* read signature */
	if (fread(buf, 1, 4, reader->fhd) != 4 || strncmp(buf, "TREE", 4)) {
		log("cannot read signature of TREE\n");
		return MYSOFA_INVALID_FORMAT;
	} log("%08lX %.4s\n", (uint64_t )ftell(reader->fhd) - 4, buf);

	node_type = (uint8_t)fgetc(reader->fhd);
	node_level = (uint8_t)fgetc(reader->fhd);
	entries_used = (uint16_t)readValue(reader, 2);
	if(entries_used>0x1000)
		return MYSOFA_UNSUPPORTED_FORMAT;
	address_of_left_sibling = readValue(reader,
					    reader->superblock.size_of_offsets);
	address_of_right_sibling = readValue(reader,
					     reader->superblock.size_of_offsets);

	elements = 1;
	for (j = 0; j < data->ds.dimensionality; j++)
		elements *= data->datalayout_chunk[j];
	dy = data->datalayout_chunk[1];
	dz = data->datalayout_chunk[2];
	sx = data->ds.dimension_size[0];
	sy = data->ds.dimension_size[1];
	sz = data->ds.dimension_size[2];
	dzy = dz * dy;
	szy = sz * sy;
	size = data->datalayout_chunk[data->ds.dimensionality];

	log("elements %d size %d\n",elements,size);

	if (!(output = malloc(elements * size))) {
		return MYSOFA_NO_MEMORY;
	}

	for (e = 0; e < entries_used * 2; e++) {
		if (node_type == 0) {
			key = readValue(reader, reader->superblock.size_of_lengths);
		} else {
			size_of_chunk = (uint32_t)readValue(reader, 4);
			filter_mask = (uint32_t)readValue(reader, 4);
			if (filter_mask) {
				log("TREE all filters must be enabled\n");
				free(output);
				return MYSOFA_INVALID_FORMAT;
			}

			for (j = 0; j < data->ds.dimensionality; j++) {
				start[j] = readValue(reader, 8);
				log("start %d %lu\n",j,start[j]);
			}

			if (readValue(reader, 8)) {
				break;
			}

			child_pointer = readValue(reader,
						  reader->superblock.size_of_offsets);
			log(" data at %lX len %u\n", child_pointer, size_of_chunk);

			/* read data */
			store = ftell(reader->fhd);
			if (fseek(reader->fhd, child_pointer, SEEK_SET)<0) {
				free(output);
				return errno;
			}

			if (!(input = malloc(size_of_chunk))) {
				free(output);
				return MYSOFA_NO_MEMORY;
			}
			if (fread(input, 1, size_of_chunk, reader->fhd) != size_of_chunk) {
				free(output);
				free(input);
				return MYSOFA_INVALID_FORMAT;
			}

			olen = elements * size;
			err = gunzip(size_of_chunk, input, &olen, output);
			free(input);

			log("   gunzip %d %d %d\n",err, olen, elements*size);
			if (err || olen != elements * size) {
				free(output);
				return MYSOFA_INVALID_FORMAT;
			}

			switch (data->ds.dimensionality) {
			case 1:
				for (i = 0; i < olen; i++) {
					b = i / elements;
					x = i % elements + start[0];
					if (x < sx) {

						j = x * size + b;
						if (j >= 0 && j < data->data_len) {
							((char*) data->data)[j] = output[i];
						}
					}
				}
				break;
			case 2:
				for (i = 0; i < olen; i++) {
					b = i / elements;
					x = i % elements;
					y = x % dy + start[1];
					x = x / dy + start[0];
					if (y < sy && x < sx) {
						j = ((x * sy + y) * size) + b;
						if (j >= 0 && j < data->data_len) {
							((char*) data->data)[j] = output[i];
						}
					}
				}
				break;
			case 3:
				for (i = 0; i < olen; i++) {
					b = i / elements;
					x = i % elements;
					z = x % dz + start[2];
					y = (x / dz) % dy + start[1];
					x = (x / dzy) + start[0];
					if (z < sz && y < sy && x < sx) {
						j = (x * szy + y * sz + z) * size + b;
						if (j >= 0 && j < data->data_len) {
							((char*) data->data)[j] = output[i];
						}
					}
				}
				break;
			default:
				log("invalid dim\n");
				return MYSOFA_INTERNAL_ERROR;
			}

			if(fseek(reader->fhd, store, SEEK_SET)<0) {
				free(output);
				return errno;
			}
		}
	}

	free(output);
	if(fseek(reader->fhd, 4, SEEK_CUR)<0) /* skip checksum */
		return errno;

	return MYSOFA_OK;
}