首页 > 代码库 > linux内核中的位图

linux内核中的位图

    位图(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

本文出自 “阿辉仔” 博客,请务必保留此出处http://weiguozhihui.blog.51cto.com/3060615/1575876

linux内核中的位图