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_ 指向 chunk
2. 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_ * blocksize
3. 由此可计算出每一块 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 的比拟