重温编程珠玑之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;
}