is a tool to change a file-system from one format to another, for example from jfs, xfs, or reiser to ext2, ext3, or ext4, in-place and without the need for backup.
| map.t.hh (fstransform-0.9.3-src) | : | map.t.hh (fstransform-0.9.4) |
|---|
| | |
| skipping to change at line 381 | | skipping to change at line 381 |
|---|
| } | | } |
| return ret; | | return ret; |
| } | | } |
| | |
| /** | | /** |
| * find the intersections (matching physical, or both physical and logical) betw
een specified map1 and map2. | | * find the intersections (matching physical, or both physical and logical) betw
een specified map1 and map2. |
| * insert list of intersections into this map and return true. | | * insert list of intersections into this map and return true. |
| * if no intersections, return false and this map will be unchanged | | * if no intersections, return false and this map will be unchanged |
| * | | * |
| * note: if the intersection is only physical, | | * note: if the intersection is only physical, |
|
| * the intersection will contain the appropriate subrange of extent1 -> logical | | * the intersection will contain the appropriate subrange of map[match] -> logic
al |
| */ | | */ |
| template<typename T> | | template<typename T> |
| bool fr_map<T>::intersect_all_all(const fr_map<T> & map1, const fr_map<T> & map2
, ft_match match) | | bool fr_map<T>::intersect_all_all(const fr_map<T> & map1, const fr_map<T> & map2
, ft_match match) |
| { | | { |
| ft_size size1 = map1.size(), size2 = map2.size(); | | ft_size size1 = map1.size(), size2 = map2.size(); |
| if (size1 == 0 || size2 == 0) | | if (size1 == 0 || size2 == 0) |
| return false; | | return false; |
| | |
| const fr_map<T> & map_iterate = size1 < size2 ? map1 : map2; | | const fr_map<T> & map_iterate = size1 < size2 ? map1 : map2; |
| const fr_map<T> & map_other = size1 < size2 ? map2 : map1; | | const fr_map<T> & map_other = size1 < size2 ? map2 : map1; |
| | |
| skipping to change at line 471 | | skipping to change at line 471 |
|---|
| } | | } |
| | |
| /** | | /** |
| * remove a part of an existing extent (or a whole existing extent) | | * remove a part of an existing extent (or a whole existing extent) |
| * from this fr_map, splitting the existing extent if needed. | | * from this fr_map, splitting the existing extent if needed. |
| * throws an assertion failure if extent to remove is not part of existing exten
ts. | | * throws an assertion failure if extent to remove is not part of existing exten
ts. |
| * | | * |
| * does not support removing an extent that is part of TWO OR MORE existing exte
nts. | | * does not support removing an extent that is part of TWO OR MORE existing exte
nts. |
| */ | | */ |
| template<typename T> | | template<typename T> |
|
| void fr_map<T>::remove1(const value_type & extent) | | void fr_map<T>::remove1(const value_type & extent, ft_match match) |
| { | | { |
| ff_assert(!empty()); | | ff_assert(!empty()); |
| const key_type & key = extent.first; | | const key_type & key = extent.first; |
| const mapped_type & value = extent.second; | | const mapped_type & value = extent.second; |
| /* | | /* |
| * pos = "next" extent, i.e. first extent greater than key to remove, | | * pos = "next" extent, i.e. first extent greater than key to remove, |
| * or end() if no such extent exists | | * or end() if no such extent exists |
| */ | | */ |
| iterator pos = super_type::upper_bound(key); | | iterator pos = super_type::upper_bound(key); |
| ff_assert(pos != begin()); | | ff_assert(pos != begin()); |
| /* | | /* |
| * go back one place. pos will now be "prev", | | * go back one place. pos will now be "prev", |
| * i.e. the last extent lesser than or equal to key to remove | | * i.e. the last extent lesser than or equal to key to remove |
| */ | | */ |
| --pos; | | --pos; |
| const key_type & last_key = pos->first; | | const key_type & last_key = pos->first; |
|
| mapped_type & last_value_ = pos->second; | | mapped_type & last_payload = pos->second; |
| | |
| T last_physical = last_key.physical; | | T last_physical = last_key.physical; |
|
| T last_logical = last_value_.logical; | | T last_logical = last_payload.logical; |
| T last_length = last_value_.length; | | T last_length = last_payload.length; |
| ft_size user_data = last_value_.user_data; | | ft_size user_data = last_payload.user_data; |
| | |
| T physical = key.physical; | | T physical = key.physical; |
| T logical = value.logical; | | T logical = value.logical; |
| T length = value.length; | | T length = value.length; |
| | |
| ff_assert(last_physical <= physical); | | ff_assert(last_physical <= physical); |
|
| ff_assert(last_logical <= logical); | | if (match == FC_BOTH) { |
| /* also logical to remove must match */ | | ff_assert(last_logical <= logical); |
| ff_assert(physical - last_physical == logical - last_logical); | | /* also logical to remove must match */ |
| | ff_assert(physical - last_physical == logical - last_logical); |
| | } |
| /* last must finish together or after extent to remove */ | | /* last must finish together or after extent to remove */ |
| ff_assert(last_physical + last_length >= physical + length); | | ff_assert(last_physical + last_length >= physical + length); |
| | |
| /* let's consider extents start points */ | | /* let's consider extents start points */ |
| if (last_physical < physical) { | | if (last_physical < physical) { |
| /* first case: | | /* first case: |
| * "last" existing extent starts before extent to remove | | * "last" existing extent starts before extent to remove |
| * +------------ | | * +------------ |
| * | to_remove | | * | to_remove |
| * +-+------------ | | * +-+------------ |
| * | last extent | | * | last extent |
| * +-------------- | | * +-------------- |
| */ | | */ |
|
| last_value_.length = physical - last_physical; | | last_payload.length = physical - last_physical; |
| } else { | | } else { |
| /* second case: | | /* second case: |
| * "last" existing extent starts together with extent to remove | | * "last" existing extent starts together with extent to remove |
| * +-------------- | | * +-------------- |
| * | to_remove | | * | to_remove |
| * +-------------- | | * +-------------- |
| * | last extent | | * | last extent |
| * +-------------- | | * +-------------- |
| */ | | */ |
| super_type::erase(pos); | | super_type::erase(pos); |
| | |
| skipping to change at line 566 | | skipping to change at line 568 |
|---|
| void fr_map<T>::remove(iterator iter) | | void fr_map<T>::remove(iterator iter) |
| { | | { |
| super_type::erase(iter); | | super_type::erase(iter); |
| } | | } |
| | |
| /** | | /** |
| * remove a part of an existing extent (or one or more existing extents) | | * remove a part of an existing extent (or one or more existing extents) |
| * from this fr_map, splitting the existing extents if needed. | | * from this fr_map, splitting the existing extents if needed. |
| */ | | */ |
| template<typename T> | | template<typename T> |
|
| void fr_map<T>::remove(const value_type & extent) | | void fr_map<T>::remove(const value_type & extent, ft_match match) |
| { | | { |
| fr_map<T> intersect_list; | | fr_map<T> intersect_list; |
|
| intersect_list.intersect_all(*this, extent, FC_BOTH); | | intersect_list.intersect_all(*this, extent, match); |
| const_iterator iter = intersect_list.begin(), end = intersect_list.end(); | | const_iterator iter = intersect_list.begin(), end = intersect_list.end(); |
| for (; iter != end; ++iter) | | for (; iter != end; ++iter) |
|
| remove1(*iter); | | remove1(*iter, match); |
| } | | } |
| | |
| /** | | /** |
| * remove a part of an existing extent (or one or more existing extents) | | * remove a part of an existing extent (or one or more existing extents) |
| * from this fr_map, splitting the existing extents if needed. | | * from this fr_map, splitting the existing extents if needed. |
| */ | | */ |
| template<typename T> | | template<typename T> |
|
| void fr_map<T>::remove(T physical, T logical, T length) | | void fr_map<T>::remove(T physical, T logical, T length, ft_match match) |
| { | | { |
| key_type key = { physical }; | | key_type key = { physical }; |
| mapped_type value = { logical, length, FC_DEFAULT_USER_DATA }; | | mapped_type value = { logical, length, FC_DEFAULT_USER_DATA }; |
| value_type extent(key, value); | | value_type extent(key, value); |
|
| remove(extent); | | remove(extent, match); |
| } | | } |
| | |
| /** | | /** |
| * remove any (partial or full) intersection with existing extents from this fr_
map, | | * remove any (partial or full) intersection with existing extents from this fr_
map, |
| * splitting the existing extents if needed. | | * splitting the existing extents if needed. |
| */ | | */ |
| template<typename T> | | template<typename T> |
|
| void fr_map<T>::remove_all(const fr_map<T> & map) | | void fr_map<T>::remove_all(const fr_map<T> & map, ft_match match) |
| { | | { |
| if (this == & map) { | | if (this == & map) { |
| clear(); | | clear(); |
| return; | | return; |
| } | | } |
| key_type bound_lo, bound_hi; | | key_type bound_lo, bound_hi; |
| bounds(bound_lo, bound_hi); | | bounds(bound_lo, bound_hi); |
| const_iterator iter = map.super_type::upper_bound(bound_lo), end = map.super
_type::lower_bound(bound_hi); | | const_iterator iter = map.super_type::upper_bound(bound_lo), end = map.super
_type::lower_bound(bound_hi); |
| if (iter != map.begin()) | | if (iter != map.begin()) |
| --iter; | | --iter; |
|
| remove_all(iter, end); | | remove_all(iter, end, match); |
| } | | } |
| | |
| /** | | /** |
| * remove an initial part of an existing extent from this fr_map. | | * remove an initial part of an existing extent from this fr_map. |
| * returns iterator to new, smaller extent, or end() if the whole extent was rem
oved | | * returns iterator to new, smaller extent, or end() if the whole extent was rem
oved |
| */ | | */ |
| template<typename T> | | template<typename T> |
| typename fr_map<T>::iterator fr_map<T>::remove_front(iterator iter, T shrink_len
gth) | | typename fr_map<T>::iterator fr_map<T>::remove_front(iterator iter, T shrink_len
gth) |
| { | | { |
| ff_assert(iter != end()); | | ff_assert(iter != end()); |
| | |
| skipping to change at line 714 | | skipping to change at line 716 |
|---|
| for (; iter != end; ++iter) { | | for (; iter != end; ++iter) { |
| const fr_extent<ft_uoff> & extent = * iter; | | const fr_extent<ft_uoff> & extent = * iter; |
| append0(extent.physical() >> effective_block_size_log2, | | append0(extent.physical() >> effective_block_size_log2, |
| extent.logical() >> effective_block_size_log2, | | extent.logical() >> effective_block_size_log2, |
| extent.length() >> effective_block_size_log2, | | extent.length() >> effective_block_size_log2, |
| extent.user_data()); | | extent.user_data()); |
| } | | } |
| } | | } |
| | |
| /** | | /** |
|
| | * shift and merge specified extent vector |
| | * into this map, skipping any intersection. |
| | */ |
| | template<typename T> |
| | void fr_map<T>::merge_shift(const fr_vector<ft_uoff> & other, ft_uoff effective_ |
| | block_size_log2, ft_match match) |
| | { |
| | if (other.empty()) { |
| | // nothing to do |
| | } else if (this->empty()) { |
| | // easy |
| | this->append0_shift(other, effective_block_size_log2); |
| | } else { |
| | fr_map<T> other_map; |
| | |
| | other_map.append0_shift(other, effective_block_size_log2); |
| | |
| | // delete the intersection between this and other |
| | if (match == FC_PHYSICAL1) |
| | other_map.remove_all(* this, FC_PHYSICAL2); |
| | else |
| | this->remove_all(other_map, FC_PHYSICAL2); |
| | |
| | // insert the remainder into this |
| | this->insert_all(other_map); |
| | } |
| | } |
| | |
| | /** |
| * makes the physical complement of 'other' vector, | | * makes the physical complement of 'other' vector, |
| * i.e. calculates the physical extents NOT used in 'other' vector, | | * i.e. calculates the physical extents NOT used in 'other' vector, |
| * shifts them by effective_block_size_log2, | | * shifts them by effective_block_size_log2, |
| * and inserts it in this map (with user_data = FC_DEFAULT_USER_DATA) | | * and inserts it in this map (with user_data = FC_DEFAULT_USER_DATA) |
| * | | * |
| * since the file(s) contained in such complementary extents are not known, | | * since the file(s) contained in such complementary extents are not known, |
| * all calculated extents will have ->logical == ->physical. | | * all calculated extents will have ->logical == ->physical. |
| * | | * |
| * 'other' must be already sorted by physical! | | * 'other' must be already sorted by physical! |
| * does not merge and does not check for merges | | * does not merge and does not check for merges |
| | |
| skipping to change at line 741 | | skipping to change at line 771 |
|---|
| ft_size i, n = other.size(); | | ft_size i, n = other.size(); |
| | |
| if (empty()) | | if (empty()) |
| last = 0; | | last = 0; |
| else { | | else { |
| const value_type & back = *--this->end(); | | const value_type & back = *--this->end(); |
| last = back.first.physical + back.second.length; | | last = back.first.physical + back.second.length; |
| } | | } |
| /* loop on 'other' extents */ | | /* loop on 'other' extents */ |
| for (i = 0; i < n; i++) { | | for (i = 0; i < n; i++) { |
|
| physical = other[i].physical() >> effective_block_size_log2; | | const fr_extent<ft_uoff> & curr = other[i]; |
| | physical = curr.physical() >> effective_block_size_log2; |
| | |
| if (physical == last) { | | if (physical == last) { |
| /* nothing to do */ | | /* nothing to do */ |
| } else if (physical > last) { | | } else if (physical > last) { |
| /* add "hole" with logical == physical */ | | /* add "hole" with logical == physical */ |
| append0(last, last, physical - last, FC_DEFAULT_USER_DATA); | | append0(last, last, physical - last, FC_DEFAULT_USER_DATA); |
| } else { | | } else { |
| /* oops.. some programmer really screwed up */ | | /* oops.. some programmer really screwed up */ |
|
| ff_assert_fail("somebody programmed a call to ft_map<T>::complement0 | | const fr_extent<ft_uoff> & prev = other[i-1]; |
| _physical_shift() with an argument not sorted by ->physical() !"); | | ff_log(FC_FATAL, 0, "internal error in ft_map<T>::complement0_phy |
| | sical_shift():"); |
| | ff_log(FC_FATAL, 0, "\textent[%" FT_ULL "] = {physical = %" FT_UL |
| | L ", logical = %" FT_ULL ", length = %" FT_ULL " /* physical end = %" FT_ULL " * |
| | /} does not end before", |
| | (ft_ull) (i-1), (ft_ull) prev.physical(), (ft_ull |
| | ) prev.logical(), (ft_ull) prev.length(), (ft_ull) (prev.physical() + prev.lengt |
| | h())); |
| | ff_log(FC_FATAL, 0, "\textent[%" FT_ULL "] = {physical = %" FT_UL |
| | L ", logical = %" FT_ULL ", length = %" FT_ULL " /* physical end = %" FT_ULL " * |
| | /}", |
| | (ft_ull) i, (ft_ull) curr.physical(), (ft_ull |
| | ) curr.logical(), (ft_ull) curr.length(), (ft_ull) (curr.physical() + curr.lengt |
| | h())); |
| | ff_assert_fail("internal error in ft_map<T>::complement0_physical_sh |
| | ift(): map is not sorted by ->physical()"); |
| } | | } |
| | |
|
| last = physical + (other[i].length() >> effective_block_size_log2); | | last = physical + (curr.length() >> effective_block_size_log2); |
| } | | } |
| device_length >>= effective_block_size_log2; | | device_length >>= effective_block_size_log2; |
| if (last < device_length) { | | if (last < device_length) { |
| /* add last "hole" with logical == physical */ | | /* add last "hole" with logical == physical */ |
| append0(last, last, device_length - last, FC_DEFAULT_USER_DATA); | | append0(last, last, device_length - last, FC_DEFAULT_USER_DATA); |
| } | | } |
| } | | } |
| | |
| /** | | /** |
| * makes the logical complement of 'other' vector, | | * makes the logical complement of 'other' vector, |
| | |
| skipping to change at line 789 | | skipping to change at line 826 |
|---|
| ft_size i, n = other.size(); | | ft_size i, n = other.size(); |
| | |
| if (empty()) | | if (empty()) |
| last = 0; | | last = 0; |
| else { | | else { |
| const mapped_type & back = (--this->end())->second; | | const mapped_type & back = (--this->end())->second; |
| last = back.logical + back.length; | | last = back.logical + back.length; |
| } | | } |
| /* loop on 'other' extents */ | | /* loop on 'other' extents */ |
| for (i = 0; i < n; i++) { | | for (i = 0; i < n; i++) { |
|
| logical = other[i].logical() >> effective_block_size_log2; | | const fr_extent<ft_uoff> & curr = other[i]; |
| | logical = curr.logical() >> effective_block_size_log2; |
| | |
| if (logical == last) { | | if (logical == last) { |
| /* nothing to do */ | | /* nothing to do */ |
| } else if (logical > last) { | | } else if (logical > last) { |
| /* add "hole" with logical == logical */ | | /* add "hole" with logical == logical */ |
| append0(last, last, logical - last, FC_DEFAULT_USER_DATA); | | append0(last, last, logical - last, FC_DEFAULT_USER_DATA); |
| } else { | | } else { |
| /* oops.. some programmer really screwed up */ | | /* oops.. some programmer really screwed up */ |
|
| | const fr_extent<ft_uoff> & prev = other[i-1]; |
| | ff_log(FC_FATAL, 0, "internal error in ft_map<T>::complement0_log |
| | ical_shift():"); |
| | ff_log(FC_FATAL, 0, "\textent[%" FT_ULL "] = {physical = %" FT_UL |
| | L ", logical = %" FT_ULL ", length = %" FT_ULL " /* logical end = %" FT_ULL " */ |
| | } does not end before", |
| | (ft_ull) (i-1), (ft_ull) prev.physical(), (ft_ull |
| | ) prev.logical(), (ft_ull) prev.length(), (ft_ull) (prev.logical() + prev.length |
| | ())); |
| | ff_log(FC_FATAL, 0, "\textent[%" FT_ULL "] = {physical = %" FT_UL |
| | L ", logical = %" FT_ULL ", length = %" FT_ULL " /* logical end = %" FT_ULL " */ |
| | }", |
| | (ft_ull) i, (ft_ull) curr.physical(), (ft_ull |
| | ) curr.logical(), (ft_ull) curr.length(), (ft_ull) (curr.logical() + curr.length |
| | ())); |
| ff_assert_fail("somebody programmed a call to ft_map<T>::complement0
_logical_shift() with an argument not sorted by ->logical() !"); | | ff_assert_fail("somebody programmed a call to ft_map<T>::complement0
_logical_shift() with an argument not sorted by ->logical() !"); |
| } | | } |
| | |
|
| last = logical + (other[i].length() >> effective_block_size_log2); | | last = logical + (curr.length() >> effective_block_size_log2); |
| } | | } |
| /* | | /* |
| * NOTE: right-shifting device_length by effective_block_size_log2 | | * NOTE: right-shifting device_length by effective_block_size_log2 |
| * forgets any odd-sized last device block | | * forgets any odd-sized last device block |
| */ | | */ |
| device_length >>= effective_block_size_log2; | | device_length >>= effective_block_size_log2; |
| if (last < device_length) { | | if (last < device_length) { |
| /* add last "hole" with logical == logical */ | | /* add last "hole" with logical == logical */ |
| append0(last, last, device_length - last, FC_DEFAULT_USER_DATA); | | append0(last, last, device_length - last, FC_DEFAULT_USER_DATA); |
| } | | } |
| } | | } |
| | |
|
| | /** print map contents to log */ |
| | template<typename T> |
| | void fr_map<T>::show(const char * label1, const char * label2, ft_uoff effective |
| | _block_size, ft_log_level level) const |
| | { |
| | fr_extent<T>::show(this->begin(), this->end(), this->size(), label1, labe |
| | l2, effective_block_size, level); |
| | } |
| | |
| FT_NAMESPACE_END | | FT_NAMESPACE_END |
| | | |
| End of changes. 21 change blocks. |
|---|
| 23 lines changed or deleted | | 95 lines changed or added |
|---|
"Fossies" - the Fresh Open Source Software Archive 