1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/jsd/jshash.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,118 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jshash_h___
1.11 +#define jshash_h___
1.12 +
1.13 +/*
1.14 + * API to portable hash table code.
1.15 + */
1.16 +#include <stddef.h>
1.17 +#include <stdint.h>
1.18 +#include <stdio.h>
1.19 +
1.20 +extern "C" {
1.21 +
1.22 +typedef uint32_t JSHashNumber;
1.23 +typedef struct JSHashEntry JSHashEntry;
1.24 +typedef struct JSHashTable JSHashTable;
1.25 +
1.26 +#define JS_HASH_BITS 32
1.27 +#define JS_GOLDEN_RATIO 0x9E3779B9U
1.28 +
1.29 +typedef JSHashNumber (* JSHashFunction)(const void *key);
1.30 +typedef int (* JSHashComparator)(const void *v1, const void *v2);
1.31 +typedef int (* JSHashEnumerator)(JSHashEntry *he, int i, void *arg);
1.32 +
1.33 +/* Flag bits in JSHashEnumerator's return value */
1.34 +#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */
1.35 +#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */
1.36 +#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */
1.37 +
1.38 +typedef struct JSHashAllocOps {
1.39 + void * (*allocTable)(void *pool, size_t size);
1.40 + void (*freeTable)(void *pool, void *item, size_t size);
1.41 + JSHashEntry * (*allocEntry)(void *pool, const void *key);
1.42 + void (*freeEntry)(void *pool, JSHashEntry *he, unsigned flag);
1.43 +} JSHashAllocOps;
1.44 +
1.45 +#define HT_FREE_VALUE 0 /* just free the entry's value */
1.46 +#define HT_FREE_ENTRY 1 /* free value and entire entry */
1.47 +
1.48 +struct JSHashEntry {
1.49 + JSHashEntry *next; /* hash chain linkage */
1.50 + JSHashNumber keyHash; /* key hash function result */
1.51 + const void *key; /* ptr to opaque key */
1.52 + void *value; /* ptr to opaque value */
1.53 +};
1.54 +
1.55 +struct JSHashTable {
1.56 + JSHashEntry **buckets; /* vector of hash buckets */
1.57 + uint32_t nentries; /* number of entries in table */
1.58 + uint32_t shift; /* multiplicative hash shift */
1.59 + JSHashFunction keyHash; /* key hash function */
1.60 + JSHashComparator keyCompare; /* key comparison function */
1.61 + JSHashComparator valueCompare; /* value comparison function */
1.62 + const JSHashAllocOps *allocOps; /* allocation operations */
1.63 + void *allocPriv; /* allocation private data */
1.64 +#ifdef JS_HASHMETER
1.65 + uint32_t nlookups; /* total number of lookups */
1.66 + uint32_t nsteps; /* number of hash chains traversed */
1.67 + uint32_t ngrows; /* number of table expansions */
1.68 + uint32_t nshrinks; /* number of table contractions */
1.69 +#endif
1.70 +};
1.71 +
1.72 +/*
1.73 + * Create a new hash table.
1.74 + * If allocOps is null, use default allocator ops built on top of malloc().
1.75 + */
1.76 +extern JSHashTable *
1.77 +JS_NewHashTable(uint32_t n, JSHashFunction keyHash,
1.78 + JSHashComparator keyCompare, JSHashComparator valueCompare,
1.79 + const JSHashAllocOps *allocOps, void *allocPriv);
1.80 +
1.81 +extern void
1.82 +JS_HashTableDestroy(JSHashTable *ht);
1.83 +
1.84 +/* Low level access methods */
1.85 +extern JSHashEntry **
1.86 +JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key);
1.87 +
1.88 +extern JSHashEntry *
1.89 +JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash,
1.90 + const void *key, void *value);
1.91 +
1.92 +extern void
1.93 +JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he);
1.94 +
1.95 +/* Higher level access methods */
1.96 +extern JSHashEntry *
1.97 +JS_HashTableAdd(JSHashTable *ht, const void *key, void *value);
1.98 +
1.99 +extern bool
1.100 +JS_HashTableRemove(JSHashTable *ht, const void *key);
1.101 +
1.102 +extern int
1.103 +JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg);
1.104 +
1.105 +extern void *
1.106 +JS_HashTableLookup(JSHashTable *ht, const void *key);
1.107 +
1.108 +extern int
1.109 +JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp);
1.110 +
1.111 +/* General-purpose C string hash function. */
1.112 +extern JSHashNumber
1.113 +JS_HashString(const void *key);
1.114 +
1.115 +/* Stub function just returns v1 == v2 */
1.116 +extern int
1.117 +JS_CompareValues(const void *v1, const void *v2);
1.118 +
1.119 +} // extern "C"
1.120 +
1.121 +#endif /* jshash_h___ */
