15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The contents of this file are subject to the Mozilla Public 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * License Version 1.1 (the "License"); you may not use this file 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * except in compliance with the License. You may obtain a copy of 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the License at http://www.mozilla.org/MPL/ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Software distributed under the License is distributed on an "AS 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * implied. See the License for the specific language governing 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * rights and limitations under the License. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The Original Code is the Netscape Portable Runtime (NSPR). 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The Initial Developer of the Original Code is Netscape 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Communications Corporation. Portions created by Netscape are 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright (C) 1998-2000 Netscape Communications Corporation. All 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Rights Reserved. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Contributor(s): 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Alternatively, the contents of this file may be used under the 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * terms of the GNU General Public License Version 2 or later (the 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "GPL"), in which case the provisions of the GPL are applicable 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * instead of those above. If you wish to allow use of your 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * version of this file only under the terms of the GPL and not to 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * allow others to use your version of this file under the MPL, 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * indicate your decision by deleting the provisions above and 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * replace them with the notice and other provisions required by 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the GPL. If you do not delete the provisions above, a recipient 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * may use your version of this file under either the MPL or the 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * GPL. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef plhash_h___ 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define plhash_h___ 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * API to portable hash table code. 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h> 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "prtypes.h" 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_BEGIN_EXTERN_C 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct PLHashEntry PLHashEntry; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct PLHashTable PLHashTable; 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef PRUint32 PLHashNumber; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */ 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) /* for nsSpaceManager.cpp */ 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_END_EXTERN_C /* and nsHTMLDocument.cpp */ 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_BEGIN_EXTERN_C 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Flag bits in PLHashEnumerator's return value */ 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HT_ENUMERATE_UNHASH 4 /* just unhash the current entry */ 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct PLHashAllocOps { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void * (PR_CALLBACK *allocTable)(void *pool, PRSize size); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void (PR_CALLBACK *freeTable)(void *pool, void *item); 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashEntry * (PR_CALLBACK *allocEntry)(void *pool, const void *key); 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} PLHashAllocOps; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HT_FREE_VALUE 0 /* just free the entry's value */ 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HT_FREE_ENTRY 1 /* free value and entire entry */ 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct PLHashEntry { 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashEntry *next; /* hash chain linkage */ 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashNumber keyHash; /* key hash function result */ 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const void *key; /* ptr to opaque key */ 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *value; /* ptr to opaque value */ 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct PLHashTable { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashEntry **buckets; /* vector of hash buckets */ 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PRUint32 nentries; /* number of entries in table */ 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PRUint32 shift; /* multiplicative hash shift */ 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashFunction keyHash; /* key hash function */ 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashComparator keyCompare; /* key comparison function */ 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashComparator valueCompare; /* value comparison function */ 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PLHashAllocOps *allocOps; /* allocation operations */ 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *allocPriv; /* allocation private data */ 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HASHMETER 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PRUint32 nlookups; /* total number of lookups */ 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PRUint32 nsteps; /* number of hash chains traversed */ 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PRUint32 ngrows; /* number of table expansions */ 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PRUint32 nshrinks; /* number of table contractions */ 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Create a new hash table. 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * If allocOps is null, use default allocator ops built on top of malloc(). 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PLHashTable *) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash, 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PLHashComparator keyCompare, PLHashComparator valueCompare, 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PLHashAllocOps *allocOps, void *allocPriv); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(void) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableDestroy(PLHashTable *ht); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Higher level access methods */ 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PLHashEntry *) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableAdd(PLHashTable *ht, const void *key, void *value); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PRBool) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableRemove(PLHashTable *ht, const void *key); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(void *) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableLookup(PLHashTable *ht, const void *key); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(void *) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableLookupConst(PLHashTable *ht, const void *key); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PRIntn) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* General-purpose C string hash function. */ 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PLHashNumber) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashString(const void *key); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Compare strings using strcmp(), return true if equal. */ 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PRIntn) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_CompareStrings(const void *v1, const void *v2); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Stub function just returns v1 == v2 */ 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PRIntn) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_CompareValues(const void *v1, const void *v2); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Low level access methods */ 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PLHashEntry **) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PLHashEntry **) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const void *key); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PLHashEntry *) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash, 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const void *key, void *value); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(void) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* This can be trivially implemented using PL_HashTableEnumerateEntries. */ 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_EXTERN(PRIntn) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PR_END_EXTERN_C 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* plhash_h___ */ 163