适用于连续资源块的数组空闲链表的算法

editor-side-new">

如何来管理空闲资源，显而易见的是组织成一个双向链表，称作freelist，然后每次从该链表上取出一个，释放的时候再放回去。为了减少碎片，最好的策略就是优先分配最近释放掉的那个，如果能考虑合并的话，类似伙伴系统那样，就再好不过了，本文给出的是一个通用的可以将资源映射到一个整型ID的资源分配算法，完全基于一个数组，不需要内存管理，也不需要分配结构体。
组织链表的时候，内存管理要耗去大量的工作，前向指针和后向指针的修改前提是必须有这些指针。典型的数据结构就是Linux内核的list_head结构体。但是对于静态的类似位图的资源并不适合用list_head来组织，因为这类资源本身可以映射到一块连续的以自然数计数的ID，比较典型的就是磁盘的空闲块，连续内存块的分配。
既然资源位置是连续的，它就一定能用连续的自然数来表示，那么所有的资源就可以表示成一个数组了-其映射成自然数的ID的数组，记为ArrayA。
接下来我们需要另外一个数组来表示空闲链表，记为ArrayB。
接下来的然后，就是构造ArrayB了...ArrayB的大小等于ArrayA大小加上1，多出来的这个元素可以作为不动点存在，它是不会被分配出去的。ArrayB的元素的大小是ArrayA数组大小占据字节数的两倍，是为了在一个元素中存储两个INDEX，比如数组大小可以用8位数据表示，即最多256个元素，那么ArrayB的元素就应该是2*8这么大的，举例说明：
数组大小：short-最多65536个元素
ArrayA的数组定义：int arrayA[MAX];MAX最大65536
ArrayB的数组定义：int arrayB[];int型为两个short型
结构体形象化表示ArrayB：

#define NUM    8
struct freeHL {
        short high_preindex; //表示前一个ArrayA数组中索引
        short low_nextindex;  //表示后一个ArrayA数组中索引
};
struct freeHL  freelist[NUM+1];

相当于将ArrayB劈开成了两半。
然后就可以在连续的数组空间进行链接操作了。实际上这个数组表示的freelist和指针表示的prev，next的freelist是一致的，数组下标也是一个指针，只是在数组表示的freelist中，使用的是相对指针偏移而已，表示为下标！
下面就是一个算法实现问题了，很简单。在freelist中分配了一个index后，需要修改其前向index的后向index以及后向index的前向index，释放过程和分配过程相反。代码如下：

short data[NUM]; //是为ArrayA
struct freeHL  freelist[NUM+1]; /是为ArrayB
//表示一个下一个分配的index;
unsigned int position = 0;
//全局的一次性初始化，注意，如果是序列化到了文件，
//则不能再次初始化了，应该从文件反序列化来初始化。
void list_init()
{
        int i = 0, j = -1;
        for (; i < NUM+1; i++) {
                freelist[i].high_preindex = (i + NUM)%(NUM+1);
                freelist[i].low_nextindex = (i + 1)%(NUM+1);
        }
        position = 0;
}
//分配接口
int nalloc()
{
        int ret_index = -1, next_index = -1, pre_index = -1;
        ret_index = position;
    //保存当前要分配index的前向index
        next_index = freelist[position].low_nextindex;
    //保存当前要分配index的后向index
        pre_index = freelist[position].high_preindex;
    //分配当前index
        position = next_index;
        if (ret_index == next_index) {
                return -1;
        }
    //更新当前index前向index的后向index
        freelist[freelist[ret_index].high_preindex].low_nextindex = next_index;
    //更新当前index后向index的前向index
        freelist[freelist[ret_index].low_nextindex].high_preindex = pre_index;
        return ret_index;
}
//释放接口
int nfree(unsigned int id)
{
        int pos_pre = -1, pos_next = -1;
    //保存下一个要分配的index的前向index，减少碎片以及更加容易命中cache
        pos_pre = freelist[position].high_preindex;
    //释放index为id的元素
        freelist[pos_pre].low_nextindex = id;
        freelist[id].high_preindex = pos_pre;
        freelist[id].low_nextindex = position;
    //下一个要分配的index为刚释放的index
        position = id;
}

下面是一个测试：

int main(int argc, char **argv)
{
        list_init();
        int i = 0;
        printf("begin\n");
        for (; i < NUM+1; i++) {
                printf("\n%d \n", nalloc());
        }
        nfree(5);
        nfree(0);
        nfree(7);
        for (i = 0; i < NUM+1; i++) {
                printf("\n%d \n", nalloc());
        }
        printf("\nend\n");
}

这个代码用在何处呢？前面说过，用在资源可以表示为连续ID的场合，这种场合何在？在《编写一个UNIX文件系统》中，我说那个空闲i节点以及空闲块的分配算法不好，而上述的方法就可以用，效果比较好，也就是说，将一点点的工作施放于每次分配/释放的时候，就可以避免在某个时间点做大量的积攒下来的繁重的工作。这个算法省去了遍历操作，代价就是占用了一点连续的地址空间。