home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / ROBOT01.ZIP / RCCL092 < prev    next >
Encoding:
Text File  |  1987-03-02  |  4.6 KB  |  218 lines
  1. /* @(#)malloc.c    4.1 (Berkeley) 12/21/80 */
  2. /*
  3.  * rtc  V1      Modified : Vincent Hayward,
  4.  *              School of Electrical Engineering, Purdue University
  5.  *              Mon Apr 11 11:01:47 EST 1983
  6.  */
  7.  
  8. /*LINTLIBRARY*/
  9.  
  10.  
  11.  
  12. /*    avoid break bug */
  13. #ifdef pdp11
  14. #define GRANULE 64
  15. #else
  16. #define GRANULE 0
  17. #endif
  18. /*    C storage allocator
  19.  *    circular first-fit strategy
  20.  *    works with noncontiguous, but monotonically linked, arena
  21.  *    each block is preceded by a ptr to the (pointer of)
  22.  *    the next following block
  23.  *    blocks are exact number of words long
  24.  *    aligned to the data type requirements of ALIGN
  25.  *    pointers to blocks must have BUSY bit 0
  26.  *    bit in ptr is 1 for busy, 0 for idle
  27.  *    gaps in arena are merely noted as busy blocks
  28.  *    last block of arena (pointed to by alloct) is empty and
  29.  *    has a pointer to first
  30.  *    idle blocks are coalesced during space search
  31.  *
  32.  *    a different implementation may need to redefine
  33.  *    ALIGN, NALIGN, BLOCK, BUSY, INT
  34.  *    where INT is integer type to which a pointer can be cast
  35. */
  36. #define INT int
  37. #define ALIGN int
  38. #define NALIGN 1
  39. #define WORD sizeof(union store)
  40. #define BLOCK 1024    /* a multiple of WORD*/
  41. #define BUSY 1
  42. #define NULL 0
  43. #define testbusy(p) ((INT)(p)&BUSY)
  44. #define setbusy(p) (union store *)((INT)(p)|BUSY)
  45. #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
  46.  
  47. union store { union store *ptr;
  48.           ALIGN dummy[NALIGN];
  49.           int calloc;    /*calloc clears an array of integers*/
  50. };
  51.  
  52. static    union store allocs[2];    /*initial arena*/
  53. static    union store *allocp;    /*search ptr*/
  54. static    union store *alloct;    /*arena top*/
  55. static    union store *allocx;    /*for benefit of realloc*/
  56. char    *sbrk_l();
  57.  
  58. char *
  59. malloc_l(nbytes)
  60. unsigned nbytes;
  61. {
  62.     register union store *p, *q;
  63.     register nw;
  64.     static temp;    /*coroutines assume no auto*/
  65.  
  66.     if(allocs[0].ptr==0) {    /*first time*/
  67.         allocs[0].ptr = setbusy(&allocs[1]);
  68.         allocs[1].ptr = setbusy(&allocs[0]);
  69.         alloct = &allocs[1];
  70.         allocp = &allocs[0];
  71.     }
  72.     nw = (nbytes+WORD+WORD-1)/WORD;
  73.     for(p=allocp; ; ) {
  74.         for(temp=0; ; ) {
  75.             if(!testbusy(p->ptr)) {
  76.                 while(!testbusy((q=p->ptr)->ptr)) {
  77.                     p->ptr = q->ptr;
  78.                 }
  79.                 if(q>=p+nw && p+nw>=p)
  80.                     goto found;
  81.             }
  82.             q = p;
  83.             p = clearbusy(p->ptr);
  84.             if(p>q)
  85.                 ;
  86.             else if(q!=alloct || p!=allocs) {
  87.                 return(NULL);
  88.             } else if(++temp>1)
  89.                 break;
  90.         }
  91.         temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
  92.         q = (union store *)sbrk_l(0);
  93.         if(q+temp+GRANULE < q) {
  94.             return(NULL);
  95.         }
  96.         q = (union store *)sbrk_l((unsigned int)temp*WORD);
  97.         if((INT)q == -1) {
  98.             return(NULL);
  99.         }
  100.         alloct->ptr = q;
  101.         if(q!=alloct+1)
  102.             alloct->ptr = setbusy(alloct->ptr);
  103.         alloct = q->ptr = q+temp-1;
  104.         alloct->ptr = setbusy(allocs);
  105.     }
  106. found:
  107.     allocp = p + nw;
  108.     if(q>allocp) {
  109.         allocx = allocp->ptr;
  110.         allocp->ptr = p->ptr;
  111.     }
  112.     p->ptr = setbusy(allocp);
  113.     return((char *)(p+1));
  114. }
  115.  
  116. /*    freeing strategy tuned for LIFO allocation
  117. */
  118. free_l(ap)
  119. register char *ap;
  120. {
  121.     register union store *p = (union store *)ap;
  122.  
  123.     allocp = --p;
  124.     p->ptr = clearbusy(p->ptr);
  125. }
  126.  
  127. /*    realloc(p, nbytes) reallocates a block obtained from malloc()
  128.  *    and freed since last call of malloc()
  129.  *    to have new size nbytes, and old content
  130.  *    returns new location, or 0 on failure
  131. */
  132.  
  133. char *
  134. realloc_l(p, nbytes)
  135. register union store *p;
  136. unsigned nbytes;
  137. {
  138.     register union store *q;
  139.     union store *s, *t;
  140.     register unsigned nw;
  141.     unsigned onw;
  142.  
  143.     if(testbusy(p[-1].ptr))
  144.         free_l((char *)p);
  145.     onw = p[-1].ptr - p;
  146.     q = (union store *)malloc_l(nbytes);
  147.     if(q==NULL || q==p)
  148.         return((char *)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++ = *s++;
  156.     if(q<p && q+nw>=p)
  157.         (q+(q+nw-p))->ptr = allocx;
  158.     return((char *)q);
  159. }
  160.  
  161. /* @(#)calloc.c    4.1 (Berkeley) 12/21/80 */
  162. /*    calloc - allocate and clear memory block
  163. */
  164. #define CHARPERINT (sizeof(int)/sizeof(char))
  165. #define NULL 0
  166.  
  167. char *
  168. calloc_l(num, size)
  169. unsigned num, size;
  170. {
  171.     register char *mp;
  172.     char *malloc();
  173.     register int *q;
  174.     register m;
  175.  
  176.     num *= size;
  177.     mp = malloc_l(num);
  178.     if(mp == NULL)
  179.         return(NULL);
  180.     q = (int *) mp;
  181.     m = (num+CHARPERINT-1)/CHARPERINT;
  182.     while(--m>=0)
  183.         *q++ = 0;
  184.     return(mp);
  185. }
  186.  
  187. /*ARGSUSED*/
  188.  
  189. cfree_l(p, num, size)
  190. char *p;
  191. unsigned num, size;
  192. {
  193.     free_l(p);
  194. }
  195.  
  196.  
  197.  
  198. #define NPOOL   BLOCK*64
  199.  
  200.  
  201. static char *
  202. sbrk_l(inc)
  203. register unsigned int inc;
  204. {
  205.     static char pool[NPOOL];
  206.     static char *pt = pool+NPOOL;
  207.     static char *pp = pool;
  208.     char *p;
  209.  
  210.     inc += inc % BLOCK;
  211.     if (pp+inc>=pt) {
  212.         return((char *)-1);
  213.     }
  214.     p = pp;
  215.     pp += inc;
  216.     return(p);
  217. }
  218.