// Copyright 2018 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.

#pragma once

#ifdef __cplusplus

#include <stdint.h>

#include <fbl/alloc_checker.h>
#include <fbl/intrusive_wavl_tree.h>
#include <fbl/unique_ptr.h>
#include <fbl/vector.h>
#include <fvm/format.h>

namespace fvm {

class SliceExtent : public fbl::WAVLTreeContainable<fbl::unique_ptr<SliceExtent>> {
public:
    SliceExtent() = delete;
    explicit SliceExtent(uint64_t vslice_start) : vslice_start_(vslice_start) {}
    SliceExtent(const SliceExtent&) = delete;
    SliceExtent(SliceExtent&&) = delete;
    SliceExtent& operator=(const SliceExtent&) = delete;
    SliceExtent& operator=(SliceExtent&&) = delete;
    ~SliceExtent() = default;

    uint64_t GetKey() const { return vslice_start_; }

    // Vslice start (inclusive)
    uint64_t start() const { return vslice_start_; }

    // Vslice end (exclusive)
    uint64_t end() const { return vslice_start_ + pslices_.size(); }

    // Extent length
    uint64_t size() const { return end() - start(); }

    // Look up a pslice given a vslice
    bool find(uint64_t vslice, uint64_t* out_pslice) const {
        size_t offset = vslice - vslice_start_;
        if (offset >= pslices_.size()) {
            return false;
        }
        *out_pslice = at(vslice);
        return true;
    }

    uint64_t at(uint64_t vslice) const {
        ZX_ASSERT(vslice >= vslice_start_);
        uint64_t offset = vslice - vslice_start_;
        ZX_ASSERT(offset < pslices_.size());
        return pslices_[offset];
    }

    bool contains(uint64_t vslice) const {
        uint64_t pslice;
        return find(vslice, &pslice);
    }

    // Breaks the extent from:
    //   [start(), end())
    // Into:
    //   [start(), vslice] and [vslice + 1, end()).
    // Returns the latter extent on success; returns nullptr
    // if a memory allocation failure occurs.
    fbl::unique_ptr<SliceExtent> Split(uint64_t vslice);

    // Combines the other extent into this one.
    // 'other' must immediately follow the current slice.
    void Merge(const SliceExtent& other);

    void push_back(uint64_t pslice) { pslices_.push_back(pslice); }

    void pop_back() { pslices_.pop_back(); }

    bool empty() const { return pslices_.size() == 0; }

private:
    friend class TypeWAVLTraits;

    fbl::Vector<uint64_t> pslices_;
    const uint64_t vslice_start_;
};

} // namespace fvm

#endif // __cplusplus