allocator_bit_vector.cc

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

  };
  
  //////////////////////////////////////////////////////////////////////////////////
  //////                          find_bytes
  //////////////////////////////////////////////////////////////////////////////////
  /////
  /////    Assists in finding free blocks of memory for allocation        
  /////    This routine finds the middle blocks of memory in the bit vector in a       
  /////    byte by byte 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_bytes(int *global_start_block,int *block_count) {
    // Search byte by byte to ensure that the request bytes are not allocated
    // The global_start_block should be the first block on a byte or wrong
    // routine was called.
//      const int nelem = bit_vec_sz/esize;
    int start_block = *global_start_block%nelem;
    int start_bit   = start_block%8;
    int start_byte  = start_block/8;
    bool success = true;
    
    if (start_bit!=0) {
      std::cerr << __FILE__ << ':' << __LINE__ << ':' << " find_bytes(): ";
      std::cerr << "routine started on non-byte boundry.\n";
      exit(1);
    }
    int chunk_num=0;
//      Chunk* this_chunk = find_chunk(*global_start_block,&chunk_num);
    std::bitset<8> val;
    
    int upper_bound = start_byte+((*block_count)/8);
    if (upper_bound>bit_vec_sz) {
      return false;
    }
    
    for (int i=start_byte; ((i<upper_bound)&&((*block_count)>=0));
	 i++,(*block_count)-=8,(*global_start_block)+=8) {
      val = bit_vec[i];
      if (val.any()) {
	// found an allocated block - failure
	// working backwards through the byte, find the block which caused the failure
	int j;
	for (j=7; j>=0; j--)
	  if (val.test(j))
	    break;
	// i == bytes worth of blocks
	// j == each bit is one block
	// put the failed block in the global_start_block
	*global_start_block = chunk_num*nelem + i*8 + j;
	success=false;
	break;			// exit the for loop
      }
    }
    
    return success;
  };
  
  
  //////////////////////////////////////////////////////////////////////////////////
  //////                        find_prev_free_block()
  //////////////////////////////////////////////////////////////////////////////////
  /////
  /////    Find the previous free block to the block cited in the parameter start_block.
  /////    This routine is called during allocation of memory so that the pointer stored
  /////    in the previous free memory block will be redirected to point to the free 
  /////    spacce after the newly allocated memory block.
  /////    
  /////    
  //////////////////////////////////////////////////////////////////////////////////
  
  int allocator_bit_vector_t::find_prev_free_block(int start_block) {
    // Find the previous free block to the block cited in the parameter start_block.
    // Jump to the start_block and from there work backwards to find the first free
    // block in the bit_vec.  If a -1 is returned, the head pointer is the previous
    // free block
    
    if (start_block==0)
      return -1;
    else
      start_block--;
    // first find the correct chunk address for this block
//      int chunk_num=0;
//      Chunk* this_chunk = find_chunk(start_block,&chunk_num);
    
    // correct chunk is hopefully now in this chunk
    // search for previous block starting from start_block-1
    // Search in 2 parts
    //     1. individual bits before start_block bit
    //     2. byte by byte before start_block
    //     3. individual bits within found byte (if necessary)
    
    // Start with previous bits within this byte
    // Find which bit and which byte this head_block corresponds to in the memory array
    // within the chunk
//      const int nelem = bit_vec_sz/esize;
    int local_start_block = start_block%nelem;
    int start_bit   = local_start_block%8;
    int start_byte  = local_start_block/8;
    // int start_chunk = local_start_block/(bit_vec_sz);
    int result_block= -1;
    bool finished = false;
    std::bitset<8> val;
    
    if (start_bit!=8-1) {
      // if we are not directly on a byte border (not on the last bit of a byte)
      val = bit_vec[start_byte];
      for (int i=start_bit; ((i>-1)&&(!finished)); i--) {
	if (!val.test(i)) {
	  // found the empty, unused block
	  result_block = start_byte*8 + i;
	  finished=true;
	  break;
	}
      }
      start_byte--;
    } // if (start_bit!=sizeof(unsigned char)*8-1)
    
    // Search backwards through the remaining bytes to the beginning of the chunk
    if (!finished) {
      // search byte by byte backwards
      if (start_byte<0) {
	// No place left to go backwards in this block, check for a previous block
	result_block = -1; //set the head to point forwards
	finished=true;
      }  else {
	// start_byte is not the 0th byte of the chunk, so there is space to search
	// backwards through.
	for (int i=start_byte; ((i>=0)&&(!finished)); i--,start_byte-=8) {
	  val = bit_vec[i];
	  val.flip(); // invert bits
	  if (val.any()) {
	    // found free block in this byte, need to identify which one
	    for (int j=7; ((j>0)&&(!finished)); j--) {
	      if (val.test(j)) {
		// found the specific bit set
		result_block = i*8 + j;// which block
		finished = true;
	      } // if (val.test(j))
	    }  // for (int j=7; ((j>0)&&(!finished)); j--) 
	  }  // if (val.any())
	}  // for (int i=start_byte; ((i>=0)&&(!finished)); i--)
      }  // if (start_byte==0)
    }
    if (!finished) {
      result_block = -1; //set the head to point forwards
      finished=true;
    }  // if (!finished)
    return result_block;
  }; // find_prev_free_block(int start_block)
  
  
  //////////////////////////////////////////////////////////////////////////////////
  //////                        find_next_free_block()
  //////////////////////////////////////////////////////////////////////////////////
  /////
  /////    Find the next free block after the start_block.  This routine is used 
  /////    during a find failure.  It lets the find continue with a new starting 
  /////    point.  The blocks_needed parameter allows the routine to look ahead to 
  /////    see if the routine is now too close to the end of a given page to  
  /////    possibly find an allocatable block.
  /////    
  //////////////////////////////////////////////////////////////////////////////////
  
  int allocator_bit_vector_t::find_next_free_block(int global_start_block,int blocks_needed) {
    // Search the this_chunk page bitvector for a new starting block to find
    // blocks_needed.  Search and find the next free block starting at 
    // start_block.  If no free block is found, grow a new chunk and return a
    // pointer to that new chunk.
    
    int free_block;
    bool finished=false;
    int start_block = global_start_block;
    // first see if there is any possible space in this chunk
    // if not, add new chunk.
    int chunk_num=0;
    // bit_vec_sz is in bytes, 8*bit_vec_sz is the number of elements
    if ((((blocks_needed+start_block)/8.0)+1) > bit_vec_sz) {
      // if not check for next chunk
      free_block = -1;
      finished=true;
    }  // if ((blocks_needed+start_block+1) > bit_vec_sz)
    if (!finished) {
      // now find the first avail block and stop there
      
      int start_bit = start_block%8;
      int start_byte= start_block/8;
      // first find the correct chunk address for this block
      std::bitset<8> val = bit_vec[start_byte];
      free_block=-1;
      // 1. search bits into next integral char
      // 2. search for char with open bit
      // 3. identify and return which open bit within the char
      
      // Search bit by bit to the first integral char
      finished=false;
      if ((start_bit != 0)||(blocks_needed<8)) {
	// if not starting at the beginning of a full char
	// See if you need to search to the end of this char, or just within this char
	// int upper_bound = ((start_bit+blocks_needed) > 8)?8:(start_bit+blocks_needed);
	for (int i = start_bit; ((i<8)&&(blocks_needed>0)); i++) {
	  if (!val.test(i)) {
	    // found the first free location at block i.
	    // Now need to see if blocks from i to
	    // ((i + blocks_needed)>8)?8:(i + blocks_needed)
	    // or end of this char are available and free
	    // Create a bit mask to test block availability
	    std::bitset<8> mask;
	    const int upper_bound = ((i+blocks_needed) > 8)?8:(i+blocks_needed);
	    for (int j = i; j < upper_bound; j++)
	      mask.set(j);
	    // test needed bit set
	    mask &= val;
	    // if zero, then sucess an the search continues if neccessary
	    if (mask.none()) {
	      blocks_needed-=(upper_bound-i);
	      if (blocks_needed == 0) {
		finished=true;
		// set free_block to the chunk wide value
		free_block=i + start_byte*8;
		break;
	      }
	    }
	    // otherwise; failed on this attempt, i gets incremented
	    // loop back and try again.
	  }  // if (!val.test(i))
	}
	start_byte+=1;
      }  // if (start_bit != 0)
      
      // Search byte by byte to the first free block
      while (!finished) {
	// Search until a free block is found.  If no free block is encountered
	// add a new chunk and allocate from it.
	
	// if not finished, continue the search char by char
	for (int i=start_byte; i<bit_vec_sz; i++) {
	  val = bit_vec[i];
	  // 1. flip all bit values.
	  // 2. then search the result for any ones (previously where 0's)
	  val.flip();		// all 1's to 0's and visa versa
	  if (val.any()) {
	    finished=true;
	    // find the explicit bit within this found byte
	    int j;
	    for (j = 0; j<8; j++) {
	      // bits have been flipped so find the 1 here
	      if (val.test(j)) {
		break;
	      }
	    }
	    // Set value of finished free_block
	    // i == finished byte #
	    // j == finished bit #
	    free_block = i*8 + j + chunk_num*bit_vec_sz;
	    finished=true;
	    break;
	  }  //  if (val.any())
	}  // for (int i=start_byte; i<size; i++)
	if (!finished) {
	  // reached the end of the current chunk and still no empty byte
	  // move to next chunk, or if no next chunk add a new one.
	  // if not check for next chunk
	  free_block = -1;
	  finished=true;
	}  // if (!finished)
      }  // if (!finished)
    }  // if (!finished)
    return free_block;
  };  // find_next_free_block()

  //////////////////////////////////////////////////////////////////////////////////
  //////                        assigned
  //////////////////////////////////////////////////////////////////////////////////
  /////      
  /////      get_item finds the state of the indicated item_num.  Determines if
  /////      the items is true or false.
  /////      
  //////////////////////////////////////////////////////////////////////////////////

  bool allocator_bit_vector_t::assigned(int item_num) {
    // returns false if unused/unmarked, true if used/marked
    // get item state
    bool return_val;
    if ((0<=item_num) && (item_num<nelem)) {
      int byte=item_num/8;
      int bit=item_num%8;
      std::bitset<8> val = bit_vec[byte];
      return_val=val.test(bit);
    } else {
      return_val=false;
    }
    return return_val;
  };  // get_item()

}  // namespace bit_vec_space