Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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 */
+