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 <security_asn1/prtypes.h> 42// @@@ for Boolean 43#include <Security/SecBase.h> 44 45PR_BEGIN_EXTERN_C 46 47typedef struct PLHashEntry PLHashEntry; 48typedef struct PLHashTable PLHashTable; 49typedef PRUint32 PLHashNumber; 50#define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */ 51typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key); 52typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2); 53 54#if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) /* for nsSpaceManager.cpp */ 55PR_END_EXTERN_C /* and nsHTMLDocument.cpp */ 56#endif 57typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg); 58 59#if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) 60PR_BEGIN_EXTERN_C 61#endif 62 63/* Flag bits in PLHashEnumerator's return value */ 64#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ 65#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ 66#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ 67#define HT_ENUMERATE_UNHASH 4 /* just unhash the current entry */ 68 69typedef struct PLHashAllocOps { 70 void * (PR_CALLBACK *allocTable)(void *pool, PRSize size); 71 void (PR_CALLBACK *freeTable)(void *pool, void *item); 72 PLHashEntry * (PR_CALLBACK *allocEntry)(void *pool, const void *key); 73 void (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag); 74} PLHashAllocOps; 75 76#define HT_FREE_VALUE 0 /* just free the entry's value */ 77#define HT_FREE_ENTRY 1 /* free value and entire entry */ 78 79struct PLHashEntry { 80 PLHashEntry *next; /* hash chain linkage */ 81 PLHashNumber keyHash; /* key hash function result */ 82 const void *key; /* ptr to opaque key */ 83 void *value; /* ptr to opaque value */ 84}; 85 86struct PLHashTable { 87 PLHashEntry **buckets; /* vector of hash buckets */ 88 PRUint32 nentries; /* number of entries in table */ 89 PRUint32 shift; /* multiplicative hash shift */ 90 PLHashFunction keyHash; /* key hash function */ 91 PLHashComparator keyCompare; /* key comparison function */ 92 PLHashComparator valueCompare; /* value comparison function */ 93 const PLHashAllocOps *allocOps; /* allocation operations */ 94 void *allocPriv; /* allocation private data */ 95#ifdef HASHMETER 96 PRUint32 nlookups; /* total number of lookups */ 97 PRUint32 nsteps; /* number of hash chains traversed */ 98 PRUint32 ngrows; /* number of table expansions */ 99 PRUint32 nshrinks; /* number of table contractions */ 100#endif 101}; 102 103/* 104 * Create a new hash table. 105 * If allocOps is null, use default allocator ops built on top of malloc(). 106 */ 107PR_EXTERN(PLHashTable *) 108PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash, 109 PLHashComparator keyCompare, PLHashComparator valueCompare, 110 const PLHashAllocOps *allocOps, void *allocPriv); 111 112PR_EXTERN(void) 113PL_HashTableDestroy(PLHashTable *ht); 114 115/* Higher level access methods */ 116PR_EXTERN(PLHashEntry *) 117PL_HashTableAdd(PLHashTable *ht, const void *key, void *value); 118 119PR_EXTERN(Boolean) 120PL_HashTableRemove(PLHashTable *ht, const void *key); 121 122PR_EXTERN(void *) 123PL_HashTableLookup(PLHashTable *ht, const void *key); 124 125PR_EXTERN(void *) 126PL_HashTableLookupConst(PLHashTable *ht, const void *key); 127 128PR_EXTERN(PRIntn) 129PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg); 130 131/* General-purpose C string hash function. */ 132PR_EXTERN(PLHashNumber) 133PL_HashString(const void *key); 134 135/* Compare strings using strcmp(), return true if equal. */ 136PR_EXTERN(PRIntn) 137PL_CompareStrings(const void *v1, const void *v2); 138 139/* Stub function just returns v1 == v2 */ 140PR_EXTERN(PRIntn) 141PL_CompareValues(const void *v1, const void *v2); 142 143/* Low level access methods */ 144PR_EXTERN(PLHashEntry **) 145PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key); 146 147PR_EXTERN(PLHashEntry **) 148PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, 149 const void *key); 150 151PR_EXTERN(PLHashEntry *) 152PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash, 153 const void *key, void *value); 154 155PR_EXTERN(void) 156PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he); 157 158/* This can be trivially implemented using PL_HashTableEnumerateEntries. */ 159PR_EXTERN(PRIntn) 160PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp); 161 162PR_END_EXTERN_C 163 164#endif /* plhash_h___ */ 165