linux内核中的位图

yanfangsheng123

　　位图(bitmap)是一种非常有用的数据结构，在处理系统中的进程数管理、磁盘中的磁盘块管理、以及内存中的内存页的使用情况管理时非常有用。
　　同时在内核中对位图进行各种操作，现在总结一些常用的操作，以便在以后用到时方便回顾。
　　几个常用的宏定义：
　　

　　#define BIT_PER_TYPE 8  

　　#define __WORDSIZE   32
　　#define BITS_PER_LONG  __WORDSIZE
　　#define DIV_ROUND_UP(nr, d)  \
　　( (nr) + (d) - 1) / (d)
　　这个DIV_ROUND_UP(nr, d)宏的作用是：如果定义了一个： unsinged long name[128]用作位图的话，则 d = 32bits, 在假设 nr = 128*32 - 1，则n在数组中的下标可以通过 nr / 32 = 127来计算出来，而实际的数组name中有128个元素，所有 DIV_ROUND_UP()函数的作用是将比特位与数组的大小关联起来，可以通过 nr 比特位来求出数组的长度。
　　
　　#define BITS_TO_LONGS(bits)  DIV_ROUND_UP(bits, sizeof(long) * BTT_PER_BYTE)

　　#define DEFINE_BITMAP(name, bits) \
　　unsigend long int name[BITS_TO_LONGS(bits)]
　　

　　DEFINE_BITMAP(name, bits）定义了一个比特位图，name为比特位图的名字，bits为比特位图的大小。
　　

　　#define BIT(nr)   1UL << (nr)  //将1左移 nr位
　　

　　#define BIT_MASK(nr)  1UL << ( (nr) % BITS_PER_LONG ) //将第nr位置一；
　　

　　#define BIT_WORD(nr)  (nr / BITS_PER_LONG )  // 用于nr位于那个数组元素之中；
　　

　　#define BITMAP_LAST_WORD_MASK(bits)  \
　　( bits % BITS_PER_LONG ) ?  (1 << (bits % BITS_PER_LONG) ) - 1 : ~0UL
　　

　　BITMAP_LAST_WORD_MASK()主要用于保存第bits位所在的元素中的前(bits % BITS_PER_LONG -1)个位中的值。
　　

　　2.位图中的函数操作：
　　
　　1.判断一个位图是否没有还没有别使用：
　　// bitmap : 位图的起始地址；
　　// bits   : 位图的大小；

　　int __bitmap_empty(unsigned long *bitmap, int bits)
　　{
　　unsigned long *addr= bitmap;

　　unsigned int k, limit;
　　limit = bits / BITS_PER_LONG ; //数组下标值；
　　// 用于看看数组下标为0 - limit-1的数组元素是否都为0；

　　for(k = 0; k < limit ; k++)
　　{
　　if(addr[k])
　　return 0;

　　}
　　//用于看下标为 bits / BITS_PER_LONG 的元素中的 0 - bits%BITS_PER_LONG-1位是否也全都为零

　　if( bits % BITS_PER_LONG )
　　{
　　if( addr[k] & BITMAP_LAST_WORD_MASK(bits) )
　　return 0;

　　}

　　return 1;

　　}
　　如果位图中的所有位都为0，则 int __bitmap_empty()返回 1；否则返回 0；
　　

　　2.判断一个位图中的所有位是否置为 1：
　　int __bitmap_full(unsigned long *bitmap, int bits)
　　{
　　unsigned long *addr = bitmap;
　　int k, limit;
　　limit = bits / BITS_PER_LONG;
　　for(k = 0; k < limit; k++)
　　{
　　// 如果addr[k]中的每个位都为1的话，那么～addr[k]必然为0；
　　// 否则如果addr[k]中有的位为1，有的位为0的话，那么～addr[k]中的每一个位必然也是有的为零，有的为1；
　　if(~addr[k])
　　return 0;

　　}
　　if(bits % BITS_PER_LONG)
　　{
　　if( ~addr[k] & BITMAP_LAST_WORD_MASK(bits) )
　　return 0;

　　}
　　return 1;

　　}
　　

　　3.判断两个位图是否相等，前提时这两个位图的长度必须要相等。
　　int __bitmap_equal(unsigned long *bitmap1, unsigned long *bitmap2, int bits)
　　{
　　int k , limit;
　　limit = bits / BITS_PER_LONG;
　　for(k = 0; k < limit; k++)
　　{
　　// ^ 是异或操作运算符， 如果 a == b 则 a ^ b == 0
　　如果 a != b 则 a ^ b != 0
　　// 所以判断两个数是否相等，可以将这两个数进行异或操作，结果为0，表示相等
　　结果不为0，表示不想等

　　if(bitmap1[k] ^ bitmap[k])
　　return 0;

　　}
　　if(bits % BITS_PER_LONG)
　　{
　　if( (bitmap1[k] ^ bitmap[k]) & BITMAP_LAST_WORD_MASK(bits) )
　　return 0;

　　}
　　return 1;

　　}
　　

　　
　　4. 对一个位图中的所有位进行取反操作，然后将结果存入到另一个位图中：
　　void __bitmap_complement(unsigned long *dest, unsigned long *src, int bits)
　　{
　　int k, limit;
　　limit = bits / BITS_PER_LONG ;
　　for(k = 0 ; k < limit ; k++)
　　dest[k] = ~src[k];
　　if(bits % BITS_PER_LONG )
　　dest[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);

　　}
　　

　　5.判断一个位图是否是另一个位图的子集：
　　此处用到的数学集合的思想： 如果 A 属于 B 话，即A 是 B 的子集的，那么 A 必然不属于 ～B了；   A & ～B其结果必然为0；

　　int __bitmap_subset(unsigned long *bitamp1, unsigned long *bitmap2, int bits)
　　{
　　int k, limit;
　　limit = bits / BITS_PER_LONG ;
　　for(k = 0; k < limit ; k++)
　　{
　　// 用于bitmap1[]中的每个元素的二进制形式是否是bitmap2[]中的每个元素二进制的
　　//子集。如果是的话，则 bitmap1[k] & ～bitmap2[k]为零；否则非零。

　　if(bitmap1[k] & ~bitmap2[k])
　　return 0;

　　}
　　if(bits % BITS_PER_LONG)
　　if((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits) )
　　return 0;
　　return 1;

　　}
　　

　　6.用于求出位图中已经置为1的位的个数：
　　int __bitmap_weight(unsigned long *bitmap, int bits)
　　{
　　int count, k, limit;
　　count = 0;
　　limit = bits / BITS_PER_LONG ;
　　for(k = 0; k < limit ; k++)
　　count += hweight_long(bitmap[k]);
　　if( bits % BITS_PER_LONG )
　　count += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
　　return count;

　　}
　　hweight_long() 用于计算一个8,16,32位的二进制数，1的个数；
　　

　　下面的这几个函数要用到这个宏定义，所以先定义一下：
　　#define small_const_nbits(nbits) \
　　( __builtin_const_p(nbits) && (nbits) <= BITS_PER_LONG )
　　__builtin_const_p(n) 是gcc内嵌的用于判断一个变量的内容是不是一个常数；
　　所以 small_const_nbits()这个宏的主要作用是来判断一个变量的内容是否是一个常数，以及这两个变量的值是否大于32；
　　
　　7.对位图进行初始化：
　　void bitmap_zero(unsigned long *bimap, int nbits)
　　{
　　//如果位图的长度小于32的话

　　if(small_const_nbits(nbits))
　　*bitmap = 0UL;
　　else
　　{           

　　int length = BITS_TO_LONGS(nbits) * sizeof(long);
　　memset(bitmap, 0, length);
　　}

　　}
　　

　　8.对位图进行填充：
　　void bitmap_fill(unsigned long *bitmap, int nbits)
　　{
　　if( small_const_nbits(nbits) )
　　*bitmap = BITS_TO_LONGS(nbits);
　　else
　　{
　　//最后的一个long数组元素可能并没有用完，所以只对用到的进行填充；

　　int length = BITS_TO_LONGS(nbits);
　　int len = (length - 1) * sizeof(long);
　　memset(bitmap, 0xff, len);
　　bitmap[length - 1] = BITS_TO_LONGS(nbits);

　　}

　　}
　　

　　9.位图的拷贝：
　　void bitmap_copy(unsigned long *dest, unsigned long *src, int nbits)
　　{
　　if( small_const_nbits(nbits) )
　　*dest = *src;
　　else
　　{
　　int length = BITS_TO_LONGS(nbits) * sizeof(long);
　　memcpy(dest, src, length);

　　}

　　}
　　

　　下面的这些函数只做说明，并不在介绍其是如何实现：
　　set_bit(int n, unsigned long *addr) //将addr位图中的第n位设置为1；
　　clear_bit(int n, unsigned long *addr) //将addr位图中的第n位置0；
　　change_bit(int n, unsigned long *addr) //将addr位图中的第n位改变，即1变0，0变1；
　　test_bit(int n, unsigned long *addr) //测试addr位图中的第n位是否为1；
　　test_and_set_bit(int n, unsigned long *addr)//测试addr位图中的第n位是否为1，如果不是
　　的话，将其设置为1，其返回值是之前第n位的值；
　　test_and_clear_bit(int n, unsigned long *addr);
　　test_and_change_bit(int n, unsigned long *addr);
　　

　　unsigned int  find_first_zero_bit(unsigned long *addr, int size) //在位图addr中，查找第一个为零的比特位，并返回其位置值；
　　find_first_bit(unsigned long *addr, int size) //在位图addr中，查找第一个为1的比特位，并返回其位置；
　　find_next_zero_bit(unsigned long *addr, int size, int pos) //在位图addr中，从pos开始
　　查找下一个为零的比特位，并返回其位置值；
　　fine_next_bit(unsigned long *addr, int size, int pos)
　　

　　对位图进行遍历操作：
　　#define for_each_bit(bit, addr, size) \
　　for( (bit) = find_firt_bit( (addr), (size) ); \
　　(bit) < (size); \
　　(bit) = find_next_bit( (addr), (size), (bit)+1 ) )  
　　

　　在linux源代码中关于位图各种操作实现位于： /include/linux/bitmap.h   

　　/include/linux/bitops.h
　　/lib/bitmap.c