diff options
Diffstat (limited to '')
| -rw-r--r-- | nsprpub/lib/ds/Makefile.in | 147 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plarena.c | 348 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plarena.h | 338 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plarenas.h | 12 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plds.def | 60 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plds.rc | 69 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plhash.c | 495 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plhash.h | 126 | ||||
| -rw-r--r-- | nsprpub/lib/ds/plvrsion.c | 100 |
9 files changed, 1695 insertions, 0 deletions
diff --git a/nsprpub/lib/ds/Makefile.in b/nsprpub/lib/ds/Makefile.in new file mode 100644 index 0000000000..38a9e3dd15 --- /dev/null +++ b/nsprpub/lib/ds/Makefile.in @@ -0,0 +1,147 @@ +# +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +#! gmake + +MOD_DEPTH = ../.. +topsrcdir = @top_srcdir@ +srcdir = @srcdir@ +VPATH = @srcdir@ + +include $(MOD_DEPTH)/config/autoconf.mk + +include $(topsrcdir)/config/config.mk + +INCLUDES = -I$(dist_includedir) -I$(topsrcdir)/pr/include + +CSRCS = \ + plarena.c \ + plhash.c \ + plvrsion.c \ + $(NULL) + +HEADERS = \ + plarenas.h \ + plarena.h \ + plhash.h \ + $(NULL) + +HEADERS := $(addprefix $(srcdir)/, $(HEADERS)) + +ifeq ($(OS_ARCH), WINNT) +RES=$(OBJDIR)/plds.res +RESNAME=plds.rc +endif # WINNT + +ifeq ($(OS_ARCH), AIX) +ifeq ($(CLASSIC_NSPR),1) +OS_LIBS = -lc +else +OS_LIBS = -lc_r +endif +endif + +ifeq ($(OS_ARCH),SunOS) +OS_LIBS = -lc +MAPFILE = $(OBJDIR)/pldsmap.sun +GARBAGE += $(MAPFILE) +ifdef NS_USE_GCC +ifdef GCC_USE_GNU_LD +MKSHLIB += -Wl,--version-script,$(MAPFILE) +else +MKSHLIB += -Wl,-M,$(MAPFILE) +endif +else +MKSHLIB += -M $(MAPFILE) +endif +# The -R '$ORIGIN' linker option instructs this library to search for its +# dependencies in the same directory where it resides. +MKSHLIB += -R '$$ORIGIN' +endif + +ifeq ($(OS_ARCH),OS2) +MAPFILE = $(OBJDIR)/$(LIBRARY_NAME)$(LIBRARY_VERSION).def +GARBAGE += $(MAPFILE) +MKSHLIB += $(MAPFILE) +endif + +EXTRA_LIBS = $(LIBNSPR) + +# On SCOOS, we can't link with extra libraries when +# we build a shared library. If we do so, the linker doesn't +# complain, but we would run into weird problems at run-time. +# Therefore on these platforms, we link just the .o files. +ifeq ($(OS_ARCH),SCOOS) +EXTRA_LIBS = +endif + +ifdef RESOLVE_LINK_SYMBOLS +EXTRA_LIBS += $(OS_LIBS) +endif + +LIBRARY_NAME = plds +LIBRARY_VERSION = $(MOD_MAJOR_VERSION) + +RELEASE_HEADERS = $(HEADERS) +RELEASE_HEADERS_DEST = $(RELEASE_INCLUDE_DIR) +RELEASE_LIBS = $(TARGETS) + +include $(topsrcdir)/config/rules.mk + +# +# Version information generation (begin) +# +ECHO = echo +TINC = $(OBJDIR)/_pl_bld.h +PROD = $(notdir $(SHARED_LIBRARY)) +NOW = $(MOD_DEPTH)/config/$(OBJDIR)/now +SH_DATE = $(shell date "+%Y-%m-%d %T") +SH_NOW = $(shell $(NOW)) + +ifeq ($(NS_USE_GCC)_$(OS_ARCH),_WINNT) + SUF = i64 +else + SUF = LL +endif + +GARBAGE += $(TINC) + +$(TINC): + @$(MAKE_OBJDIR) + @$(ECHO) '#define _BUILD_STRING "$(SH_DATE)"' > $(TINC) + @if test ! -z "$(SH_NOW)"; then \ + $(ECHO) '#define _BUILD_TIME $(SH_NOW)$(SUF)' >> $(TINC); \ + else \ + true; \ + fi + @$(ECHO) '#define _PRODUCTION "$(PROD)"' >> $(TINC) + + +$(OBJDIR)/plvrsion.$(OBJ_SUFFIX): plvrsion.c $(TINC) +ifeq ($(NS_USE_GCC)_$(OS_ARCH),_WINNT) + $(CC) -Fo$@ -c $(CFLAGS) -I$(OBJDIR) $< +else + $(CC) -o $@ -c $(CFLAGS) -I$(OBJDIR) $< +endif +# +# Version information generation (end) +# + +# +# The Client build wants the shared libraries in $(dist_bindir), +# so we also install them there. +# + +export:: $(TARGETS) + $(INSTALL) -m 444 $(HEADERS) $(dist_includedir) + $(INSTALL) -m 444 $(TARGETS) $(dist_libdir) +ifdef SHARED_LIBRARY +ifeq ($(OS_ARCH),HP-UX) + $(INSTALL) -m 755 $(SHARED_LIBRARY) $(dist_libdir) + $(INSTALL) -m 755 $(SHARED_LIBRARY) $(dist_bindir) +else + $(INSTALL) -m 444 $(SHARED_LIBRARY) $(dist_bindir) +endif +endif diff --git a/nsprpub/lib/ds/plarena.c b/nsprpub/lib/ds/plarena.c new file mode 100644 index 0000000000..3c6df2b7f7 --- /dev/null +++ b/nsprpub/lib/ds/plarena.c @@ -0,0 +1,348 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + * 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 <stdlib.h> +#include <string.h> +#include "plarena.h" +#include "prmem.h" +#include "prbit.h" +#include "prlog.h" +#include "prlock.h" +#include "prinit.h" + +#ifdef PL_ARENAMETER +static PLArenaStats *arena_stats_list; + +#define COUNT(pool,what) (pool)->stats.what++ +#else +#define COUNT(pool,what) /* nothing */ +#endif + +#define PL_ARENA_DEFAULT_ALIGN sizeof(double) + +PR_IMPLEMENT(void) PL_InitArenaPool( + PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align) +{ + /* + * Look-up table of PR_BITMASK(PR_CeilingLog2(align)) values for + * align = 1 to 32. + */ + static const PRUint8 pmasks[33] = { + 0, /* not used */ + 0, 1, 3, 3, 7, 7, 7, 7,15,15,15,15,15,15,15,15, /* 1 ... 16 */ + 31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31 /* 17 ... 32 */ + }; + + if (align == 0) { + align = PL_ARENA_DEFAULT_ALIGN; + } + + if (align < sizeof(pmasks)/sizeof(pmasks[0])) { + pool->mask = pmasks[align]; + } + else { + pool->mask = PR_BITMASK(PR_CeilingLog2(align)); + } + + pool->first.next = NULL; + /* Set all three addresses in pool->first to the same dummy value. + * These addresses are only compared with each other, but never + * dereferenced. */ + pool->first.base = pool->first.avail = pool->first.limit = + (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1); + pool->current = &pool->first; + /* + * Compute the net size so that each arena's gross size is |size|. + * sizeof(PLArena) + pool->mask is the header and alignment slop + * that PL_ArenaAllocate adds to the net size. + */ + if (size > sizeof(PLArena) + pool->mask) { + pool->arenasize = size - (sizeof(PLArena) + pool->mask); + } + else { + pool->arenasize = size; + } +#ifdef PL_ARENAMETER + memset(&pool->stats, 0, sizeof pool->stats); + pool->stats.name = strdup(name); + pool->stats.next = arena_stats_list; + arena_stats_list = &pool->stats; +#endif +} + + +/* +** PL_ArenaAllocate() -- allocate space from an arena pool +** +** Description: PL_ArenaAllocate() allocates space from an arena +** pool. +** +** First, try to satisfy the request from arenas starting at +** pool->current. Then try to allocate a new arena from the heap. +** +** Returns: pointer to allocated space or NULL +** +** Notes: The original implementation had some difficult to +** solve bugs; the code was difficult to read. Sometimes it's +** just easier to rewrite it. I did that. larryh. +** +** See also: bugzilla: 45343. +** +*/ + +PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb) +{ + PLArena *a; + char *rp; /* returned pointer */ + PRUint32 nbOld; + + PR_ASSERT((nb & pool->mask) == 0); + + nbOld = nb; + nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */ + if (nb < nbOld) { + return NULL; + } + + /* attempt to allocate from arenas at pool->current */ + { + a = pool->current; + do { + if ( nb <= a->limit - a->avail ) { + pool->current = a; + rp = (char *)a->avail; + a->avail += nb; + return rp; + } + } while( NULL != (a = a->next) ); + } + + /* attempt to allocate from the heap */ + { + PRUint32 sz = PR_MAX(pool->arenasize, nb); + if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) { + a = NULL; + } else { + sz += sizeof *a + pool->mask; /* header and alignment slop */ + a = (PLArena*)PR_MALLOC(sz); + } + if ( NULL != a ) { + a->limit = (PRUword)a + sz; + a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1); + PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail); + rp = (char *)a->avail; + a->avail += nb; + PR_ASSERT(a->avail <= a->limit); + /* 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 ( NULL == pool->first.next ) { + pool->first.next = a; + } + PL_COUNT_ARENA(pool,++); + COUNT(pool, nmallocs); + return(rp); + } + } + + /* we got to here, and there's no memory to allocate */ + return(NULL); +} /* --- end PL_ArenaAllocate() --- */ + +PR_IMPLEMENT(void *) PL_ArenaGrow( + PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr) +{ + void *newp; + + if (PR_UINT32_MAX - size < incr) { + return NULL; + } + PL_ARENA_ALLOCATE(newp, pool, size + incr); + if (newp) { + memcpy(newp, p, size); + } + return newp; +} + +PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern) +{ + PLArena *a; + + for (a = pool->first.next; a; a = a->next) { + PR_ASSERT(a->base <= a->avail && a->avail <= a->limit); + a->avail = a->base; + PL_CLEAR_UNUSED_PATTERN(a, pattern); + PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail); + } +} + +/* + * 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(PLArenaPool *pool, PLArena *head) +{ + PLArena *a = head->next; + if (!a) { + return; + } + + head->next = NULL; + + do { + PLArena *tmp = a; + a = a->next; + PL_CLEAR_ARENA(tmp); + PL_COUNT_ARENA(pool,--); + PR_DELETE(tmp); + } while (a); + + pool->current = head; +} + +PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark) +{ + PLArena *a; + + for (a = &pool->first; a; a = a->next) { + if (PR_UPTRDIFF(mark, a->base) <= PR_UPTRDIFF(a->avail, a->base)) { + a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark); + FreeArenaList(pool, a); + return; + } + } +} + +PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool) +{ + FreeArenaList(pool, &pool->first); + COUNT(pool, ndeallocs); +} + +PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool) +{ + FreeArenaList(pool, &pool->first); +#ifdef PL_ARENAMETER + { + PLArenaStats *stats, **statsp; + + if (pool->stats.name) { + PR_DELETE(pool->stats.name); + } + for (statsp = &arena_stats_list; (stats = *statsp) != 0; + statsp = &stats->next) { + if (stats == &pool->stats) { + *statsp = stats->next; + return; + } + } + } +#endif +} + +PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap) +{ +} + +PR_IMPLEMENT(void) PL_ArenaFinish(void) +{ +} + +PR_IMPLEMENT(size_t) PL_SizeOfArenaPoolExcludingPool( + const PLArenaPool *pool, PLMallocSizeFn mallocSizeOf) +{ + /* + * The first PLArena is within |pool|, so don't measure it. Subsequent + * PLArenas are separate and must be measured. + */ + size_t size = 0; + const PLArena *arena = pool->first.next; + while (arena) { + size += mallocSizeOf(arena); + arena = arena->next; + } + return size; +} + +#ifdef PL_ARENAMETER +PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb) +{ + pool->stats.nallocs++; + pool->stats.nbytes += nb; + if (nb > pool->stats.maxalloc) { + pool->stats.maxalloc = nb; + } + pool->stats.variance += nb * nb; +} + +PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth( + PLArenaPool *pool, PRUint32 size, PRUint32 incr) +{ + pool->stats.ninplace++; +} + +PR_IMPLEMENT(void) PL_ArenaCountGrowth( + PLArenaPool *pool, PRUint32 size, PRUint32 incr) +{ + pool->stats.ngrows++; + pool->stats.nbytes += incr; + pool->stats.variance -= size * size; + size += incr; + if (size > pool->stats.maxalloc) { + pool->stats.maxalloc = size; + } + pool->stats.variance += size * size; +} + +PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark) +{ + pool->stats.nreleases++; +} + +PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark) +{ + pool->stats.nfastrels++; +} + +#include <math.h> +#include <stdio.h> + +PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp) +{ + PLArenaStats *stats; + double mean, variance; + + for (stats = arena_stats_list; stats; stats = stats->next) { + if (stats->nallocs != 0) { + mean = (double)stats->nbytes / stats->nallocs; + variance = fabs(stats->variance / stats->nallocs - mean * mean); + } else { + mean = variance = 0; + } + + fprintf(fp, "\n%s allocation statistics:\n", stats->name); + fprintf(fp, " number of arenas: %u\n", stats->narenas); + fprintf(fp, " number of allocations: %u\n", stats->nallocs); + fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims); + fprintf(fp, " number of malloc calls: %u\n", stats->nmallocs); + fprintf(fp, " number of deallocations: %u\n", stats->ndeallocs); + fprintf(fp, " number of allocation growths: %u\n", stats->ngrows); + fprintf(fp, " number of in-place growths: %u\n", stats->ninplace); + fprintf(fp, "number of released allocations: %u\n", stats->nreleases); + fprintf(fp, " number of fast releases: %u\n", stats->nfastrels); + fprintf(fp, " total bytes allocated: %u\n", stats->nbytes); + fprintf(fp, " mean allocation size: %g\n", mean); + fprintf(fp, " standard deviation: %g\n", sqrt(variance)); + fprintf(fp, " maximum allocation size: %u\n", stats->maxalloc); + } +} +#endif /* PL_ARENAMETER */ diff --git a/nsprpub/lib/ds/plarena.h b/nsprpub/lib/ds/plarena.h new file mode 100644 index 0000000000..0ca00c0ac1 --- /dev/null +++ b/nsprpub/lib/ds/plarena.h @@ -0,0 +1,338 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef plarena_h___ +#define plarena_h___ +/* + * 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). + * + * Also supports LIFO allocation (PL_ARENA_MARK/PL_ARENA_RELEASE). + */ +#include "prtypes.h" + +PR_BEGIN_EXTERN_C + +typedef struct PLArena PLArena; + +struct PLArena { + PLArena *next; /* next arena for this lifetime */ + PRUword base; /* aligned base address, follows this header */ + PRUword limit; /* one beyond last byte in arena */ + PRUword avail; /* points to next available byte */ +}; + +#ifdef PL_ARENAMETER +typedef struct PLArenaStats PLArenaStats; + +struct PLArenaStats { + PLArenaStats *next; /* next in arenaStats list */ + char *name; /* name for debugging */ + PRUint32 narenas; /* number of arenas in pool */ + PRUint32 nallocs; /* number of PL_ARENA_ALLOCATE() calls */ + PRUint32 nreclaims; /* number of reclaims from freeArenas */ + PRUint32 nmallocs; /* number of malloc() calls */ + PRUint32 ndeallocs; /* number of lifetime deallocations */ + PRUint32 ngrows; /* number of PL_ARENA_GROW() calls */ + PRUint32 ninplace; /* number of in-place growths */ + PRUint32 nreleases; /* number of PL_ARENA_RELEASE() calls */ + PRUint32 nfastrels; /* number of "fast path" releases */ + PRUint32 nbytes; /* total bytes allocated */ + PRUint32 maxalloc; /* maximum allocation size in bytes */ + PRFloat64 variance; /* size variance accumulator */ +}; +#endif + +typedef struct PLArenaPool PLArenaPool; + +struct PLArenaPool { + PLArena first; /* first arena in pool list */ + PLArena *current; /* arena from which to allocate space */ + PRUint32 arenasize; /* net exact size of a new arena */ + PRUword mask; /* alignment mask (power-of-2 - 1) */ +#ifdef PL_ARENAMETER + PLArenaStats stats; +#endif +}; + +/* + * WARNING: The PL_MAKE_MEM_ macros are for internal use by NSPR. Do NOT use + * them in your code. + * + * NOTE: Valgrind support to be added. + * + * The PL_MAKE_MEM_ macros are modeled after the MOZ_MAKE_MEM_ macros in + * Mozilla's mfbt/MemoryChecking.h. Only AddressSanitizer is supported now. + * + * Provides a common interface to the ASan (AddressSanitizer) and Valgrind + * functions used to mark memory in certain ways. In detail, the following + * three macros are provided: + * + * PL_MAKE_MEM_NOACCESS - Mark memory as unsafe to access (e.g. freed) + * PL_MAKE_MEM_UNDEFINED - Mark memory as accessible, with content undefined + * PL_MAKE_MEM_DEFINED - Mark memory as accessible, with content defined + * + * With Valgrind in use, these directly map to the three respective Valgrind + * macros. With ASan in use, the NOACCESS macro maps to poisoning the memory, + * while the UNDEFINED/DEFINED macros unpoison memory. + * + * With no memory checker available, all macros expand to the empty statement. + */ + +/* WARNING: PL_SANITIZE_ADDRESS is for internal use by this header. Do NOT + * define or test this macro in your code. + */ +#if defined(__has_feature) +#if __has_feature(address_sanitizer) +#define PL_SANITIZE_ADDRESS 1 +#endif +#elif defined(__SANITIZE_ADDRESS__) +#define PL_SANITIZE_ADDRESS 1 +#endif + +#if defined(PL_SANITIZE_ADDRESS) + +#if defined(_MSC_VER) +/* We can't use dllimport due to DLL linkage mismatch with + * sanitizer/asan_interface.h. + */ +#define PL_ASAN_VISIBILITY(type_) type_ +#else +#define PL_ASAN_VISIBILITY(type_) PR_IMPORT(type_) +#endif + +/* These definitions are usually provided through the + * sanitizer/asan_interface.h header installed by ASan. + * See https://github.com/google/sanitizers/wiki/AddressSanitizerManualPoisoning + */ + +PL_ASAN_VISIBILITY(void) __asan_poison_memory_region( + void const volatile *addr, size_t size); +PL_ASAN_VISIBILITY(void) __asan_unpoison_memory_region( + void const volatile *addr, size_t size); + +#define PL_MAKE_MEM_NOACCESS(addr, size) \ + __asan_poison_memory_region((addr), (size)) + +#define PL_MAKE_MEM_UNDEFINED(addr, size) \ + __asan_unpoison_memory_region((addr), (size)) + +#define PL_MAKE_MEM_DEFINED(addr, size) \ + __asan_unpoison_memory_region((addr), (size)) + +#else + +#define PL_MAKE_MEM_NOACCESS(addr, size) +#define PL_MAKE_MEM_UNDEFINED(addr, size) +#define PL_MAKE_MEM_DEFINED(addr, size) + +#endif + +/* + * If the including .c file uses only one power-of-2 alignment, it may define + * PL_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions + * per ALLOCATE and GROW. + */ +#ifdef PL_ARENA_CONST_ALIGN_MASK +#define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + PL_ARENA_CONST_ALIGN_MASK) \ + & ~PL_ARENA_CONST_ALIGN_MASK) + +#define PL_INIT_ARENA_POOL(pool, name, size) \ + PL_InitArenaPool(pool, name, size, PL_ARENA_CONST_ALIGN_MASK + 1) +#else +#define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + (pool)->mask) & ~(pool)->mask) +#endif + +#define PL_ARENA_ALLOCATE(p, pool, nb) \ + PR_BEGIN_MACRO \ + PLArena *_a = (pool)->current; \ + PRUint32 _nb = PL_ARENA_ALIGN(pool, (PRUint32)nb); \ + PRUword _p = _a->avail; \ + if (_nb < (PRUint32)nb) { \ + _p = 0; \ + } else if (_nb > (_a->limit - _a->avail)) { \ + _p = (PRUword)PL_ArenaAllocate(pool, _nb); \ + } else { \ + _a->avail += _nb; \ + } \ + p = (void *)_p; \ + if (p) { \ + PL_MAKE_MEM_UNDEFINED(p, (PRUint32)nb); \ + PL_ArenaCountAllocation(pool, (PRUint32)nb); \ + } \ + PR_END_MACRO + +#define PL_ARENA_GROW(p, pool, size, incr) \ + PR_BEGIN_MACRO \ + PLArena *_a = (pool)->current; \ + PRUint32 _incr = PL_ARENA_ALIGN(pool, (PRUint32)incr); \ + if (_incr < (PRUint32)incr) { \ + p = NULL; \ + } else if (_a->avail == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \ + _incr <= (_a->limit - _a->avail)) { \ + PL_MAKE_MEM_UNDEFINED((unsigned char *)(p) + size, (PRUint32)incr); \ + _a->avail += _incr; \ + PL_ArenaCountInplaceGrowth(pool, size, (PRUint32)incr); \ + } else { \ + p = PL_ArenaGrow(pool, p, size, (PRUint32)incr); \ + } \ + if (p) {\ + PL_ArenaCountGrowth(pool, size, (PRUint32)incr); \ + } \ + PR_END_MACRO + +#define PL_ARENA_MARK(pool) ((void *) (pool)->current->avail) +#define PR_UPTRDIFF(p,q) ((PRUword)(p) - (PRUword)(q)) + +#define PL_CLEAR_UNUSED_PATTERN(a, pattern) \ + PR_BEGIN_MACRO \ + PR_ASSERT((a)->avail <= (a)->limit); \ + PL_MAKE_MEM_UNDEFINED((void*)(a)->avail, (a)->limit - (a)->avail); \ + memset((void*)(a)->avail, (pattern), (a)->limit - (a)->avail); \ + PR_END_MACRO +#ifdef DEBUG +#define PL_FREE_PATTERN 0xDA +#define PL_CLEAR_UNUSED(a) PL_CLEAR_UNUSED_PATTERN((a), PL_FREE_PATTERN) +#define PL_CLEAR_ARENA(a) \ + PR_BEGIN_MACRO \ + PL_MAKE_MEM_UNDEFINED((void*)(a), (a)->limit - (PRUword)(a)); \ + memset((void*)(a), PL_FREE_PATTERN, (a)->limit - (PRUword)(a)); \ + PR_END_MACRO +#else +#define PL_CLEAR_UNUSED(a) +#define PL_CLEAR_ARENA(a) +#endif + +#define PL_ARENA_RELEASE(pool, mark) \ + PR_BEGIN_MACRO \ + char *_m = (char *)(mark); \ + PLArena *_a = (pool)->current; \ + if (PR_UPTRDIFF(_m, _a->base) <= PR_UPTRDIFF(_a->avail, _a->base)) { \ + _a->avail = (PRUword)PL_ARENA_ALIGN(pool, _m); \ + PL_CLEAR_UNUSED(_a); \ + PL_MAKE_MEM_NOACCESS((void*)_a->avail, _a->limit - _a->avail); \ + PL_ArenaCountRetract(pool, _m); \ + } else { \ + PL_ArenaRelease(pool, _m); \ + } \ + PL_ArenaCountRelease(pool, _m); \ + PR_END_MACRO + +#ifdef PL_ARENAMETER +#define PL_COUNT_ARENA(pool,op) ((pool)->stats.narenas op) +#else +#define PL_COUNT_ARENA(pool,op) +#endif + +#define PL_ARENA_DESTROY(pool, a, pnext) \ + PR_BEGIN_MACRO \ + PL_COUNT_ARENA(pool,--); \ + if ((pool)->current == (a)) (pool)->current = &(pool)->first; \ + *(pnext) = (a)->next; \ + PL_CLEAR_ARENA(a); \ + free(a); \ + (a) = 0; \ + PR_END_MACRO + +/* +** Initialize an arena pool with the given name for debugging and metering, +** with a minimum gross size per arena of size bytes. The net size per arena +** is smaller than the gross size by a header of four pointers plus any +** necessary padding for alignment. +** +** Note: choose a gross size that's a power of two to avoid the heap allocator +** rounding the size up. +**/ +PR_EXTERN(void) PL_InitArenaPool( + PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align); + +/* +** Finish using arenas, freeing all memory associated with them. +** NOTE: this function is now a no-op. If you want to free a single +** PLArenaPoolUse use PL_FreeArenaPool() or PL_FinishArenaPool(). +**/ +PR_EXTERN(void) PL_ArenaFinish(void); + +/* +** Free the arenas in pool. The user may continue to allocate from pool +** after calling this function. There is no need to call PL_InitArenaPool() +** again unless PL_FinishArenaPool(pool) has been called. +**/ +PR_EXTERN(void) PL_FreeArenaPool(PLArenaPool *pool); + +/* +** Free the arenas in pool and finish using it altogether. +**/ +PR_EXTERN(void) PL_FinishArenaPool(PLArenaPool *pool); + +/* +** Compact all of the arenas in a pool so that no space is wasted. +** NOT IMPLEMENTED. Do not use. +**/ +PR_EXTERN(void) PL_CompactArenaPool(PLArenaPool *pool); + +/* +** Friend functions used by the PL_ARENA_*() macros. +** +** WARNING: do not call these functions directly. Always use the +** PL_ARENA_*() macros. +**/ +PR_EXTERN(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb); + +PR_EXTERN(void *) PL_ArenaGrow( + PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr); + +PR_EXTERN(void) PL_ArenaRelease(PLArenaPool *pool, char *mark); + +/* +** memset contents of all arenas in pool to pattern +*/ +PR_EXTERN(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern); + +/* +** A function like malloc_size() or malloc_usable_size() that measures the +** size of a heap block. +*/ +typedef size_t (*PLMallocSizeFn)(const void *ptr); + +/* +** Measure all memory used by a PLArenaPool, excluding the PLArenaPool +** structure. +*/ +PR_EXTERN(size_t) PL_SizeOfArenaPoolExcludingPool( + const PLArenaPool *pool, PLMallocSizeFn mallocSizeOf); + +#ifdef PL_ARENAMETER + +#include <stdio.h> + +PR_EXTERN(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb); + +PR_EXTERN(void) PL_ArenaCountInplaceGrowth( + PLArenaPool *pool, PRUint32 size, PRUint32 incr); + +PR_EXTERN(void) PL_ArenaCountGrowth( + PLArenaPool *pool, PRUint32 size, PRUint32 incr); + +PR_EXTERN(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark); + +PR_EXTERN(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark); + +PR_EXTERN(void) PL_DumpArenaStats(FILE *fp); + +#else /* !PL_ARENAMETER */ + +#define PL_ArenaCountAllocation(ap, nb) /* nothing */ +#define PL_ArenaCountInplaceGrowth(ap, size, incr) /* nothing */ +#define PL_ArenaCountGrowth(ap, size, incr) /* nothing */ +#define PL_ArenaCountRelease(ap, mark) /* nothing */ +#define PL_ArenaCountRetract(ap, mark) /* nothing */ + +#endif /* !PL_ARENAMETER */ + +PR_END_EXTERN_C + +#endif /* plarena_h___ */ diff --git a/nsprpub/lib/ds/plarenas.h b/nsprpub/lib/ds/plarenas.h new file mode 100644 index 0000000000..4a0f5a8d5b --- /dev/null +++ b/nsprpub/lib/ds/plarenas.h @@ -0,0 +1,12 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* +** PLArena-related declarations used to be split between plarenas.h and +** plarena.h. That split wasn't useful, so now all the declarations are in +** plarena.h. However, this file still exists so that any old code that +** includes it will still work. +**/ +#include "plarena.h" diff --git a/nsprpub/lib/ds/plds.def b/nsprpub/lib/ds/plds.def new file mode 100644 index 0000000000..cc54a4de2e --- /dev/null +++ b/nsprpub/lib/ds/plds.def @@ -0,0 +1,60 @@ +;+# +;+# This Source Code Form is subject to the terms of the Mozilla Public +;+# License, v. 2.0. If a copy of the MPL was not distributed with this +;+# file, You can obtain one at http://mozilla.org/MPL/2.0/. +;+# +;+# OK, this file is meant to support SUN, LINUX, AIX, OS/2 and WINDOWS +;+# 1. For all unix platforms, the string ";-" means "remove this line" +;+# 2. For all unix platforms, the string " DATA " will be removed from any +;+# line on which it occurs. +;+# 3. Lines containing ";+" will have ";+" removed on SUN and LINUX. +;+# On AIX, lines containing ";+" will be removed. +;+# 4. For all unix platforms, the string ";;" will thave the ";;" removed. +;+# 5. For all unix platforms, after the above processing has taken place, +;+# all characters after the first ";" on the line will be removed. +;+# And for AIX, the first ";" will also be removed. +;+# This file is passed directly to windows. Since ';' is a comment, all UNIX +;+# directives are hidden behind ";", ";+", and ";-" +;+NSPR_4.0 { +;+ global: +LIBRARY plds4 ;- +EXPORTS ;- +PL_ArenaAllocate; +PL_ArenaFinish; +PL_ArenaGrow; +PL_ArenaRelease; +PL_CompactArenaPool; +PL_CompareStrings; +PL_CompareValues; +PL_FinishArenaPool; +PL_FreeArenaPool; +PL_HashString; +PL_HashTableAdd; +PL_HashTableDestroy; +PL_HashTableDump; +PL_HashTableEnumerateEntries; +PL_HashTableLookup; +PL_HashTableRawAdd; +PL_HashTableRawLookup; +PL_HashTableRawRemove; +PL_HashTableRemove; +PL_InitArenaPool; +PL_NewHashTable; +libVersionPoint; +;+ local: *; +;+}; +;+ +;+NSPR_4.1 { +;+ global: +PL_HashTableLookupConst; +PL_HashTableRawLookupConst; +;+} NSPR_4.0; +;+ +;+NSPR_4.8.5 { +;+ global: +PL_ClearArenaPool; +;+} NSPR_4.1; +;+NSPR_4.9.6 { +;+ global: +PL_SizeOfArenaPoolExcludingPool; +;+} NSPR_4.8.5; diff --git a/nsprpub/lib/ds/plds.rc b/nsprpub/lib/ds/plds.rc new file mode 100644 index 0000000000..d8017e732e --- /dev/null +++ b/nsprpub/lib/ds/plds.rc @@ -0,0 +1,69 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "prinit.h" +#include <winver.h> + +#define MY_LIBNAME "plds" +#define MY_FILEDESCRIPTION "PLDS Library" + +#define STRINGIZE(x) #x +#define STRINGIZE2(x) STRINGIZE(x) +#define PR_VMAJOR_STR STRINGIZE2(PR_VMAJOR) + +#ifdef _DEBUG +#define MY_DEBUG_STR " (debug)" +#define MY_FILEFLAGS_1 VS_FF_DEBUG +#else +#define MY_DEBUG_STR "" +#define MY_FILEFLAGS_1 0x0L +#endif +#if PR_BETA +#define MY_FILEFLAGS_2 MY_FILEFLAGS_1|VS_FF_PRERELEASE +#else +#define MY_FILEFLAGS_2 MY_FILEFLAGS_1 +#endif + +#ifdef WINNT +#define MY_FILEOS VOS_NT_WINDOWS32 +#define MY_INTERNAL_NAME "lib" MY_LIBNAME PR_VMAJOR_STR +#else +#define MY_FILEOS VOS__WINDOWS32 +#define MY_INTERNAL_NAME MY_LIBNAME PR_VMAJOR_STR +#endif + +///////////////////////////////////////////////////////////////////////////// +// +// Version-information resource +// + +VS_VERSION_INFO VERSIONINFO + FILEVERSION PR_VMAJOR,PR_VMINOR,PR_VPATCH,0 + PRODUCTVERSION PR_VMAJOR,PR_VMINOR,PR_VPATCH,0 + FILEFLAGSMASK VS_FFI_FILEFLAGSMASK + FILEFLAGS MY_FILEFLAGS_2 + FILEOS MY_FILEOS + FILETYPE VFT_DLL + FILESUBTYPE 0x0L // not used + +BEGIN + BLOCK "StringFileInfo" + BEGIN + BLOCK "040904B0" // Lang=US English, CharSet=Unicode + BEGIN + VALUE "CompanyName", "Mozilla Foundation\0" + VALUE "FileDescription", MY_FILEDESCRIPTION MY_DEBUG_STR "\0" + VALUE "FileVersion", PR_VERSION "\0" + VALUE "InternalName", MY_INTERNAL_NAME "\0" + VALUE "OriginalFilename", MY_INTERNAL_NAME ".dll\0" + VALUE "ProductName", "Netscape Portable Runtime\0" + VALUE "ProductVersion", PR_VERSION "\0" + END + END + BLOCK "VarFileInfo" + BEGIN + VALUE "Translation", 0x409, 1200 + END +END diff --git a/nsprpub/lib/ds/plhash.c b/nsprpub/lib/ds/plhash.c new file mode 100644 index 0000000000..95497f06fe --- /dev/null +++ b/nsprpub/lib/ds/plhash.c @@ -0,0 +1,495 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + * PL hash table package. + */ +#include "plhash.h" +#include "prbit.h" +#include "prlog.h" +#include "prmem.h" +#include "prtypes.h" +#include <stdlib.h> +#include <string.h> + +/* Compute the number of buckets in ht */ +#define NBUCKETS(ht) (1 << (PL_HASH_BITS - (ht)->shift)) + +/* The smallest table has 16 buckets */ +#define MINBUCKETSLOG2 4 +#define MINBUCKETS (1 << MINBUCKETSLOG2) + +/* Compute the maximum entries given n buckets that we will tolerate, ~90% */ +#define OVERLOADED(n) ((n) - ((n) >> 3)) + +/* Compute the number of entries below which we shrink the table by half */ +#define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0) + +/* +** Stubs for default hash allocator ops. +*/ +static void * PR_CALLBACK +DefaultAllocTable(void *pool, PRSize size) +{ + return PR_MALLOC(size); +} + +static void PR_CALLBACK +DefaultFreeTable(void *pool, void *item) +{ + PR_Free(item); +} + +static PLHashEntry * PR_CALLBACK +DefaultAllocEntry(void *pool, const void *key) +{ + return PR_NEW(PLHashEntry); +} + +static void PR_CALLBACK +DefaultFreeEntry(void *pool, PLHashEntry *he, PRUintn flag) +{ + if (flag == HT_FREE_ENTRY) { + PR_Free(he); + } +} + +static PLHashAllocOps defaultHashAllocOps = { + DefaultAllocTable, DefaultFreeTable, + DefaultAllocEntry, DefaultFreeEntry +}; + +PR_IMPLEMENT(PLHashTable *) +PL_NewHashTable(PRUint32 n, PLHashFunction keyHash, + PLHashComparator keyCompare, PLHashComparator valueCompare, + const PLHashAllocOps *allocOps, void *allocPriv) +{ + PLHashTable *ht; + PRSize nb; + + if (n <= MINBUCKETS) { + n = MINBUCKETSLOG2; + } else { + n = PR_CeilingLog2(n); + if ((PRInt32)n < 0) { + return 0; + } + } + + if (!allocOps) { + allocOps = &defaultHashAllocOps; + } + + ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht)); + if (!ht) { + return 0; + } + memset(ht, 0, sizeof *ht); + ht->shift = PL_HASH_BITS - n; + n = 1 << n; + nb = n * sizeof(PLHashEntry *); + ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb)); + if (!ht->buckets) { + (*allocOps->freeTable)(allocPriv, ht); + return 0; + } + memset(ht->buckets, 0, nb); + + ht->keyHash = keyHash; + ht->keyCompare = keyCompare; + ht->valueCompare = valueCompare; + ht->allocOps = allocOps; + ht->allocPriv = allocPriv; + return ht; +} + +PR_IMPLEMENT(void) +PL_HashTableDestroy(PLHashTable *ht) +{ + PRUint32 i, n; + PLHashEntry *he, *next; + const PLHashAllocOps *allocOps = ht->allocOps; + void *allocPriv = ht->allocPriv; + + n = NBUCKETS(ht); + for (i = 0; i < n; i++) { + for (he = ht->buckets[i]; he; he = next) { + next = he->next; + (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY); + } + } +#ifdef DEBUG + memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]); +#endif + (*allocOps->freeTable)(allocPriv, ht->buckets); +#ifdef DEBUG + memset(ht, 0xDB, sizeof *ht); +#endif + (*allocOps->freeTable)(allocPriv, ht); +} + +/* +** Multiplicative hash, from Knuth 6.4. +*/ +#define GOLDEN_RATIO 0x9E3779B9U /* 2/(1+sqrt(5))*(2^32) */ + +PR_IMPLEMENT(PLHashEntry **) +PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key) +{ + PLHashEntry *he, **hep, **hep0; + PLHashNumber h; + +#ifdef HASHMETER + ht->nlookups++; +#endif + h = keyHash * GOLDEN_RATIO; + h >>= ht->shift; + hep = hep0 = &ht->buckets[h]; + while ((he = *hep) != 0) { + if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) { + /* Move to front of chain if not already there */ + if (hep != hep0) { + *hep = he->next; + he->next = *hep0; + *hep0 = he; + } + return hep0; + } + hep = &he->next; +#ifdef HASHMETER + ht->nsteps++; +#endif + } + return hep; +} + +/* +** Same as PL_HashTableRawLookup but doesn't reorder the hash entries. +*/ +PR_IMPLEMENT(PLHashEntry **) +PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, + const void *key) +{ + PLHashEntry *he, **hep; + PLHashNumber h; + +#ifdef HASHMETER + ht->nlookups++; +#endif + h = keyHash * GOLDEN_RATIO; + h >>= ht->shift; + hep = &ht->buckets[h]; + while ((he = *hep) != 0) { + if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) { + break; + } + hep = &he->next; +#ifdef HASHMETER + ht->nsteps++; +#endif + } + return hep; +} + +PR_IMPLEMENT(PLHashEntry *) +PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, + PLHashNumber keyHash, const void *key, void *value) +{ + PRUint32 i, n; + PLHashEntry *he, *next, **oldbuckets; + PRSize nb; + + /* Grow the table if it is overloaded */ + n = NBUCKETS(ht); + if (ht->nentries >= OVERLOADED(n)) { + oldbuckets = ht->buckets; + nb = 2 * n * sizeof(PLHashEntry *); + ht->buckets = (PLHashEntry**) + ((*ht->allocOps->allocTable)(ht->allocPriv, nb)); + if (!ht->buckets) { + ht->buckets = oldbuckets; + return 0; + } + memset(ht->buckets, 0, nb); +#ifdef HASHMETER + ht->ngrows++; +#endif + ht->shift--; + + for (i = 0; i < n; i++) { + for (he = oldbuckets[i]; he; he = next) { + next = he->next; + hep = PL_HashTableRawLookup(ht, he->keyHash, he->key); + PR_ASSERT(*hep == 0); + he->next = 0; + *hep = he; + } + } +#ifdef DEBUG + memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]); +#endif + (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets); + hep = PL_HashTableRawLookup(ht, keyHash, key); + } + + /* Make a new key value entry */ + he = (*ht->allocOps->allocEntry)(ht->allocPriv, key); + if (!he) { + return 0; + } + he->keyHash = keyHash; + he->key = key; + he->value = value; + he->next = *hep; + *hep = he; + ht->nentries++; + return he; +} + +PR_IMPLEMENT(PLHashEntry *) +PL_HashTableAdd(PLHashTable *ht, const void *key, void *value) +{ + PLHashNumber keyHash; + PLHashEntry *he, **hep; + + keyHash = (*ht->keyHash)(key); + hep = PL_HashTableRawLookup(ht, keyHash, key); + if ((he = *hep) != 0) { + /* Hit; see if values match */ + if ((*ht->valueCompare)(he->value, value)) { + /* key,value pair is already present in table */ + return he; + } + if (he->value) { + (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE); + } + he->value = value; + return he; + } + return PL_HashTableRawAdd(ht, hep, keyHash, key, value); +} + +PR_IMPLEMENT(void) +PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he) +{ + PRUint32 i, n; + PLHashEntry *next, **oldbuckets; + PRSize nb; + + *hep = he->next; + (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY); + + /* Shrink table if it's underloaded */ + n = NBUCKETS(ht); + if (--ht->nentries < UNDERLOADED(n)) { + oldbuckets = ht->buckets; + nb = n * sizeof(PLHashEntry*) / 2; + ht->buckets = (PLHashEntry**)( + (*ht->allocOps->allocTable)(ht->allocPriv, nb)); + if (!ht->buckets) { + ht->buckets = oldbuckets; + return; + } + memset(ht->buckets, 0, nb); +#ifdef HASHMETER + ht->nshrinks++; +#endif + ht->shift++; + + for (i = 0; i < n; i++) { + for (he = oldbuckets[i]; he; he = next) { + next = he->next; + hep = PL_HashTableRawLookup(ht, he->keyHash, he->key); + PR_ASSERT(*hep == 0); + he->next = 0; + *hep = he; + } + } +#ifdef DEBUG + memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]); +#endif + (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets); + } +} + +PR_IMPLEMENT(PRBool) +PL_HashTableRemove(PLHashTable *ht, const void *key) +{ + PLHashNumber keyHash; + PLHashEntry *he, **hep; + + keyHash = (*ht->keyHash)(key); + hep = PL_HashTableRawLookup(ht, keyHash, key); + if ((he = *hep) == 0) { + return PR_FALSE; + } + + /* Hit; remove element */ + PL_HashTableRawRemove(ht, hep, he); + return PR_TRUE; +} + +PR_IMPLEMENT(void *) +PL_HashTableLookup(PLHashTable *ht, const void *key) +{ + PLHashNumber keyHash; + PLHashEntry *he, **hep; + + keyHash = (*ht->keyHash)(key); + hep = PL_HashTableRawLookup(ht, keyHash, key); + if ((he = *hep) != 0) { + return he->value; + } + return 0; +} + +/* +** Same as PL_HashTableLookup but doesn't reorder the hash entries. +*/ +PR_IMPLEMENT(void *) +PL_HashTableLookupConst(PLHashTable *ht, const void *key) +{ + PLHashNumber keyHash; + PLHashEntry *he, **hep; + + keyHash = (*ht->keyHash)(key); + hep = PL_HashTableRawLookupConst(ht, keyHash, key); + if ((he = *hep) != 0) { + return he->value; + } + return 0; +} + +/* +** Iterate over the entries in the hash table calling func for each +** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP). +** Return a count of the number of elements scanned. +*/ +PR_IMPLEMENT(int) +PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg) +{ + PLHashEntry *he, **hep; + PRUint32 i, nbuckets; + int rv, n = 0; + PLHashEntry *todo = 0; + + nbuckets = NBUCKETS(ht); + for (i = 0; i < nbuckets; i++) { + hep = &ht->buckets[i]; + while ((he = *hep) != 0) { + rv = (*f)(he, n, arg); + n++; + if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) { + *hep = he->next; + if (rv & HT_ENUMERATE_REMOVE) { + he->next = todo; + todo = he; + } + } else { + hep = &he->next; + } + if (rv & HT_ENUMERATE_STOP) { + goto out; + } + } + } + +out: + hep = &todo; + while ((he = *hep) != 0) { + PL_HashTableRawRemove(ht, hep, he); + } + return n; +} + +#ifdef HASHMETER +#include <math.h> +#include <stdio.h> + +PR_IMPLEMENT(void) +PL_HashTableDumpMeter(PLHashTable *ht, PLHashEnumerator dump, FILE *fp) +{ + double mean, variance; + PRUint32 nchains, nbuckets; + PRUint32 i, n, maxChain, maxChainLen; + PLHashEntry *he; + + variance = 0; + nchains = 0; + maxChainLen = 0; + nbuckets = NBUCKETS(ht); + for (i = 0; i < nbuckets; i++) { + he = ht->buckets[i]; + if (!he) { + continue; + } + nchains++; + for (n = 0; he; he = he->next) { + n++; + } + variance += n * n; + if (n > maxChainLen) { + maxChainLen = n; + maxChain = i; + } + } + mean = (double)ht->nentries / nchains; + variance = fabs(variance / nchains - mean * mean); + + fprintf(fp, "\nHash table statistics:\n"); + fprintf(fp, " number of lookups: %u\n", ht->nlookups); + fprintf(fp, " number of entries: %u\n", ht->nentries); + fprintf(fp, " number of grows: %u\n", ht->ngrows); + fprintf(fp, " number of shrinks: %u\n", ht->nshrinks); + fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps + / ht->nlookups); + fprintf(fp, "mean hash chain length: %g\n", mean); + fprintf(fp, " standard deviation: %g\n", sqrt(variance)); + fprintf(fp, " max hash chain length: %u\n", maxChainLen); + fprintf(fp, " max hash chain: [%u]\n", maxChain); + + for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++) + if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT) { + break; + } +} +#endif /* HASHMETER */ + +PR_IMPLEMENT(int) +PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp) +{ + int count; + + count = PL_HashTableEnumerateEntries(ht, dump, fp); +#ifdef HASHMETER + PL_HashTableDumpMeter(ht, dump, fp); +#endif + return count; +} + +PR_IMPLEMENT(PLHashNumber) +PL_HashString(const void *key) +{ + PLHashNumber h; + const PRUint8 *s; + + h = 0; + for (s = (const PRUint8*)key; *s; s++) { + h = PR_ROTATE_LEFT32(h, 4) ^ *s; + } + return h; +} + +PR_IMPLEMENT(int) +PL_CompareStrings(const void *v1, const void *v2) +{ + return strcmp((const char*)v1, (const char*)v2) == 0; +} + +PR_IMPLEMENT(int) +PL_CompareValues(const void *v1, const void *v2) +{ + return v1 == v2; +} diff --git a/nsprpub/lib/ds/plhash.h b/nsprpub/lib/ds/plhash.h new file mode 100644 index 0000000000..2c221aed77 --- /dev/null +++ b/nsprpub/lib/ds/plhash.h @@ -0,0 +1,126 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef plhash_h___ +#define plhash_h___ +/* + * API to portable hash table code. + */ +#include <stdio.h> +#include "prtypes.h" + +PR_BEGIN_EXTERN_C + +typedef struct PLHashEntry PLHashEntry; +typedef struct PLHashTable PLHashTable; +typedef PRUint32 PLHashNumber; +#define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */ +typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key); +typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2); + +typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg); + +/* Flag bits in PLHashEnumerator's return value */ +#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ +#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ +#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ +#define HT_ENUMERATE_UNHASH 4 /* just unhash the current entry */ + +typedef struct PLHashAllocOps { + void * (PR_CALLBACK *allocTable)(void *pool, PRSize size); + void (PR_CALLBACK *freeTable)(void *pool, void *item); + PLHashEntry * (PR_CALLBACK *allocEntry)(void *pool, const void *key); + void (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag); +} PLHashAllocOps; + +#define HT_FREE_VALUE 0 /* just free the entry's value */ +#define HT_FREE_ENTRY 1 /* free value and entire entry */ + +struct PLHashEntry { + PLHashEntry *next; /* hash chain linkage */ + PLHashNumber keyHash; /* key hash function result */ + const void *key; /* ptr to opaque key */ + void *value; /* ptr to opaque value */ +}; + +struct PLHashTable { + PLHashEntry **buckets; /* vector of hash buckets */ + PRUint32 nentries; /* number of entries in table */ + PRUint32 shift; /* multiplicative hash shift */ + PLHashFunction keyHash; /* key hash function */ + PLHashComparator keyCompare; /* key comparison function */ + PLHashComparator valueCompare; /* value comparison function */ + const PLHashAllocOps *allocOps; /* allocation operations */ + void *allocPriv; /* allocation private data */ +#ifdef HASHMETER + PRUint32 nlookups; /* total number of lookups */ + PRUint32 nsteps; /* number of hash chains traversed */ + PRUint32 ngrows; /* number of table expansions */ + PRUint32 nshrinks; /* number of table contractions */ +#endif +}; + +/* + * Create a new hash table. + * If allocOps is null, use default allocator ops built on top of malloc(). + */ +PR_EXTERN(PLHashTable *) +PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash, + PLHashComparator keyCompare, PLHashComparator valueCompare, + const PLHashAllocOps *allocOps, void *allocPriv); + +PR_EXTERN(void) +PL_HashTableDestroy(PLHashTable *ht); + +/* Higher level access methods */ +PR_EXTERN(PLHashEntry *) +PL_HashTableAdd(PLHashTable *ht, const void *key, void *value); + +PR_EXTERN(PRBool) +PL_HashTableRemove(PLHashTable *ht, const void *key); + +PR_EXTERN(void *) +PL_HashTableLookup(PLHashTable *ht, const void *key); + +PR_EXTERN(void *) +PL_HashTableLookupConst(PLHashTable *ht, const void *key); + +PR_EXTERN(PRIntn) +PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg); + +/* General-purpose C string hash function. */ +PR_EXTERN(PLHashNumber) +PL_HashString(const void *key); + +/* Compare strings using strcmp(), return true if equal. */ +PR_EXTERN(PRIntn) +PL_CompareStrings(const void *v1, const void *v2); + +/* Stub function just returns v1 == v2 */ +PR_EXTERN(PRIntn) +PL_CompareValues(const void *v1, const void *v2); + +/* Low level access methods */ +PR_EXTERN(PLHashEntry **) +PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key); + +PR_EXTERN(PLHashEntry **) +PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, + const void *key); + +PR_EXTERN(PLHashEntry *) +PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash, + const void *key, void *value); + +PR_EXTERN(void) +PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he); + +/* This can be trivially implemented using PL_HashTableEnumerateEntries. */ +PR_EXTERN(PRIntn) +PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp); + +PR_END_EXTERN_C + +#endif /* plhash_h___ */ diff --git a/nsprpub/lib/ds/plvrsion.c b/nsprpub/lib/ds/plvrsion.c new file mode 100644 index 0000000000..14c1d676e6 --- /dev/null +++ b/nsprpub/lib/ds/plvrsion.c @@ -0,0 +1,100 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "prinit.h" +#include "prvrsion.h" + +/************************************************************************/ +/**************************IDENTITY AND VERSIONING***********************/ +/************************************************************************/ +#include "_pl_bld.h" +#if !defined(_BUILD_TIME) +#ifdef HAVE_LONG_LONG +#define _BUILD_TIME 0 +#else +#define _BUILD_TIME {0, 0} +#endif +#endif +#if !defined(_BUILD_STRING) +#define _BUILD_STRING "" +#endif +#if !defined(_PRODUCTION) +#define _PRODUCTION "" +#endif +#if defined(DEBUG) +#define _DEBUG_STRING " (debug)" +#else +#define _DEBUG_STRING "" +#endif + +/* + * A trick to expand the PR_VMAJOR macro before concatenation. + */ +#define CONCAT(x, y) x ## y +#define CONCAT2(x, y) CONCAT(x, y) +#define VERSION_DESC_NAME CONCAT2(prVersionDescription_libplds, PR_VMAJOR) + +PRVersionDescription VERSION_DESC_NAME = +{ + /* version */ 2, /* this is the only one supported */ + /* buildTime */ _BUILD_TIME, /* usecs since midnight 1/1/1970 GMT */ + /* buildTimeString */ _BUILD_STRING, /* ditto, but human readable */ + /* vMajor */ PR_VMAJOR, /* NSPR's version number */ + /* vMinor */ PR_VMINOR, /* and minor version */ + /* vPatch */ PR_VPATCH, /* and patch */ + /* beta */ PR_BETA, /* beta build boolean */ +#if defined(DEBUG) + /* debug */ PR_TRUE, /* a debug build */ +#else + /* debug */ PR_FALSE, /* an optomized build */ +#endif + /* special */ PR_FALSE, /* they're all special, but ... */ + /* filename */ _PRODUCTION, /* the produced library name */ + /* description */ "Portable runtime", /* what we are */ + /* security */ "N/A", /* not applicable here */ + /* copywrite */ "This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.", + /* comment */ "http://www.mozilla.org/MPL/", + /* specialString */ "" +}; + +#ifdef XP_UNIX + +/* + * Version information for the 'ident' and 'what commands + * + * NOTE: the first component of the concatenated rcsid string + * must not end in a '$' to prevent rcs keyword substitution. + */ +static char rcsid[] = "$Header: NSPR " PR_VERSION _DEBUG_STRING + " " _BUILD_STRING " $"; +static char sccsid[] = "@(#)NSPR " PR_VERSION _DEBUG_STRING + " " _BUILD_STRING; + +#endif /* XP_UNIX */ + +#ifdef _PR_HAS_PRAGMA_DIAGNOSTIC +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-but-set-variable" +#endif +PR_IMPLEMENT(const PRVersionDescription*) libVersionPoint() +{ +#ifdef XP_UNIX + /* + * Add dummy references to rcsid and sccsid to prevent them + * from being optimized away as unused variables. + */ + const char *dummy; + + dummy = rcsid; + dummy = sccsid; +#endif + return &VERSION_DESC_NAME; +} /* versionEntryPointType */ +#ifdef _PR_HAS_PRAGMA_DIAGNOSTIC +#pragma GCC diagnostic pop +#endif + +/* plvrsion.c */ + |