Chinaunix首页 | 论坛 | 博客
  • 博客访问: 579787
  • 博文数量: 104
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1559
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-21 00:58
个人简介

锻炼精神,首先要锻炼肉体

文章分类

全部博文(104)

文章存档

2018年(1)

2016年(1)

2015年(101)

2014年(1)

我的朋友

分类: C/C++

2015-04-17 10:40:25

如果你看过操作系统相关的书籍,那么你一定对位图存储这个概念有所了解。

位图在这种情况下也被称作是 "位示图" 它利用二进制中的一个比特位来一一映射磁盘中的一个磁盘块(一个页的大小)是否被使用。
位所指代的是,这个二进制在全部位图中的位置,位置与操作系统中的磁盘块是一一对应的,位置不同,映射的磁盘块也是不同的。

而位上面的数值代表的所映射磁盘块的状态,可以根据不同的编程需要为其赋予不同的语义,可以这样设定:

如果位示图中的 bit = 0 ,可以认为该磁盘块并没有被分配出去,它是空闲的磁盘块。
若有页面
申请可将该 bit 映射的磁盘块分配出去。

如果 bit = 1 ,可以认为该磁盘块已经被分配出去,被占用。
若有页面写申请,并不允许将 bit = 1 所映射的磁盘块的操作权限
分配出去。

在点对点传输文件的过程中,我们通常把资源文件分割成为多个 pieces 进行传输,每个 piece 可以看做是操作系统中的磁盘块,
那么同样我们可以使用位图中的每个 bit 的状态来表示当前下载端点所下载资源文件中每个piece是否已经下载。
这里每个 bit 的位置也是与
文件中的每个 piece 是一一对应的。

可以根据情况为其赋予的含义:
如果 bit = 0 ,则表明当前端点还没有下载到该 bit 对应的文件中的 piece ,
如果 bit = 1 ,说明该文件中的该 piece 已经被下载到本地中。

所有的piece 组成的整体是一个资源文件,所有的 bit 组成的整体便是位图,也就是 bit-map

了解背景知识以后,我们可以分析一下 bit-map 中需要存放信息的变量,以及基于变量所需要执行的操作有哪些,
分析这些可以帮助我们设计并且封装一个 bit-map 的 class 。

1. bit-map 中必须要有存放 0,1 数值的数组
2. bit-map 中必须要有存放有效位长度的变量,用来控制访问0,1 数组的最大限度
3. bit-map 中需要有给某个bit上 置1 或是 置0 的方法
4. bit-map 中需要有从某个 bit 上面取值的方法,用来访问bit-map 中的某个位上的数值,通过bit的数值来判断
   该 bit 所映射的文件块(piece)的状态
5. bit-map 中可以考虑用来在有效长度上为全部位进行置位 (0/1) 的方法
6. bit-map 中可以有一个将全部位进行输出并且显示出来的方法

在 C/C++ 语言中,并没有 bit 单位的变量存在,因为最小的单位便是 unsigned char ,它通常占位 1 byte = 8 bits
所以,在 bit-map 中我们通过操作 unsigned char 来实现对 bit 的操作。

对于存放数值的数组一定是 unsigned char 类型,在这里使用 vectorchar> 来作为bit-map 中存放 bit 的变量。
如果想要找位图中第 index = 234 个bit 上面的数值的话,可以通过
234/8 来锁定,这个 bit 出现在第几个 byte (字节中) 对应映射到的就是 vector> bit_field , 中的 bit_field [234/8] 
而 234 %8 便是这个 bit 出现在第 (234/8) 个字节中的第 (234%8) 个偏移位置上即可。

下面是实现代码,里面用到了 google 的 glog 日志库,详情看 
http://blog.chinaunix.net/uid-28595538-id-4956104.html

//bit_map.h

点击(此处)折叠或打开

  1. #ifndef BIT_MAP_H
  2. #define BIT_MAP_H

  3. #include <vector>

  4. class Bitmap
  5. {
  6. private:
  7.     std::vector<unsigned char> bit_field ;
  8.     int byte_length ;
  9.     int bit_length ;
  10. public :
  11.     Bitmap () {}
  12.     Bitmap ( int need_bit_length )
  13.     {
  14.         bit_length = need_bit_length ;
  15.         byte_length = need_bit_length / 8 ;
  16.     
  17.         // i am afriaid we need one more byte
  18.         if ( (need_bit_length%8) != 0 )
  19.          byte_length += 1 ;
  20.         
  21.         for ( int i = 0 ; i < byte_length ; i++ )
  22.         {
  23.             unsigned char v = 0x00 ; //all bit initialized into 0
  24.             bit_field.push_back ( v ) ;
  25.         }
  26.     }

  27.     ~Bitmap ()
  28.     {
  29.         bit_field.clear () ;
  30.     }

  31.     
  32.     int get_bit_map_value ( int index ) ;
  33.     int set_bit_map_value ( int index , int set_value ) ;
  34.     int set_all ( int set_value ) ;
  35.     void print () ;
  36.     
  37. } ;

  38. #endif

//bit_map.cpp

点击(此处)折叠或打开

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <vector>
  5. #include <glog/logging.h>

  6. #include "bit_map.h"

  7. #define set_value_one(value,index) value|=(1<<index)
  8. #define set_value_zero(value,index) value&=!(1<<index)


  9. using namespace std ;

  10. int Bitmap::set_all ( int set_value )
  11. {
  12.   char v ;

  13.   // first , we check set_value : this should be either 0 or 1
  14.   if ( set_value != 1 && set_value != 0 )
  15.   {
  16.     LOG(WARNING)<<"[warning] set value should be 0 or 1";
  17.     return -1 ;
  18.   }
  19.   
  20.  // justify set_value = 1 or = 0
  21.     
  22.  if ( set_value == 0 )
  23.  {
  24.     v = 0x00 ;
  25.  }
  26.  
  27.  if ( set_value == 1 )
  28.  {
  29.     v = 0xff ;
  30.  }
  31.  for ( int i = 0 ; i < bit_field.size() ; i++ )
  32.  {
  33.     bit_field[i] = v ;
  34.  }
  35.  
  36.   return 0 ;
  37. }


  38. int Bitmap::get_bit_map_value ( int index )
  39. {
  40.     int pos_byte = index / 8 ;
  41.     int pos_bit = index % 8 ;

  42.     // first check whether index is leagal
  43.     // index increase by bit

  44.     if ( index < 0 || index > bit_length )
  45.     {
  46.     LOG(WARNING)<<"[warning] index not illegal ";
  47.     return -1 ;
  48.     }
  49.       
  50.     if ( (bit_field[pos_byte] >> pos_bit)&1)
  51.     {
  52.     return 1 ;
  53.     }
  54.     
  55.    else
  56.    {
  57.     return 0 ;
  58.    }
  59.   
  60.    return -1 ; // this branch could not be reach
  61. }

  62. int Bitmap::set_bit_map_value ( int index, int set_value )
  63. {
  64.    int pos_byte = index / 8 ;
  65.    int pos_bit = index % 8 ;

  66.    printf ("pos_byte %d pos_bit %d\n", pos_byte , pos_bit) ;

  67.    // index legal testing , incr by bits

  68.    if ( index < 0 || index >bit_length )
  69.    {
  70.     LOG(WARNING)<<"[warning] index illegal range";
  71.     return -1 ;
  72.    }

  73.   // then set_value
  74.    
  75.    if ( set_value != 0 && set_value != 1 )
  76.    {
  77.     LOG(WARNING)<<"[warning] input set_value error ";
  78.     return -1 ;
  79.    }

  80.    char value = bit_field[pos_byte] ;
  81.    // now divide two branches by set_value = 1 or 0
  82.    if ( set_value == 1)
  83.    {
  84.     
  85.     printf ("before %x \n", bit_field[pos_byte]) ;
  86.     // call set_value_one
  87.        set_value_one(value,pos_bit ) ;
  88.         bit_field[pos_byte] = value ;
  89.     printf ("after %x \n",bit_field[pos_byte]) ;
  90.    }
  91.    
  92.    if ( set_value == 0 )
  93.    {
  94.     printf ("before %x \n", bit_field[pos_byte]) ;
  95.     // call set_value_zero
  96.       set_value_zero(value,pos_bit) ;
  97.       bit_field[pos_byte] = value ;
  98.     printf ("after %x \n", bit_field[pos_byte]) ;
  99.    }

  100.   
  101.    return 0 ;
  102. }


  103. void Bitmap::print ()
  104. {
  105.   // this method is used to output each bit in each unsigned char
  106.   // as element stored in each vector<char> bit_field ;
  107.     
  108.   for ( int i = 0 ; i < bit_field.size() ;i++ )
  109.   {
  110.     for ( int j = 0 ; j < 7 ; j++ ) // each unsigned char has 8 bits [0...7]
  111.      {
  112.         if ( (bit_field[i] >> j) &1 )
  113.          printf ("1") ;
  114.         else
  115.          printf ("0") ;
  116.     }
  117.     
  118. //    printf ("\n") ;
  119.  }

  120.  printf ("\n") ;
  121. }
//Main.cpp

点击(此处)折叠或打开

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <vector>
  5. #include <glog/logging.h>
  6. #include "bit_map.h"

  7. using namespace std ;

  8. int main ( int argc , char **argv )
  9. {
  10.     int need_bit_length = 1024 ;

  11.     // initialize log system
  12.     google::InitGoogleLogging( argv[0] ) ;
  13.     // set log path
  14.     FLAGS_log_dir = "./log/" ;
  15.     
  16. // test Bitmap's constructor
  17.     Bitmap bitMap(need_bit_length) ;
  18.  
  19. // test Bitmap's set all
  20.     bitMap.set_all( 0 ) ;
  21.     
  22. // test Bitmap's print
  23.     bitMap.print () ;
  24.   
  25.     int index = 5 ;
  26.    
  27. // test Bitmap's set_bit_map_value
  28.     bitMap.set_bit_map_value ( index , 1) ;

  29.     bitMap.print () ;
  30.     
  31. // test Bitmap's get_bit_map_value
  32.    
  33.     int result = bitMap.get_bit_map_value ( index ) ;
  34.     // it must should be 1
  35.    
  36.     printf (" get value = %d \n",result ) ;

  37.     return 0 ;
  38. }
//Makefile

点击(此处)折叠或打开

  1. CPPFLAGS = -O3
  2. LDFLAGS = -lglog

  3. all:Main

  4. clean :
  5.     rm -f *.o Main
  6. Main :Main.o bit_map.o
  7.     g++ -o $@ $^ $(LDFLAGS)
end 
阅读(1546) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~