| // Copyright 2019 The Fuchsia Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #ifndef SRC_STORAGE_LIB_RANGE_RANGE_H_ | |
| #define SRC_STORAGE_LIB_RANGE_RANGE_H_ | |
| #include <zircon/assert.h> | |
| #include <zircon/errors.h> | |
| #include <zircon/types.h> | |
| #include <algorithm> | |
| #include <type_traits> | |
| namespace range { | |
| // Provides default mechanisms for accessing and updating the range within the | |
| // RangeContainer. This abstraction allows customized versions of |Range| to | |
| // access these semantics from arbitrary containers. | |
| template <typename RangeContainer, typename KeyType> | |
| struct DefaultRangeTraits { | |
| // Returns the start of the range (inclusive). | |
| static KeyType Start(const RangeContainer& obj) { return obj.Start(); } | |
| // Returns the end of the range (exclusive). | |
| static KeyType End(const RangeContainer& obj) { return obj.End(); } | |
| // Updates |obj| with a new |start| and |end|. | |
| // | |
| // ARGUMENTS: | |
| // | |
| // If |other| is nullptr, then |obj| is being updated independently (typically, | |
| // when the range is shrinking). | |
| // If |other| is not nullptr, then |obj| is being updated due to a merge with |other|. | |
| // |obj| must not be nullptr. | |
| // | |
| // BEHAVIOR: | |
| // | |
| // - If the merge with |other| is valid, |Start()| and |End()| should be updated to return the | |
| // new values, and ZX_OK should be returned. | |
| // - If the merge with |other| is invalid, an error status should be returned, and |Start()| | |
| // and |End()| must return unmodified values. | |
| // - If |other| is null, then ZX_OK must be returned. | |
| static zx_status_t Update(const RangeContainer* other, KeyType start, KeyType end, | |
| RangeContainer* obj) { | |
| // The default implementation has no reason to reject any merges. | |
| obj->Update(start, end); | |
| return ZX_OK; | |
| } | |
| }; | |
| // Provides a default container for storing range values. | |
| // If a custom container is utilized, custom traits may also be supplied to |Range|'s | |
| // template arguments to alter how these fields are accessed. | |
| template <typename KeyType> | |
| class DefaultRangeContainer { | |
| public: | |
| DefaultRangeContainer() = default; | |
| DefaultRangeContainer(KeyType start, KeyType end) : start_(start), end_(end) {} | |
| [[nodiscard]] KeyType Start() const { return start_; } | |
| [[nodiscard]] KeyType End() const { return end_; } | |
| void Update(KeyType start, KeyType end) { | |
| start_ = start; | |
| end_ = end; | |
| } | |
| private: | |
| KeyType start_ = 0; | |
| KeyType end_ = 0; | |
| }; | |
| // Range is a half closed interval [start, end). | |
| // | |
| // The values of the range are stored in a |Container| type, which holds these values. | |
| // |ContainerTraits| describes how these values may be extracted from the |Container| type. | |
| template <typename _KeyType = uint64_t, typename _Container = DefaultRangeContainer<_KeyType>, | |
| typename _ContainerTraits = DefaultRangeTraits<_Container, _KeyType>> | |
| class Range { | |
| public: | |
| using KeyType = _KeyType; | |
| using Container = _Container; | |
| using ContainerTraits = _ContainerTraits; | |
| static_assert(std::is_unsigned_v<KeyType>); | |
| // Creates Range from [start, end). | |
| template < | |
| typename T = KeyType, | |
| std::enable_if_t<std::is_convertible<Container, DefaultRangeContainer<T>>::value, int> = 0> | |
| Range(KeyType start, KeyType end) : container_(start, end) {} | |
| explicit Range(Container container) : container_(std::move(container)) {} | |
| Range() = delete; | |
| Range(const Range&) = default; | |
| Range& operator=(const Range&) = default; | |
| Range& operator=(Range&&) = default; | |
| bool operator==(Range const& y) const { return (Start() == y.Start()) && (End() == y.End()); } | |
| bool operator!=(Range const& y) const { return (Start() != y.Start()) || (End() != y.End()); } | |
| ~Range() = default; | |
| [[nodiscard]] KeyType Start() const { return ContainerTraits::Start(container_); } | |
| [[nodiscard]] KeyType End() const { return ContainerTraits::End(container_); } | |
| // The length of the range is end - start. When start => end, then length is | |
| // considered as zero. | |
| [[nodiscard]] KeyType Length() const { | |
| if (End() <= Start()) { | |
| return KeyType(0); | |
| } | |
| return End() - Start(); | |
| } | |
| // Merges another range into this one by modifying the start and end | |
| // of the current range object. | |
| // | |
| // Returns an error if the two ranges cannot be merged. | |
| zx_status_t Merge(const Range& other) { | |
| if (!Mergable(*this, other)) { | |
| return ZX_ERR_OUT_OF_RANGE; | |
| } | |
| KeyType current_start = Start(); | |
| KeyType current_end = End(); | |
| KeyType new_start = std::min(Start(), other.Start()); | |
| KeyType new_end = std::max(End(), other.End()); | |
| zx_status_t status = | |
| ContainerTraits::Update(&other.container(), new_start, new_end, &container_); | |
| if (status != ZX_OK) { | |
| // |Start()| and |End()| must not change on error. | |
| ZX_DEBUG_ASSERT(current_start == Start()); | |
| ZX_DEBUG_ASSERT(current_end == End()); | |
| } else { | |
| // |Start()| and |End()| should have updated on success. | |
| ZX_DEBUG_ASSERT(new_start == Start()); | |
| ZX_DEBUG_ASSERT(new_end == End()); | |
| } | |
| return status; | |
| } | |
| // Extracts the container from underneath the range object. | |
| // | |
| // This operation invalidates the Range object. | |
| Container release() { return std::move(container_); } | |
| [[nodiscard]] const Container& container() const { return container_; } | |
| private: | |
| Container container_; | |
| }; | |
| // Returns true if two extents overlap. | |
| template <typename R> | |
| bool Overlap(const R& x, const R& y) { | |
| if (x.Length() == 0 || y.Length() == 0) { | |
| return false; | |
| } | |
| auto max_start = std::max(x.Start(), y.Start()); | |
| auto min_end = std::min(x.End(), y.End()); | |
| return max_start < min_end; | |
| } | |
| // Returns true if two extents are adjacent. Two ranges are considered adjacent | |
| // if one range starts right after another ends i.e. [a, b) [b, c] are | |
| // adjacent ranges where a < b < c. | |
| template <typename R> | |
| bool Adjacent(const R& x, const R& y) { | |
| if (x.Length() == 0 || y.Length() == 0) { | |
| return false; | |
| } | |
| if (Overlap(x, y)) { | |
| return false; | |
| } | |
| auto max_start = std::max(x.Start(), y.Start()); | |
| auto min_end = std::min(x.End(), y.End()); | |
| return max_start == min_end; | |
| } | |
| // Two ranges are mergable is they either overlap or are adjacent. | |
| template <typename R> | |
| bool Mergable(const R& x, const R& y) { | |
| return Adjacent(x, y) || Overlap(x, y); | |
| } | |
| // Returns true if |x| contains |y|. | |
| // Ex. | |
| // ASSERT_TRUE(Contains(Range(1, 10). Range(4, 8))); | |
| // ASSERT_TRUE(Contains(Range(1, 10). Range(1, 10))); | |
| // ASSERT_FALSE(Contains(Range(4, 8). Range(1, 10))); | |
| // ASSERT_FALSE(Contains(Range(1, 10). Range(5, 11))); | |
| // ASSERT_FALSE(Contains(Range(4, 8). Range(1, 5))); | |
| template <typename R> | |
| bool Contains(const R& x, const R& y) { | |
| if (x.Length() == 0 || y.Length() == 0) { | |
| return false; | |
| } | |
| return (x.Start() <= y.Start() && x.End() >= y.End()); | |
| } | |
| extern template class Range<uint64_t>; | |
| extern template bool Overlap<Range<uint64_t>>(const Range<uint64_t>& x, const Range<uint64_t>& y); | |
| extern template bool Adjacent<Range<uint64_t>>(const Range<uint64_t>& x, const Range<uint64_t>& y); | |
| extern template bool Mergable<Range<uint64_t>>(const Range<uint64_t>& x, const Range<uint64_t>& y); | |
| } // namespace range | |
| #endif // SRC_STORAGE_LIB_RANGE_RANGE_H_ |