bitmap 節約記憶體,用一個位去表示兩種狀態.對於數據量比較多的開關量非常適用。 linux提供了相關的介面進行初始化和操作bitmap. include/linux/types.h define DECLARE_BITMAP(name,bits) \ unsigned long name[BIT ...
bitmap
節約記憶體,用一個位去表示兩種狀態.對於數據量比較多的開關量非常適用。
linux提供了相關的介面進行初始化和操作bitmap.
include/linux/types.h
#define DECLARE_BITMAP(name,bits) \
unsigned long name[BITS_TO_LONGS(bits)]bitmap_set
函數原型:
void bitmap_set(unsigned long *map, int start, int nr)
start: 起始位
nr : 長度- 計算start位的WORD的指針地址
- 設置第一個WORD的相應高位為1
- 設置2~n-1(倒數第二個)數據的位為1(通過mask設置,一次設置BITS_PER_LONG位，mask_to_set = ~0UL)
- 設置最後一個數據的相應位為1,可能只有部分低位為1.
bitmap_clear
函數原型:
void bitmap_clear(unsigned long *map, int start, int nr)
start: 起始位
nr : 長度 - 計算start位的WORD的指針地址
- 清除第一個WORD的相應高位為0
- 清除2~n-1(倒數第二個)數據的位為0(通過mask設置,一次設置BITS_PER_LONG位，mask_to_set = ~0UL)
- 設置最後一個數據的相應位為0,可能只有部分低位為1.
__bitmap_empty
函數原型:
int __bitmap_empty(const unsigned long *bitmap, int bits)
功能: 0~bits位是否為空- 計算總共多少個WORD,得到總共lim個
- 遍歷bitmap[0~lim]是否有WORD不是0,有返回0
- 判斷最後一個WORD是否有位為1,,有返回0
- return 1
__bitmap_full
函數原型:
int __bitmap_full(const unsigned long *bitmap, int bits)
功能:判斷0~bits位是否全為1- 計算總共多少個WORD,得到總共lim個
- 遍歷bitmap[0~lim]是否有WORD為0,有返回0
- 判斷最後一個WORD是否有位為0,有返回0
- return 1
__bitmap_equal
函數原型:
int __bitmap_equal(const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: 比較bitmap1和bitmap2 ，從0~bits位相等- 計算總共多少個WORD,得到總共lim個
- 比較bitmap1[0~lim]和bitmap2[0~lim]是否相等,如果不相等返回0
- 比較最後一個WORD剩餘位是否相等(異或bitmap1[lim]和bitmap2[lim]，後與上mask)
__bitmap_shift_right
函數原型:
void __bitmap_shift_right(unsigned long *dst,
const unsigned long *src, int shift, int bits)
功能: 把長度為bits位的src右移shift位後保存到dst中- 計算整個bitmap的長度為多少個WORD(lim),剩餘的位數left, 計算公式bits = lim * BITS_PER_LONG + left
- 計算右移的WORD數off,和剩餘的位數(rem) ,計算公式shift = off * BITS_PER_LONG + rem
- 右移bitmap[0~lim-1], 獲取右移後,用下個WORD(或0)填充高位部分(upper),
獲取右移得到的低位部分(lower), dst[0~lim-1] = upper | lower.- 如果是最後一個WORD，右移rem位後,高位用0填充;採用mask的方式實現
- 如果left不等於0,最後第2個WORD的upper部分，最後一個WORD只有部分bits,需要mask不屬於的bits為0
- 把右移後,左邊的相應的MSB位清0
__bitmap_shift_left
函數原型
void __bitmap_shift_left(unsigned long *dst,
const unsigned long *src, int shift, int bits)
功能: 把長度為bits位的src左移shift位後保存到dst中整個流程跟__bit_shift_right一樣，只是左移換成右移,低位填0.
- 計算整個bitmap的長度為多少個WORD(lim),剩餘的位數left, 計算公式bits = lim * BITS_PER_LONG + left
- 計算右移的WORD數off,和剩餘的位數(rem) ,計算公式shift = off * BITS_PER_LONG + rem
- 左移bitmap[lim-1~0],獲取低位lower,獲取高位,
dst[] = upper | lower- lower 是前一個WORD(src[k-1])的高rem位
- upper 是當前的WORD(src[k])的左移rem位
- src[lim-1]的WORD,如果left不為0, mask不屬於bits的位為0
- 左移後的最後剩餘WORD都需要清0
__bitmap_and
函數原型:
int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: bitmap1和bitmap2進行與操作並把值保存到dst中。__bitmap_or
函數原型:
void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: bitmap1和bitmap2進行或操作並把值保存到dst中。 __bitmap_xor
函數原型:
void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: bitmap1和bitmap2進行異或操作並把值保存到dst中。__bitmap_andnot
函數原型:
int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: bitmap1和bitmap2進行與非(~bitmap2)操作並把值保存到dst中。__bitmap_intersects
函數原型:
int __bitmap_intersects(const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: bitmap1和bitmap2進行與的操作，如果存在都為1的位,返回1,不存在返回0
判斷bitmap1和bitmap2是否有相同的位被設置__bitmap_subset
函數原型:
int __bitmap_subset(const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits)
功能: 判斷bitmap2是否是bitmap1的子集,是返回1,不是返回0__bitmap_weight
函數原型:
int __bitmap_weight(const unsigned long *bitmap, int bits)
功能: 計算漢明權重大小,即bitmap中1的個數- 漢明權重 Hammingcode是指一個字串中非0符號的個數(TheHamming weight of a stringis
the number of symbols that are different from the zero-symbol ofthealphabetused.）
應用到2進位符號序列中來，即二進位串中1的個數就是該串的Hammingcode.
未完待續......
