michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef jshash_h___
michael@0: #define jshash_h___
michael@0: 
michael@0: /*
michael@0:  * API to portable hash table code.
michael@0:  */
michael@0: #include <stddef.h>
michael@0: #include <stdint.h>
michael@0: #include <stdio.h>
michael@0: 
michael@0: extern "C" {
michael@0: 
michael@0: typedef uint32_t JSHashNumber;
michael@0: typedef struct JSHashEntry JSHashEntry;
michael@0: typedef struct JSHashTable JSHashTable;
michael@0: 
michael@0: #define JS_HASH_BITS 32
michael@0: #define JS_GOLDEN_RATIO 0x9E3779B9U
michael@0: 
michael@0: typedef JSHashNumber (* JSHashFunction)(const void *key);
michael@0: typedef int (* JSHashComparator)(const void *v1, const void *v2);
michael@0: typedef int (* JSHashEnumerator)(JSHashEntry *he, int i, void *arg);
michael@0: 
michael@0: /* Flag bits in JSHashEnumerator's return value */
michael@0: #define HT_ENUMERATE_NEXT       0       /* continue enumerating entries */
michael@0: #define HT_ENUMERATE_STOP       1       /* stop enumerating entries */
michael@0: #define HT_ENUMERATE_REMOVE     2       /* remove and free the current entry */
michael@0: 
michael@0: typedef struct JSHashAllocOps {
michael@0:     void *              (*allocTable)(void *pool, size_t size);
michael@0:     void                (*freeTable)(void *pool, void *item, size_t size);
michael@0:     JSHashEntry *       (*allocEntry)(void *pool, const void *key);
michael@0:     void                (*freeEntry)(void *pool, JSHashEntry *he, unsigned flag);
michael@0: } JSHashAllocOps;
michael@0: 
michael@0: #define HT_FREE_VALUE   0               /* just free the entry's value */
michael@0: #define HT_FREE_ENTRY   1               /* free value and entire entry */
michael@0: 
michael@0: struct JSHashEntry {
michael@0:     JSHashEntry         *next;          /* hash chain linkage */
michael@0:     JSHashNumber        keyHash;        /* key hash function result */
michael@0:     const void          *key;           /* ptr to opaque key */
michael@0:     void                *value;         /* ptr to opaque value */
michael@0: };
michael@0: 
michael@0: struct JSHashTable {
michael@0:     JSHashEntry         **buckets;      /* vector of hash buckets */
michael@0:     uint32_t            nentries;       /* number of entries in table */
michael@0:     uint32_t            shift;          /* multiplicative hash shift */
michael@0:     JSHashFunction      keyHash;        /* key hash function */
michael@0:     JSHashComparator    keyCompare;     /* key comparison function */
michael@0:     JSHashComparator    valueCompare;   /* value comparison function */
michael@0:     const JSHashAllocOps *allocOps;     /* allocation operations */
michael@0:     void                *allocPriv;     /* allocation private data */
michael@0: #ifdef JS_HASHMETER
michael@0:     uint32_t            nlookups;       /* total number of lookups */
michael@0:     uint32_t            nsteps;         /* number of hash chains traversed */
michael@0:     uint32_t            ngrows;         /* number of table expansions */
michael@0:     uint32_t            nshrinks;       /* number of table contractions */
michael@0: #endif
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * Create a new hash table.
michael@0:  * If allocOps is null, use default allocator ops built on top of malloc().
michael@0:  */
michael@0: extern JSHashTable * 
michael@0: JS_NewHashTable(uint32_t n, JSHashFunction keyHash,
michael@0:                 JSHashComparator keyCompare, JSHashComparator valueCompare,
michael@0:                 const JSHashAllocOps *allocOps, void *allocPriv);
michael@0: 
michael@0: extern void
michael@0: JS_HashTableDestroy(JSHashTable *ht);
michael@0: 
michael@0: /* Low level access methods */
michael@0: extern JSHashEntry **
michael@0: JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key);
michael@0: 
michael@0: extern JSHashEntry *
michael@0: JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash,
michael@0:                    const void *key, void *value);
michael@0: 
michael@0: extern void
michael@0: JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he);
michael@0: 
michael@0: /* Higher level access methods */
michael@0: extern JSHashEntry *
michael@0: JS_HashTableAdd(JSHashTable *ht, const void *key, void *value);
michael@0: 
michael@0: extern bool
michael@0: JS_HashTableRemove(JSHashTable *ht, const void *key);
michael@0: 
michael@0: extern int
michael@0: JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg);
michael@0: 
michael@0: extern void *
michael@0: JS_HashTableLookup(JSHashTable *ht, const void *key);
michael@0: 
michael@0: extern int
michael@0: JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp);
michael@0: 
michael@0: /* General-purpose C string hash function. */
michael@0: extern JSHashNumber
michael@0: JS_HashString(const void *key);
michael@0: 
michael@0: /* Stub function just returns v1 == v2 */
michael@0: extern int
michael@0: JS_CompareValues(const void *v1, const void *v2);
michael@0: 
michael@0: } // extern "C"
michael@0: 
michael@0: #endif /* jshash_h___ */