张行
0%

字符处理

发表于

FString

封装TArray实现，效果基本等同于std::string，应用于任何的字符串处理。UE中提供了大量的ToString函数，便于各种数据结构或对象的调试。

FName

用于保存对象或资产名称的字符串类型，在查找、比较、存储方面做了优化。

相关类型与内存布局

EFindName

针对FNamePool操作时的操作方法，分为查找Name、添加Name、添加Name(若已存在则替换，要求编码类型与字符串长度相等)

EName

对UE常用的FName进行特殊记录，用于更高效的查找与创建

FNameBuffer

对字符串进行比较或计算处理时，临时使用的结构体类型

1
2
3
4
5
union FNameBuffer
{
   ANSICHAR AnsiName[NAME_SIZE];
   WIDECHAR WideName[NAME_SIZE];
};

FNameEntry

用于在内存分配器中最终存储Name字符串

1
2
3
4
5
6
7
8
9
#if WITH_CASE_PRESERVING_NAME
   FNameEntryId ComparisonId;
#endif
   FNameEntryHeader Header;//字符串的长度以及是否为宽字符串
   union//记录真实的字符串数据，注意这里虽然是静态分配空间，但是实际上在FNameEntryAllocator完成了数据压缩，不存在空间浪费。
   {
      ANSICHAR   AnsiName[NAME_SIZE];
      WIDECHAR   WideName[NAME_SIZE];
   };

FNameEntryAllocator

一个分块存储的内存分配器，首先开辟空间并记录在在Blocks[0]，当Blocks[0]存满后，继续开辟空间记录在Blocks[1]，依次类推。

1
2
3
4
mutable FRWLock Lock;
uint32 CurrentBlock = 0;
uint32 CurrentByteCursor = 0;
uint8* Blocks[FNameMaxBlocks] = {};

FNameEntryHandle

用于记录FNameEntryAllocator中的某一个FNameEntry的地址

1
2
uint32 Block = 0;//FNameEntry所在的内存块
uint32 Offset = 0;//FNameEntry所在块中的具体偏移位置

FNameEntryId

用一个uint32记录FNameEntry在内存分配器中的地址

1
uint32 Value;//将FNameEntryHandle中的两个数压缩到32位中存储，0-15位表示Offset，16-28位表示Block

FName

1
2
3
4
5
6
7
8
//FNameEntryId作为字符串的唯一标识符
FNameEntryId    ComparisonIndex;
//表示后缀的数值
uint32            Number;

#if WITH_CASE_PRESERVING_NAME
    FNameEntryId    DisplayIndex;
#endif

FNameHash

将字符串哈希为 64 位，用于确定分片和插槽索引

1
2
3
4
5
6
7
uint32 ShardIndex;//Hash值的高32位值，FNameComparisonValue对应的FNamePoolShard索引
uint32 UnmaskedSlotIndex; // Hash值的低32位值，FNamePoolShard对应的Slot索引
uint32 SlotProbeHash; // 当FNamePoolShardBase的Slot出现Hash冲突时辅助用于唯一标识
FNameEntryHeader EntryProbeHeader; // Helps cull equality checks when probing inspects entries

static constexpr uint64 AlgorithmId = 0xC1640000;
static constexpr uint32 ShardMask = FNamePoolShards - 1;

FNameHelper

1
//纯函数类

FNamePool

1
2
3
4
5
6
7
8
9
10
11
12
13
    FNameEntryAllocator Entries;

#if WITH_CASE_PRESERVING_NAME
   FNamePoolShard<ENameCase::CaseSensitive> DisplayShards[FNamePoolShards];
#endif
    //真正用于存储字符串的容器，根据字符串高位hash值分桶存储
   FNamePoolShard<ENameCase::IgnoreCase> ComparisonShards[FNamePoolShards];

   // 使用单独的缓冲区完成EName到FNameEntryId的查找
   alignas(PLATFORM_CACHE_LINE_SIZE) FNameEntryId ENameToEntry[NAME_MaxHardcodedNameIndex] = {};
   uint32 LargestEnameUnstableId;
// 使用单独的缓冲区完成FNameEntryId到EName的查找
   TMap<FNameEntryId, EName, TInlineSetAllocator<MaxENames>> EntryToEName;

FNamePoolShard

1
//继承FNamePoolShardBase，子类无数据

FNamePoolShardBase

1
2
3
4
5
6
7
mutable FRWLock Lock;
uint32 UsedSlots = 0;
uint32 CapacityMask = 0;
FNameSlot* Slots = nullptr;
FNameEntryAllocator* Entries = nullptr;
uint32 NumCreatedEntries = 0;
uint32 NumCreatedWideEntries = 0;

FNameSlot

用于记录FNameEntryId，以及字符串hash值中的3比特位(用于加快查找)

1
2
3
4
5
6
static constexpr uint32 EntryIdBits = FNameMaxBlockBits + FNameBlockOffsetBits;
static constexpr uint32 EntryIdMask = (1 << EntryIdBits) - 1;
static constexpr uint32 ProbeHashShift = EntryIdBits;
static constexpr uint32 ProbeHashMask = ~EntryIdMask;

uint32 IdAndHash = 0;//0-28表示FNameEntryId，29-31位表示字符串的hash

FNameStringView

一种通用的数据格式，用于包裹WIDECHAR或ANSICHAR字符串

1
2
3
4
5
6
7
8
9
union //存储实际的字符串
{
   const void* Data;
   const ANSICHAR* Ansi;
   const WIDECHAR* Wide;
};

uint32 Len;//字符串长度
bool bIsWide;//是否为宽字符编码

FNameValue

包含完整的字符串与对应的Hash值

1
2
3
4
5
   FNameStringView Name; //实际的字符串
   FNameHash Hash; //Name的Hash索引
#if WITH_CASE_PRESERVING_NAME
   FNameEntryId ComparisonId;
#endif

FWideStringViewWithWidth

仅用于包裹WIDECHAR字符串

1
2
3
const WIDECHAR* Str;//原始的字符串
int32 Len;//字符数量(4字节的字符被统计为两个字符)，经过MakeDetectNumber计算之后字符数量将仅表示去除数字之后的字符数量。
bool bIsWide;//是否为真正的宽字节编码(内部包含ANSI以外的字符)

典型的构造方法

默认构造方法

FName()：将成员初始化为0

FName(ENoInit)：不执行成员初始化

常规的文本构造流程

FName(const WIDECHAR* Name, EFindName FindType=FNAME_Add)

  1. WIDECHAR转换为FWideStringViewWithWidth类型，并记录对应的数据。

    1
    static FWideStringViewWithWidth MakeUnconvertedView(const WIDECHAR* Str)

  2. 解析字符串，将Name_1格式的数据解析成的数字部分与字符部分，若无数字则解析为0。

    1
    2
    template<typename ViewType>
    static FName MakeDetectNumber(ViewType View, EFindName FindType)

  3. 若不是真正的宽字符编码则转换为ANSI编码，将转码完成的数据更换为FNameStringView存储，以便进一步压缩空间。

    1
    static FName MakeWithNumber(const FWideStringViewWithWidth View, EFindName FindType, int32 InternalNumber)

  4. 通过FNamePool完成数据存储，返回DisplayId与ComparisonId。

    1
    static FName Make(FNameStringView View, EFindName FindType, int32 InternalNumber)
    1. 若是第一次使用FNamePool，则需要先执行构造函数FNamePool()。
      • 建议先查看FNamePool成员含义
      • 初始化DisplayShards与ComparisonShards的每一个元素，分配Slots内存。查看FNamePoolShardBase
      • 将UnrealNames.inl中的UE常用FName调用Store()函数完成数据存储。
      • 将默认常用FName的FNameEntryId保存到ENameToEntry，用于快速根据EName查找FName，同时封装FNameEntryId到EName的映射表到EntryToEName。便于EName与FName的互相查找。
    2. 接下来执行Store()函数完成数据存储
      • 将字符串转换为小写，并使用CityHash算法完成Hash计算，将结果保存于FNameValue中。
      • 根据Hash值，向对应的预分配好的ComparisonShards中插入元素，调用Insert方法最终返回FNameEntryId作为DisplayId。
        • 根据字符串Hash值查找FNamePoolShard中对应位置的FNameSlot
        • 若hash值对应的桶中已存在字符串，则依次比较哈希值、字符串长度与类型、字符串原始数据，若完全相同则直接返回。
        • 若字符串不完全相同，仅仅是普通的hash冲突，则循环查找桶的下一个位置。
      • 字符串若已存在，直接返回即可，否则根据FNameValue在ComparisonShards中生成FNameSlot。
        • 使用FNameEntryAllocator内存分配器分配一块空间，将空间的位置信息保存到FNameEntryHandle
        • 在刚才分配的空间中按照FNameEntry格式记录原始的字符串数据。
        • 将最终的FNameEntryId转换为FNameSlot格式并记录在Slots。
        • 若Slots存满则倍增扩容。

  5. 根据DisplayId、ComparisonId、后缀数字完成FName构造。

    1
    return FName(ComparisonId, DisplayId, InternalNumber);

通过EName构造

FName(EName Ename, int32 InNumber)：EName直接通过FNamePool中ENameToEntry缓存是数据返回ComparisonId。

总结

内存布局

  1. 使用FName存储字符串索引与字符串后缀。
  2. 在FNamePool中按照字符串的高位hash值分桶到FNamePoolShard。
  3. 在FNamePoolShard中按照字符串的低位hash值分桶到FNameSlot。
  4. 使用FNameEntryAllocator分配内存存储字符串，并将对应的索引保存到刚才查找到的FNameSlot中。

特点

  1. 高效查找与比较
  2. 特定类型字符串的高效存储(字符串复用、字符串空间精密排布)
  3. 不支持删除