aboutsummaryrefslogtreecommitdiffstats
path: root/drivers/md/persistent-data
diff options
context:
space:
mode:
authorJoe Thornber <ejt@redhat.com>2013-12-20 10:41:11 -0500
committerMike Snitzer <snitzer@redhat.com>2014-01-09 16:29:17 -0500
commitf164e6900f2be2c29f5c11ca52af5bb824f40826 (patch)
treef727095ad5fdbbc79c34796a1c7e79abc29456f5 /drivers/md/persistent-data
parent7e664b3dec431eebf0c5df5ff704d6197634cf35 (diff)
dm btree: add dm_btree_find_lowest_key
dm_btree_find_lowest_key is the reciprocal of dm_btree_find_highest_key. Factor out common code for dm_btree_find_{highest,lowest}_key. dm_btree_find_lowest_key is needed for an upcoming DM target, as such it is best to get this interface in place. Signed-off-by: Joe Thornber <ejt@redhat.com> Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Diffstat (limited to 'drivers/md/persistent-data')
-rw-r--r--drivers/md/persistent-data/dm-btree.c33
-rw-r--r--drivers/md/persistent-data/dm-btree.h8
2 files changed, 34 insertions, 7 deletions
diff --git a/drivers/md/persistent-data/dm-btree.c b/drivers/md/persistent-data/dm-btree.c
index 468e371ee9b2..416060c25709 100644
--- a/drivers/md/persistent-data/dm-btree.c
+++ b/drivers/md/persistent-data/dm-btree.c
@@ -770,8 +770,8 @@ EXPORT_SYMBOL_GPL(dm_btree_insert_notify);
770 770
771/*----------------------------------------------------------------*/ 771/*----------------------------------------------------------------*/
772 772
773static int find_highest_key(struct ro_spine *s, dm_block_t block, 773static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest,
774 uint64_t *result_key, dm_block_t *next_block) 774 uint64_t *result_key, dm_block_t *next_block)
775{ 775{
776 int i, r; 776 int i, r;
777 uint32_t flags; 777 uint32_t flags;
@@ -788,7 +788,11 @@ static int find_highest_key(struct ro_spine *s, dm_block_t block,
788 else 788 else
789 i--; 789 i--;
790 790
791 *result_key = le64_to_cpu(ro_node(s)->keys[i]); 791 if (find_highest)
792 *result_key = le64_to_cpu(ro_node(s)->keys[i]);
793 else
794 *result_key = le64_to_cpu(ro_node(s)->keys[0]);
795
792 if (next_block || flags & INTERNAL_NODE) 796 if (next_block || flags & INTERNAL_NODE)
793 block = value64(ro_node(s), i); 797 block = value64(ro_node(s), i);
794 798
@@ -799,16 +803,16 @@ static int find_highest_key(struct ro_spine *s, dm_block_t block,
799 return 0; 803 return 0;
800} 804}
801 805
802int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root, 806static int dm_btree_find_key(struct dm_btree_info *info, dm_block_t root,
803 uint64_t *result_keys) 807 bool find_highest, uint64_t *result_keys)
804{ 808{
805 int r = 0, count = 0, level; 809 int r = 0, count = 0, level;
806 struct ro_spine spine; 810 struct ro_spine spine;
807 811
808 init_ro_spine(&spine, info); 812 init_ro_spine(&spine, info);
809 for (level = 0; level < info->levels; level++) { 813 for (level = 0; level < info->levels; level++) {
810 r = find_highest_key(&spine, root, result_keys + level, 814 r = find_key(&spine, root, find_highest, result_keys + level,
811 level == info->levels - 1 ? NULL : &root); 815 level == info->levels - 1 ? NULL : &root);
812 if (r == -ENODATA) { 816 if (r == -ENODATA) {
813 r = 0; 817 r = 0;
814 break; 818 break;
@@ -822,8 +826,23 @@ int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
822 826
823 return r ? r : count; 827 return r ? r : count;
824} 828}
829
830int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
831 uint64_t *result_keys)
832{
833 return dm_btree_find_key(info, root, true, result_keys);
834}
825EXPORT_SYMBOL_GPL(dm_btree_find_highest_key); 835EXPORT_SYMBOL_GPL(dm_btree_find_highest_key);
826 836
837int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
838 uint64_t *result_keys)
839{
840 return dm_btree_find_key(info, root, false, result_keys);
841}
842EXPORT_SYMBOL_GPL(dm_btree_find_lowest_key);
843
844/*----------------------------------------------------------------*/
845
827/* 846/*
828 * FIXME: We shouldn't use a recursive algorithm when we have limited stack 847 * FIXME: We shouldn't use a recursive algorithm when we have limited stack
829 * space. Also this only works for single level trees. 848 * space. Also this only works for single level trees.
diff --git a/drivers/md/persistent-data/dm-btree.h b/drivers/md/persistent-data/dm-btree.h
index 8672d159e0b5..dacfc34180b4 100644
--- a/drivers/md/persistent-data/dm-btree.h
+++ b/drivers/md/persistent-data/dm-btree.h
@@ -137,6 +137,14 @@ int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
137/* 137/*
138 * Returns < 0 on failure. Otherwise the number of key entries that have 138 * Returns < 0 on failure. Otherwise the number of key entries that have
139 * been filled out. Remember trees can have zero entries, and as such have 139 * been filled out. Remember trees can have zero entries, and as such have
140 * no lowest key.
141 */
142int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
143 uint64_t *result_keys);
144
145/*
146 * Returns < 0 on failure. Otherwise the number of key entries that have
147 * been filled out. Remember trees can have zero entries, and as such have
140 * no highest key. 148 * no highest key.
141 */ 149 */
142int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root, 150int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,