util/ass/asscm.c

   1 /*
   2  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   3  * See the copyright notice in the ACK home directory, in the file "Copyright".
   4  *
   5  */
   6
   7 /*  Core management for the EM assembler.
   8     two routines:
   9         getarea(size)
  10                 returns a pointer to a free area of 'size' bytes.
  11         freearea(ptr,size)
  12                 free's the area of 'size' bytes pointed to by ptr
  13
  14     Free blocks are linked together and kept sorted.
  15     Adjacent free blocks are collapsed.
  16     Free blocks with a size smaller then the administration cannot
  17     exist.
  18     The algorithm is first fit.
  19 */
  20
  21 #include "ass00.h"
  22
  23 #ifndef NORCSID
  24 static char rcs_id[] = "$Id: asscm.c,v 2.6 1994/06/24 10:15:30 ceriel Exp $" ;
  25 #endif
  26
  27 #ifdef MEMUSE
  28 static unsigned m_used = 0 ;
  29 static unsigned m_free = 0 ;
  30 #endif
  31
  32 struct freeblock {
  33         struct freeblock *f_next ;
  34         unsigned         f_size  ;
  35 } ;
  36
  37 static struct freeblock freexx[2] = {
  38         { freexx, 0 },
  39         { freexx+1, 0 }
  40 } ;
  41
  42 #define freehead freexx[1]
  43
  44 #define CHUNK 2048              /* Smallest chunk to be gotten from UNIX */
  45
  46 area_t getarea(size) unsigned size ; {
  47         register struct freeblock *c_ptr,*l_ptr ;
  48         register char *ptr ;
  49         unsigned rqsize ;
  50         char *malloc() ;
  51
  52         size = ((size + (sizeof(int) - 1)) / sizeof(int)) * sizeof(int);
  53 #ifdef MEMUSE
  54         m_used += size ;
  55         m_free -= size ;
  56 #endif
  57         for(;;) {
  58                 for ( l_ptr= &freehead, c_ptr= freehead.f_next ;
  59                       c_ptr!= &freehead ; c_ptr = c_ptr->f_next ) {
  60                         if ( size==c_ptr->f_size ) {
  61                                 l_ptr->f_next= c_ptr->f_next ;
  62                                 return (area_t) c_ptr ;
  63                         }
  64                         if ( size+sizeof freehead <= c_ptr->f_size ) {
  65                                 c_ptr->f_size -= size ;
  66                            return (area_t) ((char *) c_ptr + c_ptr->f_size) ;
  67                         }
  68                         l_ptr = c_ptr ;
  69                 }
  70                 rqsize = size<CHUNK ? CHUNK : size ;
  71                 for(;;){
  72                         ptr = malloc( rqsize ) ;
  73                         if ( ptr ) break ; /* request succesfull */
  74                         rqsize /= 2 ;
  75                         rqsize -= rqsize%sizeof (int) ;
  76                         if ( rqsize < sizeof freehead ) {
  77                                 fatal("Out of memory") ;
  78                         }
  79                 }
  80                 freearea((area_t)ptr,rqsize) ;
  81 #ifdef MEMUSE
  82                 m_used += rqsize ;
  83 #endif
  84         }
  85         /* NOTREACHED */
  86 }
  87
  88 freearea(ptr,size) register area_t ptr ; unsigned size ; {
  89         register struct freeblock *c_ptr, *l_ptr ;
  90
  91         size = ((size + (sizeof(int) - 1)) / sizeof(int)) * sizeof(int);
  92 #ifdef MEMUSE
  93         m_free += size ;
  94         m_used -= size ;
  95 #endif
  96         for ( l_ptr= &freehead, c_ptr=freehead.f_next ;
  97               c_ptr!= &freehead ; c_ptr= c_ptr->f_next ) {
  98                 if ( (area_t)c_ptr>ptr ) break ;
  99                 l_ptr= c_ptr ;
 100         }
 101         /* now insert between l_ptr and c_ptr */
 102         /* Beware they may both point to freehead */
 103
 104 #ifdef MEMUSE
 105         if ( ((char *)l_ptr)+l_ptr->f_size> (char *)ptr && (char *)l_ptr<=(char *)ptr )
 106                 fatal("Double freed") ;
 107         if ( ((char *)ptr)+size > (char *)c_ptr && (char *)ptr<=(char *)c_ptr )
 108                 fatal("Frreed double") ;
 109 #endif
 110         /* Is the block before this one adjacent ? */
 111         if ( ((char *)l_ptr) + l_ptr->f_size == (char *) ptr ) {
 112                 l_ptr->f_size += size ; /* yes */
 113         } else {
 114                 /* No, create an entry */
 115                 ((struct freeblock *)ptr)->f_next = c_ptr ;
 116                 ((struct freeblock *)ptr)->f_size = size ;
 117                 l_ptr->f_next = (struct freeblock *)ptr ;
 118                 l_ptr = (struct freeblock *)ptr ;
 119         }
 120         /* Are the two entries adjacent ? */
 121         if ( (char *)l_ptr + l_ptr->f_size == (char *) c_ptr ) {
 122                 /* the two entries are adjacent */
 123                 l_ptr->f_next = c_ptr->f_next ;
 124                 l_ptr->f_size += c_ptr->f_size ;
 125         }
 126 }
 127
 128 #ifdef MEMUSE
 129 memuse() {
 130         printf("Free %7u, Used %7u, Total %7u\n",m_free,m_used,m_free+m_used);
 131 }
 132 #endif