15 UE5 SetAllocator介绍

SetAllocator

• 用于SET MAP 容器的默认内存分配器
• class FDefaultSetAllocator : public TSetAllocator<>
• Allocator = FDefaultSetAllocator> class TSet

#if !defined(DEFAULT_NUMBER_OF_ELEMENTS_PER_HASH_BUCKET)
#   define DEFAULT_NUMBER_OF_ELEMENTS_PER_HASH_BUCKET   2
#endif
#define DEFAULT_BASE_NUMBER_OF_HASH_BUCKETS             8
#define DEFAULT_MIN_NUMBER_OF_HASHED_ELEMENTS           4

TSetAllocator的模板参数

template<
    typename InSparseArrayAllocator               = TSparseArrayAllocator<>,
    typename InHashAllocator                      = TInlineAllocator<1,FDefaultAllocator>,
    uint32   AverageNumberOfElementsPerHashBucket = DEFAULT_NUMBER_OF_ELEMENTS_PER_HASH_BUCKET,
    uint32   BaseNumberOfHashBuckets              = DEFAULT_BASE_NUMBER_OF_HASH_BUCKETS,
    uint32   MinNumberOfHashedElements            = DEFAULT_MIN_NUMBER_OF_HASHED_ELEMENTS
    >
class TSetAllocator
{
......
    typedef InSparseArrayAllocator SparseArrayAllocator;
    typedef InHashAllocator        HashAllocator;
}

两个内存分配器的存储

• 数据存储区 InSparseArrayAllocator 稀疏数组
• 内部实际存储了TSetElement
• Hash存储区 InHashAllocator（TInlineAllocator）可扩展的
• 内部为 数据存储区（SparseArray）的下标

TSparseArrayAllocator

• 数据存储区，里面存放多个数据。
• 是用来给set map使用的数据存储器

/** Encapsulates the allocators used by a sparse array in a single type. */
template<typename InElementAllocator = FDefaultAllocator,typename InBitArrayAllocator = FDefaultBitArrayAllocator>
class TSparseArrayAllocator
{
public:

    typedef InElementAllocator ElementAllocator;
    typedef InBitArrayAllocator BitArrayAllocator;
};

union类型 TSparseArrayElementOrFreeListLink

• 在安放数据的时候，ElementData就是实际的元素内容
• 在没有安放数据的时候，PrevFreeIndex 和 NextFreeIndex 就是前/后指针。

template<typename ElementType>
union TSparseArrayElementOrFreeListLink
{
    // 有数据，这里是内容
    ElementType ElementData;

    // 无数据，这里是前后指针
    struct
    {
        int32 PrevFreeIndex;
        int32 NextFreeIndex;
    };
};

TSet添加元素

• 在实际存储Elements稀疏数组中构造元素
• 调用TryReplaceExisting 有旧值替换
• 判断是否需要RehashOrLink
• 返回FSetElementId（元素在Elements集合中的索引地址）

    template <typename ArgsType = ElementType>
    FSetElementId Emplace(ArgsType&& Args, bool* bIsAlreadyInSetPtr = nullptr)
    {
        // Create a new element.
        FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
        SetElementType& Element = *new (ElementAllocation) SetElementType(Forward<ArgsType>(Args));

        SizeType NewHashIndex = ElementAllocation.Index;

        uint32 KeyHash = KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(Element.Value));
        if (!TryReplaceExisting(KeyHash, Element, NewHashIndex, bIsAlreadyInSetPtr))
        {
            RehashOrLink(KeyHash, Element, NewHashIndex);
        }
        return FSetElementId(NewHashIndex);
    }

TryReplaceExisting分析

• 1 通过插入的值获取hashkey
• 2 判断是否存在，已存在用新值更新旧值
• 3返回 是否已存在set中 bIsAlreadyInSet

    bool TryReplaceExisting(uint32 KeyHash, SetElementType& Element, 
SizeType& InOutElementIndex, bool* bIsAlreadyInSetPtr)
    {
        bool bIsAlreadyInSet = false;
        // 如果不允许重复的KEY
        if (!KeyFuncs::bAllowDuplicateKeys)
        {
            // 添加第一个元素时不用麻烦了
            if (Elements.Num() != 1)
            {
                SizeType ExistingIndex = FindIndexByHash(KeyHash, KeyFuncs::GetSetKey(Element.Value));

                bIsAlreadyInSet = ExistingIndex != INDEX_NONE;
                if (bIsAlreadyInSet)
                {
                    //  用新的元素替换掉旧的
                    MoveByRelocate(Elements[ExistingIndex].Value, Element.Value);

                    Elements.RemoveAtUninitialized(InOutElementIndex);

                    // 返回索引的更新
                    InOutElementIndex = ExistingIndex;
                }
            }
        }
        if (bIsAlreadyInSetPtr)
        {
            *bIsAlreadyInSetPtr = bIsAlreadyInSet;
        }
        return bIsAlreadyInSet;
    }

TSet查找元素

• 可以看到就是返回 存储数组中的下标

    FORCEINLINE ElementType* Find(KeyInitType Key)
    {
        SizeType ElementIndex = FindIndexByHash(KeyFuncs::GetKeyHash(Key), Key);
        if (ElementIndex != INDEX_NONE)
        {
            return &Elements[ElementIndex].Value;
        }
        else
        {
            return nullptr;
        }
    }

FindIndexByHash函数分析

• TSetElement：TSetElementBase
• TSetElementBase：成员有：
• 元素的值：Value
• 同一哈希桶中下一个元素的id ： HashNextId
• 某元素当前链接到的哈希桶：HashIndex
  HashIndex

    template <typename ComparableKey>
    SizeType FindIndexByHash(uint32 KeyHash, const ComparableKey& Key) const
    {
        if (Elements.Num() == 0)
        {
            return INDEX_NONE;
        }

        FSetElementId* HashPtr      = Hash.GetAllocation();
        SizeType       ElementIndex = HashPtr[KeyHash & (HashSize - 1)].Index;
        for (;;)
        {
            if (ElementIndex == INDEX_NONE)
            {
                return INDEX_NONE;
            }

            if (KeyFuncs::Matches(KeyFuncs::GetSetKey(Elements[ElementIndex].Value), Key))
            {
                // 第一个匹配就返回，哪怕是有多个键匹配
                return ElementIndex;
            }

            // 不匹配 就继续在HashNextId 寻找
            ElementIndex = Elements[ElementIndex].HashNextId.Index;
        }
    }

• 行： 函数值对应的桶

• 列： 链表结构的HASH相等的元素串在一起

  
  image.png

TMap的区别

• 继承TSortableMapBase : TMapBase
• 内存分配器使用SetAllocator
• Emplace传递给Pairs.Emplace实现 大部分功能都转给Pairs

class TMap : public TSortableMapBase<InKeyType, InValueType, SetAllocator, KeyFuncs>
class TSortableMapBase : public TMapBase<KeyType, ValueType, SetAllocator, KeyFuncs>

    ValueType& Emplace(InitKeyType&& InKey, InitValueType&& InValue)
    {
        const FSetElementId PairId = Pairs.Emplace(
TPairInitializer<InitKeyType&&, InitValueType&&>(Forward<InitKeyType>(InKey), 
Forward<InitValueType>(InValue)));

        return Pairs[PairId].Value;
    }

    FORCEINLINE ValueType* Find(KeyConstPointerType Key)
    {
        if (auto* Pair = Pairs.Find(Key))
        {
            return &Pair->Value;
        }

        return nullptr;
    }

ElementSetType Pairs

• Pairs就是Set<TPair<KeyType, ValueType>>

typedef TPair<KeyType, ValueType> ElementType;
typedef TSet<ElementType, KeyFuncs, SetAllocator> ElementSetType;
ElementSetType Pairs