91 static int befs_btree_seekleaf(struct super_block *sb, befs_data_stream * ds,
96 static int befs_bt_read_super(struct super_block *sb, befs_data_stream * ds,
99 static int befs_bt_read_node(struct super_block *sb, befs_data_stream * ds,
111 static int befs_find_key(struct super_block *sb,
115 static char *befs_bt_get_key(struct super_block *sb,
137 befs_bt_read_super(struct super_block *sb, befs_data_stream * ds,  in befs_bt_read_super()  argument
143 	befs_debug(sb, "---> %s", __func__);  in befs_bt_read_super()
145 	bh = befs_read_datastream(sb, ds, 0, NULL);  in befs_bt_read_super()
148 		befs_error(sb, "Couldn't read index header.");  in befs_bt_read_super()
152 	befs_dump_index_entry(sb, od_sup);  in befs_bt_read_super()
154 	sup->magic = fs32_to_cpu(sb, od_sup->magic);  in befs_bt_read_super()
155 	sup->node_size = fs32_to_cpu(sb, od_sup->node_size);  in befs_bt_read_super()
156 	sup->max_depth = fs32_to_cpu(sb, od_sup->max_depth);  in befs_bt_read_super()
157 	sup->data_type = fs32_to_cpu(sb, od_sup->data_type);  in befs_bt_read_super()
158 	sup->root_node_ptr = fs64_to_cpu(sb, od_sup->root_node_ptr);  in befs_bt_read_super()
159 	sup->free_node_ptr = fs64_to_cpu(sb, od_sup->free_node_ptr);  in befs_bt_read_super()
160 	sup->max_size = fs64_to_cpu(sb, od_sup->max_size);  in befs_bt_read_super()
164 		befs_error(sb, "Index header has bad magic.");  in befs_bt_read_super()
168 	befs_debug(sb, "<--- %s", __func__);  in befs_bt_read_super()
172 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_bt_read_super()
196 befs_bt_read_node(struct super_block *sb, befs_data_stream * ds,  in befs_bt_read_node()  argument
201 	befs_debug(sb, "---> %s", __func__);  in befs_bt_read_node()
206 	node->bh = befs_read_datastream(sb, ds, node_off, &off);  in befs_bt_read_node()
208 		befs_error(sb, "%s failed to read "  in befs_bt_read_node()
210 		befs_debug(sb, "<--- %s ERROR", __func__);  in befs_bt_read_node()
217 	befs_dump_index_node(sb, node->od_node);  in befs_bt_read_node()
219 	node->head.left = fs64_to_cpu(sb, node->od_node->left);  in befs_bt_read_node()
220 	node->head.right = fs64_to_cpu(sb, node->od_node->right);  in befs_bt_read_node()
221 	node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);  in befs_bt_read_node()
223 	    fs16_to_cpu(sb, node->od_node->all_key_count);  in befs_bt_read_node()
225 	    fs16_to_cpu(sb, node->od_node->all_key_length);  in befs_bt_read_node()
227 	befs_debug(sb, "<--- %s", __func__);  in befs_bt_read_node()
250 befs_btree_find(struct super_block *sb, befs_data_stream * ds,  in befs_btree_find()  argument
258 	befs_debug(sb, "---> %s Key: %s", __func__, key);  in befs_btree_find()
260 	if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {  in befs_btree_find()
261 		befs_error(sb,  in befs_btree_find()
269 		befs_error(sb, "befs_btree_find() failed to allocate %zu "  in befs_btree_find()
278 	if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {  in befs_btree_find()
279 		befs_error(sb, "befs_btree_find() failed to read "  in befs_btree_find()
285 		res = befs_find_key(sb, this_node, key, &node_off);  in befs_btree_find()
289 		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {  in befs_btree_find()
290 			befs_error(sb, "befs_btree_find() failed to read "  in befs_btree_find()
298 	res = befs_find_key(sb, this_node, key, value);  in befs_btree_find()
304 		befs_debug(sb, "<--- %s Key %s not found", __func__, key);  in befs_btree_find()
308 	befs_debug(sb, "<--- %s Found key %s, value %llu", __func__,  in befs_btree_find()
316 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_find()
339 befs_find_key(struct super_block *sb, struct befs_btree_node *node,  in befs_find_key()  argument
349 	befs_debug(sb, "---> %s %s", __func__, findkey);  in befs_find_key()
357 	thiskey = befs_bt_get_key(sb, node, last, &keylen);  in befs_find_key()
361 		befs_debug(sb, "<--- %s %s not found", __func__, findkey);  in befs_find_key()
372 		befs_debug(sb, "first: %d, last: %d, mid: %d", first, last,  in befs_find_key()
374 		thiskey = befs_bt_get_key(sb, node, mid, &keylen);  in befs_find_key()
379 			befs_debug(sb, "<--- %s found %s at %d",  in befs_find_key()
382 			*value = fs64_to_cpu(sb, valarray[mid]);  in befs_find_key()
391 		*value = fs64_to_cpu(sb, valarray[mid + 1]);  in befs_find_key()
393 		*value = fs64_to_cpu(sb, valarray[mid]);  in befs_find_key()
394 	befs_debug(sb, "<--- %s found %s at %d", __func__, thiskey, mid);  in befs_find_key()
419 befs_btree_read(struct super_block *sb, befs_data_stream * ds,  in befs_btree_read()  argument
434 	befs_debug(sb, "---> %s", __func__);  in befs_btree_read()
436 	if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {  in befs_btree_read()
437 		befs_error(sb,  in befs_btree_read()
444 		befs_error(sb, "befs_btree_read() failed to allocate %zu "  in befs_btree_read()
453 	res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);  in befs_btree_read()
459 		befs_debug(sb, "<--- %s Tree is EMPTY", __func__);  in befs_btree_read()
473 			befs_debug(sb,  in befs_btree_read()
485 		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {  in befs_btree_read()
486 			befs_error(sb, "%s failed to read node at %llu",  in befs_btree_read()
498 	keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);  in befs_btree_read()
500 	befs_debug(sb, "Read [%llu,%d]: keysize %d",  in befs_btree_read()
505 		befs_error(sb, "%s keybuf too small (%zu) "  in befs_btree_read()
512 	*value = fs64_to_cpu(sb, valarray[cur_key]);  in befs_btree_read()
515 	befs_debug(sb, "Read [%llu,%d]: Key \"%.*s\", Value %llu", node_off,  in befs_btree_read()
521 	befs_debug(sb, "<--- %s", __func__);  in befs_btree_read()
531 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_read()
551 befs_btree_seekleaf(struct super_block *sb, befs_data_stream * ds,  in befs_btree_seekleaf()  argument
557 	befs_debug(sb, "---> %s", __func__);  in befs_btree_seekleaf()
559 	if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {  in befs_btree_seekleaf()
560 		befs_error(sb, "%s failed to read "  in befs_btree_seekleaf()
564 	befs_debug(sb, "Seekleaf to root node %llu", *node_off);  in befs_btree_seekleaf()
567 		befs_debug(sb, "<--- %s Tree is EMPTY", __func__);  in befs_btree_seekleaf()
574 			befs_debug(sb, "%s encountered "  in befs_btree_seekleaf()
581 			*node_off = fs64_to_cpu(sb, valarray[0]);  in befs_btree_seekleaf()
583 		if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {  in befs_btree_seekleaf()
584 			befs_error(sb, "%s failed to read "  in befs_btree_seekleaf()
589 		befs_debug(sb, "Seekleaf to child node %llu", *node_off);  in befs_btree_seekleaf()
591 	befs_debug(sb, "Node %llu is a leaf node", *node_off);  in befs_btree_seekleaf()
596 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_seekleaf()
684 befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,  in befs_bt_get_key()  argument
702 		prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);  in befs_bt_get_key()
704 	*keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;  in befs_bt_get_key()