From dfe289850f068f19ba4a83ab4e7e22a7e09c13c9 Mon Sep 17 00:00:00 2001 From: Timothy Pearson Date: Sat, 26 Jan 2013 13:17:21 -0600 Subject: Rename a number of libraries and executables to avoid conflicts with KDE4 --- tdehtml/misc/arena.cpp | 333 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 333 insertions(+) create mode 100644 tdehtml/misc/arena.cpp (limited to 'tdehtml/misc/arena.cpp') diff --git a/tdehtml/misc/arena.cpp b/tdehtml/misc/arena.cpp new file mode 100644 index 000000000..cfbce24ab --- /dev/null +++ b/tdehtml/misc/arena.cpp @@ -0,0 +1,333 @@ +/* + * Copyright (C) 1998-2000 Netscape Communications Corporation. + * + * Other contributors: + * Nick Blievers + * Jeff Hostetler + * Tom Rini + * Raffaele Sena + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * Alternatively, the contents of this file may be used under the terms + * of either the Mozilla Public License Version 1.1, found at + * http://www.mozilla.org/MPL/ (the "MPL") or the GNU General Public + * License Version 2.0, found at http://www.fsf.org/copyleft/gpl.html + * (the "GPL"), in which case the provisions of the MPL or the GPL are + * applicable instead of those above. If you wish to allow use of your + * version of this file only under the terms of one of those two + * licenses (the MPL or the GPL) and not to allow others to use your + * version of this file under the LGPL, indicate your decision by + * deletingthe provisions above and replace them with the notice and + * other provisions required by the MPL or the GPL, as the case may be. + * If you do not delete the provisions above, a recipient may use your + * version of this file under any of the LGPL, the MPL or the GPL. + */ + +/* + * Lifetime-based fast allocation, inspired by much prior art, including + * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes" + * David R. Hanson, Software -- Practice and Experience, Vol. 20(1). + */ + +#include +#include +#include +#include +#include "arena.h" + +#ifdef HAVE_GETPAGESIZE +#include +#define POOL_SIZE kMax(8192u, 2*( unsigned ) getpagesize()) +#else +#define POOL_SIZE 8192 +#endif + +//#define DEBUG_ARENA_MALLOC +#ifdef DEBUG_ARENA_MALLOC +#include +#include +#endif + +namespace tdehtml { + +#ifdef DEBUG_ARENA_MALLOC +static int i = 0; +#endif + +#define FREELIST_MAX 50 +#define LARGE_ALLOCATION_CEIL(pool) (pool)->arenasize * 256 +#define MAX_DISCRETE_ALLOCATION(pool) (pool)->arenasize * 32 +static Arena *arena_freelist = 0; +static int freelist_count = 0; + +#define ARENA_DEFAULT_ALIGN sizeof(double) +#define BIT(n) ((unsigned int)1 << (n)) +#define BITMASK(n) (BIT(n) - 1) +#define CEILING_LOG2(_log2,_n) \ + unsigned int j_ = (unsigned int)(_n); \ + (_log2) = 0; \ + if ((j_) & ((j_)-1)) \ + (_log2) += 1; \ + if ((j_) >> 16) \ + (_log2) += 16, (j_) >>= 16; \ + if ((j_) >> 8) \ + (_log2) += 8, (j_) >>= 8; \ + if ((j_) >> 4) \ + (_log2) += 4, (j_) >>= 4; \ + if ((j_) >> 2) \ + (_log2) += 2, (j_) >>= 2; \ + if ((j_) >> 1) \ + (_log2) += 1; + +int CeilingLog2(unsigned int i) { + int log2; + CEILING_LOG2(log2,i); + return log2; +} + +void InitArenaPool(ArenaPool *pool, const char* /*name*/, + unsigned int /*size*/, unsigned int align) +{ + unsigned int size = POOL_SIZE; + if (align == 0) + align = ARENA_DEFAULT_ALIGN; + pool->mask = BITMASK(CeilingLog2(align)); + pool->first.next = NULL; + pool->first.base = pool->first.avail = pool->first.limit = + (uword)ARENA_ALIGN(pool, &pool->first + 1); + pool->current = &pool->first; + pool->arenasize = size; + pool->largealloc = LARGE_ALLOCATION_CEIL(pool); + pool->cumul = 0; +} + + +/* + ** ArenaAllocate() -- allocate space from an arena pool + ** + ** Description: ArenaAllocate() allocates space from an arena + ** pool. + ** + ** First try to satisfy the request from arenas starting at + ** pool->current. + ** + ** If there is not enough space in the arena pool->current, try + ** to claim an arena, on a first fit basis, from the global + ** freelist (arena_freelist). + ** + ** If no arena in arena_freelist is suitable, then try to + ** allocate a new arena from the heap. + ** + ** Returns: pointer to allocated space or NULL + ** + */ +void* ArenaAllocate(ArenaPool *pool, unsigned int nb) +{ + Arena *a; + char *rp; /* returned pointer */ + +#ifdef DEBUG_ARENA_MALLOC + assert((nb & pool->mask) == 0); +#endif + + nb = (uword)ARENA_ALIGN(pool, nb); /* force alignment */ + + /* attempt to allocate from arenas at pool->current */ + { + a = pool->current; + do { + if ( a->avail +nb <= a->limit ) { + pool->current = a; + rp = (char *)a->avail; + a->avail += nb; + VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb); + return rp; + } + } while( NULL != (a = a->next) ); + } + + /* attempt to allocate from arena_freelist */ + { + Arena *p; /* previous pointer, for unlinking from freelist */ + + for ( a = p = arena_freelist; a != NULL ; p = a, a = a->next ) { + if ( a->base +nb <= a->limit ) { + if ( p == arena_freelist ) + arena_freelist = a->next; + else + p->next = a->next; + a->avail = a->base; + rp = (char *)a->avail; + a->avail += nb; + VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb); + /* the newly allocated arena is linked after pool->current + * and becomes pool->current */ + a->next = pool->current->next; + pool->current->next = a; + pool->current = a; + if ( 0 == pool->first.next ) + pool->first.next = a; + freelist_count--; + return(rp); + } + } + } + + /* attempt to allocate from the heap */ + { + unsigned int sz; +#ifdef HAVE_MMAP + if (pool->cumul > pool->largealloc) { + // High memory pressure. Switch to a fractional allocation strategy + // so that malloc gets a chance to successfully trim us down when it's over. + sz = kMin(pool->cumul/25, MAX_DISCRETE_ALLOCATION(pool)); + } else +#endif + sz = pool->arenasize > nb ? pool->arenasize : nb; + sz += sizeof *a + pool->mask; /* header and alignment slop */ + pool->cumul += sz; +#ifdef DEBUG_ARENA_MALLOC + i++; + printf("Malloc: %d\n", i); +#endif + a = (Arena*)malloc(sz); + if (a) { + a->limit = (uword)a + sz; + a->base = a->avail = (uword)ARENA_ALIGN(pool, a + 1); + VALGRIND_CREATE_MEMPOOL(a->base, 0, 0); + rp = (char *)a->avail; + a->avail += nb; + VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb); + + /* the newly allocated arena is linked after pool->current + * and becomes pool->current */ + a->next = pool->current->next; + pool->current->next = a; + pool->current = a; + if ( !pool->first.next ) + pool->first.next = a; + return(rp); + } + } + + /* we got to here, and there's no memory to allocate */ + return(0); +} /* --- end ArenaAllocate() --- */ + +/* + * Free tail arenas linked after head, which may not be the true list head. + * Reset pool->current to point to head in case it pointed at a tail arena. + */ +static void FreeArenaList(ArenaPool *pool, Arena *head, bool reallyFree) +{ + Arena **ap, *a; + + ap = &head->next; + a = *ap; + if (!a) + return; + +#ifdef DEBUG_ARENA_MALLOC + do { + assert(a->base <= a->avail && a->avail <= a->limit); + a->avail = a->base; + CLEAR_UNUSED(a); + } while ((a = a->next) != 0); + a = *ap; +#endif + + if (freelist_count >= FREELIST_MAX) + reallyFree = true; + + if (reallyFree) { + do { + *ap = a->next; + VALGRIND_DESTROY_MEMPOOL(a->base); + CLEAR_ARENA(a); +#ifdef DEBUG_ARENA_MALLOC + if (a) { + i--; + printf("Free: %d\n", i); + } +#endif + free(a); a = 0; + } while ((a = *ap) != 0); + } else { + /* Insert as much of the arena chain as we can hold at the front of the freelist. */ + do { + ap = &(*ap)->next; + freelist_count++; + } while (*ap && freelist_count < FREELIST_MAX); + + /* Get rid of excess */ + if (*ap) { + Arena *xa, *n; + for (xa = *ap; xa; xa = n) { + VALGRIND_DESTROY_MEMPOOL(xa->base); + n = xa->next; +#ifdef DEBUG_ARENA_MALLOC + i--; + printf("Free: %d\n", i); +#endif + CLEAR_ARENA(xa); + free(xa); + } + } + *ap = arena_freelist; + arena_freelist = a; + head->next = 0; + } + pool->current = head; +} + +void ArenaRelease(ArenaPool *pool, char *mark) +{ + Arena *a; + + for (a = pool->first.next; a; a = a->next) { + if (UPTRDIFF(mark, a->base) < UPTRDIFF(a->avail, a->base)) { + a->avail = (uword)ARENA_ALIGN(pool, mark); + FreeArenaList(pool, a, false); + return; + } + } +} + +void FreeArenaPool(ArenaPool *pool) +{ + FreeArenaList(pool, &pool->first, false); +} + +void FinishArenaPool(ArenaPool *pool) +{ + FreeArenaList(pool, &pool->first, true); +} + +void ArenaFinish() +{ + Arena *a, *next; +#ifdef DEBUG_ARENA_MALLOC + printf("releasing global Arena freelist\n"); +#endif + for (a = arena_freelist; a; a = next) { + next = a->next; + free(a); a = 0; + } + freelist_count = 0; + arena_freelist = NULL; +} + +} // namespace -- cgit v1.2.1