/*LINTLIBRARY*/

#ifndef lint
#ifndef NOID
#endif /* !NOID */
#endif /* !lint */

#ifdef vax

struct qelem *	_p;
struct qelem *	_q;

#define remque(p)	{ _p = (p); asm("remque	*__p,r0"); }
#define insque(p, q)	{ _p = (p); _q = (q) ; asm("insque	*__p,*__q"); }

#endif /* vax */

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * A  "smarter" malloc				William L. Sebok
 *			Then modified by Arthur David Olsen
 *			MALLOCTRACE added by Mark Brader
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *	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_length field includes sizeof(struct overhead)
 *		adjacency chain includes all memory, allocated plus free.
 */

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

/* alignment requirement for machine (in bytes) */
#define NALIGN	4

/* 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 void *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 void *brk();
#endif /* !BRK */

/* END of machine dependent portion */

#ifdef	MALLOCTRACE
/* Tracing of all calls to malloc, free, realloc... see ./TRACE_README */

enum _malstate {S_INITIAL, S_IN_STDIO, S_IN_REALLOC, S_TRACING};

#define	TRACEFILE	"malloc.out"	/* default output filename */

#undef	MALLOCTRACE		/* so the next line means what it says! */
#define	TRACEENVVAR	"MALLOCTRACE"	/* where to read nondefault name */
#define	MALLOCTRACE		/* cancel #undef! */

#define	TRACEBUFVAR	"MALLOCTRACEBUF"	/* No-flush request */
#endif

#define	MAGIC_FREE	0x548a934c
#define	MAGIC_BUSY	0xc139569a

#define NBUCKETS	18

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;
	Size		ov_length;
};

/*
 * 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)))

/*
 * return to the system memory freed adjacent to the break 
 * default is Off
 */
extern char endfree;

/* head of adjacency chain */
extern struct qelem adjhead;

/* head of bucket chains */
extern struct qelem buckets[NBUCKETS];
extern struct qelem *	hifreebp;

extern void (*mlabort)();

#ifndef vax
extern void insque(), remque();
#endif
extern void mllcerr();
extern char *malloc(), *realloc();

#ifdef debug
# define ASSERT(p,q)	if (!(p)) mllcerr(q)
#else
# define ASSERT(p,q)	((void)(p),(void)(q))
#endif