如果你看过操作系统相关的书籍,那么你一定对位图存储这个概念有所了解。
位图在这种情况下也被称作是 "位示图" 它利用二进制中的一个比特位来一一映射磁盘中的一个磁盘块(一个页的大小)是否被使用。
位所指代的是,这个二进制在全部位图中的位置,位置与操作系统中的磁盘块是一一对应的,位置不同,映射的磁盘块也是不同的。
而位上面的数值代表的所映射磁盘块的状态,可以根据不同的编程需要为其赋予不同的语义,可以这样设定:
如果位示图中的 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
阅读(1546) | 评论(0) | 转发(0) |