// Copyright (c) 2019-2021, NVIDIA CORPORATION. All rights reserved.
//
// NVIDIA CORPORATION and its licensors retain all intellectual property
// and proprietary rights in and to this software, related documentation
// and any modifications thereto.  Any use, reproduction, disclosure or
// distribution of this software and related documentation without an express
// license agreement from NVIDIA CORPORATION is strictly prohibited.
//
#pragma once

#include <carb/Defines.h>
#include <carb/flatcache/AttrNameAndType.h>
#include <carb/flatcache/IdTypes.h>
#include <carb/flatcache/ApiLogger.h>
#include <carb/flatcache/HashMap.h>
#include <carb/flatcache/IFlatcache.h>
#include <carb/flatcache/IPath.h>
#include <carb/flatcache/IToken.h>
#include <carb/flatcache/Ordered_Set.h>
#include <carb/flatcache/Platform.h>
#include <carb/flatcache/PrimChanges.h>
#include <carb/flatcache/Type.h>
#include <carb/logging/Log.h>
#include <carb/profiler/Profile.h>
#include <carb/thread/Mutex.h>

#include <omni/gpucompute/GpuCompute.h>


#include <fstream>

// The following is needed to include USD headers
#if defined(__GNUC__)
#    pragma GCC diagnostic push
#    pragma GCC diagnostic ignored "-Wdeprecated-declarations"
#    pragma GCC diagnostic ignored "-Wunused-local-typedefs"
#    pragma GCC diagnostic ignored "-Wunused-function"
// This suppresses deprecated header warnings, which is impossible with pragmas.
// Alternative is to specify -Wno-deprecated build option, but that disables other useful warnings too.
#    ifdef __DEPRECATED
#        define OMNI_USD_SUPPRESS_DEPRECATION_WARNINGS
#        undef __DEPRECATED
#    endif
#endif
#include <pxr/base/tf/type.h>
#include <pxr/usd/usd/timeCode.h>

// PathToAttributesMap doesn't depend on USD for tokens or paths
// However, it's useful to be able to see the USD text representation of tokens and
// paths when debugging. Set ENABLE_USD_DEBUGGING to 1 to enable that.

#if defined(_DEBUG)
#    define ENABLE_USD_DEBUGGING 1
#else
#    define ENABLE_USD_DEBUGGING 0
#endif

// TODO: Move this to some shared macro header if needed elsewhere
#if defined(_DEBUG)
#define VALIDATE_TRUE(X) CARB_ASSERT(X)
#else
#define VALIDATE_TRUE(X) X
#endif

#define PTAM_SIZE_TYPE size_t
#define PTAM_SIZE_TYPEC (flatcache::TypeC(carb::flatcache::Type(carb::flatcache::BaseDataType::eUInt64)))
static_assert(sizeof(PTAM_SIZE_TYPE) == sizeof(uint64_t), "Unexpected sizeof size_t");

#define PTAM_POINTER_TYPE void*
#define PTAM_POINTER_TYPEC (flatcache::TypeC(carb::flatcache::Type(carb::flatcache::BaseDataType::eUInt64)))
static_assert(sizeof(PTAM_POINTER_TYPE) == sizeof(uint64_t), "Unexpected sizeof void*");

// When we switch to CUDA async CPU<->GPU copies, we'll need to use pinned CPU
// memory for performance. However, the allocations themselves will be much
// slower. If you want to see how much slower, set USE_PINNED_MEMORY to 1.
// When we do switch, we should probably do a single allocation and sub
// allocate it ourselves. That way we'd only call cudaHostAlloc once.
#define USE_PINNED_MEMORY 0

// Set this to one to enable CARB profile zones for large bucket copies
#define PROFILE_LARGE_BUCKET_COPIES 0

// We plan to move TfToken and AssetPath construction to IToken.
// Until we do we have to depend on token.h, a USD header
#include "FlatCacheUSD.h"
#include <pxr/usd/sdf/pathTable.h> // 104 only - do not port this to 105+

// Enums are in their own file since they have no external dependencies
#include "Enums.h"

#include <pxr/base/tf/token.h>
#include <pxr/usd/sdf/path.h>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <utility>

using pxr::UsdTimeCode;
using Hierarchy = pxr::SdfPathTable<int>;  // 104 only - do not port this to 105+

namespace carb
{
namespace flatcache
{
struct AttrName
{
    TokenC name;
    NameSuffix suffix;

    bool operator<(const AttrName& other) const = delete;
    bool operator==(const AttrName& other) const = delete;
};

// Use the same hash_combine as boost
template <class T>
static inline size_t hash_combine(std::size_t seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
}
}
}

namespace carb
{
namespace flatcache
{

inline std::string toString(NameSuffix suffix)
{
    if (suffix == NameSuffix::connection)
        return "_connection";
    else if (suffix == NameSuffix::none)
        return "";

    return "";
}

inline std::ostream& operator<<(std::ostream& s, const NameSuffix& nameSuffix)
{
    s << toString(nameSuffix);
    return s;
}

// FlatCache buckets UsdPrims according to their type and the UsdAttributes
// they have. For example, all the UsdGeomMeshes can go in one bucket, all the
// UsdSkelAnimations in another. The user can then quickly get a contiguous
// array of all the meshes, without having to traverse the whole stage.
//
// The name of a bucket is its set of attribute names (Tokens).
// As in the USD API, these tokens are the names used in USDA files, not C++
// type names like UsdGeomMesh.
//
// Example (using C++11 initializer lists to create the sets):
//   Bucket meshes = { Token("Mesh") };
//   Bucket skelAnimations = { Token("SkelAnimation") };
//
// For efficiency, set is an ordered c++ array, not std::set
using Bucket = set<AttrNameAndType>;



struct BucketAndId
{
    const Bucket bucket;
    const BucketId bucketId;
};

// Buckets store attribute values in contiguous arrays, and in C++ array
// indices are size_t
using ArrayIndex = size_t;
const ArrayIndex kInvalidArrayIndex = 0xffff'ffff'ffff'ffff;

// Invariants:
// I0: setOfChangedIndices = [0..N), if allIndicesChanged
//                         = changedIndices, otherwise
// I1: If setOfChangedIndices==[0..N) then allIndicesChanged=true and changedIndices = {}
// where N is defined by the caller
//
// In particular this means that changedIndices can't have size N
// because if all indices were changed, then changedIndices = {}, by I1
struct ChangedIndicesImpl
{
    bool allIndicesChanged = true;
    flatcache::set<ArrayIndex> changedIndices;

    ChangedIndicesImpl(size_t N)
    {
        if (N == 0)
            allIndicesChanged = true;
        else
            allIndicesChanged = false;
    }

    // Create the singleton set {index}
    ChangedIndicesImpl(ArrayIndex index, size_t N)
    {
        if (index == 0 && N == 1)
        {
            // Maintain invariant I0
            allIndicesChanged = true;
        }
        else
        {
            // Maintain invariant I0
            changedIndices = { index };
            allIndicesChanged = false;
        }
    }

    void dirtyAll()
    {
        // Maintain invariant I1
        allIndicesChanged = true;
        changedIndices.clear();
    }

    void insert(size_t index, size_t N)
    {
        CARB_ASSERT(index < N);

        // If all indices already changed, then inserting an index has no
        // effect
        if (allIndicesChanged)
            return;

        changedIndices.insert(index);

        // Maintain invariant I1
        if (changedIndices.size() == N)
        {
            dirtyAll();
        }
    }

    void decrementN(size_t newN)
    {
        if (allIndicesChanged)
            return;

        changedIndices.erase(newN);

        if (changedIndices.size() == newN)
            allIndicesChanged = true;
    }

    void erase(size_t index, size_t N)
    {
        CARB_ASSERT(index < N);

        if (allIndicesChanged)
        {
            allIndicesChanged = false;

            // Make a sorted list of integers [0..N) \ index
            changedIndices.v.resize(N - 1);
            size_t dest = 0;
            for (size_t i = 0; i != index; i++)
            {
                changedIndices.v[dest++] = i;
            }
            for (size_t i = index + 1; i != N; i++)
            {
                changedIndices.v[dest++] = i;
            }
            return;
        }

        changedIndices.erase(index);
    }

    bool contains(size_t index)
    {
        if (allIndicesChanged)
            return true;

        return changedIndices.contains(index);
    }
};

struct ArrayAndDirtyIndices
{
    SpanC array; // We use SpanC instead of gsl::span<const uint8_t> to allow casting to array of correct type
    std::vector<ChangedIndicesImpl*> changedIndicesForEachListener; // This is empty if change tracking is not enabled for this attribute
};

// Bucket vectors and their attribute arrays are public, so users can iterate
// over them directly using for loops.
// For users that prefer opaque iterators, we provide View.
struct View;

// FlatCache doesn't need all metadata in UsdAttribute, just the attribute's
// type, size in bytes, whether it is an array, and if it is an array, the
// size of each elements in bytes
struct Typeinfo
{
    size_t size;
    bool isArray;
    size_t arrayElemSize;
};

// FlatCache stores a map from attribute names (Tokens) to their type and
// size.
using TypeToInfo = HashMap<TypeC, Typeinfo, std::hash<TypeC>, std::equal_to<TypeC>, AllocFunctor, FreeFunctor>;

// By default, an attribute's value is not in the cache, and flags == eNone
// Once the user reads a value, ePresent is true
// Once the user writes a value, eDirty is true
enum class Flags
{
    eNone = 0,
    ePresent = 1,
    eDirty = 2
};

// Operators for combining Flags
constexpr enum Flags operator|(const enum Flags a, const enum Flags b)
{
    return (enum Flags)(uint32_t(a) | uint32_t(b));
}
constexpr enum Flags operator&(const enum Flags a, const enum Flags b)
{
    return (enum Flags)(uint32_t(a) & uint32_t(b));
}

struct BucketChangesImpl
{
    // Which attributes changed
    gsl::span<const AttrNameAndType> changedAttributes;

    // For each attribute, which prims changed?
    std::vector<ConstChangedIndicesC> changedIndices;
    gsl::span<const Path> pathArray;

    // Which indices contain newly added prims?
    gsl::span<const size_t> addedIndices;
};

struct PrimBucketListImpl
{
    flatcache::set<BucketId> buckets;
    std::vector<BucketChangesImpl> changes;

    void clear()
    {
        buckets.clear();
        changes.clear();
    }
};

using SerializationCache = HashMap<uint64_t, std::string>;
using DeserializationCache = HashMap<std::string, pxr::SdfPath>;

// Now we've defined the basic types, we can define the type of FlatCache.
//
// Abstractly, FlatCache maps each Path to the UsdAttributes of the UsdPrim
// at that path. So the type of FlatCache is "PathToAttributesMap".

struct PathToAttributesMap
{
    struct MirroredArray
    {
    private:
        std::vector<uint8_t> cpuArray;

    public:
        Platform& platform;
        TypeC type;
        Typeinfo typeinfo;
        uint8_t* gpuArray;
        size_t gpuCapacity; // Amount of memory allocated at gpuArray in bytes
        std::vector<void*> d3dArrays; // Actually vector of Buffer*

        size_t count;
        bool usdValid;
        bool cpuValid;
        bool gpuValid;
        bool gpuAllocedWithCuda;
        using AttributeMutex = carb::thread::mutex;
        AttributeMutex attributeMutex;


        MirroredArray(Platform& platform_, const TypeC &type, const Typeinfo& typeinfo) noexcept;
        ~MirroredArray();

        MirroredArray(const MirroredArray& other) = delete;
        MirroredArray& operator=(const MirroredArray& other) noexcept;

        MirroredArray(MirroredArray&& other) noexcept;
        MirroredArray& operator=(MirroredArray&& other) noexcept;

        friend void swap(MirroredArray& a, MirroredArray& b) noexcept;

        inline bool isArrayOfArray() const
        {
            CARB_ASSERT((typeinfo.arrayElemSize != 0) == typeinfo.isArray);
            return typeinfo.isArray;
        }

        inline MirroredArray* getValuesArray()
        {
            return this;
        }

        void resize(size_t byteCount)
        {
            // CPU
            // At the moment, CPU always resizes, but eventually it will only
            // resize if it is allocated and valid
            // This will ensure that GPU temp data is never allocated on CPU
            cpuArray.resize(byteCount);

            // Don't need to resize GPU here, because it is deferred until next
            // copy to/from GPU mem
        }

        // GPU resize that preserves existing contents
        // This is used by addPath and addAttributes
        void resizeGpu(omni::gpucompute::GpuCompute* computeAPI,
                       omni::gpucompute::Context* computeCtx,
                       size_t byteCount,
                       size_t elemSize)
        {
            if (!computeAPI || !computeCtx)
                return;

            bool capacitySufficient = (byteCount <= gpuCapacity);
            if (!capacitySufficient)
            {
                void* oldGpuArray = gpuArray;
                size_t oldByteCount = gpuCapacity;

                gpuArray = reinterpret_cast<uint8_t*>(computeAPI->mallocAsync(*computeCtx, byteCount, elemSize));
                gpuCapacity = byteCount;

                if (oldGpuArray)
                {
                    using omni::gpucompute::MemcpyKind;
                    computeAPI->memcpyAsync(*computeCtx, gpuArray, oldGpuArray, oldByteCount, MemcpyKind::deviceToDevice);
                    computeAPI->freeAsync(*computeCtx, oldGpuArray);
                }
            }
        }

        size_t size() const
        {
            return cpuArray.size();
        }

        uint8_t* cpuData()
        {
            return cpuArray.data();
        }

        const uint8_t* cpuData() const
        {
            return cpuArray.data();
        }

        void clear()
        {
            cpuArray.clear();
        }
    };

    using ScalarAttributeArray = MirroredArray;

    struct ArrayAttributeArray
    {
        enum class MirroredArrays : uint8_t
        {
            Values,
            ElemCounts,
            CpuElemCounts,
            GpuElemCounts,
            GpuPtrs,
            Count
        };

        ArrayAttributeArray(Platform& platform_, const TypeC& type, const Typeinfo &typeinfo) noexcept;
        ~ArrayAttributeArray();

        ArrayAttributeArray(const ArrayAttributeArray& other) = delete;
        ArrayAttributeArray& operator=(const ArrayAttributeArray& other) noexcept;

        ArrayAttributeArray(ArrayAttributeArray&& other) noexcept;
        ArrayAttributeArray& operator=(ArrayAttributeArray&& other) noexcept;

        friend void swap(ArrayAttributeArray& a, ArrayAttributeArray& b) noexcept;

        inline MirroredArray* getValuesArray()
        {
            return &values;
        }

        MirroredArray values;
        MirroredArray elemCounts;
        MirroredArray cpuElemCounts;
        MirroredArray gpuElemCounts;
        MirroredArray gpuPtrs;
    };

    // DO NOT generalize this static_assert using globally named defines for magic numbers.
    // We intentionally sprinkle static_assert on hardcoded sizes around this file to increase friction when changing
    // the struct definition. Any change to ArrayAttributeArray requires evaluating multiple locations that rely on
    // keeping in sync with the struct. Having each of these be hardcoded comparions forces future authors to
    // individually evaluate each dependent site for correctness. If the comparison is generalized, future authors could
    // simply adjust the global definition without examining every dependent routine, which might lead to errors.
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");

    struct Changes
    {
        // changedAttributes and changesIndices together implement an ordered
        // map, from attribute to changed indices.
        // changedAttributes is a flatcache::set, which is a sorted std::vector.
        //
        // To lookup an element of the map, find the index, i, of the key in
        // changedAttributes, then read the value from changedIndices[i]
        //
        // changedAttributes and changedIndices must have the same size.
        //
        // TODO: make a general ordered_map class based on flatcache::set
        flatcache::set<AttrNameAndType> changedAttributes;
        std::vector<ChangedIndicesImpl> changedIndices;

        //
        // New elements are stored in a set
        //
        flatcache::set<ArrayIndex> addedIndices;

        void setDirty(const AttrNameAndType& nameAndType, size_t index, size_t maxIndex)
        {
            auto& keys = changedAttributes.v;
            auto& values = changedIndices;
            auto insertIter = lower_bound(keys.begin(), keys.end(), nameAndType);
            ptrdiff_t insertIndex = insertIter - keys.begin();
            bool found = (insertIter != keys.end() && !(nameAndType < *insertIter));

            if (found)
            {
                values[insertIndex].insert(index, maxIndex);
            }
            else
            {
                keys.insert(insertIter, nameAndType);
                values.insert(values.begin() + insertIndex, ChangedIndicesImpl(index, maxIndex));
            }
        }

        void dirtyAll(const AttrNameAndType& nameAndType, size_t maxIndex)
        {
            auto& keys = changedAttributes.v;
            auto& values = changedIndices;
            auto insertIter = lower_bound(keys.begin(), keys.end(), nameAndType);
            ptrdiff_t insertIndex = insertIter - keys.begin();
            bool found = (insertIter != keys.end() && !(nameAndType < *insertIter));

            if (found)
            {
                values[insertIndex].dirtyAll();
            }
            else
            {
                keys.insert(insertIter, nameAndType);
                ChangedIndicesImpl changedIndices(maxIndex);
                changedIndices.dirtyAll();
                values.insert(values.begin() + insertIndex, changedIndices);
            }
        }

        void addNewPrim(size_t index)
        {
            addedIndices.insert(index);
        }

        void removePrim(size_t index)
        {
            //
            // we just clean the index from the set
            //
            addedIndices.erase(index);
        }

        size_t getNewPrimCount()
        {
            return addedIndices.size();
        }
    };

    // FlatCache buckets UsdPrims according to type and attributes, and
    // BucketImpl stores the attribute values of a bucket's prims in
    // structure-of-arrays (SOA) format.
    // BucketImpl maps each attribute name (TokenC) to a MirroredArray, a
    // contiguous byte array (vector<uint8_t>) and a bitfield encoding the
    // validate/dirtiness of each mirror.
    // Abstractly, flatcache data is addressed like a multidimensional array
    // buckets[bucket][attributeName][path].
    // FlatCache uses byte arrays instead of typed arrays, because USD files,
    // scripts, and plugins can define custom types, so no dll or exe knows the
    // complete set of types at the time of its compilation.
    // BucketImpl also contains elemToPath to map each SOA element to the
    // Path it came from.
    struct BucketImpl
    {
        struct Hasher
        {
            size_t operator()(const AttrName& key) const
            {
                return hash_combine(hash(key.name), uint32_t(key.suffix));
            }
        };
        struct KeyEqual
        {
            bool operator()(const AttrName& a, const AttrName& b) const
            {
                return (a.name == b.name) && (a.suffix == b.suffix);
            }
        };

        using ScalarAttributeArrays = HashMap<AttrName, ScalarAttributeArray, Hasher, KeyEqual, AllocFunctor, FreeFunctor>;
        using ArrayAttributeArrays = HashMap<AttrName, ArrayAttributeArray, Hasher, KeyEqual, AllocFunctor, FreeFunctor>;

        Platform& platform;

        ScalarAttributeArrays scalarAttributeArrays;
        ArrayAttributeArrays arrayAttributeArrays;

        std::vector<pxr::SdfPath> elemToPath;

        // listenerIdToChanges entries are lazily created when the user changes
        // an attribute, or when an attribute moves between buckets
        HashMap<ListenerId, Changes, ListenerIdHasher, std::equal_to<ListenerId>, AllocFunctor, FreeFunctor> listenerIdToChanges;


        template<typename CallbackT>
        void forEachValueArray(CallbackT callback);

        BucketImpl(Platform &platform_)
            : platform(platform_)
            , scalarAttributeArrays(0, Hasher(), KeyEqual(), AllocFunctor{ &platform.allocator }, FreeFunctor{ &platform.allocator })
            , arrayAttributeArrays(0, Hasher(), KeyEqual(), AllocFunctor{ &platform.allocator }, FreeFunctor{ &platform.allocator })
            , elemToPath()
            , listenerIdToChanges(0, ListenerIdHasher(), std::equal_to<ListenerId>(), AllocFunctor{ &platform.allocator }, FreeFunctor{ &platform.allocator })
        {
        }

        ~BucketImpl()
        {
#if PROFILE_LARGE_BUCKET_COPIES
            size_t count = elemToPath.size();

            carb::profiler::ZoneId zoneId = carb::profiler::kUnknownZoneId;
            if (1000 <= count)
                zoneId = CARB_PROFILE_BEGIN(1, "Destroy Bucket %zu", count);

            arrays.clear();
            elemToPath.clear();

            if (1000 <= count)
                CARB_PROFILE_END(1, zoneId);
#endif // #if PROFILE_LARGE_BUCKET_COPIES
        }

        BucketImpl(const BucketImpl&) = delete;

        inline BucketImpl& operator=(const BucketImpl& other) noexcept
        {
#if PROFILE_LARGE_BUCKET_COPIES
            size_t count = other.elemToPath.size();

            carb::profiler::ZoneId zoneId = carb::profiler::kUnknownZoneId;
            if (1000 <= count)
                zoneId = CARB_PROFILE_BEGIN(1, "Copy Bucket %zu", count);
#endif // #if PROFILE_LARGE_BUCKET_COPIES

            scalarAttributeArrays.clear();
            scalarAttributeArrays.reserve(other.scalarAttributeArrays.size());
            other.scalarAttributeArrays.forEach([this](const AttrName& name, const ScalarAttributeArray &otherArray) {
                // construct new array with the current BucketImpl platform, but mimicing type of otherArray
                ScalarAttributeArray *array;
                scalarAttributeArrays.allocateEntry(name, &array);
                new (array) ScalarAttributeArray(platform, otherArray.type, otherArray.typeinfo);
                *array = otherArray;
            });

            arrayAttributeArrays.clear();
            arrayAttributeArrays.reserve(other.arrayAttributeArrays.size());
            other.arrayAttributeArrays.forEach([this](const AttrName& name, const ArrayAttributeArray &otherArray) {
                // construct new array with the current BucketImpl platform, but mimicing type of otherArray
                ArrayAttributeArray *array;
                arrayAttributeArrays.allocateEntry(name, &array);
                new (array) ArrayAttributeArray(platform, otherArray.values.type, otherArray.values.typeinfo);
                *array = otherArray;
            });

            elemToPath = other.elemToPath;

            listenerIdToChanges.clear();
            listenerIdToChanges.reserve(other.listenerIdToChanges.size());
            other.listenerIdToChanges.forEach([this](const ListenerId& listener, const Changes &otherChanges) {
                Changes* changes;
                VALIDATE_TRUE(listenerIdToChanges.allocateEntry(listener, &changes));
                static_assert(std::is_copy_constructible<Changes>::value, "Expected listenerIdToChanges values to be copy-constructible");
                new (changes) Changes(otherChanges);
            });

            bucket = other.bucket;

#if PROFILE_LARGE_BUCKET_COPIES
            if (1000 <= count)
                CARB_PROFILE_END(1, zoneId);
#endif // #if PROFILE_LARGE_BUCKET_COPIES

            return *this;
        }

        BucketImpl(BucketImpl&& other) noexcept = delete;

        inline BucketImpl& operator=(BucketImpl&& other) noexcept
        {
            // this->platform = std::move(b.platform); // intentionally not move-assigning platform (we can't anyways, it's a ref)
            this->scalarAttributeArrays = std::move(other.scalarAttributeArrays);
            this->arrayAttributeArrays = std::move(other.arrayAttributeArrays);
            this->elemToPath = std::move(other.elemToPath);
            this->listenerIdToChanges = std::move(other.listenerIdToChanges);
            this->bucket = std::move(other.bucket);

            return *this;
        }

        const Bucket& GetBucket() const
        {
            return bucket;
        }


        //
        // TODO: In the future we should support universal ref +
        // move assignments, unforuntately Bucket doesn't follow
        // the rule of 5 so that is unavailable to us currently.
        //
        void SetBucket(const Bucket& _bucket)
        {
            bucket = _bucket;
        }

    private:
        //
        // bucketImpl knows the Bucket it represents
        //
        Bucket bucket;


    };

    /**
     * @struct BucketIdToImpl
     *
     * @brief Convenience data structure for quick bucket lookups
     *
     * @details  We want to avoid the cost of hashmap lookups when possible
     *           due to the large number of times that elements are looked
     *           up via a single element lookup. This class creates a static vector
     *           to track buckets. It also will keep the array densely packed
     *            as possible, while not incurring the cost of moves
     *
     * @notes 1) NOT threadsafe
     *
     * @todo possibly store the last and first valid so one can avoid un-needed
     *       iteration
     * @todo provide an iterator
     * @todo make deleting buckets move lastFreeSlot back where approriate so that
     *       it is always meaningful as "end()"
     */
    struct BucketIdToImpl
    {
        // A reasonable first size for the number of buckets
        // If one changed this number, they would have to update
        // the constants in the unit tests "Check Bucket Growth"
        static const int max_buckets_init = 1024;

        /**
         * @brief Initialize storage to the minimum size
         *        We rely on C++ behavior that default initalizes the
         *        std::vector bool to false for valid tracking
         *
         */
        BucketIdToImpl(Platform& platform)
            : platform(platform)
            , buckets(max_buckets_init)
            , lastEmptySlot{ 0 }
        {
        }

        ~BucketIdToImpl()
        {
            clear();
        }

        /**
         * @brief mimic emplace function for stl objects
         *
         * @details This allows us to do move of buckets after they have been
         *          created into the storage. We choose for backwards compatibility
         *          with other APS to return a pair. It takes care of the correct place
         *          to store the bucket for you to keep the storage as dense as possible.
         *          This claims the next bucket, and will move out of
         * @param bucketImpl a new bucket to be added to the Storage, empty after function call
         *                   due to move.
         *
         * @return <BucketId, BucketImpl&> the pair representing the Id for lookup of the bucket
         *                                 and a reference to the data since it was moved from param
         *
         */
        std::pair<BucketId, BucketImpl&> emplace(BucketImpl* bucketImpl)
        {
            CARB_ASSERT(bucketImpl);
            BucketId bucketId = ClaimNextOpenBucket();
            if (buckets[size_t(bucketId)])
            {
                platform.allocator.delete_(buckets[size_t(bucketId)]);
            }
            buckets[size_t(bucketId)] = std::move(bucketImpl);
            return std::pair<BucketId, BucketImpl&>(bucketId, *buckets[(size_t)bucketId]);
        }

        /**
         * @brief Erase the specified bucket
         *
         * @details This actually forces deletion of the object that is to be deleted it adds the
         *          id to the list of free buckets so that it will be recycled before more are
         *          added to the end
         *
         * @param id : The id of the bucket to be deleted
         */
        void erase(BucketId id)
        {
            if (size_t(id) < buckets.size() && buckets[size_t(id)])
            {
                // Ignoring optimization of if last slot is empty
                freeSlots.push(id);
                platform.allocator.delete_(buckets[size_t(id)]);
                buckets[size_t(id)] = nullptr;
            }
        }

        // Find the bucket at the requested slot, if no bucket exists
        // then we return


        /**
         * @brief Find the bucket if it exists
         *
         * @param id : The id of the bucket to be found
         *
         * @return If the bucket exists a pointer is return, otherwise a null pointer is returned
         */
        BucketImpl* find(BucketId id)
        {
            if (size_t(id)< buckets.size())
                return buckets[size_t(id)];
            return nullptr;
        }

        /**
         * @brief Find the bucket if it exists (const)
         *
         * @param id : The id of the bucket to be found
         *
         * @return If the bucket exists a cosnt pointer is return, otherwise a null pointer is returned
         */
        const BucketImpl* find(BucketId slot) const
        {
            if (size_t(slot) < buckets.size())
                return buckets[size_t(slot)];
            return nullptr;
        }

        /**
         * @brief Clear all the buckets
         *
         * @details This will force deletion of all the nodes and make the storage appear empty
         *
         */
        void clear()
        {
            for (uint64_t i = 0; i < size_t(lastEmptySlot); ++i)
            {
                if (buckets[i])
                {
                    platform.allocator.delete_(buckets[i]);
                    buckets[i] = nullptr;
                }
            }
            // no clear in std::queue so we swap with a new one
            std::queue<BucketId>().swap(freeSlots);
            lastEmptySlot.id = 0;
        }

        /**
         * @brief get the possible end of the storage
         *
         * @details This will return the last possible id for a bucket, however
         *           should be combined with valid to be carefule
         *
         * @return The last "allocated bucket" but could not be valid
         */
        size_t end() const
        {
            return size_t(lastEmptySlot);
        }

        /**
         * @brief Support copy assignment.
         *
         * @note In order for this to be a valid copy it must be followed up
         *       by a call to PathToAttributesMap::BucketImplCopyArrays to
         *       correctly copy array-of-array data.
         *
         * @return Copy constructed buckets, without array-of-arrays set up
         */
        BucketIdToImpl& operator=(const BucketIdToImpl& other)
        {
            // Array of free slots
            this->freeSlots = other.freeSlots;
            // Track the last empty slot
            this->lastEmptySlot = other.lastEmptySlot;

            //
            // A bucketImpl is a struct that mainly contains a map
            // to arrays which are of the data type MirroredArray.
            // A MirroredArray has two states
            //     (1) It contains an array of data
            //     (2) It contains an array of arrays.
            // In the case of (2) the array itself doesn't have enough
            // information to make a copy of the array of arrays, so the
            // copy constructor is overloaded and the structure around the
            // array of arrays is loaded, but the actual copying of that data is
            // pushed off to be done by the function BucketImplCopyArrays
            // which is a member of PathToAttributesMap which is the only place
            // that currently has enough information to make the copy
            //
            this->buckets.resize(other.buckets.size());
            for (size_t i = 0; i < this->buckets.size(); ++i)
            {
                if (other.buckets[i])
                {
                    if (!this->buckets[i])
                    {
                        this->buckets[i] = platform.allocator.new_<BucketImpl>(platform);
                    }
                    *this->buckets[i] = *other.buckets[i];
                }
                else if (this->buckets[i])
                {
                    platform.allocator.delete_(this->buckets[i]);
                    this->buckets[i] = nullptr;
                }
            }

            return *this;
        }

        /**
         * @brief Resize the internals
         *
         * @details Note that resize will only grow, calling with a smaller size is a no-op
         *
         */
        void resize(size_t newSize)
        {
            if (newSize > buckets.size()) {
                buckets.resize(newSize);
            }
        }

        /**
         * @brief Claim a bucket by index, this means that the pointer will be
         *        returned regardless of valid, and that it will mark as valid
         *        and update internals where needed. In the case where an index is
         *        requested that is past the allocated then more memory is allocated
         *
         * @note  This should be used sparingly, generally it is intended to be used
         *         in the case where we are re-constructing one flat cache from another,
         *         if things are done out of order it could be expensize, also it is assumed
         *         all external mappings are maintained by the claimer
         *
         * @param id : The id of the bucket to be claimed
         *
         * @return A reference to the bucketImpl that was claimed
         */
        BucketImpl& claim(BucketId id)
        {
            // grow if needed
            if (size_t(id)>= buckets.size()) {
                resize(size_t(id)+ 1);
            }

            // if the bucket is already valid we can just return access to it
            if (!buckets[size_t(id)])
            {
                // otherwise we need to update accordingly
                while (lastEmptySlot <= id) {
                    if (!buckets[size_t(lastEmptySlot)]) {
                        freeSlots.push(lastEmptySlot);
                    }
                    ++lastEmptySlot;
                }
                buckets[size_t(id)] = platform.allocator.new_<BucketImpl>(platform);
            }
            CARB_ASSERT(buckets[size_t(id)]);
            return *buckets[size_t(id)];
        }

        template<typename CallbackT>
        void forEachValidBucket(CallbackT callback) const;

    private:
        /**
         * @brief Get the next open bucket
         *
         * @note May invalidate references to existing buckets
         *
         */
        BucketId ClaimNextOpenBucket()
        {
            BucketId slot = lastEmptySlot;

            if (freeSlots.size() != 0)
            {
                slot = freeSlots.front();
                freeSlots.pop();
            }
            else
            {
                ++lastEmptySlot;
                if (size_t(lastEmptySlot) == buckets.size())
                {
                    std::vector<BucketImpl*> newVector;
                    newVector.resize(buckets.size() * 2);

                    //
                    // A bucketImpl is a struct that mainly contains a map
                    // to arrays which are of the data type MirroredArray.
                    // A MirroredArray has two states
                    //     (1) It contains an array of data
                    //     (2) It contains an array of arrays.
                    // In the case of (2) the array itself doesn't have enough
                    // information to make a copy of the array of arrays, so the
                    // copy constructor is overloaded and the structure around the
                    // array of arrays is loaded, but the actual copying of that data is
                    // pushed off to be done by the function BucketImplCopyArrays
                    // which is a member of PathToAttributesMap which is the only place
                    // that currently has enough information to make the copy
                    //
                    // Since we cannot guarantee that someone will know to call
                    // the copyArrays function we enforce that data must be moved here.
                    //
                    for (size_t i = 0; i < buckets.size(); ++i)
                    {
                        newVector[i] = std::move(buckets[i]);
                    }
                    std::swap(newVector, buckets);
                }
            }
            CARB_ASSERT(!buckets[size_t(slot)]);
            buckets[size_t(slot)] = platform.allocator.new_<BucketImpl>(platform);
            return slot;
        }

        Platform& platform;
        // array of bucket impls
        std::vector<BucketImpl*> buckets;
        // Array of free slots
        std::queue<BucketId> freeSlots;
        // Track the last empty slot
        BucketId lastEmptySlot;
    };

    // Internally we convert Paths to uint64_t path ids using asInt().
    // PathId is the domain of pathToBucketElem, defined below.
    using PathId = PathC;

    Platform& platform;

    // Concretely, FlatCache is the following three maps:
    // 1) Each path maps to a bucket, and an SOA index within that bucket.
    //    This level of indirection allows the user to delete prims and/or
    //    attributes without creating holes in the SOAs. Whenever the user
    //    deletes a prim, the cache moves the last SOA element to the deleted
    //    element, and updates the path to element map of the moved SOA element.
    // 2) Buckets (sets of attribute names) map to BucketImpls, defined above.
    //    This allows the user to quickly get e.g. arrays of all the meshes,
    //    or all the meshes that have rigid body attributes.
    // 3) pxr::TfType names map to TypeInfos, containing attribute type and size in bytes.
    HashMap<PathId, std::pair<BucketId, ArrayIndex>, std::hash<PathId>, std::equal_to<PathId>, AllocFunctor, FreeFunctor> pathToBucketElem;
    BucketIdToImpl buckets;
    std::map<Bucket, BucketId> attrNameSetToBucketId;

    // Each listener has its own attrNamesToLog and enableChangeTracking
    struct ChangeTrackerConfig
    {
        set<TokenC> attrNamesToLog;
        bool changeTrackingEnabled = true;
    };

    HashMap<ListenerId, ChangeTrackerConfig, ListenerIdHasher, std::equal_to<ListenerId>, AllocFunctor, FreeFunctor> listenerIdToChangeTrackerConfig;

    TypeToInfo typeToInfo;
    UsdStageId usdStageId;
    bool minimalPopulationDone = false; // 104 only - do not port this forward to 105+
    Hierarchy stageHierarchy; // 104 only - do not port this forward to 105+

    mutable bool apiLogEnabled = false;

    // The rest of PathToAttributesMap is methods
    size_t size();
    void clear();
    void printMirroredArray(const char* const label, const ScalarAttributeArray &array, const size_t* const arrayElemCount) const;
    void print() const;

    // Void* multiple attribute interface
    void getArraysRdC(const void** attrsOut, const Bucket& bucket, const TokenC* attrNames, size_t attrCount);
    void getAttributesRdC(const void** attrsOut, const PathC* paths, const TokenC* attrNames, size_t attrCount);
    void getAttributesRdGpuC(const void** attrsOut, const PathC* paths, const TokenC* attrNames, size_t attrCount, PtrToPtrKind ptrToPtrKind);
    void getArraysWrC(void** attrsOut, const Bucket& bucket, const TokenC* attrNames, size_t attrCount);
    void getAttributesWrC(void** attrsOut, const PathC& path, const TokenC* attrNames, size_t attrCount);
    void getAttributesWrGpuC(void** attrsOut, const PathC& path, const TokenC* attrNames, size_t attrCount, PtrToPtrKind ptrToPtrKind);

    // Span interface
    SpanC getArraySpanC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    ConstSpanC getArraySpanRdC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getArraySpanWrC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);

    // Void* interface
    void addAttributeC(
        const PathC& path, const TokenC& attrName, TypeC type, const void* value = nullptr);
    void addArrayAttributeC(
        const PathC& path, const TokenC& attrName, TypeC type, const void* value, const size_t arrayElemCount);
    void addAttributesToPrim(
        const PathC& path, const std::vector<TokenC>& attrNames, const std::vector<TypeC>& typeCs);
    void addAttributeC(const PathC& path,
                       const TokenC& attrName,
                       NameSuffix suffix,
                       TypeC type,
                       const void* value = nullptr);
    void addArrayAttributeC(const PathC& path,
                       const TokenC& attrName,
                       NameSuffix suffix,
                       TypeC type,
                       const void* value,
                       const size_t arrayElemCount);

    void* getArrayC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getAttributeC(const PathC& path, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    const void* getArrayRdC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    ConstSpanC getAttributeRdC(const PathC& path, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    void* getArrayWrC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getAttributeWrC(const PathC& path, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getOrCreateAttributeWrC(const PathC& path, const TokenC& attrName, TypeC type);

    // Type safe interface
    template <typename T>
    void addAttribute(const PathC& path, const TokenC& attrName, TypeC type, const T& value);
    template <typename T>
    void addSubAttribute(const PathC& path, const TokenC& attrName, NameSuffix suffix, TypeC type, const T& value);
    template <typename T>
    T* getArray(const Bucket& bucket, const TokenC& attrName);
    template <typename T>
    T* getAttribute(const PathC& path, const TokenC& attrName);
    template <typename T>
    const T* getArrayRd(const Bucket& bucket, const TokenC& attrName);
    template <typename T>
    const T* getArrayRd(BucketId bucketId, const TokenC& attrName);
    template <typename T>
    const T* getAttributeRd(const PathC& path, const TokenC& attrName);
    template <typename T>
    T* getArrayWr(const Bucket& bucket, const TokenC& attrName);
    template <typename T>
    T* getAttributeWr(const PathC& path, const TokenC& attrName);
    template <typename T>
    T* getAttributeWr(const PathC& path, const TokenC& attrName, NameSuffix suffix);
    void removeAttribute(const PathC& path, const TokenC& attrName);
    void removeSubAttribute(const PathC& path, const TokenC& attrName, NameSuffix suffix);

    /** @brief Destroy all attributes with matching names from prim at given path
     *
     * @path[in] Path to the prim holding the attribute
     * @attrNames[in] Attribute name array
     *
     */
    void removeAttributesFromPath(const PathC& path, const std::vector<TokenC>& attrNames);

    ValidMirrors getAttributeValidBits(
        const PathC& path,
        const TokenC& attrName,
        ArrayAttributeArray::MirroredArrays subArray = ArrayAttributeArray::MirroredArrays::Values) const;

    // Accessors for element count of array attributes
    size_t* getArrayAttributeSize(const PathC& path, const TokenC& attrName);
    const size_t* getArrayAttributeSizeRd(const PathC& path, const TokenC& attrName);
    size_t* getArrayAttributeSizeWr(const PathC& path, const TokenC& attrName);
    size_t* getArrayAttributeSizes(const Bucket& bucket, const TokenC& attrName);
    const size_t* getArrayAttributeSizesRd(const Bucket& bucket, const TokenC& attrName);
    size_t* getArrayAttributeSizesWr(const Bucket& bucket, const TokenC& attrName);

    SpanC setArrayAttributeSizeAndGet(PathC path, const TokenC& attrName, size_t newSize);
    SpanC setArrayAttributeSizeAndGet(BucketId bucketId, size_t elementIndex, const TokenC& attrName, size_t newSize);

    // GPU can currently read, but not write, size of arrays
    // This is because writing causes array to resize, and that's not currently supported on GPU
    const size_t* getArrayAttributeSizeRdGpu(const PathC& path, const TokenC& attrName);
    const size_t* getArrayAttributeSizesRdGpu(const Bucket& bucket, const TokenC& attrName);

    // Void* CUDA GPU interface
    SpanC getAttributeGpuC(const PathC& path, const TokenC& attrName, PtrToPtrKind ptrToPtrKind = PtrToPtrKind::eNotApplicable, NameSuffix suffix = NameSuffix::none);
    ConstSpanC getAttributeRdGpuC(const PathC& path, const TokenC& attrName, PtrToPtrKind ptrToPtrKind = PtrToPtrKind::eNotApplicable, NameSuffix suffix = NameSuffix::none);
    SpanC getAttributeWrGpuC(const PathC& path, const TokenC& attrName, PtrToPtrKind ptrToPtrKind = PtrToPtrKind::eNotApplicable, NameSuffix suffix = NameSuffix::none);
    void* getArrayGpuC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    const void* getArrayRdGpuC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    void* getArrayWrGpuC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);

    // Span CUDA GPU interface
    SpanC getArraySpanGpuC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    ConstSpanC getArraySpanRdGpuC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getArraySpanWrGpuC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);

    // Type safe CUDA GPU interface
    template <typename T>
    T* getAttributeGpu(const PathC& path, const TokenC& attrName, PtrToPtrKind ptrToPtrKind = PtrToPtrKind::eNotApplicable);
    template <typename T>
    const T* getAttributeRdGpu(const PathC& path, const TokenC& attrName, PtrToPtrKind ptrToPtrKind = PtrToPtrKind::eNotApplicable);
    template <typename T>
    T* getAttributeWrGpu(const PathC& path, const TokenC& attrName, PtrToPtrKind ptrToPtrKind = PtrToPtrKind::eNotApplicable);

    template <typename T>
    T* getArrayGpu(const Bucket& bucket, const TokenC& attrName);
    template <typename T>
    const T* getArrayRdGpu(const Bucket& bucket, const TokenC& attrName);
    template <typename T>
    T* getArrayWrGpu(const Bucket& bucket, const TokenC& attrName);

    // D3D GPU interface
    omni::gpucompute::GpuPointer getAttributeD3d(const PathC& path, const TokenC& attrName);
    void* getArrayD3d(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    const void* getArrayRdD3d(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    void* getArrayWrD3d(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);

    // PathC methods
    void addPath(const PathC& path, const Bucket& bucket = {});
    void renamePath(const PathC& oldPath, const PathC& newPath);
    set<AttrNameAndType> getTypes(const PathC& path) const;
    size_t getAttributeCount(const PathC& path) const;
    TypeC getType(const PathC& path, const TokenC& attrName) const;
    void removePath(const PathC& path);
    size_t count(const PathC& path) const;
    size_t count(const PathC& path, const TokenC& attrName) const;

    // Type methods
    void addType(TypeC type, Typeinfo typeInfo);
    Typeinfo getTypeInfo(TypeC type) const;

    // Bucket methods
    BucketId addBucket(const Bucket& bucket);
    void addAttributeC(
        const Bucket& bucket, const TokenC& attrName, TypeC type, const void* value = nullptr);
    void addArrayAttributeC(const Bucket& bucket, const TokenC& attrName, TypeC type, const void* value, const size_t arrayElemCount);
    template <typename T>
    void addAttribute(const Bucket& bucket, const TokenC& attrName, TypeC type, const T& value);
    void removeAttributeC(const Bucket& bucket, const TokenC& attrName, TypeC type);
    void printBucket(const Bucket& bucket) const;
    void printBucketName(const Bucket& bucketTypes, BucketId bucketId) const;
    void printBucketNames() const;
    void printBucketNamesAndTypes() const;
    flatcache::set<BucketId> findBuckets(const set<AttrNameAndType>& all,
                                         const set<AttrNameAndType>& any = {},
                                         const set<AttrNameAndType>& none = {}) const;
    View getView(const set<AttrNameAndType>& inc, const set<AttrNameAndType>& exc = {});
    size_t getElementCount(const Bucket& bucket) const;
    const PathC* getPathArray(const Bucket& bucket) const;
    TypeC getType(const Bucket& bucket, const TokenC& attrName) const;
    /** @brief Destroy all attributes with matching names from a given Bucket - array version of removeAttributeC
     *
     * @bucket[in] Bucket to remove attributes from
     * @attrNames[in] Attribute name array
     *
     */
    void removeAttributesFromBucket(const Bucket& bucket, const std::vector<TokenC>& attrNames);

    // BucketId methods
    size_t getElementCount(BucketId bucketId) const;
    SpanC getArrayC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    ConstSpanC getArrayRdC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getArrayWrC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getOrCreateArrayWrC(
        BucketId bucketId, const TokenC& attrName, TypeC type, NameSuffix suffix = NameSuffix::none);
    SpanC getArrayGpuC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    ConstSpanC getArrayRdGpuC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    SpanC getArrayWrGpuC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix = NameSuffix::none);
    BucketId getBucketId(const PathC& path) const;

    ArrayPointersAndSizesC getArrayAttributeArrayWithSizes(BucketId bucketId, const TokenC& attrName);
    ConstArrayPointersAndSizesC getArrayAttributeArrayWithSizesRd(BucketId bucketId, const TokenC& attrName);
    ArrayPointersAndSizesC getArrayAttributeArrayWithSizesWr(BucketId bucketId, const TokenC& attrName);

    SpanSizeC getArrayAttributeSizes(BucketId bucketId, const TokenC& attrName);
    ConstSpanSizeC getArrayAttributeSizesRd(BucketId bucketId, const TokenC& attrName);
    ConstSpanSizeC getArrayAttributeSizesRdGpu(BucketId bucketId, const TokenC& attrName);
    SpanSizeC getArrayAttributeSizesWr(BucketId bucketId, const TokenC& attrName);

    ConstPathCSpan getPathArray(BucketId bucketId) const;
    Bucket getNamesAndTypes(BucketId bucketId) const;

    // std::vector<Bucket> methods
    std::vector<size_t> getElementCounts(const std::vector<Bucket>& buckets) const;
    template <typename T>
    std::vector<const T*> getArraysRd(const std::vector<Bucket>& buckets, const TokenC& attrName);
    template <typename T>
    std::vector<T*> getArraysWr(const std::vector<Bucket>& buckets, const TokenC& attrName);
    template <typename T>
    std::vector<T*> getArrays(const std::vector<Bucket>& buckets, const TokenC& attrName);

    // BucketImpl methods
    size_t getElementCount(const BucketImpl& bucketImpl) const;

    // Allow default construction
    PathToAttributesMap(const PlatformId& platformId = PlatformId::Global);

    // Disallow copying
    PathToAttributesMap(const PathToAttributesMap&) = delete;

    // Allow copy assignment. This is used by StageWithHistory
    PathToAttributesMap& operator=(const PathToAttributesMap&);

    // Allow move construction and assignment
    PathToAttributesMap(PathToAttributesMap&& other) noexcept = default;
    PathToAttributesMap& operator=(PathToAttributesMap&& other) noexcept = default;

    ~PathToAttributesMap();

    // Methods that are currently used in flatcache.cpp
    // TODO: Make private

    struct ArrayOfArrayInfo
    {
        // For each array, the element count requested by the user
        size_t* arraySizeArray;

        // For each array, the element count allocated on the CPU
        MirroredArray* arrayCpuCapacityArray;

        // For each array, the element count allocated on the GPU
        MirroredArray* arrayGpuCapacityArray;

        // For each array, the GPU data
        MirroredArray* arrayGpuPtrArray;
    };

    struct ConstArrayOfArrayInfo
    {
        // For each array, the element count requested by the user
        const MirroredArray * arraySizeArray;

        // For each array, the element count allocated on the CPU
        const MirroredArray* arrayCpuCapacityArray;

        // For each array, the element count allocated on the GPU
        const MirroredArray* arrayGpuCapacityArray;

        // For each array, the GPU data
        const MirroredArray* arrayGpuPtrArray;
    };

    // enableCpuWrite() is used in flatcache.cpp, so needs to be public
    // TODO: move that code from there to here
    void enableCpuWrite(MirroredArray& array,
                        const size_t* elemToArraySize,
                        MirroredArray* elemToArrayCpuCapacity,
                        MirroredArray* elemToArrayGpuCapacity,
                        MirroredArray* elemToArrayGpuData);

    // getArrayOfArrayInfo() is used in flatcache.cpp, so needs to be public
    // TODO: move that code from there to here
    ArrayOfArrayInfo getArrayOfArrayInfo(Typeinfo typeInfo, BucketImpl& bucketImpl, TokenC attrName);
    ArrayOfArrayInfo getArrayOfArrayInfo(ArrayAttributeArray &arrayAttributeArray);
    ConstArrayOfArrayInfo getArrayOfArrayInfo(Typeinfo typeInfo, const BucketImpl& bucketImpl, TokenC attrName) const;
    ConstArrayOfArrayInfo getArrayOfArrayInfo(const ArrayAttributeArray &arrayAttributeArray) const;
    void bucketImplCopyScalarAttributeArray(ScalarAttributeArray &dest, const ScalarAttributeArray &src);
    void bucketImplCopyArrayAttributeArray(BucketImpl& destBucketImpl, const AttrName& destName, ArrayAttributeArray &dest, const ArrayAttributeArray &src);
    void bucketImplCopyArrays(BucketImpl& destBucketImpl,
                              BucketId destBucketId,
                              const BucketImpl& srcBucketImpl,
                              BucketId srcBucketId,
                              const carb::flatcache::set<AttrNameAndType>& attrFilter = {});

    // Serialization
    struct Serializer
    {
        uint8_t *p;
        uint8_t *buf;
        uint8_t *end;
        uint64_t bytesWritten; // increments even if attempts are made to write past end
        bool overflowed;

        void init(uint8_t *const _buf, uint8_t *const end);
        bool writeBytes(const uint8_t *const src, uint64_t size);
        bool writeString(const char* const s, const size_t len);
        bool writeString(const std::string &s);

        template<typename T>
        bool write(const T &t);
    };

    struct Deserializer
    {
        const uint8_t *p;
        const uint8_t *buf;
        const uint8_t *end;
        uint64_t bytesRead; // increments even if attempts are made to read past end
        bool overflowed;

        void init(const uint8_t *const _buf, const uint8_t *const end);
        bool readBytes(uint8_t *const dst, uint64_t size);
        bool readString(std::string &s);

        template<typename T>
        bool read(T &t);
    };

    uint64_t serializeScalarAttributeArray(BucketImpl& srcBucketImpl, const BucketId& srcBucketId, const AttrName& srcName, ScalarAttributeArray& srcScalarAttributeArray, Serializer &out);
    bool deserializeScalarAttributeArray(BucketImpl& destBucketImpl, const BucketId& destBucketId, Deserializer &in);
    uint64_t serializeArrayAttributeArray(BucketImpl& srcBucketImpl, const BucketId& srcBucketId, const AttrName& srcName, ArrayAttributeArray& srcArrayAttributeArray, Serializer &out);
    bool deserializeArrayAttributeArray(BucketImpl& destBucketImpl, const BucketId& destBucketId, Deserializer &in);

    PrimBucketListImpl getChanges(ListenerId listener);
    void popChanges(ListenerId listener);

private:
    // Device is used by getArrayC
    enum class Device
    {
        eCPU = 0,
        eCudaGPU = 1,
        eD3dVkGPU = 2
    };

    static inline constexpr ArrayOfArrayInfo ScalarArrayOfArrayInfo()
    {
        return ArrayOfArrayInfo{ nullptr, nullptr, nullptr, nullptr };
    }

	// TODO: Now that EnableReadFn and EnableWriteFn can have the same type, should they just be one alias?
    using EnableReadFn = void (PathToAttributesMap::*)(PathToAttributesMap::MirroredArray& array,
                                                       const size_t* elemToArraySize,
                                                       PathToAttributesMap::MirroredArray* elemToArrayCpuCapacity,
                                                       PathToAttributesMap::MirroredArray* elemToArrayGpuCapacity,
                                                       PathToAttributesMap::MirroredArray* elemToArrayGpuData);

    using EnableWriteFn = void (PathToAttributesMap::*)(PathToAttributesMap::MirroredArray& array,
                                                        const size_t* elemToArraySize,
                                                        PathToAttributesMap::MirroredArray* elemToArrayCpuCapacity,
                                                        PathToAttributesMap::MirroredArray* elemToArrayGpuCapacity,
                                                        PathToAttributesMap::MirroredArray* elemToArrayGpuData);

    struct IOConfig
    {
        EnableReadFn enableRead;
        EnableWriteFn enableWrite;
        EnableReadFn enableRdPtrForWrite;
        Device device;
        PtrToPtrKind ptrToPtrKind;

        inline IOConfig& withEnableRead(EnableReadFn _enableRead)
        {
            enableRead = _enableRead;
            return *this;
        }

        inline IOConfig& withEnableWrite(EnableWriteFn _enableWrite)
        {
            enableWrite = _enableWrite;
            return *this;
        }

        inline IOConfig& withEnableRdPtrForWrite(EnableReadFn _enableRdPtrForWrite)
        {
            enableRdPtrForWrite = _enableRdPtrForWrite;
            return *this;
        }

        inline IOConfig& withDevice(Device _device)
        {
            device = _device;
            return *this;
        }

        inline IOConfig& withPtrToPtrKind(PtrToPtrKind _ptrToPtrKind)
        {
            ptrToPtrKind = _ptrToPtrKind;
            return *this;
        }
    };

    void serializeMirroredArrayMetadata(const AttrName& srcName, MirroredArray &srcValuesArray, Serializer &out);
    template<typename ArraysT, typename ArraysMapT>
    void deserializeMirroredArrayMetadata(Platform& platform, ArraysMapT& arraysMap, AttrName &destName, Typeinfo *&typeInfo, ArraysT *&destArray, Deserializer &in);

    BucketImpl& addAttributeInternal(BucketImpl& prevBucketImpl, const Bucket& bucket, const TokenC& attrName, const TypeC ctype, const void* value, const Typeinfo& typeinfo, const size_t arrayElemCount);
    void fillAttributeInternal(BucketImpl& bucketImpl, const AttrName& name, const size_t startIndex, const size_t endIndex, const void* value, const Typeinfo& typeinfo, const size_t arrayElemCount, MirroredArray *const valuesArray, ArrayAttributeArray *const arrayAttributeArray);

    void addAttributeInternal(const PathC& path, const TokenC& attrNameC, const NameSuffix nameSuffix, const TypeC ctype, const void* value, const Typeinfo& typeinfo, const size_t arrayElemCount);

    bool findArrayAttributeArrayForPath(const PathC& path,
                                         const TokenC& attrName,
                                         size_t& outElementIndex,
                                         BucketImpl*& outBucketImpl,
                                         ArrayAttributeArray*& outArrayAttributeArray);

    bool findArrayAttributeArrayForBucketId(const BucketId bucketId,
                                             const TokenC& attrName,
                                             BucketImpl*& outBucketImpl,
                                             ArrayAttributeArray*& outArrayAttributeArray);

    void allocElement(ScalarAttributeArray &scalar);
    void allocElement(ArrayAttributeArray &vector);
    size_t allocElement(BucketImpl& bucketImpl);
    void allocElementForMove(BucketImpl& srcBucketImpl, const ArrayOfArrayInfo &srcAoaInfo, const AttrName& name, MirroredArray &destArray, MirroredArray *const srcArray);
    size_t allocElementForMove(BucketImpl& destBucketImpl, BucketImpl& srcBucketImpl, const PathC& path);
    void addElementToTrackers(size_t elemIndex, BucketImpl& bucketImpl);
    void makeSrcValidIfDestValid(MirroredArray& srcArray,
                                 BucketImpl& srcBucketImpl,
                                 const ArrayOfArrayInfo& srcAoaInfo,
                                 const MirroredArray& destArray,
                                 const AttrName& name);
    void moveElementBetweenBuckets(const PathC& path, BucketId destBucketId, BucketId srcBucketId, const Bucket& destBucket);
    void moveElementScalarData(ScalarAttributeArray &destArray, const size_t destElemIndex, const ScalarAttributeArray &srcArray, const size_t srcElemIndex);
    void moveElementArrayData(ArrayAttributeArray &destArray, const size_t destElemIndex, const ArrayAttributeArray &srcArray, const size_t srcElemIndex);
    void moveElement(BucketImpl& destBucket, size_t destElemIndex, BucketImpl& srcBucket, size_t srcElemIndex);
    void destroyElement(BucketId bucketId, size_t elemIndex, bool destroyDataPointedTo);

    ArrayAndDirtyIndices getArraySpanC(BucketId bucketId, TokenC attrName, const IOConfig &io, NameSuffix suffix = NameSuffix::none);
    ArrayAndDirtyIndices getArraySpanC(MirroredArray& array, const AttrName& name, const ArrayOfArrayInfo& aoa, BucketImpl& bucketImpl, const IOConfig &io);
    void enableCpuReadImpl(MirroredArray& array,
        const size_t* elemToArraySize,
        MirroredArray* elemToArrayCpuCapacity,
        MirroredArray* elemToArrayGpuCapacity,
        MirroredArray* elemToArrayGpuData,
        bool printWarnings = true);
    void enableCpuRead(MirroredArray& array,
                       const size_t* elemToArraySize,
                       MirroredArray* elemToArrayCpuCapacity,
                       MirroredArray* elemToArrayGpuCapacity,
                       MirroredArray* elemToArrayGpuData);
    void enableCpuReadIfValid(MirroredArray& array,
        const size_t* elemToArraySize,
        MirroredArray* elemToArrayCpuCapacity,
        MirroredArray* elemToArrayGpuCapacity,
        MirroredArray* elemToArrayGpuData);
    void enableGpuRead(MirroredArray& array,
                       const size_t* elemToArraySize,
                       MirroredArray* elemToArrayCpuCapacity,
                       MirroredArray* elemToArrayGpuCapacity,
                       MirroredArray* elemToArrayGpuData);
    void enableGpuWrite(MirroredArray& array,
                        const size_t* elemToArraySize,
                        MirroredArray* elemToArrayCpuCapacity,
                        MirroredArray* elemToArrayGpuCapacity,
                        MirroredArray* elemToArrayGpuData);
    void enableD3dGpuRead(MirroredArray& array,
                          const size_t* elemToArraySize,
                          MirroredArray* elemToArrayCpuCapacity,
                          MirroredArray* elemToArrayGpuCapacity,
                          MirroredArray* gpuPointerArray);
    void enableD3dGpuWrite(MirroredArray& array,
                           const size_t* elemToArraySize,
                           MirroredArray* elemToArrayCpuCapacity,
                           MirroredArray* elemToArrayGpuCapacity,
                           MirroredArray* elemToArrayGpuData);

    static inline constexpr IOConfig CpuReadConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableCpuRead, // enableRead
            nullptr,                             // enableWrite
            nullptr,                             // enableRdPtrForWrite
            Device::eCPU,                        // device
            PtrToPtrKind::eNotApplicable         // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig CpuWriteConfig()
    {
        return IOConfig{
            nullptr,                              // enableRead
            &PathToAttributesMap::enableCpuWrite, // enableWrite
            &PathToAttributesMap::enableCpuRead,  // enableRdPtrForWrite
            Device::eCPU,                         // device
            PtrToPtrKind::eNotApplicable          // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig CpuReadWriteConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableCpuRead,  // enableRead
            &PathToAttributesMap::enableCpuWrite, // enableWrite
            &PathToAttributesMap::enableCpuRead,  // enableRdPtrForWrite
            Device::eCPU,                         // device
            PtrToPtrKind::eNotApplicable          // ptrToPtrKind
        };
    };

    // TODO: This probably needs to go away, it only exists to turn off "printWarnings"
    static inline constexpr IOConfig CpuReadIfValidWriteConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableCpuReadIfValid,  // enableRead
            &PathToAttributesMap::enableCpuWrite,        // enableWrite
            &PathToAttributesMap::enableCpuRead,         // enableRdPtrForWrite
            Device::eCPU,                                // device
            PtrToPtrKind::eNotApplicable                 // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig CudaReadConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableGpuRead, // enableRead
            nullptr,                             // enableWrite
            nullptr,                             // enableRdPtrForWrite
            Device::eCudaGPU,                    // device
            PtrToPtrKind::eNotApplicable         // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig CudaWriteConfig()
    {
        return IOConfig{
            nullptr,                              // enableRead
            &PathToAttributesMap::enableGpuWrite, // enableWrite
            &PathToAttributesMap::enableGpuRead,  // enableRdPtrForWrite
            Device::eCudaGPU,                     // device
            PtrToPtrKind::eNotApplicable          // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig CudaReadWriteConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableGpuRead,  // enableRead
            &PathToAttributesMap::enableGpuWrite, // enableWrite
            &PathToAttributesMap::enableGpuRead,  // enableRdPtrForWrite
            Device::eCudaGPU,                     // device
            PtrToPtrKind::eNotApplicable          // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig D3dVkReadConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableD3dGpuRead, // enableRead
            nullptr,                                // enableWrite
            nullptr,                                // enableRdPtrForWrite
            Device::eD3dVkGPU,                      // device
            PtrToPtrKind::eNotApplicable            // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig D3dVkWriteConfig()
    {
        return IOConfig{
            nullptr,                                 // enableRead
            &PathToAttributesMap::enableD3dGpuWrite, // enableWrite
            &PathToAttributesMap::enableD3dGpuRead,  // enableRdPtrForWrite
            Device::eD3dVkGPU,                       // device
            PtrToPtrKind::eNotApplicable             // ptrToPtrKind
        };
    };

    static inline constexpr IOConfig D3dVkReadWriteConfig()
    {
        return IOConfig{
            &PathToAttributesMap::enableD3dGpuRead,  // enableRead
            &PathToAttributesMap::enableD3dGpuWrite, // enableWrite
            &PathToAttributesMap::enableD3dGpuRead,  // enableRdPtrForWrite
            Device::eD3dVkGPU,                       // device
            PtrToPtrKind::eNotApplicable             // ptrToPtrKind
        };
    };

    std::tuple<bool, BucketId, size_t> getPresentAndBucketAndElement(const PathC& path) const;
    SpanC getArrayElementPtr(SpanC array, size_t bucketElement) const;
    ConstSpanC getArrayElementPtr(ConstSpanC array, size_t bucketElement) const;
    void destructiveResizeIfNecessary(uint8_t*& cpuData, size_t& capacity, size_t desiredElemCount, size_t elemByteCount);
    void destructiveResizeIfNecessaryGPU(MirroredArray& gpuPointerArray,
                                         size_t elem,
                                         size_t& capacity,
                                         size_t desiredElemCount,
                                         size_t elemByteCount,
                                         omni::gpucompute::GpuCompute* computeAPI,
                                         omni::gpucompute::Context* computeCtx);
    void resizeIfNecessary(uint8_t*& cpuData, size_t& capacity, size_t desiredElemCount, size_t elemByteCount, TypeC type);
    void resizeIfNecessaryGPU(MirroredArray& gpuPointerArray,
                              size_t elem,
                              size_t& capacity,
                              size_t desiredElemCount,
                              size_t elemByteCount,
                              omni::gpucompute::GpuCompute* computeAPI,
                              omni::gpucompute::Context* computeCtx);
    void allocGpuMemIfNecessary(PathToAttributesMap::MirroredArray& array,
                                size_t byteCount,
                                size_t elemSize,
                                omni::gpucompute::GpuCompute* computeAPI,
                                omni::gpucompute::Context* computeCtx);
    std::pair<BucketId, BucketImpl&> findOrCreateBucket(const Bucket& bucket);
    void eraseBucket(const Bucket& bucket);
    BucketId findBucketId(const Bucket& bucket);
    std::tuple<BucketId, ArrayIndex> getBucketAndArrayIndex(const PathC& path) const;
    std::tuple<BucketId, ArrayIndex> addAttributeGetBucketAndArrayIndex(
        const PathC& path, const TokenC& attrNameC, NameSuffix nameSuffix, TypeC type);
    void addAttributesToBucket(
        const PathC& path,
        const std::vector<TokenC>& attrNames,
        const std::vector<TypeC>& typeCs);

    void setArrayDirty(ArrayAndDirtyIndices& arrayAndDirtyIndices);
    void setArrayElementDirty(ArrayAndDirtyIndices& arrayAndDirtyIndices, size_t elemIndex);
    BucketImpl& addAttributeC(BucketImpl& bucketImpl,
                              const Bucket& bucket,
                              const TokenC& attrName,
                              TypeC ctype,
                              const void* value = nullptr);
    BucketImpl& addArrayAttributeC(BucketImpl& bucketImpl, const Bucket& bucket, const TokenC& attrName, TypeC ctype, const void* value, const size_t arrayElemCount);

    void checkInvariants();

    /**
     * @brief Internal debug function
     *
     * @details This loops over all the array attributes checking that the
     *          invariants hold true. Currently it just enforces
     *    (I1) If the size and cpu size match that the cpu array pointer isn't null
     *
     *
     * @return none
     */
    bool __validateArrayInvariants() const;
};

// PathToAttributesMap doesn't depend on USD for tokens or paths
// However, it's useful to be able to see the USD text representation of tokens and
// paths when debugging. Set ENABLE_USD_DEBUGGING to 1 to enable that.
// Then use toTfToken() to convert TokenC to pxr::TfToken
inline const pxr::TfToken& toTfToken(const TokenC& token)
{
    return reinterpret_cast<const pxr::TfToken&>(token);
}

inline const pxr::SdfPath& toSdfPath(const PathC& path)
{
    return reinterpret_cast<const pxr::SdfPath&>(path);
}

// Query result

struct View
{
    PathToAttributesMap* path2attrsMap;
    std::vector<Bucket> buckets;
    std::vector<size_t> bucketElemCounts;
};
using BucketImpl = PathToAttributesMap::BucketImpl;

// The rest of this file is methods


// Returns the number of Paths known to the cache

inline size_t PathToAttributesMap::size()
{
    return pathToBucketElem.size();
}

// Delete all data in the cache, meaning all the buckets and the map
// from paths to buckets.

inline void PathToAttributesMap::clear()
{
    buckets.clear();
    pathToBucketElem.clear();
    attrNameSetToBucketId.clear();
}

template<typename CallbackT>
inline void PathToAttributesMap::BucketIdToImpl::forEachValidBucket(CallbackT callback) const
{
    BucketId id{ 0 };
    for (size_t i = 0; i < buckets.size(); ++i, ++id)
    {
        if (buckets[i])
        {
            callback(id, *buckets[i]);
        }
    }
}

inline void PathToAttributesMap::printMirroredArray(const char* const label, const ScalarAttributeArray &array, const size_t* const arrayElemCount) const
{
    auto printValue = [](const uint8_t *const data, const size_t size)
    {
        if (!data)
        {
            printf("<nullptr>");
        }
        else
        {
            if (size <= sizeof(uint8_t))
            {
                printf("u8=%u, d8=%d, c=%c", *data, *(const int8_t*)data, *(const char*)data);
            }
            else if (size <= sizeof(uint16_t))
            {
                printf("u16=%u, d16=%d", *(const uint16_t*)data, *(const int16_t*)data);
            }
            else if (size <= sizeof(uint32_t))
            {
                printf("u32=%u, d32=%d, float=%f", *(const uint32_t*)data, *(const int32_t*)data, *(const float*)data);
            }
            else if (size <= sizeof(uint64_t))
            {
                printf("u64=%" PRIu64 ", d64=%" PRId64 ", double=%f, ptr=0x%p", *(const uint64_t*)data, *(const int64_t*)data, *(const double*)data, *(void**)data);
            }
            else
            {
                printf("\n");
                for (size_t i = 0; i < size; i += 16)
                {
                    printf("      %06zx: ", i);
                    for (size_t j = 0; j < 16; ++j)
                    {
                        if (i + j < size)
                        {
                            printf("%02x ", data[i + j]);
                        }
                        else
                        {
                            printf("   ");
                        }
                    }
                    printf(" ");
                    for (size_t j = 0; j < 16; j++)
                    {
                        if (i + j < size)
                        {
                            printf("%c", isprint(data[i + j]) ? data[i + j] : '.');
                        }
                    }
                    printf("\n");
                }
            }
        }
    };

    printf("  %s (type %d)[count %zu]:\n", label, array.type.type, array.count);

    const Typeinfo &typeinfo = array.typeinfo;
    const size_t elemSize = typeinfo.size;

    printf("    cpuValid=%d  0x%p\n", array.cpuValid, array.cpuData());
    if (array.cpuValid)
    {
        for (size_t elem = 0; elem < array.count; ++elem)
        {
            printf("      [%5zu]: ", elem);
            const uint8_t *const elemData = array.cpuData() + elem * elemSize;
            printf("0x%p ", elemData);
            if (arrayElemCount)
            {
                CARB_ASSERT(typeinfo.isArray);

                const uint8_t* const base = *((const uint8_t **)elemData);
                printf(" => 0x%p", base);

                for (size_t i = 0; i < arrayElemCount[elem]; ++i)
                {
                    printf("\n        [%5zu]: ", i);
                    const uint8_t* const arrayData = base ? base + i * typeinfo.arrayElemSize : nullptr;
                    printValue(arrayData, typeinfo.arrayElemSize);
                }
            }
            else
            {
                printValue(elemData, elemSize);
            }
            printf("\n");
        }
    }

    printf("    gpuValid=%d  0x%p\n", array.gpuValid, array.gpuArray);
    printf("    usdValid=%d\n", array.usdValid);
}

// Print the cache, specifically the Paths and the UsdAttributes they map to
// (but not the values of the attributes currently)

inline void PathToAttributesMap::print() const
{
    auto va = [](auto ...params) -> const char* {
        static char tmp[1024];
#ifdef _WIN32
        _snprintf_s(tmp, sizeof(tmp), params...);
#else
        snprintf(tmp, sizeof(tmp), params...);
#endif
        return (const char*)&tmp;
    };

    std::cout << "(== PathToAttributesMap::print() begin ==)\n";
    buckets.forEachValidBucket([this, va](const BucketId bucketId, const BucketImpl& bucketImpl) {
        printf("bucket [%zu]:\n", size_t(bucketId));
        if (!bucketImpl.elemToPath.size())
        {
            printf("  <no elements>\n");
        }
        else
        {
            for (size_t elem = 0; elem < bucketImpl.elemToPath.size(); ++elem)
            {
                printf("  elem [%5zu]: \"%s\"\n", elem, bucketImpl.elemToPath[elem].GetText());
            }
        }
        if (bucketImpl.scalarAttributeArrays.empty() && bucketImpl.arrayAttributeArrays.empty())
        {
            printf("  <no attributes>\n");
        }
        else
        {
            bucketImpl.scalarAttributeArrays.forEach([this, &va](const AttrName& name, const ScalarAttributeArray &array) {
                printMirroredArray(va("%s \"%s\"", "sattr", toTfToken(name.name).GetText()), array, nullptr);
            });
            bucketImpl.arrayAttributeArrays.forEach([this, &va](const AttrName& name, const ArrayAttributeArray &array) {
                printMirroredArray(va("%s \"%s\" %s", "vattr", toTfToken(name.name).GetText(), "values"), array.values, (const size_t*)array.cpuElemCounts.cpuData());
                printMirroredArray(va("%s \"%s\" %s", "vattr", toTfToken(name.name).GetText(), "elemCounts"), array.elemCounts, nullptr);
                printMirroredArray(va("%s \"%s\" %s", "vattr", toTfToken(name.name).GetText(), "cpuElemCounts"), array.cpuElemCounts, nullptr);
                printMirroredArray(va("%s \"%s\" %s", "vattr", toTfToken(name.name).GetText(), "gpuElemCounts"), array.gpuElemCounts, nullptr);
                printMirroredArray(va("%s \"%s\" %s", "vattr", toTfToken(name.name).GetText(), "gpuPtrs"), array.gpuPtrs, nullptr);
            });
        }
    });

    std::cout << "(== PathToAttributesMap::print() end ==)\n\n";
}

#define ENABLE_LOG 0
inline void log(const char* format, ...)
{
#if ENABLE_LOG
    va_list args;
    va_start(args, format);
    vprintf(format, args);
    va_end(args);
#endif
}

inline void PathToAttributesMap::addType(TypeC type, Typeinfo typeInfo)
{
    Typeinfo *v;
    typeToInfo.allocateEntry(type, &v);
    *v = typeInfo;
}

inline Typeinfo PathToAttributesMap::getTypeInfo(TypeC type) const
{
    const Typeinfo* typeinfo;
    if (typeToInfo.find(type, &typeinfo))
    {
        return *typeinfo;
    }
    else
    {
        return Typeinfo();
    }
}

inline BucketId PathToAttributesMap::addBucket(const Bucket& bucket)
{
    auto iter = attrNameSetToBucketId.find(bucket);
    bool found = (iter != attrNameSetToBucketId.end());

    if (!found)
    {
        // Create bucket
        auto bucketIdAndImpl = buckets.emplace(platform.allocator.new_<BucketImpl>(platform));
        auto bucketAndId = attrNameSetToBucketId.emplace(bucket, bucketIdAndImpl.first);

        const Bucket& addedBucket = bucketAndId.first->first;
        BucketImpl& bucketImpl = bucketIdAndImpl.second;
        bucketImpl.SetBucket(bucket);

        // Make array for each type
        for (const AttrNameAndType& b : addedBucket)
        {
            const Type attrType = b.type;
            const Token& attrName = b.name;
            const NameSuffix& suffix = b.suffix;

            const TypeC attrTypeC = TypeC(attrType);

            const Typeinfo* typeinfo;
            if (typeToInfo.find(attrTypeC, &typeinfo))
            {
                AttrName name{ attrName, suffix };

                if (typeinfo->isArray)
                {
                    ArrayAttributeArray* ptr;
                    bucketImpl.arrayAttributeArrays.allocateEntry(std::move(name), &ptr);
                    new (ptr) ArrayAttributeArray(platform, attrTypeC, *typeinfo);
                }
                else
                {
                    ScalarAttributeArray* ptr;
                    bucketImpl.scalarAttributeArrays.allocateEntry(std::move(name), &ptr);
                    new (ptr) ScalarAttributeArray(platform, attrTypeC, *typeinfo);
                }
            }
            else
            {
                std::cout << "Error: Typeinfo for " << attrType << " not found. Please add it using addType()." << std::endl;
            }
        }
        return bucketIdAndImpl.first;
    }
    else
    {
        return iter->second;
    }
}

// Multiple attribute methods
inline void PathToAttributesMap::getAttributesRdC(const void** attrsOut,
                                                  const PathC* paths,
                                                  const TokenC* attrNames,
                                                  size_t attrCount)
{
    // TODO: make optimized version instead of calling getAttributeRdC
    for (size_t i = 0; i != attrCount; i++)
    {
        attrsOut[i] = getAttributeRdC(paths[i], attrNames[i]).ptr;
    }
}

inline void PathToAttributesMap::getAttributesRdGpuC(const void** attrsOut,
                                                     const PathC* paths,
                                                     const TokenC* attrNames,
                                                     size_t attrCount,
                                                     PtrToPtrKind ptrToPtrKind)
{
    // TODO: make optimized version instead of calling getAttributeRdGpuC
    for (size_t i = 0; i != attrCount; i++)
    {
        attrsOut[i] = getAttributeRdGpuC(paths[i], attrNames[i], ptrToPtrKind).ptr;
    }
}

inline void PathToAttributesMap::getArraysRdC(const void** attrsOut,
                                              const Bucket& bucket,
                                              const TokenC* attrNames,
                                              size_t attrCount)
{
    // TODO: make optimized version instead of calling getArrayRdC
    for (size_t i = 0; i != attrCount; i++)
    {
        attrsOut[i] = getArrayRdC(bucket, attrNames[i]);
    }
}

inline void PathToAttributesMap::getAttributesWrC(void** attrsOut,
                                                  const PathC& path,
                                                  const TokenC* attrNames,
                                                  size_t attrCount)
{
    // TODO: make optimized version instead of calling getAttributeWrC
    for (size_t i = 0; i != attrCount; i++)
    {
        attrsOut[i] = getAttributeWrC(path, attrNames[i]).ptr;
    }
}

inline void PathToAttributesMap::getAttributesWrGpuC(void** attrsOut,
                                                     const PathC& path,
                                                     const TokenC* attrNames,
                                                     size_t attrCount,
                                                     PtrToPtrKind ptrToPtrKind)
{
    // TODO: make optimized version instead of calling getAttributeWrGpuC
    for (size_t i = 0; i != attrCount; i++)
    {
        attrsOut[i] = getAttributeWrGpuC(path, attrNames[i], ptrToPtrKind).ptr;
    }
}

inline void PathToAttributesMap::getArraysWrC(void** attrsOut, const Bucket& bucket, const TokenC* attrNames, size_t attrCount)
{
    // TODO: make optimized version instead of calling getArrayWrC
    for (size_t i = 0; i != attrCount; i++)
    {
        attrsOut[i] = getArrayWrC(bucket, attrNames[i]);
    }
}

// Algorithm:
// Check whether bucket already has a bucketId
// If it does:
//   Check whether bucketId has a bucketImpl
//   If it does:
//     return (bucketId, bucketImpl)
//   Else:
//     Print error message
//     return (bucketId, empty bucketImpl)
// Else:
//    Allocate a bucketId
//    attrNameSetToBucketId += (bucket->bucketId)
//    buckets += (bucketId->empty bucketImpl)
//
inline std::pair<BucketId, BucketImpl&> PathToAttributesMap::findOrCreateBucket(const Bucket& bucket)
{
    auto iter = attrNameSetToBucketId.find(bucket);
    bool foundBucketAndId = (iter != attrNameSetToBucketId.end());

    BucketId bucketId;
    if (foundBucketAndId)
    {
        bucketId = iter->second;
        auto implPtr = buckets.find(bucketId);
        if (implPtr)
        {
            return { bucketId, *implPtr };
        }
        else
        {
            // This is an error, but make an impl so that we can return gracefully
            CARB_LOG_ERROR("BucketId->impl not found");

            // Allocate an impl and id->impl mapping and then set the
            // attrNameSetToBucketId to the slot of the new impl
            auto idAndImpl = buckets.emplace(platform.allocator.new_<BucketImpl>(platform));
            iter->second = idAndImpl.first;
            idAndImpl.second.SetBucket(bucket);

            return idAndImpl;
        }
    }

    // Allocate an impl and place in vector
    auto idAndImpl = buckets.emplace(platform.allocator.new_<BucketImpl>(platform));
    // Store bucket->Id mapping
    attrNameSetToBucketId.emplace(bucket, idAndImpl.first);
    idAndImpl.second.SetBucket(bucket);

    return idAndImpl;
}

inline void PathToAttributesMap::eraseBucket(const Bucket& bucket)
{
    auto iter = attrNameSetToBucketId.find(bucket);
    bool foundBucketAndId = (iter != attrNameSetToBucketId.end());

    BucketId bucketId;
    if (foundBucketAndId)
    {
        bucketId = iter->second;
        auto implPtr = buckets.find(bucketId);
        if (implPtr)
        {
            buckets.erase(bucketId);
        }
        else
        {
            CARB_LOG_ERROR("BucketId->impl not found");
        }

        attrNameSetToBucketId.erase(bucket);
    }
    else
    {
        // Nothing to do
    }
}

// Add an attribute to all elements of a bucket
// Note that this might cause a merge with an existing bucket
//
// Here are the maps we have to update:
// pathToBucketElem :: path -> (bucketId, arrayIndex)
// buckets :: bucketId -> bucketImpl
// attrNameSetToBucketId :: bucket-> bucketId
//
inline BucketImpl& PathToAttributesMap::addAttributeC(BucketImpl& bucketImpl,
                                                      const Bucket& bucket,
                                                      const TokenC& attrName,
                                                      TypeC ctype,
                                                      const void* value)
{
    // TODO: should we warn on missing type?
    const Typeinfo& typeinfo = getTypeInfo(ctype);
    if (typeinfo.isArray && value)
    {
        CARB_LOG_ERROR("addAttributeC: Attempted to add array-value attribute with default values. Use addArrayAttribute instead.");
        return bucketImpl;
    }

    return addAttributeInternal(bucketImpl, bucket, attrName, ctype, value, typeinfo, 0);
}


inline BucketImpl& PathToAttributesMap::addArrayAttributeC(BucketImpl& bucketImpl, const Bucket& bucket, const TokenC& attrName, TypeC ctype, const void* value, const size_t arrayElemCount)
{
    CARB_ASSERT(!arrayElemCount || value);
    // TODO: should we warn on missing type?
    const Typeinfo& typeinfo = getTypeInfo(ctype);
    return addAttributeInternal(bucketImpl, bucket, attrName, ctype, value, typeinfo, arrayElemCount);

}


// Add an attribute to all elements of a bucket
inline void PathToAttributesMap::addAttributeC(
    const Bucket& bucket, const TokenC& attrName, TypeC ctype, const void* value)
{
    const auto iter = attrNameSetToBucketId.find(bucket);
    if (iter != attrNameSetToBucketId.end())
    {
        const BucketId bucketId = iter->second;
        BucketImpl *const implPtr = buckets.find(bucketId);
        if (implPtr)
        {
            // TODO: should we warn on missing type?
            const Typeinfo& typeinfo = getTypeInfo(ctype);
            if (typeinfo.isArray && value)
            {
                CARB_LOG_ERROR("addAttributeC: Attempted to add array-value attribute with default values. Use addArrayAttribute instead.");
                return;
            }
            addAttributeInternal(*implPtr, bucket, attrName, ctype, value, typeinfo, 0);
        }
    }
}

inline void PathToAttributesMap::addArrayAttributeC(const Bucket& bucket, const TokenC& attrName, TypeC ctype, const void* value, const size_t arrayElemCount)
{
    CARB_ASSERT(!arrayElemCount || value);

    const auto iter = attrNameSetToBucketId.find(bucket);
    if (iter != attrNameSetToBucketId.end())
    {
        const BucketId bucketId = iter->second;
        BucketImpl *const implPtr = buckets.find(bucketId);
        if (implPtr)
        {
            // TODO: should we warn on missing type?
            const Typeinfo& typeinfo = getTypeInfo(ctype);
            addAttributeInternal(*implPtr, bucket, attrName, ctype, value, typeinfo, arrayElemCount);
        }
    }
}

template <typename T>
void PathToAttributesMap::addAttribute(
    const Bucket& bucket, const TokenC& attrName, TypeC type, const T& value)
{
    APILOGGER("addAttribute", apiLogEnabled, attrName);

    // TODO: check that type is compatible
    return addAttributeC(bucket, attrName, type, &value);
}

inline size_t PathToAttributesMap::getElementCount(const BucketImpl& bucketImpl) const
{
    return bucketImpl.elemToPath.size();
}

inline size_t PathToAttributesMap::getElementCount(BucketId bucketId) const
{
    const auto implPtr = buckets.find(bucketId);
    if (implPtr)
    {
        return implPtr->elemToPath.size();
    }
    return 0;
}

inline size_t PathToAttributesMap::getElementCount(const Bucket& bucket) const
{
    const auto iter = attrNameSetToBucketId.find(bucket);
    if (iter != attrNameSetToBucketId.end())
    {
        BucketId bucketId = iter->second;
        return getElementCount(bucketId);
    }
    return 0;
}

inline PathToAttributesMap::ArrayOfArrayInfo PathToAttributesMap::getArrayOfArrayInfo(Typeinfo typeInfo,
                                                                                      BucketImpl& bucketImpl,
                                                                                      TokenC attrName)
{
    if (typeInfo.isArray)
    {
        ArrayAttributeArray *array;
        if (bucketImpl.arrayAttributeArrays.find(AttrName{ attrName, NameSuffix::none }, &array))
        {
            return getArrayOfArrayInfo(*array);
        }
    }

    return { nullptr, nullptr, nullptr, nullptr };
}

inline PathToAttributesMap::ArrayOfArrayInfo PathToAttributesMap::getArrayOfArrayInfo(ArrayAttributeArray &arrayAttributeArray)
{
    MirroredArray *const arraySizeArray = &arrayAttributeArray.elemCounts;
    MirroredArray *const arrayCpuCapacityArray = &arrayAttributeArray.cpuElemCounts;
    MirroredArray *const arrayGpuCapacityArray = &arrayAttributeArray.gpuElemCounts;
    MirroredArray *const arrayGpuPtrArray = &arrayAttributeArray.gpuPtrs;

    return { (size_t*)arraySizeArray->cpuData(), arrayCpuCapacityArray, arrayGpuCapacityArray, arrayGpuPtrArray };
}

inline PathToAttributesMap::ConstArrayOfArrayInfo PathToAttributesMap::getArrayOfArrayInfo(Typeinfo typeInfo,
                                                                                      const BucketImpl& bucketImpl,
                                                                                      TokenC attrName) const
{
    if (typeInfo.isArray)
    {
        const ArrayAttributeArray *array;
        if (bucketImpl.arrayAttributeArrays.find(AttrName{ attrName, NameSuffix::none }, &array))
        {
            return getArrayOfArrayInfo(*array);
        }
    }

    return { nullptr, nullptr, nullptr, nullptr };
}

inline PathToAttributesMap::ConstArrayOfArrayInfo PathToAttributesMap::getArrayOfArrayInfo(const ArrayAttributeArray &arrayAttributeArray) const
{
    const MirroredArray *const arraySizeArray = &arrayAttributeArray.elemCounts;
    const MirroredArray *const arrayCpuCapacityArray = &arrayAttributeArray.cpuElemCounts;
    const MirroredArray *const arrayGpuCapacityArray = &arrayAttributeArray.gpuElemCounts;
    const MirroredArray *const arrayGpuPtrArray = &arrayAttributeArray.gpuPtrs;

    return { arraySizeArray, arrayCpuCapacityArray, arrayGpuCapacityArray, arrayGpuPtrArray };
}



inline std::vector<size_t> PathToAttributesMap::getElementCounts(const std::vector<Bucket>& buckets) const
{
    size_t bucketCount = buckets.size();
    std::vector<size_t> retval(bucketCount);
    for (size_t i = 0; i != bucketCount; i++)
    {
        retval[i] = getElementCount(buckets[i]);
    }
    return retval;
}

inline void PathToAttributesMap::addElementToTrackers(size_t elemIndex, BucketImpl& bucketImpl)
{
    // Update change trackers
    // We allocate them lazily, so we have to iterate over listenerIdToChangeTrackerConfig
    // then allocate bucketImpl.listenerIdToChanges if necessary
    listenerIdToChangeTrackerConfig.forEach([this, &bucketImpl, &elemIndex](ListenerId& listenerId, ChangeTrackerConfig& config) {
        if (config.changeTrackingEnabled)
        {
            // Allocate changes if necessary
            Changes* changes;
            if (bucketImpl.listenerIdToChanges.allocateEntry(listenerId, &changes))
            {
                new (changes) Changes();
            }
            changes->addNewPrim(elemIndex);
        }
    });
}

inline void PathToAttributesMap::allocElement(ScalarAttributeArray &scalar)
{
    const size_t allocSize = scalar.typeinfo.size;
    const size_t newSize = scalar.size() + allocSize;
    scalar.resize(newSize);

    // Only resize GPU mirror if it was previously allocated
    if (scalar.gpuCapacity != 0)
    {
        scalar.resizeGpu(platform.gpuCuda, platform.gpuCudaCtx, newSize, allocSize);
    }

    scalar.count++;
}

inline void PathToAttributesMap::allocElement(ArrayAttributeArray &arrayAttributeArray)
{
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
    allocElement(arrayAttributeArray.values);
    allocElement(arrayAttributeArray.elemCounts);
    allocElement(arrayAttributeArray.cpuElemCounts);
    allocElement(arrayAttributeArray.gpuElemCounts);
    allocElement(arrayAttributeArray.gpuPtrs);

    // For array-valued attributes, initialize CPU and GPU element counts
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
    reinterpret_cast<size_t*>(arrayAttributeArray.elemCounts.cpuData())[arrayAttributeArray.elemCounts.count-1] = 0;
    arrayAttributeArray.elemCounts.cpuValid = true;
    reinterpret_cast<size_t*>(arrayAttributeArray.cpuElemCounts.cpuData())[arrayAttributeArray.cpuElemCounts.count - 1] = 0;
    arrayAttributeArray.cpuElemCounts.cpuValid = true;
    reinterpret_cast<size_t*>(arrayAttributeArray.gpuElemCounts.cpuData())[arrayAttributeArray.gpuElemCounts.count - 1] = 0;
    arrayAttributeArray.gpuElemCounts.cpuValid = true;
}

inline size_t PathToAttributesMap::allocElement(BucketImpl& bucketImpl)
{
    // I moved this here to support old-style ArrayBase::resize
    // TODO: Now that ArrayBase is gone, check whether we can move it back
    const size_t element = bucketImpl.elemToPath.size();
    bucketImpl.elemToPath.emplace_back(); // Allocate an empty path, it gets set later

    bucketImpl.scalarAttributeArrays.forEach([this, &bucketImpl](const AttrName& name, ScalarAttributeArray &array) {
        allocElement(array);
        CARB_UNUSED(bucketImpl);
        CARB_ASSERT(array.count == bucketImpl.elemToPath.size());
    });

    bucketImpl.arrayAttributeArrays.forEach([this, &bucketImpl](const AttrName& name, ArrayAttributeArray &array) {
        allocElement(array);
        CARB_UNUSED(bucketImpl);
        CARB_ASSERT(array.values.count == bucketImpl.elemToPath.size());
        CARB_ASSERT(array.elemCounts.count == bucketImpl.elemToPath.size());
        CARB_ASSERT(array.cpuElemCounts.count == bucketImpl.elemToPath.size());
        CARB_ASSERT(array.gpuElemCounts.count == bucketImpl.elemToPath.size());
        CARB_ASSERT(array.gpuPtrs.count == bucketImpl.elemToPath.size());
    });

    addElementToTrackers(element, bucketImpl);

    return element;
}

// CPU and GPU valid bits are per SoA array, not per-prim per-attribute.
// Suppose we have a prim with attr whose GPU mirror is not valid, and we want
// to add it to a bucket that has a valid GPU mirror of that attribute. What
// should we set the bucket array's gpuValid to after the add?
//
// Option 1: set bucket's gpuValid to false.
// If cpuValid were true for the bucket, then this would be inefficient but
// correct. But, if cpuValid were false, then we'd have to copy all the bucket's
// data from GPU to CPU to avoid invalidating the only valid copy of the data.
// That would be very inefficient for a bucket with a lot of prims, or an
// array of array-valued attributes.
//
// Option 2: set bucket's gpuValid to true.
// For the bucket plus our new element to be gpuValid, we need to make the new
// element gpuValid by copying it from CPU to GPU.
//
// We've chosen Option 2 as it is the most efficient and makeSrcValidIfDestValid
// implements it.
// The explanation above was for GPU mirrors, but it applies equally to CPU.
//
// We are changing the srcArray mirrors to match destArray, so
// counterintuitively destArray is const and srcArray is not.
inline void PathToAttributesMap::makeSrcValidIfDestValid(MirroredArray& srcArray,
                                                         BucketImpl& srcBucketImpl,
                                                         const ArrayOfArrayInfo& srcAoaInfo,
                                                         const MirroredArray& destArray,
                                                         const AttrName& name)
{
    bool srcCpuValid = srcArray.cpuValid;
    bool srcGpuValid = srcArray.gpuValid;
    bool destCpuValid = destArray.cpuValid;
    bool destGpuValid = destArray.gpuValid;
    if (srcCpuValid && !srcGpuValid && destGpuValid)
    {
        // Possible states:
        // srcCpu srcGpu destCpu destGpu
        //      1      0       0       1
        //      1      0       1       1

        // With a valid CPU source, this will copy data to the GPU to make it valid
        // We don't set dirty indices here because this method gives read-only access
        getArraySpanC(srcArray, name, srcAoaInfo, srcBucketImpl, CudaReadConfig());

        // srcCpu srcGpu destCpu destGpu
        //      1      1       0       1
        //      1      1       1       1
    }
    else if (!srcCpuValid && !srcGpuValid && !destCpuValid && destGpuValid)
    {
        // srcCpu srcGpu destCpu destGpu
        //      0      0       0       1

        // Without a valid CPU source, just allocate memory so it can be "valid" even if not initialized
        getArraySpanC(srcArray, name, srcAoaInfo, srcBucketImpl, CudaWriteConfig());

        // srcCpu srcGpu destCpu destGpu
        //      0      1       0       1
    }
    else if (!srcCpuValid && srcGpuValid && destCpuValid)
    {
        // srcCpu srcGpu destCpu destGpu
        //      0      1       1       0
        //      0      1       1       1

        // With a valid GPU source, this will copy data back to the CPU to make it valid
        // We don't set dirty indices here because this method gives read-only access
        getArraySpanC(srcArray, name, srcAoaInfo, srcBucketImpl, CpuReadConfig());

        // srcCpu srcGpu destCpu destGpu
        //      1      1       1       0
        //      1      1       1       1
    }
    else if (!srcCpuValid && !srcGpuValid && destCpuValid && !destGpuValid)
    {
        // srcCpu srcGpu destCpu destGpu
        //      0      0       1       0

        // Without a valid GPU source, just allocate memory so it can be "valid" even if not initialized
        getArraySpanC(srcArray, name, srcAoaInfo, srcBucketImpl, CpuWriteConfig());

        // srcCpu srcGpu destCpu destGpu
        //      1      0       1       0
    }
    else if (!srcCpuValid && !srcGpuValid && destCpuValid && destGpuValid)
    {
        // srcCpu srcGpu destCpu destGpu
        //      0      0       1       1

        // Without a valid GPU source, just allocate memory so it can be "valid" even if not initialized
        getArraySpanC(srcArray, name, srcAoaInfo, srcBucketImpl, CudaWriteConfig());

        // srcCpu srcGpu destCpu destGpu
        //      0      1       1       1

        // This one clears gpuValid, because we assume that the user is going to write to it
        // But, we're not passing the allocated pointer to the user so...
        getArraySpanC(srcArray, name, srcAoaInfo, srcBucketImpl, CpuWriteConfig());

        // srcCpu srcGpu destCpu destGpu
        //      1      0       1       1

        // ..we can safely set gpuValid to true
        srcArray.gpuValid = true;

        // srcCpu srcGpu destCpu destGpu
        //      1      1       1       1
    }
}

inline void PathToAttributesMap::allocElementForMove(BucketImpl& srcBucketImpl, const ArrayOfArrayInfo &srcAoaInfo, const AttrName& name, MirroredArray &destArray, MirroredArray *const srcArray)
{
    bool srcGpuAlloced = false;
    if (srcArray)
    {
        makeSrcValidIfDestValid(*srcArray, srcBucketImpl, srcAoaInfo, destArray, name);
        srcGpuAlloced = (srcArray->gpuCapacity != 0);
    }

    if (srcArray)
    {
        if (destArray.type != srcArray->type)
        {
            if (destArray.typeinfo.size != srcArray->typeinfo.size)
            {
                CARB_LOG_ERROR_ONCE("PathToAttributesMap (%p) contains attributes with duplicate name \"%s\" with different types and different per-element sizes (%zu vs %zu). Data will almost certainly become corrupted during request to move elements between buckets!", this, toTfToken(name.name).GetString().c_str(), destArray.typeinfo.size, srcArray->typeinfo.size);
            }
            else
            {
                CARB_LOG_WARN_ONCE("PathToAttributesMap (%p) contains attributes with duplicate name \"%s\" with different types but same per-element size. Data may become corrupted during request to move elements between buckets!", this, toTfToken(name.name).GetString().c_str());
            }
        }
    }

    const size_t allocSize = destArray.typeinfo.size;
    const size_t newSize = destArray.size() + allocSize;
    destArray.resize(newSize);

    const bool destGpuAlloced = (destArray.gpuCapacity != 0);
    if (srcGpuAlloced || destGpuAlloced)
    {
        destArray.resizeGpu(platform.gpuCuda, platform.gpuCudaCtx, destArray.size(), destArray.typeinfo.size);
    }

    destArray.count++;
}

// When moving elements between buckets we want to only allocate GPU storage if
// the source had a valid GPU mirror.
inline size_t PathToAttributesMap::allocElementForMove(BucketImpl& destBucketImpl,
    BucketImpl& srcBucketImpl,
    const PathC& path)
{
    const size_t element = destBucketImpl.elemToPath.size();
    destBucketImpl.elemToPath.emplace_back(); // Allocate an empty path, it gets set later

    // Only allocate dest GPU mirror if src has GPU mirror
    destBucketImpl.scalarAttributeArrays.forEach([this, &srcBucketImpl](const AttrName& name, ScalarAttributeArray &array) {
        ScalarAttributeArray *srcArray = srcBucketImpl.scalarAttributeArrays.find(name, &srcArray) ? srcArray : nullptr;

        const ArrayOfArrayInfo aoa = ScalarArrayOfArrayInfo();
        allocElementForMove(srcBucketImpl, aoa, name, array, srcArray);
    });

    destBucketImpl.arrayAttributeArrays.forEach([this, &srcBucketImpl](const AttrName& name, ArrayAttributeArray &array) {
        ArrayAttributeArray *srcArray = srcBucketImpl.arrayAttributeArrays.find(name, &srcArray) ? srcArray : nullptr;

        static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
        const ArrayOfArrayInfo aoa = srcArray ? getArrayOfArrayInfo(*srcArray) : ScalarArrayOfArrayInfo();
        allocElementForMove(srcBucketImpl, aoa, name, array.values, srcArray ? &srcArray->values : nullptr);
        allocElementForMove(srcBucketImpl, aoa, name, array.elemCounts, srcArray ? &srcArray->elemCounts : nullptr);
        allocElementForMove(srcBucketImpl, aoa, name, array.cpuElemCounts, srcArray ? &srcArray->cpuElemCounts : nullptr);
        allocElementForMove(srcBucketImpl, aoa, name, array.gpuElemCounts, srcArray ? &srcArray->gpuElemCounts : nullptr);
        allocElementForMove(srcBucketImpl, aoa, name, array.gpuPtrs, srcArray ? &srcArray->gpuPtrs : nullptr);

        // For array-valued attributes, initialize CPU and GPU element counts
        static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
        reinterpret_cast<size_t*>(array.elemCounts.cpuData())[array.elemCounts.count - 1] = 0;
        array.elemCounts.cpuValid = true;
        reinterpret_cast<size_t*>(array.cpuElemCounts.cpuData())[array.cpuElemCounts.count - 1] = 0;
        array.cpuElemCounts.cpuValid = true;
        reinterpret_cast<size_t*>(array.gpuElemCounts.cpuData())[array.gpuElemCounts.count - 1] = 0;
        array.gpuElemCounts.cpuValid = true;
    });

    addElementToTrackers(element, destBucketImpl);

    return element;
}

// Array resize that does not preserve previous data
inline void PathToAttributesMap::destructiveResizeIfNecessary(uint8_t*& cpuData,
                                                              size_t& capacity,
                                                              size_t desiredElemCount,
                                                              size_t elemByteCount)
{
    // Resize iff (capacity < desiredElemCount)
    if (capacity != desiredElemCount)
    {
        size_t byteCount = desiredElemCount * elemByteCount;

        if (!USE_PINNED_MEMORY || !platform.gpuCuda)
        {
            free(cpuData);
            cpuData = reinterpret_cast<uint8_t*>(malloc(byteCount));
        }
        else if (platform.gpuCuda)
        {
            // Use page-locked memory CPU for CUDA
            platform.gpuCuda->freeHost(*platform.gpuCudaCtx, cpuData);
            platform.gpuCuda->hostAlloc(*platform.gpuCudaCtx, (void**)&cpuData, byteCount);
        }

        capacity = desiredElemCount;
    }
}

// Flatcache only stores POD types, with the following exceptions:
// eToken (pxr::TfToken)
// eAsset (std::array<pxr::TfToken, 2>)
//
// The following code constructs an array of objects of one of these types,
// filling memory[newCpuData + oldByteCount .. newCpuData + newByteCount)
// It is called when enlarging arrays of such types
template <typename T>
void constructInPlace(uint8_t* newCpuData, size_t oldByteCount, size_t newByteCount)
{
    T* begin = reinterpret_cast<T*>(newCpuData + oldByteCount);
    T* end = reinterpret_cast<T*>(newCpuData + newByteCount);
    for (T* current = begin; current != end; current++)
    {
        new (current) T;
    }
}

// We plan to move TfToken and AssetPath construction to IToken.
// Until we do we have to declare this here and depend on USD headers.
struct AssetPath
{
    pxr::TfToken assetPath;
    pxr::TfToken resolvedPath;
};

inline bool PathToAttributesMap::__validateArrayInvariants() const
{
    bool encounteredFailure = false;
    // loop over the buckets
    BucketId id{ 0 };
    for (unsigned int i = 0; i < this->buckets.end(); ++i, ++id)
    {
        const auto bucketImplPtr = buckets.find(id);
        if (!bucketImplPtr)
            continue;
        const auto& bucketImpl = *bucketImplPtr;

        if (bucketImpl.elemToPath.size() == 0)
            continue;
        //loop over all the arrays
        bucketImpl.arrayAttributeArrays.forEach([&encounteredFailure](const AttrName& name, const ArrayAttributeArray& local_array) {
            const Typeinfo& typeInfo = local_array.values.typeinfo;
            const size_t elemSize = typeInfo.size;

            // only care about actual data
            if (name.suffix != NameSuffix::none)
                return;

            // look up array info
            const MirroredArray* arraySizeArray = &local_array.elemCounts;
            const MirroredArray* arrayCpuCapacityArray = &local_array.cpuElemCounts;

            // skip tags and not arrays
            if (elemSize != 0)
            {
                //number of elements
                const size_t elemCount = local_array.values.count;

                // pointers to data
                const uint8_t* const* elemToArrayCpuData = reinterpret_cast<const uint8_t* const*>(local_array.values.cpuData());

                for (size_t elem = 0; elem != elemCount; elem++)
                {
                    // get the actual pointer
                    const uint8_t* cpuData = elemToArrayCpuData[elem];
                    // look up the cpu capacity
                    const size_t& cpuCapacity = reinterpret_cast<const size_t*>(arraySizeArray->cpuData())[elem];
                    const size_t& desiredElemCount = reinterpret_cast<const size_t*>(arrayCpuCapacityArray->cpuData())[elem];
                    if (cpuCapacity == desiredElemCount)
                    {
                        // we should have valid data
                        if (cpuCapacity != 0 && !cpuData) {
                            std::cout << "Invalid array name = " << toTfToken(name.name).GetString() << std::endl;
                            encounteredFailure = true;
                        }
                    }
                }
            }
        });
    }
    return encounteredFailure;
}


// Array resize that preserves previous data
inline void PathToAttributesMap::resizeIfNecessary(
    uint8_t*& cpuData, size_t& capacity, size_t desiredElemCount, size_t elemByteCount, TypeC typeC)
{
    // TODO: reduce number of reallocations by allocating capacity larger than size
    // and not always reallocating when desiredElemCount<capacity
    if (capacity < desiredElemCount)
    {
        size_t oldByteCount = capacity * elemByteCount;
        size_t newByteCount = desiredElemCount * elemByteCount;

        uint8_t* newCpuData = nullptr;
        if (!USE_PINNED_MEMORY || !platform.gpuCuda)
        {
            newCpuData = reinterpret_cast<uint8_t*>(malloc(newByteCount));
        }
        else if (platform.gpuCuda)
        {
            platform.gpuCuda->hostAlloc(*platform.gpuCudaCtx, reinterpret_cast<void**>(&newCpuData), newByteCount);
        }

        if (cpuData)
        {
            size_t copyByteCount = std::min(oldByteCount, newByteCount);
            memcpy(newCpuData, cpuData, copyByteCount);

            if (!USE_PINNED_MEMORY || !platform.gpuCuda)
            {
                free(cpuData);
            }
            else if (platform.gpuCuda)
            {
                platform.gpuCuda->freeHost(*platform.gpuCudaCtx, cpuData);
            }
        }

        // If type has a constructor, construct any new elements
        if (oldByteCount < newByteCount)
        {
            Type type(typeC);
            const uint8_t kScalar = 1;
            const uint8_t kArray = 1;
            if (type == Type(BaseDataType::eToken, kScalar, kArray))
            {
                constructInPlace<pxr::TfToken>(newCpuData, oldByteCount, newByteCount);
            }
            else if (type == Type(BaseDataType::eAsset, kScalar, kArray))
            {
                constructInPlace<flatcache::AssetPath>(newCpuData, oldByteCount, newByteCount);
            }
            else if (type == Type(BaseDataType::eConnection, kScalar, kArray))
            {
                constructInPlace<flatcache::Connection>(newCpuData, oldByteCount, newByteCount);
            }
        }

        cpuData = newCpuData;

        capacity = desiredElemCount;
    }
}

inline void PathToAttributesMap::enableCpuReadImpl(PathToAttributesMap::MirroredArray& array,
                                                   const size_t* elemToArraySize,
                                                   PathToAttributesMap::MirroredArray* elemToArrayCpuCapacity,
                                                   PathToAttributesMap::MirroredArray* elemToArrayGpuCapacity,
                                                   PathToAttributesMap::MirroredArray* gpuArrayDataArray,
                                                   bool printWarnings)
{
    using omni::gpucompute::MemcpyKind;

    bool& usdValid = array.usdValid;
    bool& cpuValid = array.cpuValid;
    bool& gpuValid = array.gpuValid;
    bool& usingCuda = array.gpuAllocedWithCuda;
    uint8_t* cpuArray = array.cpuData();
    uint8_t*& gpuArray = array.gpuArray;

    // If CPU copy is valid, nothing to do
    // If GPU copy is valid, copy to CPU
    // If USD copy is valid, copy to CPU
    if (cpuValid)
    {
        // Nothing to do
    }
    else if (!cpuValid && gpuValid)
    {
        size_t byteCount = array.size();

        // Select which API to use
        omni::gpucompute::GpuCompute* computeAPI = nullptr;
        omni::gpucompute::Context* computeCtx = nullptr;
        if (usingCuda)
        {
            computeAPI = platform.gpuCuda;
            computeCtx = platform.gpuCudaCtx;
        }
        else if (!usingCuda)
        {
            computeAPI = platform.gpuD3dVk;
            computeCtx = platform.gpuD3dVkCtx;
        }

        const Typeinfo &typeinfo = array.typeinfo;

        std::lock_guard<MirroredArray::AttributeMutex> hostDeviceLock(array.attributeMutex);
        if (typeinfo.isArray)
        {
            size_t elemCount = array.count;
            uint8_t** elemToArrayCpuData = reinterpret_cast<uint8_t**>(cpuArray);
            uint8_t** elemToArrayGpuData = reinterpret_cast<uint8_t**>(gpuArrayDataArray->cpuData());

            for (size_t elem = 0; elem != elemCount; elem++)
            {
                // Make sure that the dest (CPU) buffer is large enough
                uint8_t*& cpuData = elemToArrayCpuData[elem]; // dest
                const uint8_t* const& gpuData = elemToArrayGpuData[elem]; // src
                size_t& destCapacity = reinterpret_cast<size_t*>(elemToArrayCpuCapacity->cpuData())[elem];
                size_t desiredElemCount = elemToArraySize[elem];
                destructiveResizeIfNecessary(cpuData, destCapacity, desiredElemCount, typeinfo.arrayElemSize);

                // Copy from GPU to CPU
                size_t copyByteCount = desiredElemCount * typeinfo.arrayElemSize;

                if(gpuData)
                    computeAPI->memcpy(*computeCtx, cpuData, gpuData, copyByteCount, MemcpyKind::deviceToHost);
            }

            // Don't copy the outer array to CPU, because GPU is not allowed to change outer array
        }
        else
        {
            log("array values: from GPU\n");
            computeAPI->memcpy(*computeCtx, cpuArray, gpuArray, byteCount, MemcpyKind::deviceToHost);
        }

        cpuValid = true;
    }
    else if (!cpuValid && usdValid)
    {
        // printf("TODO: read data lazily from USD\n");
    }
    else
    {
        if (printWarnings)
            CARB_LOG_WARN("No source has valid data array=%p usdValid=%i cpuValid=%i gpuValid=%i gpuAllocedWithCuda=%i", &array, array.usdValid, array.cpuValid, array.gpuValid, array.gpuAllocedWithCuda);
    }
}

inline void PathToAttributesMap::enableCpuReadIfValid(PathToAttributesMap::MirroredArray& array,
                                                      const size_t* elemToArraySize,
                                                      PathToAttributesMap::MirroredArray* elemToArrayCpuCapacity,
                                                      PathToAttributesMap::MirroredArray* elemToArrayGpuCapacity,
                                                      PathToAttributesMap::MirroredArray* gpuArrayDataArray)
{
    enableCpuReadImpl(array, elemToArraySize, elemToArrayCpuCapacity, elemToArrayGpuCapacity, gpuArrayDataArray, false);
}




inline void PathToAttributesMap::enableCpuRead(PathToAttributesMap::MirroredArray& array,
                                               const size_t* elemToArraySize,
                                               PathToAttributesMap::MirroredArray* elemToArrayCpuCapacity,
                                               PathToAttributesMap::MirroredArray* elemToArrayGpuCapacity,
                                               PathToAttributesMap::MirroredArray* gpuArrayDataArray)
{
    enableCpuReadImpl(array, elemToArraySize, elemToArrayCpuCapacity, elemToArrayGpuCapacity, gpuArrayDataArray, true);
}

inline void PathToAttributesMap::enableCpuWrite(PathToAttributesMap::MirroredArray& array,
                                                const size_t* elemToArraySize,
                                                PathToAttributesMap::MirroredArray* elemToArrayCpuCapacity,
                                                PathToAttributesMap::MirroredArray* elemToArrayGpuCapacity,
                                                PathToAttributesMap::MirroredArray* elemToArrayGpuData)
{
    using omni::gpucompute::MemcpyKind;

    bool& usdValid = array.usdValid;
    bool& cpuValid = array.cpuValid;
    bool& gpuValid = array.gpuValid;

    const Typeinfo &typeinfo = array.typeinfo;

    // Array-valued elements are lazily allocated, meaning they are only
    // resized when write access is requested.
    // Write access has been requested, so resize if necessary
    std::lock_guard<MirroredArray::AttributeMutex> hostDeviceLock(array.attributeMutex);
    if (typeinfo.isArray)
    {
        size_t elemCount = array.count;
        uint8_t** elemToArrayCpuData = reinterpret_cast<uint8_t**>(array.cpuData());

        CARB_ASSERT(elemToArrayCpuCapacity->cpuValid);

        for (size_t elem = 0; elem != elemCount; elem++)
        {
            uint8_t*& cpuData = elemToArrayCpuData[elem];
            size_t& cpuCapacity = reinterpret_cast<size_t*>(elemToArrayCpuCapacity->cpuData())[elem];
            size_t desiredElemCount = elemToArraySize[elem];

            resizeIfNecessary(cpuData, cpuCapacity, desiredElemCount, typeinfo.arrayElemSize, array.type);
        }
    }

    // New state
    usdValid = false;
    cpuValid = true;
    gpuValid = false;
}


inline ArrayAndDirtyIndices PathToAttributesMap::getArraySpanC(MirroredArray& array,
                                                               const AttrName& name,
                                                               const ArrayOfArrayInfo& aoa,
                                                               BucketImpl& bucketImpl,
                                                               const IOConfig& io)
{
    const size_t elemCount = bucketImpl.elemToPath.size();
    const Typeinfo& typeinfo = array.typeinfo;
    const size_t elemSize = typeinfo.size;
    log("begin getArrayC\n");

    bool isTag = (elemSize == 0);
    if (isTag)
    {
        // If is a tag, then array.data() will be zero, so set special value
        // to distinguish from tag absent case
        return { SpanC{ (uint8_t*)-1, elemCount, 0 }, {} };
    }

    // Read enable must come before write enable
    if (io.enableRead)
    {
        (this->*io.enableRead)(array, aoa.arraySizeArray, aoa.arrayCpuCapacityArray, aoa.arrayGpuCapacityArray, aoa.arrayGpuPtrArray);

        // If requesting GPU access to array-of-array, additionally
        // enable array of GPU pointers for GPU read
        if (typeinfo.isArray && io.device == Device::eCudaGPU)
        {
            (this->*io.enableRead)(*aoa.arrayGpuPtrArray, nullptr, nullptr, nullptr, nullptr);
        }
    }
    if (io.enableWrite)
    {
        (this->*io.enableWrite)(array, aoa.arraySizeArray, aoa.arrayCpuCapacityArray, aoa.arrayGpuCapacityArray, aoa.arrayGpuPtrArray);

        // If requesting GPU access to array-of-array, additionally
        // enable array of GPU pointers for GPU _read_
        // This is necessary because the pointers may have been
        // reallocated on CPU, and the GPU needs to _read_ these new
        // pointers
        if (typeinfo.isArray && io.device == Device::eCudaGPU)
        {
            (this->*io.enableRdPtrForWrite)(*aoa.arrayGpuPtrArray, nullptr, nullptr, nullptr, nullptr);
        }
    }

    // If CPU pointer requested
    //    return CPU pointer
    // If GPU pointer requested and not array of array
    //    return GPU pointer
    // If GPU pointer requested and array of array
    //    return GPU pointer to GPU pointer array
    uint8_t* retPtr = nullptr;
    if (io.device == Device::eCPU)
    {
        retPtr = array.cpuData();
    }
    else if (io.device == Device::eCudaGPU && !typeinfo.isArray)
    {
        retPtr = array.gpuArray;
    }
    else if (io.device == Device::eCudaGPU && typeinfo.isArray && io.ptrToPtrKind == PtrToPtrKind::eGpuPtrToGpuPtr)
    {
        retPtr = aoa.arrayGpuPtrArray->gpuArray;
    }
    else if (io.device == Device::eCudaGPU && typeinfo.isArray && io.ptrToPtrKind == PtrToPtrKind::eCpuPtrToGpuPtr)
    {
        retPtr = aoa.arrayGpuPtrArray->cpuData();
    }
    else if (io.device == Device::eD3dVkGPU && !typeinfo.isArray)
    {
        retPtr = array.gpuArray;
    }
    else if (io.device == Device::eD3dVkGPU && typeinfo.isArray)
    {
        retPtr = aoa.arrayGpuPtrArray->cpuData();
    }

    // If enabling write,
    //    for each enabled listener listening to this attribute
    //       if changedIndices exists
    //           add to vector
    //       else
    //           create changedIndices and add to vector
    //       return vector
    // else
    //    return empty vector
    std::vector<ChangedIndicesImpl*> changedIndicesForEachListener;
    changedIndicesForEachListener.reserve(listenerIdToChangeTrackerConfig.size());

    if (io.enableWrite)
    {
        // optimization because the cost to create attrNameAndType is non-trivial,
        // but they are loop invariant so we should try to only do it once.
        bool costlyInvariantsInitialized = false;
        AttrNameAndType *const attrNameAndType = (AttrNameAndType*)alloca(sizeof(AttrNameAndType)); // stack-allocate here for scope, but lazily-initialize below

        listenerIdToChangeTrackerConfig.forEach([this, &bucketImpl, &costlyInvariantsInitialized, &name, &attrNameAndType, &array, &elemCount, &changedIndicesForEachListener](ListenerId& listenerId, ChangeTrackerConfig& config) {
            // Create listener if it doesn't exist in bucket
            Changes* changes;
            if (bucketImpl.listenerIdToChanges.allocateEntry(listenerId, &changes))
            {
                new (changes) Changes();
            }
            if (config.changeTrackingEnabled && config.attrNamesToLog.contains(name.name))
            {
                if (!costlyInvariantsInitialized)
                {
                    new (attrNameAndType) AttrNameAndType(Type(array.type), name.name, name.suffix);
                    costlyInvariantsInitialized = true;
                }

                auto iter = changes->changedAttributes.find(*attrNameAndType);
                bool foundChangedIndices = (iter != changes->changedAttributes.end());

                if (!foundChangedIndices)
                {
                    // TODO: move this into a new ordered_map class
                    auto& keys = changes->changedAttributes.v;
                    auto& values = changes->changedIndices;
                    auto insertIter = lower_bound(keys.begin(), keys.end(), *attrNameAndType);
                    ptrdiff_t insertIndex = insertIter - keys.begin();
                    keys.insert(insertIter, *attrNameAndType);
                    values.insert(values.begin() + insertIndex, ChangedIndicesImpl(elemCount));

                    changedIndicesForEachListener.push_back(&values[insertIndex]);
                }
                else
                {
                    ptrdiff_t attrIndex = iter - changes->changedAttributes.begin();
                    changedIndicesForEachListener.push_back(&changes->changedIndices[attrIndex]);
                }
            }
        });
    }

    return { SpanC{ retPtr, elemCount, typeinfo.size }, changedIndicesForEachListener };
}

inline ArrayAndDirtyIndices PathToAttributesMap::getArraySpanC(BucketId bucketId,
                                                               TokenC attrName,
                                                               const IOConfig &io,
                                                               NameSuffix suffix)
{
    BucketImpl *const bucketImpl = buckets.find(bucketId);
    if (!bucketImpl)
    {
        return { SpanC{ nullptr, 0, 0 }, {} };
    }

    const AttrName name{ attrName, suffix };
    {
        ScalarAttributeArray *array;
        if (bucketImpl->scalarAttributeArrays.find(name, &array))
        {
            const ArrayOfArrayInfo aoa = ScalarArrayOfArrayInfo();
            return getArraySpanC(*array, name, aoa, *bucketImpl, io);
        }
    }

    {
        ArrayAttributeArray *array;
        if (bucketImpl->arrayAttributeArrays.find(name, &array))
        {
            const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*array);
            return getArraySpanC(array->values, name, aoa, *bucketImpl, io);
        }
    }

    return { SpanC{ nullptr, 0, 0 }, {} };
}

template <typename T>
inline const T* PathToAttributesMap::getArrayRd(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArrayRd", apiLogEnabled, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<const T*>(getArrayRdC(bucket, attrName, NameSuffix::none));
}

template <typename T>
inline const T* PathToAttributesMap::getArrayRd(BucketId bucketId, const TokenC& attrName)
{
    APILOGGER("getArrayRd", apiLogEnabled, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<const T*>(getArrayRdC(bucketId, attrName, NameSuffix::none).ptr);
}

template <typename T>
inline T* PathToAttributesMap::getArrayWr(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArrayWr", apiLogEnabled, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<T*>(getArrayWrC(bucket, attrName, NameSuffix::none));
}

template <typename T>
inline T* PathToAttributesMap::getArray(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArray", apiLogEnabled, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<T*>(getArrayC(bucket, attrName, NameSuffix::none));
}

template <typename T>
inline std::vector<const T*> PathToAttributesMap::getArraysRd(const std::vector<Bucket>& buckets, const TokenC& attrName)
{
    size_t bucketCount = buckets.size();
    std::vector<const T*> retval(bucketCount);
    for (size_t i = 0; i != bucketCount; i++)
    {
        retval[i] = getArrayRd<T>(buckets[i], attrName);
    }
    return retval;
}

template <typename T>
inline std::vector<T*> PathToAttributesMap::getArraysWr(const std::vector<Bucket>& buckets, const TokenC& attrName)
{
    size_t bucketCount = buckets.size();
    std::vector<const T*> retval(bucketCount);
    for (size_t i = 0; i != bucketCount; i++)
    {
        retval[i] = getArrayWr<T>(buckets[i], attrName);
    }
    return retval;
}

template <typename T>
inline std::vector<T*> PathToAttributesMap::getArrays(const std::vector<Bucket>& buckets, const TokenC& attrName)
{
    size_t bucketCount = buckets.size();
    std::vector<T*> retval(bucketCount);
    for (size_t i = 0; i != bucketCount; i++)
    {
        retval[i] = getArray<T>(buckets[i], attrName);
    }
    return retval;
}

inline BucketId PathToAttributesMap::findBucketId(const Bucket& bucket)
{
    auto iter = attrNameSetToBucketId.find(bucket);
    bool found = iter != attrNameSetToBucketId.end();
    if (!found)
        return { kInvalidBucketId };
    return iter->second;
}

inline ConstSpanC PathToAttributesMap::getArraySpanRdC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArraySpanRdC", apiLogEnabled, attrName);

    // Get read-only CPU access
    BucketId bucketId = findBucketId(bucket);
    if (bucketId == kInvalidBucketId)
        return { nullptr, 0, 0 };
    const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuReadConfig(), suffix);
    // We don't set dirty indices here because this method gives read-only access
    return arrayAndDirtyIndices.array;
}

inline const void* PathToAttributesMap::getArrayRdC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArrayRdC", apiLogEnabled, attrName);

    // Get read-only CPU access
    BucketId bucketId = findBucketId(bucket);
    if (bucketId == kInvalidBucketId)
        return nullptr;
    const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuReadConfig(), suffix);
    // We don't set dirty indices here because this method gives read-only access
    return arrayAndDirtyIndices.array.ptr;
}

inline ConstSpanC PathToAttributesMap::getArrayRdC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArrayRdC", apiLogEnabled, attrName);

    // Get read-only CPU access
    const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuReadConfig(), suffix);
    // We don't set dirty indices here because this method gives read-only access
    return arrayAndDirtyIndices.array;
}


inline SpanC PathToAttributesMap::getArraySpanWrC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArraySpanWrC", apiLogEnabled, attrName);

    BucketId bucketId = findBucketId(bucket);
    if (bucketId == kInvalidBucketId)
        return { nullptr, 0, 0 };

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuWriteConfig(), suffix);
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array;
}

inline void* PathToAttributesMap::getArrayWrC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArrayWrC", apiLogEnabled, attrName);

    BucketId bucketId = findBucketId(bucket);
    if (bucketId == kInvalidBucketId)
        return nullptr;

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuWriteConfig(), suffix);
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array.ptr;
}

inline SpanC PathToAttributesMap::getArrayWrC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArrayWrC", apiLogEnabled, attrName);

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuWriteConfig(), suffix);
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array;
}

inline SpanC PathToAttributesMap::getOrCreateArrayWrC(
    BucketId bucketId, const TokenC& attrName, TypeC type, NameSuffix suffix)
{
    APILOGGER("getOrCreateArrayWrC", apiLogEnabled, attrName);

    auto bucketImpl = buckets.find(bucketId);
    if (!bucketImpl)
    {
        return SpanC{ nullptr, 0, 0 };
    }

    const AttrName name{ attrName, suffix };
    ArrayOfArrayInfo aoa;
    MirroredArray* array = nullptr;
    const Typeinfo& typeinfo = getTypeInfo(type);
    if (typeinfo.isArray)
    {
        ArrayAttributeArray *arrayAttributeArray;
        if (!bucketImpl->arrayAttributeArrays.find(name, &arrayAttributeArray))
        {
            Bucket bucket = getNamesAndTypes(bucketId);
            bucketImpl = &addAttributeC(*bucketImpl, bucket, attrName, type);

            const bool found = bucketImpl->arrayAttributeArrays.find({ attrName, NameSuffix::none }, &arrayAttributeArray);
            CARB_ASSERT(found);
            CARB_UNUSED(found);

            array = &arrayAttributeArray->values;
            aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        }
        else
        {
            array = &arrayAttributeArray->values;
            aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        }
    }
    else
    {
        ScalarAttributeArray *scalarAttributeArray;
        if (!bucketImpl->scalarAttributeArrays.find(name, &scalarAttributeArray))
        {
            Bucket bucket = getNamesAndTypes(bucketId);
            bucketImpl = &addAttributeC(*bucketImpl, bucket, attrName, type);

            const bool found = bucketImpl->scalarAttributeArrays.find({ attrName, NameSuffix::none }, &scalarAttributeArray);
            CARB_ASSERT(found);
            CARB_UNUSED(found);

            array = scalarAttributeArray;
            aoa = ScalarArrayOfArrayInfo();
        }
        else
        {
            array = scalarAttributeArray;
            aoa = ScalarArrayOfArrayInfo();
        }
    }
    CARB_ASSERT(type == array->type);

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(*array, name, aoa, *bucketImpl, CpuWriteConfig());
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array;
}

inline SpanC PathToAttributesMap::getArraySpanC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArraySpanC", apiLogEnabled, attrName);

    BucketId bucketId = findBucketId(bucket);
    if (bucketId == kInvalidBucketId)
        return { nullptr, 0, 0 };

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuReadWriteConfig(), suffix);
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array;
}

inline void* PathToAttributesMap::getArrayC(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArrayC", apiLogEnabled, attrName);

    BucketId bucketId = findBucketId(bucket);
    if (bucketId == kInvalidBucketId)
        return nullptr;

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuReadWriteConfig(), suffix);
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array.ptr;
}

inline void PathToAttributesMap::setArrayDirty(ArrayAndDirtyIndices& array)
{
    for (ChangedIndicesImpl* listener : array.changedIndicesForEachListener)
    {
        listener->dirtyAll();
    }
}

inline void PathToAttributesMap::setArrayElementDirty(ArrayAndDirtyIndices& array, size_t elemIndex)
{
    for (ChangedIndicesImpl* listener : array.changedIndicesForEachListener)
    {
        listener->insert(elemIndex, array.array.elementCount);
    }
}

inline SpanC PathToAttributesMap::getArrayC(BucketId bucketId, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getArrayC", apiLogEnabled, attrName);

    ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(bucketId, attrName, CpuReadWriteConfig(), suffix);
    setArrayDirty(arrayAndDirtyIndices);

    return arrayAndDirtyIndices.array;
}

inline const PathC* PathToAttributesMap::getPathArray(const Bucket& bucket) const
{
    auto iter = attrNameSetToBucketId.find(bucket);
    bool found = (iter != attrNameSetToBucketId.end());
    if (found)
    {
        BucketId bucketId = iter->second;
        const auto implPtr = buckets.find(bucketId);
        if (implPtr)
        {
            return reinterpret_cast<const PathC*>(implPtr->elemToPath.data());
        }
        else
        {
            CARB_LOG_WARN_ONCE("Found in attrNameSetToBucketId, but didn't find BucketId %zu in buckets\n", size_t(bucketId));
        }
    }

    CARB_LOG_ERROR("getPathArray: Bucket not found");
    printBucket(bucket);
    std::cout << "\n";
    CARB_LOG_INFO("Bucket list:");
    printBucketNamesAndTypes();
    return nullptr;
}

inline ConstPathCSpan PathToAttributesMap::getPathArray(BucketId bucketId) const
{
    const auto implPtr = buckets.find(bucketId);
    if (implPtr)
    {
        const BucketImpl& bucketImpl = *implPtr;
        return { reinterpret_cast<const Path*>(bucketImpl.elemToPath.data()), bucketImpl.elemToPath.size() };
    }
    else
    {
        CARB_LOG_WARN_ONCE("Found in attrNameSetToBucketId, but didn't find BucketId %zu in buckets\n", size_t(bucketId));
    }
    return { nullptr, 0 };
}

inline Bucket PathToAttributesMap::getNamesAndTypes(BucketId bucketId) const
{
    auto implPtr = buckets.find(bucketId);
    if (implPtr)
    {
        const BucketImpl& bucketImpl = *implPtr;
        size_t maxCount = bucketImpl.scalarAttributeArrays.size();

        set<flatcache::AttrNameAndType> bucket;
        bucket.reserve(maxCount);
        bucketImpl.scalarAttributeArrays.forEach([&bucket](const AttrName& name, const ScalarAttributeArray& array) {
            const TypeC& type = array.type;

            if (name.suffix == NameSuffix::none || name.suffix == NameSuffix::connection)
            {
                AttrNameAndType attrNameAndType;
                attrNameAndType.type = carb::flatcache::Type(type);
                attrNameAndType.name = name.name;
                attrNameAndType.suffix = name.suffix;
                bucket.insert(attrNameAndType);
            }
        });
        bucketImpl.arrayAttributeArrays.forEach([&bucket](const AttrName& name, const ArrayAttributeArray& array) {
            const TypeC& type = array.values.type;

            if (name.suffix == NameSuffix::none || name.suffix == NameSuffix::connection)
            {
                AttrNameAndType attrNameAndType;
                attrNameAndType.type = Type(type);
                attrNameAndType.name = name.name;
                attrNameAndType.suffix = name.suffix;
                bucket.insert(attrNameAndType);
            }
        });
        return bucket;
    }
    else
    {
        CARB_LOG_ERROR_ONCE("getNamesAndTypes, bucketId %zu not found\n", size_t(bucketId));
        return set<AttrNameAndType>();
    }
}

inline void PathToAttributesMap::checkInvariants()
{
    for (auto& bucketAndId : attrNameSetToBucketId)
    {
        const Bucket& correctBucket = bucketAndId.first;

        BucketId bucketId = bucketAndId.second;
        Bucket candidateBucket = getNamesAndTypes(bucketId);

        if (candidateBucket.size() != correctBucket.size())
        {
            CARB_BREAK_POINT();
        }

        for (size_t i = 0; i != candidateBucket.size(); i++)
        {
            const AttrNameAndType& candidateNameAndType = candidateBucket.v[i];
            const AttrNameAndType& correctNameAndType = correctBucket.v[i];

            if (!(candidateNameAndType == correctNameAndType))
            {
                std::stringstream ss;

                ss << "Candidate: " << Type(candidateNameAndType.type) << " "
                   << Token(candidateNameAndType.name).getText() << toString(candidateNameAndType.suffix) << " "
                   << " Correct: " << Type(correctNameAndType.type)
                   << " " << Token(correctNameAndType.name).getText() << toString(correctNameAndType.suffix) << " "
                   << "\n";
                CARB_LOG_ERROR("%s", ss.str().c_str());

                CARB_BREAK_POINT();
            }
        }
    }
}

inline std::pair<bool, std::vector<AttrNameAndType>::const_iterator> findAttrNameAndType(const Bucket& bucket,
                                                                                         const TokenC& attrName)
{
#if 0
    // Do O(log n) search of bucket for attrName, ignoring type
    auto cmp = [](const AttrNameAndType& a, AttrNameAndTime b) {
        return a.name < b;
    };
    auto i = lower_bound(bucket.begin(), bucket.end(), attrName, cmp);

    // There can be multiple elements with same attrName, so check them all
    while (i != bucket.end() && i->name == attrName && i->suffix != NameSuffix::none)
        i++;
    // At this point i is either at the end, or at the end of the elements with attrName, or pointing to an element with
    // suffix==none

    // If didn't get to the end, and didn't get to the end of the elements with attrName, then must be pointing to
    // attrName with suffix==none
    bool found = (i != bucket.end() && i->name == attrName);
    return found ? (i->tfType) : (pxr::TfType());
#else
    // Until we fix the order of the fields in the tuple to make equal attrNames contiguous, do a linear search
    auto i = bucket.begin();
    while (i != bucket.end() && !(i->name == attrName && i->suffix == NameSuffix::none))
        i++;
    bool found = (i != bucket.end());

    return make_pair(found, i);
#endif
}

inline TypeC PathToAttributesMap::getType(const Bucket& bucket, const TokenC& attrName) const
{
    APILOGGER("getType", apiLogEnabled, attrName);

    std::vector<AttrNameAndType>::const_iterator pAttrNameAndType;
    bool found;
    std::tie(found, pAttrNameAndType) = findAttrNameAndType(bucket, attrName);
    return found ? TypeC(pAttrNameAndType->type) : TypeC();
}

inline void PathToAttributesMap::addPath(const PathC& path, const Bucket& destBucket)
{
    std::pair<BucketId, ArrayIndex> *pathAndBucketElem;
    if (pathToBucketElem.allocateEntry(path, &pathAndBucketElem))
    {
        auto bucketIdAndImpl = findOrCreateBucket(destBucket);
        BucketId bucketId = bucketIdAndImpl.first;
        BucketImpl& bucketImpl = bucketIdAndImpl.second;
        bucketImpl.SetBucket(destBucket);
        size_t endElement = allocElement(bucketImpl);

        *pathAndBucketElem = std::make_pair(bucketId, endElement);

        bucketImpl.elemToPath[endElement] = { toSdfPath(path) };
    }
    else
    {
        auto iter = attrNameSetToBucketId.find(destBucket);
        bool destBucketExists = (iter != attrNameSetToBucketId.end());
        BucketId destBucketId = destBucketExists ? iter->second : kInvalidBucketId;

        BucketId currentBucketId = pathAndBucketElem->first;
        bool destBucketSpecified = (destBucket.size() != 0);
        if (!destBucketSpecified || (destBucketExists && destBucketId == currentBucketId))
        {
            // If the dest bucket is not specified, or if already in the right
            // bucket, then leave path in current bucket
            return;
        }
        else if (destBucketSpecified && (destBucketId != currentBucketId))
        {
            moveElementBetweenBuckets(path, destBucketId, currentBucketId, destBucket);
        }
    }
}

// renames a path in a bucket
inline void PathToAttributesMap::renamePath(const PathC& oldPath, const PathC& newPath)
{
    // TODO: should this early exit if oldPath == newPath?

    std::pair<BucketId, ArrayIndex> *oldPathAndBucketElem;
    if (pathToBucketElem.find(oldPath, &oldPathAndBucketElem))
    {
        BucketImpl* bucketImplPtr = buckets.find(oldPathAndBucketElem->first);
        bucketImplPtr->elemToPath[oldPathAndBucketElem->second] = toSdfPath(newPath);

        std::pair<BucketId, ArrayIndex> *newPathAndBucketElem;
        pathToBucketElem.allocateEntry(newPath, &newPathAndBucketElem);
        *newPathAndBucketElem = std::move(*oldPathAndBucketElem);
        pathToBucketElem.freeEntry(oldPath);
    }
    else
    {
        CARB_LOG_WARN_ONCE("PathToAttributesMap::renamePath(%s,%s) - cannot find bucket to rename\n",
                           Path(oldPath).getText(), Path(newPath).getText());
        return;
    }
}

// present - Whether this path has a bucket
// bucket - Pointer to bucket if it does
// element - Index corresponding to path in this bucket's arrays
inline std::tuple<bool, BucketId, size_t> PathToAttributesMap::getPresentAndBucketAndElement(const PathC& path) const
{
    const std::pair<BucketId, ArrayIndex>* bucketElem;
    if (!pathToBucketElem.find(path, &bucketElem))
    {
        return { false, kInvalidBucketId, 0 };
    }

    return { true, bucketElem->first, bucketElem->second };
}

inline BucketId PathToAttributesMap::getBucketId(const PathC& path) const
{
    std::tuple<bool, flatcache::BucketId, size_t> presentAndBucketAndElement = getPresentAndBucketAndElement(path);
    bool present = std::get<0>(presentAndBucketAndElement);
    if (!present)
        return flatcache::kInvalidBucketId;

    return std::get<1>(presentAndBucketAndElement);
}

inline SpanC PathToAttributesMap::getArrayElementPtr(SpanC array, size_t bucketElement) const
{
    if (array.ptr == nullptr)
        return { nullptr, 0, 0 };

    size_t elemSize = array.elementSize;
    return { array.ptr + bucketElement * elemSize, 1, elemSize };
}

inline ConstSpanC PathToAttributesMap::getArrayElementPtr(ConstSpanC array, size_t bucketElement) const
{
    if (array.ptr == nullptr)
        return { nullptr, 0, 0 };

    size_t elemSize = array.elementSize;
    return { array.ptr + bucketElement * elemSize, 1, elemSize };
}

inline SpanC PathToAttributesMap::getAttributeC(const PathC& path, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getAttributeC", apiLogEnabled, attrName);

    bool present; // Whether this path has a bucket
    BucketId bucketId; // Pointer to the bucket if it does
    size_t element; // Index corresponding to path in this bucket's arrays
    std::tie(present, bucketId, element) = getPresentAndBucketAndElement(path);
    if (!present)
        return { nullptr, 0, 0 };

    ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(bucketId, attrName, CpuReadWriteConfig(), suffix);
    setArrayElementDirty(arrayAndchangedIndices, element);

    SpanC array = arrayAndchangedIndices.array;
    return getArrayElementPtr(array, element);
}

inline ConstSpanC PathToAttributesMap::getAttributeRdC(const PathC& path, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getAttributeRdC", apiLogEnabled, attrName);

    bool present;
    BucketId bucketId;
    size_t element;
    std::tie(present, bucketId, element) = getPresentAndBucketAndElement(path);
    if (!present)
        return { nullptr, 0, 0 };

    const ConstSpanC array = getArraySpanC(bucketId, attrName, CpuReadConfig(), suffix).array;
    // We don't set dirty indices here because this method gives read-only access
    return getArrayElementPtr(array, element);
}

inline SpanC PathToAttributesMap::getAttributeWrC(const PathC& path, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getAttributeWrC", apiLogEnabled, path, attrName);

    bool present;
    BucketId bucketId;
    size_t element;
    std::tie(present, bucketId, element) = getPresentAndBucketAndElement(path);
    if (!present)
        return { nullptr, 0, 0 };

    // Writing an element is a RMW on the whole array, so get read/write CPU access
    ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(bucketId, attrName, CpuReadIfValidWriteConfig(), suffix);
    setArrayElementDirty(arrayAndchangedIndices, element);

    SpanC array = arrayAndchangedIndices.array;
    return getArrayElementPtr(array, element);
}

inline SpanC PathToAttributesMap::setArrayAttributeSizeAndGet(PathC path, const TokenC& attrName, size_t newSize)
{
    bool present; // Whether this path has a bucket
    BucketId bucketId; // Pointer to the bucket if it does
    size_t elementIndex; // Index corresponding to path in this bucket's arrays
    std::tie(present, bucketId, elementIndex) = getPresentAndBucketAndElement(path);
    if (!present)
        return { nullptr, 0, 0 };

    return setArrayAttributeSizeAndGet(bucketId, elementIndex, attrName, newSize);
}

inline SpanC PathToAttributesMap::setArrayAttributeSizeAndGet(
    BucketId bucketId, size_t elementIndex, const TokenC& attrName, size_t newSize)
{
    APILOGGER("setArrayAttributeSizeAndGet", apiLogEnabled, attrName);

    // TODO: remove double hash lookup here

    ArrayAndDirtyIndices sizeArray;
    {
        BucketImpl* bucketImpl;
        ArrayAttributeArray *arrayAttributeArray;
        if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
        {
            const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
            sizeArray = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadWriteConfig());
        }
        else
        {
            sizeArray = { 0 };
        }
    }

    if (sizeArray.array.elementCount <= elementIndex)
        return { nullptr, 0, 0 };

    // Set the size
    size_t* sizePtr = reinterpret_cast<size_t*>(getArrayElementPtr(sizeArray.array, elementIndex).ptr);
    if (!sizePtr)
        return { nullptr, 0, 0 };
    *sizePtr = newSize;

    // TODO: does this need to be moved higher next to getArraySpanC above?
    setArrayElementDirty(sizeArray, elementIndex);

    // Get the new array-valued element
    ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(bucketId, attrName, CpuReadWriteConfig(), NameSuffix::none);
    setArrayElementDirty(arrayAndchangedIndices, elementIndex);

    SpanC array = arrayAndchangedIndices.array;
    uint8_t** arrayData = reinterpret_cast<uint8_t**>(getArrayElementPtr(array, elementIndex).ptr);
    if (!arrayData)
        return { nullptr, 0, 0 };

    return { *arrayData, newSize, 0 };
}

template <typename T>
T* PathToAttributesMap::getAttribute(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getAttribute", apiLogEnabled, path, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<T*>(getAttributeC(path, attrName, NameSuffix::none).ptr);
}

template <typename T>
const T* PathToAttributesMap::getAttributeRd(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getAttributeRd", apiLogEnabled, path, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<const T*>(getAttributeRdC(path, attrName, NameSuffix::none).ptr);
}

template <typename T>
T* PathToAttributesMap::getAttributeWr(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getAttributeWr", apiLogEnabled, path, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<T*>(getAttributeWrC(path, attrName, NameSuffix::none).ptr);
}

template <typename T>
T* PathToAttributesMap::getAttributeWr(const PathC& path, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("getAttributeWr", apiLogEnabled, path, attrName);

    // TODO: check that T is the correct type
    return reinterpret_cast<T*>(getAttributeWrC(path, attrName, suffix).ptr);
}

inline ValidMirrors PathToAttributesMap::getAttributeValidBits(const PathC& path,
                                                               const TokenC& attrName,
                                                               ArrayAttributeArray::MirroredArrays subArray) const
{
    APILOGGER("getAttributeValidBits", apiLogEnabled, path, attrName);

    bool present; // Whether this path has a bucket
    BucketId bucketId; // Pointer to the bucket if it does
    size_t element; // Index corresponding to path in this bucket's arrays
    std::tie(present, bucketId, element) = getPresentAndBucketAndElement(path);
    if (!present)
        return ValidMirrors::eNone;

    const BucketImpl* bucketImplPtr = buckets.find(bucketId);
    if (!bucketImplPtr)
        return ValidMirrors::eNone;

    const MirroredArray *array = nullptr;
    const ScalarAttributeArray *scalarAttributeArray;
    const AttrName name{ attrName, NameSuffix::none };
    if (bucketImplPtr->scalarAttributeArrays.find(name, &scalarAttributeArray))
    {
        array = scalarAttributeArray;
    }
    else
    {
        const ArrayAttributeArray *arrayAttributeArray;
        if (bucketImplPtr->arrayAttributeArrays.find(name, &arrayAttributeArray))
        {
            // This if statement is only needed because we ported OM-70434 fix from 105 to 104.2
            // In 105, these mirrored arrays are stored in an array, indexed by subarray
            if (subArray == ArrayAttributeArray::MirroredArrays::Values)
            {
                array = &arrayAttributeArray->values;
            }
            else if (subArray == ArrayAttributeArray::MirroredArrays::ElemCounts)
            {
                array = &arrayAttributeArray->elemCounts;
            }
            else if (subArray == ArrayAttributeArray::MirroredArrays::CpuElemCounts)
            {
                array = &arrayAttributeArray->cpuElemCounts;
            }
            else if (subArray == ArrayAttributeArray::MirroredArrays::GpuElemCounts)
            {
                array = &arrayAttributeArray->gpuElemCounts;
            }
            else if (subArray == ArrayAttributeArray::MirroredArrays::GpuPtrs)
            {
                array = &arrayAttributeArray->gpuPtrs;
            }
        }
        else
        {
            return ValidMirrors::eNone;
        }
    }

    const size_t elemSize = array->typeinfo.size;
    const bool isTag = (elemSize == 0);
    if (isTag)
        return ValidMirrors::eNone;

    ValidMirrors retval = ValidMirrors::eNone;

    if (array->cpuValid)
        retval = retval | ValidMirrors::eCPU;
    if (array->gpuValid && array->gpuAllocedWithCuda)
        retval = retval | ValidMirrors::eCudaGPU;
    if (array->gpuValid && !array->gpuAllocedWithCuda)
        retval = retval | ValidMirrors::eGfxGPU;
    return retval;
}

inline bool PathToAttributesMap::findArrayAttributeArrayForPath(const PathC& path, const TokenC& attrName, size_t& outElementIndex, BucketImpl*& outBucketImpl, ArrayAttributeArray*& outArrayAttributeArray)
{
    BucketId bucketId;
    bool found;
    std::tie(found, bucketId, outElementIndex) = getPresentAndBucketAndElement(path);
    if (found)
    {
        outBucketImpl = buckets.find(bucketId);
        if (outBucketImpl)
        {
            ArrayAttributeArray* array;
            if (outBucketImpl->arrayAttributeArrays.find({ attrName, NameSuffix::none }, &array))
            {
                outArrayAttributeArray = array;
                return true;
            }
        }
    }

    CARB_LOG_WARN_ONCE("Warning: %s not found\n", toTfToken(attrName).GetText());
    return false;
}

inline bool PathToAttributesMap::findArrayAttributeArrayForBucketId(const BucketId bucketId, const TokenC& attrName, BucketImpl*& outBucketImpl, ArrayAttributeArray*& outArrayAttributeArray)
{
    if (bucketId != kInvalidBucketId)
    {
        outBucketImpl = buckets.find(bucketId);
        if (outBucketImpl)
        {
            ArrayAttributeArray* array;
            if (outBucketImpl->arrayAttributeArrays.find({ attrName, NameSuffix::none }, &array))
            {
                outArrayAttributeArray = array;
                return true;
            }
        }
    }

    CARB_LOG_WARN_ONCE("Warning: %s not found\n", toTfToken(attrName).GetText());
    return false;
}

inline size_t* PathToAttributesMap::getArrayAttributeSize(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSize", apiLogEnabled, path, attrName);

    size_t element;
    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForPath(path, attrName, element, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadWriteConfig());
        setArrayElementDirty(arrayAndchangedIndices, element);

        const SpanC array = arrayAndchangedIndices.array;
        return reinterpret_cast< size_t*>(getArrayElementPtr(array, element).ptr);
    }

    return nullptr;
}

inline const size_t* PathToAttributesMap::getArrayAttributeSizeRd(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizeRd", apiLogEnabled, path, attrName);

    size_t element;
    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForPath(path, attrName, element, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        const ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
        const ConstSpanC array = arrayAndchangedIndices.array;
        return reinterpret_cast<const size_t*>(getArrayElementPtr(array, element).ptr);
    }

    return nullptr;
}

inline size_t* PathToAttributesMap::getArrayAttributeSizeWr(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizeWr", apiLogEnabled, path, attrName);

    size_t element;
    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForPath(path, attrName, element, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadIfValidWriteConfig());
        setArrayElementDirty(arrayAndchangedIndices, element);
        const SpanC array = arrayAndchangedIndices.array;
        return reinterpret_cast<size_t*>(getArrayElementPtr(array, element).ptr);
    }

    return nullptr;
}

inline const size_t* PathToAttributesMap::getArrayAttributeSizeRdGpu(const PathC& path, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizeRdGpu", apiLogEnabled, path, attrName);

    size_t element;
    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForPath(path, attrName, element, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        const ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->gpuElemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CudaReadConfig());
        const ConstSpanC array = arrayAndchangedIndices.array;
        return reinterpret_cast<const size_t*>(getArrayElementPtr(array, element).ptr);
    }

    return nullptr;
}

inline const size_t* PathToAttributesMap::getArrayAttributeSizesRdGpu(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizesRdGpu", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;

    const BucketId bucketId = findBucketId(bucket);

    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        const ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->gpuElemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CudaReadConfig());
        const ConstSpanC array = arrayAndchangedIndices.array;
        return reinterpret_cast<const size_t*>(array.ptr);
    }

    return nullptr;
}

inline ConstSpanSizeC PathToAttributesMap::getArrayAttributeSizesRdGpu(BucketId bucketId, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizesRdGpu", apiLogEnabled, attrName);


    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;

    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        const ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->gpuElemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CudaReadConfig());
        const ConstSpanC array = arrayAndchangedIndices.array;
        return { reinterpret_cast<const size_t*>(array.ptr), array.elementCount };
    }
    return { nullptr, 0 };
}

inline size_t* PathToAttributesMap::getArrayAttributeSizes(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizes", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;

    const BucketId bucketId = findBucketId(bucket);

    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadWriteConfig());
        setArrayDirty(arrayAndchangedIndices);
        const SpanC array = arrayAndchangedIndices.array;
        return reinterpret_cast<size_t*>(array.ptr);
    }

    return nullptr;
}

inline SpanSizeC PathToAttributesMap::getArrayAttributeSizes(BucketId bucketId, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizes", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;

    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadWriteConfig());
        setArrayDirty(arrayAndchangedIndices);
        const SpanC array = arrayAndchangedIndices.array;
        CARB_ASSERT(array.elementSize == sizeof(size_t));
        return { reinterpret_cast<size_t*>(array.ptr), array.elementCount };
    }

    return { 0, 0 };
}

inline ConstSpanSizeC PathToAttributesMap::getArrayAttributeSizesRd(BucketId bucketId, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizesRd", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;

    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
        const ConstSpanC array = arrayAndchangedIndices.array;
        CARB_ASSERT(array.elementSize == sizeof(size_t));
        return { reinterpret_cast<const size_t*>(array.ptr), array.elementCount };
    }

    return { 0, 0 };
}

inline SpanSizeC PathToAttributesMap::getArrayAttributeSizesWr(BucketId bucketId, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizesWr", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;

    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuWriteConfig());
        setArrayDirty(arrayAndchangedIndices);
        const SpanC array = arrayAndchangedIndices.array;
        CARB_ASSERT(array.elementSize == sizeof(size_t));
        return { reinterpret_cast<size_t*>(array.ptr), array.elementCount };
    }

    return { 0, 0 };
}

inline ArrayPointersAndSizesC PathToAttributesMap::getArrayAttributeArrayWithSizes(BucketId bucketId,
                                                                                       const TokenC& attrName)
{
    APILOGGER("getArrayAttributeArrayWithSizes", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        SpanC spanOfPointers;
        {
            ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->values, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadWriteConfig());
            setArrayDirty(arrayAndDirtyIndices);
            spanOfPointers = arrayAndDirtyIndices.array;
        }

        ConstSpanC spanOfSizes;
        {
            const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
            spanOfSizes = arrayAndDirtyIndices.array;
        }

        CARB_ASSERT(spanOfPointers.elementSize == sizeof(uint8_t*));
        CARB_ASSERT(spanOfSizes.elementSize == sizeof(size_t));
        CARB_ASSERT(spanOfPointers.elementCount == spanOfSizes.elementCount);

        return { reinterpret_cast<uint8_t* const*>(spanOfPointers.ptr), reinterpret_cast<const size_t*>(spanOfSizes.ptr),
                    spanOfPointers.elementCount };
    }

    return ArrayPointersAndSizesC{ 0, 0, 0 };
}

inline ConstArrayPointersAndSizesC PathToAttributesMap::getArrayAttributeArrayWithSizesRd(BucketId bucketId,
                                                                                          const TokenC& attrName)
{
    APILOGGER("getArrayAttributeArrayWithSizesRd", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ConstSpanC spanOfPointers;
        {
            const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->values, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
            spanOfPointers = arrayAndDirtyIndices.array;
        }

        ConstSpanC spanOfSizes;
        {
            const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
            spanOfSizes = arrayAndDirtyIndices.array;
        }

        CARB_ASSERT(spanOfPointers.elementSize == sizeof(uint8_t*));
        CARB_ASSERT(spanOfSizes.elementSize == sizeof(size_t));
        CARB_ASSERT(spanOfPointers.elementCount == spanOfSizes.elementCount);

        return { reinterpret_cast<uint8_t* const*>(spanOfPointers.ptr), reinterpret_cast<const size_t*>(spanOfSizes.ptr),
                 spanOfPointers.elementCount };
    }

    return ConstArrayPointersAndSizesC{ 0, 0, 0 };
}

inline ArrayPointersAndSizesC PathToAttributesMap::getArrayAttributeArrayWithSizesWr(BucketId bucketId,
                                                                                     const TokenC& attrName)
{
    APILOGGER("getArrayAttributeArrayWithSizesWr", apiLogEnabled, attrName);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        SpanC spanOfPointers;
        {
            ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->values, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadWriteConfig());
            setArrayDirty(arrayAndDirtyIndices);
            spanOfPointers = arrayAndDirtyIndices.array;
        }

        ConstSpanC spanOfSizes;
        {
            const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
            spanOfSizes = arrayAndDirtyIndices.array;
        }

        CARB_ASSERT(spanOfPointers.elementSize == sizeof(uint8_t*));
        CARB_ASSERT(spanOfSizes.elementSize == sizeof(size_t));
        CARB_ASSERT(spanOfPointers.elementCount == spanOfSizes.elementCount);

        return { reinterpret_cast<uint8_t* const*>(spanOfPointers.ptr), reinterpret_cast<const size_t*>(spanOfSizes.ptr),
                 spanOfPointers.elementCount };
    }

    return ArrayPointersAndSizesC{ 0, 0, 0 };
}

inline const size_t* PathToAttributesMap::getArrayAttributeSizesRd(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizesRd", apiLogEnabled, attrName);

    const BucketId bucketId = findBucketId(bucket);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        const ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuReadConfig());
        return reinterpret_cast<const size_t*>(arrayAndDirtyIndices.array.ptr);
    }

    return nullptr;
}

inline size_t* PathToAttributesMap::getArrayAttributeSizesWr(const Bucket& bucket, const TokenC& attrName)
{
    APILOGGER("getArrayAttributeSizesWr", apiLogEnabled, attrName);

    const BucketId bucketId = findBucketId(bucket);

    BucketImpl* bucketImpl;
    ArrayAttributeArray *arrayAttributeArray;
    if (findArrayAttributeArrayForBucketId(bucketId, attrName, bucketImpl, arrayAttributeArray))
    {
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);
        ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->elemCounts, AttrName{ attrName, NameSuffix::none }, aoa, *bucketImpl, CpuWriteConfig());
        setArrayDirty(arrayAndDirtyIndices);
        return reinterpret_cast<size_t*>(arrayAndDirtyIndices.array.ptr);
    }

    return nullptr;
}

// Intersect set<AttrNameAndType> and set<AttrNameAndType> comparing type,
// name and suffix, and ignoring tfType
inline void set_intersection2(set<AttrNameAndType>::const_iterator first1,
                              set<AttrNameAndType>::const_iterator last1,
                              set<AttrNameAndType>::const_iterator first2,
                              set<AttrNameAndType>::const_iterator last2,
                              std::back_insert_iterator<std::vector<AttrNameAndType>> d_first)
{
    // Note that in the name comparisons below TokenC masks off USD's lifetime bit.
    // For example, tokens created from the same string are considered equal even
    // if one was created with finite lifetime and the other infinite lifetime.

    auto comp1 = [](const AttrNameAndType& a, const AttrNameAndType& b) {
        if (TypeC(a.type) < TypeC(b.type))
            return true;
        if (TypeC(b.type) < TypeC(a.type))
            return false;
        if (TokenC(a.name) < TokenC(b.name))
            return true;
        if (TokenC(b.name) < TokenC(a.name))
            return false;
        return a.suffix < b.suffix;
    };
    auto comp2 = [](const AttrNameAndType& a, const AttrNameAndType& b) {
        if (TypeC(a.type) < TypeC(b.type))
            return true;
        if (TypeC(b.type) < TypeC(a.type))
            return false;
        if (TokenC(a.name) < TokenC(b.name))
            return true;
        if (TokenC(b.name) < TokenC(a.name))
            return false;
        return a.suffix < b.suffix;
    };

    while (first1 != last1 && first2 != last2)
    {
        if (comp1(*first1, *first2))
        {
            ++first1;
        }
        else
        {
            if (!comp2(*first2, *first1))
            {
                *d_first++ = *first1++;
            }
            ++first2;
        }
    }
}

inline flatcache::set<BucketId> PathToAttributesMap::findBuckets(const set<AttrNameAndType>& all,
                                                                 const set<AttrNameAndType>& any,
                                                                 const set<AttrNameAndType>& none) const
{
    flatcache::set<BucketId> retval;
    retval.reserve(256);

    // TODO: Do this in a less brute-force way
    for (auto& bucketAndId : attrNameSetToBucketId)
    {
        const Bucket& bucketTypes = bucketAndId.first;
        BucketId bucketId = bucketAndId.second;
        bool bucketEmpty = getElementCount(bucketId) == 0;

        if (bucketEmpty)
            continue;

        std::vector<AttrNameAndType> allTypesPresent;
        std::vector<AttrNameAndType> anyTypesPresent;
        std::vector<AttrNameAndType> noneTypesPresent;

        set_intersection2(
            all.begin(), all.end(), bucketTypes.begin(), bucketTypes.end(), std::back_inserter(allTypesPresent));
        set_intersection2(
            any.begin(), any.end(), bucketTypes.begin(), bucketTypes.end(), std::back_inserter(anyTypesPresent));
        set_intersection2(
            none.begin(), none.end(), bucketTypes.begin(), bucketTypes.end(), std::back_inserter(noneTypesPresent));

        bool allOfAllTypesPresent = (allTypesPresent.size() == all.size());
        bool oneOfAnyTypesPresent = (any.size() == 0) || (anyTypesPresent.size() != 0);
        bool noneOfNoneTypesPresent = (noneTypesPresent.size() == 0);

        if (allOfAllTypesPresent && oneOfAnyTypesPresent && noneOfNoneTypesPresent)
        {
            retval.v.push_back(bucketId);
        }
    }

    // Sort the vector to make it a flatcache::set
    std::sort(retval.begin(), retval.end());

    return retval;
}

inline std::tuple<BucketId, ArrayIndex> PathToAttributesMap::getBucketAndArrayIndex(const PathC& path) const
{
    const std::pair<BucketId, ArrayIndex>* bucketAndElem;
    if (pathToBucketElem.find(path, &bucketAndElem))
    {
        const BucketId& bucketId = bucketAndElem->first;
        const ArrayIndex& arrayIndex = bucketAndElem->second;
        return { bucketId, arrayIndex };
    }
    else
    {
        // Commenting out the error in 104.2 as there is no hasPrim API in 104.2 yet
        // and FabricSD needs to check for existence of a prim without causing an error to be logged
        // CARB_LOG_ERROR_ONCE("getBucketAndArrayIndex called on non-existent path '%s'\n", Path(path).getText());
        return { kInvalidBucketId, kInvalidArrayIndex };
    }
}

inline Bucket PathToAttributesMap::getTypes(const PathC& path) const
{
    const std::pair<BucketId, ArrayIndex>* bucketAndElem;
    if (pathToBucketElem.find(path, &bucketAndElem))
    {
        const BucketImpl* bucketImpl = buckets.find(bucketAndElem->first);
        if (bucketImpl)
        {
            return bucketImpl->GetBucket();
        }
    }

    CARB_LOG_WARN_ONCE("getTypes called on non-existent path %s\n", Path(path).getText());
    return Bucket();
}

inline size_t PathToAttributesMap::getAttributeCount(const PathC& path) const
{
    const std::pair<BucketId, ArrayIndex>* bucketAndElem;
    if (pathToBucketElem.find(path, &bucketAndElem))
    {
        const BucketImpl* bucketImpl = buckets.find(bucketAndElem->first);
        if (bucketImpl)
        {
            return bucketImpl->GetBucket().size();
        }
    }

    CARB_LOG_ERROR_ONCE("getAttributeCount called on non-existent path %s\n", Path(path).getText());
    return 0;
}

inline TypeC PathToAttributesMap::getType(const PathC& path, const TokenC& attrName) const
{
    APILOGGER("getType", apiLogEnabled, path, attrName);

    const std::pair<BucketId, ArrayIndex>* bucketAndElem;
    if (!pathToBucketElem.find(path, &bucketAndElem))
    {
        CARB_LOG_WARN_ONCE("getTfType called on non-existent path %s\n", Path(path).getText());
        return kUnknownType;
    }

    const BucketId &bucketId = bucketAndElem->first;

    const BucketImpl* bucketImplPtr = buckets.find(bucketId);
    if (!bucketImplPtr)
    {
        CARB_LOG_WARN_ONCE(
            "getTfType called on non-existent bucket pathAndBucketElem is broken %s\n", Path(path).getText());
        return kUnknownType;
    }

    const AttrName name{ attrName, NameSuffix::none };
    const ScalarAttributeArray *scalarAttributeArray;
    if (bucketImplPtr->scalarAttributeArrays.find(name, &scalarAttributeArray))
    {
        return scalarAttributeArray->type;
    }
    else
    {
        const ArrayAttributeArray *arrayAttributeArray;
        if (bucketImplPtr->arrayAttributeArrays.find(name, &arrayAttributeArray))
        {
            return arrayAttributeArray->values.type;
        }
    }

    CARB_LOG_WARN_ONCE("getType called on non-existent attribute %s %s\n", Path(path).getText(), Token(attrName).getText());
    return kUnknownType;
}

// Return 1 if attribute is present at path, 0 otherwise
inline size_t PathToAttributesMap::count(const PathC& path, const TokenC& attrName) const
{
    bool present; // Whether this path has a bucket
    BucketId bucketId; // Pointer to the bucket if it does
    size_t element; // Index corresponding to path in this bucket's arrays
    std::tie(present, bucketId, element) = getPresentAndBucketAndElement(path);

    if (!present)
    {
        return 0;
    }

    const BucketImpl* bucketImplPtr = buckets.find(bucketId);
    if (!bucketImplPtr)
        return 0;

    const AttrName name{ attrName, NameSuffix::none };
    const ScalarAttributeArray *scalarAttributeArray;
    if (bucketImplPtr->scalarAttributeArrays.find(name, &scalarAttributeArray))
    {
        return 1;
    }
    else
    {
        const ArrayAttributeArray *arrayAttributeArray;
        if (bucketImplPtr->arrayAttributeArrays.find(name, &arrayAttributeArray))
        {
            return 1;
        }
    }

    return 0;
}

inline void PathToAttributesMap::moveElementScalarData(ScalarAttributeArray &destArray, const size_t destElemIndex, const ScalarAttributeArray &srcArray, const size_t srcElemIndex)
{
    if (srcArray.type != destArray.type)
    {
        return;
    }

    const Typeinfo& typeinfo = srcArray.typeinfo;

    const size_t size = typeinfo.size;
    const bool isArray = typeinfo.isArray;

    // Ideally usdValid would be driven by the change tracker
    // however I can't use that until we have a way to tie into that
    // Ideally there would be a subsscriber for "copying back to USD"
    // and that could be parsed to see if an element in invalid. At this point
    // we just have to do it per-attribute since that is as fine-grained as we
    // have data right now. This happens in moveElement to avoid having to repeat
    // logic about matching attriubte arrays that the function already does
    if (!srcArray.usdValid) {
        destArray.usdValid = srcArray.usdValid;
    }

    //
    // In the case where this is the first element in the new bucket
    // then the validity of the data needs to be moved from the old
    // bucket.
    //
    if (destElemIndex == 0) {
        destArray.cpuValid = srcArray.cpuValid;
        destArray.gpuValid = srcArray.gpuValid;
    }

    if (destArray.cpuValid && !srcArray.cpuValid)
    {
        // This should not happen because of makeSrcValidIfDestValid
        CARB_LOG_ERROR_ONCE("Invalid state while moving element: srcArray.cpuValid=%i destArray.cpuValid=%i",
            srcArray.cpuValid, destArray.cpuValid);
        assert(false);
    }
    if (destArray.gpuValid && !srcArray.gpuValid)
    {
        // This should not happen because of makeSrcValidIfDestValid
        CARB_LOG_ERROR_ONCE("Invalid state while moving element: srcArray.gpuValid=%i destArray.gpuValid=%i",
            srcArray.gpuValid, destArray.gpuValid);
        assert(false);
    }

    //
    // As noted above the validity of the src was already matched to the destinations needs
    // in the case, where for example the src has valid but the dest doesn't that is ok
    // but we do still move data, because in the case of array-of-array you get to at least
    // avoid another malloc.
    //
    if (srcArray.cpuValid || isArray)
    {
        uint8_t* destArrayData = destArray.cpuData();
        uint8_t* destPtr = destArrayData + destElemIndex * size;

        const uint8_t* srcArrayData = srcArray.cpuData();
        const uint8_t* srcPtr = srcArrayData + srcElemIndex * size;

        memcpy(destPtr, srcPtr, size);
    }

    if (srcArray.gpuValid)
    {
        if (isArray)
        {
            if (srcArray.gpuCapacity)
            {
                destArray.resizeGpu(platform.gpuCuda, platform.gpuCudaCtx, srcArray.gpuCapacity, typeinfo.size);
                platform.gpuCuda->memcpyAsync(*platform.gpuCudaCtx, destArray.gpuArray, srcArray.gpuArray, srcArray.gpuCapacity,
                                     omni::gpucompute::MemcpyKind::deviceToDevice);
            }
        }
        else
        {
            uint8_t* destArrayData = destArray.gpuArray;
            uint8_t* destPtr = destArrayData + destElemIndex * size;

            const uint8_t* srcArrayData = srcArray.gpuArray;
            const uint8_t* srcPtr = srcArrayData + srcElemIndex * size;

            platform.gpuCuda->memcpyAsync(*platform.gpuCudaCtx, destPtr, srcPtr, size, omni::gpucompute::MemcpyKind::deviceToDevice);
        }
        destArray.gpuAllocedWithCuda = true;
    }
}

inline void PathToAttributesMap::moveElementArrayData(ArrayAttributeArray &destArray, const size_t destElemIndex, const ArrayAttributeArray &srcArray, const size_t srcElemIndex)
{
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
    moveElementScalarData(destArray.values, destElemIndex, srcArray.values, srcElemIndex);
    moveElementScalarData(destArray.elemCounts, destElemIndex, srcArray.elemCounts, srcElemIndex);
    moveElementScalarData(destArray.cpuElemCounts, destElemIndex, srcArray.cpuElemCounts, srcElemIndex);
    moveElementScalarData(destArray.gpuElemCounts, destElemIndex, srcArray.gpuElemCounts, srcElemIndex);
    moveElementScalarData(destArray.gpuPtrs, destElemIndex, srcArray.gpuPtrs, srcElemIndex);
}

inline void PathToAttributesMap::moveElement(BucketImpl& destBucket,
    size_t destElemIndex,
    BucketImpl& srcBucket,
    size_t srcElemIndex)
{
    srcBucket.scalarAttributeArrays.forEach([this, &destBucket, &destElemIndex, &srcElemIndex](const AttrName& name, const ScalarAttributeArray& srcArray) {
        // If bucket move is due to removal then one destTupleIndex will be
        // invalid. So we check for invalid here
        ScalarAttributeArray *destArray;
        if (destBucket.scalarAttributeArrays.find(name, &destArray))
        {
            moveElementScalarData(*destArray, destElemIndex, srcArray, srcElemIndex);
        }
    });

    srcBucket.arrayAttributeArrays.forEach([this, &destBucket, &destElemIndex, &srcElemIndex](const AttrName& name, const ArrayAttributeArray& srcArray) {
        // If bucket move is due to removal then one destTupleIndex will be
        // invalid. So we check for invalid here
        ArrayAttributeArray *destArray;
        if (destBucket.arrayAttributeArrays.find(name, &destArray))
        {
            moveElementArrayData(*destArray, destElemIndex, srcArray, srcElemIndex);
        }
    });

    destBucket.elemToPath[destElemIndex] = std::move(srcBucket.elemToPath[srcElemIndex]);
}

inline void PathToAttributesMap::destroyElement(BucketId bucketId, size_t elemIndex, bool destroyDataPointedTo)
{
    BucketImpl* srcBucketImplPtr = buckets.find(bucketId);
    if (!srcBucketImplPtr)
        return; // nothing to delete

    BucketImpl& srcBucketImpl = *srcBucketImplPtr;

    size_t elemCount = PathToAttributesMap::getElementCount(srcBucketImpl);
    if (elemCount == 0)
        return; // nothing to delete

    if (destroyDataPointedTo)
    {
        // Destruct element about to be overwritten
        srcBucketImpl.arrayAttributeArrays.forEach([this, &elemIndex](const AttrName& name, ArrayAttributeArray& array) {
            // If a CPU array has been allocated, delete it
            uint8_t** arrayCpuPtrArray = reinterpret_cast<uint8_t**>(array.values.cpuData());
            uint8_t*& cpuPtrToDelete = arrayCpuPtrArray[elemIndex];
            if (cpuPtrToDelete)
            {
                if (!USE_PINNED_MEMORY || !platform.gpuCuda)
                {
                    free(cpuPtrToDelete);
                }
                else if (platform.gpuCuda)
                {
                    platform.gpuCuda->freeHost(*platform.gpuCudaCtx, cpuPtrToDelete);
                }
                cpuPtrToDelete = nullptr;
            }

            // If a GPU array has been allocated, delete it
            uint8_t** arrayGpuPtrArray = reinterpret_cast<uint8_t**>(array.gpuPtrs.cpuData());
            uint8_t*& gpuPtrToDelete = arrayGpuPtrArray[elemIndex];
            if (gpuPtrToDelete)
            {
                platform.gpuCuda->free(*platform.gpuCudaCtx, gpuPtrToDelete);
                gpuPtrToDelete = nullptr;
            }

            size_t* arrayCpuCapacityArray = reinterpret_cast<size_t*>(array.cpuElemCounts.cpuData());
            arrayCpuCapacityArray[elemIndex] = 0;

            size_t* arrayGpuCapacityArray = reinterpret_cast<size_t*>(array.gpuElemCounts.cpuData());
            arrayGpuCapacityArray[elemIndex] = 0;

            size_t* arraySizeArray = reinterpret_cast<size_t*>(array.elemCounts.cpuData());
            arraySizeArray[elemIndex] = 0;
        });
    }

    // Copy last element to element to be deleted
    PathC movedElemPath;
    size_t lastElemIndex = elemCount - 1;
    bool deletingLastElement = (elemIndex == lastElemIndex);

    // If bucket has more than one element, move last element to deleted element
    if (!deletingLastElement)
    {
        moveElement(srcBucketImpl, elemIndex, srcBucketImpl, lastElemIndex);
        movedElemPath = asInt(srcBucketImpl.elemToPath[elemIndex]);

        // For all attributes, dirty[elemIndex] := dirty[lastElemIndex]
        srcBucketImpl.listenerIdToChanges.forEach([&elemIndex, &lastElemIndex, &elemCount](const ListenerId& listenerId, Changes& changes) {
            size_t trackedAttrCount = changes.changedAttributes.size();
            for (size_t i = 0; i != trackedAttrCount; i++)
            {
                ChangedIndicesImpl& changedIndices = changes.changedIndices[i];
                if (changedIndices.contains(lastElemIndex) && !changedIndices.contains(elemIndex))
                {
                    changedIndices.insert(elemIndex, elemCount - 1);
                }
                else if (!changedIndices.contains(lastElemIndex) && changedIndices.contains(elemIndex))
                {
                    changedIndices.erase(elemIndex, elemCount - 1);
                }
            }
        });
    }

    // Remove last element from change tracker
    srcBucketImpl.listenerIdToChanges.forEach([&elemCount](const ListenerId& listenerId, Changes& changes) {
        size_t trackedAttrCount = changes.changedAttributes.size();
        for (size_t i = 0; i != trackedAttrCount; i++)
        {
            ChangedIndicesImpl& changedIndices = changes.changedIndices[i];
            changedIndices.decrementN(elemCount - 1);
        }
    });

    {
        const auto removeLastElementFromMirroredArray = [this](MirroredArray& array) {
            if (array.count > 0)
            {
                const size_t newSize = array.size() - array.typeinfo.size;
                array.count--;
                array.resize(newSize);
            }
            if (array.gpuCapacity != 0)
            {
                array.resizeGpu(platform.gpuCuda, platform.gpuCudaCtx, array.size(), array.typeinfo.size);
            }
        };

        // Reduce element count
        srcBucketImpl.scalarAttributeArrays.forEach([this, &removeLastElementFromMirroredArray](const AttrName& name, ScalarAttributeArray& array) {
            removeLastElementFromMirroredArray(array);
        });

        srcBucketImpl.arrayAttributeArrays.forEach([this, &removeLastElementFromMirroredArray](const AttrName& name, ArrayAttributeArray& array) {
            removeLastElementFromMirroredArray(array.values);
            removeLastElementFromMirroredArray(array.elemCounts);
            removeLastElementFromMirroredArray(array.cpuElemCounts);
            removeLastElementFromMirroredArray(array.gpuElemCounts);
            removeLastElementFromMirroredArray(array.gpuPtrs);
        });
    }
    srcBucketImpl.elemToPath.pop_back();

    // If bucket has more than one element, remap path that pointed to last element
    if (!deletingLastElement)
    {
        std::pair<BucketId, ArrayIndex>* movedBucketAndElemIndex;
        if (pathToBucketElem.find(movedElemPath, &movedBucketAndElemIndex))
        {
            movedBucketAndElemIndex->second = elemIndex;
        }
        else
        {
            CARB_LOG_ERROR_ONCE("destroyElement attempted to re-index missing path %s\n", Path(movedElemPath).getText());
        }
    }

    // Update change trackers
    // We allocate them lazily, so we have to iterate over listenerIdToChangeTrackerConfig
    // then allocate bucketImpl.listenerIdToChanges if necessary
    auto bucketImpl = buckets.find(bucketId);
    if (bucketImpl)
    {
        listenerIdToChangeTrackerConfig.forEach([this, &bucketImpl, &elemIndex, &lastElemIndex, &deletingLastElement](ListenerId& listenerId, ChangeTrackerConfig& config) {
            if (config.changeTrackingEnabled)
            {
                // Allocate changes if necessary
                Changes* changes;
                if (bucketImpl->listenerIdToChanges.allocateEntry(listenerId, &changes))
                {
                    new (changes) Changes();
                }

                //
                // Since we may be moving within a bucket we need to inform the change tracker
                //
                if (!deletingLastElement)
                {
                    if (changes->addedIndices.contains(lastElemIndex))
                    {
                        // only need to track that it moved if we already
                        // cared about it
                        changes->addNewPrim(elemIndex);
                    }
                    changes->removePrim(lastElemIndex);
                }
                else
                {
                    changes->removePrim(elemIndex);
                }
            }
        });
    }
}

inline void PathToAttributesMap::moveElementBetweenBuckets(const PathC& path,
                                                           BucketId destBucketId,
                                                           BucketId srcBucketId,
                                                           const Bucket& destBucket)
{
    if (destBucketId == srcBucketId)
        return;

    // Get source BucketImpl
    BucketImpl* srcPtr = buckets.find(srcBucketId);
    if (!srcPtr)
    {
        CARB_LOG_ERROR("moveElementBetweenBuckets failed to move path \"%s\" to from bucketId %zu to bucketId %zu, could not find source bucket\n", Path(path).getText(), size_t(srcBucketId), size_t(destBucketId));
        return;
    }

    // Get bucket and elem index
    std::pair<BucketId, ArrayIndex>* srcBucketAndElemIndex;
    if (!pathToBucketElem.find(path, &srcBucketAndElemIndex))
    {
        CARB_LOG_ERROR_ONCE("moveElementBetweenBuckets failed to move path \"%s\" to from bucketId %zu to bucketId %zu, could not find path\n", Path(path).getText(), size_t(srcBucketId), size_t(destBucketId));
        return;
    }

    // Get dest BucketImpl
    BucketImpl* destPtr = buckets.find(destBucketId);
    if (!destPtr)
    {
        CARB_LOG_ERROR("moveElementBetweenBuckets failed to move path \"%s\" to from bucketId %zu to bucketId %zu, could not find destination bucket\n", Path(path).getText(), size_t(srcBucketId), size_t(destBucketId));
        return;
    }

    size_t destElemIndex = PathToAttributesMap::getElementCount(*destPtr);

    // Allocate element in new bucket
    allocElementForMove(*destPtr, *srcPtr, path);

    // Copy values from src to dest
    //
    // Ideally usdValid would be driven by the change tracker
    // however I can't use that until we have a way to tie into that
    // Ideally there would be a subsscriber for "copying back to USD"
    // and that could be parsed to see if an element in invalid. At this point
    // we just have to do it per-attribute since that is as fine-grained as we
    // have data right now. This happens in moveElement to avoid having to repeat
    // logic about matching attriubte arrays that the function already does
    moveElement(*destPtr, destElemIndex, *srcPtr, srcBucketAndElemIndex->second);

    // Delete element in old bucket
    // Don't destroy data pointed to, because we want dest element to point to it
    const bool destroyDataPointedTo = false;
    destroyElement(srcBucketId, srcBucketAndElemIndex->second, destroyDataPointedTo);

    // Map path to new bucket
    *srcBucketAndElemIndex = std::make_pair(destBucketId, destElemIndex);

    // Convert destBucket to a set<AttrNameAndType>

    set<AttrNameAndType> destBucket_v2;
    destBucket_v2.v.resize(destBucket.size());
    for (size_t i = 0; i != destBucket.size(); i++)
    {
        destBucket_v2.v[i] =
            AttrNameAndType(Type(destBucket.v[i].type), Token(destBucket.v[i].name), destBucket.v[i].suffix);
    }

    // Copy dirty bits to new bucket
    srcPtr->listenerIdToChanges.forEach([&destPtr, &destBucket_v2, &destElemIndex](const ListenerId &listener, const Changes& srcChanges) {
        // Create if listenerId doesn't exist on dest bucket
        Changes* destChanges;
        if (destPtr->listenerIdToChanges.allocateEntry(listener, &destChanges))
        {
            new (destChanges) Changes();
        }

        size_t changedAttrCount = srcChanges.changedAttributes.size();
        size_t destNewElemCount = destPtr->elemToPath.size();
        for (size_t i = 0; i != changedAttrCount; i++)
        {
            const AttrNameAndType& nameAndType = srcChanges.changedAttributes.v[i];
            // TODO: we could optimize this by taking advantage of destBucket_v2
            // and changeAttributes being sorted. This would allow us to iterate
            // through both at the same time, and avoid doing n O(log n) lookups.
            if (destBucket_v2.contains(nameAndType))
            {
                destChanges->setDirty(nameAndType, destElemIndex, destNewElemCount);
            }
        }
    });
}

inline void PathToAttributesMap::addAttributeC(
    const PathC& path, const TokenC& attrName, TypeC type, const void* value)
{
    addAttributeC(path, attrName, NameSuffix::none, type, value);
}

inline void PathToAttributesMap::addArrayAttributeC(
    const PathC& path, const TokenC& attrName, TypeC type, const void* value, const size_t arrayElemCount)
{
    addArrayAttributeC(path, attrName, NameSuffix::none, type, value, arrayElemCount);
}

/**
 * @brief adds attributes to a primitive
 *
 * @details As opposed to addAttributeC this function allows the user to add multiple attributes to
 *          a primitive at the same time and only does re-bucketing once after adding all of them.
 *          This should be faster than adding them one-by-one and re-bucketing after each of them.
 * @param path - primitive path
 * @param attrNames - vector of the attribute names as tokens
 * @param tfTypes - vector of dynamic runtime types of the attributes
 * @param typeCs - vector of identifiers for types
 *
 *
 */
inline void PathToAttributesMap::addAttributesToPrim(const PathC& path,
                    const std::vector<TokenC>& attrNames,
                    const std::vector<TypeC>& typeCs)
{
    CARB_ASSERT(attrNames.size() == typeCs.size());

    addAttributesToBucket(path, attrNames, typeCs);
}

// Find bucketId the path is currently in
// Find the bucket from the bucketId
inline void PathToAttributesMap::addAttributesToBucket(const PathC& path,
                                                       const std::vector<TokenC>& attrNames,
                                                       const std::vector<TypeC>& typeCs)
{
    NameSuffix suffix = NameSuffix::none;

    BucketId srcBucketId;
    ArrayIndex srcElemIndex;
    std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);

    bool pathIsInFlatcache = (srcBucketId != kInvalidBucketId);
    if (!pathIsInFlatcache)
    {
        addPath(path);
        std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);
    }

    // Get dest bucket
    // Dest bucket types = union(source bucket types, new type)
    std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    VALIDATE_TRUE(pathToBucketElem.find(path, &bucketAndElemIndex));
    BucketImpl *const bucketImplPtr = buckets.find(bucketAndElemIndex->first);
    CARB_ASSERT(bucketImplPtr);
    Bucket destBucket = bucketImplPtr->GetBucket();
    for (uint32_t c = 0; c < attrNames.size(); ++c)
    {
        Token attrName(attrNames[c]);
        AttrNameAndType nameAndType(Type(typeCs[c]), attrName, NameSuffix::none);

        // Early out if attribute already present
        if (destBucket.find(nameAndType) != destBucket.end())
            continue;

        // When adding a new attribute that shadows the name of an existing
        // attribute, but with a new type, then we choose to drop the old attribute
        // on the floor.
        // Unfortunatly since we are searching on name since we will not know the type
        // we have to scan the list of attributes.
        for (const AttrNameAndType& bucketNameAndType : destBucket)
        {
            if (bucketNameAndType.name == attrNames[c] && bucketNameAndType.suffix == suffix &&
                TypeC(bucketNameAndType.type) != typeCs[c])
            {
                // we can stop here since this enforces uniquness of attribute names
                // todo: check that USD already enforces this
                destBucket.erase(bucketNameAndType);
                break;
            }
        }

        destBucket.insert(nameAndType);
    }

    BucketId destBucketId = addBucket(destBucket);

    if (srcBucketId != destBucketId)
    {
        moveElementBetweenBuckets(path, destBucketId, srcBucketId, destBucket);
    }
}

// Find bucketId the path is currently in
// Find the bucket from the bucketId
inline std::tuple<BucketId, ArrayIndex> PathToAttributesMap::addAttributeGetBucketAndArrayIndex(
    const PathC& path, const TokenC& attrNameC, NameSuffix nameSuffix, TypeC type)
{
    BucketId srcBucketId;
    ArrayIndex srcElemIndex;
    std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);

    bool pathIsInFlatcache = (srcBucketId != kInvalidBucketId);
    if (!pathIsInFlatcache)
    {
        addPath(path);
        std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);
    }

    // Get dest bucket
    // Dest bucket types = union(source bucket types, new type)
    std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    VALIDATE_TRUE(pathToBucketElem.find(path, &bucketAndElemIndex));
    BucketImpl *const bucketImplPtr = buckets.find(bucketAndElemIndex->first);
    CARB_ASSERT(bucketImplPtr);
    Bucket destBucket = bucketImplPtr->GetBucket();
    Token attrName(attrNameC);
    AttrNameAndType nameAndType(Type(type), attrName, nameSuffix);

    // Early out if attribute already present
    if (destBucket.find(nameAndType) != destBucket.end())
        return { srcBucketId, srcElemIndex };

    // When adding a new attribute that shadows the name of an existing
    // attribute, but with a new type, then we choose to drop the old attribute
    // on the floor.
    // Unfortunatly since we are searching on name since we will not know the type
    // we have to scan the list of attributes.
    for (const AttrNameAndType& bucketNameAndType : destBucket)
    {
        if (bucketNameAndType.name == attrNameC && bucketNameAndType.suffix == nameSuffix &&
            TypeC(bucketNameAndType.type) != type)
        {
            // we can stop here since this enforces uniquness of attribute names
            // todo: check that USD already enforces this
            destBucket.erase(bucketNameAndType);
            break;
        }
    }

    destBucket.insert(nameAndType);
    BucketId destBucketId = addBucket(destBucket);
    size_t destElemIndex;

    if (srcBucketId != destBucketId)
    {
        destElemIndex = getElementCount(destBucket);
        moveElementBetweenBuckets(path, destBucketId, srcBucketId, destBucket);
    }
    else
    {
        destElemIndex = srcElemIndex;
    }
    return { destBucketId, destElemIndex };
}

inline void PathToAttributesMap::addAttributeC(
    const PathC& path, const TokenC& attrNameC, NameSuffix nameSuffix, TypeC type, const void* value)
{
    const Typeinfo& typeinfo = getTypeInfo(type);
    if (typeinfo.isArray && value)
    {
        CARB_LOG_ERROR("addAttributeC: Attempted to add array-value attribute with default values. Use addArrayAttribute instead.");
        return;
    }
    addAttributeInternal(path, attrNameC, nameSuffix, type, value, typeinfo, 0);
}

inline void PathToAttributesMap::addArrayAttributeC(const PathC& path, const TokenC& attrName, NameSuffix suffix, TypeC type, const void* value, const size_t arrayElemCount)
{
    const Typeinfo& typeinfo = getTypeInfo(type);
    addAttributeInternal(path, attrName, suffix, type, value, typeinfo, arrayElemCount);
}

inline SpanC PathToAttributesMap::getOrCreateAttributeWrC(const PathC& path,
                                                          const TokenC& attrName,
                                                          TypeC type)
{
    APILOGGER("getOrCreateAttributeWrC", apiLogEnabled, path, attrName);

    BucketId bucketId;
    ArrayIndex elemIndex;
    std::tie(bucketId, elemIndex) = addAttributeGetBucketAndArrayIndex(path, attrName, NameSuffix::none, type);

    ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(bucketId, attrName, CpuReadWriteConfig(), NameSuffix::none);
    setArrayElementDirty(arrayAndchangedIndices, elemIndex);

    SpanC array = arrayAndchangedIndices.array;
    return getArrayElementPtr(array, elemIndex);
}

template <typename T>
void PathToAttributesMap::addAttribute(
    const PathC& path, const TokenC& attrName, TypeC type, const T& value)
{
    APILOGGER("addAttribute", apiLogEnabled, path, attrName);

    // TODO: check that type is compatible
    return addAttributeC(path, attrName, type, &value);
}

template <typename T>
void PathToAttributesMap::addSubAttribute(
    const PathC& path, const TokenC& attrName, NameSuffix suffix, TypeC type, const T& value)
{
    APILOGGER("addSubAttribute", apiLogEnabled, path, attrName);

    // TODO: check that type is compatible
    return addAttributeC(path, attrName, suffix, type, &value);
}

// Return a new bucket with all sub-attributes of a single attribute removed
inline Bucket removeAllSubAttributesFromBucket(const Bucket& bucket, const TokenC& attrName)
{
    Bucket newBucket;
    // TODO: implement set::delete
    for (auto nameAndType : bucket)
    {
        // Don't compare suffix and type to delete all suffix variants of name
        if (nameAndType.name != attrName)
        {
            newBucket.insert(nameAndType);
        }
    }

    return newBucket;
}

// Return a new bucket with all sub-attributes of all named attributes removed
inline Bucket removeAllSubAttributesFromBucket(const Bucket& bucket, const std::vector<TokenC>& attrNames)
{
    Bucket newBucket;

    for (auto nameAndType : bucket)
    {
        if (std::find_if(attrNames.begin(), attrNames.end(),
                         [&](auto attrName) { return nameAndType.name == attrName; }) == attrNames.end())
        {
            newBucket.insert(nameAndType);
        }
    }

    return newBucket;
}

inline Bucket removeSubAttributeFromBucket(const Bucket& bucket, const TokenC& attrName, NameSuffix suffix)
{
    Bucket newBucket;
    // TODO: implement set::delete
    for (auto nameAndType : bucket)
    {
        // Don't compare suffix and type to delete all suffix variants of name
        if (!(nameAndType.name == attrName && nameAndType.suffix == suffix))
        {
            newBucket.insert(nameAndType);
        }
    }

    return newBucket;
}

// Remove an attribute and all its subattributes (suffixes).
inline void PathToAttributesMap::removeAttribute(const PathC& path, const TokenC& attrName)
{
    APILOGGER("removeAttribute", apiLogEnabled, path, attrName);

    BucketId srcBucketId;
    ArrayIndex srcElemIndex;
    std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);

    if (srcBucketId == kInvalidBucketId)
        return;

    // srcBucketId != kInvalidBucketId guarantees find will succeed
    std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    VALIDATE_TRUE(pathToBucketElem.find(path, &bucketAndElemIndex));
    BucketImpl *const bucketImplPtr = buckets.find(bucketAndElemIndex->first);
    CARB_ASSERT(bucketImplPtr);
    const Bucket& srcTypes = bucketImplPtr->GetBucket();
    const Bucket destBucket = removeAllSubAttributesFromBucket(srcTypes, attrName);

    const BucketId destBucketId = addBucket(destBucket);
    moveElementBetweenBuckets(path, destBucketId, srcBucketId, destBucket);
}

inline void PathToAttributesMap::removeAttributesFromPath(const PathC& path, const std::vector<TokenC>& attrNames)
{
    BucketId srcBucketId;
    ArrayIndex srcElemIndex;
    std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);

    if (srcBucketId == kInvalidBucketId)
        return;

    // srcBucketId != kInvalidBucketId guarantees find will succeed
    std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    VALIDATE_TRUE(pathToBucketElem.find(path, &bucketAndElemIndex));
    BucketImpl *const bucketImplPtr = buckets.find(bucketAndElemIndex->first);
    CARB_ASSERT(bucketImplPtr);
    const Bucket& bucket = bucketImplPtr->GetBucket();
    const Bucket destBucket = removeAllSubAttributesFromBucket(bucket, attrNames);

    const BucketId destBucketId = addBucket(destBucket);
    if (srcBucketId != destBucketId)
    {
        moveElementBetweenBuckets(path, destBucketId, srcBucketId, destBucket);
    }
}


inline void PathToAttributesMap::removeAttributesFromBucket(const Bucket& bucket, const std::vector<TokenC>& attrNames)
{
    // first we need to find the actual bucketImpl that we will be
    // deleting attributes from
    auto iter = attrNameSetToBucketId.find(bucket);
    bool found = (iter != attrNameSetToBucketId.end());
    if (!found)
        return;

    BucketId bucketId = iter->second;
    BucketImpl* bucketImplPtr = buckets.find(bucketId);
    if (!bucketImplPtr)
        return;

    // Buckets are found based on a set of the attributes, so we build
    // the new set based on the attribute names
    Bucket newBucket = removeAllSubAttributesFromBucket(bucket, attrNames);
    std::pair<BucketId, BucketImpl&> newBucketIdAndImpl = findOrCreateBucket(newBucket);
    BucketImpl& newBucketImpl = newBucketIdAndImpl.second;

    const size_t origSize = newBucketImpl.elemToPath.size();
    if (origSize == 0)
    {
        // In the case where it is a new bucket we prefer just deleting the no longer needed arrays.
        newBucketImpl = *bucketImplPtr;
        newBucketImpl.SetBucket(std::move(newBucket));

        // loop finding and deleting attribute arrays
        for (auto attrName : attrNames)
        {
            newBucketImpl.scalarAttributeArrays.forEach([this, &attrName, &newBucketImpl](const AttrName& name, ScalarAttributeArray& array) {
                if (name.name == attrName)
                {
                    newBucketImpl.scalarAttributeArrays.freeEntry(name);
                }
            });

            newBucketImpl.arrayAttributeArrays.forEach([this, &attrName, &newBucketImpl](const AttrName& name, ArrayAttributeArray& array) {
                if (name.name == attrName)
                {
                    newBucketImpl.arrayAttributeArrays.freeEntry(name);
                }
            });
        }
    }
    else
    {
        // TODO : there should be a faster way to do this but more to discuss here later
        for (const auto path : bucketImplPtr->elemToPath)
        {
            moveElementBetweenBuckets(
                asInt(path), newBucketIdAndImpl.first, bucketId, newBucket);
        }
    }

    //
    // need to update the pathToBucketElem for all the items that just "moved" buckets
    // TODO: make this work with moving buckets
    for (size_t i = origSize; i < newBucketImpl.elemToPath.size(); ++i)
    {
        std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
        pathToBucketElem.allocateEntry(asInt(newBucketImpl.elemToPath[i]), &bucketAndElemIndex);
        *bucketAndElemIndex = std::make_pair(newBucketIdAndImpl.first, i);
    }

    buckets.erase(bucketId);
    attrNameSetToBucketId.erase(bucket);
}

// Remove a particular (name,suffix) pair, for example the connection of an attribute
inline void PathToAttributesMap::removeSubAttribute(const PathC& path, const TokenC& attrName, NameSuffix suffix)
{
    APILOGGER("removeSubAttribute", apiLogEnabled, path, attrName);

    BucketId srcBucketId;
    ArrayIndex srcElemIndex;
    std::tie(srcBucketId, srcElemIndex) = getBucketAndArrayIndex(path);
    if (srcBucketId == kInvalidBucketId)
        return;
    // srcBucketId != kInvalidBucketId guarantees find will succeed

    std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    VALIDATE_TRUE(pathToBucketElem.find(path, &bucketAndElemIndex));
    BucketImpl *const bucketImplPtr = buckets.find(bucketAndElemIndex->first);
    CARB_ASSERT(bucketImplPtr);
    const Bucket& srcTypes = bucketImplPtr->GetBucket();
    bool pathFound = (srcBucketId != kInvalidBucketId);
    if (!pathFound)
    {
        CARB_LOG_ERROR_ONCE("removeSubAttribute called on non-existent path %s \n", Path(path).getText());
        return;
    }

    const Bucket destBucket = removeSubAttributeFromBucket(srcTypes, attrName, suffix);

    const BucketId destBucketId = addBucket(destBucket);
    moveElementBetweenBuckets(path, destBucketId, srcBucketId, destBucket);
}

// Removes an attribute (and all its subattributes) for all paths in a bucket
inline void PathToAttributesMap::removeAttributeC(const Bucket& bucket,
                                                  const TokenC& attrName,
                                                  TypeC type)
{
    APILOGGER("removeAttributeC", apiLogEnabled, attrName);

    // first we need to find the actual bucketImpl that we will be
    // deleting attributes from
    auto iter = attrNameSetToBucketId.find(bucket);
    bool found = (iter != attrNameSetToBucketId.end());
    if (!found)
        return;
    BucketId bucketId = iter->second;
    BucketImpl* bucketImplPtr = buckets.find(bucketId);
    if (!bucketImplPtr)
        return;

    // Buckets are found based on a set of the attributes, so we build
    // the new set based on the attribute names
    Bucket newBucket = removeAllSubAttributesFromBucket(bucket, attrName);

    BucketId newBucketId = findBucketId(newBucket);

    if (newBucketId == kInvalidBucketId)
    {
        // In the case where it is a new bucket we prefer just deleting the no longer needed arrays.
        // This means that nothing needs to be updated as all the prims are in the same place
        bucketImplPtr->SetBucket(std::move(newBucket));

        if (getTypeInfo(type).isArray)
        {
            bucketImplPtr->arrayAttributeArrays.forEach([this, &attrName, bucketImplPtr](const AttrName& name, ArrayAttributeArray& array) {
                if (name.name == attrName)
                {
                    bucketImplPtr->arrayAttributeArrays.freeEntry(name);
                }
            });
        }
        else
        {
            bucketImplPtr->scalarAttributeArrays.forEach([this, &attrName, bucketImplPtr](const AttrName& name, ScalarAttributeArray& array) {
                if (name.name == attrName)
                {
                    bucketImplPtr->scalarAttributeArrays.freeEntry(name);
                }
            });
        }
        attrNameSetToBucketId[newBucket] = bucketId;
        attrNameSetToBucketId.erase(bucket);
    }
    else
    {
        std::pair<BucketId, BucketImpl&> newBucketIdAndImpl = findOrCreateBucket(newBucket);
        BucketImpl& newBucketImpl = newBucketIdAndImpl.second;
        const size_t origSize = newBucketImpl.elemToPath.size();

        // TODO : there should be a faster way to do this but more to discuss here later
        // currently this pulls from the front, this ensures that elements stay in the same
        // "order" when moving buckets -> but this means moving stuff around in elemToPath
        // Doing this in "bulk" will make all of this better.
        while(bucketImplPtr->elemToPath.size())
        {
            moveElementBetweenBuckets(
                asInt(bucketImplPtr->elemToPath.front()), newBucketIdAndImpl.first, bucketId, newBucket);
        }

        //
        // need to update the pathToBucketElem for all the items that just "moved" buckets
        // TODO: make this work with moving buckets
        for (size_t i = origSize; i < newBucketImpl.elemToPath.size(); ++i)
        {
            std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
            pathToBucketElem.allocateEntry(asInt(newBucketImpl.elemToPath[i]), &bucketAndElemIndex);
            *bucketAndElemIndex = std::make_pair(newBucketIdAndImpl.first, i);
        }
    }
}

inline void PathToAttributesMap::removePath(const PathC& path)
{
    std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    if (!pathToBucketElem.find(path, &bucketAndElemIndex))
    {
        CARB_LOG_ERROR_ONCE("removePath called on non-existent path %s \n", Path(path).getText());
        return;
    }

    const BucketId &bucketId = bucketAndElemIndex->first;
    const size_t &elemIndex = bucketAndElemIndex->second;
    const bool destroyDataPointedTo = true;
    destroyElement(bucketId, elemIndex, destroyDataPointedTo);

    pathToBucketElem.freeEntry(path);
}

inline size_t PathToAttributesMap::count(const PathC& path) const
{
    const std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
    if (pathToBucketElem.find(path, &bucketAndElemIndex))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

struct ViewIterator
{
    size_t bucketIndex = 0;
    size_t elementIndex = 0;
    std::vector<size_t>::const_iterator bucketElemCount;

    ViewIterator& operator++()
    {
        elementIndex++;
        if (elementIndex == *bucketElemCount)
        {
            bucketIndex++;
            bucketElemCount++;
            elementIndex = 0;
        }
        return *this;
    }

    bool operator!=(const ViewIterator& rhs) const
    {
        return bucketIndex != rhs.bucketIndex || elementIndex != rhs.elementIndex;
    }

    ViewIterator& operator*()
    {
        return *this;
    }
};

// Array resize that does not preserve previous data
inline void PathToAttributesMap::destructiveResizeIfNecessaryGPU(MirroredArray& gpuPointerArray,
                                                                 size_t elem,
                                                                 size_t& capacity,
                                                                 size_t desiredElemCount,
                                                                 size_t elemByteCount,
                                                                 omni::gpucompute::GpuCompute* computeAPI,
                                                                 omni::gpucompute::Context* computeCtx)
{
        uint8_t** elemToArrayGpuData = reinterpret_cast<uint8_t**>(gpuPointerArray.cpuData());
        uint8_t*& gpuData = elemToArrayGpuData[elem];

    // Resize iff (capacity < desiredElemCount)
    if (capacity != desiredElemCount || gpuData == nullptr)
    {
        size_t byteCount = desiredElemCount * elemByteCount;
        if (gpuData)
        {
            platform.gpuCuda->freeAsync(*platform.gpuCudaCtx, gpuData);
        }
        gpuData = reinterpret_cast<uint8_t*>(computeAPI->mallocAsync(*computeCtx, byteCount, elemByteCount));
        // We've written to gpuData on the CPU so we have to invalidate any GPU mirror of it
        gpuPointerArray.gpuValid = false;
        gpuPointerArray.cpuValid = true;

        capacity = desiredElemCount;
    }
}

// Array resize that preserves previous data
inline void PathToAttributesMap::resizeIfNecessaryGPU(MirroredArray& gpuPointerArray,
                                                      size_t elem,
                                                      size_t& capacity,
                                                      size_t desiredElemCount,
                                                      size_t elemByteCount,
                                                      omni::gpucompute::GpuCompute* computeAPI,
                                                      omni::gpucompute::Context* computeCtx)
{
    // TODO: reduce number of reallocations by allocating capacity larger than size
    // and not always reallocating when desiredElemCount<capacity
    // if gpuCapacity is 0 that means the array was recently copied and needs to be reallocated
    if(computeAPI && (capacity != desiredElemCount || gpuPointerArray.gpuCapacity == 0))
    {
        size_t oldByteCount = capacity * elemByteCount;
        size_t newByteCount = desiredElemCount * elemByteCount;

        uint8_t** elemToArrayGpuData = reinterpret_cast<uint8_t**>(gpuPointerArray.cpuData());
        uint8_t*& gpuData = elemToArrayGpuData[elem];

        uint8_t* newGpuData = reinterpret_cast<uint8_t*>(computeAPI->mallocAsync(*computeCtx, newByteCount, elemByteCount));

        if (gpuData)
        {
            using omni::gpucompute::MemcpyKind;
            size_t copyByteCount = std::min(oldByteCount, newByteCount);
            computeAPI->memcpy(*computeCtx, newGpuData, gpuData, copyByteCount, MemcpyKind::deviceToDevice);

            // Note that this free has to be async even though the previous
            // memcpy is sync. The reason is that deviceToDevice memcpys
            // are always async, even if you call the sync version of cudaMemcpy.
            // So if you do "sync" memcpy and then sync free, the free can
            // execute on the CPU before the copy executes on the GPU.
            // See https://nvidia-omniverse.atlassian.net/browse/OM-46051
            computeAPI->freeAsync(*computeCtx, gpuData);
        }
        gpuData = newGpuData;
        // We've written to gpuData on the CPU so we have to invalidate any GPU mirror of it
        gpuPointerArray.gpuValid = false;
        gpuPointerArray.cpuValid = true;

        capacity = desiredElemCount;
    }
}

// This function is called when we are just about to do a transfer to GPU, to
// make sure that GPU array is large enough.
// It is called only when !gpuValid, so we don't have to preserve any existing
// GPU array.
//
// Algorithm:
// If capacity is sufficient, do nothing
// If not, free any existing allocation, then allocate

inline void PathToAttributesMap::allocGpuMemIfNecessary(PathToAttributesMap::MirroredArray& array,
                                                        size_t byteCount,
                                                        size_t elemSize,
                                                        omni::gpucompute::GpuCompute* computeAPI,
                                                        omni::gpucompute::Context* computeCtx)
{
    bool capacitySufficient = (byteCount <= array.gpuCapacity);
    if (!capacitySufficient)
    {
        if (array.gpuArray)
        {
            computeAPI->freeAsync(*computeCtx, array.gpuArray);
        }

        array.gpuArray = reinterpret_cast<uint8_t*>(computeAPI->mallocAsync(*computeCtx, byteCount, elemSize));
        array.gpuCapacity = byteCount;
    }
}

inline PrimBucketListImpl PathToAttributesMap::getChanges(ListenerId listenerId)
{
    PrimBucketListImpl changesOut;

    // For now, iterate over all buckets
    // We'll probably want the user to specify a subset of buckets for change logging

    changesOut.buckets.reserve(buckets.end());
    changesOut.changes.reserve(buckets.end());
    BucketId id{ 0 };
    for (unsigned int i = 0; i < buckets.end(); ++i, ++id)
    {
        BucketImpl* bucketPtr = buckets.find(id);
        if (!bucketPtr)
            continue;

        BucketImpl& bucketImpl = *bucketPtr;
        BucketId bucketId = id;

        Changes* changesIn;
        if (!bucketImpl.listenerIdToChanges.find(listenerId, &changesIn))
        {
            continue;
        }

        size_t changedAttrCount = changesIn->changedAttributes.size();
        size_t primCount = bucketImpl.elemToPath.size();

        bool attributesChanged = (changedAttrCount != 0 && primCount != 0);
        bool primsAdded = (changesIn->getNewPrimCount() != 0);

        if (attributesChanged || primsAdded)
        {
            changesOut.buckets.v.push_back(bucketId);
            changesOut.changes.push_back(BucketChangesImpl());
            BucketChangesImpl& bucketChanges = changesOut.changes.back();

            // Write changed attributes
            bucketChanges.changedAttributes = changesIn->changedAttributes;
            bucketChanges.changedIndices.resize(changedAttrCount);
            for (size_t j = 0; j != changedAttrCount; j++)
            {
                bucketChanges.changedIndices[j] = { changesIn->changedIndices[j].allIndicesChanged,
                                                    { changesIn->changedIndices[j].changedIndices.data(),
                                                      changesIn->changedIndices[j].changedIndices.size() } };
            }
            bucketChanges.pathArray = { reinterpret_cast<const Path*>(bucketImpl.elemToPath.data()),
                                        bucketImpl.elemToPath.size() };

            // Write added prims
            bucketChanges.addedIndices = { changesIn->addedIndices.data(), changesIn->addedIndices.size() };
        }
    }

    return changesOut;
}

inline void PathToAttributesMap::popChanges(ListenerId listenerId)
{
    BucketId id{ 0 };
    for (unsigned int i = 0; i < buckets.end(); ++i, ++id)
    {
        BucketImpl* bucketPtr = buckets.find(id);
        if (bucketPtr)
        {
            // Create listenerId if it doesn't exist
            Changes* changes;
            if (bucketPtr->listenerIdToChanges.allocateEntry(listenerId, &changes))
            {
                new (changes) Changes;
            }
            changes->changedAttributes.clear();
            changes->changedIndices.clear();
            changes->addedIndices.clear();
        }
    }
}


inline PathToAttributesMap::MirroredArray::MirroredArray(Platform& platform_, const TypeC &type, const Typeinfo& typeinfo) noexcept
    : cpuArray()
    , platform(platform_)
    , type(type)
    , typeinfo(typeinfo)
    , gpuArray(nullptr)
    , gpuCapacity(0)
    , d3dArrays()
    , count(0)
    , usdValid(true)
    , cpuValid(false)
    , gpuValid(false)
    , gpuAllocedWithCuda(false)
    , attributeMutex()
{
}


inline PathToAttributesMap::MirroredArray::~MirroredArray()
{
    // clean up any non-array gpu data
    if (gpuArray)
    {
        if (gpuAllocedWithCuda)
        {
            platform.gpuCuda->freeAsync(*platform.gpuCudaCtx, gpuArray);
        }
        else
        {
            // @TODO Fix crash during D3dVk free! N.B. that this backend is incomplete and not in active use
            // gpuD3dVk->freeAsync(*gpuD3dVkCtx, gpuArray);
        }
        gpuArray = nullptr;
    }
    gpuValid = false;
}


inline PathToAttributesMap::MirroredArray& PathToAttributesMap::MirroredArray::operator=(const MirroredArray& other) noexcept
{
    if (!other.isArrayOfArray())
    {
        cpuArray = other.cpuArray;
    }
    else
    {
        // Here we set all pointers in dest array to nullptr
        // The allocation and data copy happens in PathToAttributesMap's operator=
        cpuArray.resize(other.size());
        uint8_t** destPtrs = reinterpret_cast<uint8_t**>(cpuData());
        for (size_t elemIndex = 0; elemIndex != other.count; elemIndex++)
        {
            destPtrs[elemIndex] = nullptr;
        }
    }

    // platform = other.platform; // intentionally not copy-assigning platform
    type = other.type;
    typeinfo = other.typeinfo;
    usdValid = other.usdValid;
    cpuValid = other.cpuValid;
    count = other.count;

    // GPU data needs to be copied explicitly using the gpu compute API
    gpuArray = nullptr;
    gpuCapacity = 0;
    gpuValid = false;
    gpuAllocedWithCuda = false;

    if (other.gpuValid)
    {
        // Also need to empty the cpuArray as it is a cpu pointer to now-invalid GPU data
        uint8_t** destPtrs = reinterpret_cast<uint8_t**>(cpuData());
        for (size_t elemIndex = 0; elemIndex != other.count; elemIndex++)
        {
            destPtrs[elemIndex] = nullptr;
        }
    }

    return *this;
}


inline PathToAttributesMap::MirroredArray::MirroredArray(MirroredArray&& other) noexcept
    : cpuArray(std::move(other.cpuArray)),
      platform(other.platform),
      type(other.type),
      typeinfo(other.typeinfo),
      gpuArray(other.gpuArray),
      gpuCapacity(other.gpuCapacity),
      d3dArrays(std::move(other.d3dArrays)),
      count(other.count),
      usdValid(other.usdValid),
      cpuValid(other.cpuValid),
      gpuValid(other.gpuValid),
      gpuAllocedWithCuda(other.gpuAllocedWithCuda),
      attributeMutex() // intentionally not move constructing the mutex
{
    other.gpuArray = nullptr;
}


inline PathToAttributesMap::MirroredArray& PathToAttributesMap::MirroredArray::operator=(MirroredArray&& other) noexcept
{
    MirroredArray tmp(std::move(other));
    swap(*this, tmp);
    return *this;
}


inline void swap(PathToAttributesMap::MirroredArray& a, PathToAttributesMap::MirroredArray& b) noexcept
{
    using std::swap;
    swap(a.cpuArray, b.cpuArray);
    swap(a.type, b.type);
    swap(a.typeinfo, b.typeinfo);
    swap(a.gpuArray, b.gpuArray);
    swap(a.gpuCapacity, b.gpuCapacity);
    swap(a.d3dArrays, b.d3dArrays);
    swap(a.count, b.count);
    swap(a.usdValid, b.usdValid);
    swap(a.cpuValid, b.cpuValid);
    swap(a.gpuValid, b.gpuValid);
    swap(a.gpuAllocedWithCuda, b.gpuAllocedWithCuda);
    // swap(a.attributeMutex, b.attributeMutex); // intentionally NOT swapping attribute mutex because it is not move-constructable
}


inline PathToAttributesMap::ArrayAttributeArray::ArrayAttributeArray(Platform& platform_, const TypeC& type, const Typeinfo& typeinfo) noexcept
    : values(platform_, type, typeinfo)
    , elemCounts(platform_, PTAM_SIZE_TYPEC, Typeinfo{sizeof(PTAM_SIZE_TYPE), false, 0})
    , cpuElemCounts(platform_, PTAM_SIZE_TYPEC, Typeinfo{ sizeof(PTAM_SIZE_TYPE), false, 0 })
    , gpuElemCounts(platform_, PTAM_SIZE_TYPEC, Typeinfo{ sizeof(PTAM_SIZE_TYPE), false, 0 })
    , gpuPtrs(platform_, PTAM_POINTER_TYPEC, Typeinfo{ sizeof(PTAM_POINTER_TYPE), false, 0 })
{
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
}


inline PathToAttributesMap::ArrayAttributeArray::~ArrayAttributeArray()
{
    Platform& platform = values.platform;
    CARB_ASSERT(&platform == &elemCounts.platform);
    CARB_ASSERT(&platform == &cpuElemCounts.platform);
    CARB_ASSERT(&platform == &gpuElemCounts.platform);
    CARB_ASSERT(&platform == &gpuPtrs.platform);

    if (values.count)
    {
        uint8_t** elemToCpuPtr = reinterpret_cast<uint8_t**>(values.cpuData());
        for (size_t elemIndex = 0; elemIndex != values.count; elemIndex++)
        {
            // If a CPU array has been allocated, free it
            uint8_t*& cpuPtrToDelete = elemToCpuPtr[elemIndex];

            if (cpuPtrToDelete)
            {
                if (!USE_PINNED_MEMORY || !platform.gpuCuda)
                {
                    free(cpuPtrToDelete);
                }
                else if (platform.gpuCuda)
                {
                    platform.gpuCuda->freeHost(*platform.gpuCudaCtx, cpuPtrToDelete);
                }
                cpuPtrToDelete = nullptr;
                values.cpuValid = false;
            }
        }
    }

    if (gpuPtrs.count)
    {
        // CPU array of GPU pointers
        uint8_t** elemToGpuPtr = reinterpret_cast<uint8_t**>(gpuPtrs.cpuData());
        for (size_t elemIndex = 0; elemIndex != gpuPtrs.count; elemIndex++)
        {
            // If a GPU array has been allocated, free it
            uint8_t*& gpuPtrToDelete = elemToGpuPtr[elemIndex];
            if (gpuPtrToDelete)
            {
                CARB_ASSERT(platform.gpuCuda);
                CARB_ASSERT(platform.gpuCudaCtx);
                platform.gpuCuda->freeAsync(*platform.gpuCudaCtx, gpuPtrToDelete);
                gpuPtrToDelete = nullptr;
            }
        }
    }
}


inline PathToAttributesMap::ArrayAttributeArray& PathToAttributesMap::ArrayAttributeArray::operator=(const ArrayAttributeArray& other) noexcept
{
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");

    values = other.values;
    elemCounts = other.elemCounts;
    cpuElemCounts = other.cpuElemCounts;
    gpuElemCounts = other.gpuElemCounts;
    gpuPtrs = other.gpuPtrs;

    return *this;
}


inline PathToAttributesMap::ArrayAttributeArray::ArrayAttributeArray(ArrayAttributeArray&& other) noexcept
    : values(std::move(other.values))
    , elemCounts(std::move(other.elemCounts))
    , cpuElemCounts(std::move(other.cpuElemCounts))
    , gpuElemCounts(std::move(other.gpuElemCounts))
    , gpuPtrs(std::move(other.gpuPtrs))
{
    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");

    other.values.count = 0;
    other.elemCounts.count = 0;
    other.cpuElemCounts.count = 0;
    other.gpuElemCounts.count = 0;
    other.gpuPtrs.count = 0;
}


inline PathToAttributesMap::ArrayAttributeArray& PathToAttributesMap::ArrayAttributeArray::operator=(ArrayAttributeArray&& other) noexcept
{
    ArrayAttributeArray tmp(std::move(other));
    swap(*this, tmp);
    return *this;
}


inline void swap(PathToAttributesMap::ArrayAttributeArray& a, PathToAttributesMap::ArrayAttributeArray& b) noexcept
{
    using std::swap;
    swap(a.values, b.values);
    swap(a.elemCounts, b.elemCounts);
    swap(a.cpuElemCounts, b.cpuElemCounts);
    swap(a.gpuElemCounts, b.gpuElemCounts);
    swap(a.gpuPtrs, b.gpuPtrs);
}

inline void PathToAttributesMap::printBucket(const Bucket& bucket) const
{
    bool multiLine = (1 < bucket.size());
    printf("{");
    if (multiLine)
        printf("\n");
    for (const auto& b : bucket)
    {
        TokenC attrName = b.name;
        NameSuffix suffix = b.suffix;
        Type type(b.type);
        if (multiLine)
            printf("    ");
        Token attrNameToken(attrName);
        std::cout << "TypeC(" << type << ") " << attrNameToken.getText() << suffix;

        if (multiLine)
            printf("\n");
    }
    printf("} ");

    // Print arrays in bucket
    auto iter = attrNameSetToBucketId.find(bucket);
    bool found = (iter != attrNameSetToBucketId.end());
    if (!found)
        return;

    BucketId bucketId = iter->second;
    auto bucketImplPtr = buckets.find(bucketId);
    if (bucketImplPtr)
    {
        const BucketImpl& bucketImpl = *bucketImplPtr;
        bucketImpl.scalarAttributeArrays.forEach([&multiLine](const AttrName& name, const ScalarAttributeArray& array) {
#if ENABLE_USD_DEBUGGING
            std::cout << toTfToken(name.name).GetText() << " " << toString(name.suffix) << " ";
#else
            std::cout << name.name.token << " ";
#endif
            std::cout << array.size() << "bytes ";

            if (multiLine)
                std::cout << "\n";
        });
        bucketImpl.arrayAttributeArrays.forEach([&multiLine](const AttrName& name, const ArrayAttributeArray& array) {
#if ENABLE_USD_DEBUGGING
            std::cout << toTfToken(name.name).GetText() << " " << toString(name.suffix) << " ";
#else
            std::cout << name.name.token << " ";
#endif
            std::cout << array.values.size() << "bytes ";

            if (multiLine)
                std::cout << "\n";
        });
        }
        }

inline void PathToAttributesMap::printBucketName(const Bucket& bucketTypes, BucketId bucketId) const
{
    const BucketImpl* bucketImplPtr = buckets.find(bucketId);
    if (!bucketImplPtr)
        return;

    const BucketImpl& bucketImpl = *bucketImplPtr;

    std::cout << "Id: " << size_t(bucketId) << " ";

    size_t bucketPrimCount = bucketImpl.elemToPath.size();
    std::cout << "PrimCount: " << bucketPrimCount << " ";

    // Find USD prim type
    for (auto attrNameAndType : bucketTypes)
    {
        Type type(attrNameAndType.type);
        if (type.role == AttributeRole::ePrimTypeName)
        {
            Token nameToken(attrNameAndType.name);
            std::cout << "PrimType: " << nameToken.getText() << " ";
        }
    }

    std::cout << "AttributeNames: ";
    for (auto attrNameAndType : bucketTypes)
    {
        Token nameToken(attrNameAndType.name);
        std::cout << nameToken.getText() << toString(attrNameAndType.suffix) << " ";
    }
    std::cout << "\n";
}

inline void PathToAttributesMap::printBucketNames() const
{
    std::cout << "Buckets:\n";
    for (auto& bucketIdAndBucket : attrNameSetToBucketId)
    {
        const Bucket& bucketTypes = bucketIdAndBucket.first;
        BucketId bucketId = bucketIdAndBucket.second;

        std::cout << "  ";
        printBucketName(bucketTypes, bucketId);
    }
}

inline void PathToAttributesMap::printBucketNamesAndTypes() const
{
    std::cout << "Buckets:\n";
    for (auto& bucketIdAndBucket : attrNameSetToBucketId)
    {
        std::cout << "  ";
        const Bucket& bucketTypes = bucketIdAndBucket.first;
        for (AttrNameAndType attrNameAndType : bucketTypes)
        {
            Type type(attrNameAndType.type);
            Token nameToken(attrNameAndType.name);
            std::cout << "(" << type << " " << nameToken.getText() << " " << attrNameAndType.suffix << " "
                      << "TypeC(" << attrNameAndType.type << ") ";
        }
        std::cout << "\n";
    }
}

inline void PathToAttributesMap::bucketImplCopyScalarAttributeArray(ScalarAttributeArray &dest, const ScalarAttributeArray &src)
{
    CARB_ASSERT(dest.type == src.type);
    if (src.gpuValid)
    {
        dest.resizeGpu(platform.gpuCuda, platform.gpuCudaCtx, src.size(), dest.typeinfo.size);
        platform.gpuCuda->memcpyAsync(*platform.gpuCudaCtx, dest.gpuArray, src.gpuArray, src.gpuCapacity, omni::gpucompute::MemcpyKind::deviceToDevice);
        dest.gpuValid = true;
        dest.gpuCapacity = src.gpuCapacity;
        dest.gpuAllocedWithCuda = src.gpuAllocedWithCuda;
    }
}

inline void PathToAttributesMap::bucketImplCopyArrayAttributeArray(BucketImpl& destBucketImpl, const AttrName& destName, ArrayAttributeArray &dest, const ArrayAttributeArray &src)
{
    CARB_ASSERT(dest.values.type == src.values.type);
    const Typeinfo &typeInfo = dest.values.typeinfo;
    const size_t arrayElemSize = typeInfo.arrayElemSize;

    MirroredArray *const destSizeArray = &dest.elemCounts;
    MirroredArray *const destCpuCapacityArray = &dest.cpuElemCounts;
    const ArrayOfArrayInfo destAOA = getArrayOfArrayInfo(dest);

    // TODO: Figure out how to remove this fixup step in a more "clean" way
    // Need to set capacity to zero, because capacity will
    // have been erroneously copied from source in
    // MirroredArray copy constructor
    ArrayAndDirtyIndices arrayAndchangedIndices = getArraySpanC(*destCpuCapacityArray, destName, destAOA, destBucketImpl, CpuWriteConfig());
    setArrayDirty(arrayAndchangedIndices);

    SpanC destCapacitySpan = arrayAndchangedIndices.array;
    size_t* destCapacities = reinterpret_cast<size_t*>(destCapacitySpan.ptr);
    for (size_t elemIndex = 0; elemIndex != destCapacitySpan.elementCount; elemIndex++)
    {
        destCapacities[elemIndex] = 0;
    }

    // getArrayWrC to allocate data for arrays
    ArrayAndDirtyIndices destSpan = getArraySpanC(dest.values, destName, destAOA, destBucketImpl, CpuWriteConfig());
    setArrayDirty(destSpan);

    const size_t* elemCounts = reinterpret_cast<const size_t*>(destSizeArray->cpuData());

    if (src.values.cpuValid)
    {
        // TODO: Isn't this redundant with the call to getArraySpanC above with cpu write access?
        enableCpuWrite(dest.values, elemCounts, destCpuCapacityArray, nullptr, nullptr);

        uint8_t** destPtrs = reinterpret_cast<uint8_t**>(destSpan.array.ptr);
        uint8_t* const* srcPtrs = reinterpret_cast<uint8_t* const*>(src.values.cpuData());
        for (size_t elemIndex = 0; elemIndex != destSpan.array.elementCount; elemIndex++)
        {
            uint8_t* destPtr = destPtrs[elemIndex];
            const uint8_t* srcPtr = srcPtrs[elemIndex];
            size_t sizeBytes = elemCounts[elemIndex] * arrayElemSize;

            memcpy(destPtr, srcPtr, sizeBytes);
        }
    }
    else
    {
        dest.values.cpuValid = false;
    }

    if (src.values.gpuValid)
    {
        MirroredArray *const destGpuElemCountArray = &dest.gpuElemCounts;
        MirroredArray *const destGpuPtrArray = &dest.gpuPtrs;
        enableGpuWrite(dest.values, elemCounts, destCpuCapacityArray, destGpuElemCountArray, destGpuPtrArray);

        const MirroredArray *const srcGpuPtrArray = &src.gpuPtrs;

        // Select which API to use
        omni::gpucompute::GpuCompute* computeAPI = nullptr;
        omni::gpucompute::Context* computeCtx = nullptr;
        if (src.values.gpuAllocedWithCuda)
        {
            computeAPI = platform.gpuCuda;
            computeCtx = platform.gpuCudaCtx;
        }
        if (computeAPI)
        {
            uint8_t** destPtrs = reinterpret_cast<uint8_t**>(destGpuPtrArray->cpuData());
            uint8_t* const* srcPtrs = reinterpret_cast<uint8_t* const*>(srcGpuPtrArray->cpuData());
            for (size_t elemIndex = 0; elemIndex != destSpan.array.elementCount; elemIndex++)
            {
                uint8_t* destPtr = destPtrs[elemIndex];
                const uint8_t* srcPtr = srcPtrs[elemIndex];
                size_t sizeBytes = elemCounts[elemIndex] * arrayElemSize;

                computeAPI->memcpyAsync(*computeCtx, destPtr, srcPtr, sizeBytes, omni::gpucompute::MemcpyKind::deviceToDevice);
            }
            destGpuPtrArray->gpuAllocedWithCuda = src.values.gpuAllocedWithCuda;
        }
    }
}

inline void PathToAttributesMap::bucketImplCopyArrays(BucketImpl& destBucketImpl,
    BucketId destBucketId,
    const BucketImpl& srcBucketImpl,
    BucketId srcBucketId,
    const carb::flatcache::set<AttrNameAndType_v2>& attrFilter)
{
    destBucketImpl.scalarAttributeArrays.forEach([this, &srcBucketImpl, &attrFilter](const AttrName& destName, ScalarAttributeArray& dest) {
        AttrNameAndType_v2 destNameV2(
            carb::flatcache::Type(dest.type), destName.name, destName.suffix);
        const bool attrIsInFilter = attrFilter.size() == 0 || (attrFilter.find(destNameV2) != attrFilter.end());

        if (attrIsInFilter && destName.suffix == NameSuffix::none)
        {
            const ScalarAttributeArray* src;
            VALIDATE_TRUE(srcBucketImpl.scalarAttributeArrays.find(destName, &src));
            CARB_ASSERT(src);
            bucketImplCopyScalarAttributeArray(dest, *src);
        }
    });

    destBucketImpl.arrayAttributeArrays.forEach([this, &destBucketImpl, &srcBucketImpl, &attrFilter](const AttrName& destName, ArrayAttributeArray& dest) {
        AttrNameAndType_v2 destNameV2(
            carb::flatcache::Type(dest.values.type), destName.name, destName.suffix);
        const bool attrIsInFilter = attrFilter.size() == 0 || (attrFilter.find(destNameV2) != attrFilter.end());

        if (attrIsInFilter && destName.suffix == NameSuffix::none)
        {
            const ArrayAttributeArray* src;
            VALIDATE_TRUE(srcBucketImpl.arrayAttributeArrays.find(destName, &src));
            CARB_ASSERT(src);
            bucketImplCopyArrayAttributeArray(destBucketImpl, destName, dest, *src);
        }
    });
}

template<typename CallbackT>
void inline PathToAttributesMap::BucketImpl::forEachValueArray(CallbackT callback)
{
    scalarAttributeArrays.forEach([&callback](const AttrName& name, ScalarAttributeArray& array) {
        callback(name, array);
    });
    arrayAttributeArrays.forEach([&callback](const AttrName& name, ArrayAttributeArray& array) {
        callback(name, array.values);
        static_assert(sizeof(PathToAttributesMap::ArrayAttributeArray) == 5 * sizeof(PathToAttributesMap::MirroredArray), "ArrayAttributeArray has unexpected size");
        // Intentionally skips these
        // callback(name, array.elemCounts);
        // callback(name, array.cpuElemCounts);
        // callback(name, array.gpuElemCounts);
        // callback(name, array.gpuPtrs);
    });
}

inline void PathToAttributesMap::Serializer::init(uint8_t *const _buf, uint8_t *const _end)
{
    p = buf = _buf;
    end = _end;
    bytesWritten = 0;
    overflowed = false;
}

inline bool PathToAttributesMap::Serializer::writeBytes(const uint8_t *const src, uint64_t size)
{
    CARB_ASSERT(src);

    bytesWritten += size;
    if (p != nullptr && p + size <= end)
    {
        memcpy(p, src, size);
        p += size;
        return true;
    }
    overflowed = true;
    return false;
}

inline bool PathToAttributesMap::Serializer::writeString(const char* const s, const size_t len)
{
    bool OK = true;

    if (!write<size_t>(len))
    {
        OK = false;
    }
    if (!writeBytes(reinterpret_cast<const uint8_t*>(s), len))
    {
        OK = false;
    }

    return OK;
}


inline bool PathToAttributesMap::Serializer::writeString(const std::string &s)
{
    bool OK = true;

    if (!write<size_t>(s.length()))
    {
        OK = false;
    }
    if (!writeBytes(reinterpret_cast<const uint8_t*>(s.data()), s.length()))
    {
        OK = false;
    }

    return OK;
}

template<typename T>
bool PathToAttributesMap::Serializer::write(const T &t)
{
    static_assert(std::is_pod<T>::value, "T must be POD");
    return writeBytes(reinterpret_cast<const uint8_t*>(&t), sizeof(T));
}

inline void PathToAttributesMap::Deserializer::init(const uint8_t *const _buf, const uint8_t *const _end)
{
    p = buf = _buf;
    end = _end;
    bytesRead = 0;
    overflowed = false;
}

inline bool PathToAttributesMap::Deserializer::readBytes(uint8_t *const dst, uint64_t size)
{
    CARB_ASSERT(dst);

    bytesRead += size;
    if (p + size <= end)
    {
        memcpy(dst, p, size);
        p += size;

        return true;
    }

    overflowed = true;
    return false;
};

inline bool PathToAttributesMap::Deserializer::readString(std::string &s)
{
    size_t len;
    read<size_t>(len);
    s.resize(len);
    return readBytes(reinterpret_cast<uint8_t*>(&s[0]), len);
}

template<typename T>
bool PathToAttributesMap::Deserializer::read(T &t)
{
    static_assert(std::is_pod<T>::value, "T must be POD");
    return readBytes(reinterpret_cast<uint8_t*>(&t), sizeof(T));
}

inline void PathToAttributesMap::serializeMirroredArrayMetadata(const AttrName& srcName, MirroredArray &srcValuesArray, Serializer &out)
{
    out.writeString(toTfToken(srcName.name).GetString());
    out.write<NameSuffix>(srcName.suffix);

    // TfToken are actually pointers, so we need to serialize the encoded TypeC
    out.write<TypeC>(srcValuesArray.type);

    out.write<bool>(srcValuesArray.cpuValid);
    out.write<bool>(srcValuesArray.usdValid);
    out.write<size_t>(srcValuesArray.count);
}

pxr::TfType typeCtoTfType(TypeC typeC);

template<typename ArraysT, typename ArraysMapT>
inline void PathToAttributesMap::deserializeMirroredArrayMetadata(Platform& platform, ArraysMapT& arraysMap, AttrName &destName, Typeinfo *&typeInfo, ArraysT *&destArray, Deserializer &in)
{
    std::string nameStr;

    in.readString(nameStr);
    in.read<NameSuffix>(destName.suffix);

    destName.name = asInt(pxr::TfToken(nameStr));

    TypeC destType;
    {
        in.read<TypeC>(destType);
    }

    // typeToInfo is deserialized before all mirrored arrays, so the type must exist.
    VALIDATE_TRUE(typeToInfo.find(destType, &typeInfo));

    if (!arraysMap.allocateEntry(destName, &destArray))
    {
        CARB_LOG_ERROR("Failed to insert dest mirrored array");
        return;
    }
    CARB_ASSERT(destArray);
    new (destArray) ArraysT(platform, destType, *typeInfo);

    MirroredArray *const destValuesArray = destArray->getValuesArray();
    destValuesArray->type = destType;

    in.read<bool>(destValuesArray->cpuValid);
    in.read<bool>(destValuesArray->usdValid);
    in.read<size_t>(destValuesArray->count);

    destValuesArray->resize(destValuesArray->count * typeInfo->size);
}

inline uint64_t PathToAttributesMap::serializeScalarAttributeArray(BucketImpl& srcBucketImpl, const BucketId& srcBucketId, const AttrName& srcName, ScalarAttributeArray& srcScalarAttributeArray, Serializer &out)
{
    const size_t bytesBegin = out.bytesWritten;

    MirroredArray &srcValuesArray = srcScalarAttributeArray;

    serializeMirroredArrayMetadata(srcName, srcValuesArray, out);

    if (srcValuesArray.cpuValid)
    {
        const ConstSpanC srcSpan = getArraySpanC(srcValuesArray, srcName, ScalarArrayOfArrayInfo(), srcBucketImpl, CpuReadConfig()).array;
        CARB_ASSERT(srcSpan.elementCount == srcValuesArray.count);

        const uint8_t* srcPtr = reinterpret_cast<const uint8_t*>(srcSpan.ptr);
        const Typeinfo &typeInfo = srcValuesArray.typeinfo;
        CARB_ASSERT(!typeInfo.isArray);
        out.writeBytes(srcPtr, srcSpan.elementCount * typeInfo.size);
    }

    return out.bytesWritten - bytesBegin;
}

inline bool PathToAttributesMap::deserializeScalarAttributeArray(BucketImpl& destBucketImpl, const BucketId& destBucketId, Deserializer &in)
{
    AttrName destName;
    Typeinfo *typeInfo;
    ScalarAttributeArray *destArray;
    deserializeMirroredArrayMetadata(destBucketImpl.platform, destBucketImpl.scalarAttributeArrays, destName, typeInfo, destArray, in);
    CARB_ASSERT(typeInfo);
    CARB_ASSERT(destArray);
    CARB_ASSERT(!typeInfo->isArray);

    if (destArray->cpuValid)
    {
        uint8_t* destPtr = reinterpret_cast<uint8_t*>(destArray->cpuData());
        in.readBytes(destPtr, destArray->count * typeInfo->size);
    }

    return true;
}

inline uint64_t PathToAttributesMap::serializeArrayAttributeArray(BucketImpl& srcBucketImpl, const BucketId& srcBucketId, const AttrName& srcName, ArrayAttributeArray& srcArrayAttributeArray, Serializer &out)
{
    const size_t bytesBegin = out.bytesWritten;

    MirroredArray &srcValuesArray = srcArrayAttributeArray.values;

    serializeMirroredArrayMetadata(srcName, srcValuesArray, out);

    // write scalar metadata
    auto writeScalarArrayOfArrayMetadata = [this](BucketImpl& srcBucketImpl, const BucketId& srcBucketId, const AttrName& srcName, ScalarAttributeArray& srcScalarAttributeArray, Serializer &out) {
        // similar to serializeScalarAttributeArray, but we can skip some metadata because it should be inferrable

        out.write<bool>(srcScalarAttributeArray.cpuValid);
        out.write<bool>(srcScalarAttributeArray.usdValid);
        out.write<size_t>(srcScalarAttributeArray.count);

        if (srcScalarAttributeArray.cpuValid)
        {
            const ConstSpanC srcSpan = getArraySpanC(srcScalarAttributeArray, srcName, ScalarArrayOfArrayInfo(), srcBucketImpl, CpuReadConfig()).array;
            CARB_ASSERT(srcSpan.elementCount == srcScalarAttributeArray.count);

            const uint8_t* srcPtr = reinterpret_cast<const uint8_t*>(srcSpan.ptr);
            const Typeinfo &typeInfo = srcScalarAttributeArray.typeinfo;
            CARB_ASSERT(!typeInfo.isArray);
            out.writeBytes(srcPtr, srcSpan.elementCount * typeInfo.size);
        }
    };

    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
    writeScalarArrayOfArrayMetadata(srcBucketImpl, srcBucketId, srcName, srcArrayAttributeArray.elemCounts, out);
    writeScalarArrayOfArrayMetadata(srcBucketImpl, srcBucketId, srcName, srcArrayAttributeArray.cpuElemCounts, out);
    // TODO: Can we omit these?
    writeScalarArrayOfArrayMetadata(srcBucketImpl, srcBucketId, srcName, srcArrayAttributeArray.gpuElemCounts, out);
    writeScalarArrayOfArrayMetadata(srcBucketImpl, srcBucketId, srcName, srcArrayAttributeArray.gpuPtrs, out);

    // write array-of-array values
    if (srcValuesArray.cpuValid)
    {
        const ArrayOfArrayInfo destAOA = getArrayOfArrayInfo(srcArrayAttributeArray);
        const ConstSpanC srcSpan = getArraySpanC(srcValuesArray, srcName, destAOA, srcBucketImpl, CpuReadConfig()).array;
        CARB_ASSERT(srcSpan.elementCount == srcValuesArray.count);

        // TODO: Should this be cpuElemCounts instead of elemCounts? The requested capacity may not have been applied yet..
        const size_t* elemCounts = reinterpret_cast<const size_t*>(srcArrayAttributeArray.elemCounts.cpuData());
        const Typeinfo &typeInfo = srcValuesArray.typeinfo;
        CARB_ASSERT(typeInfo.isArray);

        uint8_t* const* srcPtrs = reinterpret_cast<uint8_t* const*>(srcSpan.ptr);
        for (size_t elemIndex = 0; elemIndex != srcSpan.elementCount; elemIndex++)
        {
            const uint8_t* srcPtr = srcPtrs[elemIndex];
            const size_t elemCount = elemCounts[elemIndex];
            out.writeBytes(srcPtr, elemCount * typeInfo.arrayElemSize);
        }
    }

    return out.bytesWritten - bytesBegin;
}

inline bool PathToAttributesMap::deserializeArrayAttributeArray(BucketImpl& destBucketImpl, const BucketId& destBucketId, Deserializer &in)
{
    AttrName destName;
    Typeinfo *typeInfo;
    ArrayAttributeArray *destArray;
    deserializeMirroredArrayMetadata(destBucketImpl.platform, destBucketImpl.arrayAttributeArrays, destName, typeInfo, destArray, in);
    CARB_ASSERT(typeInfo);
    CARB_ASSERT(destArray);
    CARB_ASSERT(typeInfo->isArray);

    // write scalar metadata
    auto readScalarArrayOfArrayMetadata = [this](BucketImpl& destBucketImpl, const BucketId& destBucketId, const AttrName& destName, ScalarAttributeArray& destScalarAttributeArray, Deserializer &in) {
        // similar to deserializeScalarAttributeArray, but we can skip some metadata because it should be inferrable

        in.read<bool>(destScalarAttributeArray.cpuValid);
        in.read<bool>(destScalarAttributeArray.usdValid);
        in.read<size_t>(destScalarAttributeArray.count);

        const Typeinfo &typeInfo = destScalarAttributeArray.typeinfo;

        destScalarAttributeArray.resize(typeInfo.size * destScalarAttributeArray.count);

        if (destScalarAttributeArray.cpuValid)
        {
            CARB_ASSERT(destScalarAttributeArray.size() == (getTypeInfo(destScalarAttributeArray.type).size * destScalarAttributeArray.count));

            uint8_t *const destPtr = reinterpret_cast<uint8_t*>(destScalarAttributeArray.cpuData());
            CARB_ASSERT(!typeInfo.isArray);
            in.readBytes(destPtr, destScalarAttributeArray.count * typeInfo.size);
        }
    };

    static_assert(sizeof(ArrayAttributeArray) == 5 * sizeof(MirroredArray), "ArrayAttributeArray has unexpected size");
    readScalarArrayOfArrayMetadata(destBucketImpl, destBucketId, destName, destArray->elemCounts, in);
    readScalarArrayOfArrayMetadata(destBucketImpl, destBucketId, destName, destArray->cpuElemCounts, in);
    // TODO: Can we omit these?
    readScalarArrayOfArrayMetadata(destBucketImpl, destBucketId, destName, destArray->gpuElemCounts, in);
    readScalarArrayOfArrayMetadata(destBucketImpl, destBucketId, destName, destArray->gpuPtrs, in);

    // read array-of-array values
    MirroredArray& destValuesArray = destArray->values;
    if (destValuesArray.cpuValid)
    {
        // Need to set capacity to zero, because capacity will
        // have been erroneously copied from source
        const ArrayOfArrayInfo destAOA = getArrayOfArrayInfo(*destArray);
        const SpanC destCapacitySpan = getArraySpanC(destArray->cpuElemCounts, destName, destAOA, destBucketImpl, CpuReadWriteConfig()).array;
        size_t *const destCapacities = reinterpret_cast<size_t*>(destCapacitySpan.ptr);
        for (size_t elemIndex = 0; elemIndex != destCapacitySpan.elementCount; elemIndex++)
        {
            destCapacities[elemIndex] = 0;
        }

        const size_t* elemCounts = reinterpret_cast<const size_t*>(destArray->elemCounts.cpuData());

        // getArrayWrC to allocate data for arrays
        const SpanC destSpan = getArraySpanC(destValuesArray, destName, destAOA, destBucketImpl, CpuReadWriteConfig()).array;

        uint8_t** destPtrs = reinterpret_cast<uint8_t**>(destSpan.ptr);
        for (size_t elemIndex = 0; elemIndex != destValuesArray.count; elemIndex++)
        {
            uint8_t* destPtr = destPtrs[elemIndex];
            size_t elemCount = elemCounts[elemIndex];

            in.readBytes(destPtr, elemCount * typeInfo->arrayElemSize);
        }

        destValuesArray.cpuValid = true;
    }

    return true;
}

inline BucketImpl& PathToAttributesMap::addAttributeInternal(BucketImpl& prevBucketImpl, const Bucket& prevBucket, const TokenC& attrName, const TypeC type, const void* value, const Typeinfo& typeinfo, const size_t arrayElemCount)
{
    APILOGGER("addAttributeInternal", apiLogEnabled, attrName);

    // newBucket := oldBucket Union { attrName }
    // findOrCreate (bucketId, bucketImpl) for newBucket, which updates
    // attrNameSetToBucketId and buckets
    Bucket nextBucket = prevBucket;
    nextBucket.insert({ carb::flatcache::Type(type), attrName, NameSuffix::none });

    // Early out if attribute already in bucket
    const bool attributeAlreadyInBucket = (nextBucket.size() == prevBucket.size());
    if (attributeAlreadyInBucket)
        return prevBucketImpl;

    const std::pair<BucketId, BucketImpl&> nextBucketIdAndImpl = findOrCreateBucket(nextBucket);
    const BucketId nextBucketId = nextBucketIdAndImpl.first;
    BucketImpl& nextBucketImpl = nextBucketIdAndImpl.second;

    const size_t nextBucketOriginalSize = nextBucketImpl.elemToPath.size();
    if (nextBucketOriginalSize == 0)
    {
        // Move arrays etc. from original bucket
        nextBucketImpl = std::move(prevBucketImpl);
        nextBucketImpl.SetBucket(std::move(nextBucket));

        // Below are codified assumptions about the side-effects of attempted move-assigning of a BucketImpl.
        // We assume that move-assigning prevBucketImpl like above will clear it as well. This is important because
        // prevBucketImpl may still reside as a valid bucket in the PathToAttributesMap::buckets map.
        //
        // These asserts live outside of the move-assignment operator definition because, technically, the compiler is
        // allowed to elect to use a copy-assignment if it needs to.
        //
        // TODO: Would this be better expressed as an explicit "clear" of prevBucketImpl? Why wasn't that the original
        // behavior?
        CARB_ASSERT(prevBucketImpl.scalarAttributeArrays.empty());
        CARB_ASSERT(prevBucketImpl.arrayAttributeArrays.empty());
        CARB_ASSERT(prevBucketImpl.elemToPath.empty());
        CARB_ASSERT(prevBucketImpl.listenerIdToChanges.empty());
    }
    else
    {
        // TODO : there should be a faster way to do this but more to discuss here later
        auto prevBucketMapIter = attrNameSetToBucketId.find(prevBucket);
        const BucketId prevBucketId = (prevBucketMapIter != attrNameSetToBucketId.end()) ? prevBucketMapIter->second : kInvalidBucketId;
        for (const auto path : prevBucketImpl.elemToPath)
        {
            moveElementBetweenBuckets(asInt(path), nextBucketId, prevBucketId, nextBucket);
        }
    }

    const size_t nextBucketNewSize = nextBucketImpl.elemToPath.size();
    CARB_ASSERT(nextBucketNewSize >= nextBucketOriginalSize);

    CARB_ASSERT(getTypeInfo(type).size == typeinfo.size);
    CARB_ASSERT(getTypeInfo(type).isArray == typeinfo.isArray);
    CARB_ASSERT(getTypeInfo(type).arrayElemSize == typeinfo.arrayElemSize);

    // Add an array for the new attribute
    const AttrName name{ attrName, NameSuffix::none };

    ArrayAttributeArray *arrayAttributeArray;
    MirroredArray* valuesArray;
    if (typeinfo.isArray)
    {
        const bool inserted = nextBucketImpl.arrayAttributeArrays.allocateEntry(std::move(name), &arrayAttributeArray);
        valuesArray = &arrayAttributeArray->values;
        if (inserted)
        {
            new (arrayAttributeArray) ArrayAttributeArray(nextBucketImpl.platform, type, typeinfo);
            while (valuesArray->count < nextBucketNewSize)
            {
                allocElement(*arrayAttributeArray);
            }
        }
    }
    else
    {
        const bool inserted = nextBucketImpl.scalarAttributeArrays.allocateEntry(std::move(name), &valuesArray);
        arrayAttributeArray = nullptr;
        if (inserted)
        {
            new (valuesArray) ScalarAttributeArray(nextBucketImpl.platform, type, typeinfo);
            while (valuesArray->count < nextBucketNewSize)
            {
                allocElement(*valuesArray);
            }
        }

        arrayAttributeArray = nullptr;
    }
    CARB_ASSERT(valuesArray);
    CARB_ASSERT(!typeinfo.isArray || arrayAttributeArray);
    CARB_ASSERT(!typeinfo.isArray || getTypeInfo(valuesArray->type).isArray);

#if CARB_ASSERT_ENABLED
    const size_t elemCount = getElementCount(nextBucketImpl.GetBucket());
    CARB_ASSERT(valuesArray->count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->cpuElemCounts.count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->elemCounts.count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->gpuElemCounts.count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->gpuPtrs.count == elemCount);
#endif // #if CARB_ASSERT_ENABLED

    // fixup elem/path maps
    for (pxr::SdfPath& path : nextBucketImpl.elemToPath)
    {
        std::pair<BucketId, ArrayIndex>* bucketAndElemIndex;
        if (pathToBucketElem.find(asInt(path), &bucketAndElemIndex))
        {
            bucketAndElemIndex->first = nextBucketId;
        }
    }

    // If default value specified, copy it to every element
    if (value)
    {
        fillAttributeInternal(nextBucketImpl, name, nextBucketOriginalSize, nextBucketNewSize, value, typeinfo, arrayElemCount, valuesArray, arrayAttributeArray);
    }

    return nextBucketImpl;
}

inline void PathToAttributesMap::fillAttributeInternal(BucketImpl& bucketImpl, const AttrName& name, const size_t startIndex, const size_t endIndex, const void* value, const Typeinfo& typeinfo, const size_t arrayElemCount, MirroredArray *const valuesArray, ArrayAttributeArray *const arrayAttributeArray)
{
    CARB_ASSERT(valuesArray);
    CARB_ASSERT(value);
    CARB_ASSERT(!typeinfo.isArray || arrayAttributeArray);
    CARB_ASSERT(startIndex < valuesArray->count);
    CARB_ASSERT(endIndex <= valuesArray->count);

    if (typeinfo.isArray)
    {
        CARB_ASSERT(arrayAttributeArray);
        const ArrayOfArrayInfo aoa = getArrayOfArrayInfo(*arrayAttributeArray);

        // Fill array sizes
        {
            ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(arrayAttributeArray->elemCounts, name, aoa, bucketImpl, CpuWriteConfig());
            CARB_ASSERT(startIndex < arrayAndDirtyIndices.array.elementCount);
            CARB_ASSERT(endIndex <= arrayAndDirtyIndices.array.elementCount);
            for (size_t i = startIndex; i < endIndex; ++i)
            {
                reinterpret_cast<size_t*>(arrayAndDirtyIndices.array.ptr)[i] = arrayElemCount;
                setArrayElementDirty(arrayAndDirtyIndices, i);
            }
        }

        // Fill array values
        {
            ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(*valuesArray, name, aoa, bucketImpl, CpuWriteConfig());
            CARB_ASSERT(startIndex < arrayAndDirtyIndices.array.elementCount);
            CARB_ASSERT(endIndex <= arrayAndDirtyIndices.array.elementCount);
            for (size_t i = startIndex; i < endIndex; ++i)
            {
                uint8_t** dest = reinterpret_cast<uint8_t**>(arrayAndDirtyIndices.array.ptr) + arrayAndDirtyIndices.array.elementSize * i;
                CARB_ASSERT(*dest);
                memcpy(*dest, value, arrayElemCount * typeinfo.arrayElemSize); // assumes coherent and packed array value provided
                setArrayElementDirty(arrayAndDirtyIndices, i);
            }
        }
    }
    else
    {
        const ArrayOfArrayInfo aoa = ScalarArrayOfArrayInfo();
        ArrayAndDirtyIndices arrayAndDirtyIndices = getArraySpanC(*valuesArray, name, aoa, bucketImpl, CpuWriteConfig());
        CARB_ASSERT(startIndex < arrayAndDirtyIndices.array.elementCount);
        CARB_ASSERT(endIndex <= arrayAndDirtyIndices.array.elementCount);
        for (size_t i = startIndex; i < endIndex; ++i)
        {
            uint8_t* dest = arrayAndDirtyIndices.array.ptr + arrayAndDirtyIndices.array.elementSize * i;
            memcpy(dest, value, typeinfo.size);
            setArrayElementDirty(arrayAndDirtyIndices, i);
        }
    }
}

inline void PathToAttributesMap::addAttributeInternal(const PathC& path, const TokenC& attrNameC, const NameSuffix nameSuffix, const TypeC ctype, const void* value, const Typeinfo& typeinfo, const size_t arrayElemCount)
{
    APILOGGER("addAttributeInternal", apiLogEnabled, path, attrNameC);

    BucketId bucketId;
    ArrayIndex elemIndex;
    std::tie(bucketId, elemIndex) = addAttributeGetBucketAndArrayIndex(path, attrNameC, nameSuffix, ctype);

    BucketImpl *const bucketImpl = buckets.find(bucketId);
    CARB_ASSERT(bucketImpl);

    ArrayAttributeArray *arrayAttributeArray;
    MirroredArray* valuesArray;

    const AttrName attrName{ attrNameC, nameSuffix };

    if (typeinfo.isArray)
    {
        bucketImpl->arrayAttributeArrays.find(attrName, &arrayAttributeArray);
        CARB_ASSERT(arrayAttributeArray);
        valuesArray = &arrayAttributeArray->values;
    }
    else
    {
        bucketImpl->scalarAttributeArrays.find(attrName, &valuesArray);
        arrayAttributeArray = nullptr;
    }
    CARB_ASSERT(valuesArray);
    CARB_ASSERT(!typeinfo.isArray || arrayAttributeArray);

    if (value)
    {
        fillAttributeInternal(*bucketImpl, attrName, elemIndex, elemIndex + 1, value, typeinfo, arrayElemCount, valuesArray, arrayAttributeArray);
    }

#if CARB_ASSERT_ENABLED
    const size_t elemCount = bucketImpl->elemToPath.size();
    CARB_ASSERT(valuesArray->count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->cpuElemCounts.count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->elemCounts.count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->gpuElemCounts.count == elemCount);
    CARB_ASSERT(!arrayAttributeArray || arrayAttributeArray->gpuPtrs.count == elemCount);
#endif // #if CARB_ASSERT_ENABLED
}

inline PathToAttributesMap::PathToAttributesMap(const PlatformId& platformId)
    : platform(carb::getCachedInterface<carb::flatcache::IPlatform>()->getMutable(platformId))
    , pathToBucketElem(0, std::hash<PathId>(), std::equal_to<PathId>(), AllocFunctor{ &platform.allocator }, FreeFunctor{ &platform.allocator })
    , buckets(platform)
    , attrNameSetToBucketId()
    , listenerIdToChangeTrackerConfig(0, ListenerIdHasher(), std::equal_to<ListenerId>(), AllocFunctor{ &platform.allocator }, FreeFunctor{ &platform.allocator })
    , typeToInfo(0, std::hash<TypeC>(), std::equal_to<TypeC>(), AllocFunctor{ &platform.allocator }, FreeFunctor{ &platform.allocator })
    , usdStageId()
    , minimalPopulationDone(false)
{
    // required types for arrays of arrays
    Typeinfo* typeinfo;
    typeToInfo.allocateEntry(PTAM_SIZE_TYPEC, &typeinfo);
    *typeinfo = Typeinfo{ sizeof(PTAM_SIZE_TYPE), false, 0 };
    typeToInfo.allocateEntry(PTAM_POINTER_TYPEC, &typeinfo);
    *typeinfo = Typeinfo{ sizeof(PTAM_POINTER_TYPE), false, 0 };
}

inline PathToAttributesMap& PathToAttributesMap::operator=(const flatcache::PathToAttributesMap& other)
{
    carb::profiler::ZoneId zoneId = CARB_PROFILE_BEGIN(1, "Clear buckets");
    buckets.clear();
    CARB_PROFILE_END(1, zoneId);

    zoneId = CARB_PROFILE_BEGIN(1, "Copy pathToBucketElem");
    pathToBucketElem.clear();
    pathToBucketElem.reserve(other.pathToBucketElem.size());
    other.pathToBucketElem.forEach([this](const PathId& key, const std::pair<BucketId, ArrayIndex> &otherValue) {
        std::pair<BucketId, ArrayIndex>* value;
        VALIDATE_TRUE(pathToBucketElem.allocateEntry(key, &value));
        static_assert(std::is_copy_constructible<std::pair<BucketId, ArrayIndex>>::value, "Expected pathToBucketElem values to be copy-constructible");
        new (value) std::pair<BucketId, ArrayIndex>(otherValue);
    });
    CARB_PROFILE_END(1, zoneId);

    zoneId = CARB_PROFILE_BEGIN(1, "Copy scalar attributes");
    buckets = other.buckets;
    CARB_PROFILE_END(1, zoneId);

    attrNameSetToBucketId = other.attrNameSetToBucketId;
    typeToInfo = other.typeToInfo;
    usdStageId = other.usdStageId;
    minimalPopulationDone = other.minimalPopulationDone;
    stageHierarchy = other.stageHierarchy;

    zoneId = CARB_PROFILE_BEGIN(1, "Copy array attributes");
    {
        BucketId id{ 0 };
        for (size_t i = 0; i < buckets.end(); ++i, ++id)
        {
            auto bucketPtr = buckets.find(id);
            if (bucketPtr)
            {
                const BucketImpl& srcBucketImpl = *(other.buckets.find(id));
                BucketImpl& destBucketImpl = *bucketPtr;
                // Copy any array-valued attributes
                bucketImplCopyArrays(destBucketImpl, id, srcBucketImpl, id);
            }
        }
    }
    CARB_PROFILE_END(1, zoneId);

    return *this;
}

inline PathToAttributesMap::~PathToAttributesMap()
{
}
}
}

#include <carb/flatcache/GetArrayGPU.h>

// Enable the warnings we disabled when we included USD headers
#if defined(__GNUC__)
#    pragma GCC diagnostic pop
#    ifdef OMNI_USD_SUPPRESS_DEPRECATION_WARNINGS
#        define __DEPRECATED
#        undef OMNI_USD_SUPPRESS_DEPRECATION_WARNINGS
#    endif
#endif
