BSD 3 development

Work on file usr/src/cmd/csh/alloc.c

Synthesized-from: 3bsd

diff --git a/usr/src/cmd/csh/alloc.c b/usr/src/cmd/csh/alloc.c
new file mode 100644 (file)
index 0000000..18a5589
--- /dev/null
+++ b/usr/src/cmd/csh/alloc.c
@@ -0,0 +1,216 @@
+/* Copyright (c) 1979 Regents of the University of California */
+#include "sh.local.h"
+#ifdef debug
+#define ASSERT(p) if(!(p))botch("p");else
+botch(s)
+char *s;
+{
+       printf("assertion botched: %s\n",s);
+       chdir("/usr/bill/cshcore");
+       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)
+#ifdef V6
+               copy(t++, s++, sizeof (*t));
+#else
+               *t++ = *s++;
+#endif
+       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
+
+#ifdef debug
+showall(v)
+       char **v;
+{
+       register union store *p, *q;
+       int used = 0, free = 0, i;
+
+       for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) {
+               q = clearbusy(p->ptr);
+               if (v[1])
+               printf("%6o %5d %s\n", p,
+                   ((unsigned) q - (unsigned) p),
+                   testbusy(p->ptr) ? "BUSY" : "FREE");
+               i = ((unsigned) q - (unsigned) p);
+               if (testbusy(p->ptr)) used += i; else free += i;
+       }
+       printf("%d used, %d free, %l end\n", used, free, clearbusy(alloct));
+}
+#endif