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