重温编程珠玑之bitmap

不知不觉毕业一年了，这一年在基本都是全身心地学习公司的项目开发流程与业务内容，作为code的核心的算法部分倒有些生疏了， 还是在本科时期看过«编程珠玑»这本书，给我的启发很大，现在想通过1个月左右的时间将该书算法部分重写一遍， 为了更好的向前，有时候是需要后退记不得。

kam@ubuntu:pearl$ cat bit_map.c

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

typedef unsigned int uint32_t;
typedef unsigned char uchar;

struct bit_map {
    uint32_t size;
    uchar *map;
};

#define IS_POWER_TWO(num) (((num) & ((num) - 1)) == 0)
#define MASK(n) ((n) & 7)
#define SET(ch, n) ((ch)|=(1 << MASK(n)))
#define CLR(ch, n) ((ch)&=(~(1 << MASK(n))))
#define TEST(ch, n) ((ch)&(1 << MASK(n)))

uint32_t get_map_count(struct bit_map *map) {
      uint32_t count = map->size >> 3;  
        printf("count: %u\n", count);
      return count? count : 1;
}

int set_bit_map_size(struct bit_map *map, uint32_t size) {
    if(IS_POWER_TWO(size)) {
        map->size = size;
    }

    size |= size >> 1;
    size |= size >> 2;
    size |= size >> 4;
    size |= size >> 8;
    size |= size >> 16;

    map->size = size + 1;

    printf("resize: %u\n", map->size);

    map->map = (uchar *)calloc(get_map_count(map), 1);
    return 0;
}

int bit_map_init(struct bit_map *map, uint32_t size) {
    set_bit_map_size(map, size);
    return 0;
}

int bit_map_set(struct bit_map *map, uint32_t num) {
    SET(map->map[num >> 3], num);
    return 0;
}

int bit_map_clear(struct bit_map *map, uint32_t num) {
    CLR(map->map[num >> 3], num);
}

int bit_map_test(struct bit_map *map, uint32_t num) {
    return TEST(map->map[num >> 3], num);
}

int bit_map_destory(struct bit_map *map) {
    map->size = 0;
    free(map->map);
    return 0;
}

uint32_t nums[] = { 10023, 345654, 12342, 1232, 41, 457, 12456, 167432, 124752 };

int main() {

    struct bit_map bmap;

    bit_map_init(&bmap, 10000000);

    for(int i = 0; i < sizeof(nums) / sizeof(uint32_t); ++i) {
        bit_map_set(&bmap, nums[i]);
    }

    for(int i = 0; i < sizeof(nums) / sizeof(uint32_t); ++i) {
        if(bit_map_test(&bmap, nums[i])) {
            printf("num: %u\n", nums[i]);
        }

        if(bit_map_test(&bmap, 24562)) {
            printf("error\n");
        }
    }

    printf("print sorted nums\n");
    for(int i = 10000000 -1; i >= 0; --i) {
        if(bit_map_test(&bmap, i)) {
            printf("num: %u\n", i);
        }
    }

    bit_map_destory(&bmap);
    return 0;

}