如何来管理空闲资源，显而易见的是组织成一个双向链表，称作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最大65536ArrayB的数组定义：int arrayB[];int型为两个short型结构体形象化表示ArrayB：
#define NUM 8struct 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]; //是为ArrayAstruct 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节点以及空闲块的分配算法不好，而上述的方法就可以用，效果比较好，也就是说，将一点点的工作施放于每次分配/释放的时候，就可以避免在某个时间点做大量的积攒下来的繁重的工作。这个算法省去了遍历操作，代价就是占用了一点连续的地址空间。
停止每日在车水马龙的市井里忙碌的穿梭，
