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