title: C++ memory pool on shared memory implementation: Is this method of allocation and deallocation correct?
body: <p>May I request that I any responder consider only "pure" C/C++ (whatever that means)? STL is ok. Boost is not.</p>
  
  <p>I am writing my own C++ memory pool class (on a Linux system) for allocating and deallocating C++ objects in shared memory. I need this for access to the same objects over multiple processes. I will control access to memory pool object manipulation using POSIX semaphores, but I had a basic allocation/deallocation question. My code will only work for objects of the same size being allocated from the same pool. For the moment, we can ignore issues related to growth and shrinking of the pool dynamically.</p>
  
  <p>Consider that I have a shared memory segment defined for a total of MAXFOOOBJECTS Foo objects. I define the shared memory segment in the following manner:</p>
  
  <pre><code>int shmid = shmget (somekey, ((sizeof(Foo) + 4) * MAXFOOOBJECTS) + 4, correctFlags);
  void* sMem = shmat (shmid, (void*)0, 0);
  </code></pre>
  
  <p>By all the processes using this shared memory, the memory will be interpreted like so:</p>
  
  <pre><code>struct SharedMemStructure
  {
     int numberOfFooObjectsInPool;
     Foo* ptrArray [MAXFOOOBJECTS]; // Pointers to all the objects in the array below
     Foo objects [MAXFOOOBJECTS]; // Same as the value in the shmget call
  };
  </code></pre>
  
  <p>Let us say I have an object Foo defined like so:</p>
  
  <pre><code>&lt;Foo.h&gt; 
  class Foo
  {
     public:
       Foo ();
       ~Foo ();
       void* operator new (); // Will allocate from shared memory
       void operator delete (void* ptr); // Will deallocate from shared memory
     private:
       static void* sharedMem; // Set this up to be a POSIX shared memory that accesses
                        // the shared region in memory
       static int shmid;
  }
  
  &lt;Foo.cpp&gt;
  int Foo::shmid = shmget (somekey, ((sizeof(Foo) + 4) * MAXFOOOBJECTS) + 4, correctFlags);
  void* Foo::sharedMem = shmat (shmid, (void*)0, 0);
  
  void* Foo::operator new ()
  {
     void* thisObject = NULL;
     sem_wait (sem); // Implementation of these is not shown
     // Pick up the start of a chunk from sharedMem (will make sure this
     // chunk has unused memory...
  
     thisObject = (sharedMem + 4 + 4 * MAXFOOOBJECTS + 
                  (sizeof (Foo) * sharedMem-&gt;numberOfFooObjectsInPool);
     sharedMem-&gt;ptrArray[numberOfFooObjectsInPool] = thisObject;
     sharedMem-&gt;numberOfFooObjectsInPool ++;
     sem_post (sem);
     return thisObject;
  }
  
  void Foo::operator delete (void* ptr)
  {
     int index = 0;
     sem_wait (sem); // Implementation of these is not shown
     // Swap the deleted item and the last item in the ptrArray;
     index = (ptr - (sharedMem + 4 + (4*MAXFOOOBJECTS)))/(sizeof(Foo));
     ptrArray[index] == ptrArray[numberOfFooObjectsInPool - 1];
     numberOfFooObjectsInPool --;
     sem_post (sem);
  }
  </code></pre>
  
  <p>Now, my questions are: </p>
  
  <ol>
  <li>Does the aforementioned scheme seem OK to you folks (O (1) for each of new and delete) or am I missing something utterly important? One problem I see immediately is that if the Foo object array is interpreted as a min heap, for example, I kill the heap property everytime I do the new and delete. </li>
  <li>If I guarantee that this pool won't be used for min heap (say, as needed by Timer management techniques), do we have any issues with the aforementioned scheme? </li>
  <li>On the flip side, I could manage the Foo array in the shared memory as a min or max heap (i.e., during new-ing and delete-ing) and incur O (lg n) worst case for each new or delete. Any comments?</li>
  <li>Any other method that is preferable?</li>
  </ol>