完整链表只用一个malloc

Question

我正在编写一个将使用链表分配内存的程序。

目标是减少对 malloc() 函数的调用次数。

为此，我设想了以下分配函数：(head (Slot<T>*) 和 free_slots(int) 是分配器的一部分)

 inline T* allocate(size_t length)
{
    if(free_slots == 0){
        head = (Slot<T>*) malloc(length * sizeof(Slot<T>) * NBR_NEW_OBJECT);
        free_slots = NBR_NEW_OBJECT;
    }

    T* result = &(head->data);
    head = static_cast<Slot<T>* >(head->next);
    return result;
}

我已经定义了Slot结构：

template <typename T>
struct Slot{
   T data;
   Slot* next;
};

但是我们第二次进入分配方法（第一次没问题）我遇到了段错误。你有什么想法吗？

Answer 1

看来最好的方法是先初始化所有的Slot->next字段所以正确的实现应该是：

inline T* allocate(size_t length)
{

    if(free_slots == 0){
        head = (Slot<T>*) malloc(length * sizeof(Slot<T>)  * NBR_NEW_OBJECT);
        free_slots = NBR_NEW_OBJECT;

        for(int i = 0; i < NBR_NEW_OBJECT; i++)
                head[i].next = reinterpret_cast<Slot<T>* >(&head[i+1]);

    }

    T* result = &(head->data);
    head = reinterpret_cast<Slot<T>* >(head->next);
    free_slots--;
    return result;
}

完整链表只用一个malloc

Use only One malloc for a complete linked list

c++

malloc

list

allocator

singly-linked-list