Loki是由 Andrei 编写的一个与《Modern C++ Design》（C++设计新思维）一书配套发行的C++代码库。其中有两个文件 SmallObj.h 、SmallObj.cpp 进行内存治理，能够独自进行应用

Loki 源码下载

类层次结构

SmallObj 文件中有三个类：chunk, FixedAllocator 和 SmallObjAllocator。其中SmallObjAllocator 位于最顶层供应用程序调用

Chunk

Chunk 是类层次结构中最底层治理内存块的类，它负责向操作系统进行内存申请

Init, Reset, Release

1. Init(), 应用 operator new 申请一段内存 chunk, 并应用 pData_ 指向 chunk2. Reset(), 对 pData_ 指向的内存进行宰割。[数组代替链表，索引代替指针]            [与嵌入式指针相似]每一块 block 的第一个字节寄存的是下一个可用的 block 间隔起始地位 pData_ 的偏移量(以 block 大小为单位)3. Relese(), 向操作系统偿还内存--1. blockSize、blocksblock, block 大小及数量            2. firstAvailableBlock_,以后可用内存块的偏移量3. blocksAvailable,以后 chunk 中残余的 block 数量          

unsigned char i = 0;unsigned char *p = pData;for(;i!=blocks; p+=blockSize)  // 以 blockSize 为距离切分 chunk 为 block    *p = ++i;                  // 以 block 的第一个字节存储下一个可用 block 索引

参数初始化后的 chunk

Allocate

用索引对区块进行治理[第一字节流水号]

Deallocate

FixedAllocator

FixedAllocate 负责管理一个具备雷同大小 block 的 chunk 汇合。它负责依据应用程序需要，创立特定大小的 chunk， 并搁置在 vcector 中进行治理

Allocate

void *FixedAllocator::allocate(){    if (allocChunk_ == 0 || allocChunk_->blocksAvailable == 0)    {        // 目前没有标定 chunk 或 该 chunk 已无可用区块                Chunks::iterator i = chunks_.begin();           // 打算从头找起        for (;; ++i)                                    // 找遍每个 chunk 直至找到领有可用区块者        {            if (i == chunks_.end())                     // 达到尾端，都没找到            {                // Initialize                chunks_.push_back(Chunk());             // 产生 a new chunk 挂于末端； Chunk()，创立长期对象拷贝至容器而后完结生命                 Chunk& newChunk = chunks_.back();       // 指向末端                newChunk.Init(blockSize_, numBlocks_);  // 设置好索引                allocChunk_ = &newChunk;                // 标定，稍后将对此 chunk 取区块                deallocChunk_ = &chunks_.front();       // 另一标定                break;            }                        if (i->blocksAvailable_ > 0)            {                // current chunk 有可用区块                allocChunk_ = &*i;  // 取地址                break;            }        }    }        // allocChunk_， 在此 chunk 找到可用区块，下次就优先从此找起    return allocChunk_->Allocate(blockSize_); // 向这个 chunk 取区块 }

allocChunk_

标记最近一次满足调配动作的 chunk, 当下次再有调配需要时，优先查看此 chunk

deallochunk_

依附数据的内聚性和区域性准则当某一 chunk 产生内存回收时，下次回收也可能产生在此 chunk 上。以此尽量避免 `void Deallocate(void *p)`中 p 落在哪一个 chunks 的遍历查找动作（类比于上述代码 for ）

deallocChunk_ = &chunks_.front()

vector 在进行 insert 时，可能会导致内存增长，内存增长时元素将从旧空间拷贝到新的空间，此时过来 deallocChunk_ 指向的地址将生效，因而须要对 deallocChunk_ 从新标定

Deallocate

咱们须要依据偿还内存的地址，把这块内存回收到对应的 chunk 中

void FixedAllocator::Deallocate(void *p){    deallocChunk = VicinityFind(p);    DoDeallocate();}

VicinityFind

依据内存应用的区域性,采纳邻近查找法确定 p 所对应的 chunk

1. 已知每一块 chunk 指向内存空间的地址 p_Data_2. 已知每一块内存空间的大小 numblocks_ * blocksize3. 由此可计算出每一块 chunk 指向内存的地址范畴 [p_Data_, p_Data_ + numblocks_ * blocksize]4. 由此可计算出偿还的内存 p 属于哪一个 chunk---查找思维：VicinityFind 采纳邻近分头查找的算法，从上一次 dealloChunk_ 的地位登程进行高低中间查找(内存调配通常是个容器服务的,而容器元素间断创立时，通常就从同一个 chunk 取得间断的地址空间，偿还的时候当然也是偿还到同一块 chunk。通过对上一次偿还 chunk 的记录，尽量避免遍历搜寻，进步了查找定位速度)在上述实现中，如果 p 并非当初由此零碎取得，必定找不到对应的 chunk，于是陷入死循环。在新版本中已修复此问题

DoDeallocate

实现理论的内存回收

1. deallocChunk->Deallocate(p, blockSize_); 由 FixedAllocator::chunk::Deallocate(void *p, std::size_t blockSize) 实现底层的内存回收2. 当 deallockChunk_->blocksAvailable_ = numBlocks_ 时示意以后内存能够归还给操作系统3. 提早偿还机制，把空的 chunk 替换到 vector 尾部，只有呈现两个空的 chunk 时，才会产生真正的内存偿还动作（表中标注①②③）

SmallObjAllocator

SmallObjAllocator 负责管理具备不同 block size 的 FixedAllocate 的vector 汇合

Allocate

void* SmallObjAllocator::Allocate(std::size_t numBytes){    if (numBytes > maxObjectSize_) return operator new(numBytes);        if (pLastAlloc_ && pLastAlloc_->BlockSize() == numBytes)    {        return pLastAlloc_->Allocate();    }    //找到第一个 >= numBytes 的地位    Pool::iterator i = std::lower_bound(pool_.begin(), pool_.end(), numBytes);    //没找到雷同的，就从新创立一个 FixedAllocator    if (i == pool_.end() || i->BlockSize() != numBytes)    {        i = pool_.insert(i, FixedAllocator(numBytes));        pLastDealloc_ = &*pool_.begin();    }    pLastAlloc_ = &*i;    return pLastAlloc_->Allocate();}

1. 当应用程序申请的 numBytes 大于 maxObjectSize_ 时交由 operator new 解决2. pLastAlloc_ 记录上次调配 block 的 FixedAllocator object。如果本次申请的 block size 等于上次调配的 block size，就间接应用同一个 FixedAllocator object，以此尽力防止查找动作（最佳客户是容器，容器的元素大小是雷同的）3. 如果本次需要的 block size 不等于上次调配的 block size，就遍历查找大小相等的 FixedAllocator object。如果没有找到，就插入新的 FixedAllocator object。同时为了防止 vector 扩容引起的内存重新分配，对 pLastDealloc_  重定位

Deallocate

void SmallObjAllocator::Deallocate(void* p, std::size_t numBytes){    if (numBytes > maxObjectSize_) return operator delete(p);    if (pLastDealloc_ && pLastDealloc_->BlockSize() == numBytes)    {        pLastDealloc_->Deallocate(p);        return;    }    Pool::iterator i = std::lower_bound(pool_.begin(), pool_.end(), numBytes);    assert(i != pool_.end());    assert(i->BlockSize() == numBytes);    pLastDealloc_ = &*i;    pLastDealloc_->Deallocate(p);}

Loki allocator 检讨

• 已经有两个 bugs, 新版已修改
• 精简强悍；伎俩暴力（对于 for-loop）
• 应用「以 array 取代 list, 以 index 取代 pointer」 的非凡实现手法
• 可能以简略的形式判断 「chunk 全回收」 进而将 memory 归还给操作系统
• 有 Deferring (提早偿还)能力
• 这是个 allocator, 用来调配大量小块不带 cookie 的memory blocks, 它的最佳客户是容器（因为应用时要记录块大小）
• 外部应用的 vector 采纳 std::allocator 实现

与 std::alloc 的比拟