Code

r11451@tres: ted | 2006-04-17 22:21:33 -0700
[inkscape.git] / src / dom / js / jsarena.h
1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2  *
3  * ***** BEGIN LICENSE BLOCK *****
4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5  *
6  * The contents of this file are subject to the Mozilla Public License Version
7  * 1.1 (the "License"); you may not use this file except in compliance with
8  * the License. You may obtain a copy of the License at
9  * http://www.mozilla.org/MPL/
10  *
11  * Software distributed under the License is distributed on an "AS IS" basis,
12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13  * for the specific language governing rights and limitations under the
14  * License.
15  *
16  * The Original Code is Mozilla Communicator client code, released
17  * March 31, 1998.
18  *
19  * The Initial Developer of the Original Code is
20  * Netscape Communications Corporation.
21  * Portions created by the Initial Developer are Copyright (C) 1998
22  * the Initial Developer. All Rights Reserved.
23  *
24  * Contributor(s):
25  *
26  * Alternatively, the contents of this file may be used under the terms of
27  * either of the GNU General Public License Version 2 or later (the "GPL"),
28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29  * in which case the provisions of the GPL or the LGPL are applicable instead
30  * of those above. If you wish to allow use of your version of this file only
31  * under the terms of either the GPL or the LGPL, and not to allow others to
32  * use your version of this file under the terms of the MPL, indicate your
33  * decision by deleting the provisions above and replace them with the notice
34  * and other provisions required by the GPL or the LGPL. If you do not delete
35  * the provisions above, a recipient may use your version of this file under
36  * the terms of any one of the MPL, the GPL or the LGPL.
37  *
38  * ***** END LICENSE BLOCK ***** */
40 #ifndef jsarena_h___
41 #define jsarena_h___
42 /*
43  * Lifetime-based fast allocation, inspired by much prior art, including
44  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
45  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
46  *
47  * Also supports LIFO allocation (JS_ARENA_MARK/JS_ARENA_RELEASE).
48  */
49 #include <stdlib.h>
50 #include "jstypes.h"
51 #include "jscompat.h"
53 JS_BEGIN_EXTERN_C
55 typedef struct JSArena JSArena;
56 typedef struct JSArenaPool JSArenaPool;
58 struct JSArena {
59     JSArena     *next;          /* next arena for this lifetime */
60     jsuword     base;           /* aligned base address, follows this header */
61     jsuword     limit;          /* one beyond last byte in arena */
62     jsuword     avail;          /* points to next available byte */
63 };
65 #ifdef JS_ARENAMETER
66 typedef struct JSArenaStats JSArenaStats;
68 struct JSArenaStats {
69     JSArenaStats *next;         /* next in arenaStats list */
70     char        *name;          /* name for debugging */
71     uint32      narenas;        /* number of arenas in pool */
72     uint32      nallocs;        /* number of JS_ARENA_ALLOCATE() calls */
73     uint32      nreclaims;      /* number of reclaims from freeArenas */
74     uint32      nmallocs;       /* number of malloc() calls */
75     uint32      ndeallocs;      /* number of lifetime deallocations */
76     uint32      ngrows;         /* number of JS_ARENA_GROW() calls */
77     uint32      ninplace;       /* number of in-place growths */
78     uint32      nreallocs;      /* number of arena grow extending reallocs */
79     uint32      nreleases;      /* number of JS_ARENA_RELEASE() calls */
80     uint32      nfastrels;      /* number of "fast path" releases */
81     size_t      nbytes;         /* total bytes allocated */
82     size_t      maxalloc;       /* maximum allocation size in bytes */
83     double      variance;       /* size variance accumulator */
84 };
85 #endif
87 struct JSArenaPool {
88     JSArena     first;          /* first arena in pool list */
89     JSArena     *current;       /* arena from which to allocate space */
90     size_t      arenasize;      /* net exact size of a new arena */
91     jsuword     mask;           /* alignment mask (power-of-2 - 1) */
92 #ifdef JS_ARENAMETER
93     JSArenaStats stats;
94 #endif
95 };
97 /*
98  * If the including .c file uses only one power-of-2 alignment, it may define
99  * JS_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions
100  * per ALLOCATE and GROW.
101  */
102 #ifdef JS_ARENA_CONST_ALIGN_MASK
103 #define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + JS_ARENA_CONST_ALIGN_MASK)   \
104                                  & ~(jsuword)JS_ARENA_CONST_ALIGN_MASK)
106 #define JS_INIT_ARENA_POOL(pool, name, size) \
107         JS_InitArenaPool(pool, name, size, JS_ARENA_CONST_ALIGN_MASK + 1)
108 #else
109 #define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + (pool)->mask) & ~(pool)->mask)
110 #endif
112 #define JS_ARENA_ALLOCATE(p, pool, nb)                                        \
113     JS_ARENA_ALLOCATE_CAST(p, void *, pool, nb)
115 #define JS_ARENA_ALLOCATE_TYPE(p, type, pool)                                 \
116     JS_ARENA_ALLOCATE_CAST(p, type *, pool, sizeof(type))
118 #define JS_ARENA_ALLOCATE_CAST(p, type, pool, nb)                             \
119     JS_BEGIN_MACRO                                                            \
120         JSArena *_a = (pool)->current;                                        \
121         size_t _nb = JS_ARENA_ALIGN(pool, nb);                                \
122         jsuword _p = _a->avail;                                               \
123         jsuword _q = _p + _nb;                                                \
124         JS_ASSERT(_q >= _p);                                                  \
125         if (_q > _a->limit)                                                   \
126             _p = (jsuword)JS_ArenaAllocate(pool, _nb);                        \
127         else                                                                  \
128             _a->avail = _q;                                                   \
129         p = (type) _p;                                                        \
130         JS_ArenaCountAllocation(pool, nb);                                    \
131     JS_END_MACRO
133 #define JS_ARENA_GROW(p, pool, size, incr)                                    \
134     JS_ARENA_GROW_CAST(p, void *, pool, size, incr)
136 #define JS_ARENA_GROW_CAST(p, type, pool, size, incr)                         \
137     JS_BEGIN_MACRO                                                            \
138         JSArena *_a = (pool)->current;                                        \
139         if (_a->avail == (jsuword)(p) + JS_ARENA_ALIGN(pool, size)) {         \
140             size_t _nb = (size) + (incr);                                     \
141             jsuword _q = (jsuword)(p) + JS_ARENA_ALIGN(pool, _nb);            \
142             if (_q <= _a->limit) {                                            \
143                 _a->avail = _q;                                               \
144                 JS_ArenaCountInplaceGrowth(pool, size, incr);                 \
145             } else if ((jsuword)(p) == _a->base) {                            \
146                 p = (type) JS_ArenaRealloc(pool, p, size, incr);              \
147             } else {                                                          \
148                 p = (type) JS_ArenaGrow(pool, p, size, incr);                 \
149             }                                                                 \
150         } else {                                                              \
151             p = (type) JS_ArenaGrow(pool, p, size, incr);                     \
152         }                                                                     \
153         JS_ArenaCountGrowth(pool, size, incr);                                \
154     JS_END_MACRO
156 #define JS_ARENA_MARK(pool)     ((void *) (pool)->current->avail)
157 #define JS_UPTRDIFF(p,q)        ((jsuword)(p) - (jsuword)(q))
159 #ifdef DEBUG
160 #define JS_FREE_PATTERN         0xDA
161 #define JS_CLEAR_UNUSED(a)      (JS_ASSERT((a)->avail <= (a)->limit),         \
162                                  memset((void*)(a)->avail, JS_FREE_PATTERN,   \
163                                         (a)->limit - (a)->avail))
164 #define JS_CLEAR_ARENA(a)       memset((void*)(a), JS_FREE_PATTERN,           \
165                                        (a)->limit - (jsuword)(a))
166 #else
167 #define JS_CLEAR_UNUSED(a)      /* nothing */
168 #define JS_CLEAR_ARENA(a)       /* nothing */
169 #endif
171 #define JS_ARENA_RELEASE(pool, mark)                                          \
172     JS_BEGIN_MACRO                                                            \
173         char *_m = (char *)(mark);                                            \
174         JSArena *_a = (pool)->current;                                        \
175         if (_a != &(pool)->first &&                                           \
176             JS_UPTRDIFF(_m, _a->base) <= JS_UPTRDIFF(_a->avail, _a->base)) {  \
177             _a->avail = (jsuword)JS_ARENA_ALIGN(pool, _m);                    \
178             JS_ASSERT(_a->avail <= _a->limit);                                \
179             JS_CLEAR_UNUSED(_a);                                              \
180             JS_ArenaCountRetract(pool, _m);                                   \
181         } else {                                                              \
182             JS_ArenaRelease(pool, _m);                                        \
183         }                                                                     \
184         JS_ArenaCountRelease(pool, _m);                                       \
185     JS_END_MACRO
187 #ifdef JS_ARENAMETER
188 #define JS_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
189 #else
190 #define JS_COUNT_ARENA(pool,op)
191 #endif
193 #define JS_ARENA_DESTROY(pool, a, pnext)                                      \
194     JS_BEGIN_MACRO                                                            \
195         JS_COUNT_ARENA(pool,--);                                              \
196         if ((pool)->current == (a)) (pool)->current = &(pool)->first;         \
197         *(pnext) = (a)->next;                                                 \
198         JS_CLEAR_ARENA(a);                                                    \
199         free(a);                                                              \
200         (a) = NULL;                                                           \
201     JS_END_MACRO
203 /*
204  * Initialize an arena pool with the given name for debugging and metering,
205  * with a minimum size per arena of size bytes.
206  */
207 extern JS_PUBLIC_API(void)
208 JS_InitArenaPool(JSArenaPool *pool, const char *name, size_t size,
209                  size_t align);
211 /*
212  * Free the arenas in pool.  The user may continue to allocate from pool
213  * after calling this function.  There is no need to call JS_InitArenaPool()
214  * again unless JS_FinishArenaPool(pool) has been called.
215  */
216 extern JS_PUBLIC_API(void)
217 JS_FreeArenaPool(JSArenaPool *pool);
219 /*
220  * Free the arenas in pool and finish using it altogether.
221  */
222 extern JS_PUBLIC_API(void)
223 JS_FinishArenaPool(JSArenaPool *pool);
225 /*
226  * Finish using arenas, freeing all memory associated with them except for
227  * any locks needed for thread safety.
228  */
229 extern JS_PUBLIC_API(void)
230 JS_ArenaFinish(void);
232 /*
233  * Free any locks or other memory needed for thread safety, just before
234  * shutting down.  At that point, we must be called by a single thread.
235  *
236  * After shutting down, the next thread to call JS_InitArenaPool must not
237  * race with any other thread.  Once a pool has been initialized, threads
238  * may safely call jsarena.c functions on thread-local pools.  The upshot
239  * is that pools are per-thread, but the underlying global freelist is
240  * thread-safe, provided that both the first pool initialization and the
241  * shut-down call are single-threaded.
242  */
243 extern JS_PUBLIC_API(void)
244 JS_ArenaShutDown(void);
246 /*
247  * Friend functions used by the JS_ARENA_*() macros.
248  */
249 extern JS_PUBLIC_API(void *)
250 JS_ArenaAllocate(JSArenaPool *pool, size_t nb);
252 extern JS_PUBLIC_API(void *)
253 JS_ArenaRealloc(JSArenaPool *pool, void *p, size_t size, size_t incr);
255 extern JS_PUBLIC_API(void *)
256 JS_ArenaGrow(JSArenaPool *pool, void *p, size_t size, size_t incr);
258 extern JS_PUBLIC_API(void)
259 JS_ArenaRelease(JSArenaPool *pool, char *mark);
261 /*
262  * Function to be used directly when an allocation has likely grown to consume
263  * an entire JSArena, in which case the arena is returned to the malloc heap.
264  */
265 extern JS_PUBLIC_API(void)
266 JS_ArenaFreeAllocation(JSArenaPool *pool, void *p, size_t size);
268 #ifdef JS_ARENAMETER
270 #include <stdio.h>
272 extern JS_PUBLIC_API(void)
273 JS_ArenaCountAllocation(JSArenaPool *pool, size_t nb);
275 extern JS_PUBLIC_API(void)
276 JS_ArenaCountInplaceGrowth(JSArenaPool *pool, size_t size, size_t incr);
278 extern JS_PUBLIC_API(void)
279 JS_ArenaCountGrowth(JSArenaPool *pool, size_t size, size_t incr);
281 extern JS_PUBLIC_API(void)
282 JS_ArenaCountRelease(JSArenaPool *pool, char *mark);
284 extern JS_PUBLIC_API(void)
285 JS_ArenaCountRetract(JSArenaPool *pool, char *mark);
287 extern JS_PUBLIC_API(void)
288 JS_DumpArenaStats(FILE *fp);
290 #else  /* !JS_ARENAMETER */
292 #define JS_ArenaCountAllocation(ap, nb)                 /* nothing */
293 #define JS_ArenaCountInplaceGrowth(ap, size, incr)      /* nothing */
294 #define JS_ArenaCountGrowth(ap, size, incr)             /* nothing */
295 #define JS_ArenaCountRelease(ap, mark)                  /* nothing */
296 #define JS_ArenaCountRetract(ap, mark)                  /* nothing */
298 #endif /* !JS_ARENAMETER */
300 JS_END_EXTERN_C
302 #endif /* jsarena_h___ */