source: buchla-68k/orig/lib/INCLUDE/MALLOC.H@ 9519422

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * MALLOC.H -- header file for A "smarter" malloc
 * Version 4 -- 1988-05-03 -- USENET
 *
 * A  "smarter" malloc          Original code by William L. Sebok
 *
 * Modified for Aztec C-II by D.N. Lynx Crowe
 *
 * 1986-12-30   Made long constants explicit as fix for bug in compiler
 * 1987-01-01   Made long constants into variables to work around compiler bug
 * 1988-05-03   Modified to work on the Atari under GEMDOS
 * 1988-05-03   Added define of SMARTMAL so we know what we've got
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *      Algorithm:
 *      Assign to each area an index "n". This is currently proportional to
 *      the log 2 of size of the area rounded down to the nearest integer.
 *      Then all free areas of storage whose length have the same index n are
 *      organized into a chain with other free areas of index n (the "bucket"
 *      chain). A request for allocation of storage first searches the list of
 *      free memory.  The search starts at the bucket chain of index equal to
 *      that of the storage request, continuing to higher index bucket chains
 *      if the first attempt fails.
 *      If the search fails then new memory is allocated.  Only the amount of
 *      new memory needed is allocated.  Any old free memory left after an
 *      allocation is returned to the free list.
 *
 *      All memory areas (free or busy) handled by malloc are also chained
 *      sequentially by increasing address (the adjacency chain).  When memory
 *      is freed it is merged with adjacent free areas, if any.  If a free area
 *      of memory ends at the end of memory (i.e. at the break), and if the
 *      variable "endfree" is non-zero, then the break is contracted, freeing
 *      the memory back to the system.
 *
 *      Notes:
 *              ov_len field includes sizeof(struct overhead)
 *              adjacency chain includes all memory, allocated plus free.
 */

/* **************************** Machine Dependencies ******************** */

/* the following items may need to be configured for a particular machine */

#define void    int     /* Aztec C doesn't have voids */

/* alignment requirement for machine (in bytes) */

#define NALIGN  2

/* size of an integer large enough to hold a character pointer */

typedef long    Size;

/*
 * CURBRK returns the value of the current system break, i.e., the system's
 * idea of the highest legal address in the data area.  It is defined as
 * a macro for the benefit of systems that have provided an easier way to
 * obtain this number (such as in an external variable)
 */

#ifndef CURBRK

#define CURBRK  sbrk(0)
extern char *sbrk();

#else  CURBRK

#if     CURBRK == curbrk
extern Size curbrk;
#endif

#endif CURBRK

/*
 * note that it is assumed that CURBRK remembers the last requested break to
 * the nearest byte (or at least the nearest word) rather than the nearest page
 * boundary.  If this is not true then the following BRK macro should be
 * replaced with one that remembers the break to within word-size accuracy.
 */

#ifndef BRK

#define BRK(x)  brk(x)
extern char *brk();

#endif  BRK

/*
        define NBUCKETS as 18 for big machines, 10 for small ones
        and adjust the definitions of mlsizes[] and buckets[], below.
*/

#define NBUCKETS        18

/* ***************** END of machine dependent portion ******************* */

struct qelem {

        struct qelem *q_forw;
        struct qelem *q_back;
};

struct overhead {

        struct qelem    ov_adj;         /* adjacency chain pointers */ 
        struct qelem    ov_buk;         /* bucket chain pointers */
        long            ov_magic;       /* MAGIC number */
        Size            ov_len;         /* length of the area in bytes */
};

/*
 * The following macros depend on the order of the elements in struct overhead
 */

#define TOADJ(p)        ((struct qelem *)(p))
#define FROMADJ(p)      ((struct overhead *)(p))
#define FROMBUK(p)      ((struct overhead *)( (char *)p - sizeof(struct qelem)))
#define TOBUK(p)        ((struct qelem *)( (char *)p + sizeof(struct qelem)))

#define XM_FREE 0x548A934CL             /* MAGIC for free blocks */
#define XM_BUSY 0xC139569AL             /* MAGIC for busy blocks */

#define M_FREE  m_free
#define M_BUSY  m_busy

#ifdef MALLOC

/*
 * return to the system memory freed adjacent to the break 
 * default is Off
 */

char endfree = 0;               /* WARNING -- this isn't PROMable */

/*
 * M_FREE and M_BUSY used to be MAGIC_FREE and MAGIC_BUSY
 * m_free and m_busy were added to work around a BUG in Aztec CII
 */

long m_free = XM_FREE;
long m_busy = XM_BUSY;

/* head of adjacency chain */

struct qelem adjhead = { &adjhead, &adjhead };

/* *************** More Machine Dependencies *********************** */

/* sizes of buckets currently proportional to log 2() */
/* must match NBUCKETS, above */

Size mlsizes[] = {0, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384,

        /* trim here if on a small machine */

        32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304};

/* head of bucket chains */
/* must match NBUCKETS, above */

struct qelem buckets[NBUCKETS] = {

        &buckets[0],  &buckets[0],      &buckets[1],  &buckets[1],
        &buckets[2],  &buckets[2],      &buckets[3],  &buckets[3],
        &buckets[4],  &buckets[4],      &buckets[5],  &buckets[5],
        &buckets[6],  &buckets[6],      &buckets[7],  &buckets[7],
        &buckets[8],  &buckets[8],      &buckets[9],  &buckets[9],

        /* trim here if on a small machine */

        &buckets[10], &buckets[10],     &buckets[11], &buckets[11],
        &buckets[12], &buckets[12],     &buckets[13], &buckets[13],
        &buckets[14], &buckets[14],     &buckets[15], &buckets[15],
        &buckets[16], &buckets[16],     &buckets[17], &buckets[17]
};

/* ********************* End of Machine Dependencies ********************* */

void (*mlabort)() = {0};

#else

extern char endfree;
extern struct qelem adjhead, buckets[NBUCKETS];
extern Size mlsizes[NBUCKETS];
extern void (*mlabort)();
extern long m_free, m_busy;

#endif

extern void insque(), remque();
extern void free(), mllcerr();
extern char *malloc(), *realloc();

#ifdef debug

# define ASSERT(p,q)    if (!(p)) mllcerr(q)

#else

# define ASSERT(p,q)

#endif

#define SMARTMAL