summaryrefslogtreecommitdiff
path: root/nsprpub/lib/ds
diff options
context:
space:
mode:
Diffstat (limited to 'nsprpub/lib/ds')
-rw-r--r--nsprpub/lib/ds/Makefile.in151
-rw-r--r--nsprpub/lib/ds/plarena.c334
-rw-r--r--nsprpub/lib/ds/plarena.h327
-rw-r--r--nsprpub/lib/ds/plarenas.h12
-rw-r--r--nsprpub/lib/ds/plds.def60
-rw-r--r--nsprpub/lib/ds/plds.rc69
-rw-r--r--nsprpub/lib/ds/plhash.c483
-rw-r--r--nsprpub/lib/ds/plhash.h126
-rw-r--r--nsprpub/lib/ds/plvrsion.c93
9 files changed, 1655 insertions, 0 deletions
diff --git a/nsprpub/lib/ds/Makefile.in b/nsprpub/lib/ds/Makefile.in
new file mode 100644
index 0000000000..e73779127e
--- /dev/null
+++ b/nsprpub/lib/ds/Makefile.in
@@ -0,0 +1,151 @@
+#
+# 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),IRIX)
+OS_LIBS = -lc
+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..a582ac6387
--- /dev/null
+++ b/nsprpub/lib/ds/plarena.c
@@ -0,0 +1,334 @@
+/* -*- 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..5336a0e4d4
--- /dev/null
+++ b/nsprpub/lib/ds/plarena.h
@@ -0,0 +1,327 @@
+/* -*- 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)
+
+/* These definitions are usually provided through the
+ * sanitizer/asan_interface.h header installed by ASan.
+ * See https://github.com/google/sanitizers/wiki/AddressSanitizerManualPoisoning
+ */
+
+PR_IMPORT(void) __asan_poison_memory_region(void const volatile *addr, size_t size);
+PR_IMPORT(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..0011df3365
--- /dev/null
+++ b/nsprpub/lib/ds/plhash.c
@@ -0,0 +1,483 @@
+/* -*- 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..e251a5ac03
--- /dev/null
+++ b/nsprpub/lib/ds/plvrsion.c
@@ -0,0 +1,93 @@
+/* -*- 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 */ "Copyright (c) 1998 Netscape Communications Corporation. All Rights Reserved",
+ /* 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 */
+
+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 */
+
+/* plvrsion.c */
+
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-15 02:04:03 +0000