\$\begingroup\$
\$\endgroup\$
#pragma once
#include <ntddk.h>
#include "move.h"
#include "testingMacro.h"
#include "util.h"
namespace anon {
namespace __vectorDetail {
//
// Global instance of a DPC queue of freeDpc
// which is necessary because we're not always at an
// IRQL level which allows us to call ExFreePool.
// It holds medium priority which should lead to us
// always freeing at APC_LEVEL.
//
inline KDPC kdpc;
//
// State holder for freeNowOrDpc, set to true
// once we initialize `kdpc`.
//
static LONG inited = 0;
//
// Function used in the initialization of `kdpc`.
//
static void freeDpc(PKDPC dpc, PVOID deferredContext, PVOID arg1, PVOID arg2) {
UNREFERENCED_PARAMETER(dpc);
UNREFERENCED_PARAMETER(deferredContext);
UNREFERENCED_PARAMETER(arg2);
ExFreePool(arg1);
}
//
// Function used to handle freeing memory, either
// frees now if possible, or schedules dpc.
//
static void freeNowOrDpc(PVOID ptr) {
if (KeGetCurrentIrql() <= APC_LEVEL)
ExFreePool(ptr);
else {
if (inited != 1) {
InterlockedExchange(&inited, 1);
KeInitializeDpc(&kdpc, freeDpc, nullptr);
}
KeInsertQueueDpc(&kdpc, ptr, nullptr);
}
}
} // namespace __vectorDetail
//
// Note: you are still responsible for IRQL safety despite there being
// safety for frees manually implemented through DPC.
//
template <class _Ty, ULONG _PoolFlags, ULONG _Tag = 'ANON'>
class vector {
public:
vector() : m_data(nullptr), m_size(0), m_capacity(0) {}
ANON_NOINLINE_T vector& operator=(const vector& other) {
if (m_data) __vectorDetail::freeNowOrDpc(m_data);
m_size = other.m_size;
m_data = (_Ty*)ExAllocatePool2(
_PoolFlags, (m_capacity = calculateCapacity(m_size)), _Tag);
// T must be copiable
for (auto i = 0u; i < m_size; i++) new (&m_data[i]) _Ty(*other[i]);
return *this;
}
ANON_NOINLINE_T vector& operator=(vector&& other) noexcept {
if (m_data) __vectorDetail::freeNowOrDpc(m_data);
m_data = other.m_data;
m_capacity = other.m_capacity;
m_size = other.m_size;
other.m_data = nullptr;
other.m_capacity = other.m_size = 0;
return *this;
}
ANON_NOINLINE_T vector(const vector& other) { *this = other; }
ANON_NOINLINE_T vector(vector&& other) noexcept { *this = move(other); }
ANON_NOINLINE_T ~vector() {
if (m_data) {
for (auto i = 0u; i < m_size; i++) m_data[i].~_Ty();
__vectorDetail::freeNowOrDpc(m_data);
}
m_data = nullptr;
m_size = m_capacity = 0;
}
//
// Front element
//
ANON_NOINLINE_T _Ty* front() noexcept {
if (m_size > 0) return &m_data[0];
return nullptr;
}
//
// Back element
//
ANON_NOINLINE_T _Ty* back() noexcept {
if (m_size > 0) return &m_data[m_size - 1];
return nullptr;
}
//
// Const front element
//
ANON_NOINLINE_T const _Ty* front() const noexcept {
if (m_size > 0) return &m_data[0];
return nullptr;
}
//
// Const back element
//
ANON_NOINLINE_T const _Ty* back() const noexcept {
if (m_size > 0) return &m_data[m_size - 1];
return nullptr;
}
//
// Operator[]
//
ANON_NOINLINE_T _Ty* operator[](size_t i) noexcept {
if (i >= 0 && i < m_size) return &m_data[i];
return nullptr;
}
//
// Const operator[]
//
ANON_NOINLINE_T const _Ty* operator[](size_t i) const noexcept {
if (i >= 0 && i < m_size) return &m_data[i];
return nullptr;
}
//
// Data
//
ANON_NOINLINE_T _Ty* data() noexcept { return m_data; }
//
// Const data
//
ANON_NOINLINE_T const _Ty* data() const noexcept { return m_data; }
//
// Preallocate for a size if the capacity is currently 0.
//
ANON_NOINLINE_T void reserve(size_t n) {
if (!m_data || m_capacity == 0) reallocate(calculateCapacityExact(n));
}
//
// Does placement-new by copy constructor
//
ANON_NOINLINE_T void pushBack(const _Ty& some) {
if (auto capacity = calculateCapacityExact(m_size + 1);
!m_data || m_capacity < capacity)
reallocate(capacity);
new (&m_data[m_size]) _Ty(some);
m_size++;
}
//
// Does placement-new by move constructor
//
ANON_NOINLINE_T void pushBack(_Ty&& some) {
if (auto capacity = calculateCapacityExact(m_size + 1);
!m_data || m_capacity < capacity)
reallocate(capacity);
new (&m_data[m_size]) _Ty(move(some));
m_size++;
}
//
// Calls destructor on back() then decrements size
//
ANON_NOINLINE_T void popBack() {
if (m_size > 0) {
back()->~_Ty();
m_size -= 1;
}
}
//
// Gets size
//
ANON_NOINLINE_T size_t size() const noexcept { return m_size; }
//
// Gets capacity
//
ANON_NOINLINE_T size_t capacity() const noexcept { return m_capacity; }
//
// Calls destructors then sets size to 0
//
ANON_NOINLINE_T void clear() {
if (m_data)
for (auto i = 0u; i < m_size; i++) m_data[i].~_Ty();
m_size = 0;
}
//
// If size is 0, then frees and sets capacity to 0,
// otherwise it copies to a buffer of capacity ceilPo2(size)
//
ANON_NOINLINE_T void shrinkToFit() {
if (m_size == 0) {
if (m_data) __vectorDetail::freeNowOrDpc(m_data);
m_data = nullptr;
m_capacity = 0;
} else if (m_capacity > 0) {
size_t oldCapacity = m_capacity;
size_t newCapacity = calculateCapacity(m_size);
if (oldCapacity <= newCapacity) return;
reallocateExact(newCapacity);
}
}
private:
//
// Calculate exact (non-rounded-up) size in bytes of N elements
//
ULONGLONG calculateCapacityExact(size_t n) { return sizeof(_Ty) * n; }
//
// Calculate size (rounded-up) in bytes of N elements
//
ULONGLONG calculateCapacity(size_t n) {
return util::ceilPo2(calculateCapacityExact(n));
}
//
// Copy operation
//
void copy(PVOID dest, size_t elements) {
if (m_size > 0 && m_size >= elements)
RtlCopyMemory(dest, m_data, calculateCapacityExact(elements));
}
//
// Reallocate and copy to buffer of exact `capacity`
//
void reallocateExact(ULONGLONG capacity) {
if (capacity < calculateCapacityExact(m_size)) {
ASSERT(false);
return;
}
PVOID newPtr = ExAllocatePool2(_PoolFlags, (m_capacity = capacity), _Tag);
ASSERT(newPtr);
copy(newPtr, m_size);
if (m_data) __vectorDetail::freeNowOrDpc(m_data);
m_data = (_Ty*)newPtr;
}
//
// Reallocate and copy to buffer of capacity equal to ceilPo2(capacity)
//
void reallocate(ULONGLONG capacity) {
reallocateExact(util::ceilPo2(capacity));
}
protected:
_Ty* m_data = nullptr;
size_t m_size = 0;
size_t m_capacity = 0;
};
} // namespace anon
Some notes:
- It looks like I'm mixing allocators, however I also implement
new
anddelete
myself, therefore I know that allocators are not infact being mixed. One may argue that this is bad practice, and I don't disagree. ANON_TESTING_T
is a macro which expands to__declspec(noinline)
in testing builds, to make debugging easier.
lang-cpp