btree.c 22 KB

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