home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / f77 / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  2.9 KB  |  132 lines
  1. #define ASSERT(p) if(!(p))botch("p");else
  2. botch(s)
  3. char *s;
  4. {
  5.     printf("assertion botched: %s\n",s);
  6.     abort();
  7. }
  8. /*    C storage allocator
  9.  *    circular first-fit strategy
  10.  *    works with noncontiguous, but monotonically linked, arena
  11.  *    each block is preceded by a ptr to the (pointer of) 
  12.  *    the next following block
  13.  *    blocks are exact number of words long; BUSY
  14.  *    bit in ptr is 1 for busy, 0 for idle
  15.  *    gaps in arena are merely noted as busy blocks
  16.  *    last block of arena (pointed to by alloct) is empty and
  17.  *    has a pointer to first
  18.  *    idle blocks are coalesced during space search
  19. */
  20. /*    all these defines must be powers of 2 */
  21. #define WORD sizeof(struct store)
  22. #define BLOCK 1024
  23. #define BUSY 1
  24. #define NULL 0
  25. #define testbusy(p) ((int)(p)&BUSY)
  26. #define setbusy(p) ((int)(p)+BUSY)
  27. #define clearbusy(p) ((int)(p)&~BUSY)
  28.  
  29. struct store { struct store *ptr; };
  30.  
  31. struct store allocs[] = {    /*initial arena*/
  32.     setbusy(&allocs[1].ptr),
  33.     setbusy(&allocs[0].ptr)
  34. };
  35. struct store *allocp = &allocs[1];    /*search ptr*/
  36. struct store *alloct = &allocs[1];    /*arena top*/
  37. struct store *allocx;        /*for benefit of realloc*/
  38. struct store *sbrk();
  39.  
  40. struct store *
  41. malloc(nbytes)
  42. unsigned nbytes;
  43. {
  44.     register struct store *p, *q;
  45.     register nw;
  46.     static temp;    /*coroutines assume no auto*/
  47.  
  48.     nw = (nbytes+2*WORD-1)/WORD;
  49.     ASSERT(allocp>allocs && allocp<=alloct);
  50.     for(p=allocp; ; ) {
  51.         for(temp=0; ; ) {
  52.             if(!testbusy(p->ptr)) {
  53.                 while(!testbusy((q=p->ptr)->ptr)) {
  54.                     ASSERT(q>p&&q<alloct);
  55.                     p->ptr = q->ptr;
  56.                 }
  57.                 if(q>=p+nw && p+nw>=p)
  58.                     goto found;
  59.             }
  60.             q = p;
  61.             p = clearbusy(p->ptr);
  62.             if(p>q)
  63.                 ASSERT(p<=alloct);
  64.             else if(q!=alloct || p!=allocs) {
  65.                 write(2,"corrupt arena\n",14);
  66.                 exit(0175);
  67.             } else if(++temp>1)
  68.                 break;
  69.         }
  70.         temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
  71.         q = sbrk(0);
  72.         if(q+temp < q)
  73.             return(NULL);
  74.         q = sbrk(temp*WORD);
  75.         if((int)q == -1)
  76.             return(NULL);
  77.         ASSERT(q>alloct);
  78.         alloct->ptr = q;
  79.         if(q!=alloct+1)
  80.             alloct->ptr = setbusy(alloct->ptr);
  81.         alloct = q->ptr = q+temp-1;
  82.         alloct->ptr = setbusy(allocs);
  83.     }
  84. found:
  85.     allocp = p + nw;
  86.     ASSERT(allocp<=alloct);
  87.     if(q>allocp) {
  88.         allocx = allocp->ptr;
  89.         allocp->ptr = p->ptr;
  90.     }
  91.     p->ptr = setbusy(allocp);
  92.     return(p+1);
  93. }
  94. /*    freeing strategy tuned for LIFO allocation
  95. */
  96. free(p)
  97. register struct store *p;
  98. {
  99.     ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
  100.     allocp = --p;
  101.     ASSERT(testbusy(p->ptr));
  102.     p->ptr = clearbusy(p->ptr);
  103.     ASSERT(p->ptr > allocp && p->ptr <= alloct);
  104. }
  105.  
  106. struct { unsigned tag:4, vtype:4;};
  107.  
  108. prbusy()
  109. {
  110.     register struct store *p, *q;
  111.  
  112.     ASSERT(allocp>allocs && allocp<=alloct);
  113.     for(p=allocs; ; ) {
  114.             if(testbusy(p->ptr))
  115.                 {
  116.                 printf("busy 0%o, tag %d, type %d, length %d\n",
  117.                     p, p[1].tag, p[1].vtype,
  118.                     clearbusy(p->ptr) - (int) p - 2 );
  119.                 }
  120.             q = p;
  121.             p = clearbusy(p->ptr);
  122.             if(p>q)
  123.                 ASSERT(p<=alloct);
  124.             else if(q!=alloct || p!=allocs)
  125.                 {
  126.                 write(2,"corrupt arena\n",14);
  127.                 exit(0175);
  128.                 }
  129.             else return;
  130.     }
  131. }
  132.