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