Removing the pool allocator from the main CVS tree.

Use the poolalloc module in CVS from now on.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7810 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 0 insertions, 465 deletions

diff --git a/runtime/GCCLibraries/libpoolalloc/Makefile b/runtime/GCCLibraries/libpoolalloc/Makefile
deleted file mode 100644
index 2788fb2730..0000000000
--- a/runtime/GCCLibraries/libpoolalloc/Makefile
+++ /dev/null
@@ -1,4 +0,0 @@
-LEVEL = ../../..
-LIBNAME = poolalloc
-include ../Makefile.libs
-
diff --git a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c b/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c
deleted file mode 100644
index 4fa0aedecf..0000000000
--- a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c
+++ /dev/null
@@ -1,461 +0,0 @@
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#undef assert
-#define assert(X)
-
-
-/* In the current implementation, each slab in the pool has NODES_PER_SLAB
- * nodes unless the isSingleArray flag is set in which case it contains a
- * single array of size ArraySize. Small arrays (size <= NODES_PER_SLAB) are
- * still allocated in the slabs of size NODES_PER_SLAB
- */
-#define NODES_PER_SLAB 512 
-
-typedef struct PoolTy {
-  void    *Data;
-  unsigned NodeSize;
-  unsigned FreeablePool; /* Set to false if the memory from this pool cannot be
-			    freed before destroy*/
-  
-} PoolTy;
-
-/* PoolSlab Structure - Hold NODES_PER_SLAB objects of the current node type.
- *   Invariants: FirstUnused <= LastUsed+1
- */
-typedef struct PoolSlab {
-  unsigned FirstUnused;     /* First empty node in slab    */
-  int LastUsed;             /* Last allocated node in slab */
-  struct PoolSlab *Next;
-  unsigned char AllocatedBitVector[NODES_PER_SLAB/8];
-  unsigned char StartOfAllocation[NODES_PER_SLAB/8];
-
-  unsigned isSingleArray;   /* If this slab is used for exactly one array */
-  /* The array is allocated from the start to the end of the slab */
-  unsigned ArraySize;       /* The size of the array allocated */ 
-
-  char Data[1];   /* Buffer to hold data in this slab... variable sized */
-
-} PoolSlab;
-
-#define NODE_ALLOCATED(POOLSLAB, NODENUM) \
-   ((POOLSLAB)->AllocatedBitVector[(NODENUM) >> 3] & (1 << ((NODENUM) & 7)))
-#define MARK_NODE_ALLOCATED(POOLSLAB, NODENUM) \
-   (POOLSLAB)->AllocatedBitVector[(NODENUM) >> 3] |= 1 << ((NODENUM) & 7)
-#define MARK_NODE_FREE(POOLSLAB, NODENUM) \
-   (POOLSLAB)->AllocatedBitVector[(NODENUM) >> 3] &= ~(1 << ((NODENUM) & 7))
-#define ALLOCATION_BEGINS(POOLSLAB, NODENUM) \
-   ((POOLSLAB)->StartOfAllocation[(NODENUM) >> 3] & (1 << ((NODENUM) & 7)))
-#define SET_START_BIT(POOLSLAB, NODENUM) \
-   (POOLSLAB)->StartOfAllocation[(NODENUM) >> 3] |= 1 << ((NODENUM) & 7)
-#define CLEAR_START_BIT(POOLSLAB, NODENUM) \
-   (POOLSLAB)->StartOfAllocation[(NODENUM) >> 3] &= ~(1 << ((NODENUM) & 7))
-
-
-/* poolinit - Initialize a pool descriptor to empty
- */
-void poolinit(PoolTy *Pool, unsigned NodeSize) {
-  if (!Pool) {
-    printf("Null pool pointer passed into poolinit!\n");
-    exit(1);
-  }
-
-  Pool->NodeSize = NodeSize;
-  Pool->Data = 0;
-
-  Pool->FreeablePool = 1;
-
-}
-
-void poolmakeunfreeable(PoolTy *Pool) {
-  if (!Pool) {
-    printf("Null pool pointer passed in to poolmakeunfreeable!\n");
-    exit(1);
-  }
-
-  Pool->FreeablePool = 0;
-}
-
-/* pooldestroy - Release all memory allocated for a pool
- */
-void pooldestroy(PoolTy *Pool) {
-  PoolSlab *PS;
-  if (!Pool) {
-    printf("Null pool pointer passed in to pooldestroy!\n");
-    exit(1);
-  }
-
-  PS = (PoolSlab*)Pool->Data;
-  while (PS) {
-    PoolSlab *Next = PS->Next;
-    free(PS);
-    PS = Next;
-  }
-}
-
-static void *FindSlabEntry(PoolSlab *PS, unsigned NodeSize) {
-  /* Loop through all of the slabs looking for one with an opening */
-  for (; PS; PS = PS->Next) {
-
-    /* If the slab is a single array, go on to the next slab */
-    /* Don't allocate single nodes in a SingleArray slab */
-    if (PS->isSingleArray) 
-      continue;
-
-    /* Check to see if there are empty entries at the end of the slab... */
-    if (PS->LastUsed < NODES_PER_SLAB-1) {
-      /* Mark the returned entry used */
-      MARK_NODE_ALLOCATED(PS, PS->LastUsed+1);
-      SET_START_BIT(PS, PS->LastUsed+1);
-
-      /* If we are allocating out the first unused field, bump its index also */
-      if (PS->FirstUnused == PS->LastUsed+1)
-        PS->FirstUnused++;
-
-      /* Return the entry, increment LastUsed field. */
-      return &PS->Data[0] + ++PS->LastUsed * NodeSize;
-    }
-
-    /* If not, check to see if this node has a declared "FirstUnused" value that
-     * is less than the number of nodes allocated...
-     */
-    if (PS->FirstUnused < NODES_PER_SLAB) {
-      /* Successfully allocate out the first unused node */
-      unsigned Idx = PS->FirstUnused;
-
-      MARK_NODE_ALLOCATED(PS, Idx);
-      SET_START_BIT(PS, Idx);
-
-      /* Increment FirstUnused to point to the new first unused value... */
-      do {
-        ++PS->FirstUnused;
-      } while (PS->FirstUnused < NODES_PER_SLAB &&
-               NODE_ALLOCATED(PS, PS->FirstUnused));
-
-      return &PS->Data[0] + Idx*NodeSize;
-    }
-  }
-
-  /* No empty nodes available, must grow # slabs! */
-  return 0;
-}
-
-char *poolalloc(PoolTy *Pool) {
-  unsigned NodeSize;
-  PoolSlab *PS;
-  void *Result;
-
-  if (!Pool) {
-    printf("Null pool pointer passed in to poolalloc!\n");
-    exit(1);
-  }
-  
-  NodeSize = Pool->NodeSize;
-  // Return if this pool has size 0
-  if (NodeSize == 0)
-    return 0;
-
-  PS = (PoolSlab*)Pool->Data;
-
-  if ((Result = FindSlabEntry(PS, NodeSize)))
-    return Result;
-
-  /* Otherwise we must allocate a new slab and add it to the list */
-  PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1);
-
-  if (!PS) {
-    printf("poolalloc: Could not allocate memory!");
-    exit(1);
-  }
-
-  /* Initialize the slab to indicate that the first element is allocated */
-  PS->FirstUnused = 1;
-  PS->LastUsed = 0;
-  /* This is not a single array */
-  PS->isSingleArray = 0;
-  PS->ArraySize = 0;
-  
-  MARK_NODE_ALLOCATED(PS, 0);
-  SET_START_BIT(PS, 0);
-
-  /* Add the slab to the list... */
-  PS->Next = (PoolSlab*)Pool->Data;
-  Pool->Data = PS;
-  return &PS->Data[0];
-}
-
-void poolfree(PoolTy *Pool, char *Node) {
-  unsigned NodeSize, Idx;
-  PoolSlab *PS;
-  PoolSlab **PPS;
-  unsigned idxiter;
-
-  if (!Pool) {
-    printf("Null pool pointer passed in to poolfree!\n");
-    exit(1);
-  }
-
-  NodeSize = Pool->NodeSize;
-
-  // Return if this pool has size 0
-  if (NodeSize == 0)
-    return;
-
-  PS = (PoolSlab*)Pool->Data;
-  PPS = (PoolSlab**)&Pool->Data;
-
-  /* Search for the slab that contains this node... */
-  while (&PS->Data[0] > Node || &PS->Data[NodeSize*NODES_PER_SLAB-1] < Node) {
-    if (!PS) { 
-      printf("poolfree: node being free'd not found in allocation pool specified!\n");
-      exit(1);
-    }
-
-    PPS = &PS->Next;
-    PS = PS->Next;
-  }
-
-  /* PS now points to the slab where Node is */
-
-  Idx = (Node-&PS->Data[0])/NodeSize;
-  assert(Idx < NODES_PER_SLAB && "Pool slab searching loop broken!");
-
-  if (PS->isSingleArray) {
-
-    /* If this slab is a SingleArray */
-
-    if (Idx != 0) {
-      printf("poolfree: Attempt to free middle of allocated array\n");
-      exit(1);
-    }
-    if (!NODE_ALLOCATED(PS,0)) {
-      printf("poolfree: Attempt to free node that is already freed\n");
-      exit(1);
-    }
-    /* Mark this SingleArray slab as being free by just marking the first
-       entry as free*/
-    MARK_NODE_FREE(PS, 0);
-  } else {
-    
-    /* If this slab is not a SingleArray */
-    
-    if (!ALLOCATION_BEGINS(PS, Idx)) { 
-      printf("poolfree: Attempt to free middle of allocated array\n");
-      exit(1);
-    }
-
-    /* Free the first node */
-    if (!NODE_ALLOCATED(PS, Idx)) {
-      printf("poolfree: Attempt to free node that is already freed\n");
-      exit(1); 
-    }
-    CLEAR_START_BIT(PS, Idx);
-    MARK_NODE_FREE(PS, Idx);
-    
-    // Free all nodes 
-    idxiter = Idx + 1;
-    while (idxiter < NODES_PER_SLAB && (!ALLOCATION_BEGINS(PS,idxiter)) && 
-	   (NODE_ALLOCATED(PS, idxiter))) {
-      MARK_NODE_FREE(PS, idxiter);
-      ++idxiter;
-    }
-
-    /* Update the first free field if this node is below the free node line */
-    if (Idx < PS->FirstUnused) PS->FirstUnused = Idx;
-    
-    /* If we are not freeing the last element in a slab... */
-    if (idxiter - 1 != PS->LastUsed) {
-      return;
-    }
-
-    /* Otherwise we are freeing the last element in a slab... shrink the
-     * LastUsed marker down to last used node.
-     */
-    PS->LastUsed = Idx;
-    do {
-      --PS->LastUsed;
-      /* Fixme, this should scan the allocated array an entire byte at a time 
-       * for performance!
-       */
-    } while (PS->LastUsed >= 0 && (!NODE_ALLOCATED(PS, PS->LastUsed)));
-    
-    assert(PS->FirstUnused <= PS->LastUsed+1 &&
-	   "FirstUnused field was out of date!");
-  }
-    
-  /* 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.
-   */
-  /* Do this only if the pool is freeable */
-  if (Pool->FreeablePool) {
-    if (PS->isSingleArray) {
-      /* If it is a SingleArray, just free it */
-      *PPS = PS->Next;
-      free(PS);
-    } else if (PS->LastUsed == -1) {   /* Empty slab? */
-      PoolSlab *HeadSlab;
-      *PPS = PS->Next;   /* Unlink from the list of slabs... */
-      
-      HeadSlab = (PoolSlab*)Pool->Data;
-      if (HeadSlab && HeadSlab->LastUsed == -1){/*List already has empty slab?*/
-	free(PS);                               /*Free memory for slab */
-      } else {
-	PS->Next = HeadSlab;                    /*No empty slab yet, add this*/
-	Pool->Data = PS;                        /*one to the head of the list */
-      }
-    }
-  } else {
-    /* Pool is not freeable for safety reasons */
-    /* Leave it in the list of PoolSlabs as an empty PoolSlab */
-    if (!PS->isSingleArray)
-      if (PS->LastUsed == -1) {
-	PS->FirstUnused = 0;
-	
-	/* Do not free the pool, but move it to the head of the list if there is
-	   no empty slab there already */
-	PoolSlab *HeadSlab;
-	HeadSlab = (PoolSlab*)Pool->Data;
-	if (HeadSlab && HeadSlab->LastUsed != -1) {
-	  PS->Next = HeadSlab;
-	  Pool->Data = PS;
-	}
-      }
-  }
-}
-
-/* The poolallocarray version of FindSlabEntry */
-static void *FindSlabEntryArray(PoolSlab *PS, unsigned NodeSize, 
-				unsigned Size) {
-  unsigned i;
-
-  /* Loop through all of the slabs looking for one with an opening */
-  for (; PS; PS = PS->Next) {
-    
-    /* For large array allocation */
-    if (Size > NODES_PER_SLAB) {
-      /* If this slab is a SingleArray that is free with size > Size, use it */
-      if (PS->isSingleArray && !NODE_ALLOCATED(PS,0) && PS->ArraySize >= Size) {
-	/* Allocate the array in this slab */
-	MARK_NODE_ALLOCATED(PS,0); /* In a single array, only the first node
-				      needs to be marked */
-	return &PS->Data[0];
-      } else
-	continue;
-    } else if (PS->isSingleArray)
-      continue; /* Do not allocate small arrays in SingleArray slabs */
-
-    /* For small array allocation */
-    /* Check to see if there are empty entries at the end of the slab... */
-    if (PS->LastUsed < NODES_PER_SLAB-Size) {
-      /* Mark the returned entry used and set the start bit*/
-      SET_START_BIT(PS, PS->LastUsed + 1);
-      for (i = PS->LastUsed + 1; i <= PS->LastUsed + Size; ++i)
-	MARK_NODE_ALLOCATED(PS, i);
-
-      /* If we are allocating out the first unused field, bump its index also */
-      if (PS->FirstUnused == PS->LastUsed+1)
-        PS->FirstUnused += Size;
-
-      /* Increment LastUsed */
-      PS->LastUsed += Size;
-
-      /* Return the entry */
-      return &PS->Data[0] + (PS->LastUsed - Size + 1) * NodeSize;
-    }
-
-    /* If not, check to see if this node has a declared "FirstUnused" value
-     * starting which Size nodes can be allocated
-     */
-    if (PS->FirstUnused < NODES_PER_SLAB - Size + 1 &&
-	(PS->LastUsed < PS->FirstUnused || 
-	 PS->LastUsed - PS->FirstUnused >= Size)) {
-      unsigned Idx = PS->FirstUnused, foundArray;
-      
-      /* Check if there is a continuous array of Size nodes starting 
-	 FirstUnused */
-      foundArray = 1;
-      for (i = Idx; (i < Idx + Size) && foundArray; ++i)
-	if (NODE_ALLOCATED(PS, i))
-	  foundArray = 0;
-
-      if (foundArray) {
-	/* Successfully allocate starting from the first unused node */
-	SET_START_BIT(PS, Idx);
-	for (i = Idx; i < Idx + Size; ++i)
-	  MARK_NODE_ALLOCATED(PS, i);
-	
-	PS->FirstUnused += Size;
-	while (PS->FirstUnused < NODES_PER_SLAB &&
-               NODE_ALLOCATED(PS, PS->FirstUnused)) {
-	  ++PS->FirstUnused;
-	}
-	return &PS->Data[0] + Idx*NodeSize;
-      }
-      
-    }
-  }
-
-  /* No empty nodes available, must grow # slabs! */
-  return 0;
-}
-
-char* poolallocarray(PoolTy* Pool, unsigned Size) {
-  unsigned NodeSize;
-  PoolSlab *PS;
-  void *Result;
-  unsigned i;
-
-  if (!Pool) {
-    printf("Null pool pointer passed to poolallocarray!\n");
-    exit(1);
-  }
-
-  NodeSize = Pool->NodeSize;
-
-  // Return if this pool has size 0
-  if (NodeSize == 0)
-    return 0;
-
-  PS = (PoolSlab*)Pool->Data;
-
-  if ((Result = FindSlabEntryArray(PS, NodeSize,Size)))
-    return Result;
-
-  /* Otherwise we must allocate a new slab and add it to the list */
-  if (Size > NODES_PER_SLAB) {
-    /* Allocate a new slab of size Size */
-    PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*Size-1);
-    if (!PS) {
-      printf("poolallocarray: Could not allocate memory!\n");
-      exit(1);
-    }
-    PS->isSingleArray = 1;
-    PS->ArraySize = Size;
-    MARK_NODE_ALLOCATED(PS, 0);
-  } else {
-    PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1);
-    if (!PS) {
-      printf("poolallocarray: Could not allocate memory!\n");
-      exit(1);
-    }
-
-    /* Initialize the slab to indicate that the first element is allocated */
-    PS->FirstUnused = Size;
-    PS->LastUsed = Size - 1;
-    
-    PS->isSingleArray = 0;
-    PS->ArraySize = 0;
-
-    SET_START_BIT(PS, 0);
-    for (i = 0; i < Size; ++i) {
-      MARK_NODE_ALLOCATED(PS, i);
-    }
-  }
-
-  /* Add the slab to the list... */
-  PS->Next = (PoolSlab*)Pool->Data;
-  Pool->Data = PS;
-  return &PS->Data[0];
-}