The R Project SVN R

/*

  This is a version (aka dlmalloc) of malloc/free/realloc written by

  Doug Lea and released to the public domain.  Use, modify, and

  redistribute this code without permission or acknowledgement in any

  way you wish.  Send questions, comments, complaints, performance

  data, etc to dl@cs.oswego.edu

* VERSION 2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)

   Note: There may be an updated version of this malloc obtainable at

           ftp://gee.cs.oswego.edu/pub/misc/malloc.c

         Check before installing!

* Quickstart

  This library is all in one file to simplify the most common usage:

  ftp it, compile it (-O), and link it into another program. All

  of the compile-time options default to reasonable values for use on

  most unix platforms. Compile -DWIN32 for reasonable defaults on windows.

  You might later want to step through various compile-time and dynamic

  tuning options.

  For convenience, an include file for code using this malloc is at:

     ftp://gee.cs.oswego.edu/pub/misc/malloc-2.7.1.h

  You don't really need this .h file unless you call functions not

  defined in your system include files.  The .h file contains only the

  excerpts from this file needed for using this malloc on ANSI C/C++

  systems, so long as you haven't changed compile-time options about

  naming and tuning parameters.  If you do, then you can create your

  own malloc.h that does include all settings by cutting at the point

  indicated below.

* Why use this malloc?

  This is not the fastest, most space-conserving, most portable, or

  most tunable malloc ever written. However it is among the fastest

  while also being among the most space-conserving, portable and tunable.

  Consistent balance across these factors results in a good general-purpose

  allocator for malloc-intensive programs.

  The main properties of the algorithms are:

  * For large (>= 512 bytes) requests, it is a pure best-fit allocator,

    with ties normally decided via FIFO (i.e. least recently used).

  * For small (<= 64 bytes by default) requests, it is a caching

    allocator, that maintains pools of quickly recycled chunks.

  * In between, and for combinations of large and small requests, it does

    the best it can trying to meet both goals at once.

  * For very large requests (>= 128KB by default), it relies on system

    memory mapping facilities, if supported.

  For a longer but slightly out of date high-level description, see

     http://gee.cs.oswego.edu/dl/html/malloc.html

  You may already by default be using a C library containing a malloc

  that is  based on some version of this malloc (for example in

  linux). You might still want to use the one in this file in order to

  customize settings or to avoid overheads associated with library

  versions.

* Contents, described in more detail in "description of public routines" below.

  Standard (ANSI/SVID/...)  functions:

    malloc(size_t n);

    calloc(size_t n_elements, size_t element_size);

    free(Void_t* p);

    realloc(Void_t* p, size_t n);

    memalign(size_t alignment, size_t n);

    valloc(size_t n);

    mallinfo()

    mallopt(int parameter_number, int parameter_value)

  Additional functions:

    independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]);

    independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);

    pvalloc(size_t n);

    cfree(Void_t* p);

    malloc_trim(size_t pad);

    malloc_usable_size(Void_t* p);

    malloc_stats();

* Vital statistics:

  Supported pointer representation:       4 or 8 bytes

  Supported size_t  representation:       4 or 8 bytes 

       Note that size_t is allowed to be 4 bytes even if pointers are 8.

       You can adjust this by defining INTERNAL_SIZE_T

  Alignment:                              2 * sizeof(size_t) (default)

       (i.e., 8 byte alignment with 4byte size_t). This suffices for

       nearly all current machines and C compilers. However, you can

       define MALLOC_ALIGNMENT to be wider than this if necessary.

  Minimum overhead per allocated chunk:   4 or 8 bytes

       Each malloced chunk has a hidden word of overhead holding size

       and status information.

  Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)

                          8-byte ptrs:  24/32 bytes (including, 4/8 overhead)

       When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte

       ptrs but 4 byte size) or 24 (for 8/8) additional bytes are

       needed; 4 (8) for a trailing size field and 8 (16) bytes for

       free list pointers. Thus, the minimum allocatable size is

       16/24/32 bytes.

       Even a request for zero bytes (i.e., malloc(0)) returns a

       pointer to something of the minimum allocatable size.

       The maximum overhead wastage (i.e., number of extra bytes

       allocated than were requested in malloc) is less than or equal

       to the minimum size, except for requests >= mmap_threshold that

       are serviced via mmap(), where the worst case wastage is 2 *

       sizeof(size_t) bytes plus the remainder from a system page (the

       minimal mmap unit); typically 4096 or 8192 bytes.

  Maximum allocated size:  4-byte size_t: 2^32 minus about two pages 

                           8-byte size_t: 2^64 minus about two pages

       It is assumed that (possibly signed) size_t values suffice to

       represent chunk sizes. `Possibly signed' is due to the fact

       that `size_t' may be defined on a system as either a signed or

       an unsigned type. The ISO C standard says that it must be

       unsigned, but a few systems are known not to adhere to this.

       Additionally, even when size_t is unsigned, sbrk (which is by

       default used to obtain memory from system) accepts signed

       arguments, and may not be able to handle size_t-wide arguments

       with negative sign bit.  Generally, values that would

       appear as negative after accounting for overhead and alignment

       are supported only via mmap(), which does not have this

       limitation.

       Requests for sizes outside the allowed range will perform an optional

       failure action and then return null. (Requests may also

       also fail because a system is out of memory.)

  Thread-safety: NOT thread-safe unless USE_MALLOC_LOCK defined

       When USE_MALLOC_LOCK is defined, wrappers are created to

       surround every public call with either a pthread mutex or

       a win32 spinlock (depending on WIN32). This is not

       especially fast, and can be a major bottleneck.

       It is designed only to provide minimal protection

       in concurrent environments, and to provide a basis for

       extensions.  If you are using malloc in a concurrent program,

       you would be far better off obtaining ptmalloc, which is

       derived from a version of this malloc, and is well-tuned for

       concurrent programs. (See http://www.malloc.de) Note that

       even when USE_MALLOC_LOCK is defined, you can can guarantee

       full thread-safety only if no threads acquire memory through 

       direct calls to MORECORE or other system-level allocators.

  Compliance: I believe it is compliant with the 1997 Single Unix Specification

       (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably 

       others as well.

* Synopsis of compile-time options:

    People have reported using previous versions of this malloc on all

    versions of Unix, sometimes by tweaking some of the defines

    below. It has been tested most extensively on Solaris and

    Linux. It is also reported to work on WIN32 platforms.

    People also report using it in stand-alone embedded systems.

    The implementation is in straight, hand-tuned ANSI C.  It is not

    at all modular. (Sorry!)  It uses a lot of macros.  To be at all

    usable, this code should be compiled using an optimizing compiler

    (for example gcc -O3) that can simplify expressions and control

    paths. (FAQ: some macros import variables as arguments rather than

    declare locals because people reported that some debuggers

    otherwise get confused.)

    OPTION                     DEFAULT VALUE

    Compilation Environment options:

    __STD_C                    derived from C compiler defines

    WIN32                      NOT defined

    HAVE_MEMCPY                defined

    USE_MEMCPY                 1 if HAVE_MEMCPY is defined

    HAVE_MMAP                  defined as 1 

    MMAP_CLEARS                1

    HAVE_MREMAP                0 unless linux defined

    malloc_getpagesize         derived from system #includes, or 4096 if not

    HAVE_USR_INCLUDE_MALLOC_H  NOT defined

    LACKS_UNISTD_H             NOT defined unless WIN32

    LACKS_SYS_PARAM_H          NOT defined unless WIN32

    LACKS_SYS_MMAN_H           NOT defined unless WIN32

    LACKS_FCNTL_H              NOT defined

    Changing default word sizes:

    INTERNAL_SIZE_T            size_t

    MALLOC_ALIGNMENT           2 * sizeof(INTERNAL_SIZE_T)

    PTR_UINT                   unsigned long

    CHUNK_SIZE_T               unsigned long

    Configuration and functionality options:

    USE_DL_PREFIX              NOT defined

    USE_PUBLIC_MALLOC_WRAPPERS NOT defined

    USE_MALLOC_LOCK            NOT defined

    DEBUG                      NOT defined

    REALLOC_ZERO_BYTES_FREES   NOT defined

    MALLOC_FAILURE_ACTION      errno = ENOMEM, if __STD_C defined, else no-op

    TRIM_FASTBINS              0

    FIRST_SORTED_BIN_SIZE      512

    Options for customizing MORECORE:

    MORECORE                   sbrk

    MORECORE_CONTIGUOUS        1 

    MORECORE_CANNOT_TRIM       NOT defined

    MMAP_AS_MORECORE_SIZE      (1024 * 1024) 

    Tuning options that are also dynamically changeable via mallopt:

    DEFAULT_MXFAST             64

    DEFAULT_TRIM_THRESHOLD     256 * 1024

    DEFAULT_TOP_PAD            0

    DEFAULT_MMAP_THRESHOLD     256 * 1024

    DEFAULT_MMAP_MAX           65536

    There are several other #defined constants and macros that you

    probably don't want to touch unless you are extending or adapting malloc.

*/

/*

  WIN32 sets up defaults for MS environment and compilers.

  Otherwise defaults are for unix.

*/

/* #define WIN32 */

#ifdef WIN32

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

/* Win32 doesn't supply or need the following headers */

/*#define LACKS_UNISTD_H*/

#define LACKS_SYS_PARAM_H

#define LACKS_SYS_MMAN_H

/* Use the supplied emulation of sbrk */

#define MORECORE sbrk

#define MORECORE_CONTIGUOUS 0

#define MORECORE_FAILURE    ((void*)(-1))

/* Use the supplied emulation of mmap and munmap */

#define HAVE_MMAP 1

#define MUNMAP_FAILURE  (-1)

#define MMAP_CLEARS 1

/* These values don't really matter in windows mmap emulation */

#define MAP_PRIVATE 1

#define MAP_ANONYMOUS 2

#define PROT_READ 1

#define PROT_WRITE 2

/* Emulation functions defined at the end of this file */

/* If USE_MALLOC_LOCK, use supplied critical-section-based lock functions */

#ifdef USE_MALLOC_LOCK

static int slwait(int *sl);

static int slrelease(int *sl);

#endif

static long getpagesize(void);

static long getregionsize(void);

static void *sbrk(long size);

static void *mmap(void *ptr, long size, long prot, long type, long handle, long arg);

static long munmap(void *ptr, long size);

static void vminfo (unsigned long*free, unsigned long*reserved, unsigned long*committed);

/* Commented out for R incompatibility

static int cpuinfo (int whole, unsigned long*kernel, unsigned long*user);

*/

#endif

/*

  Void_t* is the pointer type that malloc should say it returns

*/

#ifndef Void_t

#define Void_t      void

#endif /*Void_t*/

#include <stddef.h>   /* for size_t */

#ifdef __cplusplus

extern "C" {

#endif

/* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */

/* #define  LACKS_UNISTD_H */

#ifndef LACKS_UNISTD_H

#include <unistd.h>

#endif

/* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */

/* #define  LACKS_SYS_PARAM_H */

#include <stdio.h>    /* needed for malloc_stats */

#include <errno.h>    /* needed for optional MALLOC_FAILURE_ACTION */

/*

  Debugging:

  Because freed chunks may be overwritten with bookkeeping fields, this

  malloc will often die when freed memory is overwritten by user

  programs.  This can be very effective (albeit in an annoying way)

  in helping track down dangling pointers.

  If you compile with -DDEBUG, a number of assertion checks are

  enabled that will catch more memory errors. You probably won't be

  able to make much sense of the actual assertion errors, but they

  should help you locate incorrectly overwritten memory.  The

  checking is fairly extensive, and will slow down execution

  noticeably. Calling malloc_stats or mallinfo with DEBUG set will

  attempt to check every non-mmapped allocated and free chunk in the

  course of computing the summmaries. (By nature, mmapped regions

  cannot be checked very much automatically.)

  Setting DEBUG may also be helpful if you are trying to modify

  this code. The assertions in the check routines spell out in more

  detail the assumptions and invariants underlying the algorithms.

  Setting DEBUG does NOT provide an automated mechanism for checking

  that all accesses to malloced memory stay within their

  bounds. However, there are several add-ons and adaptations of this

  or other mallocs available that do this.

*/

/* #define DEBUG 1 */

#if DEBUG

#include <assert.h>

#else

#define assert(x) ((void)0)

#endif

/*

  The unsigned integer type used for comparing any two chunk sizes.

  This should be at least as wide as size_t, but should not be signed.

*/

#ifndef CHUNK_SIZE_T

#define CHUNK_SIZE_T unsigned long

#endif

/* 

  The unsigned integer type used to hold addresses when they are are

  manipulated as integers. Except that it is not defined on all

  systems, intptr_t would suffice.

*/

#ifndef PTR_UINT

#define PTR_UINT unsigned long

#endif

/*

  INTERNAL_SIZE_T is the word-size used for internal bookkeeping

  of chunk sizes.

  The default version is the same as size_t.

  While not strictly necessary, it is best to define this as an

  unsigned type, even if size_t is a signed type. This may avoid some

  artificial size limitations on some systems.

  On a 64-bit machine, you may be able to reduce malloc overhead by

  defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the

  expense of not being able to handle more than 2^32 of malloced

  space. If this limitation is acceptable, you are encouraged to set

  this unless you are on a platform requiring 16byte alignments. In

  this case the alignment requirements turn out to negate any

  potential advantages of decreasing size_t word size.

  Implementors: Beware of the possible combinations of:

     - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,

       and might be the same width as int or as long

     - size_t might have different width and signedness as INTERNAL_SIZE_T

     - int and long might be 32 or 64 bits, and might be the same width

  To deal with this, most comparisons and difference computations

  among INTERNAL_SIZE_Ts should cast them to CHUNK_SIZE_T, being

  aware of the fact that casting an unsigned int to a wider long does

  not sign-extend. (This also makes checking for negative numbers

  awkward.) Some of these casts result in harmless compiler warnings

  on some systems.

*/

#ifndef INTERNAL_SIZE_T

#define INTERNAL_SIZE_T size_t

#endif

/* The corresponding word size */

#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))

/*

  MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.

  It must be a power of two at least 2 * SIZE_SZ, even on machines

  for which smaller alignments would suffice. It may be defined as

  larger than this though. Note however that code and data structures

  are optimized for the case of 8-byte alignment.

*/

#ifndef MALLOC_ALIGNMENT

#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)

#endif

/* The corresponding bit mask value */

#define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)

/*

  REALLOC_ZERO_BYTES_FREES should be set if a call to

  realloc with zero bytes should be the same as a call to free.

  Some people think it should. Otherwise, since this malloc

  returns a unique pointer for malloc(0), so does realloc(p, 0).

*/

/*   #define REALLOC_ZERO_BYTES_FREES */

/*

  TRIM_FASTBINS controls whether free() of a very small chunk can

  immediately lead to trimming. Setting to true (1) can reduce memory

  footprint, but will almost always slow down programs that use a lot

  of small chunks.

  Define this only if you are willing to give up some speed to more

  aggressively reduce system-level memory footprint when releasing

  memory in programs that use many small chunks.  You can get

  essentially the same effect by setting MXFAST to 0, but this can

  lead to even greater slowdowns in programs using many small chunks.

  TRIM_FASTBINS is an in-between compile-time option, that disables

  only those chunks bordering topmost memory from being placed in

  fastbins.

*/

#ifndef TRIM_FASTBINS

#define TRIM_FASTBINS  0

#endif

/*

  USE_DL_PREFIX will prefix all public routines with the string 'dl'.

  This is necessary when you only want to use this malloc in one part 

  of a program, using your regular system malloc elsewhere.

*/

/* #define USE_DL_PREFIX */

/*

  USE_MALLOC_LOCK causes wrapper functions to surround each

  callable routine with pthread mutex lock/unlock.

  USE_MALLOC_LOCK forces USE_PUBLIC_MALLOC_WRAPPERS to be defined

*/

/* #define USE_MALLOC_LOCK */

/*

  If USE_PUBLIC_MALLOC_WRAPPERS is defined, every public routine is

  actually a wrapper function that first calls MALLOC_PREACTION, then

  calls the internal routine, and follows it with

  MALLOC_POSTACTION. This is needed for locking, but you can also use

  this, without USE_MALLOC_LOCK, for purposes of interception,

  instrumentation, etc. It is a sad fact that using wrappers often

  noticeably degrades performance of malloc-intensive programs.

*/

#ifdef USE_MALLOC_LOCK

#define USE_PUBLIC_MALLOC_WRAPPERS

#else

/* #define USE_PUBLIC_MALLOC_WRAPPERS */

#endif

/* 

   Two-phase name translation.

   All of the actual routines are given mangled names.

   When wrappers are used, they become the public callable versions.

   When DL_PREFIX is used, the callable names are prefixed.

*/

#ifndef USE_PUBLIC_MALLOC_WRAPPERS

#define cALLOc      public_cALLOc

#define fREe        public_fREe

#define cFREe       public_cFREe

#define mALLOc      public_mALLOc

#define mEMALIGn    public_mEMALIGn

#define rEALLOc     public_rEALLOc

#define vALLOc      public_vALLOc

#define pVALLOc     public_pVALLOc

#define mALLINFo    public_mALLINFo

#define mALLOPt     public_mALLOPt

#define mTRIm       public_mTRIm

#define mSTATs      public_mSTATs

#define mUSABLe     public_mUSABLe

#define iCALLOc     public_iCALLOc

#define iCOMALLOc   public_iCOMALLOc

#endif

#ifdef USE_DL_PREFIX

#define public_cALLOc    dlcalloc

#define public_fREe      dlfree

#define public_cFREe     dlcfree

#define public_mALLOc    dlmalloc

#define public_mEMALIGn  dlmemalign

#define public_rEALLOc   dlrealloc

#define public_vALLOc    dlvalloc

#define public_pVALLOc   dlpvalloc

#define public_mALLINFo  dlmallinfo

#define public_mALLOPt   dlmallopt

#define public_mTRIm     dlmalloc_trim

#define public_mSTATs    dlmalloc_stats

#define public_mUSABLe   dlmalloc_usable_size

#define public_iCALLOc   dlindependent_calloc

#define public_iCOMALLOc dlindependent_comalloc

#else /* USE_DL_PREFIX */

#define public_cALLOc    Rm_calloc

#define public_fREe      Rm_free

#define public_cFREe     Rm_cfree

#define public_mALLOc    Rm_malloc

#define public_mEMALIGn  Rm_memalign

#define public_rEALLOc   Rm_realloc

#define public_vALLOc    Rm_valloc

#define public_pVALLOc   Rm_pvalloc

#define public_mALLINFo  mallinfo

#define public_mALLOPt   mallopt

#define public_mTRIm     malloc_trim

#define public_mSTATs    malloc_stats

#define public_mUSABLe   malloc_usable_size

#define public_iCALLOc   independent_calloc

#define public_iCOMALLOc independent_comalloc

#endif /* USE_DL_PREFIX */

/*

  HAVE_MEMCPY should be defined if you are not otherwise using

  ANSI STD C, but still have memcpy and memset in your C library

  and want to use them in calloc and realloc. Otherwise simple

  macro versions are defined below.

  USE_MEMCPY should be defined as 1 if you actually want to

  have memset and memcpy called. People report that the macro

  versions are faster than libc versions on some systems.

  Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks

  (of <= 36 bytes) are manually unrolled in realloc and calloc.

*/

#define HAVE_MEMCPY

#ifndef USE_MEMCPY

#ifdef HAVE_MEMCPY

#define USE_MEMCPY 1

#else

#define USE_MEMCPY 0

#endif

#endif

#if (defined(HAVE_MEMCPY))

#ifdef WIN32

/* On Win32 memset and memcpy are already declared in windows.h */

#else

void* memset(void*, int, size_t);

void* memcpy(void*, const void*, size_t);

#endif

#endif

/*

  MALLOC_FAILURE_ACTION is the action to take before "return 0" when

  malloc fails to be able to return memory, either because memory is

  exhausted or because of illegal arguments.

  By default, sets errno if running on STD_C platform, else does nothing.  

*/

#ifndef MALLOC_FAILURE_ACTION

#define MALLOC_FAILURE_ACTION \

   errno = ENOMEM;

#endif

/*

  MORECORE-related declarations. By default, rely on sbrk

*/

#ifdef LACKS_UNISTD_H

#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)

extern Void_t*     sbrk(ptrdiff_t);

#endif

#endif

/*

  MORECORE is the name of the routine to call to obtain more memory

  from the system.  See below for general guidance on writing

  alternative MORECORE functions, as well as a version for WIN32 and a

  sample version for pre-OSX macos.

*/

#ifndef MORECORE

#define MORECORE sbrk

#endif

/*

  MORECORE_FAILURE is the value returned upon failure of MORECORE

  as well as mmap. Since it cannot be an otherwise valid memory address,

  and must reflect values of standard sys calls, you probably ought not

  try to redefine it.

*/

#ifndef MORECORE_FAILURE

#define MORECORE_FAILURE (-1)

#endif

/*

  If MORECORE_CONTIGUOUS is true, take advantage of fact that

  consecutive calls to MORECORE with positive arguments always return

  contiguous increasing addresses.  This is true of unix sbrk.  Even

  if not defined, when regions happen to be contiguous, malloc will

  permit allocations spanning regions obtained from different

  calls. But defining this when applicable enables some stronger

  consistency checks and space efficiencies. 

*/

#ifndef MORECORE_CONTIGUOUS

#define MORECORE_CONTIGUOUS 1

#endif

/*

  Define MORECORE_CANNOT_TRIM if your version of MORECORE

  cannot release space back to the system when given negative

  arguments. This is generally necessary only if you are using

  a hand-crafted MORECORE function that cannot handle negative arguments.

*/

/* #define MORECORE_CANNOT_TRIM */

/*

  Define HAVE_MMAP as true to optionally make malloc() use mmap() to

  allocate very large blocks.  These will be returned to the

  operating system immediately after a free(). Also, if mmap

  is available, it is used as a backup strategy in cases where

  MORECORE fails to provide space from system.

  This malloc is best tuned to work with mmap for large requests.

  If you do not have mmap, operations involving very large chunks (1MB

  or so) may be slower than you'd like.

*/

#ifndef HAVE_MMAP

#define HAVE_MMAP 1

#endif

#if HAVE_MMAP

/* 

   Standard unix mmap using /dev/zero clears memory so calloc doesn't

   need to.

*/

#ifndef MMAP_CLEARS

#define MMAP_CLEARS 1

#endif

#else /* no mmap */

#ifndef MMAP_CLEARS

#define MMAP_CLEARS 0

#endif

#endif

/* 

   MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if

   sbrk fails, and mmap is used as a backup (which is done only if

   HAVE_MMAP).  The value must be a multiple of page size.  This

   backup strategy generally applies only when systems have "holes" in

   address space, so sbrk cannot perform contiguous expansion, but

   there is still space available on system.  On systems for which

   this is known to be useful (i.e. most linux kernels), this occurs

   only when programs allocate huge amounts of memory.  Between this,

   and the fact that mmap regions tend to be limited, the size should

   be large, to avoid too many mmap calls and thus avoid running out

   of kernel resources.

*/

#ifndef MMAP_AS_MORECORE_SIZE

#define MMAP_AS_MORECORE_SIZE (1024 * 1024)

#endif

/*

  Define HAVE_MREMAP to make realloc() use mremap() to re-allocate

  large blocks.  This is currently only possible on Linux with

  kernel versions newer than 1.3.77.

*/

#ifndef HAVE_MREMAP

#ifdef linux

#define HAVE_MREMAP 1

#else

#define HAVE_MREMAP 0

#endif

#endif /* HAVE_MMAP */

/*

  The system page size. To the extent possible, this malloc manages

  memory from the system in page-size units.  Note that this value is

  cached during initialization into a field of malloc_state. So even

  if malloc_getpagesize is a function, it is only called once.

  The following mechanics for getpagesize were adapted from bsd/gnu

  getpagesize.h. If none of the system-probes here apply, a value of

  4096 is used, which should be OK: If they don't apply, then using

  the actual value probably doesn't impact performance.

*/

#ifndef malloc_getpagesize

#ifndef LACKS_UNISTD_H

#  include <unistd.h>

#endif

#  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */

#    ifndef _SC_PAGE_SIZE

#      define _SC_PAGE_SIZE _SC_PAGESIZE

#    endif

#  endif

#  ifdef _SC_PAGE_SIZE

#    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)

#  else

#    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)

       extern size_t getpagesize();

#      define malloc_getpagesize getpagesize()

#    else

#      ifdef WIN32 /* use supplied emulation of getpagesize */

#        define malloc_getpagesize getpagesize() 

#      else

#        ifndef LACKS_SYS_PARAM_H

#          include <sys/param.h>

#        endif

#        ifdef EXEC_PAGESIZE

#          define malloc_getpagesize EXEC_PAGESIZE

#        else

#          ifdef NBPG

#            ifndef CLSIZE

#              define malloc_getpagesize NBPG

#            else

#              define malloc_getpagesize (NBPG * CLSIZE)

#            endif

#          else

#            ifdef NBPC

#              define malloc_getpagesize NBPC

#            else

#              ifdef PAGESIZE

#                define malloc_getpagesize PAGESIZE

#              else /* just guess */

#                define malloc_getpagesize (4096) 

#              endif

#            endif

#          endif

#        endif

#      endif

#    endif

#  endif

#endif

/*

  This version of malloc supports the standard SVID/XPG mallinfo

  routine that returns a struct containing usage properties and

  statistics. It should work on any SVID/XPG compliant system that has

  a /usr/include/malloc.h defining struct mallinfo. (If you'd like to

  install such a thing yourself, cut out the preliminary declarations

  as described above and below and save them in a malloc.h file. But

  there's no compelling reason to bother to do this.)

  The main declaration needed is the mallinfo struct that is returned

  (by-copy) by mallinfo().  The SVID/XPG malloinfo struct contains a

  bunch of fields that are not even meaningful in this version of

  malloc.  These fields are are instead filled by mallinfo() with

  other numbers that might be of interest.

  HAVE_USR_INCLUDE_MALLOC_H should be set if you have a

  /usr/include/malloc.h file that includes a declaration of struct

  mallinfo.  If so, it is included; else an SVID2/XPG2 compliant

  version is declared below.  These must be precisely the same for

  mallinfo() to work.  The original SVID version of this struct,

  defined on most systems with mallinfo, declares all fields as

  ints. But some others define as unsigned long. If your system

  defines the fields using a type of different width than listed here,

  you must #include your system version and #define

  HAVE_USR_INCLUDE_MALLOC_H.

*/

/* #define HAVE_USR_INCLUDE_MALLOC_H */

#ifdef HAVE_USR_INCLUDE_MALLOC_H

#include "/usr/include/malloc.h"

#else

/* SVID2/XPG mallinfo structure */

struct mallinfo {

  int arena;    /* non-mmapped space allocated from system */

  int ordblks;  /* number of free chunks */

  int smblks;   /* number of fastbin blocks */

  int hblks;    /* number of mmapped regions */

  int hblkhd;   /* space in mmapped regions */

  int usmblks;  /* maximum total allocated space */

  int fsmblks;  /* space available in freed fastbin blocks */

  int uordblks; /* total allocated space */

  int fordblks; /* total free space */

  int keepcost; /* top-most, releasable (via malloc_trim) space */

};

/*

  SVID/XPG defines four standard parameter numbers for mallopt,

  normally defined in malloc.h.  Only one of these (M_MXFAST) is used

  in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,

  so setting them has no effect. But this malloc also supports other

  options in mallopt described below.

*/

#endif

/* R Specific declarations here */

extern unsigned int R_max_memory;

extern int R_Is_Running;

void Rf_warning(const char *, ...);

/* ---------- description of public routines ------------ */

/*

  malloc(size_t n)

  Returns a pointer to a newly allocated chunk of at least n bytes, or null

  if no space is available. Additionally, on failure, errno is

  set to ENOMEM on ANSI C systems.

  If n is zero, malloc returns a minumum-sized chunk. (The minimum

  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit

  systems.)  On most systems, size_t is an unsigned type, so calls

  with negative arguments are interpreted as requests for huge amounts

  of space, which will often fail. The maximum supported value of n

  differs across systems, but is in all cases less than the maximum

  representable value of a size_t.

*/

Void_t*  public_mALLOc(size_t);

/*

  free(Void_t* p)

  Releases the chunk of memory pointed to by p, that had been previously

  allocated using malloc or a related routine such as realloc.

  It has no effect if p is null. It can have arbitrary (i.e., bad!)

  effects if p has already been freed.

  Unless disabled (using mallopt), freeing very large spaces will

  when possible, automatically trigger operations that give

  back unused memory to the system, thus reducing program footprint.

*/

void     public_fREe(Void_t*);

/*

  calloc(size_t n_elements, size_t element_size);

  Returns a pointer to n_elements * element_size bytes, with all locations

  set to zero.

*/

Void_t*  public_cALLOc(size_t, size_t);

/*

  realloc(Void_t* p, size_t n)

  Returns a pointer to a chunk of size n that contains the same data

  as does chunk p up to the minimum of (n, p's size) bytes, or null

  if no space is available. 

  The returned pointer may or may not be the same as p. The algorithm

  prefers extending p when possible, otherwise it employs the

  equivalent of a malloc-copy-free sequence.

  If p is null, realloc is equivalent to malloc.  

  If space is not available, realloc returns null, errno is set (if on

  ANSI) and p is NOT freed.

  if n is for fewer bytes than already held by p, the newly unused

  space is lopped off and freed if possible.  Unless the #define

  REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of

  zero (re)allocates a minimum-sized chunk.

  Large chunks that were internally obtained via mmap will always

  be reallocated using malloc-copy-free sequences unless

  the system supports MREMAP (currently only linux).

  The old unix realloc convention of allowing the last-free'd chunk

  to be used as an argument to realloc is not supported.

*/

Void_t*  public_rEALLOc(Void_t*, size_t);

/*

  memalign(size_t alignment, size_t n);

  Returns a pointer to a newly allocated chunk of n bytes, aligned

  in accord with the alignment argument.

  The alignment argument should be a power of two. If the argument is

  not a power of two, the nearest greater power is used.

  8-byte alignment is guaranteed by normal malloc calls, so don't

  bother calling memalign with an argument of 8 or less.

  Overreliance on memalign is a sure way to fragment space.

*/

Void_t*  public_mEMALIGn(size_t, size_t);

/*

  valloc(size_t n);

  Equivalent to memalign(pagesize, n), where pagesize is the page

  size of the system. If the pagesize is unknown, 4096 is used.

*/

Void_t*  public_vALLOc(size_t);

/*

  mallopt(int parameter_number, int parameter_value)

  Sets tunable parameters The format is to provide a

  (parameter-number, parameter-value) pair.  mallopt then sets the

  corresponding parameter to the argument value if it can (i.e., so

  long as the value is meaningful), and returns 1 if successful else

  0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,

  normally defined in malloc.h.  Only one of these (M_MXFAST) is used

  in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,

  so setting them has no effect. But this malloc also supports four

  other options in mallopt. See below for details.  Briefly, supported

  parameters are as follows (listed defaults are for "typical"

  configurations).

  Symbol            param #   default    allowed param values

  M_MXFAST          1         64         0-80  (0 disables fastbins)

  M_TRIM_THRESHOLD -1         256*1024   any   (-1U disables trimming)

  M_TOP_PAD        -2         0          any  

  M_MMAP_THRESHOLD -3         256*1024   any   (or 0 if no MMAP support)

  M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)

*/

int      public_mALLOPt(int, int);

/*

  mallinfo()

  Returns (by copy) a struct containing various summary statistics:

  arena:     current total non-mmapped bytes allocated from system 

  ordblks:   the number of free chunks 

  smblks:    the number of fastbin blocks (i.e., small chunks that

               have been freed but not use resused or consolidated)

  hblks:     current number of mmapped regions 

  hblkhd:    total bytes held in mmapped regions 

  usmblks:   the maximum total allocated space. This will be greater

                than current total if trimming has occurred.

  fsmblks:   total bytes held in fastbin blocks 

  uordblks:  current total allocated space (normal or mmapped)

  fordblks:  total free space 

  keepcost:  the maximum number of bytes that could ideally be released

               back to system via malloc_trim. ("ideally" means that

               it ignores page restrictions etc.)