gen_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.
 
*/
 
#pragma once
 
#ifndef MTCORE_GEN_LIST_HPP
#define MTCORE_GEN_LIST_HPP
 
#include "../alloc.hpp"
#include "../core.hpp"
#include "array_list.hpp"
#include "bitset.hpp"
#include "optional.hpp"
#include "result.hpp"
 
namespace mtcore {
  struct Handle {
    size_t index;
    size_t generation;
  };

  template<typename T>
  struct GenList {

    Result<void, AllocationError> init(Allocator &alloc, size_t initCapacity = 64) {
      if (auto res = entries.init(alloc, initCapacity); res.is_error()) {
        return res;
      }
      if (auto res = dead.init(alloc, initCapacity); res.is_error()) {
        entries.deinit(alloc);
        return res;
      }
      dead.set_all(false);
      return success();
    }

    void deinit(Allocator &alloc) {
      entries.deinit(alloc);
      dead.deinit(alloc);
    }

    Result<Handle, CollectionAddNoAllocationError> add(const T &item) noexcept {
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      auto index = dead.first_set();
      if (index.has_value() && index.value() < entries.size()) {
        auto i = *index;
        ensure(dead[i], "BAD INDEX");
        entries[i].generation += 1;
        entries[i].item = item;
        dead.set(i, false);
        return success(Handle{i, entries[i].generation});
      }
 
      size_t i = entries.size();
      if (auto res = entries.push(Gen{item, 0}); res.is_error()) {
        return res.error();
      }
      return success(Handle{i, 0});
    }

    Result<Handle, AllocationError> add(Allocator &alloc, const T &item) noexcept {
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (auto res = add(item); res.is_success()) {
        return res.value();
      }
 
      entries.reserve(alloc, entries.capacity() * 2);
      dead.resize(alloc, entries.capacity(), true);
 
      return add(item).value();
    }

    const T &operator[](const Handle &handle) const noexcept {
      auto index = handle.index;
      ensure(entries[index].generation == handle.generation, "INVALID HANDLE, BAD GENERATION");
      return entries[index].item;
    }

    T &operator[](const Handle &handle) noexcept {
      auto index = handle.index;
      ensure(entries[index].generation == handle.generation, "INVALID HANDLE, BAD GENERATION");
      return entries[index].item;
    }

    Optional<T> at(const Handle &handle) const noexcept {
      auto index = handle.index;
      if (index >= entries.size()) {
        return nullopt;
      }
      if (entries[index].generation != handle.generation) {
        return nullopt;
      }
      return entries[index].item;
    }

    [[nodiscard]] bool is_handle_valid(const Handle &handle) const noexcept {
      if (handle.index >= entries.size()) {
        return false;
      }
      if (dead[handle.index]) {
        return false;
      }
      if (entries[handle.index].generation != handle.generation) {
        return false;
      }
      return true;
    }

    [[nodiscard]] size_t size() const noexcept { return entries.size() - dead.pop_count(); }

    [[nodiscard]] size_t capacity() const noexcept { return entries.capacity(); }

    void remove(const Handle &handle) noexcept {
      ensure(is_handle_valid(handle), "BAD HANDLE");
      dead[handle.index] = true;
    }

    struct PtrIter {
      GenList &list;
      size_t index = 0;

      Optional<T *> next() {
        while (index < list.entries.size()) {
          mtdefer { ++index; };
          if (list.dead[index]) {
            continue;
          }
          return &list.entries[index].item;
        }
        return nullopt;
      }
    };

    struct ConstIter {
      const GenList &list;
      size_t index = 0;

      Optional<T> next() {
        while (index < list.entries.size()) {
          mtdefer { ++index; };
          if (list.dead[index]) {
            continue;
          }
          return list.entries[index].item;
        }
        return nullopt;
      }
    };

    struct HandleIter {
      const GenList &list;
      size_t index = 0;

      Optional<Handle> next() {
        while (index < list.entries.size()) {
          mtdefer { ++index; };
          if (list.dead[index]) {
            continue;
          }
          return Handle{index, list.entries[index].generation};
        }
        return nullopt;
      }
    };

    PtrIter ptr_iter() noexcept { return PtrIter{*this}; }

    ConstIter iter() const noexcept { return ConstIter{*this}; }

    HandleIter handles() const noexcept { return HandleIter{*this}; }
 
  private:
    struct Gen {
      T item;
      size_t generation;
    };
 
    ArrayList<Gen> entries = {};
    Bitset dead            = {};
  };
}  // namespace mtcore
 
#endif  // MTCORE_GEN_LIST_HPP