fastdb中的位图应用

位图内存管理：　　

　　每块内存用一个二进制位表示它的使用状态，如果该块内存被占用，则把对应位图中的对应位置1，如果空闲则置0，原理十分简单。计算机里面处理的位数最少的变量是字节（byte），所以也就是8位做为一个整体来对待，8位表示的整数是从0到255。

　　fastdb中database的allocate实现定义了如下几个数组。

static byte const firstHoleSize [] = {
    8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
    5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
};
static byte const lastHoleSize [] = {
    8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};
static byte const maxHoleSize [] = {
    8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
    5,4,3,3,2,2,2,2,3,2,2,2,2,2,2,2,4,3,2,2,2,2,2,2,3,2,2,2,2,2,2,2,
    6,5,4,4,3,3,3,3,3,2,2,2,2,2,2,2,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
    5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
    7,6,5,5,4,4,4,4,3,3,3,3,3,3,3,3,4,3,2,2,2,2,2,2,3,2,2,2,2,2,2,2,
    5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
    6,5,4,4,3,3,3,3,3,2,2,2,2,2,2,2,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
    5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,0
};
static byte const maxHoleOffset [] = {
    0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,0,1,5,5,5,5,5,5,0,5,5,5,5,5,5,5,
    0,1,2,2,0,3,3,3,0,1,6,6,0,6,6,6,0,1,2,2,0,6,6,6,0,1,6,6,0,6,6,6,
    0,1,2,2,3,3,3,3,0,1,4,4,0,4,4,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,5,
    0,1,2,2,0,3,3,3,0,1,0,2,0,1,0,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,7,
    0,1,2,2,3,3,3,3,0,4,4,4,4,4,4,4,0,1,2,2,0,5,5,5,0,1,5,5,0,5,5,5,
    0,1,2,2,0,3,3,3,0,1,0,2,0,1,0,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,6,
    0,1,2,2,3,3,3,3,0,1,4,4,0,4,4,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,5,
    0,1,2,2,0,3,3,3,0,1,0,2,0,1,0,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,0
};

　　firstHoleSize[]，lastHoleSize[]，maxHoleSize[]，maxHoleOffset[]四个固定的数组，每个数组都有256个元素，对应从0到255的整数。输入数组的下标获得二进制内存代表的页面被占用情况。firstHoleSize数组表示从右向左数该数值的“洞”的个数，遇到占用结束计数；lastHoleSize数组表示从左向右数该数值的“洞”的个数，遇到占用结束计数。

举例来说：二进制内存B00001010代表十进制的10，内存占用如下：

firstHoleSize[]表示上面内存占用中，从右到左未被占用的页面有多少个。如上图所示，只要内存末位为是1，那么肯定没有“洞”,所以奇数全为0。该二进制内存通过firstHoleSize获得内存从右到左数，空洞个数为：firstHoleSize[10] = 1。lastHoleSize[]表示从左到右，未被占用的页面多少个，只要最左位为1，那是肯定没有“洞”,所以大于128的全是0，该二进制内存通过lastHoleSize获得从左到右数，空洞个数为：lastHoleSize[10] = 4。maxHoleSize[]，表示连续的最大的“洞”是多少个页面，该二进制内存通过maxHoleSize获得连续的最大的空洞个数为：maxHoleSize[10] = 4。maxHoleOffset[]是和maxHoleSize[]一起使用的，表示从右到左数，最大的“洞”的位置，该二进制内存通过maxHoleOffset获得最大的“洞”的位置为：maxHoleOffset[10] = 4。

依据上述规则，故形成上述表格数组数据。在内存空间的分配时，从管理位图内存的数组中取出相应位图数，先看看是不是有以前释放的满足要求，没有的话就从未分配内存空间中分配。

　　32位操作系统对应fastdb的内存分配示意图如下

参考：http://blog.csdn.net/liuxuezong/article/details/8702382