/* -*- 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
*
* 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 */
/* The smallest table has 16 buckets */
/* Compute the maximum entries given n buckets that we will tolerate, ~90% */
/* Compute the number of entries below which we shrink the table by half */
/*
** Stubs for default hash allocator ops.
*/
static void * PR_CALLBACK
{
#if defined(XP_MAC)
#endif
}
static void PR_CALLBACK
{
#if defined(XP_MAC)
#endif
}
static PLHashEntry * PR_CALLBACK
{
#if defined(XP_MAC)
#endif
return PR_NEW(PLHashEntry);
}
static void PR_CALLBACK
{
#if defined(XP_MAC)
#endif
if (flag == HT_FREE_ENTRY)
}
};
{
if (n <= MINBUCKETS) {
n = MINBUCKETSLOG2;
} else {
n = PR_CeilingLog2(n);
if ((PRInt32)n < 0)
return 0;
}
if (!ht)
return 0;
n = 1 << n;
#if defined(WIN16)
if (n > 16000) {
return 0;
}
#endif /* WIN16 */
nb = n * sizeof(PLHashEntry *);
return 0;
}
return ht;
}
PR_IMPLEMENT(void)
{
PRUint32 i, n;
for (i = 0; i < n; i++) {
}
}
#ifdef DEBUG
#endif
#ifdef DEBUG
#endif
}
/*
** Multiplicative hash, from Knuth 6.4.
*/
{
PLHashNumber h;
#ifdef HASHMETER
#endif
h = keyHash * GOLDEN_RATIO;
/* Move to front of chain if not already there */
}
return hep0;
}
#ifdef HASHMETER
#endif
}
return hep;
}
/*
** Same as PL_HashTableRawLookup but doesn't reorder the hash entries.
*/
const void *key)
{
PLHashNumber h;
#ifdef HASHMETER
#endif
h = keyHash * GOLDEN_RATIO;
break;
}
#ifdef HASHMETER
#endif
}
return hep;
}
{
PRUint32 i, n;
/* Grow the table if it is overloaded */
#if defined(WIN16)
if (2 * n > 16000)
return 0;
#endif /* WIN16 */
return 0;
}
#ifdef HASHMETER
#endif
for (i = 0; i < n; i++) {
}
}
#ifdef DEBUG
#endif
}
/* Make a new key value entry */
if (!he)
return 0;
return he;
}
{
/* Hit; see if values match */
/* key,value pair is already present in table */
return he;
}
return he;
}
}
PR_IMPLEMENT(void)
{
PRUint32 i, n;
/* Shrink table if it's underloaded */
return;
}
#ifdef HASHMETER
#endif
for (i = 0; i < n; i++) {
}
}
#ifdef DEBUG
#endif
}
}
{
return PR_FALSE;
/* Hit; remove element */
return PR_TRUE;
}
PR_IMPLEMENT(void *)
{
}
return 0;
}
/*
** Same as PL_HashTableLookup but doesn't reorder the hash entries.
*/
PR_IMPLEMENT(void *)
{
}
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)
{
int rv, n = 0;
for (i = 0; i < nbuckets; i++) {
n++;
if (rv & HT_ENUMERATE_REMOVE) {
}
} else {
}
if (rv & HT_ENUMERATE_STOP) {
goto out;
}
}
}
out:
}
return n;
}
#ifdef HASHMETER
#include <math.h>
#include <stdio.h>
PR_IMPLEMENT(void)
{
variance = 0;
nchains = 0;
maxChainLen = 0;
for (i = 0; i < nbuckets; i++) {
if (!he)
continue;
nchains++;
n++;
variance += n * n;
if (n > maxChainLen) {
maxChainLen = n;
maxChain = i;
}
}
break;
}
#endif /* HASHMETER */
PR_IMPLEMENT(int)
{
int count;
#ifdef HASHMETER
#endif
return count;
}
PL_HashString(const void *key)
{
PLHashNumber h;
const PRUint8 *s;
h = 0;
h = (h >> 28) ^ (h << 4) ^ *s;
return h;
}
PR_IMPLEMENT(int)
{
}
PR_IMPLEMENT(int)
{
}