From: "A.Appleyard" <A DOT APPLEYARD AT fs2 DOT mt DOT umist DOT ac DOT uk>
Organization: Materials Science Centre
To: DJGPP AT DELORIE DOT COM
Date: Mon, 17 Mar 1997 10:16:16 GMT
Subject: malloc
Message-ID: <8FB96F09E8@fs2.mt.umist.ac.uk>

Re my messages about malloc(), here is a version of malloc() free() realloc()
which I made by altering djgpp\src\libc\ansi\stdlib\malloc.c; I have tested it
quickly and it seems to work. See the comments `/*******' herinunder.
  ..................................................................
#include <string.h>
#include <unistd.h>
#define getpagesize() 4096
typedef unsigned char byte;
static char*nextf[31]; /* pointers to chains of free blocks */
static int pagesize=0; /* page size */
#define OW 4 /* size of block-chaining overheads */
/* The first 4 bytes of a block contain:- */
/* while the block is free, a pointer to the next block in that bucket */
/* while the block is allocated, -17, then bucket number, then 2 spare bytes */
/*-----*//* allocate more memory to the indicated bucket. */
static void morecore(int bucket) {int size,amt,nblocks; char*op;
if((size=8<<bucket)<=0) return; /* how many bytes per block */
if(size<pagesize) nblocks=(amt=pagesize)/size; /* pageful of blocks that size */
else {amt=size; nblocks=1;} /* one block, of (size/pagesize) pages */
  /****** If size>=pagesize, the standard form gets (size/pagesize + 1) */
  /****** pages here. What is the extra unused page for? */
op=(char*)sbrk(amt); /* get size*nblocks bytes */
if((int)op==-1) return; /* if no more room */
nextf[bucket]=op; /* chain in the new blocks */
while(--nblocks>0) {*(char**)op=op+size; op+=size;}
*(char**)op=0;}
/*-----*/
void*malloc(long N) {char*op; long bucket,n,amt; if(!N) return 0;
if(pagesize==0) {
/* First time malloc is called, move sbrk up to OW less than a page boundary */
    for(n=0;n<31;n++) nextf[n]=0; pagesize=n=getpagesize(); op=(char*)sbrk(0);
    n=n-OW-((int)op&(n-1)); if(n<0) n+=pagesize;
    if(n) if(sbrk(n)==(char*)-1) return 0;}
{register long i=N+OW-1; i|=i>>16; i|=i>>8; i|=i>>4; i|=i>>2; i|=i>>1; amt=i+1;}
/* amt = i+OW rounded up to next power of 2 */
bucket=ffs(amt)-3; /* 1<<ffs(i) == the lowest order 1-bit in i */
/****** finding which bucket now runs quicker */
if(!(op=nextf[bucket])) {morecore(bucket); if(!(op=nextf[bucket])) return 0;}
/* remove from linked list */
nextf[bucket]=*(char**)op; op[0]=-17; op[1]=bucket; return op+OW;}
/*-----*/
void free(void*cp) {int bucket; char*op; if(!cp) return; op=(char*)cp-OW;
if(op[0]!=-17) return; /* this block was not got by malloc() */
bucket=op[1]; *(char**)op=nextf[bucket]; nextf[bucket]=op;}
/*-----*/
void*realloc(void*Old,long N) {long oldsize,n; char*op; void*New;
if(!Old) return malloc(N); op=(char*)Old-OW; if(op[0]!=-17) return 0;
oldsize=8<<op[1]; if(N+OW<=oldsize) if(N+OW>oldsize/2) return Old;
free(Old); if(!(New=malloc(N))) return 0; /* keep old block if same size */
n=N<oldsize-OW?N:oldsize-OW; if(Old!=New) memcpy(New,Old,n); return New;}
/*-----*/