[c++,BitTorrent]编程实现封装位图 Bitmap

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

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

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

如果位示图中的 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

#ifndef BIT_MAP_H
#define BIT_MAP_H

#include <vector>

class Bitmap
{
private:
    std::vector<unsigned char> bit_field ;
    int byte_length ;
    int bit_length ;
public :
    Bitmap () {}
    Bitmap ( int need_bit_length )
    {
        bit_length = need_bit_length ;
        byte_length = need_bit_length / 8 ;

        // i am afriaid we need one more byte
        if ( (need_bit_length%8) != 0 )
           byte_length += 1 ;

        for ( int i = 0 ; i < byte_length ; i++ )
        {
            unsigned char v = 0x00 ; //all bit initialized into 0
            bit_field.push_back ( v ) ;
        }
    }

    ~Bitmap ()
    {
        bit_field.clear () ;
    }


    int get_bit_map_value ( int index ) ;
    int set_bit_map_value ( int index , int set_value ) ;
    int set_all ( int set_value ) ;
    void print () ;

} ;

#endif

//bit_map.cpp

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <glog/logging.h>

#include "bit_map.h"

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


using namespace std ;

int Bitmap::set_all ( int set_value )
{
  char v ;

  // first , we check set_value : this should be either 0 or 1
  if ( set_value != 1 && set_value != 0 )
  {
    LOG(WARNING)<<"[warning] set value should be 0 or 1";
    return -1 ;
  }

 // justify set_value = 1 or = 0

 if ( set_value == 0 )
 {
    v = 0x00 ;
 }

 if ( set_value == 1 )
 {
    v = 0xff ;
 }
 for ( int i = 0 ; i < bit_field.size() ; i++ )
 {
    bit_field[i] = v ;
 }

  return 0 ;
}


int Bitmap::get_bit_map_value ( int index )
{
    int pos_byte = index / 8 ;
    int pos_bit = index % 8 ;

    // first check whether index is leagal
    // index increase by bit

    if ( index < 0 || index > bit_length )
    {
    LOG(WARNING)<<"[warning] index not illegal ";
    return -1 ;
    }

    if ( (bit_field[pos_byte] >> pos_bit)&1)
    {
    return 1 ;
    }

   else
   {
    return 0 ;
   }

   return -1 ; // this branch could not be reach
}

int Bitmap::set_bit_map_value ( int index, int set_value )
{
   int pos_byte = index / 8 ;
   int pos_bit = index % 8 ;

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

   // index legal testing , incr by bits

   if ( index < 0 || index >bit_length )
   {
    LOG(WARNING)<<"[warning] index illegal range";
    return -1 ;
   }

  // then set_value

   if ( set_value != 0 && set_value != 1 )
   {
    LOG(WARNING)<<"[warning] input set_value error ";
    return -1 ;
   }

   char value = bit_field[pos_byte] ;
   // now divide two branches by set_value = 1 or 0
   if ( set_value == 1)
   {

    printf ("before %x \n", bit_field[pos_byte]) ;
    // call set_value_one
       set_value_one(value,pos_bit ) ;
        bit_field[pos_byte] = value ;
    printf ("after  %x \n",bit_field[pos_byte]) ;
   }

   if ( set_value == 0 )
   {
    printf ("before %x \n", bit_field[pos_byte]) ;
    // call set_value_zero
      set_value_zero(value,pos_bit) ;
      bit_field[pos_byte] = value ;
    printf ("after %x \n", bit_field[pos_byte]) ;
   }


   return 0 ;
}


void Bitmap::print ()
{
  // this method is used to output each bit in each unsigned char
  // as element stored in each vector<char> bit_field ;

  for ( int i = 0 ; i < bit_field.size() ;i++ )
  {
    for ( int j = 0 ; j < 7 ; j++ ) // each unsigned char has 8 bits [0...7]
     {
        if ( (bit_field[i] >> j) &1 )
           printf ("1") ;
        else
           printf ("0") ;
    }

//    printf ("\n") ;
 }

 printf ("\n") ;
}

//Main.cpp

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <glog/logging.h>
#include "bit_map.h"

using namespace std ;

int main ( int argc , char **argv )
{
    int need_bit_length = 1024 ;

    // initialize log system
    google::InitGoogleLogging( argv[0] ) ;
    // set log path
    FLAGS_log_dir = "./log/" ;

// test Bitmap's constructor
    Bitmap bitMap(need_bit_length) ;

// test Bitmap's set all
    bitMap.set_all( 0 ) ;

// test Bitmap's print
    bitMap.print () ;

    int index = 5 ;

// test Bitmap's set_bit_map_value
    bitMap.set_bit_map_value ( index , 1) ;

    bitMap.print () ;

// test Bitmap's get_bit_map_value

    int result = bitMap.get_bit_map_value ( index ) ;
    // it must should be 1

    printf (" get value = %d \n",result ) ;

    return 0 ;
}

//Makefile

CPPFLAGS = -O3
LDFLAGS = -lglog

all:Main

clean :
    rm -f *.o Main
Main :Main.o bit_map.o
    g++ -o $@ $^ $(LDFLAGS)

end