/*
* Copyright 2026 WebAssembly Community Group participants
*
* 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.
*/
//
// A vector of elements with a maximum size, storing them all in-place. This is
// similar to c++26's inplace_vector, and is basically a small_vector, except
// there is never any dynamic storage.
// TODO: remove when we have c++26
//
#ifndef wasm_support_inplace_vector_h
#define wasm_support_inplace_vector_h
#include <algorithm>
#include <array>
#include <cassert>
#include <iterator>
#include <type_traits>
#include <vector>
#include "support/parent_index_iterator.h"
namespace wasm {
template<typename T, size_t N> class inplace_vector {
// fixed-space storage
size_t usedFixed = 0;
std::array<T, N> fixed{};
public:
using value_type = T;
inplace_vector() {}
inplace_vector(const inplace_vector<T, N>& other)
: usedFixed(other.usedFixed), fixed(other.fixed) {}
inplace_vector(inplace_vector<T, N>&& other)
: usedFixed(other.usedFixed), fixed(std::move(other.fixed)) {}
inplace_vector(std::initializer_list<T> init) {
for (const T& item : init) {
push_back(item);
}
}
inplace_vector(size_t initialSize) { resize(initialSize); }
inplace_vector<T, N>& operator=(const inplace_vector<T, N>& other) {
usedFixed = other.usedFixed;
fixed = other.fixed;
return *this;
}
inplace_vector<T, N>& operator=(inplace_vector<T, N>&& other) {
usedFixed = other.usedFixed;
fixed = std::move(other.fixed);
return *this;
}
T& operator[](size_t i) { return fixed[i]; }
const T& operator[](size_t i) const {
return const_cast<inplace_vector<T, N>&>(*this)[i];
}
void push_back(const T& x) {
assert(usedFixed < N);
fixed[usedFixed++] = x;
}
template<typename... ArgTypes> void emplace_back(ArgTypes&&... Args) {
assert(usedFixed < N);
new (&fixed[usedFixed++]) T(std::forward<ArgTypes>(Args)...);
}
void pop_back() {
assert(usedFixed > 0);
usedFixed--;
}
T& back() {
assert(usedFixed > 0);
return fixed[usedFixed - 1];
}
const T& back() const {
assert(usedFixed > 0);
return fixed[usedFixed - 1];
}
size_t size() const { return usedFixed; }
bool empty() const { return size() == 0; }
void clear() { usedFixed = 0; }
void resize(size_t newSize) {
assert(newSize <= N);
usedFixed = newSize;
}
size_t capacity() const { return N; }
bool operator==(const inplace_vector<T, N>& other) const {
if (usedFixed != other.usedFixed) {
return false;
}
for (size_t i = 0; i < usedFixed; i++) {
if (fixed[i] != other.fixed[i]) {
return false;
}
}
return true;
}
bool operator!=(const inplace_vector<T, N>& other) const {
return !(*this == other);
}
// iteration
struct Iterator : wasm::ParentIndexIterator<inplace_vector<T, N>*, Iterator> {
using value_type = T;
using pointer = T*;
using reference = T&;
Iterator(inplace_vector<T, N>* parent, size_t index)
: wasm::ParentIndexIterator<inplace_vector<T, N>*, Iterator>{parent,
index} {}
T& operator*() const { return (*this->parent)[this->index]; }
T* operator->() const { return &(*this->parent)[this->index]; }
};
struct ConstIterator
: wasm::ParentIndexIterator<const inplace_vector<T, N>*, ConstIterator> {
using value_type = const T;
using pointer = const T*;
using reference = const T&;
ConstIterator(const inplace_vector<T, N>* parent, size_t index)
: wasm::ParentIndexIterator<const inplace_vector<T, N>*, ConstIterator>{
parent, index} {}
ConstIterator(const Iterator& other)
: wasm::ParentIndexIterator<const inplace_vector<T, N>*, ConstIterator>{
other.parent, other.index} {}
const T& operator*() const { return (*this->parent)[this->index]; }
const T* operator->() const { return &(*this->parent)[this->index]; }
};
Iterator begin() { return Iterator(this, 0); }
Iterator end() { return Iterator(this, size()); }
ConstIterator begin() const { return ConstIterator(this, 0); }
ConstIterator end() const { return ConstIterator(this, size()); }
Iterator insert(ConstIterator pos, const T& x) {
assert(usedFixed < N);
assert(pos.index <= usedFixed);
size_t index = pos.index;
std::move_backward(fixed.begin() + index,
fixed.begin() + usedFixed,
fixed.begin() + usedFixed + 1);
fixed[index] = x;
usedFixed++;
return Iterator(this, index);
}
Iterator erase(ConstIterator first, ConstIterator last) {
assert(first.index <= last.index);
assert(last.index <= usedFixed);
size_t numToErase = last.index - first.index;
if (numToErase > 0) {
std::move(fixed.begin() + last.index,
fixed.begin() + usedFixed,
fixed.begin() + first.index);
usedFixed -= numToErase;
}
return Iterator(this, first.index);
}
Iterator erase(Iterator first, Iterator last) {
return erase(ConstIterator(this, first.index),
ConstIterator(this, last.index));
}
Iterator erase(ConstIterator pos) { return erase(pos, pos + 1); }
Iterator erase(Iterator pos) { return erase(pos, pos + 1); }
};
namespace detail {
template<typename T> struct is_inplace_vector_or_derived {
private:
template<typename U, size_t N>
static std::true_type test(const inplace_vector<U, N>*);
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T*>()))::value;
};
} // namespace detail
template<typename Vector, typename Pred>
requires detail::is_inplace_vector_or_derived<Vector>::value
size_t erase_if(Vector& c, Pred pred) {
auto it = std::remove_if(c.begin(), c.end(), pred);
auto r = std::distance(it, c.end());
c.erase(it, c.end());
return r;
}
} // namespace wasm
namespace std {
template<typename Vector, typename Pred>
requires wasm::detail::is_inplace_vector_or_derived<Vector>::value
size_t erase_if(Vector& c, Pred pred) {
return wasm::erase_if(c, pred);
}
} // namespace std
#endif // wasm_support_inplace_vector_h