find_first_zore_bit-一个位图的实现

如果希望在多个地方在一个域内分配一个一个全局唯一的ID（或者IP地址），该怎么办呢？最简单的方式我觉得就是使用位图。Linux内核对位图的支持很强，因此一年前的我直接将kernel里面的代码copy到了OpenVPN，直到我发现OpenVPN在32位平台编译不过去时，才发现问题-决不能将汇编代码随意复制，因为那是高度平台相关的。因此就想用C语言重新实现。

        关键问题是实现将某一个bit设置为1或者0。该怎么实现呢？如果有1000000000000+个位，我总不能搞一个大循环吧...那怎么办？我们知道循环肯定是消耗CPU最多的操作，因为对于循环而言，CPU（包括我们人）都是在做重复的事情，重复的事情是比较无聊的，那么怎么办呢？当然是使用CPU原生支持的指令了，那就是移位。类比Intel x86的页表机制，我们也能将一个字节做出很多“意义”。

        试想有以下的数组：char bits[1024];那么我们可以认为内存中有连续1024字节的空间属于我们，我们怎么寻址到其中的第index位呢？很简单，第一步，我们需要知道这个index所在的位属于数组的第几个元素，而这个很简单：

bits[i >> 3];

为什么要移位3位呢？因为char是8位，而二进制的8（0-7总共8个元素）个数字能表示为3位的二进制数，那么一个index的高5位（8-3）就表示了数组的下标。接下来就需要确定该index在一个byte中的位置，对于Intel系统，它就是：

7 -1 - (i & 0x07)

这样，bit定位就解决了，接下来就是如何设置对应的bit为0或者1的问题了，这更简单：

#define INDEXSFT 3
#define MASK 0x07
#define MAX_BITS 8192
#define BYTEBITS 8

char data_bits[MAX_BITS] = {0};

void set_bit(int i, int data)
{
    if (data == 0) {
        data_bits[i >> INDEXSFT] &= ~( 1 << (BYTEBITS -1 - (i & MASK)));
    } else {
        data_bits[i >> INDEXSFT] |= (1 << (BYTEBITS -1 - (i & MASK)));
    }
}

位图的基础已经实现，最关键的是如何找出第一个为0（即空闲）的bit，因此我们需要实现一个判断函数：

int test_bit(int i)
{
    int res = data_bits[i >> INDEXSFT] & (1 << (BYTEBITS -1 - (i & MASK)));
    return res;
}

那么最后，就剩下实现find_first_zero_bit了：

int find_first_zero_bit(int size)
{
    int i = 0, test_bits = 0;
    int bits = (size+8)/BYTEBITS;
    for (; i < bits; i++) {
        int j = 0;
        for (; j < BYTEBITS; j++) {
            int index = i*BYTEBITS+j;
            if (index > size) {
                return -1;
            } else if (!test_bit(index)) {
                return test_bits;
            }
            test_bits ++;
        }
    }
    return -1;
}

这样，一切就完成了。其实我们还会有有一个helper函数：

int find_first_zero_bit_set(int size)
{
    int zero_bit = find_first_zero_bit(size);
    if (zero_bit != -1) {
        set_bit(zero_bit);
    }
    return zero_bit;
}

整个实现很清爽，很容易维护。我在使用中还加入了序列化，文件锁的操作可以将位图同步到磁盘文件实现持久化，这里就不再赘述了。有一个问题，为何不用int或者long long数组呢？效率还会快一些，比8字节的char要好吧。因为我害怕那些big/littile endian的问题...

         遗留的问题是，怎么将上述实现用PHP以及bash完成，这么做的理由是对于打包少了一次编译的过程，代码也更好维护。姑且不论这么做的价值，最终我想在某个时间搞一次调查，那就是：有谁能一次性成功编写100+行的bash脚本。我每写一个脚本，都要试好几次才能成功，特别是是在makefile里面调用bash，有时3行代码要试一上午，最终发现最后的\标记后面有一个空格...

     ......