C语言查表法问题

在设计内存管理器时，经常需要根据内存的size找到对应的数组index，查表是个不错的解决办法。

 

假设有一个数组，数组中每个元素代表一个范围，任意给定一个数，要尽可能快得找到其对应的数组索引，有什么好的办法么？

 

例如，数组为

范围  [0,1) [1,2) [2,4) [4,8) [8,16) [16,32) [32,64) [64,128)

索引    0     1     2     3     4       5       6       7     

 

给定一个数37，那么由于在[32,64)范围内，故应返回索引6。

通过以下程序可生成一张索引表：

#include <stdio.h>
#include <stdlib.h>

#define MIN_MASK 5
#define MAX_MASK 12

#define MIN_VALUE (1 << (MIN_MASK))
#define MAX_VALUE (1 << (MAX_MASK))
#define DIF_VAL   (1 << ((MAX_MASK) - (MIN_MASK)))

#define ONELINE_MASK 4
#define ONELINE   (1 << (ONELINE_MASK))

int main(void)
{
    FILE *fp = fopen("c:\\data.txt", "w");
    fprintf(fp, "static char index_table[] = {\n\t");
    int idx = 0, idv = 1, lnc = 1, i;
    for (i = 0; i < DIF_VAL; i++, lnc++) {
        if (i >= idv) {
            idx++;
            idv <<= 1;
        }
        if (lnc > ONELINE) {
            fprintf(fp, "\n\t");
            lnc = 1;
        }
        fprintf(fp, "%d, ", idx);
    }
    fprintf(fp, "\n};");
    fclose(fp);
    return 0;
}

生成如下查找表

static char index_table[] = {
    0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
};

则可通过size_to_index完成从size到index的转换

static inline int size_to_index(unsigned int size)
{
    return index_table[size >> MIN_MASK];
}