^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * linux/fs/befs/btree.c
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Copyright (C) 2001-2002 Will Dyson <will_dyson@pobox.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Licensed under the GNU GPL. See the file COPYING for details.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * 2002-02-05: Sergey S. Kostyliov added binary search within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * btree nodes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * Many thanks to:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * Dominic Giampaolo, author of "Practical File System
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * Design with the Be File System", for such a helpful book.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * Marcus J. Ranum, author of the b+tree package in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * comp.sources.misc volume 10. This code is not copied from that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * work, but it is partially based on it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * Makoto Kato, author of the original BeFS for linux filesystem
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * driver.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) #include <linux/string.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) #include <linux/mm.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) #include <linux/buffer_head.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) #include "befs.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) #include "btree.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) #include "datastream.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * The btree functions in this file are built on top of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * datastream.c interface, which is in turn built on top of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * io.c interface.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) /* Befs B+tree structure:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * The first thing in the tree is the tree superblock. It tells you
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * all kinds of useful things about the tree, like where the rootnode
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * is located, and the size of the nodes (always 1024 with current version
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) * of BeOS).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * The rest of the tree consists of a series of nodes. Nodes contain a header
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * (struct befs_btree_nodehead), the packed key data, an array of shorts
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * containing the ending offsets for each of the keys, and an array of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * befs_off_t values. In interior nodes, the keys are the ending keys for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * the childnode they point to, and the values are offsets into the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * datastream containing the tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) /* Note:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) * The book states 2 confusing things about befs b+trees. First,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * it states that the overflow field of node headers is used by internal nodes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * to point to another node that "effectively continues this one". Here is what
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * I believe that means. Each key in internal nodes points to another node that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * contains key values less than itself. Inspection reveals that the last key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * in the internal node is not the last key in the index. Keys that are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * greater than the last key in the internal node go into the overflow node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * I imagine there is a performance reason for this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * Second, it states that the header of a btree node is sufficient to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * distinguish internal nodes from leaf nodes. Without saying exactly how.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * After figuring out the first, it becomes obvious that internal nodes have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * overflow nodes and leafnodes do not.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * Currently, this code is only good for directory B+trees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * In order to be used for other BFS indexes, it needs to be extended to handle
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) * duplicate keys and non-string keytypes (int32, int64, float, double).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) * In memory structure of each btree node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) struct befs_btree_node {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) befs_host_btree_nodehead head; /* head of node converted to cpu byteorder */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) struct buffer_head *bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) befs_btree_nodehead *od_node; /* on disk node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) /* local constants */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) static const befs_off_t BEFS_BT_INVAL = 0xffffffffffffffffULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) /* local functions */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) static int befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) befs_btree_super * bt_super,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) struct befs_btree_node *this_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) befs_off_t * node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) static int befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) befs_btree_super * sup);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) static int befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) struct befs_btree_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) befs_off_t node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) static int befs_leafnode(struct befs_btree_node *node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) static fs16 *befs_bt_keylen_index(struct befs_btree_node *node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) static fs64 *befs_bt_valarray(struct befs_btree_node *node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) static char *befs_bt_keydata(struct befs_btree_node *node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) static int befs_find_key(struct super_block *sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) struct befs_btree_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) const char *findkey, befs_off_t * value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) static char *befs_bt_get_key(struct super_block *sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) struct befs_btree_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) int index, u16 * keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) static int befs_compare_strings(const void *key1, int keylen1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) const void *key2, int keylen2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) * befs_bt_read_super() - read in btree superblock convert to cpu byteorder
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) * @sb: Filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) * @ds: Datastream to read from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) * @sup: Buffer in which to place the btree superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) * Calls befs_read_datastream to read in the btree superblock and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) * makes sure it is in cpu byteorder, byteswapping if necessary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) * Return: BEFS_OK on success and if *@sup contains the btree superblock in cpu
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) * byte order. Otherwise return BEFS_ERR on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) befs_btree_super * sup)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) struct buffer_head *bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) befs_disk_btree_super *od_sup;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) befs_debug(sb, "---> %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) bh = befs_read_datastream(sb, ds, 0, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) if (!bh) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) befs_error(sb, "Couldn't read index header.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) od_sup = (befs_disk_btree_super *) bh->b_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) befs_dump_index_entry(sb, od_sup);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) sup->magic = fs32_to_cpu(sb, od_sup->magic);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) sup->node_size = fs32_to_cpu(sb, od_sup->node_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) sup->max_depth = fs32_to_cpu(sb, od_sup->max_depth);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) sup->data_type = fs32_to_cpu(sb, od_sup->data_type);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) sup->root_node_ptr = fs64_to_cpu(sb, od_sup->root_node_ptr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) brelse(bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) if (sup->magic != BEFS_BTREE_MAGIC) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) befs_error(sb, "Index header has bad magic.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) befs_debug(sb, "<--- %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) return BEFS_OK;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) return BEFS_ERR;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) * befs_bt_read_node - read in btree node and convert to cpu byteorder
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) * @sb: Filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) * @ds: Datastream to read from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) * @node: Buffer in which to place the btree node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) * @node_off: Starting offset (in bytes) of the node in @ds
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) * Calls befs_read_datastream to read in the indicated btree node and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) * makes sure its header fields are in cpu byteorder, byteswapping if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) * necessary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) * Note: node->bh must be NULL when this function is called the first time.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) * Don't forget brelse(node->bh) after last call.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) * On success, returns BEFS_OK and *@node contains the btree node that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) * starts at @node_off, with the node->head fields in cpu byte order.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) * On failure, BEFS_ERR is returned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) struct befs_btree_node *node, befs_off_t node_off)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) uint off = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) befs_debug(sb, "---> %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) if (node->bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) brelse(node->bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) node->bh = befs_read_datastream(sb, ds, node_off, &off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) if (!node->bh) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) befs_error(sb, "%s failed to read "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) "node at %llu", __func__, node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) return BEFS_ERR;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) node->od_node =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) (befs_btree_nodehead *) ((void *) node->bh->b_data + off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) befs_dump_index_node(sb, node->od_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) node->head.left = fs64_to_cpu(sb, node->od_node->left);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) node->head.right = fs64_to_cpu(sb, node->od_node->right);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) node->head.all_key_count =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) fs16_to_cpu(sb, node->od_node->all_key_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) node->head.all_key_length =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) fs16_to_cpu(sb, node->od_node->all_key_length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) befs_debug(sb, "<--- %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) return BEFS_OK;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) * befs_btree_find - Find a key in a befs B+tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) * @sb: Filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) * @ds: Datastream containing btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) * @key: Key string to lookup in btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) * @value: Value stored with @key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) * On success, returns BEFS_OK and sets *@value to the value stored
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) * with @key (usually the disk block number of an inode).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) * On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) * Algorithm:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) * Read the superblock and rootnode of the b+tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) * Drill down through the interior nodes using befs_find_key().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) * Once at the correct leaf node, use befs_find_key() again to get the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) * actual value stored with the key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) const char *key, befs_off_t * value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) struct befs_btree_node *this_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) befs_btree_super bt_super;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) befs_off_t node_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) int res;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) befs_debug(sb, "---> %s Key: %s", __func__, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) befs_error(sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) "befs_btree_find() failed to read index superblock");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) this_node = kmalloc(sizeof(struct befs_btree_node),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) GFP_NOFS);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) if (!this_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) befs_error(sb, "befs_btree_find() failed to allocate %zu "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) "bytes of memory", sizeof(struct befs_btree_node));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) this_node->bh = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) /* read in root node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) node_off = bt_super.root_node_ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) befs_error(sb, "befs_btree_find() failed to read "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) "node at %llu", node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) goto error_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) while (!befs_leafnode(this_node)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) res = befs_find_key(sb, this_node, key, &node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) /* if no key set, try the overflow node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) if (res == BEFS_BT_OVERFLOW)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) node_off = this_node->head.overflow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) befs_error(sb, "befs_btree_find() failed to read "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) "node at %llu", node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) goto error_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) /* at a leaf node now, check if it is correct */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) res = befs_find_key(sb, this_node, key, value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) brelse(this_node->bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) kfree(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) if (res != BEFS_BT_MATCH) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) befs_error(sb, "<--- %s Key %s not found", __func__, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) *value = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) return BEFS_BT_NOT_FOUND;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) befs_debug(sb, "<--- %s Found key %s, value %llu", __func__,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) key, *value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) return BEFS_OK;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) error_alloc:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) kfree(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) *value = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) return BEFS_ERR;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) * befs_find_key - Search for a key within a node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) * @sb: Filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) * @node: Node to find the key within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) * @findkey: Keystring to search for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) * @value: If key is found, the value stored with the key is put here
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) * Finds exact match if one exists, and returns BEFS_BT_MATCH.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) * If there is no match and node's value array is too small for key, return
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) * BEFS_BT_OVERFLOW.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) * If no match and node should countain this key, return BEFS_BT_NOT_FOUND.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) * Uses binary search instead of a linear.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) befs_find_key(struct super_block *sb, struct befs_btree_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) const char *findkey, befs_off_t * value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) int first, last, mid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) int eq;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) u16 keylen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) int findkey_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) char *thiskey;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) fs64 *valarray;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) befs_debug(sb, "---> %s %s", __func__, findkey);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) findkey_len = strlen(findkey);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) /* if node can not contain key, just skip this node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) last = node->head.all_key_count - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) thiskey = befs_bt_get_key(sb, node, last, &keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) eq = befs_compare_strings(thiskey, keylen, findkey, findkey_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) if (eq < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) befs_debug(sb, "<--- node can't contain %s", findkey);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) return BEFS_BT_OVERFLOW;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) valarray = befs_bt_valarray(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) /* simple binary search */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) first = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) mid = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) while (last >= first) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) mid = (last + first) / 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) befs_debug(sb, "first: %d, last: %d, mid: %d", first, last,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) mid);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) thiskey = befs_bt_get_key(sb, node, mid, &keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) eq = befs_compare_strings(thiskey, keylen, findkey,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) findkey_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) if (eq == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) befs_debug(sb, "<--- %s found %s at %d",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) __func__, thiskey, mid);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) *value = fs64_to_cpu(sb, valarray[mid]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) return BEFS_BT_MATCH;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) if (eq > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) last = mid - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) first = mid + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) /* return an existing value so caller can arrive to a leaf node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) if (eq < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) *value = fs64_to_cpu(sb, valarray[mid + 1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) *value = fs64_to_cpu(sb, valarray[mid]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) befs_error(sb, "<--- %s %s not found", __func__, findkey);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) return BEFS_BT_NOT_FOUND;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) * befs_btree_read - Traverse leafnodes of a btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) * @sb: Filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) * @ds: Datastream containing btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) * @key_no: Key number (alphabetical order) of key to read
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) * @bufsize: Size of the buffer to return key in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) * @keybuf: Pointer to a buffer to put the key in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) * @keysize: Length of the returned key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) * @value: Value stored with the returned key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) * Here's how it works: Key_no is the index of the key/value pair to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) * return in keybuf/value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) * the number of characters in the key (just a convenience).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) * Algorithm:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) * Get the first leafnode of the tree. See if the requested key is in that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) * node. If not, follow the node->right link to the next leafnode. Repeat
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) * until the (key_no)th key is found or the tree is out of keys.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) befs_btree_read(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) befs_off_t * value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) struct befs_btree_node *this_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) befs_btree_super bt_super;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) befs_off_t node_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) int cur_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) fs64 *valarray;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) char *keystart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) u16 keylen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) int res;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) uint key_sum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) befs_debug(sb, "---> %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) befs_error(sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) "befs_btree_read() failed to read index superblock");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) this_node = kmalloc(sizeof(struct befs_btree_node), GFP_NOFS);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) if (this_node == NULL) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) befs_error(sb, "befs_btree_read() failed to allocate %zu "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) "bytes of memory", sizeof(struct befs_btree_node));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) node_off = bt_super.root_node_ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) this_node->bh = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) /* seeks down to first leafnode, reads it into this_node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) if (res == BEFS_BT_EMPTY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) brelse(this_node->bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) kfree(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) *value = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) *keysize = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) befs_debug(sb, "<--- %s Tree is EMPTY", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) return BEFS_BT_EMPTY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) } else if (res == BEFS_ERR) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) goto error_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) /* find the leaf node containing the key_no key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) while (key_sum + this_node->head.all_key_count <= key_no) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) /* no more nodes to look in: key_no is too large */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) if (this_node->head.right == BEFS_BT_INVAL) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) *keysize = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) *value = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) befs_debug(sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) "<--- %s END of keys at %llu", __func__,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) (unsigned long long)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) key_sum + this_node->head.all_key_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) brelse(this_node->bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) kfree(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) return BEFS_BT_END;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) key_sum += this_node->head.all_key_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) node_off = this_node->head.right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) befs_error(sb, "%s failed to read node at %llu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) __func__, (unsigned long long)node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) goto error_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) /* how many keys into this_node is key_no */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) cur_key = key_no - key_sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) /* get pointers to datastructures within the node body */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) valarray = befs_bt_valarray(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) befs_debug(sb, "Read [%llu,%d]: keysize %d",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) (long long unsigned int)node_off, (int)cur_key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) (int)keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) if (bufsize < keylen + 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) befs_error(sb, "%s keybuf too small (%zu) "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) "for key of size %d", __func__, bufsize, keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) brelse(this_node->bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) goto error_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) strlcpy(keybuf, keystart, keylen + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) *value = fs64_to_cpu(sb, valarray[cur_key]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) *keysize = keylen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) befs_debug(sb, "Read [%llu,%d]: Key \"%.*s\", Value %llu", node_off,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) cur_key, keylen, keybuf, *value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) brelse(this_node->bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) kfree(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) befs_debug(sb, "<--- %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) return BEFS_OK;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) error_alloc:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) kfree(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) *keysize = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) *value = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) return BEFS_ERR;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) * befs_btree_seekleaf - Find the first leafnode in the btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) * @sb: Filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) * @ds: Datastream containing btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) * @bt_super: Pointer to the superblock of the btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) * @this_node: Buffer to return the leafnode in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) * @node_off: Pointer to offset of current node within datastream. Modified
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) * by the function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) * Helper function for btree traverse. Moves the current position to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) * start of the first leaf node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) befs_btree_super *bt_super,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) struct befs_btree_node *this_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) befs_off_t * node_off)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) befs_debug(sb, "---> %s", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) befs_error(sb, "%s failed to read "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) "node at %llu", __func__, *node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) befs_debug(sb, "Seekleaf to root node %llu", *node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) if (this_node->head.all_key_count == 0 && befs_leafnode(this_node)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) befs_debug(sb, "<--- %s Tree is EMPTY", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) return BEFS_BT_EMPTY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) while (!befs_leafnode(this_node)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) if (this_node->head.all_key_count == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) befs_debug(sb, "%s encountered "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) "an empty interior node: %llu. Using Overflow "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) "node: %llu", __func__, *node_off,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) this_node->head.overflow);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) *node_off = this_node->head.overflow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) fs64 *valarray = befs_bt_valarray(this_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) *node_off = fs64_to_cpu(sb, valarray[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) befs_error(sb, "%s failed to read "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) "node at %llu", __func__, *node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) goto error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) befs_debug(sb, "Seekleaf to child node %llu", *node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) befs_debug(sb, "Node %llu is a leaf node", *node_off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) return BEFS_OK;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) befs_debug(sb, "<--- %s ERROR", __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) return BEFS_ERR;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) * befs_leafnode - Determine if the btree node is a leaf node or an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) * interior node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) * @node: Pointer to node structure to test
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) * Return 1 if leaf, 0 if interior
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) befs_leafnode(struct befs_btree_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) /* all interior nodes (and only interior nodes) have an overflow node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) if (node->head.overflow == BEFS_BT_INVAL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) * befs_bt_keylen_index - Finds start of keylen index in a node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) * @node: Pointer to the node structure to find the keylen index within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) * Returns a pointer to the start of the key length index array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) * of the B+tree node *@node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) * "The length of all the keys in the node is added to the size of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) * header and then rounded up to a multiple of four to get the beginning
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) * of the key length index" (p.88, practical filesystem design).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) * Except that rounding up to 8 works, and rounding up to 4 doesn't.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) static fs16 *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) befs_bt_keylen_index(struct befs_btree_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) const int keylen_align = 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) unsigned long int off =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) (sizeof (befs_btree_nodehead) + node->head.all_key_length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) ulong tmp = off % keylen_align;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) if (tmp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) off += keylen_align - tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) return (fs16 *) ((void *) node->od_node + off);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) * befs_bt_valarray - Finds the start of value array in a node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) * @node: Pointer to the node structure to find the value array within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) * Returns a pointer to the start of the value array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) * of the node pointed to by the node header
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) static fs64 *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) befs_bt_valarray(struct befs_btree_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) void *keylen_index_start = (void *) befs_bt_keylen_index(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) size_t keylen_index_size = node->head.all_key_count * sizeof (fs16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) return (fs64 *) (keylen_index_start + keylen_index_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) * befs_bt_keydata - Finds start of keydata array in a node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) * @node: Pointer to the node structure to find the keydata array within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) * Returns a pointer to the start of the keydata array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) * of the node pointed to by the node header
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) static char *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) befs_bt_keydata(struct befs_btree_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) * befs_bt_get_key - returns a pointer to the start of a key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) * @sb: filesystem superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) * @node: node in which to look for the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) * @index: the index of the key to get
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) * @keylen: modified to be the length of the key at @index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) * Returns a valid pointer into @node on success.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) * Returns NULL on failure (bad input) and sets *@keylen = 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) static char *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) int index, u16 * keylen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) int prev_key_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) char *keystart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) fs16 *keylen_index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) if (index < 0 || index > node->head.all_key_count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) *keylen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) keystart = befs_bt_keydata(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) keylen_index = befs_bt_keylen_index(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) if (index == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) prev_key_end = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) *keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) return keystart + prev_key_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) * befs_compare_strings - compare two strings
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) * @key1: pointer to the first key to be compared
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) * @keylen1: length in bytes of key1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) * @key2: pointer to the second key to be compared
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) * @keylen2: length in bytes of key2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) * Returns 0 if @key1 and @key2 are equal.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) * Returns >0 if @key1 is greater.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) * Returns <0 if @key2 is greater.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) befs_compare_strings(const void *key1, int keylen1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) int len = min_t(int, keylen1, keylen2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) int result = strncmp(key1, key2, len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) if (result == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) result = keylen1 - keylen2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) return result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) /* These will be used for non-string keyed btrees */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) #if 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) btree_compare_int32(cont void *key1, int keylen1, const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) return *(int32_t *) key1 - *(int32_t *) key2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) btree_compare_uint32(cont void *key1, int keylen1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) if (*(u_int32_t *) key1 == *(u_int32_t *) key2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) else if (*(u_int32_t *) key1 > *(u_int32_t *) key2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) btree_compare_int64(cont void *key1, int keylen1, const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) if (*(int64_t *) key1 == *(int64_t *) key2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) else if (*(int64_t *) key1 > *(int64_t *) key2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) btree_compare_uint64(cont void *key1, int keylen1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) if (*(u_int64_t *) key1 == *(u_int64_t *) key2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) else if (*(u_int64_t *) key1 > *(u_int64_t *) key2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) btree_compare_float(cont void *key1, int keylen1, const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) float result = *(float *) key1 - *(float *) key2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) if (result == 0.0f)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) return (result < 0.0f) ? -1 : 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) btree_compare_double(cont void *key1, int keylen1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) const void *key2, int keylen2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) double result = *(double *) key1 - *(double *) key2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) if (result == 0.0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) return (result < 0.0) ? -1 : 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) #endif //0
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags