btree.c 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787
  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 withing
  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. typedef struct {
  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. } befs_btree_node;
  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, befs_data_stream * ds,
  83. befs_btree_super * bt_super,
  84. befs_btree_node * this_node,
  85. befs_off_t * node_off);
  86. static int befs_bt_read_super(struct super_block *sb, befs_data_stream * ds,
  87. befs_btree_super * sup);
  88. static int befs_bt_read_node(struct super_block *sb, befs_data_stream * ds,
  89. befs_btree_node * node, befs_off_t node_off);
  90. static int befs_leafnode(befs_btree_node * node);
  91. static fs16 *befs_bt_keylen_index(befs_btree_node * node);
  92. static fs64 *befs_bt_valarray(befs_btree_node * node);
  93. static char *befs_bt_keydata(befs_btree_node * node);
  94. static int befs_find_key(struct super_block *sb, befs_btree_node * node,
  95. const char *findkey, befs_off_t * value);
  96. static char *befs_bt_get_key(struct super_block *sb, befs_btree_node * node,
  97. int index, u16 * keylen);
  98. static int befs_compare_strings(const void *key1, int keylen1,
  99. const void *key2, int keylen2);
  100. /**
  101. * befs_bt_read_super - read in btree superblock convert to cpu byteorder
  102. * @sb: Filesystem superblock
  103. * @ds: Datastream to read from
  104. * @sup: Buffer in which to place the btree superblock
  105. *
  106. * Calls befs_read_datastream to read in the btree superblock and
  107. * makes sure it is in cpu byteorder, byteswapping if necessary.
  108. *
  109. * On success, returns BEFS_OK and *@sup contains the btree superblock,
  110. * in cpu byte order.
  111. *
  112. * On failure, BEFS_ERR is returned.
  113. */
  114. static int
  115. befs_bt_read_super(struct super_block *sb, befs_data_stream * ds,
  116. befs_btree_super * sup)
  117. {
  118. struct buffer_head *bh = NULL;
  119. befs_disk_btree_super *od_sup = NULL;
  120. befs_debug(sb, "---> befs_btree_read_super()");
  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. sup->free_node_ptr = fs64_to_cpu(sb, od_sup->free_node_ptr);
  134. sup->max_size = fs64_to_cpu(sb, od_sup->max_size);
  135. brelse(bh);
  136. if (sup->magic != BEFS_BTREE_MAGIC) {
  137. befs_error(sb, "Index header has bad magic.");
  138. goto error;
  139. }
  140. befs_debug(sb, "<--- befs_btree_read_super()");
  141. return BEFS_OK;
  142. error:
  143. befs_debug(sb, "<--- befs_btree_read_super() ERROR");
  144. return BEFS_ERR;
  145. }
  146. /**
  147. * befs_bt_read_node - read in btree node and convert to cpu byteorder
  148. * @sb: Filesystem superblock
  149. * @ds: Datastream to read from
  150. * @node: Buffer in which to place the btree node
  151. * @node_off: Starting offset (in bytes) of the node in @ds
  152. *
  153. * Calls befs_read_datastream to read in the indicated btree node and
  154. * makes sure its header fields are in cpu byteorder, byteswapping if
  155. * necessary.
  156. * Note: node->bh must be NULL when this function called first
  157. * time. Don't forget brelse(node->bh) after last call.
  158. *
  159. * On success, returns BEFS_OK and *@node contains the btree node that
  160. * starts at @node_off, with the node->head fields in cpu byte order.
  161. *
  162. * On failure, BEFS_ERR is returned.
  163. */
  164. static int
  165. befs_bt_read_node(struct super_block *sb, befs_data_stream * ds,
  166. befs_btree_node * node, befs_off_t node_off)
  167. {
  168. uint off = 0;
  169. befs_debug(sb, "---> befs_bt_read_node()");
  170. if (node->bh)
  171. brelse(node->bh);
  172. node->bh = befs_read_datastream(sb, ds, node_off, &off);
  173. if (!node->bh) {
  174. befs_error(sb, "befs_bt_read_node() failed to read "
  175. "node at %Lu", node_off);
  176. befs_debug(sb, "<--- befs_bt_read_node() ERROR");
  177. return BEFS_ERR;
  178. }
  179. node->od_node =
  180. (befs_btree_nodehead *) ((void *) node->bh->b_data + off);
  181. befs_dump_index_node(sb, node->od_node);
  182. node->head.left = fs64_to_cpu(sb, node->od_node->left);
  183. node->head.right = fs64_to_cpu(sb, node->od_node->right);
  184. node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);
  185. node->head.all_key_count =
  186. fs16_to_cpu(sb, node->od_node->all_key_count);
  187. node->head.all_key_length =
  188. fs16_to_cpu(sb, node->od_node->all_key_length);
  189. befs_debug(sb, "<--- befs_btree_read_node()");
  190. return BEFS_OK;
  191. }
  192. /**
  193. * befs_btree_find - Find a key in a befs B+tree
  194. * @sb: Filesystem superblock
  195. * @ds: Datastream containing btree
  196. * @key: Key string to lookup in btree
  197. * @value: Value stored with @key
  198. *
  199. * On sucess, returns BEFS_OK and sets *@value to the value stored
  200. * with @key (usually the disk block number of an inode).
  201. *
  202. * On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND.
  203. *
  204. * Algorithm:
  205. * Read the superblock and rootnode of the b+tree.
  206. * Drill down through the interior nodes using befs_find_key().
  207. * Once at the correct leaf node, use befs_find_key() again to get the
  208. * actuall value stored with the key.
  209. */
  210. int
  211. befs_btree_find(struct super_block *sb, befs_data_stream * ds,
  212. const char *key, befs_off_t * value)
  213. {
  214. befs_btree_node *this_node = NULL;
  215. befs_btree_super bt_super;
  216. befs_off_t node_off;
  217. int res;
  218. befs_debug(sb, "---> befs_btree_find() Key: %s", key);
  219. if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
  220. befs_error(sb,
  221. "befs_btree_find() failed to read index superblock");
  222. goto error;
  223. }
  224. this_node = kmalloc(sizeof (befs_btree_node),
  225. GFP_NOFS);
  226. if (!this_node) {
  227. befs_error(sb, "befs_btree_find() failed to allocate %u "
  228. "bytes of memory", sizeof (befs_btree_node));
  229. goto error;
  230. }
  231. this_node->bh = NULL;
  232. /* read in root node */
  233. node_off = bt_super.root_node_ptr;
  234. if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
  235. befs_error(sb, "befs_btree_find() failed to read "
  236. "node at %Lu", node_off);
  237. goto error_alloc;
  238. }
  239. while (!befs_leafnode(this_node)) {
  240. res = befs_find_key(sb, this_node, key, &node_off);
  241. if (res == BEFS_BT_NOT_FOUND)
  242. node_off = this_node->head.overflow;
  243. /* if no match, go to overflow node */
  244. if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
  245. befs_error(sb, "befs_btree_find() failed to read "
  246. "node at %Lu", node_off);
  247. goto error_alloc;
  248. }
  249. }
  250. /* at the correct leaf node now */
  251. res = befs_find_key(sb, this_node, key, value);
  252. brelse(this_node->bh);
  253. kfree(this_node);
  254. if (res != BEFS_BT_MATCH) {
  255. befs_debug(sb, "<--- befs_btree_find() Key %s not found", key);
  256. *value = 0;
  257. return BEFS_BT_NOT_FOUND;
  258. }
  259. befs_debug(sb, "<--- befs_btree_find() Found key %s, value %Lu",
  260. key, *value);
  261. return BEFS_OK;
  262. error_alloc:
  263. kfree(this_node);
  264. error:
  265. *value = 0;
  266. befs_debug(sb, "<--- befs_btree_find() ERROR");
  267. return BEFS_ERR;
  268. }
  269. /**
  270. * befs_find_key - Search for a key within a node
  271. * @sb: Filesystem superblock
  272. * @node: Node to find the key within
  273. * @key: Keystring to search for
  274. * @value: If key is found, the value stored with the key is put here
  275. *
  276. * finds exact match if one exists, and returns BEFS_BT_MATCH
  277. * If no exact match, finds first key in node that is greater
  278. * (alphabetically) than the search key and returns BEFS_BT_PARMATCH
  279. * (for partial match, I guess). Can you think of something better to
  280. * call it?
  281. *
  282. * If no key was a match or greater than the search key, return
  283. * BEFS_BT_NOT_FOUND.
  284. *
  285. * Use binary search instead of a linear.
  286. */
  287. static int
  288. befs_find_key(struct super_block *sb, befs_btree_node * node,
  289. const char *findkey, befs_off_t * value)
  290. {
  291. int first, last, mid;
  292. int eq;
  293. u16 keylen;
  294. int findkey_len;
  295. char *thiskey;
  296. fs64 *valarray;
  297. befs_debug(sb, "---> befs_find_key() %s", findkey);
  298. *value = 0;
  299. findkey_len = strlen(findkey);
  300. /* if node can not contain key, just skeep this node */
  301. last = node->head.all_key_count - 1;
  302. thiskey = befs_bt_get_key(sb, node, last, &keylen);
  303. eq = befs_compare_strings(thiskey, keylen, findkey, findkey_len);
  304. if (eq < 0) {
  305. befs_debug(sb, "<--- befs_find_key() %s not found", findkey);
  306. return BEFS_BT_NOT_FOUND;
  307. }
  308. valarray = befs_bt_valarray(node);
  309. /* simple binary search */
  310. first = 0;
  311. mid = 0;
  312. while (last >= first) {
  313. mid = (last + first) / 2;
  314. befs_debug(sb, "first: %d, last: %d, mid: %d", first, last,
  315. mid);
  316. thiskey = befs_bt_get_key(sb, node, mid, &keylen);
  317. eq = befs_compare_strings(thiskey, keylen, findkey,
  318. findkey_len);
  319. if (eq == 0) {
  320. befs_debug(sb, "<--- befs_find_key() found %s at %d",
  321. thiskey, mid);
  322. *value = fs64_to_cpu(sb, valarray[mid]);
  323. return BEFS_BT_MATCH;
  324. }
  325. if (eq > 0)
  326. last = mid - 1;
  327. else
  328. first = mid + 1;
  329. }
  330. if (eq < 0)
  331. *value = fs64_to_cpu(sb, valarray[mid + 1]);
  332. else
  333. *value = fs64_to_cpu(sb, valarray[mid]);
  334. befs_debug(sb, "<--- befs_find_key() found %s at %d", thiskey, mid);
  335. return BEFS_BT_PARMATCH;
  336. }
  337. /**
  338. * befs_btree_read - Traverse leafnodes of a btree
  339. * @sb: Filesystem superblock
  340. * @ds: Datastream containing btree
  341. * @key_no: Key number (alphabetical order) of key to read
  342. * @bufsize: Size of the buffer to return key in
  343. * @keybuf: Pointer to a buffer to put the key in
  344. * @keysize: Length of the returned key
  345. * @value: Value stored with the returned key
  346. *
  347. * Heres how it works: Key_no is the index of the key/value pair to
  348. * return in keybuf/value.
  349. * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is
  350. * the number of charecters in the key (just a convenience).
  351. *
  352. * Algorithm:
  353. * Get the first leafnode of the tree. See if the requested key is in that
  354. * node. If not, follow the node->right link to the next leafnode. Repeat
  355. * until the (key_no)th key is found or the tree is out of keys.
  356. */
  357. int
  358. befs_btree_read(struct super_block *sb, befs_data_stream * ds,
  359. loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize,
  360. befs_off_t * value)
  361. {
  362. befs_btree_node *this_node;
  363. befs_btree_super bt_super;
  364. befs_off_t node_off = 0;
  365. int cur_key;
  366. fs64 *valarray;
  367. char *keystart;
  368. u16 keylen;
  369. int res;
  370. uint key_sum = 0;
  371. befs_debug(sb, "---> befs_btree_read()");
  372. if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
  373. befs_error(sb,
  374. "befs_btree_read() failed to read index superblock");
  375. goto error;
  376. }
  377. if ((this_node = (befs_btree_node *)
  378. kmalloc(sizeof (befs_btree_node), GFP_NOFS)) == NULL) {
  379. befs_error(sb, "befs_btree_read() failed to allocate %u "
  380. "bytes of memory", sizeof (befs_btree_node));
  381. goto error;
  382. }
  383. node_off = bt_super.root_node_ptr;
  384. this_node->bh = NULL;
  385. /* seeks down to first leafnode, reads it into this_node */
  386. res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);
  387. if (res == BEFS_BT_EMPTY) {
  388. brelse(this_node->bh);
  389. kfree(this_node);
  390. *value = 0;
  391. *keysize = 0;
  392. befs_debug(sb, "<--- befs_btree_read() Tree is EMPTY");
  393. return BEFS_BT_EMPTY;
  394. } else if (res == BEFS_ERR) {
  395. goto error_alloc;
  396. }
  397. /* find the leaf node containing the key_no key */
  398. while (key_sum + this_node->head.all_key_count <= key_no) {
  399. /* no more nodes to look in: key_no is too large */
  400. if (this_node->head.right == befs_bt_inval) {
  401. *keysize = 0;
  402. *value = 0;
  403. befs_debug(sb,
  404. "<--- befs_btree_read() END of keys at %Lu",
  405. key_sum + this_node->head.all_key_count);
  406. brelse(this_node->bh);
  407. kfree(this_node);
  408. return BEFS_BT_END;
  409. }
  410. key_sum += this_node->head.all_key_count;
  411. node_off = this_node->head.right;
  412. if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
  413. befs_error(sb, "befs_btree_read() failed to read "
  414. "node at %Lu", node_off);
  415. goto error_alloc;
  416. }
  417. }
  418. /* how many keys into this_node is key_no */
  419. cur_key = key_no - key_sum;
  420. /* get pointers to datastructures within the node body */
  421. valarray = befs_bt_valarray(this_node);
  422. keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);
  423. befs_debug(sb, "Read [%Lu,%d]: keysize %d", node_off, cur_key, keylen);
  424. if (bufsize < keylen + 1) {
  425. befs_error(sb, "befs_btree_read() keybuf too small (%u) "
  426. "for key of size %d", bufsize, keylen);
  427. brelse(this_node->bh);
  428. goto error_alloc;
  429. };
  430. strncpy(keybuf, keystart, keylen);
  431. *value = fs64_to_cpu(sb, valarray[cur_key]);
  432. *keysize = keylen;
  433. keybuf[keylen] = '\0';
  434. befs_debug(sb, "Read [%Lu,%d]: Key \"%.*s\", Value %Lu", node_off,
  435. cur_key, keylen, keybuf, *value);
  436. brelse(this_node->bh);
  437. kfree(this_node);
  438. befs_debug(sb, "<--- befs_btree_read()");
  439. return BEFS_OK;
  440. error_alloc:
  441. kfree(this_node);
  442. error:
  443. *keysize = 0;
  444. *value = 0;
  445. befs_debug(sb, "<--- befs_btree_read() ERROR");
  446. return BEFS_ERR;
  447. }
  448. /**
  449. * befs_btree_seekleaf - Find the first leafnode in the btree
  450. * @sb: Filesystem superblock
  451. * @ds: Datastream containing btree
  452. * @bt_super: Pointer to the superblock of the btree
  453. * @this_node: Buffer to return the leafnode in
  454. * @node_off: Pointer to offset of current node within datastream. Modified
  455. * by the function.
  456. *
  457. *
  458. * Helper function for btree traverse. Moves the current position to the
  459. * start of the first leaf node.
  460. *
  461. * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY.
  462. */
  463. static int
  464. befs_btree_seekleaf(struct super_block *sb, befs_data_stream * ds,
  465. befs_btree_super * bt_super, befs_btree_node * this_node,
  466. befs_off_t * node_off)
  467. {
  468. befs_debug(sb, "---> befs_btree_seekleaf()");
  469. if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
  470. befs_error(sb, "befs_btree_seekleaf() failed to read "
  471. "node at %Lu", *node_off);
  472. goto error;
  473. }
  474. befs_debug(sb, "Seekleaf to root node %Lu", *node_off);
  475. if (this_node->head.all_key_count == 0 && befs_leafnode(this_node)) {
  476. befs_debug(sb, "<--- befs_btree_seekleaf() Tree is EMPTY");
  477. return BEFS_BT_EMPTY;
  478. }
  479. while (!befs_leafnode(this_node)) {
  480. if (this_node->head.all_key_count == 0) {
  481. befs_debug(sb, "befs_btree_seekleaf() encountered "
  482. "an empty interior node: %Lu. Using Overflow "
  483. "node: %Lu", *node_off,
  484. this_node->head.overflow);
  485. *node_off = this_node->head.overflow;
  486. } else {
  487. fs64 *valarray = befs_bt_valarray(this_node);
  488. *node_off = fs64_to_cpu(sb, valarray[0]);
  489. }
  490. if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
  491. befs_error(sb, "befs_btree_seekleaf() failed to read "
  492. "node at %Lu", *node_off);
  493. goto error;
  494. }
  495. befs_debug(sb, "Seekleaf to child node %Lu", *node_off);
  496. }
  497. befs_debug(sb, "Node %Lu is a leaf node", *node_off);
  498. return BEFS_OK;
  499. error:
  500. befs_debug(sb, "<--- befs_btree_seekleaf() ERROR");
  501. return BEFS_ERR;
  502. }
  503. /**
  504. * befs_leafnode - Determine if the btree node is a leaf node or an
  505. * interior node
  506. * @node: Pointer to node structure to test
  507. *
  508. * Return 1 if leaf, 0 if interior
  509. */
  510. static int
  511. befs_leafnode(befs_btree_node * node)
  512. {
  513. /* all interior nodes (and only interior nodes) have an overflow node */
  514. if (node->head.overflow == befs_bt_inval)
  515. return 1;
  516. else
  517. return 0;
  518. }
  519. /**
  520. * befs_bt_keylen_index - Finds start of keylen index in a node
  521. * @node: Pointer to the node structure to find the keylen index within
  522. *
  523. * Returns a pointer to the start of the key length index array
  524. * of the B+tree node *@node
  525. *
  526. * "The length of all the keys in the node is added to the size of the
  527. * header and then rounded up to a multiple of four to get the beginning
  528. * of the key length index" (p.88, practical filesystem design).
  529. *
  530. * Except that rounding up to 8 works, and rounding up to 4 doesn't.
  531. */
  532. static fs16 *
  533. befs_bt_keylen_index(befs_btree_node * node)
  534. {
  535. const int keylen_align = 8;
  536. unsigned long int off =
  537. (sizeof (befs_btree_nodehead) + node->head.all_key_length);
  538. ulong tmp = off % keylen_align;
  539. if (tmp)
  540. off += keylen_align - tmp;
  541. return (fs16 *) ((void *) node->od_node + off);
  542. }
  543. /**
  544. * befs_bt_valarray - Finds the start of value array in a node
  545. * @node: Pointer to the node structure to find the value array within
  546. *
  547. * Returns a pointer to the start of the value array
  548. * of the node pointed to by the node header
  549. */
  550. static fs64 *
  551. befs_bt_valarray(befs_btree_node * node)
  552. {
  553. void *keylen_index_start = (void *) befs_bt_keylen_index(node);
  554. size_t keylen_index_size = node->head.all_key_count * sizeof (fs16);
  555. return (fs64 *) (keylen_index_start + keylen_index_size);
  556. }
  557. /**
  558. * befs_bt_keydata - Finds start of keydata array in a node
  559. * @node: Pointer to the node structure to find the keydata array within
  560. *
  561. * Returns a pointer to the start of the keydata array
  562. * of the node pointed to by the node header
  563. */
  564. static char *
  565. befs_bt_keydata(befs_btree_node * node)
  566. {
  567. return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead));
  568. }
  569. /**
  570. * befs_bt_get_key - returns a pointer to the start of a key
  571. * @sb: filesystem superblock
  572. * @node: node in which to look for the key
  573. * @index: the index of the key to get
  574. * @keylen: modified to be the length of the key at @index
  575. *
  576. * Returns a valid pointer into @node on success.
  577. * Returns NULL on failure (bad input) and sets *@keylen = 0
  578. */
  579. static char *
  580. befs_bt_get_key(struct super_block *sb, befs_btree_node * node,
  581. int index, u16 * keylen)
  582. {
  583. int prev_key_end;
  584. char *keystart;
  585. fs16 *keylen_index;
  586. if (index < 0 || index > node->head.all_key_count) {
  587. *keylen = 0;
  588. return NULL;
  589. }
  590. keystart = befs_bt_keydata(node);
  591. keylen_index = befs_bt_keylen_index(node);
  592. if (index == 0)
  593. prev_key_end = 0;
  594. else
  595. prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);
  596. *keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;
  597. return keystart + prev_key_end;
  598. }
  599. /**
  600. * befs_compare_strings - compare two strings
  601. * @key1: pointer to the first key to be compared
  602. * @keylen1: length in bytes of key1
  603. * @key2: pointer to the second key to be compared
  604. * @kelen2: length in bytes of key2
  605. *
  606. * Returns 0 if @key1 and @key2 are equal.
  607. * Returns >0 if @key1 is greater.
  608. * Returns <0 if @key2 is greater..
  609. */
  610. static int
  611. befs_compare_strings(const void *key1, int keylen1,
  612. const void *key2, int keylen2)
  613. {
  614. int len = min_t(int, keylen1, keylen2);
  615. int result = strncmp(key1, key2, len);
  616. if (result == 0)
  617. result = keylen1 - keylen2;
  618. return result;
  619. }
  620. /* These will be used for non-string keyed btrees */
  621. #if 0
  622. static int
  623. btree_compare_int32(cont void *key1, int keylen1, const void *key2, int keylen2)
  624. {
  625. return *(int32_t *) key1 - *(int32_t *) key2;
  626. }
  627. static int
  628. btree_compare_uint32(cont void *key1, int keylen1,
  629. const void *key2, int keylen2)
  630. {
  631. if (*(u_int32_t *) key1 == *(u_int32_t *) key2)
  632. return 0;
  633. else if (*(u_int32_t *) key1 > *(u_int32_t *) key2)
  634. return 1;
  635. return -1;
  636. }
  637. static int
  638. btree_compare_int64(cont void *key1, int keylen1, const void *key2, int keylen2)
  639. {
  640. if (*(int64_t *) key1 == *(int64_t *) key2)
  641. return 0;
  642. else if (*(int64_t *) key1 > *(int64_t *) key2)
  643. return 1;
  644. return -1;
  645. }
  646. static int
  647. btree_compare_uint64(cont void *key1, int keylen1,
  648. const void *key2, int keylen2)
  649. {
  650. if (*(u_int64_t *) key1 == *(u_int64_t *) key2)
  651. return 0;
  652. else if (*(u_int64_t *) key1 > *(u_int64_t *) key2)
  653. return 1;
  654. return -1;
  655. }
  656. static int
  657. btree_compare_float(cont void *key1, int keylen1, const void *key2, int keylen2)
  658. {
  659. float result = *(float *) key1 - *(float *) key2;
  660. if (result == 0.0f)
  661. return 0;
  662. return (result < 0.0f) ? -1 : 1;
  663. }
  664. static int
  665. btree_compare_double(cont void *key1, int keylen1,
  666. const void *key2, int keylen2)
  667. {
  668. double result = *(double *) key1 - *(double *) key2;
  669. if (result == 0.0)
  670. return 0;
  671. return (result < 0.0) ? -1 : 1;
  672. }
  673. #endif //0