[应用相关]

位图数据结构

[复制链接]
439|13
手机看帖
扫描二维码
随时随地手机跟帖
dingbo95|  楼主 | 2019-6-29 18:49 | 显示全部楼层 |阅读模式
本节我们来学习一种数据结构为下次我们学习多任务优先级做铺垫,位图数据结构就是一组连续的标志位,每一位用于标识某种状态的有无。下面以32位为例:
135335d174250ae56d.png

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:50 | 显示全部楼层
对位图数据结构操作主要分为以下四步:
1.        初始化:即是对所有的标志位清0。
2.        对某一位置1操作。
3.        对某一位清0操作。
4.        查找操作,判断第一位为1的标志位为哪一位(从低位至高位)。

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:50 | 显示全部楼层
1.        位图数据结构的定义:
typedef struct
{
uint32_t bitmap;
}t_bitmap;

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:51 | 显示全部楼层
2.        位图数据结构的初始化
void BitMapInit(t_bitmap *bitmap)
{
bitmap->bitmap = 0;
}

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:51 | 显示全部楼层
3.        位图数据结构某一位置1操作
void BitMapSet(t_bitmap *bitmap,uint32_t pos)
{
  bitmap->bitmap |= 1<<pos;
}

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:51 | 显示全部楼层
4.        位图数据结构某一位清0操作。
void BitMapClear(t_bitmap *bitmap,uint32_t pos)
{
bitmap->bitmap &= ~(1<<pos);
}

使用特权

评论回复
dingbo95|  楼主 | 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;
        }
       
}

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:52 | 显示全部楼层
下面我们在任务1中对刚才编写的位图结构进行测试,首先定义了是三个变量:
t_bitmap bitmap;  //位图结构变量
int i;  //用于循环的变量
uint32_t  numbit; //用于临时存储从查询位图结构中的位置数据变量

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:52 | 显示全部楼层
接着在任务1中先对位图结构初始化,通过循环方式从31位到0位依次置1,再通过位图数据结构查找操作读出第一位置1的位置。然后再通过循环方式从0位到31位依次清0,再通过位图数据结构查找操作读出第一位置1的位置。
394915d1742ef786ea.png

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:52 | 显示全部楼层
开始Debug来观察一下,验证位图结构是否正确操作,现在BitMapInit(&bitmap)位置设置断点,单步执行,位图结构已经被初始化完毕,其值为0。
762445d17430803120.png

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:53 | 显示全部楼层
单步F11 通过循环方式从31位到0位依次置1,看下位图数据结构查找操作读出的numbit变量变化,执行第一次,numbit的值已经变为31
133645d174324895ad.png

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:54 | 显示全部楼层
在下一个循环处设置断点,全速运行,将从31位到0位依次置1操作完成,这时bitmap的值为0xffffffff,numbit的值已经变为0。
906305d17434875d34.png

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:54 | 显示全部楼层
下一个循环同样操作,执行一次清0操作,bitmap的值为0xfffffffe,numbit的值已经变为1。
147185d174364e9891.png

使用特权

评论回复
dingbo95|  楼主 | 2019-6-29 18:54 | 显示全部楼层
在task1Flag = 1处设置断点,全速运行,将完成从0位到31位依次清0操作,这时bitmap的值为0x00000000,numbit的值已经变为32。
108385d17437c7ca41.png

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

52

主题

1197

帖子

5

粉丝