/[jscoverage]/trunk/js/jshash.h
ViewVC logotype

Contents of /trunk/js/jshash.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 507 - (show annotations)
Sun Jan 10 07:23:34 2010 UTC (9 years, 5 months ago) by siliconforks
File MIME type: text/plain
File size: 5963 byte(s)
Update SpiderMonkey from Firefox 3.6rc1.

1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 *
3 * ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5 *
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
10 *
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
14 * License.
15 *
16 * The Original Code is Mozilla Communicator client code, released
17 * March 31, 1998.
18 *
19 * The Initial Developer of the Original Code is
20 * Netscape Communications Corporation.
21 * Portions created by the Initial Developer are Copyright (C) 1998
22 * the Initial Developer. All Rights Reserved.
23 *
24 * Contributor(s):
25 *
26 * Alternatively, the contents of this file may be used under the terms of
27 * either of the GNU General Public License Version 2 or later (the "GPL"),
28 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
37 *
38 * ***** END LICENSE BLOCK ***** */
39
40 #ifndef jshash_h___
41 #define jshash_h___
42 /*
43 * API to portable hash table code.
44 */
45 #include <stddef.h>
46 #include <stdio.h>
47 #include "jstypes.h"
48 #include "jscompat.h"
49
50 JS_BEGIN_EXTERN_C
51
52 typedef uint32 JSHashNumber;
53 typedef struct JSHashEntry JSHashEntry;
54 typedef struct JSHashTable JSHashTable;
55
56 #define JS_HASH_BITS 32
57 #define JS_GOLDEN_RATIO 0x9E3779B9U
58
59 typedef JSHashNumber (* JSHashFunction)(const void *key);
60 typedef intN (* JSHashComparator)(const void *v1, const void *v2);
61 typedef intN (* JSHashEnumerator)(JSHashEntry *he, intN i, void *arg);
62
63 /* Flag bits in JSHashEnumerator'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
68 typedef struct JSHashAllocOps {
69 void * (*allocTable)(void *pool, size_t size);
70 void (*freeTable)(void *pool, void *item, size_t size);
71 JSHashEntry * (*allocEntry)(void *pool, const void *key);
72 void (*freeEntry)(void *pool, JSHashEntry *he, uintN flag);
73 } JSHashAllocOps;
74
75 #define HT_FREE_VALUE 0 /* just free the entry's value */
76 #define HT_FREE_ENTRY 1 /* free value and entire entry */
77
78 struct JSHashEntry {
79 JSHashEntry *next; /* hash chain linkage */
80 JSHashNumber keyHash; /* key hash function result */
81 const void *key; /* ptr to opaque key */
82 void *value; /* ptr to opaque value */
83 };
84
85 struct JSHashTable {
86 JSHashEntry **buckets; /* vector of hash buckets */
87 uint32 nentries; /* number of entries in table */
88 uint32 shift; /* multiplicative hash shift */
89 JSHashFunction keyHash; /* key hash function */
90 JSHashComparator keyCompare; /* key comparison function */
91 JSHashComparator valueCompare; /* value comparison function */
92 JSHashAllocOps *allocOps; /* allocation operations */
93 void *allocPriv; /* allocation private data */
94 #ifdef JS_HASHMETER
95 uint32 nlookups; /* total number of lookups */
96 uint32 nsteps; /* number of hash chains traversed */
97 uint32 ngrows; /* number of table expansions */
98 uint32 nshrinks; /* number of table contractions */
99 #endif
100 };
101
102 /*
103 * Create a new hash table.
104 * If allocOps is null, use default allocator ops built on top of malloc().
105 */
106 extern JS_PUBLIC_API(JSHashTable *)
107 JS_NewHashTable(uint32 n, JSHashFunction keyHash,
108 JSHashComparator keyCompare, JSHashComparator valueCompare,
109 JSHashAllocOps *allocOps, void *allocPriv);
110
111 extern JS_PUBLIC_API(void)
112 JS_HashTableDestroy(JSHashTable *ht);
113
114 /* Low level access methods */
115 extern JS_PUBLIC_API(JSHashEntry **)
116 JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key);
117
118 #ifdef __cplusplus
119 extern JS_PUBLIC_API(JSHashEntry *)
120 JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash,
121 const void *key, void *value);
122 #endif
123
124 extern JS_PUBLIC_API(void)
125 JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he);
126
127 /* Higher level access methods */
128 extern JS_PUBLIC_API(JSHashEntry *)
129 JS_HashTableAdd(JSHashTable *ht, const void *key, void *value);
130
131 extern JS_PUBLIC_API(JSBool)
132 JS_HashTableRemove(JSHashTable *ht, const void *key);
133
134 extern JS_PUBLIC_API(intN)
135 JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg);
136
137 extern JS_PUBLIC_API(void *)
138 JS_HashTableLookup(JSHashTable *ht, const void *key);
139
140 extern JS_PUBLIC_API(intN)
141 JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp);
142
143 /* General-purpose C string hash function. */
144 extern JS_PUBLIC_API(JSHashNumber)
145 JS_HashString(const void *key);
146
147 /* Stub function just returns v1 == v2 */
148 extern JS_PUBLIC_API(intN)
149 JS_CompareValues(const void *v1, const void *v2);
150
151 JS_END_EXTERN_C
152
153 #endif /* jshash_h___ */

  ViewVC Help
Powered by ViewVC 1.1.24