/* @(#)qalloc.h 9.3 88/01/19	 */

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc. 
 */

/*-
	Quick memory allocation/deallocation

	qualloc.h, Wed Jul 31 09:08:54 1985


 */

/*-This module defines a number of routines and macros to perform blazingly
   fast memory allocation and deallocation.  The exported routines are:

	QALLOC(p, s, c)	Sets p to point to a block of size s.  c is the
			type of block for pointer casting purposes.  Expanded
			inline, generates particularly good code when s is a
			constant.
	qalloc(s)	returns a pointer to a block of storage of size s.
		        It's a procedure call, so it isn't quite as fast as
		        QALLOC, but it generates less code.
	qtalloc(p, c)	Sets p to point to a block of a size appropriate for
		        p's type.  c is p's type, used for casting.  Expanded 
			inline.
	QFREE(p)	Returns the storage associated with p.  Expanded
		        inline.
	qfree(p)	Returns the storage associated with p.  Procedure
		        call.
	qtfree(p)	Returns the storage associated with p, assuming that
		        the size of the block is "sizeof *p".  Expanded
		        inline.
 */

#ifndef qtfree
#define QAllocStatistics	/* Needs to be on for vmstatus to work */
#ifndef QAllocStatistics
#define QAllocStatistics 0
#define IFVMSTAT(x)
#else
#define IFVMSTAT(x) x
#undef QAllocStatistics
#define QAllocStatistics 1
#endif
extern int  QuickAllocs,
            FastAllocs,
            SlowAllocs,
            QuickFrees,
            SlowFrees,
            SpaceAllocated,
            PoolsCreated,
	    QVMavail,
	    QVMused,
	    QLGused,
	    VMbreak,
            SpaceLost;

#ifndef QAllocDebug
#define QAllocDebug 0
#else
#undef QAllocDebug
#define QAllocDebug 1
#endif

struct QuickFreeblock {
    int         size;
#ifdef sparc
    int		pad;
#endif
    struct QuickFreeblock *next;
};

#ifdef sun
#ifdef mc68000
/*** PORTABILITY NOTE ***/
#define MallocPreceedsBlockWithSize	/* Define this if the malloc routine
					   on your system puts the size of
					   the block immediatly in front of
					   the block -- this way the qalloc
					   package doesn't have to put it's
					   own size field in */
#endif
#endif

#ifdef MallocPreceedsBlockWithSize
#define HasSizePrefix(a,b) (a)		/* Compiles a if MallocPreceedsBlockWithSize
					   is defined, b otherwise */
#else
#define HasSizePrefix(a,b) (b)
#endif

#define NBuckets 1000
#define LogBytesPerBucket 3
#define BytesPerBucket (1<<LogBytesPerBucket)
#define LogBytesPerLargeBucket 6
#define BytesPerLargeBucket (1<<LogBytesPerLargeBucket)
#define LargeBucketThreshhold (4*BytesPerLargeBucket)
#define FirstLargeBucketSlot (LargeBucketThreshhold>>LogBytesPerBucket)
#define LargestBucketedChunk ((2000 +  BytesPerLargeBucket - 1) & ~(BytesPerLargeBucket - 1))
#define QuickSize(s) QuickSizeMap[((s)+(BytesPerBucket-1))>>LogBytesPerBucket]
#define QuickSlot(s) QuickBuckets[(s)>=LargeBucketThreshhold		\
		? (((s)-LargeBucketThreshhold+BytesPerLargeBucket-1)	\
			>>LogBytesPerLargeBucket)+FirstLargeBucketSlot	\
		: ((s)+BytesPerBucket-1)>>LogBytesPerBucket]

/*
 * QUICKMINUSOFFSET is the number of bytes that sub from client pointer to get
 * back to the length.
 */
#ifdef	sparc
#define	QUICKMINUSOFFSET \
	(sizeof(struct QuickFreeblock) - sizeof(struct QuickFreeblock *))
#else
#define	QUICKMINUSOFFSET \
	(sizeof(int))
#endif	/* sparc */

#define QUICKFREEBLOCK(p) ((struct QuickFreeblock *)(((int)p)-QUICKMINUSOFFSET))

extern struct QuickFreeblock *QuickBuckets[];
#ifdef LOGALLOC
#define QLOGFLAG 1
#define IFLOGGING(a) a
#else
#define QLOGFLAG 0
#define IFLOGGING(a)
#endif

#define QALLOC(p, dsize, cast)						\
{									\
    register struct QuickFreeblock **QuickFreeblock;			\
    if ((dsize) > LargestBucketedChunk || *(QuickFreeblock = &QuickSlot(dsize)) == 0)		\
	p = cast (qalloc(dsize));				\
    else {								\
	p = cast (&(*QuickFreeblock)->next);		\
	if (QAllocDebug && &QuickSlot((*QuickFreeblock)->size)!=QuickFreeblock) AllocCorruption(0); \
	IFVMSTAT(QuickAllocs++; QVMused += (*QuickFreeblock)->size);	\
	*QuickFreeblock = (*QuickFreeblock)->next;			\
    }									\
    IFLOGGING(qal_log(p,dsize,__LINE__,__FILE__,'A',"cast"));		\
}

#define QSFREE(p,dsize)							\
{									\
    IFLOGGING(qal_log(p,dsize,__LINE__,__FILE__,'F',0));		\
    if ((dsize) > LargestBucketedChunk) {				\
	free(HasSizePrefix(p,(int)(p)-QUICKMINUSOFFSET));		\
	IFVMSTAT(SlowFrees++;QLGused -= (dsize+3)&~3);			\
    } else {								\
	register struct QuickFreeblock **QuickFreeblock = &QuickSlot(dsize);\
	if (QAllocDebug && &QuickSlot(QUICKFREEBLOCK(p)->size)!=QuickFreeblock) AllocCorruption(1); \
	QUICKFREEBLOCK(p)->next = *QuickFreeblock;			\
	*QuickFreeblock = QUICKFREEBLOCK(p);				\
	IFVMSTAT(QuickFrees++; QVMused -= (*QuickFreeblock)->size);	\
    }									\
}

#define qtalloc(p,c) QALLOC(p,sizeof *p,c)
#define qtfree(p) QSFREE(p,sizeof *p)
#define QFREE(p) QSFREE(p,QUICKFREEBLOCK(p)->size)
#endif