home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / lib / ds / plarena.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  6.9 KB  |  194 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. #ifndef plarena_h___
  20. #define plarena_h___
  21. /*
  22.  * Lifetime-based fast allocation, inspired by much prior art, including
  23.  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
  24.  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
  25.  *
  26.  * Also supports LIFO allocation (PL_ARENA_MARK/PL_ARENA_RELEASE).
  27.  */
  28. #include "prtypes.h"
  29. #include "plarenas.h"
  30.  
  31. PR_BEGIN_EXTERN_C
  32.  
  33. typedef struct PLArena          PLArena;
  34.  
  35. struct PLArena {
  36.     PLArena     *next;          /* next arena for this lifetime */
  37.     PRUword     base;           /* aligned base address, follows this header */
  38.     PRUword     limit;          /* one beyond last byte in arena */
  39.     PRUword     avail;          /* points to next available byte */
  40. };
  41.  
  42. #ifdef PL_ARENAMETER
  43. typedef struct PLArenaStats PLArenaStats;
  44.  
  45. struct PLArenaStats {
  46.     PLArenaStats  *next;        /* next in arenaStats list */
  47.     char          *name;        /* name for debugging */
  48.     PRUint32      narenas;      /* number of arenas in pool */
  49.     PRUint32      nallocs;      /* number of PL_ARENA_ALLOCATE() calls */
  50.     PRUint32      nreclaims;    /* number of reclaims from freeArenas */
  51.     PRUint32      nmallocs;     /* number of malloc() calls */
  52.     PRUint32      ndeallocs;    /* number of lifetime deallocations */
  53.     PRUint32      ngrows;       /* number of PL_ARENA_GROW() calls */
  54.     PRUint32      ninplace;     /* number of in-place growths */
  55.     PRUint32      nreleases;    /* number of PL_ARENA_RELEASE() calls */
  56.     PRUint32      nfastrels;    /* number of "fast path" releases */
  57.     PRUint32      nbytes;       /* total bytes allocated */
  58.     PRUint32      maxalloc;     /* maximum allocation size in bytes */
  59.     PRFloat64     variance;     /* size variance accumulator */
  60. };
  61. #endif
  62.  
  63. struct PLArenaPool {
  64.     PLArena     first;          /* first arena in pool list */
  65.     PLArena     *current;       /* arena from which to allocate space */
  66.     PRUint32    arenasize;      /* net exact size of a new arena */
  67.     PRUword     mask;           /* alignment mask (power-of-2 - 1) */
  68. #ifdef PL_ARENAMETER
  69.     PLArenaStats stats;
  70. #endif
  71. };
  72.  
  73. /*
  74.  * If the including .c file uses only one power-of-2 alignment, it may define
  75.  * PL_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions
  76.  * per ALLOCATE and GROW.
  77.  */
  78. #ifdef PL_ARENA_CONST_ALIGN_MASK
  79. #define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + PL_ARENA_CONST_ALIGN_MASK) \
  80.                                 & ~PL_ARENA_CONST_ALIGN_MASK)
  81.  
  82. #define PL_INIT_ARENA_POOL(pool, name, size) \
  83.         PL_InitArenaPool(pool, name, size, PL_ARENA_CONST_ALIGN_MASK + 1)
  84. #else
  85. #define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + (pool)->mask) & ~(pool)->mask)
  86. #endif
  87.  
  88. #define PL_ARENA_ALLOCATE(p, pool, nb) \
  89.     PR_BEGIN_MACRO \
  90.         PLArena *_a = (pool)->current; \
  91.         PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \
  92.         PRUword _p = _a->avail; \
  93.         PRUword _q = _p + _nb; \
  94.         if (_q > _a->limit) \
  95.             _p = (PRUword)PL_ArenaAllocate(pool, _nb); \
  96.         else \
  97.             _a->avail = _q; \
  98.         p = (void *)_p; \
  99.         PL_ArenaCountAllocation(pool, nb); \
  100.     PR_END_MACRO
  101.  
  102. #define PL_ARENA_GROW(p, pool, size, incr) \
  103.     PR_BEGIN_MACRO \
  104.         PLArena *_a = (pool)->current; \
  105.         PRUint32 _incr = PL_ARENA_ALIGN(pool, incr); \
  106.         PRUword _p = _a->avail; \
  107.         PRUword _q = _p + _incr; \
  108.         if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
  109.             _q <= _a->limit) { \
  110.             _a->avail = _q; \
  111.             PL_ArenaCountInplaceGrowth(pool, size, incr); \
  112.         } else { \
  113.             p = PL_ArenaGrow(pool, p, size, incr); \
  114.         } \
  115.         PL_ArenaCountGrowth(pool, size, incr); \
  116.     PR_END_MACRO
  117.  
  118. #define PL_ARENA_MARK(pool) ((void *) (pool)->current->avail)
  119. #define PR_UPTRDIFF(p,q) ((PRUword)(p) - (PRUword)(q))
  120.  
  121. #ifdef DEBUG
  122. #define PL_FREE_PATTERN 0xDA
  123. #define PL_CLEAR_UNUSED(a) (PR_ASSERT((a)->avail <= (a)->limit), \
  124.                            memset((void*)(a)->avail, PL_FREE_PATTERN, \
  125.                            (a)->limit - (a)->avail))
  126. #define PL_CLEAR_ARENA(a)  memset((void*)(a), PL_FREE_PATTERN, \
  127.                            (a)->limit - (PRUword)(a))
  128. #else
  129. #define PL_CLEAR_UNUSED(a)
  130. #define PL_CLEAR_ARENA(a)
  131. #endif
  132.  
  133. #define PL_ARENA_RELEASE(pool, mark) \
  134.     PR_BEGIN_MACRO \
  135.         char *_m = (char *)(mark); \
  136.         PLArena *_a = (pool)->current; \
  137.         if (PR_UPTRDIFF(_m, _a) <= PR_UPTRDIFF(_a->avail, _a)) { \
  138.             _a->avail = (PRUword)PL_ARENA_ALIGN(pool, _m); \
  139.             PL_CLEAR_UNUSED(_a); \
  140.             PL_ArenaCountRetract(pool, _m); \
  141.         } else { \
  142.             PL_ArenaRelease(pool, _m); \
  143.         } \
  144.         PL_ArenaCountRelease(pool, _m); \
  145.     PR_END_MACRO
  146.  
  147. #ifdef PL_ARENAMETER
  148. #define PL_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
  149. #else
  150. #define PL_COUNT_ARENA(pool,op)
  151. #endif
  152.  
  153. #define PL_ARENA_DESTROY(pool, a, pnext) \
  154.     PR_BEGIN_MACRO \
  155.         PL_COUNT_ARENA(pool,--); \
  156.         if ((pool)->current == (a)) (pool)->current = &(pool)->first; \
  157.         *(pnext) = (a)->next; \
  158.         PL_CLEAR_ARENA(a); \
  159.         free(a); \
  160.         (a) = 0; \
  161.     PR_END_MACRO
  162.  
  163. #ifdef PL_ARENAMETER
  164.  
  165. #include <stdio.h>
  166.  
  167. PR_EXTERN(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb);
  168.  
  169. PR_EXTERN(void) PL_ArenaCountInplaceGrowth(
  170.     PLArenaPool *pool, PRUint32 size, PRUint32 incr);
  171.  
  172. PR_EXTERN(void) PL_ArenaCountGrowth(
  173.     PLArenaPool *pool, PRUint32 size, PRUint32 incr);
  174.  
  175. PR_EXTERN(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark);
  176.  
  177. PR_EXTERN(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark);
  178.  
  179. PR_EXTERN(void) PL_DumpArenaStats(FILE *fp);
  180.  
  181. #else  /* !PL_ARENAMETER */
  182.  
  183. #define PL_ArenaCountAllocation(ap, nb)                 /* nothing */
  184. #define PL_ArenaCountInplaceGrowth(ap, size, incr)      /* nothing */
  185. #define PL_ArenaCountGrowth(ap, size, incr)             /* nothing */
  186. #define PL_ArenaCountRelease(ap, mark)                  /* nothing */
  187. #define PL_ArenaCountRetract(ap, mark)                  /* nothing */
  188.  
  189. #endif /* !PL_ARENAMETER */
  190.  
  191. PR_END_EXTERN_C
  192.  
  193. #endif /* plarena_h___ */
  194.