bget.doc

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

                      BGET  --  Memory Allocator
                      ==========================

                            by John Walker
                         [e-mail]
                       http://www.fourmilab.ch/

BGET  is  a  comprehensive  memory  allocation  package  which is easily
configured to the needs of an application.  BGET is  efficient  in  both
the  time  needed  to  allocate  and  release  buffers and in the memory
overhead  required  for  buffer  pool  management.    It   automatically
consolidates  contiguous  space  to  minimise  fragmentation.   BGET  is
configured by compile-time definitions, Major options include:

    *   A  built-in  test  program  to  exercise  BGET   and
        demonstrate how the various functions are used.

    *   Allocation  by  either the "first fit" or "best fit"
        method.

    *   Wiping buffers at release time to catch  code  which
        references previously released storage.

    *   Built-in  routines to dump individual buffers or the
        entire buffer pool.

    *   Retrieval of allocation and pool size statistics.

    *   Quantisation of buffer sizes to a power  of  two  to
        satisfy hardware alignment constraints.

    *   Automatic  pool compaction, growth, and shrinkage by
        means of call-backs to user defined functions.

Applications  of  BGET  can  range  from storage management in ROM-based
embedded programs to providing the framework upon which  a  multitasking
system   incorporating   garbage   collection   is   constructed.   BGET
incorporates  extensive  internal   consistency   checking   using   the
<assert.h>  mechanism;  all  these checks can be turned off by compiling
with NDEBUG defined, yielding a version of BGET with  minimal  size  and
maximum speed.

The basic algorithm underlying BGET has withstood the test of time; more
than 25 years have passed since the first implementation of  this  code.
And  yet,  it is substantially more efficient than the native allocation
schemes of many operating systems: the Macintosh and  Microsoft  Windows
to  name  two,  on which programs have obtained substantial speed-ups by
layering BGET as an application level memory manager atop the underlying
system's.

BGET  has  been  implemented on the largest mainframes and the lowest of
microprocessors.  It has served as the core for  multitasking  operating
systems,  multi-thread  applications,  embedded software in data network
switching processors, and a host  of  C  programs.   And  while  it  has
accreted  flexibility  and additional options over the years, it remains
fast, memory efficient,  portable,  and  easy  to  integrate  into  your
program.


BGET IMPLEMENTATION ASSUMPTIONS
===============================

BGET  is  written  in  as portable a dialect of C as possible.  The only
fundamental assumption about the  underlying  hardware  architecture  is
that  memory  is allocated is a linear array which can be addressed as a
vector of C "char" objects.  On segmented address  space  architectures,
this generally means that BGET should be used to allocate storage within
a single segment (although some compilers simulate linear address spaces
on  segmented  architectures).   On  segmented architectures, then, BGET
buffer pools may not be larger than a segment, but since BGET allows any
number  of separate buffer pools, there is no limit on the total storage
which can be managed, only on the largest individual object which can be
allocated.   Machines  with  a  linear address architecture, such as the
VAX, 680x0, Sparc, MIPS, or the Intel 80386 and above  in  native  mode,
may use BGET without restriction.


GETTING STARTED WITH BGET
=========================

Although  BGET  can  be configured in a multitude of fashions, there are
three basic ways of working with BGET.  The  functions  mentioned  below
are  documented  in  the  following  section.  Please excuse the forward
references which are made in the interest  of  providing  a  roadmap  to
guide you to the BGET functions you're likely to need.

Embedded Applications
---------------------

Embedded applications typically have a fixed area of memory dedicated to
buffer  allocation  (often in a separate RAM address space distinct from
the ROM that contains the executable code).  To  use  BGET  in  such  an
environment,  simply  call  bpool() with the start address and length of
the buffer pool area in RAM,  then  allocate  buffers  with  bget()  and
release  them  with brel().  Embedded applications with very limited RAM
but abundant CPU speed may  benefit  by  configuring  BGET  for  BestFit
allocation (which is usually not worth it in other environments).

Malloc() Emulation
------------------

If  the  C  library  malloc()  function is too slow, not present in your
development environment (for example, an a native Windows  or  Macintosh
program),  or  otherwise  unsuitable,  you  can  replace  it  with BGET.
Initially  define  a  buffer  pool   of   an   appropriate   size   with
bpool()--usually  obtained  by  making  a call to the operating system's
low-level memory allocator.  Then allocate buffers with bget(), bgetz(),
and  bgetr()  (the last two permit the allocation of buffers initialised
to  zero  and  [inefficient]  re-allocation  of  existing  buffers   for
compatibility  with  C  library  functions).  Release buffers by calling
brel().  If a buffer allocation request fails, obtain more storage  from
the  underlying  operating  system, add it to the buffer pool by another
call to bpool(), and continue execution.

Automatic Storage Management
----------------------------

You can use  BGET  as  your  application's  native  memory  manager  and
implement  automatic storage pool expansion, contraction, and optionally
application-specific memory compaction by compiling BGET with the  BECtl
variable  defined,  then  calling  bectl()  and  supplying functions for
storage compaction, acquisition, and release, as well as a standard pool
expansion  increment.   All of these functions are optional (although it
doesn't make much  sense  to  provide  a  release  function  without  an
acquisition function, does it?).  Once the call-back functions have been
defined with bectl(), you simply use bget() and brel() to  allocate  and
release  storage  as before.  You can supply an initial buffer pool with
bpool() or rely on automatic allocation  to  acquire  the  entire  pool.
When  a  call  on  bget()  cannot  be  satisfied, BGET first checks if a
compaction function has been supplied.  If so, it is  called  (with  the
space  required  to satisfy the allocation request and a sequence number
to allow the  compaction  routine  to  be  called  successively  without
looping).   If  the  compaction function is able to free any storage (it
needn't know whether the storage it freed was adequate) it should return
a  nonzero  value, whereupon BGET will retry the allocation request and,
if  it  fails  again,  call  the  compaction  function  again  with  the
next-higher sequence number.

If  the  compaction  function  returns  zero, indicating failure to free
space, or no compaction function is defined, BGET next tests  whether  a
non-NULL  allocation  function  was  supplied  to  bectl().  If so, that
function is called  with  an  argument  indicating  how  many  bytes  of
additional space are required.  This will be the standard pool expansion
increment supplied in the call to bectl()  unless  the  original  bget()
call  requested  a  buffer  larger  than  this;  buffers larger than the
standard pool block can be managed "off the books" by BGET in this mode.
If the allocation function succeeds in obtaining the storage, it returns
a pointer to the new block and BGET  expands  the  buffer  pool;  if  it
fails,  the allocation request fails and returns NULL to the caller.  If
a non-NULL release function is supplied, expansion blocks  which  become
totally  empty  are  released  to  the global free pool by passing their
addresses to the release function.

Equipped with appropriate allocation, release, and compaction functions,
BGET  can  be  used  as  part  of  very  sophisticated memory management
strategies, including garbage collection.  (Note, however, that BGET  is
*not*  a  garbage collector by itself, and that developing such a system
requires much additional logic and careful design of  the  application's
memory allocation strategy.)


BGET FUNCTION DESCRIPTIONS
==========================

Functions implemented by BGET  (some  are  enabled  by  certain  of  the
optional settings below):

        void bpool(void *buffer, bufsize len);