![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to omalloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / libc / gen|
Return to omalloc.c CVS log | Up to [Research Unix] / researchv10no / libc / gen |
1.1 ! root 1: #ifdef debug ! 2: #define ASSERT(p) if(!(p))botch("p");else ! 3: botch(s) ! 4: char *s; ! 5: { ! 6: printf("assertion botched: %s\n",s); ! 7: abort(); ! 8: } ! 9: #else ! 10: #define ASSERT(p) ! 11: #endif ! 12: ! 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 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 ! 36: #define BUSY 1 ! 37: #define NULL 0 ! 38: #define testbusy(p) ((INT)(p)&BUSY) ! 39: #define setbusy(p) (union store *)((INT)(p)|BUSY) ! 40: #define clearbusy(p) (union store *)((INT)(p)&~BUSY) ! 41: ! 42: union store { ! 43: union store *ptr; ! 44: ALIGN dummy[NALIGN]; ! 45: int calloc; /*calloc clears an array of integers*/ ! 46: }; ! 47: ! 48: static union store alloca; /* initial arena */ ! 49: static union store *allocb = &alloca; /*arena base*/ ! 50: static union store *allocp = &alloca; /*search ptr*/ ! 51: static union store *allocx; /*for benefit of realloc*/ ! 52: extern char *sbrk(); ! 53: ! 54: char * ! 55: malloc(nbytes) ! 56: unsigned nbytes; ! 57: { ! 58: register union store *p, *q; ! 59: register nw; ! 60: register temp; ! 61: register union store *r = 0; ! 62: ! 63: nw = (nbytes+WORD+WORD-1)/WORD; ! 64: ASSERT(allock(allocp)); ! 65: for(; ; ) { /* done at most twice */ ! 66: p = allocp; ! 67: if(alloca.ptr!=0) /*C can't initialize union*/ ! 68: for(temp=0; ; ) { ! 69: if(!testbusy(p->ptr)) { ! 70: while(!testbusy((q=p->ptr)->ptr)) { ! 71: ASSERT(q>p); ! 72: p->ptr = q->ptr; ! 73: allocp = p; ! 74: } ! 75: if(q>=p+nw && p+nw>=p) ! 76: goto found; ! 77: r = p; ! 78: } ! 79: q = p; ! 80: p = clearbusy(p->ptr); ! 81: if(p <= q) { ! 82: ASSERT(p==allocb); ! 83: if(p != allocb) ! 84: return(NULL); ! 85: if(++temp>1) ! 86: break; ! 87: } ! 88: } ! 89: temp = nw; ! 90: p = (union store *)sbrk(0); ! 91: if (r && !testbusy(r->ptr) && r->ptr + 1 == p) ! 92: temp -= p - r - 1; ! 93: temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD); ! 94: if(p+temp <= p) ! 95: return(NULL); ! 96: for(; ; ) { ! 97: q = (union store *)sbrk(temp*WORD); ! 98: if((INT)q != -1) ! 99: break; ! 100: temp -= (temp-nw)/2; ! 101: if(temp-nw <= 1) ! 102: return(NULL); ! 103: } ! 104: ialloc((char *)q, (unsigned)temp*WORD); ! 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(ap) ! 119: char *ap; ! 120: { ! 121: register union store *p = (union store *)ap; ! 122: ! 123: allocp = --p; ! 124: ASSERT(allock(allocp)); ! 125: ASSERT(testbusy(p->ptr)); ! 126: p->ptr = clearbusy(p->ptr); ! 127: ASSERT(p->ptr > allocp); ! 128: } ! 129: ! 130: /* ialloc(q, nbytes) inserts a block that did not come ! 131: * from malloc into the arena ! 132: * ! 133: * q points to new block ! 134: * r points to last of new block ! 135: * p points to last cell of arena before new block ! 136: * s points to first cell of arena after new block ! 137: */ ! 138: ialloc(qq, nbytes) ! 139: char *qq; ! 140: unsigned nbytes; ! 141: { ! 142: register union store *p, *q, *s; ! 143: union store *r; ! 144: ! 145: q = (union store *)qq; ! 146: r = q + (nbytes/WORD) - 1; ! 147: q->ptr = r; ! 148: if(alloca.ptr==0) /*C can't initialize union*/ ! 149: alloca.ptr = &alloca; ! 150: for(p=allocb; ; p=s) { ! 151: s = clearbusy(p->ptr); ! 152: if(s==allocb) ! 153: break; ! 154: ASSERT(s>p); ! 155: if(s>r) { ! 156: if(p<q) ! 157: break; ! 158: else ! 159: ASSERT(p>r); ! 160: } ! 161: } ! 162: p->ptr = q==p+1? q: setbusy(q); ! 163: r->ptr = s==r+1? s: setbusy(s); ! 164: if(allocb > q) ! 165: allocb = q; ! 166: allocp = allocb; ! 167: } ! 168: ! 169: /* realloc(p, nbytes) reallocates a block obtained from malloc() ! 170: * and freed since last call of malloc() ! 171: * to have new size nbytes, and old content ! 172: * returns new location, or 0 on failure ! 173: */ ! 174: ! 175: char * ! 176: realloc(pp, nbytes) ! 177: char *pp; ! 178: unsigned nbytes; ! 179: { ! 180: register union store *q; ! 181: register union store *p = (union store *)pp; ! 182: union store *s, *t; ! 183: register unsigned nw; ! 184: unsigned onw; ! 185: ! 186: ASSERT(allock(p-1)); ! 187: if(testbusy(p[-1].ptr)) ! 188: free((char *)p); ! 189: onw = p[-1].ptr - p; ! 190: q = (union store *)malloc(nbytes); ! 191: if(q==NULL || q==p) ! 192: return((char *)q); ! 193: ASSERT(q<p||q>p[-1].ptr); ! 194: s = p; ! 195: t = q; ! 196: nw = (nbytes+WORD-1)/WORD; ! 197: if(nw<onw) ! 198: onw = nw; ! 199: while(onw--!=0) ! 200: *t++ = *s++; ! 201: ASSERT(clearbusy(q[-1].ptr)-q==nw); ! 202: if(q<p && q+nw>=p) ! 203: (q+(q+nw-p))->ptr = allocx; ! 204: ASSERT(allock(q-1)); ! 205: return((char *)q); ! 206: } ! 207: ! 208: #ifdef debug ! 209: allock(q) ! 210: union store *q; ! 211: { ! 212: #ifdef longdebug ! 213: register union store *p, *r; ! 214: int x; ! 215: x = 0; ! 216: p = allocb; ! 217: if(alloca.ptr==0) ! 218: return(1); ! 219: for( ; (r=clearbusy(p->ptr)) > p; p=r) { ! 220: if(p==q) ! 221: x++; ! 222: } ! 223: return(r==allocb&(x==1|p==q)); ! 224: #else ! 225: return(q>=allocb); ! 226: #endif ! 227: } ! 228: #endif ! 229:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.