The Tor Browser / file comparison
comparison: js/jsd/jshash.h
js/jsd/jshash.h
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:8f7e243ef9a5 |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | |
| 2 * vim: set ts=8 sts=4 et sw=4 tw=99: | |
| 3 * This Source Code Form is subject to the terms of the Mozilla Public | |
| 4 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 6 | |
| 7 #ifndef jshash_h___ | |
| 8 #define jshash_h___ | |
| 9 | |
| 10 /* | |
| 11 * API to portable hash table code. | |
| 12 */ | |
| 13 #include <stddef.h> | |
| 14 #include <stdint.h> | |
| 15 #include <stdio.h> | |
| 16 | |
| 17 extern "C" { | |
| 18 | |
| 19 typedef uint32_t JSHashNumber; | |
| 20 typedef struct JSHashEntry JSHashEntry; | |
| 21 typedef struct JSHashTable JSHashTable; | |
| 22 | |
| 23 #define JS_HASH_BITS 32 | |
| 24 #define JS_GOLDEN_RATIO 0x9E3779B9U | |
| 25 | |
| 26 typedef JSHashNumber (* JSHashFunction)(const void *key); | |
| 27 typedef int (* JSHashComparator)(const void *v1, const void *v2); | |
| 28 typedef int (* JSHashEnumerator)(JSHashEntry *he, int i, void *arg); | |
| 29 | |
| 30 /* Flag bits in JSHashEnumerator's return value */ | |
| 31 #define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ | |
| 32 #define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ | |
| 33 #define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ | |
| 34 | |
| 35 typedef struct JSHashAllocOps { | |
| 36 void * (*allocTable)(void *pool, size_t size); | |
| 37 void (*freeTable)(void *pool, void *item, size_t size); | |
| 38 JSHashEntry * (*allocEntry)(void *pool, const void *key); | |
| 39 void (*freeEntry)(void *pool, JSHashEntry *he, unsigned flag); | |
| 40 } JSHashAllocOps; | |
| 41 | |
| 42 #define HT_FREE_VALUE 0 /* just free the entry's value */ | |
| 43 #define HT_FREE_ENTRY 1 /* free value and entire entry */ | |
| 44 | |
| 45 struct JSHashEntry { | |
| 46 JSHashEntry *next; /* hash chain linkage */ | |
| 47 JSHashNumber keyHash; /* key hash function result */ | |
| 48 const void *key; /* ptr to opaque key */ | |
| 49 void *value; /* ptr to opaque value */ | |
| 50 }; | |
| 51 | |
| 52 struct JSHashTable { | |
| 53 JSHashEntry **buckets; /* vector of hash buckets */ | |
| 54 uint32_t nentries; /* number of entries in table */ | |
| 55 uint32_t shift; /* multiplicative hash shift */ | |
| 56 JSHashFunction keyHash; /* key hash function */ | |
| 57 JSHashComparator keyCompare; /* key comparison function */ | |
| 58 JSHashComparator valueCompare; /* value comparison function */ | |
| 59 const JSHashAllocOps *allocOps; /* allocation operations */ | |
| 60 void *allocPriv; /* allocation private data */ | |
| 61 #ifdef JS_HASHMETER | |
| 62 uint32_t nlookups; /* total number of lookups */ | |
| 63 uint32_t nsteps; /* number of hash chains traversed */ | |
| 64 uint32_t ngrows; /* number of table expansions */ | |
| 65 uint32_t nshrinks; /* number of table contractions */ | |
| 66 #endif | |
| 67 }; | |
| 68 | |
| 69 /* | |
| 70 * Create a new hash table. | |
| 71 * If allocOps is null, use default allocator ops built on top of malloc(). | |
| 72 */ | |
| 73 extern JSHashTable * | |
| 74 JS_NewHashTable(uint32_t n, JSHashFunction keyHash, | |
| 75 JSHashComparator keyCompare, JSHashComparator valueCompare, | |
| 76 const JSHashAllocOps *allocOps, void *allocPriv); | |
| 77 | |
| 78 extern void | |
| 79 JS_HashTableDestroy(JSHashTable *ht); | |
| 80 | |
| 81 /* Low level access methods */ | |
| 82 extern JSHashEntry ** | |
| 83 JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key); | |
| 84 | |
| 85 extern JSHashEntry * | |
| 86 JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash, | |
| 87 const void *key, void *value); | |
| 88 | |
| 89 extern void | |
| 90 JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he); | |
| 91 | |
| 92 /* Higher level access methods */ | |
| 93 extern JSHashEntry * | |
| 94 JS_HashTableAdd(JSHashTable *ht, const void *key, void *value); | |
| 95 | |
| 96 extern bool | |
| 97 JS_HashTableRemove(JSHashTable *ht, const void *key); | |
| 98 | |
| 99 extern int | |
| 100 JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg); | |
| 101 | |
| 102 extern void * | |
| 103 JS_HashTableLookup(JSHashTable *ht, const void *key); | |
| 104 | |
| 105 extern int | |
| 106 JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp); | |
| 107 | |
| 108 /* General-purpose C string hash function. */ | |
| 109 extern JSHashNumber | |
| 110 JS_HashString(const void *key); | |
| 111 | |
| 112 /* Stub function just returns v1 == v2 */ | |
| 113 extern int | |
| 114 JS_CompareValues(const void *v1, const void *v2); | |
| 115 | |
| 116 } // extern "C" | |
| 117 | |
| 118 #endif /* jshash_h___ */ |
