![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 41BSD / cmd / csh|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 41BSD / cmd / csh |
1.1 ! root 1: static char *sccsid = "@(#)malloc.c 4.1 10/9/80"; ! 2: ! 3: #ifdef debug ! 4: #define ASSERT(p) if(!(p))botch("p");else ! 5: botch(s) ! 6: char *s; ! 7: { ! 8: printf("assertion botched: %s\n",s); ! 9: abort(); ! 10: } ! 11: #else ! 12: #define ASSERT(p) ! 13: #endif ! 14: ! 15: /* avoid break bug */ ! 16: #ifdef pdp11 ! 17: #define GRANULE 64 ! 18: #else ! 19: #define GRANULE 0 ! 20: #endif ! 21: /* C storage allocator ! 22: * circular first-fit strategy ! 23: * works with noncontiguous, but monotonically linked, arena ! 24: * each block is preceded by a ptr to the (pointer of) ! 25: * the next following block ! 26: * blocks are exact number of words long ! 27: * aligned to the data type requirements of ALIGN ! 28: * pointers to blocks must have BUSY bit 0 ! 29: * bit in ptr is 1 for busy, 0 for idle ! 30: * gaps in arena are merely noted as busy blocks ! 31: * last block of arena (pointed to by alloct) is empty and ! 32: * has a pointer to first ! 33: * idle blocks are coalesced during space search ! 34: * ! 35: * a different implementation may need to redefine ! 36: * ALIGN, NALIGN, BLOCK, BUSY, INT ! 37: * where INT is integer type to which a pointer can be cast ! 38: */ ! 39: #define INT int ! 40: #define ALIGN int ! 41: #define NALIGN 1 ! 42: #define WORD sizeof(union store) ! 43: #define BLOCK 1024 /* a multiple of WORD*/ ! 44: #define BUSY 1 ! 45: #define NULL 0 ! 46: #define testbusy(p) ((INT)(p)&BUSY) ! 47: #define setbusy(p) (union store *)((INT)(p)|BUSY) ! 48: #define clearbusy(p) (union store *)((INT)(p)&~BUSY) ! 49: ! 50: union store { union store *ptr; ! 51: ALIGN dummy[NALIGN]; ! 52: int calloc; /*calloc clears an array of integers*/ ! 53: }; ! 54: ! 55: static union store allocs[2]; /*initial arena*/ ! 56: static union store *allocp; /*search ptr*/ ! 57: static union store *alloct; /*arena top*/ ! 58: static union store *allocx; /*for benefit of realloc*/ ! 59: char *sbrk(); ! 60: ! 61: char * ! 62: malloc(nbytes) ! 63: unsigned nbytes; ! 64: { ! 65: register union store *p, *q; ! 66: register nw; ! 67: static temp; /*coroutines assume no auto*/ ! 68: ! 69: if(allocs[0].ptr==0) { /*first time*/ ! 70: allocs[0].ptr = setbusy(&allocs[1]); ! 71: allocs[1].ptr = setbusy(&allocs[0]); ! 72: alloct = &allocs[1]; ! 73: allocp = &allocs[0]; ! 74: } ! 75: nw = (nbytes+WORD+WORD-1)/WORD; ! 76: ASSERT(allocp>=allocs && allocp<=alloct); ! 77: ASSERT(allock()); ! 78: for(p=allocp; ; ) { ! 79: for(temp=0; ; ) { ! 80: if(!testbusy(p->ptr)) { ! 81: while(!testbusy((q=p->ptr)->ptr)) { ! 82: ASSERT(q>p&&q<alloct); ! 83: p->ptr = q->ptr; ! 84: } ! 85: if(q>=p+nw && p+nw>=p) ! 86: goto found; ! 87: } ! 88: q = p; ! 89: p = clearbusy(p->ptr); ! 90: if(p>q) ! 91: ASSERT(p<=alloct); ! 92: else if(q!=alloct || p!=allocs) { ! 93: ASSERT(q==alloct&&p==allocs); ! 94: return(NULL); ! 95: } else if(++temp>1) ! 96: break; ! 97: } ! 98: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD); ! 99: q = (union store *)sbrk(0); ! 100: if(q+temp+GRANULE < q) { ! 101: return(NULL); ! 102: } ! 103: q = (union store *)sbrk(temp*WORD); ! 104: if((INT)q == -1) { ! 105: return(NULL); ! 106: } ! 107: ASSERT(q>alloct); ! 108: alloct->ptr = q; ! 109: if(q!=alloct+1) ! 110: alloct->ptr = setbusy(alloct->ptr); ! 111: alloct = q->ptr = q+temp-1; ! 112: alloct->ptr = setbusy(allocs); ! 113: } ! 114: found: ! 115: allocp = p + nw; ! 116: ASSERT(allocp<=alloct); ! 117: if(q>allocp) { ! 118: allocx = allocp->ptr; ! 119: allocp->ptr = p->ptr; ! 120: } ! 121: p->ptr = setbusy(allocp); ! 122: return((char *)(p+1)); ! 123: } ! 124: ! 125: /* freeing strategy tuned for LIFO allocation ! 126: */ ! 127: free(ap) ! 128: register char *ap; ! 129: { ! 130: register union store *p = (union store *)ap; ! 131: ! 132: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct); ! 133: ASSERT(allock()); ! 134: allocp = --p; ! 135: ASSERT(testbusy(p->ptr)); ! 136: p->ptr = clearbusy(p->ptr); ! 137: ASSERT(p->ptr > allocp && p->ptr <= alloct); ! 138: } ! 139: ! 140: /* realloc(p, nbytes) reallocates a block obtained from malloc() ! 141: * and freed since last call of malloc() ! 142: * to have new size nbytes, and old content ! 143: * returns new location, or 0 on failure ! 144: */ ! 145: ! 146: char * ! 147: realloc(p, nbytes) ! 148: register union store *p; ! 149: unsigned nbytes; ! 150: { ! 151: register union store *q; ! 152: union store *s, *t; ! 153: register unsigned nw; ! 154: unsigned onw; ! 155: ! 156: if(testbusy(p[-1].ptr)) ! 157: free((char *)p); ! 158: onw = p[-1].ptr - p; ! 159: q = (union store *)malloc(nbytes); ! 160: if(q==NULL || q==p) ! 161: return((char *)q); ! 162: s = p; ! 163: t = q; ! 164: nw = (nbytes+WORD-1)/WORD; ! 165: if(nw<onw) ! 166: onw = nw; ! 167: while(onw--!=0) ! 168: *t++ = *s++; ! 169: if(q<p && q+nw>=p) ! 170: (q+(q+nw-p))->ptr = allocx; ! 171: return((char *)q); ! 172: } ! 173: ! 174: #ifdef debug ! 175: allock() ! 176: { ! 177: #ifdef longdebug ! 178: register union store *p; ! 179: int x; ! 180: x = 0; ! 181: for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) { ! 182: if(p==allocp) ! 183: x++; ! 184: } ! 185: ASSERT(p==alloct); ! 186: return(x==1|p==allocp); ! 187: #else ! 188: return(1); ! 189: #endif ! 190: } ! 191: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.