pldhash.c revision 489ce997e6d81472bf0d1322ad2b5b57ffa4c53d
/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/* ***** 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
*
* 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 Mozilla JavaScript code.
*
* The Initial Developer of the Original Code is
* Netscape Communications Corporation.
* Portions created by the Initial Developer are Copyright (C) 1999-2001
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
* Brendan Eich <brendan@mozilla.org> (Original Author)
* Chris Waterson <waterson@netscape.com>
*
* Alternatively, the contents of this file may be used under the terms of
* either of 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 ***** */
/*
* Double hashing implementation.
* GENERATED BY js/src/plify_jsdhash.sed -- DO NOT EDIT!!!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "prbit.h"
#include "pldhash.h"
#include "prlog.h" /* for PR_ASSERT */
#ifdef PL_DHASHMETER
# if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
# include "nsTraceMalloc.h"
# endif
# define METER(x) x
#else
# define METER(x) /* nothing */
#endif
#ifdef VBOX_USE_IPRT_IN_XPCOM
#endif
PR_IMPLEMENT(void *)
{
#ifdef VBOX_USE_IPRT_IN_XPCOM
return RTMemAlloc(nbytes);
#else
#endif
}
PR_IMPLEMENT(void)
{
#ifdef VBOX_USE_IPRT_IN_XPCOM
#else
#endif
}
{
const unsigned char *s;
h = 0;
for (s = key; *s != '\0'; s++)
return h;
}
PR_IMPLEMENT(const void *)
{
}
{
}
const PLDHashEntryHdr *entry,
const void *key)
{
}
const PLDHashEntryHdr *entry,
const void *key)
{
/* XXX tolerate null keys on account of sloppy Mozilla callers. */
}
PR_IMPLEMENT(void)
const PLDHashEntryHdr *from,
{
}
PR_IMPLEMENT(void)
{
}
PR_IMPLEMENT(void)
{
#ifdef VBOX_USE_IPRT_IN_XPCOM
#else
#endif
}
PR_IMPLEMENT(void)
{
}
static const PLDHashTableOps stub_ops = {
};
PR_IMPLEMENT(const PLDHashTableOps *)
PL_DHashGetStubOps(void)
{
return &stub_ops;
}
{
#ifdef VBOX_USE_IPRT_IN_XPCOM
#else
#endif
if (!table)
return NULL;
#ifdef VBOX_USE_IPRT_IN_XPCOM
#else
#endif
return NULL;
}
return table;
}
PR_IMPLEMENT(void)
{
#ifdef VBOX_USE_IPRT_IN_XPCOM
#else
#endif
}
{
int log2;
#ifdef DEBUG
if (entrySize > 10 * sizeof(void *)) {
"pldhash: for the table at address %p, the given entrySize"
" of %lu %s favors chaining over double hashing.\n",
(void *)table,
(unsigned long) entrySize,
}
#endif
if (capacity < PL_DHASH_MIN_SIZE)
if (capacity >= PL_DHASH_SIZE_LIMIT)
return PR_FALSE;
table->generation = 0;
if (!table->entryStore)
return PR_FALSE;
return PR_TRUE;
}
/*
* Compute max and min load numbers (entry counts) from table params.
*/
PR_IMPLEMENT(void)
float maxAlpha,
float minAlpha)
{
/*
* Reject obviously insane bounds, rather than trying to guess what the
* buggy caller intended.
*/
return;
/*
* Ensure that at least one entry will always be free. If maxAlpha at
* minimum size leaves no entries free, reduce maxAlpha based on minimum
* size and the precision limit of maxAlphaFrac's fixed point format.
*/
maxAlpha = (float)
}
/*
* Ensure that minAlpha is strictly less than half maxAlpha. Take care
* not to truncate an entry's worth of alpha when storing in minAlphaFrac
* (8-bit fixed point format).
*/
}
}
/*
* Double hashing needs the second hash code to be relatively prime to table
* size, so we simply make hash2 odd.
*/
/*
* Reserve keyHash 0 for free entries and 1 for removed-entry sentinels. Note
* that a removed-entry sentinel need be stored only if the removed entry had
* a colliding entry added after it. Therefore we can use 1 as the collision
* flag in addition to the removed-entry sentinel value. Multiplicative hash
* uses the high order bits of keyHash, so this least-significant reservation
* should not hurt the hash function's effectiveness much.
*
* If you change any of these magic numbers, also update PL_DHASH_ENTRY_IS_LIVE
* assist iterator writers who inspect table->entryStore directly.
*/
/* Match an entry's keyHash against an unstored one computed from a key. */
/* Compute the address of the indexed entry in table. */
PR_IMPLEMENT(void)
{
char *entryAddr, *entryLimit;
#ifdef DEBUG_XXXbrendan
if (dumpfp) {
#ifdef MOZILLA_CLIENT
#endif
}
#endif
/* Call finalize before clearing entries, so it can enumerate them. */
/* Clear any remaining live entries. */
while (entryAddr < entryLimit) {
if (ENTRY_IS_LIVE(entry)) {
}
}
/* Free entry storage last. */
}
static PLDHashEntryHdr * PL_DHASH_FASTCALL
{
/* Compute the primary hash address. */
/* Miss: return space for a new entry. */
if (PL_DHASH_ENTRY_IS_FREE(entry)) {
return entry;
}
/* Hit: return entry. */
return entry;
}
/* Collision: double hash. */
/* Save the first removed entry pointer so PL_DHASH_ADD can recycle it. */
if (ENTRY_IS_REMOVED(entry)) {
} else {
firstRemoved = NULL;
if (op == PL_DHASH_ADD)
}
for (;;) {
if (PL_DHASH_ENTRY_IS_FREE(entry)) {
}
return entry;
}
if (ENTRY_IS_REMOVED(entry)) {
if (!firstRemoved)
} else {
if (op == PL_DHASH_ADD)
}
}
/* NOTREACHED */
return NULL;
}
static PRBool
{
#ifdef VBOX /* HACK ALERT! generation == PR_UINT32_MAX during enumeration. */
return PR_FALSE;
#endif
/* Look, but don't touch, until we succeed in getting new entry store. */
if (newCapacity >= PL_DHASH_SIZE_LIMIT)
return PR_FALSE;
if (!newEntryStore)
return PR_FALSE;
/* We can't fail from here on, so update table parameters. */
table->removedCount = 0;
table->generation++;
#ifdef VBOX /* HACK ALERT! generation == PR_UINT32_MAX during enumeration. */
table->generation++;
#endif
/* Assign the new entry store to table. */
/* Copy only live entries, leaving removed ones behind. */
for (i = 0; i < oldCapacity; i++) {
if (ENTRY_IS_LIVE(oldEntry)) {
}
}
return PR_TRUE;
}
{
int deltaLog2;
/* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
keyHash &= ~COLLISION_FLAG;
switch (op) {
case PL_DHASH_LOOKUP:
break;
case PL_DHASH_ADD:
/*
* If alpha is >= .75, grow or compress the table. If key is already
* in the table, we may grow once more than necessary, but only if we
* are on the edge of being overloaded.
*/
/* Compress if a quarter or more of all entries are removed. */
deltaLog2 = 0;
} else {
deltaLog2 = 1;
}
/*
* Grow or compress table, returning null if ChangeTable fails and
* falling through might claim the last free entry.
*/
return NULL;
}
}
/*
* Look for entry after possibly growing, so we don't have to add it,
* then skip it while growing the table and re-add it after.
*/
if (!ENTRY_IS_LIVE(entry)) {
/* Initialize the entry, indicating that it's no longer free. */
if (ENTRY_IS_REMOVED(entry)) {
table->removedCount--;
}
/* We haven't claimed entry yet; fail with null return. */
return NULL;
}
table->entryCount++;
}
break;
case PL_DHASH_REMOVE:
if (ENTRY_IS_LIVE(entry)) {
/* Clear this entry and mark it as "removed". */
/* Shrink if alpha is <= .25 and table isn't too small already. */
if (size > PL_DHASH_MIN_SIZE &&
#ifdef VBOX /* HACK ALERT! generation == PR_UINT32_MAX during enumeration. */
/** @todo This is where IPC screws up, avoid the assertion in ChangeTable until it's fixed. */
#endif
}
}
break;
default:
PR_ASSERT(0);
}
return entry;
}
PR_IMPLEMENT(void)
{
if (keyHash & COLLISION_FLAG) {
table->removedCount++;
} else {
}
table->entryCount--;
}
{
char *entryAddr, *entryLimit;
#ifdef VBOX /* HACK ALERT! generation == PR_UINT32_MAX during enumeration. */
/*
* The hack! Set generation to PR_UINT32_MAX during the enumeration so
* we can prevent ChangeTable from being called.
*
* This happens during ipcDConnectService::OnClientStateChange()
* / ipcDConnectService::DeleteInstance() now when running
* java clienttest list hostinfo and vboxwebsrv crashes. It's quite
* likely that the IPC code isn't following the rules here, but it
* looks more difficult to fix that just hacking this hash code.
*/
#endif /* VBOX */
i = 0;
while (entryAddr < entryLimit) {
if (ENTRY_IS_LIVE(entry)) {
#ifdef VBOX /* HACK ALERT! generation == PR_UINT32_MAX during enumeration. */
#endif
if (op & PL_DHASH_REMOVE) {
}
if (op & PL_DHASH_STOP)
break;
}
}
#ifdef VBOX /* HACK ALERT! generation == PR_UINT32_MAX during enumeration. */
#endif
/*
* Shrink or compress if a quarter or more of all entries are removed, or
* if the table is underloaded according to the configured minimum alpha,
* and is not minimal-size already. Do this only if we removed above, so
* non-removing enumerations can count on stable table->entryStore until
* the next non-lookup-Operate or removing-Enumerate.
*/
if (didRemove &&
(capacity > PL_DHASH_MIN_SIZE &&
if (capacity < PL_DHASH_MIN_SIZE)
(void) ChangeTable(table,
}
return i;
}
#ifdef PL_DHASHMETER
#include <math.h>
PR_IMPLEMENT(void)
{
char *entryAddr;
chainCount = maxChainLen = 0;
hash2 = 0;
sqsum = 0;
for (i = 0; i < tableSize; i++) {
if (!ENTRY_IS_LIVE(entry))
continue;
chainLen = 1;
/* Start of a (possibly unit-length) chain. */
chainCount++;
} else {
do {
chainLen++;
}
if (chainLen > maxChainLen) {
}
}
if (entryCount && chainCount) {
variance = 0;
else
} else {
}
0.);
i = 0;
do {
break;
} while (PL_DHASH_ENTRY_IS_BUSY(entry));
}
}
#endif /* PL_DHASHMETER */