+/* Copyright (c) 1979 Regents of the University of California */
+#ifdef debug
+#define ASSERT(p) if(!(p))botch("p");else
+botch(s)
+char *s;
+{
+ printf("assertion botched: %s\n",s);
+ abort();
+}
+#else
+#define ASSERT(p)
+#endif
+
+/* avoid break bug */
+#ifdef pdp11
+#define GRANULE 64
+#else
+#define GRANULE 0
+#endif
+/* C storage allocator
+ * circular first-fit strategy
+ * works with noncontiguous, but monotonically linked, arena
+ * each block is preceded by a ptr to the (pointer of)
+ * the next following block
+ * blocks are exact number of words long
+ * aligned to the data type requirements of ALIGN
+ * pointers to blocks must have BUSY bit 0
+ * bit in ptr is 1 for busy, 0 for idle
+ * gaps in arena are merely noted as busy blocks
+ * last block of arena (pointed to by alloct) is empty and
+ * has a pointer to first
+ * idle blocks are coalesced during space search
+ *
+ * a different implementation may need to redefine
+ * ALIGN, NALIGN, BLOCK, BUSY, INT
+ * where INT is integer type to which a pointer can be cast
+*/
+#define INT int
+#define ALIGN int
+#define NALIGN 1
+#define WORD sizeof(union store)
+#define BLOCK 1024 /* a multiple of WORD*/
+#define BUSY 1
+#define NULL 0
+#define testbusy(p) ((INT)(p)&BUSY)
+#define setbusy(p) (union store *)((INT)(p)|BUSY)
+#define clearbusy(p) (union store *)((INT)(p)&~BUSY)
+
+union store { union store *ptr;
+ ALIGN dummy[NALIGN];
+ int calloc; /*calloc clears an array of integers*/
+};
+
+static union store allocs[2]; /*initial arena*/
+static union store *allocp; /*search ptr*/
+static union store *alloct; /*arena top*/
+static union store *allocx; /*for benefit of realloc*/
+char *sbrk();
+
+char *
+malloc(nbytes)
+unsigned nbytes;
+{
+ register union store *p, *q;
+ register nw;
+ static temp; /*coroutines assume no auto*/
+
+ if(allocs[0].ptr==0) { /*first time*/
+ allocs[0].ptr = setbusy(&allocs[1]);
+ allocs[1].ptr = setbusy(&allocs[0]);
+ alloct = &allocs[1];
+ allocp = &allocs[0];
+ }
+ nw = (nbytes+WORD+WORD-1)/WORD;
+ ASSERT(allocp>=allocs && allocp<=alloct);
+ ASSERT(allock());
+ for(p=allocp; ; ) {
+ for(temp=0; ; ) {
+ if(!testbusy(p->ptr)) {
+ while(!testbusy((q=p->ptr)->ptr)) {
+ ASSERT(q>p&&q<alloct);
+ p->ptr = q->ptr;
+ }
+ if(q>=p+nw && p+nw>=p)
+ goto found;
+ }
+ q = p;
+ p = clearbusy(p->ptr);
+ if(p>q)
+ ASSERT(p<=alloct);
+ else if(q!=alloct || p!=allocs) {
+ ASSERT(q==alloct&&p==allocs);
+ return(NULL);
+ } else if(++temp>1)
+ break;
+ }
+ temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
+ q = (union store *)sbrk(0);
+ if(q+temp+GRANULE < q) {
+ return(NULL);
+ }
+ q = (union store *)sbrk(temp*WORD);
+ if((INT)q == -1) {
+ return(NULL);
+ }
+ ASSERT(q>alloct);
+ alloct->ptr = q;
+ if(q!=alloct+1)
+ alloct->ptr = setbusy(alloct->ptr);
+ alloct = q->ptr = q+temp-1;
+ alloct->ptr = setbusy(allocs);
+ }
+found:
+ allocp = p + nw;
+ ASSERT(allocp<=alloct);
+ if(q>allocp) {
+ allocx = allocp->ptr;
+ allocp->ptr = p->ptr;
+ }
+ p->ptr = setbusy(allocp);
+ return((char *)(p+1));
+}
+
+/* freeing strategy tuned for LIFO allocation
+*/
+free(ap)
+register char *ap;
+{
+ register union store *p = (union store *)ap;
+
+ ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
+ ASSERT(allock());
+ allocp = --p;
+ ASSERT(testbusy(p->ptr));
+ p->ptr = clearbusy(p->ptr);
+ ASSERT(p->ptr > allocp && p->ptr <= alloct);
+}
+
+/* realloc(p, nbytes) reallocates a block obtained from malloc()
+ * and freed since last call of malloc()
+ * to have new size nbytes, and old content
+ * returns new location, or 0 on failure
+*/
+
+char *
+realloc(p, nbytes)
+register union store *p;
+unsigned nbytes;
+{
+ register union store *q;
+ union store *s, *t;
+ register unsigned nw;
+ unsigned onw;
+
+ if(testbusy(p[-1].ptr))
+ free((char *)p);
+ onw = p[-1].ptr - p;
+ q = (union store *)malloc(nbytes);
+ if(q==NULL || q==p)
+ return((char *)q);
+ s = p;
+ t = q;
+ nw = (nbytes+WORD-1)/WORD;
+ if(nw<onw)
+ onw = nw;
+ while(onw--!=0)
+ *t++ = *s++;
+ if(q<p && q+nw>=p)
+ (q+(q+nw-p))->ptr = allocx;
+ return((char *)q);
+}
+
+#ifdef debug
+allock()
+{
+#ifdef longdebug
+ register union store *p;
+ int x;
+ x = 0;
+ for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
+ if(p==allocp)
+ x++;
+ }
+ ASSERT(p==alloct);
+ return(x==1|p==allocp);
+#else
+ return(1);
+#endif
+}
+#endif
projects / unix-history / commitdiff