UE源码学习——常用容器

#define NumBitsPerDWORD ((int32)32)
FORCEINLINE FBitReference operator[](int32 Index)
{
	check(Index>=0 && Index<NumBits);
	return FBitReference(
		GetData()[Index / NumBitsPerDWORD],
		1 << (Index & (NumBitsPerDWORD - 1))
		);
}

void SetBitNoCheck(int32 Index, bool Value)
{
    uint32& Word = GetData()[Index/NumBitsPerDWORD];
    uint32 BitOffset = (Index % NumBitsPerDWORD);
    // 先清除目标位的数据，再做或运算
    Word = (Word & ~(1 << BitOffset)) | (((uint32)Value) << BitOffset);
}

int32 Add(const bool Value)
{
    const int32 Index = AddUninitialized(1);
    SetBitNoCheck(Index, Value);
    return Index;
}

template<typename InElementType,typename Allocator /*= FDefaultSparseArrayAllocator */>
class TSparseArray
{
    // ......

    /** Allocated elements are overlapped with free element info in the element list. */
    template<typename ElementType>
    union TSparseArrayElementOrFreeListLink
    {
        /** If the element is allocated, its value is stored here. */
        ElementType ElementData;

        struct
        {
            /** If the element isn't allocated, this is a link to the previous element in the array's free list. */
            int32 PrevFreeIndex;

            /** If the element isn't allocated, this is a link to the next element in the array's free list. */
            int32 NextFreeIndex;
        };
    };

    /**
        * The element type stored is only indirectly related to the element type requested, to avoid instantiating TArray redundantly for
        * compatible types.
        */
    typedef TSparseArrayElementOrFreeListLink<
        TAlignedBytes<sizeof(ElementType), alignof(ElementType)>
        > FElementOrFreeListLink;

    typedef TArray<FElementOrFreeListLink,typename Allocator::ElementAllocator> DataType;
    DataType Data;

    typedef TBitArray<typename Allocator::BitArrayAllocator> AllocationBitArrayType;
    AllocationBitArrayType AllocationFlags;

    /** The index of an unallocated element in the array that currently contains the head of the linked list of free elements. */
    int32 FirstFreeIndex = -1;

    /** The number of elements in the free list. */
    int32 NumFreeIndices = 0;

    // ......
};

/**
 * The base KeyFuncs type with some useful definitions for all KeyFuncs; meant to be derived from instead of used directly.
 * bInAllowDuplicateKeys=true is slightly faster because it allows the TSet to skip validating that
 * there isn't already a duplicate entry in the TSet.
  */
template<typename ElementType,typename InKeyType,bool bInAllowDuplicateKeys = false>
struct BaseKeyFuncs
{
	typedef InKeyType KeyType;
	typedef typename TCallTraits<InKeyType>::ParamType KeyInitType;
	typedef typename TCallTraits<ElementType>::ParamType ElementInitType;

	enum { bAllowDuplicateKeys = bInAllowDuplicateKeys };
};

/**
 * A default implementation of the KeyFuncs used by TSet which uses the element as a key.
 */
template<typename ElementType,bool bInAllowDuplicateKeys /*= false*/>
struct DefaultKeyFuncs : BaseKeyFuncs<ElementType,ElementType,bInAllowDuplicateKeys>
{
    // ...
};

FORCEINLINE FSetElementId& GetTypedHash(int32 HashIndex) const
{
	return ((FSetElementId*)Hash.GetAllocation())[HashIndex & (HashSize - 1)];
}

/** Links an added element to the hash chain. */
FORCEINLINE void LinkElement(FSetElementId ElementId, const SetElementType& Element, uint32 KeyHash) const
{
	// Compute the hash bucket the element goes in.
	Element.HashIndex = KeyHash & (HashSize - 1);

	// Link the element into the hash bucket.
	Element.HashNextId = GetTypedHash(Element.HashIndex);
	GetTypedHash(Element.HashIndex) = ElementId;
}

template<typename ComparableKey>
FORCEINLINE int32 RemoveImpl(uint32 KeyHash, const ComparableKey& Key)
{
	int32 NumRemovedElements = 0;

	FSetElementId* NextElementId = &GetTypedHash(KeyHash);
	while (NextElementId->IsValidId())
	{
		auto& Element = Elements[*NextElementId];
		if (KeyFuncs::Matches(KeyFuncs::GetSetKey(Element.Value), Key))
		{
			// This element matches the key, remove it from the set.  Note that Remove sets *NextElementId to point to the next
			// element after the removed element in the hash bucket.
			Remove(*NextElementId);
			NumRemovedElements++;

			if (!KeyFuncs::bAllowDuplicateKeys)
			{
				// If the hash disallows duplicate keys, we're done removing after the first matched key.
				break;
			}
		}
		else
		{
			NextElementId = &Element.HashNextId;
		}
	}

	return NumRemovedElements;
}

void Remove(FSetElementId ElementId)
{
	if (Elements.Num())
	{
		const auto& ElementBeingRemoved = Elements[ElementId];

		// Remove the element from the hash.
		for(FSetElementId* NextElementId = &GetTypedHash(ElementBeingRemoved.HashIndex);
			NextElementId->IsValidId();
			NextElementId = &Elements[*NextElementId].HashNextId)
		{
			if(*NextElementId == ElementId)
			{
				*NextElementId = ElementBeingRemoved.HashNextId;
				break;
			}
		}
	}

	// Remove the element from the elements array.
	Elements.RemoveAt(ElementId);
}

/** Defines how the map's pairs are hashed. */
template<typename KeyType, typename ValueType, bool bInAllowDuplicateKeys>
struct TDefaultMapKeyFuncs : BaseKeyFuncs<TPair<KeyType, ValueType>, KeyType, bInAllowDuplicateKeys>
{
	typedef typename TTypeTraits<KeyType>::ConstPointerType KeyInitType;
	typedef const TPairInitializer<typename TTypeTraits<KeyType>::ConstInitType, typename TTypeTraits<ValueType>::ConstInitType>& ElementInitType;

	static FORCEINLINE KeyInitType GetSetKey(ElementInitType Element)
	{
		return Element.Key;
	}

    // ...
};