Linux C 笔记:位图数据结构的定义,用途,使用和原理

什么是位图

位图就是位集合,位集合就是每个元素只有 0 和 1 取值的集合。

怎么创建一个位图

有两种方法,而且它们等效。

方法一 定义 unsigned long 数组

例如:

unsigned long my_bitmap[1]

方法二 使用 DECLARE_BITMAP

例如:

DECLARE_BITMAP(my_bitmap,32)

怎么使用创建的位图

位的操作有三种:置位、清零与测试

主要函数:

  1. set_bit
  2. clear_bit

set_bit 把某位设为 1 (置位)

我要把 my_bitmap 的第 23 位设置为 1:

set_bit(23, my_bitmap)

clear_bit 把某位设为 0 (清零)

我要把 my_bitmap 的第 23 位设置为 0:

clear_bit(23, my_bitmap)

test_bit 获取某位的值(测试)

我要把 my_bitmap 的第 23 位设置为 0:

clear_bit(23, my_bitmap)

位图有什么用?

位图适用于大量意义相同的flag的维护。比如 bt 下载,可以用一个位图指明哪些 piece 已经下载。每个 piece 的 flag 占一位, 0 表示未下载,1 表示已下载。

原理

#define SET_BIT(x, n) (x |= (1 << n))
#define CLR_BIT(x, n) (x &= ~(1 << n))
#define GET_BIT(x, n) ((x >> n) & 0x01)

参考文献

Bit arrays and bit operations in the Linux kernel
linux 内核中的 bitmap
set_bit
常用的位操作:置位、清零与测试

发表留言

本站启用了垃圾评论检测插件,如果误删请联系我~