diff options
Diffstat (limited to 'mozilla/nsprpub/lib/ds')
| -rw-r--r-- | mozilla/nsprpub/lib/ds/.cvsignore | 2 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/Makefile.in | 186 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plarena.c | 443 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plarena.h | 214 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plarenas.h | 92 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plds.def | 88 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plds.rc | 101 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plhash.c | 515 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plhash.h | 158 | ||||
| -rw-r--r-- | mozilla/nsprpub/lib/ds/plvrsion.c | 125 |
10 files changed, 1924 insertions, 0 deletions
diff --git a/mozilla/nsprpub/lib/ds/.cvsignore b/mozilla/nsprpub/lib/ds/.cvsignore new file mode 100644 index 0000000..bcab60f --- /dev/null +++ b/mozilla/nsprpub/lib/ds/.cvsignore @@ -0,0 +1,2 @@ +Makefile +_pl_bld.h diff --git a/mozilla/nsprpub/lib/ds/Makefile.in b/mozilla/nsprpub/lib/ds/Makefile.in new file mode 100644 index 0000000..82dca03 --- /dev/null +++ b/mozilla/nsprpub/lib/ds/Makefile.in @@ -0,0 +1,186 @@ +# +# ***** BEGIN LICENSE BLOCK ***** +# Version: MPL 1.1/GPL 2.0/LGPL 2.1 +# +# The contents of this file are subject to the Mozilla Public License Version +# 1.1 (the "License"); you may not use this file except in compliance with +# the License. You may obtain a copy of the License at +# http://www.mozilla.org/MPL/ +# +# Software distributed under the License is distributed on an "AS IS" basis, +# WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License +# for the specific language governing rights and limitations under the +# License. +# +# The Original Code is the Netscape Portable Runtime (NSPR). +# +# The Initial Developer of the Original Code is +# Netscape Communications Corporation. +# Portions created by the Initial Developer are Copyright (C) 1998-2000 +# the Initial Developer. All Rights Reserved. +# +# Contributor(s): +# +# Alternatively, the contents of this file may be used under the terms of +# either the GNU General Public License Version 2 or later (the "GPL"), or +# the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), +# in which case the provisions of the GPL or the LGPL are applicable instead +# of those above. If you wish to allow use of your version of this file only +# under the terms of either the GPL or the LGPL, and not to allow others to +# use your version of this file under the terms of the MPL, indicate your +# decision by deleting the provisions above and replace them with the notice +# and other provisions required by the GPL or the LGPL. If you do not delete +# the provisions above, a recipient may use your version of this file under +# the terms of any one of the MPL, the GPL or the LGPL. +# +# ***** END LICENSE BLOCK ***** + +#! 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 NCR and 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),NCR) +EXTRA_LIBS = +endif +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/mozilla/nsprpub/lib/ds/plarena.c b/mozilla/nsprpub/lib/ds/plarena.c new file mode 100644 index 0000000..22dae78 --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plarena.c @@ -0,0 +1,443 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is Netscape + * Communications Corporation. Portions created by Netscape are + * Copyright (C) 1998-2000 Netscape Communications Corporation. All + * Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** + */ + +/* + * 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" + +static PLArena *arena_freelist; + +#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) + +static PRLock *arenaLock; +static PRCallOnceType once; +static const PRCallOnceType pristineCallOnce; + +/* +** InitializeArenas() -- Initialize arena operations. +** +** InitializeArenas() is called exactly once and only once from +** LockArena(). This function creates the arena protection +** lock: arenaLock. +** +** Note: If the arenaLock cannot be created, InitializeArenas() +** fails quietly, returning only PR_FAILURE. This percolates up +** to the application using the Arena API. He gets no arena +** from PL_ArenaAllocate(). It's up to him to fail gracefully +** or recover. +** +*/ +static PRStatus InitializeArenas( void ) +{ + PR_ASSERT( arenaLock == NULL ); + arenaLock = PR_NewLock(); + if ( arenaLock == NULL ) + return PR_FAILURE; + else + return PR_SUCCESS; +} /* end ArenaInitialize() */ + +static PRStatus LockArena( void ) +{ + PRStatus rc = PR_CallOnce( &once, InitializeArenas ); + + if ( PR_FAILURE != rc ) + PR_Lock( arenaLock ); + return(rc); +} /* end LockArena() */ + +static void UnlockArena( void ) +{ + PR_Unlock( arenaLock ); + return; +} /* end UnlockArena() */ + +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; + pool->first.base = pool->first.avail = pool->first.limit = + (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1); + pool->current = &pool->first; + 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. +** +** If there is not enough space in the arena pool->current, try +** to claim an arena, on a first fit basis, from the global +** freelist (arena_freelist). +** +** If no arena in arena_freelist is suitable, then try to +** allocate a new arena from the heap. +** +** Returns: pointer to allocated space or NULL +** +** 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 */ + + PR_ASSERT((nb & pool->mask) == 0); + + nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */ + + /* attempt to allocate from arenas at pool->current */ + { + a = pool->current; + do { + if ( a->avail +nb <= a->limit ) { + pool->current = a; + rp = (char *)a->avail; + a->avail += nb; + return rp; + } + } while( NULL != (a = a->next) ); + } + + /* attempt to allocate from arena_freelist */ + { + PLArena *p; /* previous pointer, for unlinking from freelist */ + + /* lock the arena_freelist. Make access to the freelist MT-Safe */ + if ( PR_FAILURE == LockArena()) + return(0); + + for ( a = arena_freelist, p = NULL; a != NULL ; p = a, a = a->next ) { + if ( a->base +nb <= a->limit ) { + if ( p == NULL ) + arena_freelist = a->next; + else + p->next = a->next; + UnlockArena(); + a->avail = a->base; + rp = (char *)a->avail; + a->avail += nb; + /* the newly allocated arena is linked after pool->current + * and becomes pool->current */ + a->next = pool->current->next; + pool->current->next = a; + pool->current = a; + if ( NULL == pool->first.next ) + pool->first.next = a; + return(rp); + } + } + UnlockArena(); + } + + /* attempt to allocate from the heap */ + { + PRUint32 sz = PR_MAX(pool->arenasize, nb); + 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); + rp = (char *)a->avail; + a->avail += nb; + /* the newly allocated arena is linked after pool->current + * and becomes pool->current */ + a->next = pool->current->next; + pool->current->next = a; + pool->current = a; + if ( 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; + + PL_ARENA_ALLOCATE(newp, pool, size + incr); + if (newp) + memcpy(newp, p, size); + return newp; +} + +static void ClearArenaList(PLArena *a, PRInt32 pattern) +{ + + for (; a; a = a->next) { + PR_ASSERT(a->base <= a->avail && a->avail <= a->limit); + a->avail = a->base; + PL_CLEAR_UNUSED_PATTERN(a, pattern); + } +} + +PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern) +{ + ClearArenaList(pool->first.next, pattern); +} + +/* + * 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, PRBool reallyFree) +{ + PLArena **ap, *a; + + ap = &head->next; + a = *ap; + if (!a) + return; + +#ifdef DEBUG + ClearArenaList(a, PL_FREE_PATTERN); +#endif + + if (reallyFree) { + do { + *ap = a->next; + PL_CLEAR_ARENA(a); + PL_COUNT_ARENA(pool,--); + PR_DELETE(a); + } while ((a = *ap) != 0); + } else { + /* Insert the whole arena chain at the front of the freelist. */ + do { + ap = &(*ap)->next; + } while (*ap); + LockArena(); + *ap = arena_freelist; + arena_freelist = a; + head->next = 0; + UnlockArena(); + } + + 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, PR_FALSE); + return; + } + } +} + +PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool) +{ + FreeArenaList(pool, &pool->first, PR_FALSE); + COUNT(pool, ndeallocs); +} + +PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool) +{ + FreeArenaList(pool, &pool->first, PR_TRUE); +#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) +{ + PLArena *a, *next; + + for (a = arena_freelist; a; a = next) { + next = a->next; + PR_DELETE(a); + } + arena_freelist = NULL; + + if (arenaLock) { + PR_DestroyLock(arenaLock); + arenaLock = NULL; + } + once = pristineCallOnce; +} + +#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/mozilla/nsprpub/lib/ds/plarena.h b/mozilla/nsprpub/lib/ds/plarena.h new file mode 100644 index 0000000..d609404 --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plarena.h @@ -0,0 +1,214 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is Netscape + * Communications Corporation. Portions created by Netscape are + * Copyright (C) 1998-2000 Netscape Communications Corporation. All + * Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** + */ + +#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" +#include "plarenas.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 + +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 +}; + +/* + * 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, nb); \ + PRUword _p = _a->avail; \ + PRUword _q = _p + _nb; \ + if (_q > _a->limit) \ + _p = (PRUword)PL_ArenaAllocate(pool, _nb); \ + else \ + _a->avail = _q; \ + p = (void *)_p; \ + PL_ArenaCountAllocation(pool, 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, incr); \ + PRUword _p = _a->avail; \ + PRUword _q = _p + _incr; \ + if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \ + _q <= _a->limit) { \ + _a->avail = _q; \ + PL_ArenaCountInplaceGrowth(pool, size, incr); \ + } else { \ + p = PL_ArenaGrow(pool, p, size, incr); \ + } \ + PL_ArenaCountGrowth(pool, size, 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_ASSERT((a)->avail <= (a)->limit), \ + memset((void*)(a)->avail, (pattern), (a)->limit - (a)->avail)) +#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) memset((void*)(a), PL_FREE_PATTERN, \ + (a)->limit - (PRUword)(a)) +#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_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 + +#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/mozilla/nsprpub/lib/ds/plarenas.h b/mozilla/nsprpub/lib/ds/plarenas.h new file mode 100644 index 0000000..9c9eee8 --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plarenas.h @@ -0,0 +1,92 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1998-2000 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +#ifndef PLARENAS_H +#define PLARENAS_H + +PR_BEGIN_EXTERN_C + +typedef struct PLArenaPool PLArenaPool; + +/* +** Initialize an arena pool with the given name for debugging and metering, +** with a minimum size per arena of size bytes. +**/ +PR_EXTERN(void) PL_InitArenaPool( + PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align); + +/* +** Finish using arenas, freeing all memory associated with them. +**/ +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. +**/ +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); + +PR_END_EXTERN_C + +#endif /* PLARENAS_H */ diff --git a/mozilla/nsprpub/lib/ds/plds.def b/mozilla/nsprpub/lib/ds/plds.def new file mode 100644 index 0000000..a80e2bc --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plds.def @@ -0,0 +1,88 @@ +;+# +;+# ***** BEGIN LICENSE BLOCK ***** +;+# Version: MPL 1.1/GPL 2.0/LGPL 2.1 +;+# +;+# The contents of this file are subject to the Mozilla Public License Version +;+# 1.1 (the "License"); you may not use this file except in compliance with +;+# the License. You may obtain a copy of the License at +;+# http://www.mozilla.org/MPL/ +;+# +;+# Software distributed under the License is distributed on an "AS IS" basis, +;+# WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License +;+# for the specific language governing rights and limitations under the +;+# License. +;+# +;+# The Original Code is the Netscape Portable Runtime (NSPR). +;+# +;+# The Initial Developer of the Original Code is +;+# Netscape Communications Corporation. +;+# Portions created by the Initial Developer are Copyright (C) 2002-2003 +;+# the Initial Developer. All Rights Reserved. +;+# +;+# Contributor(s): +;+# +;+# Alternatively, the contents of this file may be used under the terms of +;+# either the GNU General Public License Version 2 or later (the "GPL"), or +;+# the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), +;+# in which case the provisions of the GPL or the LGPL are applicable instead +;+# of those above. If you wish to allow use of your version of this file only +;+# under the terms of either the GPL or the LGPL, and not to allow others to +;+# use your version of this file under the terms of the MPL, indicate your +;+# decision by deleting the provisions above and replace them with the notice +;+# and other provisions required by the GPL or the LGPL. If you do not delete +;+# the provisions above, a recipient may use your version of this file under +;+# the terms of any one of the MPL, the GPL or the LGPL. +;+# +;+# ***** END LICENSE BLOCK ***** +;+# +;+# 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; diff --git a/mozilla/nsprpub/lib/ds/plds.rc b/mozilla/nsprpub/lib/ds/plds.rc new file mode 100644 index 0000000..7a310df --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plds.rc @@ -0,0 +1,101 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1999-2000 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +#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/mozilla/nsprpub/lib/ds/plhash.c b/mozilla/nsprpub/lib/ds/plhash.c new file mode 100644 index 0000000..4f69d04 --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plhash.c @@ -0,0 +1,515 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1998-2000 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +/* + * 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/mozilla/nsprpub/lib/ds/plhash.h b/mozilla/nsprpub/lib/ds/plhash.h new file mode 100644 index 0000000..d752d16 --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plhash.h @@ -0,0 +1,158 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1998-2000 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +#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/mozilla/nsprpub/lib/ds/plvrsion.c b/mozilla/nsprpub/lib/ds/plvrsion.c new file mode 100644 index 0000000..486a6cb --- /dev/null +++ b/mozilla/nsprpub/lib/ds/plvrsion.c @@ -0,0 +1,125 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is the Netscape Portable Runtime (NSPR). + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1998-2000 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +#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 */ + |