1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2/* 3 * The contents of this file are subject to the Mozilla Public 4 * License Version 1.1 (the "License"); you may not use this file 5 * except in compliance with the License. You may obtain a copy of 6 * the License at http://www.mozilla.org/MPL/ 7 * 8 * Software distributed under the License is distributed on an "AS 9 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or 10 * implied. See the License for the specific language governing 11 * rights and limitations under the License. 12 * 13 * The Original Code is the Netscape Portable Runtime (NSPR). 14 * 15 * The Initial Developer of the Original Code is Netscape 16 * Communications Corporation. Portions created by Netscape are 17 * Copyright (C) 1998-2000 Netscape Communications Corporation. All 18 * Rights Reserved. 19 * 20 * Contributor(s): 21 * 22 * Alternatively, the contents of this file may be used under the 23 * terms of the GNU General Public License Version 2 or later (the 24 * "GPL"), in which case the provisions of the GPL are applicable 25 * instead of those above. If you wish to allow use of your 26 * version of this file only under the terms of the GPL and not to 27 * allow others to use your version of this file under the MPL, 28 * indicate your decision by deleting the provisions above and 29 * replace them with the notice and other provisions required by 30 * the GPL. If you do not delete the provisions above, a recipient 31 * may use your version of this file under either the MPL or the 32 * GPL. 33 */ 34 35#ifndef plhash_h___ 36#define plhash_h___ 37/* 38 * API to portable hash table code. 39 */ 40#include <stdio.h> 41#include "prtypes.h" 42 43PR_BEGIN_EXTERN_C 44 45typedef struct PLHashEntry PLHashEntry; 46typedef struct PLHashTable PLHashTable; 47typedef PRUint32 PLHashNumber; 48#define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */ 49typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key); 50typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2); 51 52#if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) /* for nsSpaceManager.cpp */ 53PR_END_EXTERN_C /* and nsHTMLDocument.cpp */ 54#endif 55typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg); 56 57#if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) 58PR_BEGIN_EXTERN_C 59#endif 60 61/* Flag bits in PLHashEnumerator's return value */ 62#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ 63#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ 64#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ 65#define HT_ENUMERATE_UNHASH 4 /* just unhash the current entry */ 66 67typedef struct PLHashAllocOps { 68 void * (PR_CALLBACK *allocTable)(void *pool, PRSize size); 69 void (PR_CALLBACK *freeTable)(void *pool, void *item); 70 PLHashEntry * (PR_CALLBACK *allocEntry)(void *pool, const void *key); 71 void (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag); 72} PLHashAllocOps; 73 74#define HT_FREE_VALUE 0 /* just free the entry's value */ 75#define HT_FREE_ENTRY 1 /* free value and entire entry */ 76 77struct PLHashEntry { 78 PLHashEntry *next; /* hash chain linkage */ 79 PLHashNumber keyHash; /* key hash function result */ 80 const void *key; /* ptr to opaque key */ 81 void *value; /* ptr to opaque value */ 82}; 83 84struct PLHashTable { 85 PLHashEntry **buckets; /* vector of hash buckets */ 86 PRUint32 nentries; /* number of entries in table */ 87 PRUint32 shift; /* multiplicative hash shift */ 88 PLHashFunction keyHash; /* key hash function */ 89 PLHashComparator keyCompare; /* key comparison function */ 90 PLHashComparator valueCompare; /* value comparison function */ 91 const PLHashAllocOps *allocOps; /* allocation operations */ 92 void *allocPriv; /* allocation private data */ 93#ifdef HASHMETER 94 PRUint32 nlookups; /* total number of lookups */ 95 PRUint32 nsteps; /* number of hash chains traversed */ 96 PRUint32 ngrows; /* number of table expansions */ 97 PRUint32 nshrinks; /* number of table contractions */ 98#endif 99}; 100 101/* 102 * Create a new hash table. 103 * If allocOps is null, use default allocator ops built on top of malloc(). 104 */ 105PR_EXTERN(PLHashTable *) 106PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash, 107 PLHashComparator keyCompare, PLHashComparator valueCompare, 108 const PLHashAllocOps *allocOps, void *allocPriv); 109 110PR_EXTERN(void) 111PL_HashTableDestroy(PLHashTable *ht); 112 113/* Higher level access methods */ 114PR_EXTERN(PLHashEntry *) 115PL_HashTableAdd(PLHashTable *ht, const void *key, void *value); 116 117PR_EXTERN(PRBool) 118PL_HashTableRemove(PLHashTable *ht, const void *key); 119 120PR_EXTERN(void *) 121PL_HashTableLookup(PLHashTable *ht, const void *key); 122 123PR_EXTERN(void *) 124PL_HashTableLookupConst(PLHashTable *ht, const void *key); 125 126PR_EXTERN(PRIntn) 127PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg); 128 129/* General-purpose C string hash function. */ 130PR_EXTERN(PLHashNumber) 131PL_HashString(const void *key); 132 133/* Compare strings using strcmp(), return true if equal. */ 134PR_EXTERN(PRIntn) 135PL_CompareStrings(const void *v1, const void *v2); 136 137/* Stub function just returns v1 == v2 */ 138PR_EXTERN(PRIntn) 139PL_CompareValues(const void *v1, const void *v2); 140 141/* Low level access methods */ 142PR_EXTERN(PLHashEntry **) 143PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key); 144 145PR_EXTERN(PLHashEntry **) 146PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, 147 const void *key); 148 149PR_EXTERN(PLHashEntry *) 150PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash, 151 const void *key, void *value); 152 153PR_EXTERN(void) 154PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he); 155 156/* This can be trivially implemented using PL_HashTableEnumerateEntries. */ 157PR_EXTERN(PRIntn) 158PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp); 159 160PR_END_EXTERN_C 161 162#endif /* plhash_h___ */ 163