allocator_bit_vector.cc

简单的动态内存管理程序源代码

// file: allocator_bit_vector.cc
// author: Marc Bumble
// June1, 2000
// Class and functions used to maintain a bit vector for memory allocation
// Copyright (C) 2000 by Marc D. Bumble

//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.

//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.

//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

#include <allocator_bit_vector.h>

namespace allocator_bit_vector {

  //////////////////////////////////////////////////////////////////////////////////
  //////                        Bit Vector routines
  //////////////////////////////////////////////////////////////////////////////////
  /////
  /////    These routine search, mark, and free bits within the bit vectors found 
  /////    on the allocated memory pages
  /////
  //////////////////////////////////////////////////////////////////////////////////
  

  // allocator_bit_vector constructor
  allocator_bit_vector_t::allocator_bit_vector_t(int num_of_elements,
						 unsigned char* start_addr) :
    bit_vec_sz((num_of_elements/8) + 1),
    nelem(num_of_elements) {
    
    bit_vec=start_addr;
    head=0;			// set head to point to the first free block
    for (int i=0; i<bit_vec_sz; i++)
      bit_vec[i]=0x00;
  };

  // copy constructor
  allocator_bit_vector_t::allocator_bit_vector_t(const allocator_bit_vector_t& t)
    : bit_vec_sz(t.bit_vec_sz),
      nelem(t.nelem) {

    // Copy  constructors do  not make  sense  for this  class as  the
    // location  of the bit  vector data  is not  an attribute  of the
    // class, so copying it does not make sense.

    bit_vec=t.bit_vec;		// copy data address for bit vector
    head=t.head;
    for (int i=0; i<bit_vec_sz; i++) {
      bit_vec[i]=t.bit_vec[i];
    }
  };  // copy constructor
  
  // assignment
  allocator_bit_vector_t& allocator_bit_vector_t::operator=(const allocator_bit_vector_t& t) {
    if (this != &t) {
      head=t.head;
      for (int i=0; i<bit_vec_sz; i++) {
	bit_vec[i]=t.bit_vec[i];
      }
    }  //  if (this != &t)
    return *this;
  };  // assignment

  // equality
  bool allocator_bit_vector_t::operator==(const allocator_bit_vector_t& t) {
    bool return_val=true;
    // Take  the XNOR  of  every byte  to  check for  equality of  the
    // vectors
    for (int i = 0; ((i < bit_vec_sz) && (return_val)); i++)
      return_val = !(bit_vec[i] ^= t.bit_vec[i]);
    return return_val;
  };
  

  void allocator_bit_vector_t::mark_items(int global_start_block,int blocks_needed) {
    // Mark the reqested block as assigned.  At the end, if the
    // head block is being assigned, move the head block to point
    // to the next (ie first) free block.  See at bottom

    
    // The const 8 here is 8 bits per byte
    int start_block         = global_start_block%nelem;
    int start_bit           = start_block%8;
    int start_byte          = start_block/8;
    int block_count         = blocks_needed;
    // get the byte - const 8 ==  8 bits/(unsigned char)
    std::bitset<8> val = bit_vec[start_byte];
    if ((start_bit)||(block_count<8)) {
      // if bits to be marked begin with less than one full char
      for (int i=start_bit; ((i<8)&&(block_count>0)); i++,block_count--) {
	// set the bit
	val.set(i,1);
      } // 
      // write the byte back
      bit_vec[start_byte] = val.to_ulong();
      start_byte++;		// increment the start byte
    }  // if ((start_bit)||(((unsigned)block_count)<sizeof(unsigned char)))
    // Now proceed byte by byte
    if (block_count >= 8) {
      // if still need more blocks, go char by char
      while (block_count>=8) {
	bit_vec[start_byte] = 0xff;
	start_byte++;
	block_count-=8;
      } // while (block_count>8)
    } // if (block_count > 8)
    if (block_count>0) {
      // Still need final blocks < full bytes worth
      // Allocate bit by bit
      // get the byte
      val = bit_vec[start_byte];
      for (int i=0; ((i<8) && (block_count));
	   i++,block_count--) {
	// set the bit
	val.set(i,1);
      }
      bit_vec[start_byte] = val.to_ulong();
    }
    // Now adjust the head block to point to the next free block if necessary.
    if (head == global_start_block) {
      head = find_next_free_block(global_start_block,1);
    }
    
  }; // mark()
  
  
  void allocator_bit_vector_t::clear_items(int global_start_block, int blocks_needed) {
    // Release num_of_blocks in the bit vector starting at start_block by
    // clearing the corresponding bits.  Once completed, if the head block
    // pointer is greater than the newly released blocks, move the head
    // backwards to allow memory to be recycled.
    
    int start_block       = global_start_block%nelem;
    int start_byte        = start_block/8;
    int start_bit         = start_block%8;
    int block_count       = blocks_needed;

    std::bitset<8> val = bit_vec[start_byte];
    if ((start_bit)||(block_count<8)) {
      // clear initial bits
      for(int i=start_bit; ((i<8)&&(block_count)); i++,block_count--) {
	val.reset(i);
      }
      bit_vec[start_byte] = val.to_ulong();
      // next see if byte by byte clearing makes sense
      start_byte+=1;
    }
    if (block_count>=8) {
      // if still need more blocks, go char by char
      while (block_count>=8) {
	bit_vec[start_byte] = 0x00;
	start_byte++;
	block_count-=8;
      } // while (block_count>8)
    }
    // Now finish off any non-integral or individual trailing bits
    if (block_count>0) {
      val = bit_vec[start_byte];
      for (int i=0; ((i<8) && (block_count));
	   i++,block_count--) {
	// set the bit
	val.reset(i);
      }
      bit_vec[start_byte] = val.to_ulong();
    }
    // if the head point is greater than the newly freed address, move the
    // head backwards to attempt memory recyling
    if (head > global_start_block)
      head = global_start_block;
  }; // clear()
  
  
  //////////////////////////////////////////////////////////////////////////////////
  //////                          find_free_items
  //////////////////////////////////////////////////////////////////////////////////
  /////
  /////    Finds a free block of space containing blocks_needed.  Returns the 
  /////    starting block address, or -1 if no suitable block is available in
  /////    this chunk.
  /////    
  /////    
  /////    Works in 3 stages:
  /////          1. Searchs individual bits until full free integral chars
  /////          2. Searches char by char in the allocator_bit_vector_t
  /////          3. Searches through any necessary tailing individual bits/////          
  /////          
  /////          
  //////////////////////////////////////////////////////////////////////////////////
  
  int allocator_bit_vector_t::find_free_items(size_type blocks_needed) {
    
    // First, get head block
    int start_block;
    if (head==-1) {
      return head;
    } else {
      start_block = head;
    }
    // int start_block = head;

    // const 8 is the number of bits in an unsigned char
    // int start_bit         = start_block%8;
    // int start_byte        = start_block/8;
    // Break search into three sections, any of which can fail and cause the search
    // to restart.  On failure, each of the three routines must put the failed block
    // in the start_block location.  The failed block in start_block is used to
    // determine the new starting point.
    bool successful        = false;
    int start_block_attempt;
    while (!successful) {
      // renew the block count with each new attempt.
      int block_count       = blocks_needed;
      start_block_attempt   = start_block;
      // find initial leading indvidual bits
      successful = find_single_bits(&start_block_attempt,&block_count);
      if ((successful)&&(block_count>=8)) {
	// search byte by byte for free blocks
	successful = find_bytes(&start_block_attempt,&block_count);
      }
      if ((successful)&&(block_count>0)) {
	// find tailing individual bits
	successful = find_single_bits(&start_block_attempt,&block_count);
      }
      if (!successful) {
	// if  any attempt  failed, that  attempt should  have updated
	// start_block with the site of the last failed block attempt.
	// This block  is then used  to find the next  search starting
	// block.
	start_block = find_next_free_block(start_block_attempt,blocks_needed);
	// if there is no next free block, find_next_free_block() will
	// return  a   -1.   at  this  point,  this   chunk  has  been
	// successfully searched,  so exit up  to the higher  level to
	// get the next chunk.
	if (start_block==-1) {
	  successful=true;
	}
      }  // if (!successful)
    } // while (!successful)
    return start_block;
  }  // find_free_items
  
  //////////////////////////////////////////////////////////////////////////////////
  //////                          find_single_bits
  //////////////////////////////////////////////////////////////////////////////////
  /////
  /////    Assists in finding free blocks of memory for allocation        
  /////    This routine finds the leading discrete blocks of memory in the bit       
  /////    vector in a bit by bit search.  On success, returns true, on failure, 
  /////    returns false and puts the last failed block in start_block.  Block
  /////    count is used to keep track of the number of remaining blocks still 
  /////    required in the search.  
  /////    On failure, block_count is expected to be reset by the calling routine.
  /////    
  //////////////////////////////////////////////////////////////////////////////////
  
  bool allocator_bit_vector_t::find_single_bits(int *global_start_block,int *block_count) {
    // Find which bit and which byte this head_block corresponds to in the
    // memory array.  On failure, block_count is expected to be reset by
    // the calling routine.

    int start_block = (*global_start_block)%nelem;
    int start_byte  = start_block/8;
    int start_bit   = start_block%8;
    bool success    = false;
    
    // Only bother with this routine if either 
    // 1. need less than 8 blocks (one bit vector byte's worth of blocks) or
    // 2. start bit is not on an even byte boundry
    if ((start_bit>0)||(*block_count<8)) {
      // first get correct page chunk
      success           = true;
      // const 8 bits == 1 unsigned char
      std::bitset<8> val = bit_vec[start_byte];
      // int upper_bound = ((start_bit+(*block_count)-1) > 8)?8:(start_bit+(*block_count));
      for (int i = start_bit; ((i<8) && ((*block_count)>0));
	   i++,(*global_start_block)++,(*block_count)--) {
	// while still under a full byte boundry, and still more blocks are needed
	// test each new consecutive bit to see if avail.
	if (val.test(i)) {
	  // if a 1 is detected in the bit vector, the block is allocated and we
	  // fail here.
	  success=false;
	  break;	// exit the for loop
	  // block count in block_count will be reset by calling routine.
	}  //  if (val.test(i))
      }  //  
    } else {
      // need to search byte by byte
      // haven't failed at this point
      success=true;
    }
    
    return success;