segmented_list.hpp

Go to the documentation of this file.

/*
 
Copyright 2025 Matthew Tolman
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
   http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
 
*/
 
#ifndef MTCORE_STABLE_VEC_HPP
#define MTCORE_STABLE_VEC_HPP
 
#include "../alloc.hpp"
#include "../core.hpp"
#include "../traits.hpp"
#include "slice.hpp"
 
namespace mtcore {
  template<typename T>
  struct SegmentedList {
    using Elem = T;
 
  private:
    struct Segment {
      Slice<T> elements = {};
      Segment *next     = nullptr;
    };
 
    Segment start        = {};
    Segment *end         = &start;
    size_t endIndex      = 0;
    size_t len           = 0;
    size_t totalCapacity = 0;
 
  public:
    struct PtrIter {
      size_t index = 0;
      const SegmentedList &r;
      size_t segmentIndex = 0;
      Segment *s;

      Optional<T *> next() {
        if (s == nullptr || index >= r.size()) {
          return nullopt;
        }
        if (s->elements.size() <= segmentIndex) {
          s            = s->next;
          segmentIndex = 0;
        }
        if (s == nullptr) {
          return nullopt;
        }
        ++index;
        return &s->elements[segmentIndex++];
      }
    };

    struct ConstPtrIter {
      size_t index = 0;
      const SegmentedList &r;
      size_t segmentIndex = 0;
      const Segment *s;

      Optional<const T *> next() {
        if (s == nullptr || index >= r.size()) {
          return nullopt;
        }
        if (s->elements.size() <= segmentIndex) {
          s            = s->next;
          segmentIndex = 0;
        }
        if (s == nullptr) {
          return nullopt;
        }
        ++index;
        return &s->elements[segmentIndex++];
      }
    };

    struct ConstIter {
      size_t index = 0;
      const SegmentedList &r;
      size_t segmentIndex = 0;
      const Segment *s;

      Optional<T> next() {
        if (s == nullptr || index >= r.size()) {
          return nullopt;
        }
        if (s->elements.size() <= segmentIndex) {
          s            = s->next;
          segmentIndex = 0;
        }
        if (s == nullptr) {
          return nullopt;
        }
        ++index;
        return s->elements[segmentIndex++];
      }
    };

    [[nodiscard]] PtrIter ptr_iter() noexcept {
      ensure(start.elements.head, "NOT INITIALIZED");
      return {0, *this, 0, &start};
    }

    [[nodiscard]] ConstPtrIter ptr_iter() const noexcept {
      ensure(start.elements.head, "NOT INITIALIZED");
      return {0, *this, 0, &start};
    }

    [[nodiscard]] ConstIter iter() const noexcept {
      ensure(start.elements.head, "NOT INITIALIZED");
      return {0, *this, 0, &start};
    }

    [[nodiscard]] size_t size() const noexcept { return len; }

    [[nodiscard]] Result<void, AllocationError> init(Allocator &alloc, size_t initCapacity) {
      ensure(initCapacity > 0, "NO INITIAL CAPACITY");
      ensure(start.elements.head == nullptr, "ALREADY INITIALIZED");
      ensure(start.elements.size() == 0, "ALREADY INITIALIZED");
      ensure(start.next == nullptr, "ALREADY INITIALIZED");
 
      auto allocRes = alloc.create_many<T>(initCapacity);
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      start.elements = *allocRes;
      totalCapacity  = initCapacity;
      return success();
    }

    [[nodiscard]] Result<void, AllocationError> init(Allocator &alloc, std::initializer_list<T> list) {
      ensure(start.elements.head == nullptr, "ALREADY INITIALIZED");
      ensure(list.size() > 0, "NO INITIAL CAPACITY");
      ensure(!start.elements.head, "ALREADY INITIALIZED");
      ensure(!start.elements.size(), "ALREADY INITIALIZED");
      ensure(!start.next, "ALREADY INITIALIZED");
 
      auto allocRes = alloc.create_many<T>(list.size());
      if (allocRes.is_error()) {
        return allocRes.error();
      }
      totalCapacity = list.size();
 
      start.elements = *allocRes;
 
      size_t i = 0;
      for (const auto &elem: list) {
        start.elements[i++] = elem;
      }
      len = list.size();
      end = &start;
 
      return success();
    }

    void deinit(Allocator &alloc) {
      if (start.elements.head != nullptr) {
        alloc.destroy_many(start.elements);
      }
      if (start.next != nullptr) {
        Segment *cur = start.next;
        while (cur) {
          Segment *next = cur->next;
          alloc.destroy_many(cur->elements);
          alloc.destroy(cur);
          cur = next;
        }
      }
      totalCapacity = 0;
      end           = nullptr;
    }

    void drop_unused_segments(Allocator &alloc) {
      ensure(start.elements.head, "NOT INITIALIZED");
      Segment *prev    = &start;
      Segment *cur     = start.next;
      end              = &start;
      size_t remaining = size();
      while (cur) {
        if (remaining > prev->elements.len) {
          remaining -= prev->elements.len;
          auto next = cur->next;
          end       = cur;
          prev      = cur;
          cur       = next;
        }
        else {
          prev->next = nullptr;
          while (cur) {
            Segment *next = cur->next;
            totalCapacity -= cur->elements.size();
            alloc.destroy_many(cur->elements);
            alloc.destroy(cur);
            cur = next;
          }
          break;
        }
      }
    }

    [[nodiscard]] Result<void, CollectionAddNoAllocationError> push(const T &elem) noexcept {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
 
      Segment *cur = end;
      ensure(cur);
      if (endIndex < cur->elements.size()) {
        mtdefer { ++len; };
        cur->elements[endIndex++] = elem;
        return success();
      }
      return error(CollectionAddNoAllocationError::NO_ROOM);
    }

    [[nodiscard]] Result<void, AllocationError> push(Allocator &alloc, const T &elem) noexcept {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
 
      Segment *cur = end;
      if (endIndex < cur->elements.size()) {
        mtdefer { ++len; };
        cur->elements[endIndex++] = elem;
        return success();
      }
 
      auto allocSegRes = alloc.create<Segment>();
 
      if (allocSegRes.is_error()) {
        return allocSegRes.error();
      }
 
      auto allocElemRes = alloc.create_many<T>(cur->elements.size() + cur->elements.size() / 2);
      if (allocElemRes.is_error()) {
        alloc.destroy(*allocSegRes);
        return allocElemRes.error();
      }
      mtdefer { ++len; };
      cur->next                 = *allocSegRes;
      end                       = cur->next;
      endIndex                  = 0;
      cur                       = cur->next;
      cur->elements             = *allocElemRes;
      cur->elements[endIndex++] = elem;
      end                       = cur;
      totalCapacity += cur->elements.size();
      return success();
    }

    [[nodiscard]] const T &operator[](size_t index) const noexcept {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      return at(index);
    }

    [[nodiscard]] T &operator[](size_t index) noexcept {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      return at(index);
    }

    [[nodiscard]] const T &at(size_t index) const noexcept {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      ensure(index < len, "OUT OF BOUNDS ACCESS");
      const Segment *cur = &start;
      while (cur) {
        if (index < cur->elements.len) {
          return cur->elements[index];
        }
        index -= cur->elements.len;
        cur = cur->next;
      }
      unreachable("OUT OF BOUNDS ACCESS");
    }

    [[nodiscard]] T &at(size_t index) noexcept {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      ensure(index < len, "OUT OF BOUNDS ACCESS");
      Segment *cur = &start;
      while (cur) {
        if (index < cur->elements.size()) {
          return cur->elements[index];
        }
        index -= cur->elements.size();
        cur = cur->next;
      }
      unreachable("OUT OF BOUNDS ACCESS");
    }

    [[nodiscard]] bool operator==(const SegmentedList &other) {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      ensure(other.start.elements.head != nullptr, "NOT INITIALIZED");
      if (len != other.len) {
        return false;
      }
      for (size_t i = 0; i < len; ++i) {
        if (at(i) != other.at(i)) {
          return false;
        }
      }
      return true;
    }

    [[nodiscard]] bool operator!=(const SegmentedList &other) { return !(*this == other); }

    void pop() {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      if (len > 0) {
        --len;
      }
    }
 
    [[nodiscard]] size_t capacity() const { return totalCapacity; }
  };
 
  static_assert(is_mutable_addressable<SegmentedList<int>>, "segmented_list<int> is not mutable addressable");
}  // namespace mtcore
 
#endif  // MTCORE_STABLE_VEC_HPP