www.pudn.com > allocator.rar > pooled_allocator.h


// file: pooled_allocator.h
// 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 
#include 
#include 

#include 
#include 

#ifndef POOLED_ALLOCATOR_H
#define POOLED_ALLOCATOR_H
  
namespace pooled_allocator {

  // page_size  and  num_of_pages   are  constants  here.   The  mem
  // variable is  static, so its parameters must  be declared before
  // the class objects are instantiated.
  enum {
    page_size=8192,	      // Each segment is divided into pages of
                              // this size
    num_of_pages=1000,        // There are num_of_pages per segment
    initial_num_of_elems=16   // Num of elems allocated in 1st chunk
  };

  ////////////////////////////////////////////////////////////////////
  //////                           Class Chunk
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Unit of  pooled memory composed  of multiple elements.
  //////        The Chunk objects are  allocated in Process memory.  A
  //////        process  requests  pages  of  memory from  the  shared
  //////        memory  segment  header.   There  is just  one  shared
  //////        memory segment header  per shared memory segment.  The
  //////        header is  located starting at  the first byte  of the
  //////        shared memory segment.  Chunks  are allocated on a per
  //////        process basis.  Once a  pool of memory is requested by
  //////        the process, that process  is assigned the memory as a
  //////        chunk.  Chunks are composed  of elements which are all
  //////        of the same size.
  //////        
  //////        A chunk manages  its memory on a per  chunk basis.  If
  //////        one  chunks runs  out of  memory, than  the  Pool must
  //////        request a  new chunk, and request  the required memory
  //////        from the  new chunk.  Each chunk only  knows about its
  //////        own elements.   They do  not know about  other chunks,
  //////        except for links  to create lists of chunks  so that a
  //////        set of chunks can be traversed.
  //////        
  //////        
  ////////////////////////////////////////////////////////////////////
  
  class Chunk  {
    const int element_size;	// size of objects held in container
    const int num_of_elements;	// num_of_elements in chunk
    // const int page_size;	// page size of shared seg memory
    const int memory_size;	// total element storage size in bytes
    const int bit_vec_size;	// bit vector size

    ///////////////////////////////////////////////////////////////////////////
    //////        Chunk identification
    ///////////////////////////////////////////////////////////////////////////
    const int proj_id;	        // specific segment within series
    const int segment_page_num;	// segment page number, used to compute offset
                                // from the start of the segment to the chunk.
    const int num_of_segment_pages;	// This chunk is composed of this many
				// shared memory  segment pages.  When
				// the  next chunk is  allocated, this
				// value is used to determine the size
				// of the next requested chunk.
    char pathname[mem_space::name_length];  // identifies which segment series
    int first_elem_num;		// first element number of this chunk
    ///////////////////////////////////////////////////////////////////////////

    // page free/allocated list
    allocator_bit_vector::allocator_bit_vector_t bit_vec;
    // data storage segment
    unsigned char* mem;
    // chunk to the beginning of the specific page_num
    const int get_element_offset(int page_num);
    // convert element number to pointer address
    unsigned char* element_num_to_pointer(int start_block);
    // Linked List implementation
    Chunk* prev;  // points to prev chunk
    Chunk* next;  // points to next chunk
  public:
    // 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.
    // proj_id           - The shared memory segement id or page
    // segment_page_num  - The Chunk is on allocated starting at this
    //                     page number within the shared memory segment
    //                     identified by proj_id.
    Chunk(const int& elem_size,
	  const int& total_chunk_size,
	  const int proj_id,
	  const int segment_page_num);	// The  chunk  is instantiated
					// in a  piece of memory which
					// is    total_chunk_size   in
					// bytes.
    // destructor
    virtual ~Chunk() {};
    // copy constructor
    Chunk(const Chunk& t);
    // assignment operator
    Chunk& operator=(const Chunk& t);
    bool operator==(const Chunk& t);
    // The  segment page  number is  the data  page number  within the
    // segment  specified by  the pathname  and proj_id.   The segment
    // page number  can be used  to compute the chunk_offset  which is
    // the distance from the beginning of the shared memory segment to
    // the beginning of this chunk  in bytes.  The chunk begins at the
    // page boundary.
    const int get_segment_page_num() {return segment_page_num;}
    const int get_num_of_segment_pages() {return num_of_segment_pages;}
    // get_page_offset returns the byte offset from the beginning of the
    // Each chunk consists of a sequence of elements first_elem_num is
    // the first global element number within this chunk.
    void set_first_elem_num(int val) {first_elem_num=val;}
    const int get_first_elem_num() {return first_elem_num;}
    const int get_element_size() {return element_size;}
    // bit_vec size is only for  the bit vector data, does not include
    // header which is part of the Chunk class overhead.
//     const int get_bit_vec_size() {return bit_vec_size;}
    // num_of_elements is number of elements in this chunk
    const int get_num_of_elements() {return num_of_elements;}
    // pathname is the alloc_key used to retrieve the segment in which
    // this chunk is embedded.   Pathname specifies a series of shared
    // memory segments.
    void set_pathname(char* path_name) {strcpy(pathname,path_name);}
    void get_pathname(char* path_name) {strcpy(path_name,pathname);}
    // The proj_id specifies which specific shared memory segment from
    // within this series of shared memory segments.
    const int get_proj_id() {return proj_id;}
    // find num_of_elements contiguous free blocks
    // returns local starting block number or -1
    int find(int num_of_elements);
    // mark num_of_elements starting at start_element
    // as assigned.  This function is used to link
    // newly freed memory with a previous free block.
    void mark(int start_element,int num_of_elements);
    // clear num_of_elements starting at start_element
    // as available.
    void clear(int start_element,int num_of_elements);
    // Compute the element number associated with the pointer
    int pointer_to_element_num(const unsigned char* p);
    // allocate num_of_elements starting with
    // element start_element
    mem_space::memory_index_t
    allocate(int start_element,
	     int num_of_elements);
    // release chunk elements
    void free(int global_first_element, int num_of_elements);
    // Functions for walking through the chunk list
    Chunk* get_next(void) {return next;}
    Chunk* get_prev(void) {return prev;}
    void set_next(Chunk* val) {next=val;}
    void set_prev(Chunk* val) {prev=val;}
  };  // class Chunk


  
  
  
  /////////////////////////////////////////////////////////////////////////////
  //////                           Class Pool
  /////////////////////////////////////////////////////////////////////////////
  //////        
  //////        Class Pool maintains segments of memory which are stored as a
  //////        as a list of chunks.
  //////        
  /////////////////////////////////////////////////////////////////////////////
  
  template 
  class Pool {
  private:
    const int element_size;
    // source of memory for the Pool
    // static mem_space::shared mem;
    mem_space::shared mem;
    
    // chunks list is static so that all objects in the
    // process share the same chunks
    static Chunk* chunks; // list of allocated chunks
    // Chunk* chunks; // list of allocated chunks
    void grow();
    int compute_chunk_pages();	// how  big should the  next allocated
				// chunk be?
    // locate shared memory to allocate the next chunk.
    std::pair
    find_shared_memory(int requested_pages);
    // local reference count
//     int ref_count;
  public:
    // constructor
    //    Pool(unsigned int sz,
//     Pool(const int& esize);
    Pool();
    // destructor
    virtual ~Pool();
    // copy constructor
    Pool(const Pool& t);
    // assignment operator
    Pool& operator=(const Pool& t);
    // equality operator
    bool operator==(const Pool& t) const;
    Chunk* get_last_chunk();	// retrieve the last chunk in list
    // find chunk associated with global_element_num
    Chunk* find_chunk(int global_element_num);
    // find_chunk finds the chunk and element number for pointer *p
    std::pair find_chunk(const unsigned char* p);
    std::pair find(int num_of_elements);
    void mark(int start_element,int num_of_elements);
    void clear(int start_element,int num_of_elements);
    void free_chunk(Chunk* victim); // recycle chunk
    // retrieve a specified shared memory page
    mem_space::shared_memory_header_t*
//     find_shared_segment() {
    find_shared_segment(int proj_id) {
      mem_space::memory_index_t smh_idx =
	mem.allocate(proj_id);
      return
	static_cast(smh_idx.get_memory_ptr());
    };
    mem_space::memory_index_t
    alloc(const int num_of_elements);
    void free(unsigned char* p, int num_of_elements);
    // retrieve a pointer to the object
//     unsigned char* retrieve_object_ptr(mem_space::memory_index_t obj_idx);
    // get the allocator main index map
    mem_space::map_index_t get_map_index(void);
    // set the allocator main index map
    void set_map_index(mem_space::map_index_t obj_idx);
    void shutdown(void) {
      // Close and release shared memory and semaphores
      mem_space::shared_memory_header_t* smh =
	find_shared_segment(1);
      const int shared_memory_addr = smh->get_shared_memory_addr();
      const int shared_memory_size = smh->get_shared_memory_size();
//       smh->shutdown();
      smh->~shared_memory_header_t();
      mem.free(shared_memory_addr,shared_memory_size);
    } // shutdown(void)
    void lock(int segment_num, int segment_page_num) {
      // lock access to the shared memory container
      mem_space::shared_memory_header_t* smh =
	find_shared_segment(segment_num);
      smh->lock(segment_page_num);
    }
    void unlock(int segment_num, int segment_page_num) {
      // unlock access to the shared memory container
      mem_space::shared_memory_header_t* smh =
	find_shared_segment(segment_num);
      smh->unlock(segment_page_num);
    }
    Chunk* get_chunks_list(void) {
      return chunks;
    }
    void set_chunks_list(Chunk* val) {
      // first eliminate any existing chunks on the list
      if ((chunks) && (chunks != val)) {
	int chunkcount = 1;
	Chunk* thischunk=chunks;
	Chunk* prevchunk=0;
	// get to the end of the list
	while (thischunk->get_next()) {
	  chunkcount++;
	  prevchunk = thischunk;
	  thischunk = thischunk->get_next();
	}
	if (chunkcount > 1) {
	  // Flag a warning.   There should only be one  chunk at this
	  // point.  This  function is  written to reassign  the first
	  // chunk on  the list when it  is empty, ie  when no objects
	  // are actually stored there.  If  more than one chunk is on
	  // the list,  there is a  high probability that  objects are
	  // already stored in the list.
	  std::cerr << __FILE__ << ':' << __LINE__  << "Attempting to reset a loaded Chunk list."
		    << std::endl;
	}  // if (chunkcount > 1)
	while (thischunk) {
	  // run through the chunk list and release the current existing chunks
	  free_chunk(thischunk);
	  chunkcount--;
	  thischunk = prevchunk;
	  if (prevchunk)
	    prevchunk = prevchunk->get_prev();
	}  // while ((thischunk != chunks) && (thischunk != 0))
	chunks = val;
      }
      // Then reset the chunk list to point to the list from the other
      // process
      return;
    }
    void unlink(void) {
      // use  the map  in the  shared memory  class to  remove all
      // related shared memory segments
      mem.unlink();		// call shared class to unlink shared memory
      return;
    }
  };  // class Pool

//   // static elements of class Pool
//   template 
//   mem_space::shared Pool::mem(pooled_allocator::num_of_pages,
// 					 pooled_allocator::page_size);
  
  // static elements of class Pool
  template 
  Chunk* Pool::chunks = 0; // list of allocated chunks
  
  
  ////////////////////////////////////////////////////////////////////
  //////                    Class Pool
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Pool Function Definitions start here.
  //////        
  ////////////////////////////////////////////////////////////////////
  

  // constructor
 template
//   Pool::Pool(const int& size) :
  Pool::Pool() :
    element_size(sizeof(T)),
    mem(pooled_allocator::num_of_pages,
	pooled_allocator::page_size) {
#ifdef DEBUG
   std::cerr << __FILE__ << ':' << __LINE__ << ':' <<
     " Pool() : constructor. " << std::endl;
#endif
   // instantiate the first chunk on the chunk list
   if (!chunks) {
     grow();
   }
   // chunks=0;
//    ref_count = 0;
  }; // constructor

  // destructor
 template 
  Pool::~Pool() {
   // mem.~shared();
//    if (chunks) {
//      int proj_id = chunks->get_proj_id();
//      mem_space::memory_index_t mem_idx = mem.allocate(proj_id);
//      mem_space::shared_memory_header_t* smh =
//        static_cast(mem_idx.get_memory_ptr());
//      smh->lock(chunks->get_segment_page_num());
//      int count = smh->get_ref_count();
//      smh->set_ref_count(count-ref_count);
//      smh->unlock(chunks->get_segment_page_num());
// #ifdef DEBUG
//      std::cerr << __FILE__ << ':' << __LINE__
// 	       << ": Pool<>::~Pool() count - ref_count: " <<
//        std::endl;
//      std::cerr << count <<  " - " << ref_count << " = " <<
//        count-ref_count << std::endl;
// #endif
//    }
 }; // destructor
  
  // copy constructor
 template 
  Pool::Pool(const Pool& t) :
    element_size(t.element_size),
    mem(pooled_allocator::num_of_pages,
	pooled_allocator::page_size) {
//    ref_count = 0;
   // chunks=t.chunks;
  }; // copy constructor
  
  // assignment operator
 template 
 Pool::Pool& Pool::operator=(const Pool& t) {
//     if (this != &t) {		// avoid self assignment: t=t
//       chunks=t.chunks;
//     }
    return *this;
  }; // assignment operator

  // equality operator
 template 
 bool Pool::operator==(const Pool& t) const {
    bool return_val=true;
    Chunk* this_chunk = chunks;
    Chunk* other_chunk = t.chunks;
    if (element_size!=t.element_size)
      return_val=false;
    // test the chunk lists for equality
    while ((return_val) && (this_chunk) && (other_chunk)) {
      if (!(*this_chunk==*other_chunk))
	return_val=false;
      else {
	this_chunk = this_chunk->get_next();
	other_chunk = other_chunk->get_next();
      }
    }
    return return_val;
  };  // Pool::operator==()

  
  ////////////////////////////////////////////////////////////////////
  //////                   Pool::get_last_chunk()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Retrieve the last chunk on the list, return 0 if none.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  Chunk* Pool::get_last_chunk() {
    // Retrieve the last chunk on the list, return 0 if none.
    Chunk* last_chunk = chunks;
    // if chunks have already been allocated
    // get last chunk and square previous request
    while ((last_chunk) && (last_chunk->get_next())) {
      last_chunk = last_chunk->get_next();
    }
    return last_chunk;
  }; // Chunk* Pool::get_last_chunk()

  ////////////////////////////////////////////////////////////////////
  //////           Chunk* Pool::find_chunk()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        global_element_num   -  chunk  sought   contains  this
  //////                                element number.
  //////        
  //////        Returns the chunk pointer if found, 0 otherwise.
  //////        
  ////////////////////////////////////////////////////////////////////

  // find chunk associated with global_element_num
 template 
  Chunk* Pool::find_chunk(int global_element_num) {
    bool found = false;
    Chunk* current_chunk = chunks;
    while((!found) && (current_chunk != 0)) {
      const int& lower_bound = current_chunk->get_first_elem_num();
      const int& upper_bound = lower_bound +
	current_chunk->get_num_of_elements();
      if ((lower_bound <= global_element_num) &&
	  (global_element_num < upper_bound))
	found = true;
      else
	current_chunk = current_chunk->get_next();
    }
    return current_chunk;
  };  // Chunk* Pool::find_chunk(int global_element_num)


  ////////////////////////////////////////////////////////////////////
  //////           Pool::find_chunk(const unsigned char* p)
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        p  -  pointer to  allocated  memory.  
  //////        
  //////        Find the chunk and element number corresponding to the
  //////        pointer,  p.  Returns  a pair  with a  pointer  to the
  //////        corresponding chunk and the element number within that
  //////        chunk.  If not found, return pair<>(0,-1).
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  std::pair Pool::find_chunk(const unsigned char* p) {
    bool found = false;
    Chunk* current_chunk = chunks;
    int element_num;
    while((!found) && (current_chunk != 0)) {
      element_num =
	current_chunk->pointer_to_element_num(p);
      if (element_num != -1)
	found = true;
      else
	current_chunk = current_chunk->get_next();
    }  // while((!found) && (current_chunk != 0))
    return std::pair(current_chunk,element_num);
  };  // std::pair find_chunk(const unsigned char* p)

  ////////////////////////////////////////////////////////////////////
  //////           int Pool::find()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        num_of_elements  -  finds  free, available  memory  to
  //////        store this number of elements.
  //////        
  //////        Returns  the  starting  global  element  number  which
  //////        indicates  the beginning of  the available  space.  If
  //////        the memory  is unavailable,  returns (0,-1).
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  std::pair Pool::find(int num_of_elements) {
    // Search through the list of chunks to find the requested num_of_elements.

    Chunk* current_chunk = chunks;
    int start_element=-1;
    while ((current_chunk != 0)&&(start_element == -1)) {
      // The chunk find routine returns the global block number if the
      // element is in this chunk, -1 otherwise.
      start_element = current_chunk->find(num_of_elements);
      if (start_element == -1) {
	// memory was not available in the current chunk, try next
	if (!current_chunk->get_next()) {
	  // end of the line, try to grow more
	  grow();
	}
	if (current_chunk->get_next()) {
	  current_chunk = current_chunk->get_next();
	} else {
	  // Memory appears to be exhausted for this shared
	  // segment, throw.
	  std::clog << "Error: " << __FILE__ << ':' << __LINE__ ;
	  std::clog << ": project id out of range (1 <= proj_id < 128): "
		    << std::endl;
	  throw (Alloc_Exception::mem_exhausted_exception(0));
	}
      }
    }
    return std::pair(current_chunk,start_element);
  };  // int Pool::find(int num_of_elements)

  ////////////////////////////////////////////////////////////////////
  //////           void Pool::mark()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        start_element   - global first  element  number of set
  //////                          of elements to be marked.
  //////        num_of_elements - how many elements to be marked.
  //////        
  //////        Mark elements  as in use.   The elements may  NOT span
  //////        more than one chunk.  This is due to the bytes used by
  //////        the  header information  which  prevents a  contiguous
  //////        allocation of memory  across multiple chunks.  Chunks,
  //////        however,  can be  composed  of multiple  pages from  a
  //////        segment,  and  the  allocated  memory can  span  those
  //////        subpages which do not have header information.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  void Pool::mark(int global_start_element,
					int num_of_elements) {
    // elements  can NOT  be allocated  across chunks,  so we  must be
    // working within one chunk.  Find  it and mark the elements.  The
    // chunk routines recieve global_start_element addresses.
   Chunk* current_chunk = find_chunk(global_start_element);
   if (current_chunk)
     current_chunk->mark(global_start_element,num_of_elements);
    return;
  };  // void mark(int start_element,int num_of_elements)

  ////////////////////////////////////////////////////////////////////
  //////           void Pool::clear()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        start_element   - global first  element  number of set
  //////                          of elements to be cleared.
  //////        num_of_elements - how many elements to be cleared.
  //////        
  //////        Clear elements for reuse.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  void Pool::clear(int global_start_element,
					 int num_of_elements) {
   // elements  can NOT  be allocated  across chunks,  so we  must be
   // working within one chunk.  Find it and clear the elements.  The
   // chunk routines recieve global_start_element addresses.
   Chunk* current_chunk = find_chunk(global_start_element);
   if (current_chunk)
     current_chunk->clear(global_start_element,num_of_elements);     
   return;
  };  // void clear(int start_element,int num_of_elements)

  ////////////////////////////////////////////////////////////////////
  //////              Pool::compute_chunk_pages()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Determine the size of a new chunk to be created.  Find
  //////        the last  chunk which was created.  That  chunk, if it
  //////        exists, contains information which will help to create
  //////        the next  chunk.  For example, if the  last chunk used
  //////        by  this process contained  num_pages, the  next chunk
  //////        should  contain  2*num_pages.   If  no  chunk  exists,
  //////        enough  space is  allocated  for initial_num_of_elems.
  //////        The function automatically computes the required pages
  //////        for element storage plus the regular chunk overhead.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  int Pool::compute_chunk_pages() {

    int request_pages;
    Chunk* last_chunk = get_last_chunk();

    // 
    // The total size of the last  chunk is used to determine what the
    // current requested chunk size should be.
    // 
    // Determine the size of the  last chunk and double the size for
    // the new chunk
    // tot_chunk_size = header + bit_vec_sz + elements
    // 
    const int& header   = sizeof(Chunk);
    int elements;
    int num_of_elements;
    // 
    if (last_chunk) {
      // How much space was used  for elements in the last chunk?  Use
      // this number to compute the number of pages allocated for that
      // chunk.
      num_of_elements = 2*last_chunk->get_num_of_elements();
      elements =
	num_of_elements*last_chunk->get_element_size();
      // get the next segment in the series
    } else {
      // if no chunks have been allocated
      // request enough space for 4 objects
      num_of_elements = initial_num_of_elems;
      elements = initial_num_of_elems*element_size;
      // start with the first segment in the series.
      // given the size of memory
    }
    const int& bit_vec_sz = num_of_elements/8 + 1;
    // Now use elements to  finish determining the requested number of
    // requested pages
    const int& temp_size = header + bit_vec_sz + elements;
    request_pages = temp_size/page_size;
    if (temp_size%page_size) {
      // if it does not divide exactly, round up
      request_pages++;
    }
    return request_pages;
  };  // Pool::compute_chunk_pages()

  ////////////////////////////////////////////////////////////////////
  //////           find_shared_memory(int requested_pages)
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        requested_pages - find  this number of available pages
  //////                          from the  shared memory  segments to 
  //////                          use for creating a new chunk.
  //////        
  //////        Returns a  pair containing  the starting page  for the
  //////        allocated memory  and a  pointer to the  shared memory
  //////        header which contains the allocated pages of memory.
  //////        
  //////        Attach to  memory pages  in the shared  memory segment
  //////        series which  are specified by  the alloc_key.  Search
  //////        for  the requested  number  of pages.   Memory can  be
  //////        continually allocated and freed by other processes, so
  //////        start  with the  first  segment and  work through  the
  //////        list.   Later,  other  arrangements of  shared  memory
  //////        segment searches can be developed.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  std::pair
  Pool::find_shared_memory(int requested_pages) {
    // Start to  attach to memory  pages in the shared  memory segment
    // series which  are specified  by the alloc_key.   Because memory
    // can  be continually  allocated  and freed  by other  processes,
    // always start with the first  segment and work through the list.
    // Later, other arrangements of shared memory segment searches can
    // be developed.
    
    int proj_id = 1;		// index  through  the  shared  memory
				// segments.
    mem_space::memory_index_t mem_idx =	// allocate will attach to the
      //      mem.allocate();  // shared memory segment if it
      mem.allocate(proj_id);  // shared memory segment if it
					// exists, or  create it if it
					// does not.
      
    // Access the shared memory header
    mem_space::shared_memory_header_t* smh =
      static_cast(mem_idx.get_memory_ptr());
    // smh->print();
    // The pool can request variable number of pages from the segment.
    // But it can just get full pages.  The chunk can then portion the
    // pages out in element portions.
    // locate needed memory in shared segment
    bool memory_found = false;
    int start_page;		// The  start page  num  of the  found
				// memory.
    while (!memory_found) {
      // Does this shared memory segment have the needed memory?
      start_page = smh->find_free_pages(requested_pages);
      if (start_page == -1) {
	// memory not available in this segment, try next segment
 	proj_id = smh->get_proj_id() + 1; 
 	if ((proj_id > mem_space::shared::num_of_segments) ||
 	    (proj_id < 1)) {
 	  // Memory appears to be exhausted for this shared
 	  // segment, throw.
 	  std::clog << "Error: " << __FILE__ << ':' << __LINE__ ;
 	  std::clog << ": project id out of range (1 <= proj_id < 128): "
 		    << std::endl;
 	  throw (Alloc_Exception::mem_exhausted_exception(0));
 	}
	// Using the  new proj_id, get  the next shared  memory header
	// (smh)
	mem_space::memory_index_t mem_idx =
// 	  mem.allocate();
 	  mem.allocate(proj_id);
	// Access the shared memory header
	smh =
	  static_cast(mem_idx.get_memory_ptr());
      } else {
	memory_found = true;
      } // if (start_page == -1)
    }  // while (!memory_found)
    return std::pair(smh,start_page);
  }; // void* find_shared_memory(int requested_pages)
  

  ////////////////////////////////////////////////////////////////////
  //////                   Pool::retrieve_object_ptr()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        obj_idx  -  contains  address  information  about  the
  //////        object whose pointer is to be retrieved.
  //////        
  //////        Retrieve  a pointer  to  the object  specified by  the
  //////        parameter.  This  function is  intended to be  used by
  //////        processes retrieving  an object stored  by a different
  //////        process.
  //////        
  ////////////////////////////////////////////////////////////////////

//  template 
//   unsigned char* 
//   Pool::retrieve_object_ptr(mem_space::memory_index_t obj_idx) {

//     // First retrieve the correct shared memory segement w/header
//     mem_space::shared_memory_header_t* smh =
//       find_shared_segment();
// //       find_shared_segment(obj_idx.get_proj_id());
//     // Now used the shared memory  header to locate the pointer to the
//     // object

//     // The memory_index_t values are  set by chunks when they allocate
//     // memory in Chunk::allocate().  Extract these values and use them
//     // to  find the proper  shared memory  segment, the  specific page
//     // within  that segment  and  the element  offset  to compute  the
//     // object's address.

//     const int& segment_page_num = obj_idx.get_segment_page_num();
//     const int& element_offset = obj_idx.get_element_offset();
//     int page_offset = smh->get_page_offset(segment_page_num);
//     // Now add  the page offset to  the begnning of  the shared memory
//     // segment to get the start  of the correct segment page.  Add the
//     // element_offset  to get  from  the correct  page  to the  actual
//     // element addresss and done.
//     return reinterpret_cast(smh) + page_offset +
//       element_offset;
//   };  // Pool::retrieve_object_ptr()
  
  ////////////////////////////////////////////////////////////////////
  //////                   Pool::get_map_index()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Get the  allocator main index map.  This  map, if set,
  //////        contains  a mapping of  specifically set  objects with
  //////        index informaton to obtain the memory addresses.
  //////        
  //////        Always store  the object map index  information in the
  //////        segment with proj_id == 1.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  mem_space::map_index_t 
  Pool::get_map_index(void) {
    
    // Retrieve the shared memory segement w/header for proj_id = 1.
    mem_space::shared_memory_header_t* smh =
      find_shared_segment(1);
//       find_shared_segment();
    // return the index information
    return smh->get_map_index();
  };  // get_map_index(void) 
  
  ////////////////////////////////////////////////////////////////////
  //////                   Pool::set_map_index()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        obj_idx  - contains memory  index information  used to
  //////                   retrieve the index map itself.
  //////        
  //////        This  function initializes  the  allocator main  index
  //////        map.  The  map then contains  a mapping of  key values
  //////        versus the  index information used  to retrieve offset
  //////        pointers to the objects referenced by the key values.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  void Pool::set_map_index(mem_space::map_index_t
					  obj_idx) {
    // Retrieve the shared memory segement w/header for proj_id = 1.
    mem_space::shared_memory_header_t* smh =
      find_shared_segment(1);
//       find_shared_segment();
    // return the index information
    smh->set_map_index(obj_idx);
    return;
  };  // void set_map_index()


  ////////////////////////////////////////////////////////////////////
  //////                   Pool::free_chunk()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Function releases chunk or recycles the chunk.
  //////        
  //////        
  //////        
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
 void Pool::free_chunk(Chunk* victim) {
    int num_of_segment_pages = victim->get_num_of_segment_pages();
    int segment_page_num = victim->get_segment_page_num();
    const int& proj_id = victim->get_proj_id();
    mem_space::memory_index_t mem_idx =
      // 	  mem.allocate();
      mem.allocate(proj_id);
    // Access the shared memory header
    mem_space::shared_memory_header_t* smh =
      static_cast(mem_idx.get_memory_ptr());
    victim->~Chunk();		// Call destructor manually
    smh->clear_pages(segment_page_num,num_of_segment_pages);
 };  // Pool<>::free_chunk(Chunk* victim)


  
  ////////////////////////////////////////////////////////////////////
  //////                   Pool::grow()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////      Increase  the  current  available  memory in  the  Pool.
  //////      Allocate a new 'chunk' and  organize it as a linked list
  //////      of elements of size esize.   Pool is created to exist as
  //////      an  object allocated  within  a process,  but  not as  a
  //////      static object.  
  //////      
  //////      Memory  for the  needed chunks  comes from  two possible
  //////      sources:
  //////        
  //////             1. An   existing  shared   memory   segment  with
  //////                available memory.
  //////             2. A  new shared memory  segment must  be created
  //////                and used to retrieve the requested memory.  
  //////        
  //////      If a previously used  shared memory segment exists which
  //////      has  available  memory, the  grow  routine should  first
  //////      request memory  from that existing  segment.  Otherwise,
  //////      if there are no available shared memory segments or they
  //////      exist  but  are  exhausted,  then a  new  shared  memory
  //////      segment  should be  allocated and  the memory  should be
  //////      retrieved from that new segment.
  //////      
  //////      The  grow routine uses  a static  version of  the shared
  //////      class  to retrieve  memory from  the UNIX  shared memory
  //////      segment.
  //////      
  //////      Called to increase the amount of available memory in the
  //////      memory pool.  Each chunk  represents a set of pages from
  //////      a shared memory segment.
  //////      
  ////////////////////////////////////////////////////////////////////

 template 
  void Pool::grow() {
    //
    // alloc_key - determines which  series of shared memory segements
    //             are accessed to create new chunks.
    //
    // Pool::grow() does  not return it value.  However,  it creates a
    // new chunk which it places on the Pool chunks attribute list.
    //
    // Assume:
    //    Need to allocate  a new chunk.  All current  chunk memory is
    //    exhausted.
    //
    
    //////////////////////////////////////////////////////////////////
    //////            Compute Requested Chunk Pages
    //////////////////////////////////////////////////////////////////

    const int& requested_pages = compute_chunk_pages();

    //////////////////////////////////////////////////////////////////
    ///////        Find available memory in shared segment
    //////////////////////////////////////////////////////////////////

#ifdef DEBUG
    std::clog << __FILE__ << ':' << __LINE__  << ':' <<
      " Pool<>::grow() " << std::endl;
    std::clog.flush();
#endif
    std::pair
      smh_obj = find_shared_memory(requested_pages);
    // Returns  a pair  with a  pointer to  the shared  memory segment
    // which has the needed memory pages available,
    const int& start_page_num = smh_obj.second;
    // and  the starting  page  number  in the  segment  of the  first
    // requested page.
    mem_space::shared_memory_header_t *smh = smh_obj.first;
    smh->mark_pages(start_page_num,requested_pages);

    // compute the chunk_offset
    const int& chunk_offset = smh->get_page_offset(start_page_num);
    const int& total_chunk_size = requested_pages*page_size;
    void* buff = reinterpret_cast(smh) +
      chunk_offset;
    // get the proj_id
    const int& proj_id = smh->get_proj_id();
    Chunk* n = new(buff)Chunk(element_size,     // element size
			      total_chunk_size, // data_segment size
 			      proj_id,          // shared mem segment id
			      start_page_num);  // Chunk is on this 
                                                // page  within the 
                                                // shared   memory  
                                                // segment   identified
                                                //      by   proj_id.
                                                // proj_id  == 
                                                // segment page number
                                                // start_page_num !=
                                                // segment page number
    // get the pathname, really same as alloc_key
    char pathname[mem_space::name_length];
    smh->get_key(pathname);
    n->set_pathname(pathname);

    if (chunks) {
      // Some chunks have already been allocated
      Chunk* last_chunk=get_last_chunk();
      last_chunk->set_next(n);
      n->set_prev(last_chunk);
      // set the chunk's first global element number based on previous
      // chunk
      int global_first_element = last_chunk->get_first_elem_num() +
	last_chunk->get_num_of_elements();
      n->set_first_elem_num(global_first_element);
    } else {
      // This is the first chunk to be allocated
      n->set_next(0);
      n->set_prev(0);
      // set the chunk's first global element number to 0
      n->set_first_elem_num(0);
      chunks = n;
    }
  }; // Pool::grow()
  

  ////////////////////////////////////////////////////////////////////
  //////                       Pool::allocate()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        num_of_elements - memory for num_of_elements
  //////        alloc_key - key used to specify which series of shared
  //////                    memory   segments.  Segment   series   are 
  //////                    futher   singled  out   by  their   unique 
  //////                    proj_id's.
  //////        
  //////        allocate  adjusts  pointers in  the  memory chunk  and
  //////        returns a pointer to the start of the allocated memory
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  mem_space::memory_index_t
  Pool::alloc(const int num_of_elements) {
    // Let the upper level functions attempt to catch.
    if (chunks==0) {
      grow();
    }  // if (chunks==0)
    // lock the segments to prevent similar concurrent searches
    if (!chunks)
      std::cerr << __FILE__ << ':' << __LINE__  << ':' << " Chunks is still 0."
		<< std::endl;
    int proj_id = chunks->get_proj_id();
    mem_space::memory_index_t mem_idx = mem.allocate(proj_id);
    mem_space::shared_memory_header_t* smh =
      static_cast(mem_idx.get_memory_ptr());
    smh->lock(chunks->get_segment_page_num());
    std::pair obj_pair = find(num_of_elements);
    while (!obj_pair.first) {
      // The find was unsucessful.  Try to grow some more memory
      // unlock the segment page
      smh->unlock(chunks->get_segment_page_num());
      grow();
      // Search again
      // lock the segments to prevent similar concurrent searches
      // lock on the first page
      proj_id = chunks->get_proj_id();
      mem_idx = mem.allocate(proj_id);
      smh =
	static_cast(mem_idx.get_memory_ptr());
      smh->lock(chunks->get_segment_page_num());
      obj_pair = find(num_of_elements);
      if (!obj_pair.first) {
	// still a problem, give up and throw
	  std::clog << "Error: " << __FILE__ << ':' << __LINE__ ;
	  std::clog << ": Pool::alloc(): Not enough memory for " <<
	    num_of_elements << " elements." << std::endl;
	  throw (Alloc_Exception::alloc_exception(0));
      }  // if (!obj_pair.first)
    }  // while (!obj_pair.first)
    // We now have access to the requested memory
    // mark it as in service
    Chunk* this_chunk = obj_pair.first;
    const int& global_element_number = obj_pair.second;

//     this_chunk->mark(global_element_number,num_of_elements);
    const mem_space::memory_index_t& obj_idx =
      this_chunk->allocate(global_element_number,num_of_elements);

    int count = smh->get_ref_count();
    smh->set_ref_count(count + num_of_elements);
//     ref_count += num_of_elements;  // Used by the destructor
#ifdef DEBUG
    std::cerr << __FILE__ << ':' << __LINE__  <<':' << 
      " Pool<>::alloc() ref_count + num_of_elements: " <<
      std::endl;
    std::cerr << count <<  " + " << num_of_elements << " = " <<
      count + num_of_elements << std::endl;
     mem_space::memory_index_t* obj = new mem_space::memory_index_t(obj_idx);
     void* p = obj->get_memory_ptr();
     std::cerr << "Allocated memory at address: " <<
       (const void*) p << std::endl;
#endif
    
    // After marking, unlock the chunk
    smh->unlock(chunks->get_segment_page_num());
    return obj_idx;
  }; // Pool::alloc()

  ////////////////////////////////////////////////////////////////////
  //////                       Pool::free()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        p - points to the memory to be freed.
  //////        num_of_elements - how many elements starting at p
  //////        
  //////        Release memory for reuse.
  //////        
  ////////////////////////////////////////////////////////////////////

 template 
  void
  Pool::free(unsigned char* p, int num_of_elements) {
   // Free called on existing memory, make sure chunks ptr valid.
   if (chunks==0) {
     grow();
   }  // if (chunks==0)
   std::pair obj_pair = find_chunk(p);
   if (obj_pair.first) {  // if a valid chunk found
     Chunk* this_chunk = obj_pair.first;
     const int& global_element_num = obj_pair.second +
       this_chunk->get_first_elem_num();


     int proj_id = chunks->get_proj_id();
     mem_space::memory_index_t mem_idx = mem.allocate(proj_id);
     mem_space::shared_memory_header_t* smh =
       static_cast(mem_idx.get_memory_ptr());
     smh->lock(this_chunk->get_segment_page_num());


     int count = smh->get_ref_count();
     smh->set_ref_count(count - num_of_elements);
//     ref_count -= num_of_elements;  // Used by the destructor
#ifdef DEBUG
     std::cerr << __FILE__ << ':' << __LINE__
	       << ": Pool<>::free() ref_count - num_of_elements: " <<
       std::endl;
     std::cerr << count <<  " - " << num_of_elements << " = " <<
       count-num_of_elements << std::endl;
     std::cerr << "Freed memory at address: " << (void*) p << std::endl;
#endif
     this_chunk->free(global_element_num,num_of_elements);


     smh->unlock(this_chunk->get_segment_page_num());
   } else {
     std::cerr << __FILE__ << ':' << __LINE__
	       << ": Pool<>::free() : valid chunk not found." <<
       std::endl;
     std::cerr << __FILE__ << ':' << __LINE__
	       << " *p : " << std::hex << p 
	       << " : num_of_elements : " << std::dec << num_of_elements 
	       << std::endl;
     std::cerr << "Memory at address: " << (void*) p << std::endl;
     std::cerr << "Chunks value: " << (void*) chunks << std::endl;
   }
    return;
  };  // Pool::free()


  /////////////////////////////////////////////////////////////////////////////
  //////                           Class Pool_alloc
  /////////////////////////////////////////////////////////////////////////////
  //////        
  //////        This class provide the generic allocator interface to the 
  //////        outside world.
  //////        
  //////        
  /////////////////////////////////////////////////////////////////////////////
  
  // Define template type parameters as follows
  //     T - The type of object to be allocated.  (ie the allocator will hold ints)
  //     U - Defines the type of allocator, expected to be mem_space::allocator_t.  Currently,
  //         only sharedpooled is defined.  In the future, persistent, 
  
  
  template
  class Pool_alloc {
  protected:
    Pool mem;		// pool of elements of sizeof(T)
  public:
    typedef T value_type;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    
    typedef T* pointer;
    typedef const T* const_pointer;
    
    typedef T& reference;
    typedef const T& const_reference;
    
    pointer address(reference r) const { return &r; }
    const_pointer address(const_reference r) const {return &r;}
    
    // constructor
    Pool_alloc() :
      mem() {};
    
    // copy constructor
    template
    Pool_alloc(const Pool_alloc& t) { };
    // destructor
    virtual ~Pool_alloc() throw() {
    };
    // equality operator
    bool operator==(const Pool_alloc& t) const {
      bool flag = false;
      if (mem == t.mem)
	flag = true;
      return true;
      };
    // inequality operator
    bool operator!=(const Pool_alloc& t) const {
      return !(mem == t.mem);
    };
    
    // original allocate function for the allocator interface
    // space for n Ts
    virtual pointer allocate(size_type n, const_pointer hint=0);	
    virtual mem_space::memory_index_t
    allocate_with_index(size_type n);	// space for n Ts
    virtual Chunk* get_chunks_list() {
      return mem.get_chunks_list();
    };
    virtual void set_chunks_list(Chunk* val) {
      mem.set_chunks_list(val);
      return;
    };
    // deallocate n Ts, don't destroy
    virtual void deallocate(pointer p,size_type n); 
    
    // initialize *p by val
    void construct(pointer p, const_reference val) { new(p) T(val); } 
    void destroy(pointer p) { p->~T(); } // destroy *p but don't deallocate
    
    size_type max_size() const throw();
    
    template
    // in effect: typedef Pool_alloc other
    struct rebind { typedef Pool_alloc other; };
  };  // class Pool_alloc
  
  
//   // static variable declaration for Pool
//   template
//   Pool
//   Pool_alloc::mem(sizeof(T));
  
  
  ////////////////////////////////////////////////////////////////////
  //////
  //////  Memory allocation starts here
  //////
  ////////////////////////////////////////////////////////////////////
  
  template
  T* Pool_alloc::allocate(size_type n, const_pointer hint) {
#ifdef SHARED_MEMORY_MESG
    std::cerr << "allocate: " << n << " objects ********\n";
#endif
    mem_space::memory_index_t obj_idx =
      mem.alloc(n);
    return reinterpret_cast(obj_idx.get_memory_ptr());
  }
  
  ////////////////////////////////////////////////////////////////////
  //////
  //////  Memory allocation starts here
  //////
  //////  n - how many objects to allocate
  //////  
  //////  Returns a memory_index_t which  contains a pointer to memory
  //////  big  enough to  hold n  objects.  The  memory_index_t object
  //////  also contains index informaton which allows retrieval of the
  //////  allocated memory space.
  //////  
  //////  
  //////  
  ////////////////////////////////////////////////////////////////////

  
  template
  mem_space::memory_index_t
  Pool_alloc::allocate_with_index(size_type n) {
#ifdef SHARED_MEMORY_MESG
    std::cerr << "allocate: " << n << " objects ********\n";
#endif
    return mem.alloc(n);
  }
  
  
  ////////////////////////////////////////////////////////////////////
  //////
  //////  Memory de-allocation starts here
  //////
  ////////////////////////////////////////////////////////////////////

  template
  void Pool_alloc::deallocate(pointer p, size_type n) {
    
    if (n!=0) {
      mem.free(reinterpret_cast(p),n);
      return;
    }
    
  }

  /////////////////////////////////////////////////////////////////////////////
  //////                           Class Multi_Process_Pool_alloc
  /////////////////////////////////////////////////////////////////////////////
  //////        
  //////        This class provide the generic allocator interface to the 
  //////        outside world.
  //////        
  //////        
  /////////////////////////////////////////////////////////////////////////////
  
  // Define template type parameters as follows

  //     Container - The type of  container used to store the objects,
  //                 like a map, list, set, etc.
  //     Object  -  The type  of  object  to  be allocated.   (ie  the
  //                allocator will hold ints)
  //     alloc_key - the string key used to identify the
  //                shared memory segment.
  //     container_key - the string key used to identify the container.
  //     alloc_addr - addr requested to place shared memory segment
  //                  becomes in shmaddr in shmat() call


  extern char none[];
  extern unsigned char shmaddr;
  
  template
  class Multi_Process_Pool_alloc :
    public Pool_alloc {
  private:
    // map of a string index name vs. the block number in memory
    // can not save an actual pointer to the object, need to save
    // the block numbers which are really offsets into the block.
    // physical memory.   Address vary across processes, so one 
    // can not just save a physical memory addres.

    typedef Pool_alloc char_allocator_t;

    typedef std::basic_string,
			      char_allocator_t> alloc_string_t;


//     // first  = container's allocator chunk list
//     // second = contained objects' allocator chunk list
//     typedef std::pair container_object_pr_t;

//     typedef std::pair container_info_pair_t;

//     typedef std::pair map_pair_t;

    typedef std::pair map_pair_t;

//     typedef std::pair map_pair_t;

    typedef Pool_alloc map_pair_allocator_t;

    struct ltstr {
      bool operator()(const alloc_string_t s1, const alloc_string_t s2) const {
	return (s1 < s2);
      }
    };

//     typedef std::map map_t;

    typedef std::map map_t;


    // map allocator used to instantiate reference map in constructor
    typedef Pool_alloc map_allocator_t;

    // map pointer to the index map initialized in the constructor
    map_t* map_p;
    
    // Also  need a  special allocator  to allocate  the  Container in
    // shared memory.   The container is  created in shared  memory to
    // allow multiple processes to easily use and share it.

    typedef Pool_alloc container_allocator_t;

    typedef Pool_alloc object_allocator_t;
    
    // keep track of all containers allocated by this object.  If this
    // class allocated the object,  then this class should destroy the
    // object during the destructor call.

    // For  all objects  allocated  in shared  memory, instantiate  an
    // allocator which will be used  to set the Chunk list pointer for
    // that allocator.   The Chunk list  is stored in  the allocator's
    // Pool class as a static attribute.  Attaching classes must first
    // initialize their chunk list to  point to the correct address in
    // shared memory so that these attaching allocators can access the
    // same objects on the chunk list.

    // The following three allocators are needed just for the index map

    // Map index string allocator
    char_allocator_t char_alloc;
    // Map stored pair allocator
    map_pair_allocator_t map_pr_alloc;
    // Map container allocator
    map_allocator_t map_alloc;

    // The next two allocators are required by the stored containers

    container_allocator_t container_alloc;
    object_allocator_t object_alloc;

  public:
    typedef Object* pointer;
    typedef const Object* const_pointer;
    typedef size_t size_type;
    
    // constructor
    Multi_Process_Pool_alloc();
    // destructor
//     virtual ~Multi_Process_Pool_alloc() throw() {};
    virtual ~Multi_Process_Pool_alloc() throw();
    // copy constructor
    Multi_Process_Pool_alloc(const Multi_Process_Pool_alloc<
			     Container,
			     Object,
			     alloc_key,
			     container_key,
			     alloc_addr>& t)
      : char_alloc(t.char_alloc),
	map_pr_alloc(t.map_pr_alloc),
	map_alloc(t.map_alloc),
	container_alloc(t.container_alloc),
	object_alloc(t.object_alloc) {
      map_p = t.map_p;
    }; // copy constructor
    // assignment operator
    Multi_Process_Pool_alloc& operator=(const Multi_Process_Pool_alloc& t) {
      if (this != &t) {		// avoid self assignment: t=t
	map_p = t.map_p;
      }  // if (this != &t)
     return *this;
    }; // assignment operator
    Container* attach(void);
    mem_space::map_index_t get_map_index(void) {
      return mem.get_map_index();
    };  // get_map_index(void)
    void set_map_index(mem_space::map_index_t mem_obj) {
      mem.set_map_index(mem_obj);
    };  // get_map_index(void)
    int get_proj_id() {
      mem_space::map_index_t mem_idx =
	mem.get_map_index();
      return mem_idx.get_proj_id();
    }
    int get_segment_page_num() {
      mem_space::map_index_t mem_idx =
	mem.get_map_index();
      return mem_idx.get_segment_page_num();
    }
    void lock(int segment_num, int segment_page_num) {
      // lock access to the shared memory container
      mem.lock(segment_num,segment_page_num);
    }
    void unlock(int segment_num, int segment_page_num) {
      // lock access to the shared memory container
      mem.unlock(segment_num,segment_page_num);
    }
    Chunk* get_chunks_list(void) {
      // return a pointer to the chunk list
      return mem.get_chunks_list();
    }
    void set_chunks_list(Chunk* chunks) {
      // set the pointer to the chunks list
      mem.set_chunks_list(chunks);
      return;
    }
    void shutdown(void) {
      mem.shutdown();
      return;
    }
  };  // class Multi_Process_Pool_alloc


  ////////////////////////////////////////////////////////////////////
  //////
  //////    Multi_Process_Pool_alloc::attach()
  //////
  ////////////////////////////////////////////////////////////////////
  //////    
  //////    Allows  the  user  to   attach  to  the  container  object
  //////    instantiated in shared memory.  This method gives the user
  //////    access to  the container class.  Returns a  pointer to the
  //////    container object if OK or 0 on error.
  //////    
  ////////////////////////////////////////////////////////////////////
  
  template
  Container* Multi_Process_Pool_alloc::attach(void) {

    // first, attempt to find the container key
    typename map_t::iterator it = map_p->find(container_key);
    if (it != map_p->end()) {
      // Set the container's chunklist to point to the correct chunks
      Chunk* container_chunklist =
	static_cast(it->second.get_container_chunklist());
      container_alloc.set_chunks_list(container_chunklist);
      // Set the objects' chunklist to point to the correct chunks
      Chunk* object_chunklist =
	static_cast(it->second.get_object_chunklist());
      object_alloc.set_chunks_list(object_chunklist);
      Chunk* char_chunklist =
	static_cast(it->second.get_char_chunklist());
      char_alloc.set_chunks_list(char_chunklist);
      // indicate that we are now attached
      it->second.increment_ref_count();
#ifdef DEBUG
      std::clog << __FILE__ << ':' << __LINE__ << ':' <<
	"Multi_Process_Pool_alloc<>::attach() ref_count: " <<
	it->second.get_ref_count() << std::endl;
#endif
      // found container, return pointer to requested object
      return static_cast(it->second.get_memory_ptr());
	
    } else {
      std::clog << "Error: " << __FILE__ << ':' << __LINE__ ;
      std::clog << ": Multi_Process_Pool_alloc<>::attach(): Container key " <<
		container_key << " not found." << std::endl;
    }
    return 0;
  }

  ////////////////////////////////////////////////////////////////////
  //////
  //////     Multi_Process_Pool_alloc<>::Multi_Process_Pool_alloc()
  //////
  //////     constructor
  //////     
  //////     First    the     constructor    determines    from    the
  //////     get_map_index() call whether  or not the allocator has
  //////     been initialized for this  shared memory segment.  If the
  //////     segment  created  as opposed  to  just  opened, then  the
  //////     lookup map needs to be initialized.  The map itself needs
  //////     to be instantiated in the shared memory segment.
  //////     
  //////     After  establishing the  the lookup  map now  exists, the
  //////     class needs  to determine  whether or not  the particular
  //////     container  class that  the allocator  was called  to work
  //////     with  exists yet in  shared memory.   If not,  this class
  //////     needs to  instantiate that class  and register it  in the
  //////     lookup map for later retrieval.
  //////     
  //////     
  //////     
  ////////////////////////////////////////////////////////////////////

  // constructor
  template
  Multi_Process_Pool_alloc::Multi_Process_Pool_alloc()  {


    // If object index exists, retrieve it
    // if object index does not exist, create it
    mem_space::map_index_t obj_idx =
      get_map_index();

//     mem_space::memory_index_t obj_idx;

    if (!obj_idx.get_initialized()) {
      // if the object map is not valid, need to create and install a new map
      // Get a raw block of memory of the correct size using the allocator
      obj_idx = map_alloc.allocate_with_index(1);
      
      map_p = static_cast(obj_idx.get_memory_ptr());

      // instantiate a map into the shared memory
      new(map_p)map_t;

      // Now establish all pointers for the map index.  These pointers
      // include the chunklist pointer for the following allocators:

      //    map_alloc
      //    char_alloc
      //    container_alloc
      //    object_alloc

      // The Chunk list  is stored in the allocator's  Pool class as a
      // static  attribute.  Attaching  classes must  first initialize
      // their chunk  list to point  to the correct address  in shared
      // memory so that these attaching allocators can access the same
      // objects on  the chunk list  as the original allocator  in the
      // original process.
      Chunk* char_chunklist = char_alloc.get_chunks_list();
      obj_idx.set_char_chunklist(char_chunklist);
      Chunk* map_pr_chunklist = map_pr_alloc.get_chunks_list();
      obj_idx.set_map_chunklist(map_pr_chunklist);
      Chunk* map_chunklist = map_alloc.get_chunks_list();
      obj_idx.set_map_chunklist(map_chunklist);
      Chunk* container_chunklist = container_alloc.get_chunks_list();
      obj_idx.set_container_chunklist(container_chunklist);
      Chunk* object_chunklist = object_alloc.get_chunks_list();
      obj_idx.set_object_chunklist(object_chunklist);

      // Set the object index in shared memory
      pid_t pid = getpid();
      obj_idx.set_creator_pid(pid);
      set_map_index(obj_idx);

      
    } else {
      // map_p = get_map_index();
      map_p = reinterpret_cast(obj_idx.get_memory_ptr());
      // For the index map, reconstitute the needed chunk list pointers
      Chunk* chunklist =
	reinterpret_cast(obj_idx.get_char_chunklist());
      char_alloc.set_chunks_list(chunklist);
      chunklist =
	reinterpret_cast(obj_idx.get_map_pr_chunklist());
      map_pr_alloc.set_chunks_list(chunklist);
      chunklist =
	reinterpret_cast(obj_idx.get_map_chunklist());
      map_alloc.set_chunks_list(chunklist);
      chunklist =
	reinterpret_cast(obj_idx.get_container_chunklist());
      container_alloc.set_chunks_list(chunklist);
      chunklist =
	reinterpret_cast(obj_idx.get_object_chunklist());
      object_alloc.set_chunks_list(chunklist);

    } // if (!object_index.get_initialized())     

    // Next, determine if the container class is in the map
    // if not, allocate the container class and create a lookup entry
    // for the container.
    
    alloc_string_t key_str(container_key);
    typename map_t::iterator it = map_p->find(key_str);
    
    if (it == map_p->end()) {
      // container does not yet exist, create it
      obj_idx = container_alloc.allocate_with_index(1);
      // Get the chunk list for object allocator and save it for other
      // processes to use when attaching.

      Chunk* container_chunklist = container_alloc.get_chunks_list();
      obj_idx.set_container_chunklist(container_chunklist);
      Chunk* object_chunklist = object_alloc.get_chunks_list();
      obj_idx.set_object_chunklist(object_chunklist);

      alloc_string_t temp_str(container_key);
      map_pair_t tmp_pair(temp_str,obj_idx);

//       Chunk* container_chunklist = container_alloc.get_chunks_list();
//       Chunk* object_chunklist = object_alloc.get_chunks_list();
//       container_object_pr_t container_obj_pr(container_chunklist,
// 					     object_chunklist);
//       // Create and instantiate the container here.  The attach method
//       // gives   access  to   the  container   created  here   by  the
//       // constructor.
//       Container* container_ptr = static_cast(obj_idx.get_memory_ptr());
//       // instantiate the container in memory
//       new(container_ptr)Container;
//       // Now prep to put the container in the map for easy retrieval
//       alloc_string_t temp_str(container_key);
// //       map_pair_t tmp_pair(temp_str,obj_idx);
//       // map_p->insert(map_pair_t(container_key,obj_idx));
//       container_info_pair_t temp_cont_info_pr(obj_idx,container_obj_pr);


#ifdef DEBUG
      std::cerr << __FILE__ << ':' << __LINE__
		<< ": Multi_Process_Pool_alloc<>::Multi_Process_Pool_alloc() : "
		<< "map_p->insert(tmp_pair)" <<
       std::endl;
#endif
      map_p->insert(tmp_pair);
    }  else {
      // container entry exists, found
      std::cout << "key: " << it->first << std::endl;
      
      obj_idx = it->second;
      // Set  the allocator chunk  lists to  point to  the appropriate
      // addresses
      Chunk* chunk =
	reinterpret_cast(obj_idx.get_container_chunklist());
      container_alloc.set_chunks_list(chunk);
      chunk =
	reinterpret_cast(obj_idx.get_object_chunklist());
      object_alloc.set_chunks_list(chunk);
    }

  } // constructor 
  
  ////////////////////////////////////////////////////////////////////
  //////
  //////     Multi_Process_Pool_alloc<>::~Multi_Process_Pool_alloc()
  //////
  //////     destructor
  //////     
  //////     
  //////     
  //////     
  ////////////////////////////////////////////////////////////////////

  // destructor
  template
  Multi_Process_Pool_alloc::~Multi_Process_Pool_alloc() throw () {
    // Clean up allocated memory
    if (map_p != 0) {
      // map_p->clear();
      // destruct pair which matches the constuctor call for
      // map_alloc.allocate_with_index(1)
      mem_space::map_index_t obj_idx =
	get_map_index();
      pid_t pid = getpid();
      pid_t map_pid = obj_idx.get_creator_pid();
      if (pid == map_pid) {
	int in_use = 0;
	for (typename map_t::iterator it = map_p->begin(); it != map_p->end();
	   it++) {
	  mem_space::map_index_t& obj_idx = it->second;
	  obj_idx.decrement_ref_count();
#ifdef DEBUG
	  std::clog << __FILE__ << ':' << __LINE__ << ':' <<
	    "~Multi_Process_Pool_alloc() ref_count: " <<
	    it->second.get_ref_count() << std::endl;
#endif
	  const int& count = obj_idx.get_ref_count();
	  if (count <= 0) {
	    Container* container_ptr = static_cast(obj_idx.get_memory_ptr());
	    container_ptr->clear();
	    // delete container_ptr;
	    container_alloc.deallocate(container_ptr,1);
	  } else {
	    in_use++;
	  }
	}
	if (!in_use) {
 	  // At this point, need to clean up locks and shared memory
 	  // segments associated with this container's allocator.
 	  map_p->clear();
 	  // delete map_p;
 	  map_alloc.deallocate(map_p,1);
	  // use  the map  in the  shared memory  class to  remove all
	  // related shared memory segments
	  mem.unlink();
	}
      }
    }
  }; // destructor
  
}; // namespace pooled_allocator
  
#endif // ALLOCATOR_H