text: //===- PoolAllocatorBitMask.cpp - Implementation of poolallocator runtime -===//
  // 
  //                       The LLVM Compiler Infrastructure
  //
  // This file was developed by the LLVM research group and is distributed under
  // the University of Illinois Open Source License. See LICENSE.TXT for details.
  // 
  //===----------------------------------------------------------------------===//
  //
  // This file is one possible implementation of the LLVM pool allocator runtime
  // library.
  //
  // This uses the 'Ptr1' field to maintain a linked list of slabs that are either
  // empty or are partially allocated from.  The 'Ptr2' field of the PoolTy is
  // used to track a linked list of slabs which are full, ie, all elements have
  // been allocated from them.
  //
  //===----------------------------------------------------------------------===//
  
  #include "PoolAllocator.h"
  #include "PoolCheck.h"
  #include "PageManager.h"
  #include <cassert>
  #include <cstdlib>
  #include <cstdio>
  #include <unistd.h>
  #define DEBUG(x)
  #define POOLCHECK(x) x 
  //===----------------------------------------------------------------------===//
  //
  //  PoolSlab implementation
  //
  //===----------------------------------------------------------------------===//
  unsigned ArrayBoundsCheck = 1;
  
  // PoolSlab Structure - Hold multiple objects of the current node type.
  // Invariants: FirstUnused <= UsedEnd
  //
  struct PoolSlab {
    PoolSlab **PrevPtr, *Next;
    bool isSingleArray;   // If this slab is used for exactly one array
    PoolSlab * OrigSlab;
  private:
    // FirstUnused - First empty node in slab
    unsigned short FirstUnused;
  
    // UsedBegin - The first node in the slab that is used.
    unsigned short UsedBegin;
  
    // UsedEnd - 1 past the last allocated node in slab. 0 if slab is empty
    unsigned short UsedEnd;
  
    // NumNodesInSlab - This contains the number of nodes in this slab, which
    // effects the size of the NodeFlags vector, and indicates the number of nodes
    // which are in the slab.
    unsigned int NumNodesInSlab;
    // NodeFlagsVector - This array contains two bits for each node in this pool
    // slab.  The first (low address) bit indicates whether this node has been
    // allocated, and the second (next higher) bit indicates whether this is the
    // start of an allocation.
    //
    // This is a variable sized array, which has 2*NumNodesInSlab bits (rounded up
    // to 4 bytes).
    unsigned NodeFlagsVector1;
    bool isNodeAllocated(unsigned NodeNum) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      return NodeFlagsVector[NodeNum/16] & (1 << (NodeNum & 15));
    }
  
    void markNodeAllocated(unsigned NodeNum) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      NodeFlagsVector[NodeNum/16] |= 1 << (NodeNum & 15);
    }
  
    void markNodeFree(unsigned NodeNum) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      NodeFlagsVector[NodeNum/16] &= ~(1 << (NodeNum & 15));
    }
  
    void setStartBit(unsigned NodeNum) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      NodeFlagsVector[NodeNum/16] |= 1 << ((NodeNum & 15)+16);
    }
  
    bool isStartOfAllocation(unsigned NodeNum) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      return NodeFlagsVector[NodeNum/16] & (1 << ((NodeNum & 15)+16));
    }
    
    void clearStartBit(unsigned NodeNum) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      NodeFlagsVector[NodeNum/16] &= ~(1 << ((NodeNum & 15)+16));
    }
  
  public:
    // create - Create a new (empty) slab and add it to the end of the Pools list.
    static PoolSlab *create(PoolTy *Pool);
  
    // createSingleArray - Create a slab for a large singlearray with NumNodes
    // entries in it, returning the pointer into the pool directly.
    static void *createSingleArray(PoolTy *Pool, unsigned NumNodes);
  
    // getSlabSize - Return the number of nodes that each slab should contain.
    static unsigned getSlabSize(PoolTy *Pool) {
      // We need space for the header...
      unsigned NumNodes = PageSize-sizeof(PoolSlab);
      
      // We need space for the NodeFlags...
      unsigned NodeFlagsBytes = NumNodes/Pool->NodeSize * 2 / 8;
      NumNodes -= (NodeFlagsBytes+3) & ~3;  // Round up to int boundaries.
  
      // Divide the remainder among the nodes!
      return NumNodes / Pool->NodeSize;
    }
  
    void initialize(unsigned NodesPerSlab) ;
    
    unsigned int GetNumNodesInSlab() {
      return NumNodesInSlab;
    }
    
    void addToList(PoolSlab **PrevPtrPtr) {
      PoolSlab *InsertBefore = *PrevPtrPtr;
      *PrevPtrPtr = this;
      PrevPtr = PrevPtrPtr;
      Next = InsertBefore;
      if (InsertBefore) InsertBefore->PrevPtr = &Next;
    }
  
    void unlinkFromList() {
      *PrevPtr = Next;
      if (Next) Next->PrevPtr = PrevPtr;
    }
  
    unsigned getSlabSize() const {
      return NumNodesInSlab;
    }
  
    // destroy - Release the memory for the current object.
    void destroy();
  
  
    // Unmap - Release the memory for the current object.
    void mprotect();
    
    // isEmpty - This is a quick check to see if this slab is completely empty or
    // not.
    bool isEmpty() const { return UsedEnd == 0; }
  
    // isFull - This is a quick check to see if the slab is completely allocated.
    //
    bool isFull() const { return isSingleArray || FirstUnused == getSlabSize(); }
  
    // allocateSingle - Allocate a single element from this pool, returning -1 if
    // there is no space.
    int allocateSingle();
  
    // allocateMultiple - Allocate multiple contiguous elements from this pool,
    // returning -1 if there is no space.
    int allocateMultiple(unsigned Num);
  
    // getElementAddress - Return the address of the specified element.
    void *getElementAddress(unsigned ElementNum, unsigned ElementSize) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      char *Data = (char*)&NodeFlagsVector[((unsigned)NumNodesInSlab+15)/16];
      return &Data[ElementNum*ElementSize];
    }
    const void *getElementAddress(unsigned ElementNum, unsigned ElementSize)const{
      const unsigned * NodeFlagsVector = &NodeFlagsVector1;
      const char *Data =
        (const char *)&NodeFlagsVector[(unsigned)(NumNodesInSlab+15)/16];
      return &Data[ElementNum*ElementSize];
    }
  
    // containsElement - Return the element number of the specified address in
    // this slab.  If the address is not in slab, return -1.
    int containsElement(void *Ptr, unsigned ElementSize) const;
  
    // freeElement - Free the single node, small array, or entire array indicated.
    void freeElement(unsigned short ElementIdx);
    
    // lastNodeAllocated - Return one past the last node in the pool which is
    // before ScanIdx, that is allocated.  If there are no allocated nodes in this
    // slab before ScanIdx, return 0.
    unsigned lastNodeAllocated(unsigned ScanIdx);
  };
  
  // create - Create a new (empty) slab and add it to the end of the Pools list.
  PoolSlab *PoolSlab::create(PoolTy *Pool) {
    unsigned NodesPerSlab = getSlabSize(Pool);
  
    unsigned Size = sizeof(PoolSlab) + 4*((NodesPerSlab+15)/16) +
      Pool->NodeSize*getSlabSize(Pool);
    assert(Size <= PageSize && "Trying to allocate a slab larger than a page!");
    PoolSlab *PS = (PoolSlab*)AllocatePage();
  
    PS->NumNodesInSlab = NodesPerSlab;
    PS->OrigSlab = PS; 
    PS->isSingleArray = 0;  // Not a single array!
    PS->FirstUnused = 0;    // Nothing allocated.
    PS->UsedBegin   = 0;    // Nothing allocated.
    PS->UsedEnd     = 0;    // Nothing allocated.
  
    // Add the slab to the list...
    PS->addToList((PoolSlab**)&Pool->Ptr1);
    //  printf(" creating a slab %x\n", PS);
    return PS;
  }
  
  void *PoolSlab::createSingleArray(PoolTy *Pool, unsigned NumNodes) {
    // FIXME: This wastes memory by allocating space for the NodeFlagsVector
    unsigned NodesPerSlab = getSlabSize(Pool);
    assert(NumNodes > NodesPerSlab && "No need to create a single array!");
  
    unsigned NumPages = (NumNodes+NodesPerSlab-1)/NodesPerSlab;
    PoolSlab *PS = (PoolSlab*)AllocateNPages(NumPages);
  
    assert(PS && "poolalloc: Could not allocate memory!");
  
    if (Pool->NumSlabs > AddrArrSize)
      Pool->Slabs->insert((void*)PS);
    else if (Pool->NumSlabs == AddrArrSize) {
      // Create the hash_set
      Pool->Slabs = new hash_set<void *>;
      Pool->Slabs->insert((void *)PS);
      for (unsigned i = 0; i < AddrArrSize; ++i)
        Pool->Slabs->insert((void *) Pool->SlabAddressArray[i]);
    } else {
      // Insert it in the array
      Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) PS;
    }
    Pool->NumSlabs++;
    
    PS->addToList((PoolSlab**)&Pool->LargeArrays);
  
    PS->isSingleArray = 1;
    PS->OrigSlab = PS;
    PS->NumNodesInSlab = NumPages * PageSize;
    *(unsigned*)&PS->FirstUnused = NumPages;
    return PS->getElementAddress(0, 0);
  }
  void MprotectPage(void *pa, unsigned numPages);
  
  void PoolSlab::mprotect() {
    if (isSingleArray) {
        unsigned NumPages = *(unsigned*)&FirstUnused; 
        MprotectPage((char*)this, NumPages);
    }
    else 
      MprotectPage(this, 1);
  }
  
  void PoolSlab::destroy() {
    if (isSingleArray)
      for (unsigned NumPages = *(unsigned*)&FirstUnused; NumPages != 1;--NumPages)
        FreePage((char*)this + (NumPages-1)*PageSize);
  
    FreePage(this);
  }
  
  // allocateSingle - Allocate a single element from this pool, returning -1 if
  // there is no space.
  int PoolSlab::allocateSingle() {
    // If the slab is a single array, go on to the next slab.  Don't allocate
    // single nodes in a SingleArray slab.
    if (isSingleArray) return -1;
  
    unsigned SlabSize = PoolSlab::getSlabSize();
  
    // Check to see if there are empty entries at the end of the slab...
    if (UsedEnd < SlabSize) {
      // Mark the returned entry used
      unsigned short UE = UsedEnd;
      markNodeAllocated(UE);
      setStartBit(UE);
      
      // If we are allocating out the first unused field, bump its index also
      if (FirstUnused == UE)
        FirstUnused++;
      
      // Return the entry, increment UsedEnd field.
      return UsedEnd++;
    }
    
    // If not, check to see if this node has a declared "FirstUnused" value that
    // is less than the number of nodes allocated...
    //
    if (FirstUnused < SlabSize) {
      // Successfully allocate out the first unused node
      unsigned Idx = FirstUnused;
      markNodeAllocated(Idx);
      setStartBit(Idx);
      
      // Increment FirstUnused to point to the new first unused value...
      // FIXME: this should be optimized
      unsigned short FU = FirstUnused;
      do {
        ++FU;
      } while (FU != SlabSize && isNodeAllocated(FU));
      FirstUnused = FU;
      
      return Idx;
    }
    
    return -1;
  }
  
  // allocateMultiple - Allocate multiple contiguous elements from this pool,
  // returning -1 if there is no space.
  int PoolSlab::allocateMultiple(unsigned Size) {
    // Do not allocate small arrays in SingleArray slabs
    if (isSingleArray) return -1;
  
    // For small array allocation, check to see if there are empty entries at the
    // end of the slab...
    if (UsedEnd+Size <= getSlabSize()) {
      // Mark the returned entry used and set the start bit
      unsigned UE = UsedEnd;
      setStartBit(UE);
      for (unsigned i = UE; i != UE+Size; ++i)
        markNodeAllocated(i);
      
      // If we are allocating out the first unused field, bump its index also
      if (FirstUnused == UE)
        FirstUnused += Size;
  
      // Increment UsedEnd
      UsedEnd += Size;
  
      // Return the entry
      return UE;
    }
  
    // If not, check to see if this node has a declared "FirstUnused" value
    // starting which Size nodes can be allocated
    //
    unsigned Idx = FirstUnused;
    while (Idx+Size <= getSlabSize()) {
      assert(!isNodeAllocated(Idx) && "FirstUsed is not accurate!");
  
      // Check if there is a continuous array of Size nodes starting FirstUnused
      unsigned LastUnused = Idx+1;
      for (; LastUnused != Idx+Size && !isNodeAllocated(LastUnused); ++LastUnused)
        /*empty*/;
  
      // If we found an unused section of this pool which is large enough, USE IT!
      if (LastUnused == Idx+Size) {
        setStartBit(Idx);
        // FIXME: this loop can be made more efficient!
        for (unsigned i = Idx; i != Idx + Size; ++i)
          markNodeAllocated(i);
  
        // This should not be allocating on the end of the pool, so we don't need
        // to bump the UsedEnd pointer.
        assert(Idx != UsedEnd && "Shouldn't allocate at end of pool!");
  
        // If we are allocating out the first unused field, bump its index also.
        if (Idx == FirstUnused)
          FirstUnused += Size;
        
        // Return the entry
        return Idx;
      }
  
      // Otherwise, try later in the pool.  Find the next unused entry.
      Idx = LastUnused;
      while (Idx+Size <= getSlabSize() && isNodeAllocated(Idx))
        ++Idx;
    }
  
    return -1;
  }
  
  
  // containsElement - Return the element number of the specified address in
  // this slab.  If the address is not in slab, return -1.
  int PoolSlab::containsElement(void *Ptr, unsigned ElementSize) const {
    const void *FirstElement = getElementAddress(0, 0);
    if (FirstElement <= Ptr) {
      unsigned Delta = (char*)Ptr-(char*)FirstElement;
      if (isSingleArray) 
        if (Delta < NumNodesInSlab) return Delta/ElementSize;
      unsigned Index = Delta/ElementSize;
      if (Index < getSlabSize()) {
        if (Delta % ElementSize != 0) {
  	printf("Freeing pointer into the middle of an element!");
  	abort();
        }
        
        return Index;
      }
    }
    return -1;
  }
  
  void PoolSlab::initialize(unsigned NodesPerSlab) {
    
   NumNodesInSlab = NodesPerSlab;
   isSingleArray = 0;  // Not a single array!
   FirstUnused = 0;    // Nothing allocated.
   UsedBegin   = 0;    // Nothing allocated.
   UsedEnd     = 0;    // Nothing allocated.
    
    // Add the slab to the list...
  }
  // freeElement - Free the single node, small array, or entire array indicated.
  void PoolSlab::freeElement(unsigned short ElementIdx) {
    if (!isNodeAllocated(ElementIdx)) return;
    //  assert(isNodeAllocated(ElementIdx) &&
    //         "poolfree: Attempt to free node that is already freed\n");
    //  assert(!isSingleArray && "Cannot free an element from a single array!");
  
    // Mark this element as being free!
    markNodeFree(ElementIdx);
  
    // If this slab is not a SingleArray
    assert(isStartOfAllocation(ElementIdx) &&
           "poolfree: Attempt to free middle of allocated array\n");
    
    // Free the first cell
    clearStartBit(ElementIdx);
    markNodeFree(ElementIdx);
    
    // Free all nodes if this was a small array allocation.
    unsigned short ElementEndIdx = ElementIdx + 1;
  
    // FIXME: This should use manual strength reduction to produce decent code.
    unsigned short UE = UsedEnd;
    while (ElementEndIdx != UE &&
           !isStartOfAllocation(ElementEndIdx) && 
           isNodeAllocated(ElementEndIdx)) {
      markNodeFree(ElementEndIdx);
      ++ElementEndIdx;
    }
    
    // Update the first free field if this node is below the free node line
    if (ElementIdx < FirstUnused) FirstUnused = ElementIdx;
  
    // Update the first used field if this node was the first used.
    if (ElementIdx == UsedBegin) UsedBegin = ElementEndIdx;
    
    // If we are freeing the last element in a slab, shrink the UsedEnd marker
    // down to the last used node.
    if (ElementEndIdx == UE) {
  #if 0
        printf("FU: %d, UB: %d, UE: %d  FREED: [%d-%d)",
             FirstUnused, UsedBegin, UsedEnd, ElementIdx, ElementEndIdx);
  #endif
  
      // If the user is freeing the slab entirely in-order, it's quite possible
      // that all nodes are free in the slab.  If this is the case, simply reset
      // our pointers.
      if (UsedBegin == UE) {
        //printf(": SLAB EMPTY\n");
        FirstUnused = 0;
        UsedBegin = 0;
        UsedEnd = 0;
      } else if (FirstUnused == ElementIdx) {
        // Freed the last node(s) in this slab.
        FirstUnused = ElementIdx;
        UsedEnd = ElementIdx;
      } else {
        UsedEnd = lastNodeAllocated(ElementIdx);
        assert(FirstUnused <= UsedEnd+1 &&
               "FirstUnused field was out of date!");
      }
    }
  }
  
  unsigned PoolSlab::lastNodeAllocated(unsigned ScanIdx) {
    // Check the last few nodes in the current word of flags...
    unsigned CurWord = ScanIdx/16;
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    unsigned short Flags = NodeFlagsVector[CurWord] & 0xFFFF;
    if (Flags) {
      // Mask off nodes above this one
      Flags &= (1 << ((ScanIdx & 15)+1))-1;
      if (Flags) {
        // If there is still something in the flags vector, then there is a node
        // allocated in this part.  The goto is a hack to get the uncommonly
        // executed code away from the common code path.
        //printf("A: ");
        goto ContainsAllocatedNode;
      }
    }
  
    // Ok, the top word doesn't contain anything, scan the whole flag words now.
    --CurWord;
    while (CurWord != ~0U) {
      unsigned * NodeFlagsVector = &NodeFlagsVector1;
      Flags = NodeFlagsVector[CurWord] & 0xFFFF;
      if (Flags) {
        // There must be a node allocated in this word!
        //printf("B: ");
        goto ContainsAllocatedNode;
      }
      CurWord--;
    }
    return 0;
  
  ContainsAllocatedNode:
    // Figure out exactly which node is allocated in this word now.  The node
    // allocated is the one with the highest bit set in 'Flags'.
    //
    // This should use __builtin_clz to get the value, but this builtin is only
    // available with GCC 3.4 and above.  :(
    assert(Flags && "Should have allocated node!");
    
    unsigned short MSB;
  #if GCC3_4_EVENTUALLY
    MSB = 16 - ::__builtin_clz(Flags);
  #else
    for (MSB = 15; (Flags & (1U << MSB)) == 0; --MSB)
      /*empty*/;
  #endif
  
    assert((1U << MSB) & Flags);   // The bit should be set
    assert((~(1U << MSB) & Flags) < Flags);// Removing it should make flag smaller
    ScanIdx = CurWord*16 + MSB;
    assert(isNodeAllocated(ScanIdx));
    return ScanIdx;
  }
  
  
  //===----------------------------------------------------------------------===//
  //
  //  Pool allocator library implementation
  //
  //===----------------------------------------------------------------------===//
  
  // poolinit - Initialize a pool descriptor to empty
  //
  void poolinit(PoolTy *Pool, unsigned NodeSize) {
    assert(Pool && "Null pool pointer passed into poolinit!\n");
    DEBUG(printf("pool init %x, %d\n", Pool, NodeSize);)
  
    // Ensure the page manager is initialized
    InitializePageManager();
  
    // We must alway return unique pointers, even if they asked for 0 bytes
    Pool->NodeSize = NodeSize ? NodeSize : 1;
    Pool->Ptr1 = Pool->Ptr2 = 0;
    Pool->LargeArrays = 0;
    // For SAFECode, we set FreeablePool to 0 always
    //  Pool->FreeablePool = 0;
    Pool->lastUsed = 0;
    Pool->prevPage[0] = 0;
    Pool->prevPage[1] = 0;
    // Initialize the SlabAddressArray to zero
    for (int i = 0; i < AddrArrSize; ++i) {
      Pool->SlabAddressArray[i] = 0;
    }
  
    Pool->NumSlabs = 0;
    POOLCHECK(poolcheckinit(Pool, NodeSize);)
    POOLCHECK(Pool->splay = new_splay();)
    POOLCHECK(Pool->PCS = 0;)
    ///  Pool->Slabs = new hash_set<void*>;
    // Call hash_set constructor explicitly
    //   void *SlabPtr = &Pool->Slabs;
    //   new (SlabPtr) hash_set<void*>;
  }
  
  void poolmakeunfreeable(PoolTy *Pool) {
    assert(Pool && "Null pool pointer passed in to poolmakeunfreeable!\n");
    //  Pool->FreeablePool = 0;
  }
  
  // pooldestroy - Release all memory allocated for a pool
  //
  void pooldestroy(PoolTy *Pool) {
    DEBUG(printf("pooldestroying %x\n", Pool);)
    assert(Pool && "Null pool pointer passed in to pooldestroy!\n");
    if (Pool->NumSlabs > AddrArrSize) {
      Pool->Slabs->clear();
      delete Pool->Slabs;
    }
    POOLCHECK(free_splay(Pool->splay);)
    // Free any partially allocated slabs
    PoolSlab *PS = (PoolSlab*)Pool->Ptr1;
    while (PS) {
      PoolSlab *Next = PS->Next;
      PS->destroy();
      PS = Next;
    }
  
    // Free the completely allocated slabs
    PS = (PoolSlab*)Pool->Ptr2;
    while (PS) {
      PoolSlab *Next = PS->Next;
      PS->destroy();
      PS = Next;
    }
  
    // Free the large arrays
    PS = (PoolSlab*)Pool->LargeArrays;
    while (PS) {
      PoolSlab *Next = PS->Next;
      PS->destroy();
      PS = Next;
    }
  
    POOLCHECK(poolcheckdestroy(Pool);)
  }
  
  
  // poolallocarray - a helper function used to implement poolalloc, when the
  // number of nodes to allocate is not 1.
  static void *poolallocarray(PoolTy* Pool, unsigned Size) {
    assert(Pool && "Null pool pointer passed into poolallocarray!\n");
    if (Size > PoolSlab::getSlabSize(Pool))
      return PoolSlab::createSingleArray(Pool, Size);
   
    PoolSlab *PS = (PoolSlab*)Pool->Ptr1;
  
    // Loop through all of the slabs looking for one with an opening
    for (; PS; PS = PS->Next) {
      int Element = PS->allocateMultiple(Size);
      if (Element != -1) {
        // We allocated an element.  Check to see if this slab has been completely
        // filled up.  If so, move it to the Ptr2 list.
        if (PS->isFull()) {
          PS->unlinkFromList();
          PS->addToList((PoolSlab**)&Pool->Ptr2);
        }
        return PS->getElementAddress(Element, Pool->NodeSize);
      }
    }
    
    PoolSlab *New = PoolSlab::create(Pool);
    POOLCHECK(poolcheckAddSlab(&Pool->PCS, New);)
    if (Pool->NumSlabs > AddrArrSize) {
      DEBUG(printf("new slab inserting %x \n", (void *)New);)
      Pool->Slabs->insert((void *)New);
    } else if (Pool->NumSlabs == AddrArrSize) {
      // Create the hash_set
      Pool->Slabs = new hash_set<void *>;
      Pool->Slabs->insert((void *)New);
      for (unsigned i = 0; i < AddrArrSize; ++i)
        Pool->Slabs->insert((void *)Pool->SlabAddressArray[i]);
    } else {
      // Insert it in the array
      Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) New;
    }
    Pool->NumSlabs++;
    
    //  return malloc(Size * Pool->NodeSize);
    int Idx = New->allocateMultiple(Size);
    assert(Idx == 0 && "New allocation didn't return zero'th node?");
    return New->getElementAddress(0, 0);
  }
  
  void *poolalloc(PoolTy *Pool, unsigned NumBytes) {
    //  return malloc(Size * Pool->NodeSize);
    void *retAddress = NULL;
    if (!Pool) {
      printf("Null pool pointer passed in to poolalloc!, FAILING\n");
      exit(-1);
    } 
    unsigned NodeSize = Pool->NodeSize;
    unsigned NodesToAllocate1 = NumBytes / NodeSize;
    if (NodesToAllocate1 == 0) {
      //    abort();
    }
    unsigned NodesToAllocate = (NumBytes+NodeSize-1)/NodeSize;
    if (NodesToAllocate > 1) {
      retAddress = poolallocarray(Pool, NodesToAllocate);
      DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
        POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
      return retAddress;
    }
  
    // Special case the most common situation, where a single node is being
    // allocated.
    PoolSlab *PS = (PoolSlab*)Pool->Ptr1;
  
    if (__builtin_expect(PS != 0, 1)) {
      int Element = PS->allocateSingle();
      if (__builtin_expect(Element != -1, 1)) {
        // We allocated an element.  Check to see if this slab has been
        // completely filled up.  If so, move it to the Ptr2 list.
        if (__builtin_expect(PS->isFull(), false)) {
          PS->unlinkFromList();
          PS->addToList((PoolSlab**)&Pool->Ptr2);
        }
        retAddress = PS->getElementAddress(Element, NodeSize);
        DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
        POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
        return retAddress;
      }
  
      // Loop through all of the slabs looking for one with an opening
      for (PS = PS->Next; PS; PS = PS->Next) {
        int Element = PS->allocateSingle();
        if (Element != -1) {
          // We allocated an element.  Check to see if this slab has been
          // completely filled up.  If so, move it to the Ptr2 list.
          if (PS->isFull()) {
            PS->unlinkFromList();
            PS->addToList((PoolSlab**)&Pool->Ptr2);
          }
  	retAddress = PS->getElementAddress(Element, NodeSize);
  	DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
          POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
  	return retAddress;
        }
      }
    }
  
    // Otherwise we must allocate a new slab and add it to the list
    PoolSlab *New = PoolSlab::create(Pool);
    POOLCHECK(poolcheckAddSlab(&Pool->PCS, New);)
    
    if (Pool->NumSlabs > AddrArrSize)
      Pool->Slabs->insert((void *)New);
    else if (Pool->NumSlabs == AddrArrSize) {
      // Create the hash_set
      Pool->Slabs = new hash_set<void *>;
      Pool->Slabs->insert((void *)New);
      for (unsigned i = 0; i < AddrArrSize; ++i)
        Pool->Slabs->insert((void *)Pool->SlabAddressArray[i]);
    } else {
      // Insert it in the array
      Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) New;
    }
    Pool->NumSlabs++;
  
    int Idx = New->allocateSingle();
    assert(Idx == 0 && "New allocation didn't return zero'th node?");
    retAddress = New->getElementAddress(0, 0);
    DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
    POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
    return retAddress;
  }
  
  /*
  // SearchForContainingSlab - This implementation uses the hash_set as well
  // as the array to search the list of allocated slabs for the node in question
  static PoolSlab *SearchForContainingSlab(PoolTy *Pool, void *Node,
                                           unsigned &TheIndex) {
    //  printf("in pool check for pool %x, node %x\n",Pool,Node);
    unsigned NodeSize = Pool->NodeSize;
    void *PS;
    if (!Pool) {
      printf("Empty Pool in pool check FAILING \n");
      exit(-1);
    } 
    assert (Pool->AllocadPool <= 0 && "SearchForContainingSlab not to be called"
            " for alloca'ed pools");
    
    PS = (void*)((long)Node & ~(PageSize-1));
    if (Pool->NumSlabs > AddrArrSize) {
      hash_set<void*> &theSlabs = *Pool->Slabs;
      if (theSlabs.find(PS) == theSlabs.end()) {
        // Check the LargeArrays
        if (Pool->LargeArrays) {
  	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
  	unsigned Idx = -1;
  	while (PSlab) {
  	  assert(PSlab && "poolcheck: node being free'd not found in "
  		 "allocation pool specified!\n");
  	  Idx = PSlab->containsElement(Node, NodeSize);
  	  if (Idx != -1) break;
  	  PSlab = PSlab->Next;
  	}
  	if (Idx == -1) {
  	  printf("poolcheck: node being checked not found in pool \n");
  	  abort();
  	}
  	TheIndex = Idx;
  	return PSlab;
        } else {
  	printf("poolcheck: node being checked not found in pool \n");
  	abort();
        }
      } else {
        // Check that Node does not point to PoolSlab meta-data
        if ((PoolSlab *)PS->getElementAddress(0,0) > (long) Node) {
  	printf("poolcheck: node being checked points to meta-data \n");
  	abort();
        }	
        TheIndex = PS->containsElement(Node, NodeSize);
        return (PoolSlab *)PS;
      }
    } else {
      bool found;
      for (unsigned i = 0; i < AddrArrSize && !found; ++i) {
        if (Pool->SlabAddressArray[i] == (unsigned) PS)
  	found = true;
      } 
  
      if (found) {
        // Check that Node does not point to PoolSlab meta-data
        if ((PoolSlab *)PS->getElementAddress(0,0) > (long) Node) {
  	printf("poolcheck: node being checked points to meta-data \n");
  	abort();
        }	
        TheIndex = PS->containsElement(Node, NodeSize);
        return (PoolSlab *)PS;
      } else {
        // Check the LargeArrays
        if (Pool->LargeArrays) {
  	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
  	unsigned Idx = -1;
  	while (PSlab) {
  	  assert(PSlab && "poolcheck: node being free'd not found in "
  		 "allocation pool specified!\n");
  	  Idx = PSlab->containsElement(Node, NodeSize);
  	  if (Idx != -1) break;
  	  PSlab = PSlab->Next;
  	}
  	if (Idx == -1) {
  	  printf("poolcheck: node being checked not found in pool \n");
  	  abort();
  	}
  	TheIndex = Idx;
  	return PSlab;	
        }
        printf("poolcheck: node being checked not found in pool \n");
        abort();
      }
    }
  }
  */
  
  #if 0
  // SearchForContainingSlab - Do a brute force search through the list of
  // allocated slabs for the node in question.
  //
  static PoolSlab *SearchForContainingSlab(PoolTy *Pool, void *Node,
                                           unsigned &TheIndex) {
    PoolSlab *PS = (PoolSlab*)Pool->Ptr1;
    unsigned NodeSize = Pool->NodeSize;
  
    // Search the partially allocated slab list for the slab that contains this
    // node.
    int Idx = -1;
    if (PS) {               // Pool->Ptr1 could be null if Ptr2 isn't
      for (; PS; PS = PS->Next) {
        Idx = PS->containsElement(Node, NodeSize);
        if (Idx != -1) break;
      }
    }
  
    // If the partially allocated slab list doesn't contain it, maybe the
    // completely allocated list does.
    if (PS == 0) {
      PS = (PoolSlab*)Pool->Ptr2;
      assert(Idx == -1 && "Found node but don't have PS?");
      
      while (PS) {
        assert(PS && "poolfree: node being free'd not found in allocation "
               " pool specified!\n");
        Idx = PS->containsElement(Node, NodeSize);
        if (Idx != -1) break;
        PS = PS->Next;
      }
    }
    
    // Otherwise, maybe its a block within LargeArrays
    if(PS == 0) {
      PS = (PoolSlab*)Pool->LargeArrays;
      assert(Idx == -1  && "Found node but don't have PS?");
      
      while (PS) {
        assert(PS && "poolfree: node being free'd not found in allocation "
               " pool specified!\n");
        Idx = PS->containsElement(Node, NodeSize);
        if (Idx != -1) break;
        PS = PS->Next;
      }
    }
  
    TheIndex = Idx;
    return PS;
  }
  #endif
  
  void* poolallocatorcheck(PoolTy *Pool, void *Node) {
    PoolSlab *PS = (PoolSlab*)((unsigned)Node & ~(PageSize-1));
  
    if (Pool->NumSlabs > AddrArrSize) {
      hash_set<void*> &theSlabs = *Pool->Slabs;
      if (theSlabs.find((void*)PS) == theSlabs.end()) {
        // Check the LargeArrays
        if (Pool->LargeArrays) {
  	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
  	int Idx = -1;
  	while (PSlab) {
  	  assert(PSlab && "poolcheck: node being free'd not found in "
  		 "allocation pool specified!\n");
  	  Idx = PSlab->containsElement(Node, Pool->NodeSize);
  	  if (Idx != -1) {
  	    Pool->prevPage[Pool->lastUsed] = PS;
  	    Pool->lastUsed = (Pool->lastUsed + 1) % 4;
  	    return PS;
  	    break;
  	  }
  	  PSlab = PSlab->Next;
  	}
  	
  	if (Idx == -1) {
  	  Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
  	  if (ref)   {
  	    return 0;
  	  }
  	  printf("poolcheck1: node being checked not found in pool with right"
  		 " alignment\n");
  	  abort();
  	} else {
  	  return 0;
  	  //exit(-1);
  	}
        } else {
  	// here we check for the splay tree
  	Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
  	if (ref) {
  	  return 0;
  	} else {
  	  printf("poolcheck2: ref not found "
  		 " alignment\n");
  	  abort();
  	  exit(-1);
  	}
        }
      } else {
        unsigned long startaddr = (unsigned long)PS->getElementAddress(0,0);
        if (startaddr > (unsigned long) Node) {
  	printf("poolcheck: node being checked points to meta-data \n");
  	abort();
        }
        unsigned long offset = ((unsigned long) Node - (unsigned long) startaddr) % Pool->NodeSize;
        if (offset != 0) {
  	printf("poolcheck3: node being checked does not have right alignment\n");
  	abort();
        }
        Pool->prevPage[Pool->lastUsed] = PS;
        Pool->lastUsed = (Pool->lastUsed + 1) % 4;
        return PS;
      }
    } else {
      bool found = false;
      for (unsigned i = 0; i < AddrArrSize && !found; ++i) {
        if ((unsigned)Pool->SlabAddressArray[i] == (unsigned) PS) {
  	found = true;
  	Pool->prevPage[Pool->lastUsed] = PS;
  	Pool->lastUsed = (Pool->lastUsed + 1) % 4;
        }
      } 
  
      if (found) {
        // Check that Node does not point to PoolSlab meta-data
        unsigned long startaddr = (unsigned long)PS->getElementAddress(0,0);
        if (startaddr > (unsigned long) Node) {
  	printf("poolcheck: node being checked points to meta-data \n");
  	exit(-1);
        }
        unsigned long offset = ((unsigned long) Node - (unsigned long) startaddr) % Pool->NodeSize;
        if (offset != 0) {
  	printf("poolcheck4: node being checked does not have right alignment\n");
  	abort();
        }
        return PS;
      } else {
        // Check the LargeArrays
        if (Pool->LargeArrays) {
  	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
  	int Idx = -1;
  	while (PSlab) {
  	  assert(PSlab && "poolcheck: node being free'd not found in "
  		 "allocation pool specified!\n");
  	  Idx = PSlab->containsElement(Node, Pool->NodeSize);
  	  if (Idx != -1) {
  	    Pool->prevPage[Pool->lastUsed] = PS;
  	    Pool->lastUsed = (Pool->lastUsed + 1) % 4;
  	    break;
  	  }
  	  PSlab = PSlab->Next;
  	}
  	if (Idx == -1) {
  	  Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
  	  if (ref)    return 0;	  
  	  printf("poolcheck6: node being checked not found in pool with right"
  		 " alignment\n");
  	  abort();
  	} else {
  	  return PSlab;
  	}
        } else {
  	Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
  	if (ref) {
  	  return 0;
  	} else {
  	  printf("poolcheck5: ref not found "
  		 " alignment check not done \n");
  	  abort();
  	}	
        }
      }
    }
  }
  
  /*
  void poolcheckarray(MetaPoolTy **MP, void *NodeSrc, void *NodeResult) {
    MetaPoolTy *MetaPool = *MP;
    if (!MetaPool) {
      printf("Empty meta pool? \n");
      exit(-1);
    }
    //iteratively search through the list
    //Check if there are other efficient data structures.
    hash_set<void *>::iterator PTI = MetaPool->PoolTySet->begin(), PTE = MetaPool->PoolTySet->end();
    PoolTy *srcPool = 0;
    for (; PTI != PTE; ++PTI) {
      PoolTy *Pool = (PoolTy *)*PTI;
      PoolSlab *PS;
      PS = (PoolSlab*)((unsigned long)NodeSrc & ~(PageSize-1));
      if (Pool->prevPage[0] == PS) {
        srcPool = Pool;
      }
      if (Pool->prevPage[1] == PS) {
        srcPool = Pool;
      }    
      if (Pool->prevPage[2] == PS) {
        srcPool = Pool;
      }    
      if (Pool->prevPage[3] == PS) {
        srcPool = Pool;
      }
      if (poolcheckoptim(Pool, NodeSrc)) {
        srcPool = Pool;
      } else continue;
      //Now check for reuslt
      if (poolcheckoptim(srcPool, NodeResult)) {          
          MetaPool->cachePool = srcPool;
          return;
      } else {
          printf("source and dest belong to different pools\n");
          exit(-1);
      }
    }
    printf("poolcheck failure \n");
    exit(-1);
  }
  */
  
  void poolfree(PoolTy *Pool, void *Node) {
    assert(Pool && "Null pool pointer passed in to poolfree!\n");
    DEBUG(printf("poolfree  %x %x \n",Pool,Node);)
    PoolSlab *PS;
    int Idx;
    PS = (PoolSlab *)poolallocatorcheck(Pool, Node);
    assert(PS && "poolfree the element not in pool ");
    if (PS->isSingleArray) {
      PS->unlinkFromList();
      unsigned  NumPages = PS->GetNumNodesInSlab() / PageSize;
      
      unsigned NodesPerSlab = PoolSlab::getSlabSize(Pool);
  
      unsigned Size = sizeof(PoolSlab) + 4*((NodesPerSlab+15)/16) +
        Pool->NodeSize* NodesPerSlab;
      assert(Size <= PageSize && "Trying to allocate a slab larger than a page!");
      for (unsigned i = 0; i <NumPages; ++i) {
        PoolSlab *PSi = (PoolSlab *)((unsigned long)PS + i * PageSize);
  
        PSi->initialize(NodesPerSlab);
        if (i != 0) {
  	PSi->addToList((PoolSlab**)&Pool->Ptr1);
        }
        if (Pool->NumSlabs > AddrArrSize) {
  	DEBUG(printf("new slab inserting %x \n", (void *)New);)
  	  Pool->Slabs->insert((void *)PSi);
        } else if (Pool->NumSlabs == AddrArrSize) {
  	// Create the hash_set
  	Pool->Slabs = new hash_set<void *>;
  	Pool->Slabs->insert((void *)PSi);
  	for (unsigned i = 0; i < AddrArrSize; ++i)
  	  Pool->Slabs->insert((void *)Pool->SlabAddressArray[i]);
        } else {
  	// Insert it in the array
  	Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) PSi;
        }
        Pool->NumSlabs++;       
      }
      return;
    } 
    Idx = PS->containsElement(Node, Pool->NodeSize);
    assert((Idx != -1) && " node not present, it should have aborted ");
  
    // If PS was full, it must have been in list #2.  Unlink it and move it to
    // list #1.
    if (PS->isFull()) {
      // Now that we found the node, we are about to free an element from it.
      // This will make the slab no longer completely full, so we must move it to
      // the other list!
      PS->unlinkFromList(); // Remove it from the Ptr2 list.
  
      PoolSlab **InsertPosPtr = (PoolSlab**)&Pool->Ptr1;
  
      // If the partially full list has an empty node sitting at the front of the
      // list, insert right after it.
      if (*InsertPosPtr && (*InsertPosPtr)->isEmpty())
        InsertPosPtr = &(*InsertPosPtr)->Next;
  
      PS->addToList(InsertPosPtr);     // Insert it now in the Ptr1 list.
    }
  
    // Free the actual element now!
    PS->freeElement(Idx);
  
    // Ok, if this slab is empty, we unlink it from the of slabs and either move
    // it to the head of the list, or free it, depending on whether or not there
    // is already an empty slab at the head of the list.
    //
    if (PS->isEmpty()) {
      PS->unlinkFromList();   // Unlink from the list of slabs...
      
      // If we can free this pool, check to see if there are any empty slabs at
      // the start of this list.  If so, delete the FirstSlab!
      PoolSlab *FirstSlab = (PoolSlab*)Pool->Ptr1;
      if (0 && FirstSlab && FirstSlab->isEmpty()) {
        // Here we choose to delete FirstSlab instead of the pool we just freed
        // from because the pool we just freed from is more likely to be in the
        // processor cache.
        FirstSlab->unlinkFromList();
        FirstSlab->destroy();
        //      Pool->Slabs.erase((void *)FirstSlab);
      }
   
      // Link our slab onto the head of the list so that allocations will find it
      // efficiently.    
      PS->addToList((PoolSlab**)&Pool->Ptr1);
    }
  }
  
  
    void *poolrealloc(PoolTy *Pool, void *Node, unsigned NumBytes) {
      if (Node == 0) return poolalloc(Pool, NumBytes);
      if (NumBytes == 0) {
        poolfree(Pool, Node);
        return 0;
      }
      void *New = poolalloc(Pool, NumBytes);
      //    unsigned Size =
      //FIXME the following may not work in all cases  
      memcpy(New, Node, NumBytes);
      poolfree(Pool, Node);
      return New;
    }
  
    void poolregister(PoolTy *Pool, void *allocadptr, unsigned NumBytes) {
      POOLCHECK(poolcheckregister(Pool->splay, allocadptr, NumBytes);)
    }
    PoolCheckSlab *poolcheckslab(void *Pool) {
      return ((PoolTy *)Pool)->PCS;
    }
  
    Splay *poolchecksplay(void *Pool) {
      return ((PoolTy *)Pool)->splay;
    }
  
    void poolcheckfail (const char * msg) {
      fprintf (stderr, msg);
      fflush (stderr);
      exit (-1);
    }
  
    void * poolcheckmalloc (unsigned int size) {
      return malloc (size);
    }
  