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