RTOS位图数据结构
位图概述
位图是一组连续的标志位，每一位用于标识某种状态的有无。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
typedef struct {
uint32_t bitmap;
}Bitmap;
void bitmapInit(Bitmap* bitmap);
void bitmapSet(Bitmap* bitmap, uint32_t pos);
void bitmapClear(Bitmap* bitmap, uint32_t pos);
uint32_t bitmapPosCount(void);
uint32_t bitmapGetFirstSet(Bitmap* bitmap);
// 位图初始化
void bitmapInit(Bitmap* bitmap) {
bitmap->bitmap = 0;
}
// 置位操作
void bitmapSet(Bitmap* bitmap, uint32_t pos) {
assert(pos < 32);
bitmap->bitmap |= 1 << pos;
}
// 置0操作
void bitmapClear(Bitmap* bitmap, uint32_t pos) {
assert(pos < 32);
bitmap->bitmap &= ~(1 << pos);
}
// 返回位图的大小
uint32_t bitmapPosCount() {
return 32;
}
// 查找位图中第一个为1的位，这里使用查找表，为了获得更好的性能
uint32_t bitmapGetFirstSet(Bitmap* bitmap) {
static const uint8_t quickFindTable[] = {
/* 00 */ 0xff, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
/* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
if (bitmap->bitmap & 0xff) {
return quickFindTable[bitmap->bitmap & 0xff];
}
else if (bitmap->bitmap & 0xff00) {
return quickFindTable[(bitmap->bitmap >> 8) & 0xff] + 8;
}
else if (bitmap->bitmap & 0xff0000) {
return quickFindTable[(bitmap->bitmap >> 16) & 0xff] + 16;
}
else if (bitmap->bitmap & 0xff000000) {
return quickFindTable[(bitmap->bitmap >> 24) & 0xff] + 24;
}
else {
return bitmapPosCount();
}
}
END
本文由作者按照 CC BY 4.0 进行授权