小小STL实现教程的重点和详细步骤记录

#ifndef _ALLOC_H_
#define _ALLOC_H_

#include<cstdlib>

namespace TinySTL {
    /* 空间配置器，以字节数（Bytes）单位分配
        考虑内存破碎问题，SIG采用双层配置器，第一层配置器直接使用malloc( ) and  free( ) （源码剖析-候捷P57）
        SGI二级适配器设计了一些机制，尽量避免造成过多内存碎片（源码剖析-候捷P60）
    */

    class alloc {
    private:
        enum EAlign{ ALIGN = 8 };            //小型区块的上调边界（上调至8的倍数，例如客户端要求30bytes，则自动上调至32bytes）
        enum EMaxBytes{ MAXBYTES = 128 }; //小型区块大小上限，超过则由malloc( ) 分配 
        enum ENFreeLists { NFREELISTS = (EMaxBytes::MAXBYTES / EAlign::ALIGN) }; //free-list 个数 128/8 =16 个 
        enum ENObjs { NOBJS = 20 }; //每次增加的节点数
    
    private:    
        //free-lists 的结点结构，free-list一是指向下一个块空白内存，二是提供用户使用的一块内存（因为union）
        union obj
        {
            union obj* next;  //可看作指针 指向空闲区块
            char client[1];    //客户使用的内存块，若使用中，咋obj *next则不会指向这块内存
        };

        static obj* free_list[ENFreeLists::NFREELISTS];    //free-list 数组编号

        //表示内存池
    private:
        static char* start_free;    //内存池起始位置,只在chunk_alloc( )中变化
        static char* end_free; //结束位置
        static size_t heap_size; 

    private:
        //将bytes上调至8的倍数,尽量避免内存碎片化
        static size_t ROUND_UP(size_t bytes) {
            return ((bytes + EAlign::ALIGN - 1) & ~(EAlign::ALIGN - 1));
        }

        //根据区块大小决定使用地n号free-list,n从0开始计算
        static size_t FREELIST_INDEX(size_t bytes) {
            return (((bytes)+EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
        }

        //返回一个大小为n的对象，并可能 加入大小为n的其他区块到 free-list
//此函数准备为free-lists重新填充空间，新的空间曲子内存池（该部分由chunk_alloc（）完成）

        static void* refill(size_t n);

        //配置一大块空间，可容纳nobjs个大小为size的区块
        //如果配置nobjs个区块有所不便，nobjs可能会降低
        static char* chunk_alloc(size_t bytes);

    public:
        static void* allocate(size_t bytes);
        static void deallocate(void* ptr, size_t bytes);
        static void* reallocate(void* ptr, size_t old_sz, size_t new_sz);
    };
}

#endif // !_ALLOC_H_

#include "Alloc.h"

namespace TinySTL {
    //alloc class initialization
    char* alloc::start_free = 0; 
    char* alloc::end_free = 0;
    size_t alloc::heap_size = 0;

    //initialize 16 free-lists
    alloc::obj* alloc::free_list[alloc::ENFreeLists::NFREELISTS] = {
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    };

    void* alloc::allocate(size_t bytes) {
        // 如果大于128bytes ，调用一级适配器，即直接malloc
        if (bytes > EMaxBytes::MAXBYTES) {
            return malloc(bytes);
        }
        //寻找16个free-list中合适的一个
        size_t index = FREELIST_INDEX(bytes);
        obj* list = free_list[index]; //list 为找到的那个free-list
        if (list) {//找到的free-list还有空间
            free_list[index] = list->next; //调整list指向下一块空闲内存块，客户端使用的区块free-list将不再指向它们
            return list;  
        }
        else { // 此list无足够空间，需要从内存池里面取，调用refill（）
            return refill(ROUND_UP(bytes));
        }
    }

    void alloc::deallocate(void* ptr, size_t bytes) {
        //大于128bytes则用一级配置器 直接free（）
        if (bytes > EMaxBytes::MAXBYTES) {
            free(ptr);
        }
        else {
            //寻找对应的free-list，调整free-list 区块回收
            size_t index = FREELIST_INDEX(bytes);
            obj* node = static_cast<obj*>(ptr);
            node->next = free_list[index];  //调整free-list回收区块
            free_list[index] = node;            //回收的区块是挂接到free-list 对应区块的第一位置，而不是添加到尾端
        }
    }

    //重新分配
    void* alloc::reallocate(void* ptr, size_t old_sz, size_t new_sz) {
        deallocate(ptr, old_sz);
        ptr = allocate(new_sz);
        return ptr;
    }

    //当发现free-list无可用区块时，调用refill（）准备重新填充空间，新的空间将从内存池取（该部分由chunk_alloc（）完成）
    //返回一个大小为n的对象，并且有时候会为适当的 free-list 增加节点
    //假设bytes已经调整为8的倍数
    void* alloc::refill(size_t bytes) {
        size_t nobjs = ENObjs::NOBJS;
        //从内存池取内存
        char *chunk = chunk_alloc(bytes, nobjs); //尝试取得nobjs个区块作为free-list 的新结点 ，nobjs 是pass by reference
        obj** my_free_list = 0;
        obj *result = 0;
        obj* current_obj = 0 , *next_obj = 0;

        if (nobjs == 1) { //只够一个区块的获取，分配给调用者，free-list无新节点
            return chunk;
        }
        else {
            //否则准备调整free-list，纳入新结点
            my_free_list = free_list + FREELIST_INDEX(bytes);
            result = (obj*)(chunk);  //这一块准备返回给客户端
            *my_free_list = next_obj = (obj*)(chunk + bytes); //引导free-list指向新配置的空间，bytes是用户申请的内存被上调为8倍数的大下
            //以下将free-list的各个结点串接起来
            for (int i = 1;; ++i) {    //从1开始，因为第0个区块要返回给客户端
                current_obj = next_obj;
                next_obj = (obj*)((char*)next_obj + bytes); //链接指向下一新节点
                if (nobjs - 1 == i) { //最后一个区块
                    current_obj->next = 0;
                    break;
                }
                else {
                    current_obj->next = next_obj;
                }
            }
                return result;
            }
        }

    //此函数功能是从内存池取出空间
    char* alloc::chunk_alloc(size_t bytes, size_t & nobjs) {
            char* result = 0;
            size_t total_bytes = bytes * nobjs;        //块数 * 块大小
            size_t bytes_left = end_free - start_free;
            
            if (bytes_left >= total_bytes) {
                result = start_free;
                start_free = start_free + total_bytes;
                return result ;
            }
            else if (bytes_left >= bytes) { //内存剩余空间不满足需要，但足够供应一个或者以上的区块内存
                nobjs = bytes_left / bytes;
                total_bytes = nobjs * bytes;
                result = start_free;
                start_free += total_bytes;
                return result;
        }
            else { //剩余空间甚至不足一个区块大小
                size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
                //内存池可能残余一些零头 （内存），先配给适当的free-list
                if (bytes_left > 0) {
                    obj** my_free_list = free_list + FREELIST_INDEX(bytes_left);
                    //调整free-list，将内存池参与空间编入
                    ((obj*)start_free)->next = *my_free_list;
                    *my_free_list = (obj*)start_free;
                }
                //配置heap空间来补充内存池
                start_free = (char*)malloc(bytes_to_get);

                //如果heap空间不足，malloc失败
                if (!start_free) {
                    obj** my_free_list = 0, * p = 0;
                    for (int i = 0; i <= EMaxBytes::MAXBYTES; i += EAlign::ALIGN) {
                        my_free_list = free_list + FREELIST_INDEX(i);  //free-list的index
                        p = *my_free_list;
                        //free-list 内未使用的区块，调整free-list释放出未使用区块
                        if (p != 0) {
                            *my_free_list = p->next;
                            start_free = (char*)p;
                            end_free = start_free + i;
                            //递归调用 修正nobjs （块数）
                            return chunk_alloc(bytes, nobjs);
                        }
                    }
                    end_free = 0;
                }
                heap_size += bytes_to_get;
                end_free = start_free + bytes_to_get;
                //递归调用 修正nobjs
                return chunk_alloc(bytes, nobjs);
            }                                                        
    }
}