2
\$\begingroup\$
#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:

  1. It looks like I'm mixing allocators, however I also implement new and delete myself, therefore I know that allocators are not infact being mixed. One may argue that this is bad practice, and I don't disagree.
  2. ANON_TESTING_T is a macro which expands to __declspec(noinline) in testing builds, to make debugging easier.
asked Aug 27, 2023 at 15:20
\$\endgroup\$

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.