lib-src/memory/boundtag.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <assert.h>
  26 #include <string.h>
  27 #include <AD/memory/boundtag.h>   // Boundary tag memory manager
  28
  29 //////////////////////////////////////////////////////////////////////////////
  30 // Constructor: initialize the memory manager.  The free list initially
  31 // contains one ``stub'' element.
  32 //////////////////////////////////////////////////////////////////////////////
  33 BoundaryTag::BoundaryTag(long size) : Mem("BoundaryTag"), pages(0)
  34 {  pageSize = size > 256 ? size : 256;         // The default page size
  35    clear();
  36 }
  37
  38 BoundaryTag::BoundaryTag(Mem& m, long size) : Mem(m, "BoundaryTag"), pages(0)
  39 {  pageSize = size > 256 ? size : 256;         // The default page size
  40    clear();
  41 }
  42 //////////////////////////////////////////////////////////////////////////////
  43 // Destructor:  frees all the pages allocated
  44 //////////////////////////////////////////////////////////////////////////////
  45 BoundaryTag::~BoundaryTag() { clear(); }
  46
  47 //////////////////////////////////////////////////////////////////////////////
  48 // Release all memory from the manager
  49 //////////////////////////////////////////////////////////////////////////////
  50 void BoundaryTag::clear()
  51 {  Page * current, * next;
  52    for (current = pages; current; current = next) {
  53       next = current->next;
  54       manager_mem->free(current);
  55    }
  56    pages = NULL;                               // Linked list of pages
  57    freeList = stub.next = stub.last = &stub;   // Dummy element
  58    stub.size = stub.last_size = 0;
  59    allocated = 0;
  60 }
  61
  62 //////////////////////////////////////////////////////////////////////////////
  63 //  Allocate a new string from the manager.
  64 //////////////////////////////////////////////////////////////////////////////
  65 char * BoundaryTag::operator [] (const char * string)
  66 {  char * newString = (char *) (*this)[strlen(string) + 1];
  67    strcpy(newString,string);
  68    return newString;
  69 }
  70
  71 //////////////////////////////////////////////////////////////////////////////
  72 //  Allocate a chunk of storage from the memory manager
  73 //////////////////////////////////////////////////////////////////////////////
  74 void * BoundaryTag::m_alloc(size_t size)
  75 {  register unsigned long elements =
  76       (size + 2*sizeof(Block) - offsetof(Block,next)-1) / sizeof(Block);
  77    register Block * B, * start;
  78
  79    //
  80    // Use first fit strategy starting from the free list
  81    //
  82    for (;;) {
  83       for (B = start = freeList;  ;B = B->next) {
  84          if (B->size >= elements) {         // Size fitting??
  85             if (B->size - elements < 2) {   // Split block or not??
  86                //
  87                // The block should not be split.  Mark the block as allocated,
  88                // unlink it from the free list and returns the free block
  89                // to the client.  We'll also advance the free list to the
  90                // next block after the current block so that we will not
  91                // stuck at one end of the free list.
  92                //
  93                B[B->size].last_size |= Block::USED_BIT;
  94                B->size |= Block::USED_BIT;
  95                B->next->last = B->last;
  96                B->last->next = B->next;
  97                freeList = B->next;
  98                return &B->next;
  99             } else {
 100                //
 101                // The block will be split.  We'll keep the top chunk
 102                // and return the bottom chunk to the client.  Nothing
 103                // will have to be deleted from the free list.
 104                //
 105                register long leftOver = B->size - elements;
 106                register Block * newBlock = B + leftOver;
 107                newBlock[elements].last_size =
 108                   newBlock->size = elements | Block::USED_BIT;
 109                newBlock->last_size = B->size = leftOver;
 110                freeList = B;
 111                return &newBlock->next;
 112             }
 113          }
 114          if (B->next == start) break;  // back to the start??
 115       }
 116       this->grow(size);  // Allocate a new page
 117    }
 118 }
 119
 120 //////////////////////////////////////////////////////////////////////////////
 121 // This auxiliary function allocate a new page and puts it onto the
 122 // free list.
 123 //////////////////////////////////////////////////////////////////////////////
 124 void BoundaryTag::grow(long bytes)
 125 {
 126    if (bytes < pageSize) bytes = pageSize;
 127    long elements =
 128       (bytes + 2*sizeof(Block) - offsetof(Block,next)-1) / sizeof(Block);
 129
 130    Page * newPage = (Page*)
 131       manager_mem->m_alloc(sizeof(Page) + elements * sizeof(Block));
 132    Block * B = newPage->blocks;
 133
 134    newPage->next = pages;   // Chain the pages together
 135    pages = newPage;
 136
 137    allocated += elements * sizeof(Block);
 138
 139    //
 140    // The new page is split into two blocks.  One is of size |elements|
 141    // and the other is of size 1 and is located just after the first
 142    // block.  The latter block is a stub and is marked with the used bit
 143    // so that it will not be accidently merged with the first.
 144    //
 145
 146    B[elements].last_size = B->size = elements;
 147    B[elements].size = B->last_size = (LongWord)Block::USED_BIT | 1;
 148
 149    //
 150    // Link the new block |B| so that it is located after the
 151    // current starting point of the free list
 152    //
 153
 154    B->next = freeList->next;
 155    B->last = freeList;
 156    freeList->next = B;
 157    B->next->last = B;
 158    freeList = B;          // Point the free list directly to the new block
 159                           // so that we'll won't have to search for it
 160                           // when we return
 161 }
 162
 163 //////////////////////////////////////////////////////////////////////////////
 164 //  Free block, combines it with adjacent blocks if that is possible.
 165 //////////////////////////////////////////////////////////////////////////////
 166 void BoundaryTag::free(void * core)
 167 {  if (core != 0) {
 168       register Block * B = (Block*) (((char *)core) - offsetof(Block,next));
 169       register Block * aBlock;
 170
 171       assert( (B->size & Block::USED_BIT) == Block::USED_BIT);
 172
 173       B->size &= ~Block::USED_BIT;                  // Unmark the used bit
 174       aBlock = B + B->size;                         // This is the next block
 175       if ( (aBlock->size & Block::USED_BIT) == 0) { // Merge with next block??
 176          aBlock->next->last = aBlock->last;         // Unlink the next block
 177          aBlock->last->next = aBlock->next;
 178          if (aBlock == freeList) freeList = aBlock->next;
 179          B->size += aBlock->size;                   // and merge
 180          B[B->size].last_size = B->size;
 181       } else {
 182          aBlock->last_size &= ~Block::USED_BIT;
 183       }
 184
 185       if ( (B->last_size & Block::USED_BIT) == 0) { // Merge with last block??
 186          aBlock = B - B->last_size;                 // This is the last block
 187          aBlock->size += B->size;                   // and merge
 188          aBlock[aBlock->size].last_size = aBlock->size;
 189          return;
 190       }
 191
 192       // Now, merges |B|, the (possibly coalesed) free block,
 193       // to the position {\em before} the current starting point
 194       // of the free list.   This way there is time before this same
 195       // block is encountered again.  This gives this block more opportunity
 196       // to be merged with some other adjacent blocks, which might be
 197       // freed during this time.
 198
 199       B->next = freeList;
 200       B->last = freeList->last;
 201       freeList->last = B;
 202       B->last->next = B;
 203    }
 204 }
 205
 206 //////////////////////////////////////////////////////////////////////////////
 207 // Compute allocation statistics of the memory manager.
 208 //////////////////////////////////////////////////////////////////////////////
 209 BoundaryTag::Statistics BoundaryTag::statistics() const
 210 {  Statistics S;
 211    register Page * page;
 212    register Block * B;
 213
 214    S.bytes_allocated = allocated;
 215
 216    // Count the number of pages allocated
 217
 218    for (S.page_count = 0, page = pages; page; page = page->next)
 219       S.page_count++;
 220
 221    //
 222    // Count the number of free blocks within freelist and compute
 223    // the amount of bytes free
 224
 225    for (S.free_block_count = 0, S.bytes_available = 0,
 226         B = freeList; ; B = B->next) {
 227       S.bytes_available += B->size;
 228       S.free_block_count++;
 229       if (B->next == freeList) break;
 230    }
 231
 232    S.bytes_available *= sizeof(Block);
 233
 234    return S;
 235 }
 236
 237 //////////////////////////////////////////////////////////////////////////////
 238 //  Returns the size of an allocated block
 239 //////////////////////////////////////////////////////////////////////////////
 240 size_t BoundaryTag::size(const void * core) const
 241 {  register Block * B = (Block*) (((char *)core) - offsetof(Block,next));
 242    assert( (B->size & Block::USED_BIT) == Block::USED_BIT);
 243    return B->size & ~Block::USED_BIT;
 244 }
 245