union使用在空闲链表里如何节省空间？

Question

我在阅读《STL源码剖析》中看到关于内存组织成空闲链表的结构：

union obj{
    union obj* next;
    char client_data[1];
};

使用union主要是为了节省空间，当我们以一个指针得到该块内存时，可以完全使用该块内存。假如我们用result*得到该块内存后，请问我们应该如何根据client_data来存储数据呢？

Answer 1

client_data是C/C++常见的变长数组实现方式，如果编译器支持0长度的数组，还可以申明为client_data[0]达到更节省的目的（非标准，这里client_data[1]具有广泛的兼容性）。

由于节省了内存，union obj的大小也就一个指针大小（next指针的大小)。

EDIT: 之前犯了严重的错误，写成了对应struct的了。。。

分配内存的时候，直接分配一块内存给obj即可，一般是8的倍数（因为内存对齐等因素）：

obj * block = (obj *)malloc(128); // 分配一块128字节的内存
free_list_ptr->next = block; // 挂接到free_list上

由于这个是free_list用于分配内存的，就有两个作用，一个是指向下一块空白内存（当存在与free_list中时），一个就是供用户使用的一块内存（不存在于free_list）。

当在free_list中时，不要担心next指针与用户数据重叠，因为该块内存会从free_list中取出：

// detach
obj * block = free_list_ptr->next;
free_list_ptr->next = NULL;
// 使用这块内存(block, 128字节)

这里补一个简单的例子，固定大小的内存池（每次只能取一整块，每块大小固定）

// g++ -std=c++11
#include <cstdio>
#include <new>
#include <vector>

using std::size_t;
using std::vector;
using std::bad_alloc;

// 固定大小内存池, 非常基本的演示
template<size_t _BLOCK_SIZE = 64, size_t _NUM_BLOCKS = 16>
class fixed_mem_pool
{
    union obj
    {
        union obj *next;
        char client_data[1];
    };

public:
    enum
    {
        BLOCK_SIZE = _BLOCK_SIZE,
        NUM_BLOCKS = _NUM_BLOCKS
    };

public:
    fixed_mem_pool()
    {
        // 连续分配一块内存, 初始化时分成`NUM_BLOCKS`份
        chunks_ = new char[BLOCK_SIZE * NUM_BLOCKS];

        free_list_head_ = reinterpret_cast<obj *>(chunks_);
        auto cur_obj = free_list_head_;
        auto next_block_ptr = free_list_head_->client_data + BLOCK_SIZE;

        // 构建free_list（链表）, 标记可用内存
        for (auto i = 1; i < NUM_BLOCKS; i++)
        {
            cur_obj->next = reinterpret_cast<obj *>(next_block_ptr);
            cur_obj = cur_obj->next;
            next_block_ptr += BLOCK_SIZE;
        }

        cur_obj->next = nullptr;
    }

    ~fixed_mem_pool()
    {
        delete chunks_;
    }

    void *allocate()
    {
        if (free_list_head_ == nullptr)
        {
            throw bad_alloc();
        }

        // Take block from head directy.
        void *p = free_list_head_;
        free_list_head_ = free_list_head_->next;
        // Remember, The size of this block is `BLOCK_SIZE`.
        return p;
    }

    void free(void *p)
    {
        // Return ptr back to free list
        auto head = reinterpret_cast<obj *>(p);
        head->next = free_list_head_;
        free_list_head_ = head;
    }

    // print free list strucutre
    void diagnose()
    {
        printf("----------------------------------\n");
        printf("Blocks: %4d, block size: %4d\n", blocks(), block_size());
        auto p = free_list_head_;
        while (p != nullptr)
        {
            printf("free block @ %p\n", p);
            p = p->next;
        }
        printf("----------------------------------\n");
    }

    inline size_t blocks() const
    {
        return NUM_BLOCKS;
    }

    inline size_t block_size() const
    {
        return BLOCK_SIZE;
    }

private:
    char *chunks_;
    obj *free_list_head_;
};


int main()
{
    // Create a memory pool, with 4 blocks, each block size is 64.
    fixed_mem_pool<64, 4> mempool;
    mempool.diagnose();

    vector<char *> blocks;

    for (auto i = 0; i < mempool.blocks(); i++)
    {
        char *p = reinterpret_cast<char *>(mempool.allocate());
        blocks.push_back(p);
        printf("Got a free block, addr @ %p\n", p);
    }

    try
    {
        // Will bad_alloc because no free block in mempool
        mempool.allocate();
    }
    catch (bad_alloc &)
    {
        printf("Allocated %u memory blocks, each of size %u\n", blocks.size(), mempool.block_size());
    }

    // Use the blocks, this is just a naive demonstration...
    for (auto i = 0; i < blocks.size(); i++)
    {
        snprintf(blocks[i], mempool.block_size(), "This is allocated block #%d.\n", i + 1);
    }

    // Return all blocks back
    for (auto block : blocks)
    {
        mempool.free(block);
    }
    blocks.clear();

    return 0;
}