// file: pooled_allocator.cc// author: Marc Bumble// May 12, 2000// Memory allocator for shared memory access// 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 <pooled_allocator.h>namespace pooled_allocator {  char none[] = "my_x_key";  unsigned char shmaddr = 0x00000000;    ////////////////////////////////////////////////////////////////////  //////                    Class Chunk  ////////////////////////////////////////////////////////////////////  //////          //////        Unit of  pooled memory composed  of multiple elements.  //////        The  Pool class  defined below  retrieve a  portion of  //////        UNIX  shared  memory  using  the shared  class.   That  //////        retrived memory is formated using the class chunk into  //////        element sized portions.  //////          //////          //////          ////////////////////////////////////////////////////////////////////  // constructor  // constructor  // elem_size         - element   size    in    bytes.  // total_chunk_size  - The  chunk is  instantiated in  a  piece of  //                     memory which is total_chunk_size in bytes.  // Need to  do some calculatons  of memory sizes to  instantiate the  // chunk.  The goal is to  determine how many elements can be stored  // in the chunk, and then setup the space to hold the maximum number  // of elements:  //  //      total_chunk_size = header + bit_vec + elements (1)  //  // where total_chunk_size is defined  above, the header is the Chunk  // overhead or  sizeof(Chunk).  The bit_vec is the  data buffer used  // by the bit  vector.  The rest of the bit  vector overhead is part  // of the header or normal chunk overhead.  Finally, elements is the  // space occupied by the elements stored in the Chunk.  //  // Known quantities:  //  // total_chunk_size - this is a given parameter, the amount of space  //                    allocated to hold the chunk.  //  // header - sizeof(Chunk), the chunk class overhead.  //  // Use equation 1 above to solve for the number of elements:  //  //   total_chunk_size = header + (nelem/8 + 1) + (nelem*esize)  //  // Where:  //  //   nelem - number of elements  //   esize - size of elements  //  // Solve for nelem:  //  //   nelem = (8*(chunk - header - 1))/(1 + 8*esize)       (2)  //     Chunk::Chunk(const int& elem_size,	       const int& total_chunk_size, 	       const int project_id,	       const int segment_page_number)    // elem_size - element size in bytes.    // pg_size   - page size in bytes.    : element_size(elem_size),      // see derivation of num_of_elements above equation 2      num_of_elements((8*(total_chunk_size - sizeof(Chunk) - 1))/(1 + 8*element_size)),      memory_size(num_of_elements*element_size),      bit_vec_size((num_of_elements/8) + 1),      proj_id(project_id),      segment_page_num(segment_page_number),      num_of_segment_pages(total_chunk_size/page_size),      // bit vector monitors num_of_elements elements      // bit vector is stored after this class, which is      //    at the address (this + sizeof(Chunk))      bit_vec(num_of_elements,	      reinterpret_cast<unsigned char*>(this)+	      sizeof(Chunk)) {    // first_elem_num is initially unknown        first_elem_num=-1;    // set the start of the data segment    mem = reinterpret_cast<unsigned char*>(this) +      sizeof(Chunk) + bit_vec_size;    prev=0;    next=0;  };  // Chunk::Chunk()  constructor  // copy constructor  Chunk::Chunk(const Chunk& t)    : element_size(t.element_size),      num_of_elements(t.num_of_elements),      memory_size(t.memory_size),      bit_vec_size(t.bit_vec_size),      proj_id(t.proj_id),      segment_page_num(t.segment_page_num),      num_of_segment_pages(t.num_of_segment_pages),      bit_vec(t.bit_vec) {    first_elem_num=t.first_elem_num;    mem=reinterpret_cast<unsigned char*>(this)+sizeof(Chunk)+bit_vec_size;    for (int i=0; i<memory_size; i++) {      mem[i] = t.mem[i];    }    prev=t.prev;    next=t.next;  }; // copy constructor    // assignment operator  Chunk& Chunk::operator=(const Chunk& t) {    if (this != &t) {		// avoid self assignment: t=t            first_elem_num=t.first_elem_num;       mem=reinterpret_cast<unsigned char*>(this) +	sizeof(Chunk) +	bit_vec_size;      for (int i=0; i<memory_size; i++) {	mem[i] = t.mem[i];      }      bit_vec=t.bit_vec;      prev=t.prev;      next=t.next;    }  // if (this != &t)    return *this;  }; // assignment operator  bool Chunk::operator==(const Chunk& t) {    // Define logical equality for a chunk    bool return_val = false;    if ((element_size==t.element_size) &&	(num_of_elements==t.num_of_elements) &&	(memory_size==t.memory_size) && 	(bit_vec_size==t.bit_vec_size) &&	(!strcmp(pathname,t.pathname)) && 	(proj_id==t.proj_id) &&	(segment_page_num==t.segment_page_num) &&	(num_of_segment_pages==t.num_of_segment_pages) &&	(first_elem_num==t.first_elem_num) &&	(bit_vec==t.bit_vec))      return_val=true;    else      return_val=false;    return return_val;  };  ////////////////////////////////////////////////////////////////////  //////                 Chunk::find()  ////////////////////////////////////////////////////////////////////  //////          //////        num_of_elements - memory for num_of_elements  //////          //////        find free memory  space for num_of_elements.    //////          //////        Returns  the   global  start_element  number   of  the  //////        requested space.  //////          ////////////////////////////////////////////////////////////////////  int Chunk::find(int num_of_elements) {    // find num_of_elements contiguous free blocks Query this chunk to    // see  if num_of_elements  memory  is avail.   If  so return  its    // start_block number, otherwise return -1;    // first find starting point.  This function may return a -1 which    // will be sent to the higher level indicating that the next chunk    // should  be searched  (there is  no more  suitable space  in the    // current chunk).    int start_elem = bit_vec.find_free_items(num_of_elements);    // Convert the start_block  addr which is the block  addr local to    // this block, into a global  block number by adding in the global    // address of the first_elem_num of this chunk    if (start_elem!=-1)      start_elem += first_elem_num;    return start_elem;  };  // Chunk::find()