src/D3D12MemAlloc.cpp

//
// Copyright (c) 2019-2022 Advanced Micro Devices, Inc. All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//

#include "D3D12MemAlloc.h"

#include <combaseapi.h>
#include <mutex>
#include <algorithm>
#include <utility>
#include <cstdlib>
#include <cstdint>
#include <malloc.h> // for _aligned_malloc, _aligned_free
#ifndef _WIN32
    #include <shared_mutex>
#endif

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
// Configuration Begin
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#ifndef _D3D12MA_CONFIGURATION

#ifdef _WIN32
    #if !defined(WINVER) || WINVER < 0x0600
        #error Required at least WinAPI version supporting: client = Windows Vista, server = Windows Server 2008.
    #endif
#endif

#ifndef D3D12MA_SORT
    #define D3D12MA_SORT(beg, end, cmp)  std::sort(beg, end, cmp)
#endif

#ifndef D3D12MA_D3D12_HEADERS_ALREADY_INCLUDED
    #include <dxgi.h>
    #if D3D12MA_DXGI_1_4
        #include <dxgi1_4.h>
    #endif
#endif

#ifndef D3D12MA_ASSERT
    #include <cassert>
    #define D3D12MA_ASSERT(cond) assert(cond)
#endif

// Assert that will be called very often, like inside data structures e.g. operator[].
// Making it non-empty can make program slow.
#ifndef D3D12MA_HEAVY_ASSERT
    #ifdef _DEBUG
        #define D3D12MA_HEAVY_ASSERT(expr)   //D3D12MA_ASSERT(expr)
    #else
        #define D3D12MA_HEAVY_ASSERT(expr)
    #endif
#endif

#ifndef D3D12MA_DEBUG_ALIGNMENT
    /*
    Minimum alignment of all allocations, in bytes.
    Set to more than 1 for debugging purposes only. Must be power of two.
    */
    #define D3D12MA_DEBUG_ALIGNMENT (1)
#endif

#ifndef D3D12MA_DEBUG_MARGIN
    // Minimum margin before and after every allocation, in bytes.
    // Set nonzero for debugging purposes only.
    #define D3D12MA_DEBUG_MARGIN (0)
#endif

#ifndef D3D12MA_DEBUG_GLOBAL_MUTEX
    /*
    Set this to 1 for debugging purposes only, to enable single mutex protecting all
    entry calls to the library. Can be useful for debugging multithreading issues.
    */
    #define D3D12MA_DEBUG_GLOBAL_MUTEX (0)
#endif

/*
Define this macro for debugging purposes only to force specific D3D12_RESOURCE_HEAP_TIER,
especially to test compatibility with D3D12_RESOURCE_HEAP_TIER_1 on modern GPUs.
*/
//#define D3D12MA_FORCE_RESOURCE_HEAP_TIER D3D12_RESOURCE_HEAP_TIER_1

#ifndef D3D12MA_DEFAULT_BLOCK_SIZE
   /// Default size of a block allocated as single ID3D12Heap.
   #define D3D12MA_DEFAULT_BLOCK_SIZE (64ull * 1024 * 1024)
#endif

#endif // _D3D12MA_CONFIGURATION
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
// Configuration End
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

#define D3D12MA_IID_PPV_ARGS(ppType)   __uuidof(**(ppType)), reinterpret_cast<void**>(ppType)

namespace D3D12MA
{
static constexpr UINT HEAP_TYPE_COUNT = 4;
static constexpr UINT STANDARD_HEAP_TYPE_COUNT = 3; // Only DEFAULT, UPLOAD, READBACK.
static constexpr UINT DEFAULT_POOL_MAX_COUNT = 9;
static const UINT NEW_BLOCK_SIZE_SHIFT_MAX = 3;
// Minimum size of a free suballocation to register it in the free suballocation collection.
static const UINT64 MIN_FREE_SUBALLOCATION_SIZE_TO_REGISTER = 16;

static const WCHAR* const HeapTypeNames[] =
{
    L"DEFAULT",
    L"UPLOAD",
    L"READBACK",
    L"CUSTOM",
};

static const D3D12_HEAP_FLAGS RESOURCE_CLASS_HEAP_FLAGS =
    D3D12_HEAP_FLAG_DENY_BUFFERS | D3D12_HEAP_FLAG_DENY_RT_DS_TEXTURES | D3D12_HEAP_FLAG_DENY_NON_RT_DS_TEXTURES;

#ifndef _D3D12MA_ENUM_DECLARATIONS

// Local copy of this enum, as it is provided only by <dxgi1_4.h>, so it may not be available.
enum DXGI_MEMORY_SEGMENT_GROUP_COPY
{
    DXGI_MEMORY_SEGMENT_GROUP_LOCAL_COPY = 0,
    DXGI_MEMORY_SEGMENT_GROUP_NON_LOCAL_COPY = 1,
    DXGI_MEMORY_SEGMENT_GROUP_COUNT
};

enum class ResourceClass
{
    Unknown, Buffer, Non_RT_DS_Texture, RT_DS_Texture
};

enum SuballocationType
{
    SUBALLOCATION_TYPE_FREE = 0,
    SUBALLOCATION_TYPE_ALLOCATION = 1,
};

#endif // _D3D12MA_ENUM_DECLARATIONS


#ifndef _D3D12MA_FUNCTIONS

static void* DefaultAllocate(size_t Size, size_t Alignment, void* /*pPrivateData*/)
{
#ifdef _WIN32
    return _aligned_malloc(Size, Alignment);
#else
    return aligned_alloc(Alignment, Size);
#endif
}
static void DefaultFree(void* pMemory, void* /*pPrivateData*/)
{
#ifdef _WIN32
    return _aligned_free(pMemory);
#else
    return free(pMemory);
#endif
}

static void* Malloc(const ALLOCATION_CALLBACKS& allocs, size_t size, size_t alignment)
{
    void* const result = (*allocs.pAllocate)(size, alignment, allocs.pPrivateData);
    D3D12MA_ASSERT(result);
    return result;
}
static void Free(const ALLOCATION_CALLBACKS& allocs, void* memory)
{
    (*allocs.pFree)(memory, allocs.pPrivateData);
}

template<typename T>
static T* Allocate(const ALLOCATION_CALLBACKS& allocs)
{
    return (T*)Malloc(allocs, sizeof(T), __alignof(T));
}
template<typename T>
static T* AllocateArray(const ALLOCATION_CALLBACKS& allocs, size_t count)
{
    return (T*)Malloc(allocs, sizeof(T) * count, __alignof(T));
}

#define D3D12MA_NEW(allocs, type) new(D3D12MA::Allocate<type>(allocs))(type)
#define D3D12MA_NEW_ARRAY(allocs, type, count) new(D3D12MA::AllocateArray<type>((allocs), (count)))(type)

template<typename T>
void D3D12MA_DELETE(const ALLOCATION_CALLBACKS& allocs, T* memory)
{
    if (memory)
    {
        memory->~T();
        Free(allocs, memory);
    }
}
template<typename T>
void D3D12MA_DELETE_ARRAY(const ALLOCATION_CALLBACKS& allocs, T* memory, size_t count)
{
    if (memory)
    {
        for (size_t i = count; i--; )
        {
            memory[i].~T();
        }
        Free(allocs, memory);
    }
}

static void SetupAllocationCallbacks(ALLOCATION_CALLBACKS& outAllocs, const ALLOCATION_CALLBACKS* allocationCallbacks)
{
    if (allocationCallbacks)
    {
        outAllocs = *allocationCallbacks;
        D3D12MA_ASSERT(outAllocs.pAllocate != NULL && outAllocs.pFree != NULL);
    }
    else
    {
        outAllocs.pAllocate = &DefaultAllocate;
        outAllocs.pFree = &DefaultFree;
        outAllocs.pPrivateData = NULL;
    }
}

#define SAFE_RELEASE(ptr)   do { if(ptr) { (ptr)->Release(); (ptr) = NULL; } } while(false)

#define D3D12MA_VALIDATE(cond) do { if(!(cond)) { \
    D3D12MA_ASSERT(0 && "Validation failed: " #cond); \
    return false; \
} } while(false)

template<typename T>
static T D3D12MA_MIN(const T& a, const T& b) { return a <= b ? a : b; }
template<typename T>
static T D3D12MA_MAX(const T& a, const T& b) { return a <= b ? b : a; }

template<typename T>
static void D3D12MA_SWAP(T& a, T& b) { T tmp = a; a = b; b = tmp; }

// Scans integer for index of first nonzero bit from the Least Significant Bit (LSB). If mask is 0 then returns UINT8_MAX
static UINT8 BitScanLSB(UINT64 mask)
{
#if defined(_MSC_VER) && defined(_WIN64)
    unsigned long pos;
    if (_BitScanForward64(&pos, mask))
        return static_cast<UINT8>(pos);
    return UINT8_MAX;
#elif defined __GNUC__ || defined __clang__
    return static_cast<UINT8>(__builtin_ffsll(mask)) - 1U;
#else
    UINT8 pos = 0;
    UINT64 bit = 1;
    do
    {
        if (mask & bit)
            return pos;
        bit <<= 1;
    } while (pos++ < 63);
    return UINT8_MAX;
#endif
}
// Scans integer for index of first nonzero bit from the Least Significant Bit (LSB). If mask is 0 then returns UINT8_MAX
static UINT8 BitScanLSB(UINT32 mask)
{
#ifdef _MSC_VER
    unsigned long pos;
    if (_BitScanForward(&pos, mask))
        return static_cast<UINT8>(pos);
    return UINT8_MAX;
#elif defined __GNUC__ || defined __clang__
    return static_cast<UINT8>(__builtin_ffs(mask)) - 1U;
#else
    UINT8 pos = 0;
    UINT32 bit = 1;
    do
    {
        if (mask & bit)
            return pos;
        bit <<= 1;
    } while (pos++ < 31);
    return UINT8_MAX;
#endif
}

// Scans integer for index of first nonzero bit from the Most Significant Bit (MSB). If mask is 0 then returns UINT8_MAX
static UINT8 BitScanMSB(UINT64 mask)
{
#if defined(_MSC_VER) && defined(_WIN64)
    unsigned long pos;
    if (_BitScanReverse64(&pos, mask))
        return static_cast<UINT8>(pos);
#elif defined __GNUC__ || defined __clang__
    if (mask)
        return 63 - static_cast<UINT8>(__builtin_clzll(mask));
#else
    UINT8 pos = 63;
    UINT64 bit = 1ULL << 63;
    do
    {
        if (mask & bit)
            return pos;
        bit >>= 1;
    } while (pos-- > 0);
#endif
    return UINT8_MAX;
}
// Scans integer for index of first nonzero bit from the Most Significant Bit (MSB). If mask is 0 then returns UINT8_MAX
static UINT8 BitScanMSB(UINT32 mask)
{
#ifdef _MSC_VER
    unsigned long pos;
    if (_BitScanReverse(&pos, mask))
        return static_cast<UINT8>(pos);
#elif defined __GNUC__ || defined __clang__
    if (mask)
        return 31 - static_cast<UINT8>(__builtin_clz(mask));
#else
    UINT8 pos = 31;
    UINT32 bit = 1UL << 31;
    do
    {
        if (mask & bit)
            return pos;
        bit >>= 1;
    } while (pos-- > 0);
#endif
    return UINT8_MAX;
}

/*
Returns true if given number is a power of two.
T must be unsigned integer number or signed integer but always nonnegative.
For 0 returns true.
*/
template <typename T>
static bool IsPow2(T x) { return (x & (x - 1)) == 0; }

// Aligns given value up to nearest multiply of align value. For example: AlignUp(11, 8) = 16.
// Use types like UINT, uint64_t as T.
template <typename T>
static T AlignUp(T val, T alignment)
{
    D3D12MA_HEAVY_ASSERT(IsPow2(alignment));
    return (val + alignment - 1) & ~(alignment - 1);
}
// Aligns given value down to nearest multiply of align value. For example: AlignUp(11, 8) = 8.
// Use types like UINT, uint64_t as T.
template <typename T>
static T AlignDown(T val, T alignment)
{
    D3D12MA_HEAVY_ASSERT(IsPow2(alignment));
    return val & ~(alignment - 1);
}

// Division with mathematical rounding to nearest number.
template <typename T>
static T RoundDiv(T x, T y) { return (x + (y / (T)2)) / y; }
template <typename T>
static T DivideRoundingUp(T x, T y) { return (x + y - 1) / y; }

static WCHAR HexDigitToChar(UINT8 digit)
{
    if(digit < 10)
        return L'0' + digit;
    else
        return L'A' + (digit - 10);
}

/*
Performs binary search and returns iterator to first element that is greater or
equal to `key`, according to comparison `cmp`.

Cmp should return true if first argument is less than second argument.

Returned value is the found element, if present in the collection or place where
new element with value (key) should be inserted.
*/
template <typename CmpLess, typename IterT, typename KeyT>
static IterT BinaryFindFirstNotLess(IterT beg, IterT end, const KeyT& key, const CmpLess& cmp)
{
    size_t down = 0, up = (end - beg);
    while (down < up)
    {
        const size_t mid = (down + up) / 2;
        if (cmp(*(beg + mid), key))
        {
            down = mid + 1;
        }
        else
        {
            up = mid;
        }
    }
    return beg + down;
}

/*
Performs binary search and returns iterator to an element that is equal to `key`,
according to comparison `cmp`.

Cmp should return true if first argument is less than second argument.

Returned value is the found element, if present in the collection or end if not
found.
*/
template<typename CmpLess, typename IterT, typename KeyT>
static IterT BinaryFindSorted(const IterT& beg, const IterT& end, const KeyT& value, const CmpLess& cmp)
{
    IterT it = BinaryFindFirstNotLess<CmpLess, IterT, KeyT>(beg, end, value, cmp);
    if (it == end ||
        (!cmp(*it, value) && !cmp(value, *it)))
    {
        return it;
    }
    return end;
}

static UINT HeapTypeToIndex(D3D12_HEAP_TYPE type)
{
    switch (type)
    {
    case D3D12_HEAP_TYPE_DEFAULT:  return 0;
    case D3D12_HEAP_TYPE_UPLOAD:   return 1;
    case D3D12_HEAP_TYPE_READBACK: return 2;
    case D3D12_HEAP_TYPE_CUSTOM:   return 3;
    default: D3D12MA_ASSERT(0); return UINT_MAX;
    }
}

static D3D12_HEAP_TYPE IndexToHeapType(UINT heapTypeIndex)
{
    D3D12MA_ASSERT(heapTypeIndex < 4);
    // D3D12_HEAP_TYPE_DEFAULT starts at 1.
    return (D3D12_HEAP_TYPE)(heapTypeIndex + 1);
}

static UINT64 HeapFlagsToAlignment(D3D12_HEAP_FLAGS flags, bool denyMsaaTextures)
{
    /*
    Documentation of D3D12_HEAP_DESC structure says:

    - D3D12_DEFAULT_RESOURCE_PLACEMENT_ALIGNMENT   defined as 64KB.
    - D3D12_DEFAULT_MSAA_RESOURCE_PLACEMENT_ALIGNMENT   defined as 4MB. An
    application must decide whether the heap will contain multi-sample
    anti-aliasing (MSAA), in which case, the application must choose [this flag].

    https://docs.microsoft.com/en-us/windows/desktop/api/d3d12/ns-d3d12-d3d12_heap_desc
    */

    if (denyMsaaTextures)
        return D3D12_DEFAULT_RESOURCE_PLACEMENT_ALIGNMENT;

    const D3D12_HEAP_FLAGS denyAllTexturesFlags =
        D3D12_HEAP_FLAG_DENY_NON_RT_DS_TEXTURES | D3D12_HEAP_FLAG_DENY_RT_DS_TEXTURES;
    const bool canContainAnyTextures =
        (flags & denyAllTexturesFlags) != denyAllTexturesFlags;
    return canContainAnyTextures ?
        D3D12_DEFAULT_MSAA_RESOURCE_PLACEMENT_ALIGNMENT : D3D12_DEFAULT_RESOURCE_PLACEMENT_ALIGNMENT;
}

static ResourceClass HeapFlagsToResourceClass(D3D12_HEAP_FLAGS heapFlags)
{
    const bool allowBuffers = (heapFlags & D3D12_HEAP_FLAG_DENY_BUFFERS) == 0;
    const bool allowRtDsTextures = (heapFlags & D3D12_HEAP_FLAG_DENY_RT_DS_TEXTURES) == 0;
    const bool allowNonRtDsTextures = (heapFlags & D3D12_HEAP_FLAG_DENY_NON_RT_DS_TEXTURES) == 0;

    const uint8_t allowedGroupCount = (allowBuffers ? 1 : 0) + (allowRtDsTextures ? 1 : 0) + (allowNonRtDsTextures ? 1 : 0);
    if (allowedGroupCount != 1)
        return ResourceClass::Unknown;

    if (allowRtDsTextures)
        return ResourceClass::RT_DS_Texture;
    if (allowNonRtDsTextures)
        return ResourceClass::Non_RT_DS_Texture;
    return ResourceClass::Buffer;
}

static bool IsHeapTypeStandard(D3D12_HEAP_TYPE type)
{
    return type == D3D12_HEAP_TYPE_DEFAULT ||
        type == D3D12_HEAP_TYPE_UPLOAD ||
        type == D3D12_HEAP_TYPE_READBACK;
}

static D3D12_HEAP_PROPERTIES StandardHeapTypeToHeapProperties(D3D12_HEAP_TYPE type)
{
    D3D12MA_ASSERT(IsHeapTypeStandard(type));
    D3D12_HEAP_PROPERTIES result = {};
    result.Type = type;
    return result;
}

static bool IsFormatCompressed(DXGI_FORMAT format)
{
    switch (format)
    {
    case DXGI_FORMAT_BC1_TYPELESS:
    case DXGI_FORMAT_BC1_UNORM:
    case DXGI_FORMAT_BC1_UNORM_SRGB:
    case DXGI_FORMAT_BC2_TYPELESS:
    case DXGI_FORMAT_BC2_UNORM:
    case DXGI_FORMAT_BC2_UNORM_SRGB:
    case DXGI_FORMAT_BC3_TYPELESS:
    case DXGI_FORMAT_BC3_UNORM:
    case DXGI_FORMAT_BC3_UNORM_SRGB:
    case DXGI_FORMAT_BC4_TYPELESS:
    case DXGI_FORMAT_BC4_UNORM:
    case DXGI_FORMAT_BC4_SNORM:
    case DXGI_FORMAT_BC5_TYPELESS:
    case DXGI_FORMAT_BC5_UNORM:
    case DXGI_FORMAT_BC5_SNORM:
    case DXGI_FORMAT_BC6H_TYPELESS:
    case DXGI_FORMAT_BC6H_UF16:
    case DXGI_FORMAT_BC6H_SF16:
    case DXGI_FORMAT_BC7_TYPELESS:
    case DXGI_FORMAT_BC7_UNORM:
    case DXGI_FORMAT_BC7_UNORM_SRGB:
        return true;
    default:
        return false;
    }
}

// Only some formats are supported. For others it returns 0.
static UINT GetBitsPerPixel(DXGI_FORMAT format)
{
    switch (format)
    {
    case DXGI_FORMAT_R32G32B32A32_TYPELESS:
    case DXGI_FORMAT_R32G32B32A32_FLOAT:
    case DXGI_FORMAT_R32G32B32A32_UINT:
    case DXGI_FORMAT_R32G32B32A32_SINT:
        return 128;
    case DXGI_FORMAT_R32G32B32_TYPELESS:
    case DXGI_FORMAT_R32G32B32_FLOAT:
    case DXGI_FORMAT_R32G32B32_UINT:
    case DXGI_FORMAT_R32G32B32_SINT:
        return 96;
    case DXGI_FORMAT_R16G16B16A16_TYPELESS:
    case DXGI_FORMAT_R16G16B16A16_FLOAT:
    case DXGI_FORMAT_R16G16B16A16_UNORM:
    case DXGI_FORMAT_R16G16B16A16_UINT:
    case DXGI_FORMAT_R16G16B16A16_SNORM:
    case DXGI_FORMAT_R16G16B16A16_SINT:
        return 64;
    case DXGI_FORMAT_R32G32_TYPELESS:
    case DXGI_FORMAT_R32G32_FLOAT:
    case DXGI_FORMAT_R32G32_UINT:
    case DXGI_FORMAT_R32G32_SINT:
        return 64;
    case DXGI_FORMAT_R32G8X24_TYPELESS:
    case DXGI_FORMAT_D32_FLOAT_S8X24_UINT:
    case DXGI_FORMAT_R32_FLOAT_X8X24_TYPELESS:
    case DXGI_FORMAT_X32_TYPELESS_G8X24_UINT:
        return 64;
    case DXGI_FORMAT_R10G10B10A2_TYPELESS:
    case DXGI_FORMAT_R10G10B10A2_UNORM:
    case DXGI_FORMAT_R10G10B10A2_UINT:
    case DXGI_FORMAT_R11G11B10_FLOAT:
        return 32;
    case DXGI_FORMAT_R8G8B8A8_TYPELESS:
    case DXGI_FORMAT_R8G8B8A8_UNORM:
    case DXGI_FORMAT_R8G8B8A8_UNORM_SRGB:
    case DXGI_FORMAT_R8G8B8A8_UINT:
    case DXGI_FORMAT_R8G8B8A8_SNORM:
    case DXGI_FORMAT_R8G8B8A8_SINT:
        return 32;
    case DXGI_FORMAT_R16G16_TYPELESS:
    case DXGI_FORMAT_R16G16_FLOAT:
    case DXGI_FORMAT_R16G16_UNORM:
    case DXGI_FORMAT_R16G16_UINT:
    case DXGI_FORMAT_R16G16_SNORM:
    case DXGI_FORMAT_R16G16_SINT:
        return 32;
    case DXGI_FORMAT_R32_TYPELESS:
    case DXGI_FORMAT_D32_FLOAT:
    case DXGI_FORMAT_R32_FLOAT:
    case DXGI_FORMAT_R32_UINT:
    case DXGI_FORMAT_R32_SINT:
        return 32;
    case DXGI_FORMAT_R24G8_TYPELESS:
    case DXGI_FORMAT_D24_UNORM_S8_UINT:
    case DXGI_FORMAT_R24_UNORM_X8_TYPELESS:
    case DXGI_FORMAT_X24_TYPELESS_G8_UINT:
        return 32;
    case DXGI_FORMAT_R8G8_TYPELESS:
    case DXGI_FORMAT_R8G8_UNORM:
    case DXGI_FORMAT_R8G8_UINT:
    case DXGI_FORMAT_R8G8_SNORM:
    case DXGI_FORMAT_R8G8_SINT:
        return 16;
    case DXGI_FORMAT_R16_TYPELESS:
    case DXGI_FORMAT_R16_FLOAT:
    case DXGI_FORMAT_D16_UNORM:
    case DXGI_FORMAT_R16_UNORM:
    case DXGI_FORMAT_R16_UINT:
    case DXGI_FORMAT_R16_SNORM:
    case DXGI_FORMAT_R16_SINT:
        return 16;
    case DXGI_FORMAT_R8_TYPELESS:
    case DXGI_FORMAT_R8_UNORM:
    case DXGI_FORMAT_R8_UINT:
    case DXGI_FORMAT_R8_SNORM:
    case DXGI_FORMAT_R8_SINT:
    case DXGI_FORMAT_A8_UNORM:
        return 8;
    case DXGI_FORMAT_BC1_TYPELESS:
    case DXGI_FORMAT_BC1_UNORM:
    case DXGI_FORMAT_BC1_UNORM_SRGB:
        return 4;
    case DXGI_FORMAT_BC2_TYPELESS:
    case DXGI_FORMAT_BC2_UNORM:
    case DXGI_FORMAT_BC2_UNORM_SRGB:
        return 8;
    case DXGI_FORMAT_BC3_TYPELESS:
    case DXGI_FORMAT_BC3_UNORM:
    case DXGI_FORMAT_BC3_UNORM_SRGB:
        return 8;
    case DXGI_FORMAT_BC4_TYPELESS:
    case DXGI_FORMAT_BC4_UNORM:
    case DXGI_FORMAT_BC4_SNORM:
        return 4;
    case DXGI_FORMAT_BC5_TYPELESS:
    case DXGI_FORMAT_BC5_UNORM:
    case DXGI_FORMAT_BC5_SNORM:
        return 8;
    case DXGI_FORMAT_BC6H_TYPELESS:
    case DXGI_FORMAT_BC6H_UF16:
    case DXGI_FORMAT_BC6H_SF16:
        return 8;
    case DXGI_FORMAT_BC7_TYPELESS:
    case DXGI_FORMAT_BC7_UNORM:
    case DXGI_FORMAT_BC7_UNORM_SRGB:
        return 8;
    default:
        return 0;
    }
}
    
template<typename D3D12_RESOURCE_DESC_T>
static ResourceClass ResourceDescToResourceClass(const D3D12_RESOURCE_DESC_T& resDesc)
{
    if (resDesc.Dimension == D3D12_RESOURCE_DIMENSION_BUFFER)
        return ResourceClass::Buffer;
    // Else: it's surely a texture.
    const bool isRenderTargetOrDepthStencil =
        (resDesc.Flags & (D3D12_RESOURCE_FLAG_ALLOW_RENDER_TARGET | D3D12_RESOURCE_FLAG_ALLOW_DEPTH_STENCIL)) != 0;
    return isRenderTargetOrDepthStencil ? ResourceClass::RT_DS_Texture : ResourceClass::Non_RT_DS_Texture;
}
    
// This algorithm is overly conservative.
template<typename D3D12_RESOURCE_DESC_T>
static bool CanUseSmallAlignment(const D3D12_RESOURCE_DESC_T& resourceDesc)
{
    if (resourceDesc.Dimension != D3D12_RESOURCE_DIMENSION_TEXTURE2D)
        return false;
    if ((resourceDesc.Flags & (D3D12_RESOURCE_FLAG_ALLOW_RENDER_TARGET | D3D12_RESOURCE_FLAG_ALLOW_DEPTH_STENCIL)) != 0)
        return false;
    if (resourceDesc.SampleDesc.Count > 1)
        return false;
    if (resourceDesc.DepthOrArraySize != 1)
        return false;

    UINT sizeX = (UINT)resourceDesc.Width;
    UINT sizeY = resourceDesc.Height;
    UINT bitsPerPixel = GetBitsPerPixel(resourceDesc.Format);
    if (bitsPerPixel == 0)
        return false;

    if (IsFormatCompressed(resourceDesc.Format))
    {
        sizeX = DivideRoundingUp(sizeX, 4u);
        sizeY = DivideRoundingUp(sizeY, 4u);
        bitsPerPixel *= 16;
    }

    UINT tileSizeX = 0, tileSizeY = 0;
    switch (bitsPerPixel)
    {
    case   8: tileSizeX = 64; tileSizeY = 64; break;
    case  16: tileSizeX = 64; tileSizeY = 32; break;
    case  32: tileSizeX = 32; tileSizeY = 32; break;
    case  64: tileSizeX = 32; tileSizeY = 16; break;
    case 128: tileSizeX = 16; tileSizeY = 16; break;
    default: return false;
    }

    const UINT tileCount = DivideRoundingUp(sizeX, tileSizeX) * DivideRoundingUp(sizeY, tileSizeY);
    return tileCount <= 16;
}
    
static bool ValidateAllocateMemoryParameters(
    const ALLOCATION_DESC* pAllocDesc,
    const D3D12_RESOURCE_ALLOCATION_INFO* pAllocInfo,
    Allocation** ppAllocation)
{
    return pAllocDesc &&
        pAllocInfo &&
        ppAllocation &&
        (pAllocInfo->Alignment == 0 ||
            pAllocInfo->Alignment == D3D12_DEFAULT_RESOURCE_PLACEMENT_ALIGNMENT ||
            pAllocInfo->Alignment == D3D12_DEFAULT_MSAA_RESOURCE_PLACEMENT_ALIGNMENT) &&
        pAllocInfo->SizeInBytes != 0 &&
        pAllocInfo->SizeInBytes % (64ull * 1024) == 0;
}

#endif // _D3D12MA_FUNCTIONS
    
#ifndef _D3D12MA_STATISTICS_FUNCTIONS

static void ClearStatistics(Statistics& outStats)
{
    outStats.BlockCount = 0;
    outStats.AllocationCount = 0;
    outStats.BlockBytes = 0;
    outStats.AllocationBytes = 0;
}

static void ClearDetailedStatistics(DetailedStatistics& outStats)
{
    ClearStatistics(outStats.Stats);
    outStats.UnusedRangeCount = 0;
    outStats.AllocationSizeMin = UINT64_MAX;
    outStats.AllocationSizeMax = 0;
    outStats.UnusedRangeSizeMin = UINT64_MAX;
    outStats.UnusedRangeSizeMax = 0;
}

static void AddStatistics(Statistics& inoutStats, const Statistics& src)
{
    inoutStats.BlockCount += src.BlockCount;
    inoutStats.AllocationCount += src.AllocationCount;
    inoutStats.BlockBytes += src.BlockBytes;
    inoutStats.AllocationBytes += src.AllocationBytes;
}

static void AddDetailedStatistics(DetailedStatistics& inoutStats, const DetailedStatistics& src)
{
    AddStatistics(inoutStats.Stats, src.Stats);
    inoutStats.UnusedRangeCount += src.UnusedRangeCount;
    inoutStats.AllocationSizeMin = D3D12MA_MIN(inoutStats.AllocationSizeMin, src.AllocationSizeMin);
    inoutStats.AllocationSizeMax = D3D12MA_MAX(inoutStats.AllocationSizeMax, src.AllocationSizeMax);
    inoutStats.UnusedRangeSizeMin = D3D12MA_MIN(inoutStats.UnusedRangeSizeMin, src.UnusedRangeSizeMin);
    inoutStats.UnusedRangeSizeMax = D3D12MA_MAX(inoutStats.UnusedRangeSizeMax, src.UnusedRangeSizeMax);
}

static void AddDetailedStatisticsAllocation(DetailedStatistics& inoutStats, UINT64 size)
{
    inoutStats.Stats.AllocationCount++;
    inoutStats.Stats.AllocationBytes += size;
    inoutStats.AllocationSizeMin = D3D12MA_MIN(inoutStats.AllocationSizeMin, size);
    inoutStats.AllocationSizeMax = D3D12MA_MAX(inoutStats.AllocationSizeMax, size);
}

static void AddDetailedStatisticsUnusedRange(DetailedStatistics& inoutStats, UINT64 size)
{
    inoutStats.UnusedRangeCount++;
    inoutStats.UnusedRangeSizeMin = D3D12MA_MIN(inoutStats.UnusedRangeSizeMin, size);
    inoutStats.UnusedRangeSizeMax = D3D12MA_MAX(inoutStats.UnusedRangeSizeMax, size);
}
    
#endif // _D3D12MA_STATISTICS_FUNCTIONS


#ifndef _D3D12MA_MUTEX

#ifndef D3D12MA_MUTEX
    class Mutex
    {
    public:
        void Lock() { m_Mutex.lock(); }
        void Unlock() { m_Mutex.unlock(); }
    
    private:
        std::mutex m_Mutex;
    };
    #define D3D12MA_MUTEX Mutex
#endif

#ifndef D3D12MA_RW_MUTEX
#ifdef _WIN32
    class RWMutex
    {
    public:
        RWMutex() { InitializeSRWLock(&m_Lock); }
        void LockRead() { AcquireSRWLockShared(&m_Lock); }
        void UnlockRead() { ReleaseSRWLockShared(&m_Lock); }
        void LockWrite() { AcquireSRWLockExclusive(&m_Lock); }
        void UnlockWrite() { ReleaseSRWLockExclusive(&m_Lock); }
    
    private:
        SRWLOCK m_Lock;
    };
#else // #ifdef _WIN32
    class RWMutex
    {
    public:
        RWMutex() {}
        void LockRead() { m_Mutex.lock_shared(); }
        void UnlockRead() { m_Mutex.unlock_shared(); }
        void LockWrite() { m_Mutex.lock(); }
        void UnlockWrite() { m_Mutex.unlock(); }
    
    private:
        std::shared_timed_mutex m_Mutex;
    };
#endif // #ifdef _WIN32
    #define D3D12MA_RW_MUTEX RWMutex
#endif // #ifndef D3D12MA_RW_MUTEX

// Helper RAII class to lock a mutex in constructor and unlock it in destructor (at the end of scope).
struct MutexLock
{
    D3D12MA_CLASS_NO_COPY(MutexLock);
public:
    MutexLock(D3D12MA_MUTEX& mutex, bool useMutex = true) :
        m_pMutex(useMutex ? &mutex : NULL)
    {
        if (m_pMutex) m_pMutex->Lock(); 
    }
    ~MutexLock() { if (m_pMutex) m_pMutex->Unlock(); }

private:
    D3D12MA_MUTEX* m_pMutex;
};

// Helper RAII class to lock a RW mutex in constructor and unlock it in destructor (at the end of scope), for reading.
struct MutexLockRead
{
    D3D12MA_CLASS_NO_COPY(MutexLockRead);
public:
    MutexLockRead(D3D12MA_RW_MUTEX& mutex, bool useMutex)
        :  m_pMutex(useMutex ? &mutex : NULL)
    {
        if(m_pMutex)
        {
            m_pMutex->LockRead();
        }
    }
    ~MutexLockRead() { if (m_pMutex) m_pMutex->UnlockRead(); }

private:
    D3D12MA_RW_MUTEX* m_pMutex;
};

// Helper RAII class to lock a RW mutex in constructor and unlock it in destructor (at the end of scope), for writing.
struct MutexLockWrite
{
    D3D12MA_CLASS_NO_COPY(MutexLockWrite);
public:
    MutexLockWrite(D3D12MA_RW_MUTEX& mutex, bool useMutex)
        : m_pMutex(useMutex ? &mutex : NULL)
    {
        if (m_pMutex) m_pMutex->LockWrite(); 
    }
    ~MutexLockWrite() { if (m_pMutex) m_pMutex->UnlockWrite(); }

private:
    D3D12MA_RW_MUTEX* m_pMutex;
};

#if D3D12MA_DEBUG_GLOBAL_MUTEX
    static D3D12MA_MUTEX g_DebugGlobalMutex;
    #define D3D12MA_DEBUG_GLOBAL_MUTEX_LOCK MutexLock debugGlobalMutexLock(g_DebugGlobalMutex, true);
#else
    #define D3D12MA_DEBUG_GLOBAL_MUTEX_LOCK
#endif
#endif // _D3D12MA_MUTEX

#ifndef _D3D12MA_VECTOR
/*
Dynamically resizing continuous array. Class with interface similar to std::vector.
T must be POD because constructors and destructors are not called and memcpy is
used for these objects.
*/
template<typename T>
class Vector
{
public:
    using value_type = T;
    using iterator = T*;

    // allocationCallbacks externally owned, must outlive this object.
    Vector(const ALLOCATION_CALLBACKS& allocationCallbacks);
    Vector(size_t count, const ALLOCATION_CALLBACKS& allocationCallbacks);
    Vector(const Vector<T>& src);
    ~Vector();

    const ALLOCATION_CALLBACKS& GetAllocs() const { return m_AllocationCallbacks; }
    bool empty() const { return m_Count == 0; }
    size_t size() const { return m_Count; }
    T* data() { return m_pArray; }
    const T* data() const { return m_pArray; }
    void clear(bool freeMemory = false) { resize(0, freeMemory); }

    iterator begin() { return m_pArray; }
    iterator end() { return m_pArray + m_Count; }
    iterator rend() { return begin() - 1; }
    iterator rbegin() { return end() - 1; }

    const iterator cbegin() const { return m_pArray; }
    const iterator cend() const { return m_pArray + m_Count; }
    const iterator crbegin() const { return cend() - 1; }
    const iterator crend() const { return cbegin() - 1; }

    void push_front(const T& src) { insert(0, src); }
    void push_back(const T& src);
    void pop_front();
    void pop_back();

    T& front();
    T& back();
    const T& front() const;
    const T& back() const;

    void reserve(size_t newCapacity, bool freeMemory = false);
    void resize(size_t newCount, bool freeMemory = false);
    void insert(size_t index, const T& src);
    void remove(size_t index);

    template<typename CmpLess>
    size_t InsertSorted(const T& value, const CmpLess& cmp);
    template<typename CmpLess>
    bool RemoveSorted(const T& value, const CmpLess& cmp);

    Vector& operator=(const Vector<T>& rhs);
    T& operator[](size_t index);
    const T& operator[](size_t index) const;

private:
    const ALLOCATION_CALLBACKS& m_AllocationCallbacks;
    T* m_pArray;
    size_t m_Count;
    size_t m_Capacity;
};

#ifndef _D3D12MA_VECTOR_FUNCTIONS
template<typename T>
Vector<T>::Vector(const ALLOCATION_CALLBACKS& allocationCallbacks)
    : m_AllocationCallbacks(allocationCallbacks),
    m_pArray(NULL),
    m_Count(0),
    m_Capacity(0) {}

template<typename T>
Vector<T>::Vector(size_t count, const ALLOCATION_CALLBACKS& allocationCallbacks)
    : m_AllocationCallbacks(allocationCallbacks),
    m_pArray(count ? AllocateArray<T>(allocationCallbacks, count) : NULL),
    m_Count(count),
    m_Capacity(count) {}

template<typename T>
Vector<T>::Vector(const Vector<T>& src)
    : m_AllocationCallbacks(src.m_AllocationCallbacks),
    m_pArray(src.m_Count ? AllocateArray<T>(src.m_AllocationCallbacks, src.m_Count) : NULL),
    m_Count(src.m_Count),
    m_Capacity(src.m_Count)
{
    if (m_Count > 0)
    {
        memcpy(m_pArray, src.m_pArray, m_Count * sizeof(T));
    }
}

template<typename T>
Vector<T>::~Vector()
{
    Free(m_AllocationCallbacks, m_pArray);
}

template<typename T>
void Vector<T>::push_back(const T& src)
{
    const size_t newIndex = size();
    resize(newIndex + 1);
    m_pArray[newIndex] = src;
}

template<typename T>
void Vector<T>::pop_front()
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    remove(0);
}

template<typename T>
void Vector<T>::pop_back()
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    resize(size() - 1);
}

template<typename T>
T& Vector<T>::front()
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    return m_pArray[0];
}

template<typename T>
T& Vector<T>::back()
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    return m_pArray[m_Count - 1];
}

template<typename T>
const T& Vector<T>::front() const
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    return m_pArray[0];
}

template<typename T>
const T& Vector<T>::back() const
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    return m_pArray[m_Count - 1];
}

template<typename T>
void Vector<T>::reserve(size_t newCapacity, bool freeMemory)
{
    newCapacity = D3D12MA_MAX(newCapacity, m_Count);

    if ((newCapacity < m_Capacity) && !freeMemory)
    {
        newCapacity = m_Capacity;
    }

    if (newCapacity != m_Capacity)
    {
        T* const newArray = newCapacity ? AllocateArray<T>(m_AllocationCallbacks, newCapacity) : NULL;
        if (m_Count != 0)
        {
            memcpy(newArray, m_pArray, m_Count * sizeof(T));
        }
        Free(m_AllocationCallbacks, m_pArray);
        m_Capacity = newCapacity;
        m_pArray = newArray;
    }
}

template<typename T>
void Vector<T>::resize(size_t newCount, bool freeMemory)
{
    size_t newCapacity = m_Capacity;
    if (newCount > m_Capacity)
    {
        newCapacity = D3D12MA_MAX(newCount, D3D12MA_MAX(m_Capacity * 3 / 2, (size_t)8));
    }
    else if (freeMemory)
    {
        newCapacity = newCount;
    }

    if (newCapacity != m_Capacity)
    {
        T* const newArray = newCapacity ? AllocateArray<T>(m_AllocationCallbacks, newCapacity) : NULL;
        const size_t elementsToCopy = D3D12MA_MIN(m_Count, newCount);
        if (elementsToCopy != 0)
        {
            memcpy(newArray, m_pArray, elementsToCopy * sizeof(T));
        }
        Free(m_AllocationCallbacks, m_pArray);
        m_Capacity = newCapacity;
        m_pArray = newArray;
    }

    m_Count = newCount;
}

template<typename T>
void Vector<T>::insert(size_t index, const T& src)
{
    D3D12MA_HEAVY_ASSERT(index <= m_Count);
    const size_t oldCount = size();
    resize(oldCount + 1);
    if (index < oldCount)
    {
        memmove(m_pArray + (index + 1), m_pArray + index, (oldCount - index) * sizeof(T));
    }
    m_pArray[index] = src;
}

template<typename T>
void Vector<T>::remove(size_t index)
{
    D3D12MA_HEAVY_ASSERT(index < m_Count);
    const size_t oldCount = size();
    if (index < oldCount - 1)
    {
        memmove(m_pArray + index, m_pArray + (index + 1), (oldCount - index - 1) * sizeof(T));
    }
    resize(oldCount - 1);
}

template<typename T> template<typename CmpLess>
size_t Vector<T>::InsertSorted(const T& value, const CmpLess& cmp)
{
    const size_t indexToInsert = BinaryFindFirstNotLess<CmpLess, iterator, T>(
        m_pArray,
        m_pArray + m_Count,
        value,
        cmp) - m_pArray;
    insert(indexToInsert, value);
    return indexToInsert;
}

template<typename T> template<typename CmpLess>
bool Vector<T>::RemoveSorted(const T& value, const CmpLess& cmp)
{
    const iterator it = BinaryFindFirstNotLess(
        m_pArray,
        m_pArray + m_Count,
        value,
        cmp);
    if ((it != end()) && !cmp(*it, value) && !cmp(value, *it))
    {
        size_t indexToRemove = it - begin();
        remove(indexToRemove);
        return true;
    }
    return false;
}

template<typename T>
Vector<T>& Vector<T>::operator=(const Vector<T>& rhs)
{
    if (&rhs != this)
    {
        resize(rhs.m_Count);
        if (m_Count != 0)
        {
            memcpy(m_pArray, rhs.m_pArray, m_Count * sizeof(T));
        }
    }
    return *this;
}

template<typename T>
T& Vector<T>::operator[](size_t index)
{
    D3D12MA_HEAVY_ASSERT(index < m_Count);
    return m_pArray[index];
}

template<typename T>
const T& Vector<T>::operator[](size_t index) const
{
    D3D12MA_HEAVY_ASSERT(index < m_Count);
    return m_pArray[index];
}
#endif // _D3D12MA_VECTOR_FUNCTIONS
#endif // _D3D12MA_VECTOR

#ifndef _D3D12MA_STRING_BUILDER
class StringBuilder
{
public:
    StringBuilder(const ALLOCATION_CALLBACKS& allocationCallbacks) : m_Data(allocationCallbacks) {}

    size_t GetLength() const { return m_Data.size(); }
    LPCWSTR GetData() const { return m_Data.data(); }

    void Add(WCHAR ch) { m_Data.push_back(ch); }
    void Add(LPCWSTR str);
    void AddNewLine() { Add(L'\n'); }
    void AddNumber(UINT num);
    void AddNumber(UINT64 num);
    void AddPointer(const void* ptr);

private:
    Vector<WCHAR> m_Data;
};

#ifndef _D3D12MA_STRING_BUILDER_FUNCTIONS
void StringBuilder::Add(LPCWSTR str)
{
    const size_t len = wcslen(str);
    if (len > 0)
    {
        const size_t oldCount = m_Data.size();
        m_Data.resize(oldCount + len);
        memcpy(m_Data.data() + oldCount, str, len * sizeof(WCHAR));
    }
}

void StringBuilder::AddNumber(UINT num)
{
    WCHAR buf[11];
    buf[10] = L'\0';
    WCHAR *p = &buf[10];
    do
    {
        *--p = L'0' + (num % 10);
        num /= 10;
    }
    while (num);
    Add(p);
}

void StringBuilder::AddNumber(UINT64 num)
{
    WCHAR buf[21];
    buf[20] = L'\0';
    WCHAR *p = &buf[20];
    do
    {
        *--p = L'0' + (num % 10);
        num /= 10;
    }
    while (num);
    Add(p);
}

void StringBuilder::AddPointer(const void* ptr)
{
    WCHAR buf[21];
    uintptr_t num = (uintptr_t)ptr;
    buf[20] = L'\0';
    WCHAR *p = &buf[20];
    do
    {
        *--p = HexDigitToChar((UINT8)(num & 0xF));
        num >>= 4;
    }
    while (num);
    Add(p);
}

#endif // _D3D12MA_STRING_BUILDER_FUNCTIONS
#endif // _D3D12MA_STRING_BUILDER

#ifndef _D3D12MA_JSON_WRITER
/*
Allows to conveniently build a correct JSON document to be written to the
StringBuilder passed to the constructor.
*/
class JsonWriter
{
public:
    // stringBuilder - string builder to write the document to. Must remain alive for the whole lifetime of this object.
    JsonWriter(const ALLOCATION_CALLBACKS& allocationCallbacks, StringBuilder& stringBuilder);
    ~JsonWriter();

    // Begins object by writing "{".
    // Inside an object, you must call pairs of WriteString and a value, e.g.:
    // j.BeginObject(true); j.WriteString("A"); j.WriteNumber(1); j.WriteString("B"); j.WriteNumber(2); j.EndObject();
    // Will write: { "A": 1, "B": 2 }
    void BeginObject(bool singleLine = false);
    // Ends object by writing "}".
    void EndObject();

    // Begins array by writing "[".
    // Inside an array, you can write a sequence of any values.
    void BeginArray(bool singleLine = false);
    // Ends array by writing "[".
    void EndArray();

    // Writes a string value inside "".
    // pStr can contain any UTF-16 characters, including '"', new line etc. - they will be properly escaped.
    void WriteString(LPCWSTR pStr);

    // Begins writing a string value.
    // Call BeginString, ContinueString, ContinueString, ..., EndString instead of
    // WriteString to conveniently build the string content incrementally, made of
    // parts including numbers.
    void BeginString(LPCWSTR pStr = NULL);
    // Posts next part of an open string.
    void ContinueString(LPCWSTR pStr);
    // Posts next part of an open string. The number is converted to decimal characters.
    void ContinueString(UINT num);
    void ContinueString(UINT64 num);
    void ContinueString_Pointer(const void* ptr);
    // Posts next part of an open string. Pointer value is converted to characters
    // using "%p" formatting - shown as hexadecimal number, e.g.: 000000081276Ad00
    // void ContinueString_Pointer(const void* ptr);
    // Ends writing a string value by writing '"'.
    void EndString(LPCWSTR pStr = NULL);

    // Writes a number value.
    void WriteNumber(UINT num);
    void WriteNumber(UINT64 num);
    // Writes a boolean value - false or true.
    void WriteBool(bool b);
    // Writes a null value.
    void WriteNull();

    void AddAllocationToObject(const Allocation& alloc);
    void AddDetailedStatisticsInfoObject(const DetailedStatistics& stats);

private:
    static const WCHAR* const INDENT;

    enum CollectionType
    {
        COLLECTION_TYPE_OBJECT,
        COLLECTION_TYPE_ARRAY,
    };
    struct StackItem
    {
        CollectionType type;
        UINT valueCount;
        bool singleLineMode;
    };

    StringBuilder& m_SB;
    Vector<StackItem> m_Stack;
    bool m_InsideString;

    void BeginValue(bool isString);
    void WriteIndent(bool oneLess = false);
};

#ifndef _D3D12MA_JSON_WRITER_FUNCTIONS
const WCHAR* const JsonWriter::INDENT = L"  ";

JsonWriter::JsonWriter(const ALLOCATION_CALLBACKS& allocationCallbacks, StringBuilder& stringBuilder)
    : m_SB(stringBuilder),
    m_Stack(allocationCallbacks),
    m_InsideString(false) {}

JsonWriter::~JsonWriter()
{
    D3D12MA_ASSERT(!m_InsideString);
    D3D12MA_ASSERT(m_Stack.empty());
}

void JsonWriter::BeginObject(bool singleLine)
{
    D3D12MA_ASSERT(!m_InsideString);

    BeginValue(false);
    m_SB.Add(L'{');

    StackItem stackItem;
    stackItem.type = COLLECTION_TYPE_OBJECT;
    stackItem.valueCount = 0;
    stackItem.singleLineMode = singleLine;
    m_Stack.push_back(stackItem);
}

void JsonWriter::EndObject()
{
    D3D12MA_ASSERT(!m_InsideString);
    D3D12MA_ASSERT(!m_Stack.empty() && m_Stack.back().type == COLLECTION_TYPE_OBJECT);
    D3D12MA_ASSERT(m_Stack.back().valueCount % 2 == 0);

    WriteIndent(true);
    m_SB.Add(L'}');

    m_Stack.pop_back();
}

void JsonWriter::BeginArray(bool singleLine)
{
    D3D12MA_ASSERT(!m_InsideString);

    BeginValue(false);
    m_SB.Add(L'[');

    StackItem stackItem;
    stackItem.type = COLLECTION_TYPE_ARRAY;
    stackItem.valueCount = 0;
    stackItem.singleLineMode = singleLine;
    m_Stack.push_back(stackItem);
}

void JsonWriter::EndArray()
{
    D3D12MA_ASSERT(!m_InsideString);
    D3D12MA_ASSERT(!m_Stack.empty() && m_Stack.back().type == COLLECTION_TYPE_ARRAY);

    WriteIndent(true);
    m_SB.Add(L']');

    m_Stack.pop_back();
}

void JsonWriter::WriteString(LPCWSTR pStr)
{
    BeginString(pStr);
    EndString();
}

void JsonWriter::BeginString(LPCWSTR pStr)
{
    D3D12MA_ASSERT(!m_InsideString);

    BeginValue(true);
    m_InsideString = true;
    m_SB.Add(L'"');
    if (pStr != NULL)
    {
        ContinueString(pStr);
    }
}

void JsonWriter::ContinueString(LPCWSTR pStr)
{
    D3D12MA_ASSERT(m_InsideString);
    D3D12MA_ASSERT(pStr);

    for (const WCHAR *p = pStr; *p; ++p)
    {
        // the strings we encode are assumed to be in UTF-16LE format, the native
        // windows wide character Unicode format. In this encoding Unicode code
        // points U+0000 to U+D7FF and U+E000 to U+FFFF are encoded in two bytes,
        // and everything else takes more than two bytes. We will reject any
        // multi wchar character encodings for simplicity.
        UINT val = (UINT)*p;
        D3D12MA_ASSERT(((val <= 0xD7FF) || (0xE000 <= val && val <= 0xFFFF)) &&
            "Character not currently supported.");
        switch (*p)
        {
        case L'"':  m_SB.Add(L'\\'); m_SB.Add(L'"');  break;
        case L'\\': m_SB.Add(L'\\'); m_SB.Add(L'\\'); break;
        case L'/':  m_SB.Add(L'\\'); m_SB.Add(L'/');  break;
        case L'\b': m_SB.Add(L'\\'); m_SB.Add(L'b');  break;
        case L'\f': m_SB.Add(L'\\'); m_SB.Add(L'f');  break;
        case L'\n': m_SB.Add(L'\\'); m_SB.Add(L'n');  break;
        case L'\r': m_SB.Add(L'\\'); m_SB.Add(L'r');  break;
        case L'\t': m_SB.Add(L'\\'); m_SB.Add(L't');  break;
        default:
            // conservatively use encoding \uXXXX for any Unicode character
            // requiring more than one byte.
            if (32 <= val && val < 256)
                m_SB.Add(*p);
            else
            {
                m_SB.Add(L'\\');
                m_SB.Add(L'u');
                for (UINT i = 0; i < 4; ++i)
                {
                    UINT hexDigit = (val & 0xF000) >> 12;
                    val <<= 4;
                    if (hexDigit < 10)
                        m_SB.Add(L'0' + (WCHAR)hexDigit);
                    else
                        m_SB.Add(L'A' + (WCHAR)hexDigit);
                }
            }
            break;
        }
    }
}

void JsonWriter::ContinueString(UINT num)
{
    D3D12MA_ASSERT(m_InsideString);
    m_SB.AddNumber(num);
}

void JsonWriter::ContinueString(UINT64 num)
{
    D3D12MA_ASSERT(m_InsideString);
    m_SB.AddNumber(num);
}

void JsonWriter::ContinueString_Pointer(const void* ptr)
{
    D3D12MA_ASSERT(m_InsideString);
    m_SB.AddPointer(ptr);
}

void JsonWriter::EndString(LPCWSTR pStr)
{
    D3D12MA_ASSERT(m_InsideString);

    if (pStr)
        ContinueString(pStr);
    m_SB.Add(L'"');
    m_InsideString = false;
}

void JsonWriter::WriteNumber(UINT num)
{
    D3D12MA_ASSERT(!m_InsideString);
    BeginValue(false);
    m_SB.AddNumber(num);
}

void JsonWriter::WriteNumber(UINT64 num)
{
    D3D12MA_ASSERT(!m_InsideString);
    BeginValue(false);
    m_SB.AddNumber(num);
}

void JsonWriter::WriteBool(bool b)
{
    D3D12MA_ASSERT(!m_InsideString);
    BeginValue(false);
    if (b)
        m_SB.Add(L"true");
    else
        m_SB.Add(L"false");
}

void JsonWriter::WriteNull()
{
    D3D12MA_ASSERT(!m_InsideString);
    BeginValue(false);
    m_SB.Add(L"null");
}

void JsonWriter::AddAllocationToObject(const Allocation& alloc)
{
    WriteString(L"Type");
    switch (alloc.m_PackedData.GetResourceDimension()) {
    case D3D12_RESOURCE_DIMENSION_UNKNOWN:
        WriteString(L"UNKNOWN");
        break;
    case D3D12_RESOURCE_DIMENSION_BUFFER:
        WriteString(L"BUFFER");
        break;
    case D3D12_RESOURCE_DIMENSION_TEXTURE1D:
        WriteString(L"TEXTURE1D");
        break;
    case D3D12_RESOURCE_DIMENSION_TEXTURE2D:
        WriteString(L"TEXTURE2D");
        break;
    case D3D12_RESOURCE_DIMENSION_TEXTURE3D:
        WriteString(L"TEXTURE3D");
        break;
    default: D3D12MA_ASSERT(0); break;
    }

    WriteString(L"Size");
    WriteNumber(alloc.GetSize());
    WriteString(L"Usage");
    WriteNumber((UINT)alloc.m_PackedData.GetResourceFlags());

    void* privateData = alloc.GetPrivateData();
    if (privateData)
    {
        WriteString(L"CustomData");
        BeginString();
        ContinueString_Pointer(privateData);
        EndString();
    }

    LPCWSTR name = alloc.GetName();
    if (name != NULL)
    {
        WriteString(L"Name");
        WriteString(name);
    }
    if (alloc.m_PackedData.GetTextureLayout())
    {
        WriteString(L"Layout");
        WriteNumber((UINT)alloc.m_PackedData.GetTextureLayout());
    }
}

void JsonWriter::AddDetailedStatisticsInfoObject(const DetailedStatistics& stats)
{
    BeginObject();

    WriteString(L"BlockCount");
    WriteNumber(stats.Stats.BlockCount);
    WriteString(L"BlockBytes");
    WriteNumber(stats.Stats.BlockBytes);
    WriteString(L"AllocationCount");
    WriteNumber(stats.Stats.AllocationCount);
    WriteString(L"AllocationBytes");
    WriteNumber(stats.Stats.AllocationBytes);
    WriteString(L"UnusedRangeCount");
    WriteNumber(stats.UnusedRangeCount);

    if (stats.Stats.AllocationCount > 1)
    {
        WriteString(L"AllocationSizeMin");
        WriteNumber(stats.AllocationSizeMin);
        WriteString(L"AllocationSizeMax");
        WriteNumber(stats.AllocationSizeMax);
    }
    if (stats.UnusedRangeCount > 1)
    {
        WriteString(L"UnusedRangeSizeMin");
        WriteNumber(stats.UnusedRangeSizeMin);
        WriteString(L"UnusedRangeSizeMax");
        WriteNumber(stats.UnusedRangeSizeMax);
    }
    EndObject();
}

void JsonWriter::BeginValue(bool isString)
{
    if (!m_Stack.empty())
    {
        StackItem& currItem = m_Stack.back();
        if (currItem.type == COLLECTION_TYPE_OBJECT && currItem.valueCount % 2 == 0)
        {
            D3D12MA_ASSERT(isString);
        }

        if (currItem.type == COLLECTION_TYPE_OBJECT && currItem.valueCount % 2 == 1)
        {
            m_SB.Add(L':'); m_SB.Add(L' ');
        }
        else if (currItem.valueCount > 0)
        {
            m_SB.Add(L','); m_SB.Add(L' ');
            WriteIndent();
        }
        else
        {
            WriteIndent();
        }
        ++currItem.valueCount;
    }
}

void JsonWriter::WriteIndent(bool oneLess)
{
    if (!m_Stack.empty() && !m_Stack.back().singleLineMode)
    {
        m_SB.AddNewLine();

        size_t count = m_Stack.size();
        if (count > 0 && oneLess)
        {
            --count;
        }
        for (size_t i = 0; i < count; ++i)
        {
            m_SB.Add(INDENT);
        }
    }
}
#endif // _D3D12MA_JSON_WRITER_FUNCTIONS
#endif // _D3D12MA_JSON_WRITER

#ifndef _D3D12MA_POOL_ALLOCATOR
/*
Allocator for objects of type T using a list of arrays (pools) to speed up
allocation. Number of elements that can be allocated is not bounded because
allocator can create multiple blocks.
T should be POD because constructor and destructor is not called in Alloc or
Free.
*/
template<typename T>
class PoolAllocator
{
    D3D12MA_CLASS_NO_COPY(PoolAllocator)
public:
    // allocationCallbacks externally owned, must outlive this object.
    PoolAllocator(const ALLOCATION_CALLBACKS& allocationCallbacks, UINT firstBlockCapacity);
    ~PoolAllocator() { Clear(); }

    void Clear();
    template<typename... Types>
    T* Alloc(Types... args);
    void Free(T* ptr);

private:
    union Item
    {
        UINT NextFreeIndex; // UINT32_MAX means end of list.
        alignas(T) char Value[sizeof(T)];
    };

    struct ItemBlock
    {
        Item* pItems;
        UINT Capacity;
        UINT FirstFreeIndex;
    };

    const ALLOCATION_CALLBACKS& m_AllocationCallbacks;
    const UINT m_FirstBlockCapacity;
    Vector<ItemBlock> m_ItemBlocks;

    ItemBlock& CreateNewBlock();
};

#ifndef _D3D12MA_POOL_ALLOCATOR_FUNCTIONS
template<typename T>
PoolAllocator<T>::PoolAllocator(const ALLOCATION_CALLBACKS& allocationCallbacks, UINT firstBlockCapacity)
    : m_AllocationCallbacks(allocationCallbacks),
    m_FirstBlockCapacity(firstBlockCapacity),
    m_ItemBlocks(allocationCallbacks)
{
    D3D12MA_ASSERT(m_FirstBlockCapacity > 1);
}

template<typename T>
void PoolAllocator<T>::Clear()
{
    for(size_t i = m_ItemBlocks.size(); i--; )
    {
        D3D12MA_DELETE_ARRAY(m_AllocationCallbacks, m_ItemBlocks[i].pItems, m_ItemBlocks[i].Capacity);
    }
    m_ItemBlocks.clear(true);
}

template<typename T> template<typename... Types>
T* PoolAllocator<T>::Alloc(Types... args)
{
    for(size_t i = m_ItemBlocks.size(); i--; )
    {
        ItemBlock& block = m_ItemBlocks[i];
        // This block has some free items: Use first one.
        if(block.FirstFreeIndex != UINT32_MAX)
        {
            Item* const pItem = &block.pItems[block.FirstFreeIndex];
            block.FirstFreeIndex = pItem->NextFreeIndex;
            T* result = (T*)&pItem->Value;
            new(result)T(std::forward<Types>(args)...); // Explicit constructor call.
            return result;
        }
    }

    // No block has free item: Create new one and use it.
    ItemBlock& newBlock = CreateNewBlock();
    Item* const pItem = &newBlock.pItems[0];
    newBlock.FirstFreeIndex = pItem->NextFreeIndex;
    T* result = (T*)pItem->Value;
    new(result)T(std::forward<Types>(args)...); // Explicit constructor call.
    return result;
}

template<typename T>
void PoolAllocator<T>::Free(T* ptr)
{
    // Search all memory blocks to find ptr.
    for(size_t i = m_ItemBlocks.size(); i--; )
    {
        ItemBlock& block = m_ItemBlocks[i];

        Item* pItemPtr;
        memcpy(&pItemPtr, &ptr, sizeof(pItemPtr));

        // Check if pItemPtr is in address range of this block.
        if((pItemPtr >= block.pItems) && (pItemPtr < block.pItems + block.Capacity))
        {
            ptr->~T(); // Explicit destructor call.
            const UINT index = static_cast<UINT>(pItemPtr - block.pItems);
            pItemPtr->NextFreeIndex = block.FirstFreeIndex;
            block.FirstFreeIndex = index;
            return;
        }
    }
    D3D12MA_ASSERT(0 && "Pointer doesn't belong to this memory pool.");
}

template<typename T>
typename PoolAllocator<T>::ItemBlock& PoolAllocator<T>::CreateNewBlock()
{
    const UINT newBlockCapacity = m_ItemBlocks.empty() ?
        m_FirstBlockCapacity : m_ItemBlocks.back().Capacity * 3 / 2;

    const ItemBlock newBlock = {
        D3D12MA_NEW_ARRAY(m_AllocationCallbacks, Item, newBlockCapacity),
        newBlockCapacity,
        0 };

    m_ItemBlocks.push_back(newBlock);

    // Setup singly-linked list of all free items in this block.
    for(UINT i = 0; i < newBlockCapacity - 1; ++i)
    {
        newBlock.pItems[i].NextFreeIndex = i + 1;
    }
    newBlock.pItems[newBlockCapacity - 1].NextFreeIndex = UINT32_MAX;
    return m_ItemBlocks.back();
}
#endif // _D3D12MA_POOL_ALLOCATOR_FUNCTIONS
#endif // _D3D12MA_POOL_ALLOCATOR

#ifndef _D3D12MA_LIST
/*
Doubly linked list, with elements allocated out of PoolAllocator.
Has custom interface, as well as STL-style interface, including iterator and
const_iterator.
*/
template<typename T>
class List
{
    D3D12MA_CLASS_NO_COPY(List)
public:
    struct Item
    {
        Item* pPrev;
        Item* pNext;
        T Value;
    };

    class reverse_iterator;
    class const_reverse_iterator;
    class iterator
    {
        friend class List<T>;
        friend class const_iterator;

    public:
        iterator() = default;
        iterator(const reverse_iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}

        T& operator*() const;
        T* operator->() const;

        iterator& operator++();
        iterator& operator--();
        iterator operator++(int);
        iterator operator--(int);

        bool operator==(const iterator& rhs) const;
        bool operator!=(const iterator& rhs) const;

    private:
        List<T>* m_pList = NULL;
        Item* m_pItem = NULL;

        iterator(List<T>* pList, Item* pItem) : m_pList(pList), m_pItem(pItem) {}
    };

    class reverse_iterator
    {
        friend class List<T>;
        friend class const_reverse_iterator;

    public:
        reverse_iterator() = default;
        reverse_iterator(const iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}

        T& operator*() const;
        T* operator->() const;

        reverse_iterator& operator++();
        reverse_iterator& operator--();
        reverse_iterator operator++(int);
        reverse_iterator operator--(int);

        bool operator==(const reverse_iterator& rhs) const;
        bool operator!=(const reverse_iterator& rhs) const;

    private:
        List<T>* m_pList = NULL;
        Item* m_pItem = NULL;

        reverse_iterator(List<T>* pList, Item* pItem)
            : m_pList(pList), m_pItem(pItem) {}
    };

    class const_iterator
    {
        friend class List<T>;

    public:
        const_iterator() = default;
        const_iterator(const iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}
        const_iterator(const reverse_iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}
        const_iterator(const const_reverse_iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}

        iterator dropConst() const;
        const T& operator*() const;
        const T* operator->() const;

        const_iterator& operator++();
        const_iterator& operator--();
        const_iterator operator++(int);
        const_iterator operator--(int);

        bool operator==(const const_iterator& rhs) const;
        bool operator!=(const const_iterator& rhs) const;

    private:
        const List<T>* m_pList = NULL;
        const Item* m_pItem = NULL;

        const_iterator(const List<T>* pList, const Item* pItem)
            : m_pList(pList), m_pItem(pItem) {}
    };

    class const_reverse_iterator
    {
        friend class List<T>;

    public:
        const_reverse_iterator() = default;
        const_reverse_iterator(const iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}
        const_reverse_iterator(const reverse_iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}
        const_reverse_iterator(const const_iterator& src)
            : m_pList(src.m_pList), m_pItem(src.m_pItem) {}

        reverse_iterator dropConst() const;
        const T& operator*() const;
        const T* operator->() const;

        const_reverse_iterator& operator++();
        const_reverse_iterator& operator--();
        const_reverse_iterator operator++(int);
        const_reverse_iterator operator--(int);

        bool operator==(const const_reverse_iterator& rhs) const;
        bool operator!=(const const_reverse_iterator& rhs) const;

    private:
        const List<T>* m_pList = NULL;
        const Item* m_pItem = NULL;

        const_reverse_iterator(const List<T>* pList, const Item* pItem)
            : m_pList(pList), m_pItem(pItem) {}
    };

    // allocationCallbacks externally owned, must outlive this object.
    List(const ALLOCATION_CALLBACKS& allocationCallbacks);
    // Intentionally not calling Clear, because that would be unnecessary
    // computations to return all items to m_ItemAllocator as free.
    ~List() = default;
    
    size_t GetCount() const { return m_Count; }
    bool IsEmpty() const { return m_Count == 0; }

    Item* Front() { return m_pFront; }
    const Item* Front() const { return m_pFront; }
    Item* Back() { return m_pBack; }
    const Item* Back() const { return m_pBack; }

    bool empty() const { return IsEmpty(); }
    size_t size() const { return GetCount(); }
    void push_back(const T& value) { PushBack(value); }
    iterator insert(iterator it, const T& value) { return iterator(this, InsertBefore(it.m_pItem, value)); }
    void clear() { Clear(); }
    void erase(iterator it) { Remove(it.m_pItem); }

    iterator begin() { return iterator(this, Front()); }
    iterator end() { return iterator(this, NULL); }
    reverse_iterator rbegin() { return reverse_iterator(this, Back()); }
    reverse_iterator rend() { return reverse_iterator(this, NULL); }

    const_iterator cbegin() const { return const_iterator(this, Front()); }
    const_iterator cend() const { return const_iterator(this, NULL); }
    const_iterator begin() const { return cbegin(); }
    const_iterator end() const { return cend(); }

    const_reverse_iterator crbegin() const { return const_reverse_iterator(this, Back()); }
    const_reverse_iterator crend() const { return const_reverse_iterator(this, NULL); }
    const_reverse_iterator rbegin() const { return crbegin(); }
    const_reverse_iterator rend() const { return crend(); }

    Item* PushBack();
    Item* PushFront();
    Item* PushBack(const T& value);
    Item* PushFront(const T& value);
    void PopBack();
    void PopFront();

    // Item can be null - it means PushBack.
    Item* InsertBefore(Item* pItem);
    // Item can be null - it means PushFront.
    Item* InsertAfter(Item* pItem);
    Item* InsertBefore(Item* pItem, const T& value);
    Item* InsertAfter(Item* pItem, const T& value);

    void Clear();
    void Remove(Item* pItem);

private:
    const ALLOCATION_CALLBACKS& m_AllocationCallbacks;
    PoolAllocator<Item> m_ItemAllocator;
    Item* m_pFront;
    Item* m_pBack;
    size_t m_Count;
};

#ifndef _D3D12MA_LIST_ITERATOR_FUNCTIONS
template<typename T>
T& List<T>::iterator::operator*() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return m_pItem->Value;
}

template<typename T>
T* List<T>::iterator::operator->() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return &m_pItem->Value;
}

template<typename T>
typename List<T>::iterator& List<T>::iterator::operator++()
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    m_pItem = m_pItem->pNext;
    return *this;
}

template<typename T>
typename List<T>::iterator& List<T>::iterator::operator--()
{
    if (m_pItem != NULL)
    {
        m_pItem = m_pItem->pPrev;
    }
    else
    {
        D3D12MA_HEAVY_ASSERT(!m_pList->IsEmpty());
        m_pItem = m_pList->Back();
    }
    return *this;
}

template<typename T>
typename List<T>::iterator List<T>::iterator::operator++(int)
{
    iterator result = *this;
    ++* this;
    return result;
}

template<typename T>
typename List<T>::iterator List<T>::iterator::operator--(int)
{
    iterator result = *this;
    --* this;
    return result;
}

template<typename T>
bool List<T>::iterator::operator==(const iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem == rhs.m_pItem;
}

template<typename T>
bool List<T>::iterator::operator!=(const iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem != rhs.m_pItem;
}
#endif // _D3D12MA_LIST_ITERATOR_FUNCTIONS

#ifndef _D3D12MA_LIST_REVERSE_ITERATOR_FUNCTIONS
template<typename T>
T& List<T>::reverse_iterator::operator*() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return m_pItem->Value;
}

template<typename T>
T* List<T>::reverse_iterator::operator->() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return &m_pItem->Value;
}

template<typename T>
typename List<T>::reverse_iterator& List<T>::reverse_iterator::operator++()
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    m_pItem = m_pItem->pPrev;
    return *this;
}

template<typename T>
typename List<T>::reverse_iterator& List<T>::reverse_iterator::operator--()
{
    if (m_pItem != NULL)
    {
        m_pItem = m_pItem->pNext;
    }
    else
    {
        D3D12MA_HEAVY_ASSERT(!m_pList->IsEmpty());
        m_pItem = m_pList->Front();
    }
    return *this;
}

template<typename T>
typename List<T>::reverse_iterator List<T>::reverse_iterator::operator++(int)
{
    reverse_iterator result = *this;
    ++* this;
    return result;
}

template<typename T>
typename List<T>::reverse_iterator List<T>::reverse_iterator::operator--(int)
{
    reverse_iterator result = *this;
    --* this;
    return result;
}

template<typename T>
bool List<T>::reverse_iterator::operator==(const reverse_iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem == rhs.m_pItem;
}

template<typename T>
bool List<T>::reverse_iterator::operator!=(const reverse_iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem != rhs.m_pItem;
}
#endif // _D3D12MA_LIST_REVERSE_ITERATOR_FUNCTIONS

#ifndef _D3D12MA_LIST_CONST_ITERATOR_FUNCTIONS
template<typename T>
typename List<T>::iterator List<T>::const_iterator::dropConst() const
{
    return iterator(const_cast<List<T>*>(m_pList), const_cast<Item*>(m_pItem));
}

template<typename T>
const T& List<T>::const_iterator::operator*() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return m_pItem->Value;
}

template<typename T>
const T* List<T>::const_iterator::operator->() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return &m_pItem->Value;
}

template<typename T>
typename List<T>::const_iterator& List<T>::const_iterator::operator++()
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    m_pItem = m_pItem->pNext;
    return *this;
}

template<typename T>
typename List<T>::const_iterator& List<T>::const_iterator::operator--()
{
    if (m_pItem != NULL)
    {
        m_pItem = m_pItem->pPrev;
    }
    else
    {
        D3D12MA_HEAVY_ASSERT(!m_pList->IsEmpty());
        m_pItem = m_pList->Back();
    }
    return *this;
}

template<typename T>
typename List<T>::const_iterator List<T>::const_iterator::operator++(int)
{
    const_iterator result = *this;
    ++* this;
    return result;
}

template<typename T>
typename List<T>::const_iterator List<T>::const_iterator::operator--(int)
{
    const_iterator result = *this;
    --* this;
    return result;
}

template<typename T>
bool List<T>::const_iterator::operator==(const const_iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem == rhs.m_pItem;
}

template<typename T>
bool List<T>::const_iterator::operator!=(const const_iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem != rhs.m_pItem;
}
#endif // _D3D12MA_LIST_CONST_ITERATOR_FUNCTIONS

#ifndef _D3D12MA_LIST_CONST_REVERSE_ITERATOR_FUNCTIONS
template<typename T>
typename List<T>::reverse_iterator List<T>::const_reverse_iterator::dropConst() const
{
    return reverse_iterator(const_cast<List<T>*>(m_pList), const_cast<Item*>(m_pItem));
}

template<typename T>
const T& List<T>::const_reverse_iterator::operator*() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return m_pItem->Value;
}

template<typename T>
const T* List<T>::const_reverse_iterator::operator->() const
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    return &m_pItem->Value;
}

template<typename T>
typename List<T>::const_reverse_iterator& List<T>::const_reverse_iterator::operator++()
{
    D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
    m_pItem = m_pItem->pPrev;
    return *this;
}

template<typename T>
typename List<T>::const_reverse_iterator& List<T>::const_reverse_iterator::operator--()
{
    if (m_pItem != NULL)
    {
        m_pItem = m_pItem->pNext;
    }
    else
    {
        D3D12MA_HEAVY_ASSERT(!m_pList->IsEmpty());
        m_pItem = m_pList->Front();
    }
    return *this;
}

template<typename T>
typename List<T>::const_reverse_iterator List<T>::const_reverse_iterator::operator++(int)
{
    const_reverse_iterator result = *this;
    ++* this;
    return result;
}

template<typename T>
typename List<T>::const_reverse_iterator List<T>::const_reverse_iterator::operator--(int)
{
    const_reverse_iterator result = *this;
    --* this;
    return result;
}

template<typename T>
bool List<T>::const_reverse_iterator::operator==(const const_reverse_iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem == rhs.m_pItem;
}

template<typename T>
bool List<T>::const_reverse_iterator::operator!=(const const_reverse_iterator& rhs) const
{
    D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
    return m_pItem != rhs.m_pItem;
}
#endif // _D3D12MA_LIST_CONST_REVERSE_ITERATOR_FUNCTIONS

#ifndef _D3D12MA_LIST_FUNCTIONS
template<typename T>
List<T>::List(const ALLOCATION_CALLBACKS& allocationCallbacks)
    : m_AllocationCallbacks(allocationCallbacks),
    m_ItemAllocator(allocationCallbacks, 128),
    m_pFront(NULL),
    m_pBack(NULL),
    m_Count(0) {}

template<typename T>
void List<T>::Clear()
{
    if(!IsEmpty())
    {
        Item* pItem = m_pBack;
        while(pItem != NULL)
        {
            Item* const pPrevItem = pItem->pPrev;
            m_ItemAllocator.Free(pItem);
            pItem = pPrevItem;
        }
        m_pFront = NULL;
        m_pBack = NULL;
        m_Count = 0;
    }
}

template<typename T>
typename List<T>::Item* List<T>::PushBack()
{
    Item* const pNewItem = m_ItemAllocator.Alloc();
    pNewItem->pNext = NULL;
    if(IsEmpty())
    {
        pNewItem->pPrev = NULL;
        m_pFront = pNewItem;
        m_pBack = pNewItem;
        m_Count = 1;
    }
    else
    {
        pNewItem->pPrev = m_pBack;
        m_pBack->pNext = pNewItem;
        m_pBack = pNewItem;
        ++m_Count;
    }
    return pNewItem;
}

template<typename T>
typename List<T>::Item* List<T>::PushFront()
{
    Item* const pNewItem = m_ItemAllocator.Alloc();
    pNewItem->pPrev = NULL;
    if(IsEmpty())
    {
        pNewItem->pNext = NULL;
        m_pFront = pNewItem;
        m_pBack = pNewItem;
        m_Count = 1;
    }
    else
    {
        pNewItem->pNext = m_pFront;
        m_pFront->pPrev = pNewItem;
        m_pFront = pNewItem;
        ++m_Count;
    }
    return pNewItem;
}

template<typename T>
typename List<T>::Item* List<T>::PushBack(const T& value)
{
    Item* const pNewItem = PushBack();
    pNewItem->Value = value;
    return pNewItem;
}

template<typename T>
typename List<T>::Item* List<T>::PushFront(const T& value)
{
    Item* const pNewItem = PushFront();
    pNewItem->Value = value;
    return pNewItem;
}

template<typename T>
void List<T>::PopBack()
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    Item* const pBackItem = m_pBack;
    Item* const pPrevItem = pBackItem->pPrev;
    if(pPrevItem != NULL)
    {
        pPrevItem->pNext = NULL;
    }
    m_pBack = pPrevItem;
    m_ItemAllocator.Free(pBackItem);
    --m_Count;
}

template<typename T>
void List<T>::PopFront()
{
    D3D12MA_HEAVY_ASSERT(m_Count > 0);
    Item* const pFrontItem = m_pFront;
    Item* const pNextItem = pFrontItem->pNext;
    if(pNextItem != NULL)
    {
        pNextItem->pPrev = NULL;
    }
    m_pFront = pNextItem;
    m_ItemAllocator.Free(pFrontItem);
    --m_Count;
}

template<typename T>
void List<T>::Remove(Item* pItem)
{
    D3D12MA_HEAVY_ASSERT(pItem != NULL);
    D3D12MA_HEAVY_ASSERT(m_Count > 0);

    if(pItem->pPrev != NULL)
    {
        pItem->pPrev->pNext = pItem->pNext;
    }
    else
    {
        D3D12MA_HEAVY_ASSERT(m_pFront == pItem);
        m_pFront = pItem->pNext;
    }

    if(pItem->pNext != NULL)
    {
        pItem->pNext->pPrev = pItem->pPrev;
    }
    else
    {
        D3D12MA_HEAVY_ASSERT(m_pBack == pItem);
        m_pBack = pItem->pPrev;
    }

    m_ItemAllocator.Free(pItem);
    --m_Count;
}

template<typename T>
typename List<T>::Item* List<T>::InsertBefore(Item* pItem)
{
    if(pItem != NULL)
    {
        Item* const prevItem = pItem->pPrev;
        Item* const newItem = m_ItemAllocator.Alloc();
        newItem->pPrev = prevItem;
        newItem->pNext = pItem;
        pItem->pPrev = newItem;
        if(prevItem != NULL)
        {
            prevItem->pNext = newItem;
        }
        else
        {
            D3D12MA_HEAVY_ASSERT(m_pFront == pItem);
            m_pFront = newItem;
        }
        ++m_Count;
        return newItem;
    }
    else
    {
        return PushBack();
    }
}

template<typename T>
typename List<T>::Item* List<T>::InsertAfter(Item* pItem)
{
    if(pItem != NULL)
    {
        Item* const nextItem = pItem->pNext;
        Item* const newItem = m_ItemAllocator.Alloc();
        newItem->pNext = nextItem;
        newItem->pPrev = pItem;
        pItem->pNext = newItem;
        if(nextItem != NULL)
        {
            nextItem->pPrev = newItem;
        }
        else
        {
            D3D12MA_HEAVY_ASSERT(m_pBack == pItem);
            m_pBack = newItem;
        }
        ++m_Count;
        return newItem;
    }
    else
        return PushFront();
}

template<typename T>
typename List<T>::Item* List<T>::InsertBefore(Item* pItem, const T& value)
{
    Item* const newItem = InsertBefore(pItem);
    newItem->Value = value;
    return newItem;
}

template<typename T>
typename List<T>::Item* List<T>::InsertAfter(Item* pItem, const T& value)
{
    Item* const newItem = InsertAfter(pItem);
    newItem->Value = value;
    return newItem;
}
#endif // _D3D12MA_LIST_FUNCTIONS
#endif // _D3D12MA_LIST

#ifndef _D3D12MA_INTRUSIVE_LINKED_LIST
/*
Expected interface of ItemTypeTraits:
struct MyItemTypeTraits
{
    using ItemType = MyItem;
    static ItemType* GetPrev(const ItemType* item) { return item->myPrevPtr; }
    static ItemType* GetNext(const ItemType* item) { return item->myNextPtr; }
    static ItemType*& AccessPrev(ItemType* item) { return item->myPrevPtr; }
    static ItemType*& AccessNext(ItemType* item) { return item->myNextPtr; }
};
*/
template<typename ItemTypeTraits>
class IntrusiveLinkedList
{
public:
    using ItemType = typename ItemTypeTraits::ItemType;
    static ItemType* GetPrev(const ItemType* item) { return ItemTypeTraits::GetPrev(item); }
    static ItemType* GetNext(const ItemType* item) { return ItemTypeTraits::GetNext(item); }

    // Movable, not copyable.
    IntrusiveLinkedList() = default;
    IntrusiveLinkedList(const IntrusiveLinkedList&) = delete;
    IntrusiveLinkedList(IntrusiveLinkedList&& src);
    IntrusiveLinkedList& operator=(const IntrusiveLinkedList&) = delete;
    IntrusiveLinkedList& operator=(IntrusiveLinkedList&& src);
    ~IntrusiveLinkedList() { D3D12MA_HEAVY_ASSERT(IsEmpty()); }

    size_t GetCount() const { return m_Count; }
    bool IsEmpty() const { return m_Count == 0; }

    ItemType* Front() { return m_Front; }
    ItemType* Back() { return m_Back; }
    const ItemType* Front() const { return m_Front; }
    const ItemType* Back() const { return m_Back; }

    void PushBack(ItemType* item);
    void PushFront(ItemType* item);
    ItemType* PopBack();
    ItemType* PopFront();

    // MyItem can be null - it means PushBack.
    void InsertBefore(ItemType* existingItem,