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 43 PR_BEGIN_EXTERN_C 44 45 typedef struct PLHashEntry PLHashEntry; 46 typedef struct PLHashTable PLHashTable; 47 typedef PRUint32 PLHashNumber; 48 #define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */ 49 typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key); 50 typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2); 51 52 #if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) /* for nsSpaceManager.cpp */ 53 PR_END_EXTERN_C /* and nsHTMLDocument.cpp */ 54 #endif 55 typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg); 56 57 #if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) 58 PR_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 67 typedef 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 77 struct 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 84 struct 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 */ 105 PR_EXTERN(PLHashTable *) 106 PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash, 107 PLHashComparator keyCompare, PLHashComparator valueCompare, 108 const PLHashAllocOps *allocOps, void *allocPriv); 109 110 PR_EXTERN(void) 111 PL_HashTableDestroy(PLHashTable *ht); 112 113 /* Higher level access methods */ 114 PR_EXTERN(PLHashEntry *) 115 PL_HashTableAdd(PLHashTable *ht, const void *key, void *value); 116 117 PR_EXTERN(PRBool) 118 PL_HashTableRemove(PLHashTable *ht, const void *key); 119 120 PR_EXTERN(void *) 121 PL_HashTableLookup(PLHashTable *ht, const void *key); 122 123 PR_EXTERN(void *) 124 PL_HashTableLookupConst(PLHashTable *ht, const void *key); 125 126 PR_EXTERN(PRIntn) 127 PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg); 128 129 /* General-purpose C string hash function. */ 130 PR_EXTERN(PLHashNumber) 131 PL_HashString(const void *key); 132 133 /* Compare strings using strcmp(), return true if equal. */ 134 PR_EXTERN(PRIntn) 135 PL_CompareStrings(const void *v1, const void *v2); 136 137 /* Stub function just returns v1 == v2 */ 138 PR_EXTERN(PRIntn) 139 PL_CompareValues(const void *v1, const void *v2); 140 141 /* Low level access methods */ 142 PR_EXTERN(PLHashEntry **) 143 PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key); 144 145 PR_EXTERN(PLHashEntry **) 146 PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, 147 const void *key); 148 149 PR_EXTERN(PLHashEntry *) 150 PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash, 151 const void *key, void *value); 152 153 PR_EXTERN(void) 154 PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he); 155 156 /* This can be trivially implemented using PL_HashTableEnumerateEntries. */ 157 PR_EXTERN(PRIntn) 158 PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp); 159 160 PR_END_EXTERN_C 161 162 #endif /* plhash_h___ */ 163