91 static int befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
96 static int befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
99 static int befs_bt_read_node(struct super_block *sb, const 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,
134 befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,  in befs_bt_read_super()  argument
140 	befs_debug(sb, "---> %s", __func__);  in befs_bt_read_super()
142 	bh = befs_read_datastream(sb, ds, 0, NULL);  in befs_bt_read_super()
145 		befs_error(sb, "Couldn't read index header.");  in befs_bt_read_super()
149 	befs_dump_index_entry(sb, od_sup);  in befs_bt_read_super()
151 	sup->magic = fs32_to_cpu(sb, od_sup->magic);  in befs_bt_read_super()
152 	sup->node_size = fs32_to_cpu(sb, od_sup->node_size);  in befs_bt_read_super()
153 	sup->max_depth = fs32_to_cpu(sb, od_sup->max_depth);  in befs_bt_read_super()
154 	sup->data_type = fs32_to_cpu(sb, od_sup->data_type);  in befs_bt_read_super()
155 	sup->root_node_ptr = fs64_to_cpu(sb, od_sup->root_node_ptr);  in befs_bt_read_super()
159 		befs_error(sb, "Index header has bad magic.");  in befs_bt_read_super()
163 	befs_debug(sb, "<--- %s", __func__);  in befs_bt_read_super()
167 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_bt_read_super()
191 befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,  in befs_bt_read_node()  argument
196 	befs_debug(sb, "---> %s", __func__);  in befs_bt_read_node()
201 	node->bh = befs_read_datastream(sb, ds, node_off, &off);  in befs_bt_read_node()
203 		befs_error(sb, "%s failed to read "  in befs_bt_read_node()
205 		befs_debug(sb, "<--- %s ERROR", __func__);  in befs_bt_read_node()
212 	befs_dump_index_node(sb, node->od_node);  in befs_bt_read_node()
214 	node->head.left = fs64_to_cpu(sb, node->od_node->left);  in befs_bt_read_node()
215 	node->head.right = fs64_to_cpu(sb, node->od_node->right);  in befs_bt_read_node()
216 	node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);  in befs_bt_read_node()
218 	    fs16_to_cpu(sb, node->od_node->all_key_count);  in befs_bt_read_node()
220 	    fs16_to_cpu(sb, node->od_node->all_key_length);  in befs_bt_read_node()
222 	befs_debug(sb, "<--- %s", __func__);  in befs_bt_read_node()
245 befs_btree_find(struct super_block *sb, const befs_data_stream *ds,  in befs_btree_find()  argument
253 	befs_debug(sb, "---> %s Key: %s", __func__, key);  in befs_btree_find()
255 	if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {  in befs_btree_find()
256 		befs_error(sb,  in befs_btree_find()
264 		befs_error(sb, "befs_btree_find() failed to allocate %zu "  in befs_btree_find()
273 	if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {  in befs_btree_find()
274 		befs_error(sb, "befs_btree_find() failed to read "  in befs_btree_find()
280 		res = befs_find_key(sb, this_node, key, &node_off);  in befs_btree_find()
284 		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {  in befs_btree_find()
285 			befs_error(sb, "befs_btree_find() failed to read "  in befs_btree_find()
292 	res = befs_find_key(sb, this_node, key, value);  in befs_btree_find()
298 		befs_error(sb, "<--- %s Key %s not found", __func__, key);  in befs_btree_find()
299 		befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_find()
303 	befs_debug(sb, "<--- %s Found key %s, value %llu", __func__,  in befs_btree_find()
311 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_find()
330 befs_find_key(struct super_block *sb, struct befs_btree_node *node,  in befs_find_key()  argument
340 	befs_debug(sb, "---> %s %s", __func__, findkey);  in befs_find_key()
346 	thiskey = befs_bt_get_key(sb, node, last, &keylen);  in befs_find_key()
350 		befs_debug(sb, "<--- node can't contain %s", findkey);  in befs_find_key()
361 		befs_debug(sb, "first: %d, last: %d, mid: %d", first, last,  in befs_find_key()
363 		thiskey = befs_bt_get_key(sb, node, mid, &keylen);  in befs_find_key()
368 			befs_debug(sb, "<--- %s found %s at %d",  in befs_find_key()
371 			*value = fs64_to_cpu(sb, valarray[mid]);  in befs_find_key()
382 		*value = fs64_to_cpu(sb, valarray[mid + 1]);  in befs_find_key()
384 		*value = fs64_to_cpu(sb, valarray[mid]);  in befs_find_key()
385 	befs_error(sb, "<--- %s %s not found", __func__, findkey);  in befs_find_key()
386 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_find_key()
411 befs_btree_read(struct super_block *sb, const befs_data_stream *ds,  in befs_btree_read()  argument
426 	befs_debug(sb, "---> %s", __func__);  in befs_btree_read()
428 	if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {  in befs_btree_read()
429 		befs_error(sb,  in befs_btree_read()
436 		befs_error(sb, "befs_btree_read() failed to allocate %zu "  in befs_btree_read()
445 	res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);  in befs_btree_read()
451 		befs_debug(sb, "<--- %s Tree is EMPTY", __func__);  in befs_btree_read()
465 			befs_debug(sb,  in befs_btree_read()
477 		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {  in befs_btree_read()
478 			befs_error(sb, "%s failed to read node at %llu",  in befs_btree_read()
490 	keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);  in befs_btree_read()
492 	befs_debug(sb, "Read [%llu,%d]: keysize %d",  in befs_btree_read()
497 		befs_error(sb, "%s keybuf too small (%zu) "  in befs_btree_read()
504 	*value = fs64_to_cpu(sb, valarray[cur_key]);  in befs_btree_read()
507 	befs_debug(sb, "Read [%llu,%d]: Key \"%.*s\", Value %llu", node_off,  in befs_btree_read()
513 	befs_debug(sb, "<--- %s", __func__);  in befs_btree_read()
523 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_read()
542 befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,  in befs_btree_seekleaf()  argument
548 	befs_debug(sb, "---> %s", __func__);  in befs_btree_seekleaf()
550 	if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {  in befs_btree_seekleaf()
551 		befs_error(sb, "%s failed to read "  in befs_btree_seekleaf()
555 	befs_debug(sb, "Seekleaf to root node %llu", *node_off);  in befs_btree_seekleaf()
558 		befs_debug(sb, "<--- %s Tree is EMPTY", __func__);  in befs_btree_seekleaf()
565 			befs_debug(sb, "%s encountered "  in befs_btree_seekleaf()
572 			*node_off = fs64_to_cpu(sb, valarray[0]);  in befs_btree_seekleaf()
574 		if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {  in befs_btree_seekleaf()
575 			befs_error(sb, "%s failed to read "  in befs_btree_seekleaf()
580 		befs_debug(sb, "Seekleaf to child node %llu", *node_off);  in befs_btree_seekleaf()
582 	befs_debug(sb, "Node %llu is a leaf node", *node_off);  in befs_btree_seekleaf()
587 	befs_debug(sb, "<--- %s ERROR", __func__);  in befs_btree_seekleaf()
675 befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,  in befs_bt_get_key()  argument
693 		prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);  in befs_bt_get_key()
695 	*keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;  in befs_bt_get_key()