bfind.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209
  1. /*
  2. * linux/fs/hfs/bfind.c
  3. *
  4. * Copyright (C) 2001
  5. * Brad Boyer (flar@allandria.com)
  6. * (C) 2003 Ardis Technologies <roman@ardistech.com>
  7. *
  8. * Search routines for btrees
  9. */
  10. #include <linux/slab.h>
  11. #include "btree.h"
  12. int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
  13. {
  14. void *ptr;
  15. fd->tree = tree;
  16. fd->bnode = NULL;
  17. ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
  18. if (!ptr)
  19. return -ENOMEM;
  20. fd->search_key = ptr;
  21. fd->key = ptr + tree->max_key_len + 2;
  22. dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0));
  23. down(&tree->tree_lock);
  24. return 0;
  25. }
  26. void hfs_find_exit(struct hfs_find_data *fd)
  27. {
  28. hfs_bnode_put(fd->bnode);
  29. kfree(fd->search_key);
  30. dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0));
  31. up(&fd->tree->tree_lock);
  32. fd->tree = NULL;
  33. }
  34. /* Find the record in bnode that best matches key (not greater than...)*/
  35. int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
  36. {
  37. int cmpval;
  38. u16 off, len, keylen;
  39. int rec;
  40. int b, e;
  41. int res;
  42. b = 0;
  43. e = bnode->num_recs - 1;
  44. res = -ENOENT;
  45. do {
  46. rec = (e + b) / 2;
  47. len = hfs_brec_lenoff(bnode, rec, &off);
  48. keylen = hfs_brec_keylen(bnode, rec);
  49. hfs_bnode_read(bnode, fd->key, off, keylen);
  50. cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
  51. if (!cmpval) {
  52. e = rec;
  53. res = 0;
  54. goto done;
  55. }
  56. if (cmpval < 0)
  57. b = rec + 1;
  58. else
  59. e = rec - 1;
  60. } while (b <= e);
  61. if (rec != e && e >= 0) {
  62. len = hfs_brec_lenoff(bnode, e, &off);
  63. keylen = hfs_brec_keylen(bnode, e);
  64. hfs_bnode_read(bnode, fd->key, off, keylen);
  65. }
  66. done:
  67. fd->record = e;
  68. fd->keyoffset = off;
  69. fd->keylength = keylen;
  70. fd->entryoffset = off + keylen;
  71. fd->entrylength = len - keylen;
  72. return res;
  73. }
  74. /* Traverse a B*Tree from the root to a leaf finding best fit to key */
  75. /* Return allocated copy of node found, set recnum to best record */
  76. int hfs_brec_find(struct hfs_find_data *fd)
  77. {
  78. struct hfs_btree *tree;
  79. struct hfs_bnode *bnode;
  80. u32 nidx, parent;
  81. __be32 data;
  82. int height, res;
  83. tree = fd->tree;
  84. if (fd->bnode)
  85. hfs_bnode_put(fd->bnode);
  86. fd->bnode = NULL;
  87. nidx = tree->root;
  88. if (!nidx)
  89. return -ENOENT;
  90. height = tree->depth;
  91. res = 0;
  92. parent = 0;
  93. for (;;) {
  94. bnode = hfs_bnode_find(tree, nidx);
  95. if (IS_ERR(bnode)) {
  96. res = PTR_ERR(bnode);
  97. bnode = NULL;
  98. break;
  99. }
  100. if (bnode->height != height)
  101. goto invalid;
  102. if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
  103. goto invalid;
  104. bnode->parent = parent;
  105. res = __hfs_brec_find(bnode, fd);
  106. if (!height)
  107. break;
  108. if (fd->record < 0)
  109. goto release;
  110. parent = nidx;
  111. hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
  112. nidx = be32_to_cpu(data);
  113. hfs_bnode_put(bnode);
  114. }
  115. fd->bnode = bnode;
  116. return res;
  117. invalid:
  118. printk(KERN_ERR "hfs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
  119. height, bnode->height, bnode->type, nidx, parent);
  120. res = -EIO;
  121. release:
  122. hfs_bnode_put(bnode);
  123. return res;
  124. }
  125. int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
  126. {
  127. int res;
  128. res = hfs_brec_find(fd);
  129. if (res)
  130. return res;
  131. if (fd->entrylength > rec_len)
  132. return -EINVAL;
  133. hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
  134. return 0;
  135. }
  136. int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
  137. {
  138. struct hfs_btree *tree;
  139. struct hfs_bnode *bnode;
  140. int idx, res = 0;
  141. u16 off, len, keylen;
  142. bnode = fd->bnode;
  143. tree = bnode->tree;
  144. if (cnt < 0) {
  145. cnt = -cnt;
  146. while (cnt > fd->record) {
  147. cnt -= fd->record + 1;
  148. fd->record = bnode->num_recs - 1;
  149. idx = bnode->prev;
  150. if (!idx) {
  151. res = -ENOENT;
  152. goto out;
  153. }
  154. hfs_bnode_put(bnode);
  155. bnode = hfs_bnode_find(tree, idx);
  156. if (IS_ERR(bnode)) {
  157. res = PTR_ERR(bnode);
  158. bnode = NULL;
  159. goto out;
  160. }
  161. }
  162. fd->record -= cnt;
  163. } else {
  164. while (cnt >= bnode->num_recs - fd->record) {
  165. cnt -= bnode->num_recs - fd->record;
  166. fd->record = 0;
  167. idx = bnode->next;
  168. if (!idx) {
  169. res = -ENOENT;
  170. goto out;
  171. }
  172. hfs_bnode_put(bnode);
  173. bnode = hfs_bnode_find(tree, idx);
  174. if (IS_ERR(bnode)) {
  175. res = PTR_ERR(bnode);
  176. bnode = NULL;
  177. goto out;
  178. }
  179. }
  180. fd->record += cnt;
  181. }
  182. len = hfs_brec_lenoff(bnode, fd->record, &off);
  183. keylen = hfs_brec_keylen(bnode, fd->record);
  184. fd->keyoffset = off;
  185. fd->keylength = keylen;
  186. fd->entryoffset = off + keylen;
  187. fd->entrylength = len - keylen;
  188. hfs_bnode_read(bnode, fd->key, off, keylen);
  189. out:
  190. fd->bnode = bnode;
  191. return res;
  192. }