位图数据结构

只看该作者 · 2019-6-29 18:49

本节我们来学习一种数据结构为下次我们学习多任务优先级做铺垫，位图数据结构就是一组连续的标志位，每一位用于标识某种状态的有无。下面以32位为例：

只看该作者 · 2019-6-29 18:50

对位图数据结构操作主要分为以下四步：
1. 初始化：即是对所有的标志位清0。
2. 对某一位置1操作。
3. 对某一位清0操作。
4. 查找操作，判断第一位为1的标志位为哪一位（从低位至高位）。

只看该作者 · 2019-6-29 18:50

1. 位图数据结构的定义：
typedef struct
{
uint32_t bitmap;
}t_bitmap;

只看该作者 · 2019-6-29 18:51

2. 位图数据结构的初始化
void BitMapInit(t_bitmap *bitmap)
{
bitmap->bitmap = 0;
}

只看该作者 · 2019-6-29 18:51

3. 位图数据结构某一位置1操作
void BitMapSet(t_bitmap *bitmap,uint32_t pos)
{
bitmap->bitmap |= 1<<pos;
}

只看该作者 · 2019-6-29 18:51

4. 位图数据结构某一位清0操作。
void BitMapClear(t_bitmap *bitmap,uint32_t pos)
{
bitmap->bitmap &= ~(1<<pos);
}

只看该作者 · 2019-6-29 18:51

5. 位图数据结构查找操作，判断第一位为1的标志位为哪一位（从低位至高位）。
uint32_t  BitMapQueryFirstSet(t_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>>8 & 0xff)
{
   return quickFindTable[bitmap->bitmap>>8 & 0xff]+8;
}
  else if(bitmap->bitmap>>16 & 0xff)
{
   return quickFindTable[bitmap->bitmap>>16 & 0xff]+16;
}
else if(bitmap->bitmap>>24 & 0xff)
{
   return quickFindTable[bitmap->bitmap>>24 & 0xff]+24;
}
else
{
return 32;
}

}