bget.cpp

这是整套横扫千军3D版游戏的源码

    Allocate a buffer of <size> bytes and clear it to all zeroes.  The
    address of the buffer is returned, or NULL if insufficient	memory
    was available to allocate the buffer.

	    void *bgetr(void *buffer, bufsize newsize);

    Reallocate a buffer previously allocated by bget(),  changing  its
    size  to  <newsize>  and  preserving  all  existing data.  NULL is
    returned if insufficient memory is	available  to  reallocate  the
    buffer, in which case the original buffer remains intact.

	    void brel(void *buf);

    Return  the  buffer  <buf>, previously allocated by bget(), to the
    free space pool.

	    void bectl(int (*compact)(bufsize sizereq, int sequence),
		       void *(*acquire)(bufsize size),
		       void (*release)(void *buf),
		       bufsize pool_incr);

    Expansion control: specify functions through which the package may
    compact  storage  (or  take  other	appropriate  action)  when  an
    allocation	request  fails,  and  optionally automatically acquire
    storage for expansion blocks  when	necessary,  and  release  such
    blocks when they become empty.  If <compact> is non-NULL, whenever
    a buffer allocation request fails, the <compact> function will  be
    called with arguments specifying the number of bytes (total buffer
    size,  including  header  overhead)  required   to	 satisfy   the
    allocation request, and a sequence number indicating the number of
    consecutive  calls	on  <compact>  attempting  to	satisfy   this
    allocation	request.   The sequence number is 1 for the first call
    on <compact> for a given allocation  request,  and	increments  on
    subsequent	calls,	permitting  the  <compact>  function  to  take
    increasingly dire measures in an attempt to free up  storage.   If
    the  <compact>  function  returns  a nonzero value, the allocation
    attempt is re-tried.  If <compact> returns 0 (as  it  must	if  it
    isn't  able  to  release  any  space  or add storage to the buffer
    pool), the allocation request fails, which can  trigger  automatic
    pool expansion if the <acquire> argument is non-NULL.  At the time
    the  <compact>  function  is  called,  the	state  of  the	buffer
    allocator  is  identical  to  that	at  the  moment the allocation
    request was made; consequently, the <compact>  function  may  call
    brel(), bpool(), bstats(), and/or directly manipulate  the	buffer
    pool  in  any  manner which would be valid were the application in
    control.  This does not, however, relieve the  <compact>  function
    of the need to ensure that whatever actions it takes do not change
    things   underneath  the  application  that  made  the  allocation
    request.  For example, a <compact> function that released a buffer
    in	the  process  of  being reallocated with bgetr() would lead to
    disaster.  Implementing a safe and effective  <compact>  mechanism
    requires  careful  design of an application's memory architecture,
    and cannot generally be easily retrofitted into existing code.

    If <acquire> is non-NULL, that function will be called whenever an
    allocation	request  fails.  If the <acquire> function succeeds in
    allocating the requested space and returns a pointer  to  the  new
    area,  allocation will proceed using the expanded buffer pool.  If
    <acquire> cannot obtain the requested space, it should return NULL
    and   the	entire	allocation  process  will  fail.   <pool_incr>
    specifies the normal expansion block size.	Providing an <acquire>
    function will cause subsequent bget()  requests  for  buffers  too
    large  to  be  managed in the linked-block scheme (in other words,
    larger than <pool_incr> minus the buffer overhead) to be satisfied
    directly by calls to the <acquire> function.  Automatic release of
    empty pool blocks will occur only if all pool blocks in the system
    are the size given by <pool_incr>.

	    void bstats(bufsize *curalloc, bufsize *totfree,
			bufsize *maxfree, long *nget, long *nrel);

    The amount	of  space  currently  allocated  is  stored  into  the
    variable  pointed  to by <curalloc>.  The total free space (sum of
    all free blocks in the pool) is stored into the  variable  pointed
    to	by  <totfree>, and the size of the largest single block in the
    free space	pool  is  stored  into	the  variable  pointed	to  by
    <maxfree>.	 The  variables  pointed  to  by <nget> and <nrel> are
    filled, respectively, with	the  number  of  successful  (non-NULL
    return) bget() calls and the number of brel() calls.

	    void bstatse(bufsize *pool_incr, long *npool,
			 long *npget, long *nprel,
			 long *ndget, long *ndrel);

    Extended  statistics: The expansion block size will be stored into
    the variable pointed to by <pool_incr>, or the negative thereof if
    automatic  expansion  block  releases are disabled.  The number of
    currently active pool blocks will  be  stored  into  the  variable
    pointed  to  by  <npool>.  The variables pointed to by <npget> and
    <nprel> will be filled with, respectively, the number of expansion
    block   acquisitions   and	releases  which  have  occurred.   The
    variables pointed to by <ndget> and <ndrel> will  be  filled  with
    the  number  of  bget()  and  brel()  calls, respectively, managed
    through blocks directly allocated by the acquisition  and  release
    functions.

	    void bufdump(void *buf);

    The buffer pointed to by <buf> is dumped on standard output.

	    void bpoold(void *pool, int dumpalloc, int dumpfree);

    All buffers in the buffer pool <pool>, previously initialised by a
    call on bpool(), are listed in ascending memory address order.  If
    <dumpalloc> is nonzero, the  contents  of  allocated  buffers  are
    dumped;  if <dumpfree> is nonzero, the contents of free blocks are
    dumped.

	    int bpoolv(void *pool);

    The  named	buffer	pool,  previously  initialised	by  a  call on
    bpool(), is validated for bad pointers, overwritten data, etc.  If
    compiled with NDEBUG not defined, any error generates an assertion
    failure.  Otherwise 1 is returned if the pool is valid,  0	if  an
    error is found.


    BGET CONFIGURATION
    ==================
*/

#define SizeQuant   4		      /* Buffer allocation size quantum:
					 all buffers allocated are a
					 multiple of this size.  This
					 MUST be a power of two. */

#define FreeWipe    1		      /* Wipe free buffers to a guaranteed
					 pattern of garbage to trip up
					 miscreants who attempt to use
					 pointers into released buffers. */

#define BestFit     0		      /* Use a best fit algorithm when
					 searching for space for an
					 allocation request.  This uses
					 memory more efficiently, but
					 allocation will be much slower. */

#define BECtl	    1		      /* Define this symbol to enable the
					 bectl() function for automatic
					 pool space control.  */

#include <stdio.h>

#include <assert.h>
#include <memory.h>

/*  Declare the interface, including the requested buffer size type,
bufsize.  */

#include "bget.h"

#define MemSize     int 	      /* Type for size arguments to memxxx()
functions such as memcmp(). */

/* Queue links */


static bufsize exp_incr = 0;	      /* Expansion block size */
static bufsize pool_len = 0;	      /* 0: no bpool calls have been made
																		-1: not all pool blocks are
																		the same size
																		>0: (common) block size for all
																		bpool calls made so far
																		*/
/*  Minimum allocation quantum: */

#define QLSize	(sizeof(struct qlinks))
#define SizeQ	((SizeQuant > QLSize) ? SizeQuant : QLSize)

#define V   (void)		      /* To denote unwanted returned values */

/* End sentinel: value placed in bsize field of dummy block delimiting
end of pool block.  The most negative number which will  fit  in  a
bufsize, defined in a way that the compiler will accept. */

#define ESent	((bufsize) (-(((1L << (sizeof(bufsize) * 8 - 2)) - 1) * 2) - 2))

/*  BGET  --  Allocate a buffer.  */

BGet::BGet()
{
	freelist.bh.bsize=0;
	freelist.bh.prevfree=0;
	freelist.ql.blink=&freelist;
	freelist.ql.flink=&freelist;

	acqfcn=0;
}

void* BGet::bget(bufsize requested_size)
{
	bufsize size = requested_size;
	struct bfhead *b;
#ifdef BestFit
	struct bfhead *best;
#endif
	void *buf;

	assert(size >= 0);

	if (size < SizeQ) { 	      /* Need at least room for the */
		size = SizeQ;		      /*    queue links.  */
	}
#ifdef SizeQuant
#if SizeQuant > 1
	size = (size + (SizeQuant - 1)) & (~(SizeQuant - 1));
#endif
#endif

	size += sizeof(struct bhead);     /* Add overhead in allocated buffer
																		to size required. */
	b = freelist.ql.flink;
#ifdef BestFit
	best = &freelist;
#endif


	/* Scan the free list searching for the first buffer big enough
	to hold the requested size buffer. */

#ifdef BestFit
	while (b != &freelist) {
		if (b->bh.bsize >= size) {
			if ((best == &freelist) || (b->bh.bsize < best->bh.bsize)) {
				best = b;
			}
		}
		b = b->ql.flink;		  /* Link to next buffer */
	}
	b = best;
#endif /* BestFit */

	while (b != &freelist) {
		if ((bufsize) b->bh.bsize >= size) {

			/* Buffer  is big enough to satisfy  the request.  Allocate it
			to the caller.  We must decide whether the buffer is  large
			enough  to  split  into  the part given to the caller and a
			free buffer that remains on the free list, or  whether  the
			entire  buffer  should  be  removed	from the free list and
			given to the caller in its entirety.   We  only  split  the
			buffer if enough room remains for a header plus the minimum
			quantum of allocation. */

			if ((b->bh.bsize - size) > (SizeQ + (sizeof(struct bhead)))) {
				struct bhead *ba, *bn;

				ba = BH(((char *) b) + (b->bh.bsize - size));
				bn = BH(((char *) ba) + size);
				assert(bn->prevfree == b->bh.bsize);
				/* Subtract size from length of free block. */
				b->bh.bsize -= size;
				/* Link allocated buffer to the previous free buffer. */
				ba->prevfree = b->bh.bsize;
				/* Plug negative size into user buffer. */
				ba->bsize = -(bufsize) size;
				/* Mark buffer after this one not preceded by free block. */
				bn->prevfree = 0;

				buf = (void *) ((((char *) ba) + sizeof(struct bhead)));
				return buf;
			} else {
				struct bhead *ba;

				ba = BH(((char *) b) + b->bh.bsize);
				assert(ba->prevfree == b->bh.bsize);

				/* The buffer isn't big enough to split.  Give  the  whole
				shebang to the caller and remove it from the free list. */

				assert(b->ql.blink->ql.flink == b);
				assert(b->ql.flink->ql.blink == b);
				b->ql.blink->ql.flink = b->ql.flink;
				b->ql.flink->ql.blink = b->ql.blink;

				/* Negate size to mark buffer allocated. */
				b->bh.bsize = -(b->bh.bsize);

				/* Zero the back pointer in the next buffer in memory
				to indicate that this buffer is allocated. */
				ba->prevfree = 0;