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 |
/* |
41 |
* JS atom table. |
42 |
*/ |
43 |
#include <stdlib.h> |
44 |
#include <string.h> |
45 |
#include "jstypes.h" |
46 |
#include "jsstdint.h" |
47 |
#include "jsutil.h" /* Added by JSIFY */ |
48 |
#include "jshash.h" /* Added by JSIFY */ |
49 |
#include "jsprf.h" |
50 |
#include "jsapi.h" |
51 |
#include "jsatom.h" |
52 |
#include "jsbit.h" |
53 |
#include "jscntxt.h" |
54 |
#include "jsgc.h" |
55 |
#include "jslock.h" |
56 |
#include "jsnum.h" |
57 |
#include "jsparse.h" |
58 |
#include "jsscan.h" |
59 |
#include "jsstr.h" |
60 |
#include "jsversion.h" |
61 |
#include "jsstrinlines.h" |
62 |
|
63 |
/* |
64 |
* ATOM_HASH assumes that JSHashNumber is 32-bit even on 64-bit systems. |
65 |
*/ |
66 |
JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4); |
67 |
JS_STATIC_ASSERT(sizeof(JSAtom *) == JS_BYTES_PER_WORD); |
68 |
|
69 |
/* |
70 |
* Start and limit offsets for atom pointers in JSAtomState must be aligned |
71 |
* on the word boundary. |
72 |
*/ |
73 |
JS_STATIC_ASSERT(ATOM_OFFSET_START % sizeof(JSAtom *) == 0); |
74 |
JS_STATIC_ASSERT(ATOM_OFFSET_LIMIT % sizeof(JSAtom *) == 0); |
75 |
|
76 |
/* |
77 |
* JS_BOOLEAN_STR and JS_TYPE_STR assume that boolean names starts from the |
78 |
* index 1 and type name starts from the index 1+2 atoms in JSAtomState. |
79 |
*/ |
80 |
JS_STATIC_ASSERT(1 * sizeof(JSAtom *) == |
81 |
offsetof(JSAtomState, booleanAtoms) - ATOM_OFFSET_START); |
82 |
JS_STATIC_ASSERT((1 + 2) * sizeof(JSAtom *) == |
83 |
offsetof(JSAtomState, typeAtoms) - ATOM_OFFSET_START); |
84 |
|
85 |
const char * |
86 |
js_AtomToPrintableString(JSContext *cx, JSAtom *atom) |
87 |
{ |
88 |
return js_ValueToPrintableString(cx, ATOM_KEY(atom)); |
89 |
} |
90 |
|
91 |
#define JS_PROTO(name,code,init) const char js_##name##_str[] = #name; |
92 |
#include "jsproto.tbl" |
93 |
#undef JS_PROTO |
94 |
|
95 |
/* |
96 |
* String constants for common atoms defined in JSAtomState starting from |
97 |
* JSAtomState.emptyAtom until JSAtomState.lazy. |
98 |
* |
99 |
* The elements of the array after the first empty string define strings |
100 |
* corresponding to the two boolean literals, false and true, followed by the |
101 |
* JSType enumerators from jspubtd.h starting with "undefined" for JSTYPE_VOID |
102 |
* (which is special-value 2) and continuing as initialized below. The static |
103 |
* asserts check these relations. |
104 |
*/ |
105 |
JS_STATIC_ASSERT(JSTYPE_LIMIT == 8); |
106 |
JS_STATIC_ASSERT(JSTYPE_VOID == 0); |
107 |
|
108 |
const char *const js_common_atom_names[] = { |
109 |
"", /* emptyAtom */ |
110 |
js_false_str, /* booleanAtoms[0] */ |
111 |
js_true_str, /* booleanAtoms[1] */ |
112 |
js_undefined_str, /* typeAtoms[JSTYPE_VOID] */ |
113 |
js_object_str, /* typeAtoms[JSTYPE_OBJECT] */ |
114 |
js_function_str, /* typeAtoms[JSTYPE_FUNCTION] */ |
115 |
"string", /* typeAtoms[JSTYPE_STRING] */ |
116 |
"number", /* typeAtoms[JSTYPE_NUMBER] */ |
117 |
"boolean", /* typeAtoms[JSTYPE_BOOLEAN] */ |
118 |
js_null_str, /* typeAtoms[JSTYPE_NULL] */ |
119 |
"xml", /* typeAtoms[JSTYPE_XML] */ |
120 |
js_null_str, /* nullAtom */ |
121 |
|
122 |
#define JS_PROTO(name,code,init) js_##name##_str, |
123 |
#include "jsproto.tbl" |
124 |
#undef JS_PROTO |
125 |
|
126 |
js_anonymous_str, /* anonymousAtom */ |
127 |
js_apply_str, /* applyAtom */ |
128 |
js_arguments_str, /* argumentsAtom */ |
129 |
js_arity_str, /* arityAtom */ |
130 |
js_call_str, /* callAtom */ |
131 |
js_callee_str, /* calleeAtom */ |
132 |
js_caller_str, /* callerAtom */ |
133 |
js_class_prototype_str, /* classPrototypeAtom */ |
134 |
js_constructor_str, /* constructorAtom */ |
135 |
js_count_str, /* countAtom */ |
136 |
js_each_str, /* eachAtom */ |
137 |
js_eval_str, /* evalAtom */ |
138 |
js_fileName_str, /* fileNameAtom */ |
139 |
js_get_str, /* getAtom */ |
140 |
js_getter_str, /* getterAtom */ |
141 |
js_index_str, /* indexAtom */ |
142 |
js_input_str, /* inputAtom */ |
143 |
js_iterator_str, /* iteratorAtom */ |
144 |
js_length_str, /* lengthAtom */ |
145 |
js_lineNumber_str, /* lineNumberAtom */ |
146 |
js_message_str, /* messageAtom */ |
147 |
js_name_str, /* nameAtom */ |
148 |
js_next_str, /* nextAtom */ |
149 |
js_noSuchMethod_str, /* noSuchMethodAtom */ |
150 |
js_parent_str, /* parentAtom */ |
151 |
js_proto_str, /* protoAtom */ |
152 |
js_set_str, /* setAtom */ |
153 |
js_setter_str, /* setterAtom */ |
154 |
js_stack_str, /* stackAtom */ |
155 |
js_toLocaleString_str, /* toLocaleStringAtom */ |
156 |
js_toSource_str, /* toSourceAtom */ |
157 |
js_toString_str, /* toStringAtom */ |
158 |
js_valueOf_str, /* valueOfAtom */ |
159 |
js_toJSON_str, /* toJSONAtom */ |
160 |
"(void 0)", /* void0Atom */ |
161 |
|
162 |
#if JS_HAS_XML_SUPPORT |
163 |
js_etago_str, /* etagoAtom */ |
164 |
js_namespace_str, /* namespaceAtom */ |
165 |
js_ptagc_str, /* ptagcAtom */ |
166 |
js_qualifier_str, /* qualifierAtom */ |
167 |
js_space_str, /* spaceAtom */ |
168 |
js_stago_str, /* stagoAtom */ |
169 |
js_star_str, /* starAtom */ |
170 |
js_starQualifier_str, /* starQualifierAtom */ |
171 |
js_tagc_str, /* tagcAtom */ |
172 |
js_xml_str, /* xmlAtom */ |
173 |
#endif |
174 |
|
175 |
#ifdef NARCISSUS |
176 |
js___call___str, /* __call__Atom */ |
177 |
js___construct___str, /* __construct__Atom */ |
178 |
js___hasInstance___str, /* __hasInstance__Atom */ |
179 |
js_ExecutionContext_str, /* ExecutionContextAtom */ |
180 |
js_current_str, /* currentAtom */ |
181 |
#endif |
182 |
}; |
183 |
|
184 |
JS_STATIC_ASSERT(JS_ARRAY_LENGTH(js_common_atom_names) * sizeof(JSAtom *) == |
185 |
LAZY_ATOM_OFFSET_START - ATOM_OFFSET_START); |
186 |
|
187 |
/* |
188 |
* Interpreter macros called by the trace recorder assume common atom indexes |
189 |
* fit in one byte of immediate operand. |
190 |
*/ |
191 |
JS_STATIC_ASSERT(JS_ARRAY_LENGTH(js_common_atom_names) < 256); |
192 |
|
193 |
const size_t js_common_atom_count = JS_ARRAY_LENGTH(js_common_atom_names); |
194 |
|
195 |
const char js_anonymous_str[] = "anonymous"; |
196 |
const char js_apply_str[] = "apply"; |
197 |
const char js_arguments_str[] = "arguments"; |
198 |
const char js_arity_str[] = "arity"; |
199 |
const char js_call_str[] = "call"; |
200 |
const char js_callee_str[] = "callee"; |
201 |
const char js_caller_str[] = "caller"; |
202 |
const char js_class_prototype_str[] = "prototype"; |
203 |
const char js_constructor_str[] = "constructor"; |
204 |
const char js_count_str[] = "__count__"; |
205 |
const char js_each_str[] = "each"; |
206 |
const char js_eval_str[] = "eval"; |
207 |
const char js_fileName_str[] = "fileName"; |
208 |
const char js_get_str[] = "get"; |
209 |
const char js_getter_str[] = "getter"; |
210 |
const char js_index_str[] = "index"; |
211 |
const char js_input_str[] = "input"; |
212 |
const char js_iterator_str[] = "__iterator__"; |
213 |
const char js_length_str[] = "length"; |
214 |
const char js_lineNumber_str[] = "lineNumber"; |
215 |
const char js_message_str[] = "message"; |
216 |
const char js_name_str[] = "name"; |
217 |
const char js_next_str[] = "next"; |
218 |
const char js_noSuchMethod_str[] = "__noSuchMethod__"; |
219 |
const char js_object_str[] = "object"; |
220 |
const char js_parent_str[] = "__parent__"; |
221 |
const char js_proto_str[] = "__proto__"; |
222 |
const char js_setter_str[] = "setter"; |
223 |
const char js_set_str[] = "set"; |
224 |
const char js_stack_str[] = "stack"; |
225 |
const char js_toSource_str[] = "toSource"; |
226 |
const char js_toString_str[] = "toString"; |
227 |
const char js_toLocaleString_str[] = "toLocaleString"; |
228 |
const char js_undefined_str[] = "undefined"; |
229 |
const char js_valueOf_str[] = "valueOf"; |
230 |
const char js_toJSON_str[] = "toJSON"; |
231 |
|
232 |
#if JS_HAS_XML_SUPPORT |
233 |
const char js_etago_str[] = "</"; |
234 |
const char js_namespace_str[] = "namespace"; |
235 |
const char js_ptagc_str[] = "/>"; |
236 |
const char js_qualifier_str[] = "::"; |
237 |
const char js_space_str[] = " "; |
238 |
const char js_stago_str[] = "<"; |
239 |
const char js_star_str[] = "*"; |
240 |
const char js_starQualifier_str[] = "*::"; |
241 |
const char js_tagc_str[] = ">"; |
242 |
const char js_xml_str[] = "xml"; |
243 |
#endif |
244 |
|
245 |
#if JS_HAS_GENERATORS |
246 |
const char js_close_str[] = "close"; |
247 |
const char js_send_str[] = "send"; |
248 |
#endif |
249 |
|
250 |
#ifdef NARCISSUS |
251 |
const char js___call___str[] = "__call__"; |
252 |
const char js___construct___str[] = "__construct__"; |
253 |
const char js___hasInstance___str[] = "__hasInstance__"; |
254 |
const char js_ExecutionContext_str[] = "ExecutionContext"; |
255 |
const char js_current_str[] = "current"; |
256 |
#endif |
257 |
|
258 |
/* |
259 |
* JSAtomState.doubleAtoms and JSAtomState.stringAtoms hashtable entry. To |
260 |
* support pinned and interned string atoms, we use the lowest bits of the |
261 |
* keyAndFlags field to store ATOM_PINNED and ATOM_INTERNED flags. |
262 |
*/ |
263 |
typedef struct JSAtomHashEntry { |
264 |
JSDHashEntryHdr hdr; |
265 |
jsuword keyAndFlags; |
266 |
} JSAtomHashEntry; |
267 |
|
268 |
#define ATOM_ENTRY_FLAG_MASK (ATOM_PINNED | ATOM_INTERNED) |
269 |
|
270 |
JS_STATIC_ASSERT(ATOM_ENTRY_FLAG_MASK < JSVAL_ALIGN); |
271 |
|
272 |
/* |
273 |
* Helper macros to access and modify JSAtomHashEntry. |
274 |
*/ |
275 |
#define TO_ATOM_ENTRY(hdr) ((JSAtomHashEntry *) hdr) |
276 |
#define ATOM_ENTRY_KEY(entry) \ |
277 |
((void *)((entry)->keyAndFlags & ~ATOM_ENTRY_FLAG_MASK)) |
278 |
#define ATOM_ENTRY_FLAGS(entry) \ |
279 |
((uintN)((entry)->keyAndFlags & ATOM_ENTRY_FLAG_MASK)) |
280 |
#define INIT_ATOM_ENTRY(entry, key) \ |
281 |
((void)((entry)->keyAndFlags = (jsuword)(key))) |
282 |
#define ADD_ATOM_ENTRY_FLAGS(entry, flags) \ |
283 |
((void)((entry)->keyAndFlags |= (jsuword)(flags))) |
284 |
#define CLEAR_ATOM_ENTRY_FLAGS(entry, flags) \ |
285 |
((void)((entry)->keyAndFlags &= ~(jsuword)(flags))) |
286 |
|
287 |
static JSDHashNumber |
288 |
HashDouble(JSDHashTable *table, const void *key); |
289 |
|
290 |
static JSBool |
291 |
MatchDouble(JSDHashTable *table, const JSDHashEntryHdr *hdr, const void *key); |
292 |
|
293 |
static JSDHashNumber |
294 |
HashString(JSDHashTable *table, const void *key); |
295 |
|
296 |
static JSBool |
297 |
MatchString(JSDHashTable *table, const JSDHashEntryHdr *hdr, const void *key); |
298 |
|
299 |
static const JSDHashTableOps DoubleHashOps = { |
300 |
JS_DHashAllocTable, |
301 |
JS_DHashFreeTable, |
302 |
HashDouble, |
303 |
MatchDouble, |
304 |
JS_DHashMoveEntryStub, |
305 |
JS_DHashClearEntryStub, |
306 |
JS_DHashFinalizeStub, |
307 |
NULL |
308 |
}; |
309 |
|
310 |
static const JSDHashTableOps StringHashOps = { |
311 |
JS_DHashAllocTable, |
312 |
JS_DHashFreeTable, |
313 |
HashString, |
314 |
MatchString, |
315 |
JS_DHashMoveEntryStub, |
316 |
JS_DHashClearEntryStub, |
317 |
JS_DHashFinalizeStub, |
318 |
NULL |
319 |
}; |
320 |
|
321 |
#define IS_DOUBLE_TABLE(table) ((table)->ops == &DoubleHashOps) |
322 |
#define IS_STRING_TABLE(table) ((table)->ops == &StringHashOps) |
323 |
|
324 |
#define IS_INITIALIZED_STATE(state) IS_DOUBLE_TABLE(&(state)->doubleAtoms) |
325 |
|
326 |
static JSDHashNumber |
327 |
HashDouble(JSDHashTable *table, const void *key) |
328 |
{ |
329 |
JS_ASSERT(IS_DOUBLE_TABLE(table)); |
330 |
return JS_HASH_DOUBLE(*(jsdouble *)key); |
331 |
} |
332 |
|
333 |
static JSDHashNumber |
334 |
HashString(JSDHashTable *table, const void *key) |
335 |
{ |
336 |
JS_ASSERT(IS_STRING_TABLE(table)); |
337 |
return js_HashString((JSString *)key); |
338 |
} |
339 |
|
340 |
static JSBool |
341 |
MatchDouble(JSDHashTable *table, const JSDHashEntryHdr *hdr, const void *key) |
342 |
{ |
343 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
344 |
jsdouble d1, d2; |
345 |
|
346 |
JS_ASSERT(IS_DOUBLE_TABLE(table)); |
347 |
if (entry->keyAndFlags == 0) { |
348 |
/* See comments in MatchString. */ |
349 |
return JS_FALSE; |
350 |
} |
351 |
|
352 |
d1 = *(jsdouble *)ATOM_ENTRY_KEY(entry); |
353 |
d2 = *(jsdouble *)key; |
354 |
if (JSDOUBLE_IS_NaN(d1)) |
355 |
return JSDOUBLE_IS_NaN(d2); |
356 |
#if defined(XP_WIN) |
357 |
/* XXX MSVC miscompiles such that (NaN == 0) */ |
358 |
if (JSDOUBLE_IS_NaN(d2)) |
359 |
return JS_FALSE; |
360 |
#endif |
361 |
return d1 == d2; |
362 |
} |
363 |
|
364 |
static JSBool |
365 |
MatchString(JSDHashTable *table, const JSDHashEntryHdr *hdr, const void *key) |
366 |
{ |
367 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
368 |
|
369 |
JS_ASSERT(IS_STRING_TABLE(table)); |
370 |
if (entry->keyAndFlags == 0) { |
371 |
/* |
372 |
* This happens when js_AtomizeString adds a new hash entry and |
373 |
* releases the lock but before it takes the lock the second time to |
374 |
* initialize keyAndFlags for the entry. |
375 |
* |
376 |
* We always return false for such entries so JS_DHashTableOperate |
377 |
* never finds them. We clean them during GC's sweep phase. |
378 |
* |
379 |
* It means that with a contested lock or when GC is triggered outside |
380 |
* the lock we may end up adding two entries, but this is a price for |
381 |
* simpler code. |
382 |
*/ |
383 |
return JS_FALSE; |
384 |
} |
385 |
return js_EqualStrings((JSString *)ATOM_ENTRY_KEY(entry), (JSString *)key); |
386 |
} |
387 |
|
388 |
/* |
389 |
* For a browser build from 2007-08-09 after the browser starts up there are |
390 |
* just 55 double atoms, but over 15000 string atoms. Not to penalize more |
391 |
* economical embeddings allocating too much memory initially we initialize |
392 |
* atomized strings with just 1K entries. |
393 |
*/ |
394 |
#define JS_STRING_HASH_COUNT 1024 |
395 |
#define JS_DOUBLE_HASH_COUNT 64 |
396 |
|
397 |
JSBool |
398 |
js_InitAtomState(JSRuntime *rt) |
399 |
{ |
400 |
JSAtomState *state = &rt->atomState; |
401 |
|
402 |
/* |
403 |
* The caller must zero the state before calling this function. |
404 |
*/ |
405 |
JS_ASSERT(!state->stringAtoms.ops); |
406 |
JS_ASSERT(!state->doubleAtoms.ops); |
407 |
|
408 |
if (!JS_DHashTableInit(&state->stringAtoms, &StringHashOps, |
409 |
NULL, sizeof(JSAtomHashEntry), |
410 |
JS_DHASH_DEFAULT_CAPACITY(JS_STRING_HASH_COUNT))) { |
411 |
state->stringAtoms.ops = NULL; |
412 |
return JS_FALSE; |
413 |
} |
414 |
JS_ASSERT(IS_STRING_TABLE(&state->stringAtoms)); |
415 |
|
416 |
if (!JS_DHashTableInit(&state->doubleAtoms, &DoubleHashOps, |
417 |
NULL, sizeof(JSAtomHashEntry), |
418 |
JS_DHASH_DEFAULT_CAPACITY(JS_DOUBLE_HASH_COUNT))) { |
419 |
state->doubleAtoms.ops = NULL; |
420 |
JS_DHashTableFinish(&state->stringAtoms); |
421 |
state->stringAtoms.ops = NULL; |
422 |
return JS_FALSE; |
423 |
} |
424 |
JS_ASSERT(IS_DOUBLE_TABLE(&state->doubleAtoms)); |
425 |
|
426 |
#ifdef JS_THREADSAFE |
427 |
js_InitLock(&state->lock); |
428 |
#endif |
429 |
JS_ASSERT(IS_INITIALIZED_STATE(state)); |
430 |
return JS_TRUE; |
431 |
} |
432 |
|
433 |
static JSDHashOperator |
434 |
js_string_uninterner(JSDHashTable *table, JSDHashEntryHdr *hdr, |
435 |
uint32 number, void *arg) |
436 |
{ |
437 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
438 |
JSRuntime *rt = (JSRuntime *)arg; |
439 |
JSString *str; |
440 |
|
441 |
/* |
442 |
* Any string entry that remains at this point must be initialized, as the |
443 |
* last GC should clean any uninitialized ones. |
444 |
*/ |
445 |
JS_ASSERT(IS_STRING_TABLE(table)); |
446 |
JS_ASSERT(entry->keyAndFlags != 0); |
447 |
str = (JSString *)ATOM_ENTRY_KEY(entry); |
448 |
|
449 |
/* Pass null as context. */ |
450 |
js_FinalizeStringRT(rt, str, js_GetExternalStringGCType(str), NULL); |
451 |
return JS_DHASH_NEXT; |
452 |
} |
453 |
|
454 |
void |
455 |
js_FinishAtomState(JSRuntime *rt) |
456 |
{ |
457 |
JSAtomState *state = &rt->atomState; |
458 |
|
459 |
if (!IS_INITIALIZED_STATE(state)) { |
460 |
/* |
461 |
* We are called with uninitialized state when JS_NewRuntime fails and |
462 |
* calls JS_DestroyRuntime on a partially initialized runtime. |
463 |
*/ |
464 |
return; |
465 |
} |
466 |
|
467 |
JS_DHashTableEnumerate(&state->stringAtoms, js_string_uninterner, rt); |
468 |
JS_DHashTableFinish(&state->stringAtoms); |
469 |
JS_DHashTableFinish(&state->doubleAtoms); |
470 |
|
471 |
#ifdef JS_THREADSAFE |
472 |
js_FinishLock(&state->lock); |
473 |
#endif |
474 |
#ifdef DEBUG |
475 |
memset(state, JS_FREE_PATTERN, sizeof *state); |
476 |
#endif |
477 |
} |
478 |
|
479 |
JSBool |
480 |
js_InitCommonAtoms(JSContext *cx) |
481 |
{ |
482 |
JSAtomState *state = &cx->runtime->atomState; |
483 |
uintN i; |
484 |
JSAtom **atoms; |
485 |
|
486 |
atoms = COMMON_ATOMS_START(state); |
487 |
for (i = 0; i < JS_ARRAY_LENGTH(js_common_atom_names); i++, atoms++) { |
488 |
*atoms = js_Atomize(cx, js_common_atom_names[i], |
489 |
strlen(js_common_atom_names[i]), ATOM_PINNED); |
490 |
if (!*atoms) |
491 |
return JS_FALSE; |
492 |
} |
493 |
JS_ASSERT((uint8 *)atoms - (uint8 *)state == LAZY_ATOM_OFFSET_START); |
494 |
memset(atoms, 0, ATOM_OFFSET_LIMIT - LAZY_ATOM_OFFSET_START); |
495 |
|
496 |
return JS_TRUE; |
497 |
} |
498 |
|
499 |
static JSDHashOperator |
500 |
js_atom_unpinner(JSDHashTable *table, JSDHashEntryHdr *hdr, |
501 |
uint32 number, void *arg) |
502 |
{ |
503 |
JS_ASSERT(IS_STRING_TABLE(table)); |
504 |
CLEAR_ATOM_ENTRY_FLAGS(TO_ATOM_ENTRY(hdr), ATOM_PINNED); |
505 |
return JS_DHASH_NEXT; |
506 |
} |
507 |
|
508 |
void |
509 |
js_FinishCommonAtoms(JSContext *cx) |
510 |
{ |
511 |
JSAtomState *state = &cx->runtime->atomState; |
512 |
|
513 |
JS_DHashTableEnumerate(&state->stringAtoms, js_atom_unpinner, NULL); |
514 |
#ifdef DEBUG |
515 |
memset(COMMON_ATOMS_START(state), JS_FREE_PATTERN, |
516 |
ATOM_OFFSET_LIMIT - ATOM_OFFSET_START); |
517 |
#endif |
518 |
} |
519 |
|
520 |
static JSDHashOperator |
521 |
js_locked_atom_tracer(JSDHashTable *table, JSDHashEntryHdr *hdr, |
522 |
uint32 number, void *arg) |
523 |
{ |
524 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
525 |
JSTracer *trc = (JSTracer *)arg; |
526 |
|
527 |
if (entry->keyAndFlags == 0) { |
528 |
/* Ignore uninitialized entries during tracing. */ |
529 |
return JS_DHASH_NEXT; |
530 |
} |
531 |
JS_SET_TRACING_INDEX(trc, "locked_atom", (size_t)number); |
532 |
JS_CallTracer(trc, ATOM_ENTRY_KEY(entry), |
533 |
IS_STRING_TABLE(table) ? JSTRACE_STRING : JSTRACE_DOUBLE); |
534 |
return JS_DHASH_NEXT; |
535 |
} |
536 |
|
537 |
static JSDHashOperator |
538 |
js_pinned_atom_tracer(JSDHashTable *table, JSDHashEntryHdr *hdr, |
539 |
uint32 number, void *arg) |
540 |
{ |
541 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
542 |
JSTracer *trc = (JSTracer *)arg; |
543 |
uintN flags = ATOM_ENTRY_FLAGS(entry); |
544 |
|
545 |
JS_ASSERT(IS_STRING_TABLE(table)); |
546 |
if (flags & (ATOM_PINNED | ATOM_INTERNED)) { |
547 |
JS_SET_TRACING_INDEX(trc, |
548 |
flags & ATOM_PINNED |
549 |
? "pinned_atom" |
550 |
: "interned_atom", |
551 |
(size_t)number); |
552 |
JS_CallTracer(trc, ATOM_ENTRY_KEY(entry), JSTRACE_STRING); |
553 |
} |
554 |
return JS_DHASH_NEXT; |
555 |
} |
556 |
|
557 |
void |
558 |
js_TraceAtomState(JSTracer *trc, JSBool allAtoms) |
559 |
{ |
560 |
JSRuntime *rt = trc->context->runtime; |
561 |
JSAtomState *state = &rt->atomState; |
562 |
|
563 |
if (allAtoms) { |
564 |
JS_DHashTableEnumerate(&state->doubleAtoms, js_locked_atom_tracer, trc); |
565 |
JS_DHashTableEnumerate(&state->stringAtoms, js_locked_atom_tracer, trc); |
566 |
} else { |
567 |
JS_DHashTableEnumerate(&state->stringAtoms, js_pinned_atom_tracer, trc); |
568 |
} |
569 |
} |
570 |
|
571 |
static JSDHashOperator |
572 |
js_atom_sweeper(JSDHashTable *table, JSDHashEntryHdr *hdr, |
573 |
uint32 number, void *arg) |
574 |
{ |
575 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
576 |
JSContext *cx = (JSContext *)arg; |
577 |
|
578 |
/* Remove uninitialized entries. */ |
579 |
if (entry->keyAndFlags == 0) |
580 |
return JS_DHASH_REMOVE; |
581 |
|
582 |
if (ATOM_ENTRY_FLAGS(entry) & (ATOM_PINNED | ATOM_INTERNED)) { |
583 |
/* Pinned or interned key cannot be finalized. */ |
584 |
JS_ASSERT(!js_IsAboutToBeFinalized(cx, ATOM_ENTRY_KEY(entry))); |
585 |
} else if (js_IsAboutToBeFinalized(cx, ATOM_ENTRY_KEY(entry))) { |
586 |
/* Remove entries with things about to be GC'ed. */ |
587 |
return JS_DHASH_REMOVE; |
588 |
} |
589 |
return JS_DHASH_NEXT; |
590 |
} |
591 |
|
592 |
void |
593 |
js_SweepAtomState(JSContext *cx) |
594 |
{ |
595 |
JSAtomState *state = &cx->runtime->atomState; |
596 |
|
597 |
JS_DHashTableEnumerate(&state->doubleAtoms, js_atom_sweeper, cx); |
598 |
JS_DHashTableEnumerate(&state->stringAtoms, js_atom_sweeper, cx); |
599 |
|
600 |
/* |
601 |
* Optimize for simplicity and mutate table generation numbers even if the |
602 |
* sweeper has not removed any entries. |
603 |
*/ |
604 |
state->doubleAtoms.generation++; |
605 |
state->stringAtoms.generation++; |
606 |
} |
607 |
|
608 |
JSAtom * |
609 |
js_AtomizeDouble(JSContext *cx, jsdouble d) |
610 |
{ |
611 |
JSAtomState *state; |
612 |
JSDHashTable *table; |
613 |
JSAtomHashEntry *entry; |
614 |
uint32 gen; |
615 |
jsdouble *key; |
616 |
jsval v; |
617 |
|
618 |
state = &cx->runtime->atomState; |
619 |
table = &state->doubleAtoms; |
620 |
|
621 |
JS_LOCK(cx, &state->lock); |
622 |
entry = TO_ATOM_ENTRY(JS_DHashTableOperate(table, &d, JS_DHASH_ADD)); |
623 |
if (!entry) |
624 |
goto failed_hash_add; |
625 |
if (entry->keyAndFlags == 0) { |
626 |
gen = ++table->generation; |
627 |
JS_UNLOCK(cx, &state->lock); |
628 |
|
629 |
key = js_NewWeaklyRootedDouble(cx, d); |
630 |
if (!key) |
631 |
return NULL; |
632 |
|
633 |
JS_LOCK(cx, &state->lock); |
634 |
if (table->generation == gen) { |
635 |
JS_ASSERT(entry->keyAndFlags == 0); |
636 |
} else { |
637 |
entry = TO_ATOM_ENTRY(JS_DHashTableOperate(table, key, |
638 |
JS_DHASH_ADD)); |
639 |
if (!entry) |
640 |
goto failed_hash_add; |
641 |
if (entry->keyAndFlags != 0) |
642 |
goto finish; |
643 |
++table->generation; |
644 |
} |
645 |
INIT_ATOM_ENTRY(entry, key); |
646 |
} |
647 |
|
648 |
finish: |
649 |
v = DOUBLE_TO_JSVAL((jsdouble *)ATOM_ENTRY_KEY(entry)); |
650 |
cx->weakRoots.lastAtom = v; |
651 |
JS_UNLOCK(cx, &state->lock); |
652 |
|
653 |
return (JSAtom *)v; |
654 |
|
655 |
failed_hash_add: |
656 |
JS_UNLOCK(cx, &state->lock); |
657 |
JS_ReportOutOfMemory(cx); |
658 |
return NULL; |
659 |
} |
660 |
|
661 |
JSAtom * |
662 |
js_AtomizeString(JSContext *cx, JSString *str, uintN flags) |
663 |
{ |
664 |
jsval v; |
665 |
JSAtomState *state; |
666 |
JSDHashTable *table; |
667 |
JSAtomHashEntry *entry; |
668 |
JSString *key; |
669 |
uint32 gen; |
670 |
|
671 |
JS_ASSERT(!(flags & ~(ATOM_PINNED|ATOM_INTERNED|ATOM_TMPSTR|ATOM_NOCOPY))); |
672 |
JS_ASSERT_IF(flags & ATOM_NOCOPY, flags & ATOM_TMPSTR); |
673 |
|
674 |
if (str->isAtomized()) |
675 |
return (JSAtom *) STRING_TO_JSVAL(str); |
676 |
|
677 |
size_t length = str->length(); |
678 |
if (length == 1) { |
679 |
jschar c = str->chars()[0]; |
680 |
if (c < UNIT_STRING_LIMIT) |
681 |
return (JSAtom *) STRING_TO_JSVAL(JSString::unitString(c)); |
682 |
} |
683 |
|
684 |
/* |
685 |
* Here we know that JSString::intStringTable covers only 256 (or at least |
686 |
* not 1000 or more) chars. We rely on order here to resolve the unit vs. |
687 |
* int string atom identity issue by giving priority to unit strings for |
688 |
* '0' through '9' (see JSString::intString in jsstrinlines.h). |
689 |
*/ |
690 |
JS_STATIC_ASSERT(INT_STRING_LIMIT <= 999); |
691 |
if (2 <= length && length <= 3) { |
692 |
const jschar *chars = str->chars(); |
693 |
|
694 |
if ('1' <= chars[0] && chars[0] <= '9' && |
695 |
'0' <= chars[1] && chars[1] <= '9' && |
696 |
(length == 2 || ('0' <= chars[2] && chars[2] <= '9'))) { |
697 |
jsint i = (chars[0] - '0') * 10 + chars[1] - '0'; |
698 |
|
699 |
if (length == 3) |
700 |
i = i * 10 + chars[2] - '0'; |
701 |
if (jsuint(i) < INT_STRING_LIMIT) |
702 |
return (JSAtom *) STRING_TO_JSVAL(JSString::intString(i)); |
703 |
} |
704 |
} |
705 |
|
706 |
state = &cx->runtime->atomState; |
707 |
table = &state->stringAtoms; |
708 |
|
709 |
JS_LOCK(cx, &state->lock); |
710 |
entry = TO_ATOM_ENTRY(JS_DHashTableOperate(table, str, JS_DHASH_ADD)); |
711 |
if (!entry) |
712 |
goto failed_hash_add; |
713 |
if (entry->keyAndFlags != 0) { |
714 |
key = (JSString *)ATOM_ENTRY_KEY(entry); |
715 |
} else { |
716 |
/* |
717 |
* We created a new hashtable entry. Unless str is already allocated |
718 |
* from the GC heap and flat, we have to release state->lock as |
719 |
* string construction is a complex operation. For example, it can |
720 |
* trigger GC which may rehash the table and make the entry invalid. |
721 |
*/ |
722 |
++table->generation; |
723 |
if (!(flags & ATOM_TMPSTR) && str->isFlat()) { |
724 |
str->flatClearMutable(); |
725 |
key = str; |
726 |
} else { |
727 |
gen = table->generation; |
728 |
JS_UNLOCK(cx, &state->lock); |
729 |
|
730 |
if (flags & ATOM_TMPSTR) { |
731 |
if (flags & ATOM_NOCOPY) { |
732 |
key = js_NewString(cx, str->flatChars(), str->flatLength()); |
733 |
if (!key) |
734 |
return NULL; |
735 |
|
736 |
/* Finish handing off chars to the GC'ed key string. */ |
737 |
str->mChars = NULL; |
738 |
} else { |
739 |
key = js_NewStringCopyN(cx, str->flatChars(), str->flatLength()); |
740 |
if (!key) |
741 |
return NULL; |
742 |
} |
743 |
} else { |
744 |
JS_ASSERT(str->isDependent()); |
745 |
if (!js_UndependString(cx, str)) |
746 |
return NULL; |
747 |
key = str; |
748 |
} |
749 |
|
750 |
JS_LOCK(cx, &state->lock); |
751 |
if (table->generation == gen) { |
752 |
JS_ASSERT(entry->keyAndFlags == 0); |
753 |
} else { |
754 |
entry = TO_ATOM_ENTRY(JS_DHashTableOperate(table, key, |
755 |
JS_DHASH_ADD)); |
756 |
if (!entry) |
757 |
goto failed_hash_add; |
758 |
if (entry->keyAndFlags != 0) { |
759 |
key = (JSString *)ATOM_ENTRY_KEY(entry); |
760 |
goto finish; |
761 |
} |
762 |
++table->generation; |
763 |
} |
764 |
} |
765 |
INIT_ATOM_ENTRY(entry, key); |
766 |
key->flatSetAtomized(); |
767 |
} |
768 |
|
769 |
finish: |
770 |
ADD_ATOM_ENTRY_FLAGS(entry, flags & (ATOM_PINNED | ATOM_INTERNED)); |
771 |
JS_ASSERT(key->isAtomized()); |
772 |
v = STRING_TO_JSVAL(key); |
773 |
cx->weakRoots.lastAtom = v; |
774 |
JS_UNLOCK(cx, &state->lock); |
775 |
return (JSAtom *)v; |
776 |
|
777 |
failed_hash_add: |
778 |
JS_UNLOCK(cx, &state->lock); |
779 |
JS_ReportOutOfMemory(cx); |
780 |
return NULL; |
781 |
} |
782 |
|
783 |
JSAtom * |
784 |
js_Atomize(JSContext *cx, const char *bytes, size_t length, uintN flags) |
785 |
{ |
786 |
jschar *chars; |
787 |
JSString str; |
788 |
JSAtom *atom; |
789 |
|
790 |
/* |
791 |
* Avoiding the malloc in js_InflateString on shorter strings saves us |
792 |
* over 20,000 malloc calls on mozilla browser startup. This compares to |
793 |
* only 131 calls where the string is longer than a 31 char (net) buffer. |
794 |
* The vast majority of atomized strings are already in the hashtable. So |
795 |
* js_AtomizeString rarely has to copy the temp string we make. |
796 |
*/ |
797 |
#define ATOMIZE_BUF_MAX 32 |
798 |
jschar inflated[ATOMIZE_BUF_MAX]; |
799 |
size_t inflatedLength = ATOMIZE_BUF_MAX - 1; |
800 |
|
801 |
if (length < ATOMIZE_BUF_MAX) { |
802 |
js_InflateStringToBuffer(cx, bytes, length, inflated, &inflatedLength); |
803 |
inflated[inflatedLength] = 0; |
804 |
chars = inflated; |
805 |
} else { |
806 |
inflatedLength = length; |
807 |
chars = js_InflateString(cx, bytes, &inflatedLength); |
808 |
if (!chars) |
809 |
return NULL; |
810 |
flags |= ATOM_NOCOPY; |
811 |
} |
812 |
|
813 |
str.initFlat(chars, inflatedLength); |
814 |
atom = js_AtomizeString(cx, &str, ATOM_TMPSTR | flags); |
815 |
if (chars != inflated && str.flatChars()) |
816 |
cx->free(chars); |
817 |
return atom; |
818 |
} |
819 |
|
820 |
JSAtom * |
821 |
js_AtomizeChars(JSContext *cx, const jschar *chars, size_t length, uintN flags) |
822 |
{ |
823 |
JSString str; |
824 |
|
825 |
str.initFlat((jschar *)chars, length); |
826 |
return js_AtomizeString(cx, &str, ATOM_TMPSTR | flags); |
827 |
} |
828 |
|
829 |
JSAtom * |
830 |
js_GetExistingStringAtom(JSContext *cx, const jschar *chars, size_t length) |
831 |
{ |
832 |
JSString str, *str2; |
833 |
JSAtomState *state; |
834 |
JSDHashEntryHdr *hdr; |
835 |
|
836 |
if (length == 1) { |
837 |
jschar c = *chars; |
838 |
if (c < UNIT_STRING_LIMIT) |
839 |
return (JSAtom *) STRING_TO_JSVAL(JSString::unitString(c)); |
840 |
} |
841 |
|
842 |
str.initFlat((jschar *)chars, length); |
843 |
state = &cx->runtime->atomState; |
844 |
|
845 |
JS_LOCK(cx, &state->lock); |
846 |
hdr = JS_DHashTableOperate(&state->stringAtoms, &str, JS_DHASH_LOOKUP); |
847 |
str2 = JS_DHASH_ENTRY_IS_BUSY(hdr) |
848 |
? (JSString *)ATOM_ENTRY_KEY(TO_ATOM_ENTRY(hdr)) |
849 |
: NULL; |
850 |
JS_UNLOCK(cx, &state->lock); |
851 |
|
852 |
return str2 ? (JSAtom *)STRING_TO_JSVAL(str2) : NULL; |
853 |
} |
854 |
|
855 |
JSBool |
856 |
js_AtomizePrimitiveValue(JSContext *cx, jsval v, JSAtom **atomp) |
857 |
{ |
858 |
JSAtom *atom; |
859 |
|
860 |
if (JSVAL_IS_STRING(v)) { |
861 |
atom = js_AtomizeString(cx, JSVAL_TO_STRING(v), 0); |
862 |
if (!atom) |
863 |
return JS_FALSE; |
864 |
} else if (JSVAL_IS_DOUBLE(v)) { |
865 |
atom = js_AtomizeDouble(cx, *JSVAL_TO_DOUBLE(v)); |
866 |
if (!atom) |
867 |
return JS_FALSE; |
868 |
} else { |
869 |
JS_ASSERT(JSVAL_IS_INT(v) || JSVAL_IS_BOOLEAN(v) || |
870 |
JSVAL_IS_NULL(v) || JSVAL_IS_VOID(v)); |
871 |
atom = (JSAtom *)v; |
872 |
} |
873 |
*atomp = atom; |
874 |
return JS_TRUE; |
875 |
} |
876 |
|
877 |
#ifdef DEBUG |
878 |
|
879 |
static JSDHashOperator |
880 |
atom_dumper(JSDHashTable *table, JSDHashEntryHdr *hdr, |
881 |
uint32 number, void *arg) |
882 |
{ |
883 |
JSAtomHashEntry *entry = TO_ATOM_ENTRY(hdr); |
884 |
FILE *fp = (FILE *)arg; |
885 |
void *key; |
886 |
uintN flags; |
887 |
|
888 |
fprintf(fp, "%3u %08x ", number, (uintN)entry->hdr.keyHash); |
889 |
if (entry->keyAndFlags == 0) { |
890 |
fputs("<uninitialized>", fp); |
891 |
} else { |
892 |
key = ATOM_ENTRY_KEY(entry); |
893 |
if (IS_DOUBLE_TABLE(table)) { |
894 |
fprintf(fp, "%.16g", *(jsdouble *)key); |
895 |
} else { |
896 |
JS_ASSERT(IS_STRING_TABLE(table)); |
897 |
js_FileEscapedString(fp, (JSString *)key, '"'); |
898 |
} |
899 |
flags = ATOM_ENTRY_FLAGS(entry); |
900 |
if (flags != 0) { |
901 |
fputs((flags & (ATOM_PINNED | ATOM_INTERNED)) |
902 |
? " pinned | interned" |
903 |
: (flags & ATOM_PINNED) ? " pinned" : " interned", |
904 |
fp); |
905 |
} |
906 |
} |
907 |
putc('\n', fp); |
908 |
return JS_DHASH_NEXT; |
909 |
} |
910 |
|
911 |
JS_FRIEND_API(void) |
912 |
js_DumpAtoms(JSContext *cx, FILE *fp) |
913 |
{ |
914 |
JSAtomState *state = &cx->runtime->atomState; |
915 |
|
916 |
fprintf(fp, "stringAtoms table contents:\n"); |
917 |
JS_DHashTableEnumerate(&state->stringAtoms, atom_dumper, fp); |
918 |
#ifdef JS_DHASHMETER |
919 |
JS_DHashTableDumpMeter(&state->stringAtoms, atom_dumper, fp); |
920 |
#endif |
921 |
putc('\n', fp); |
922 |
|
923 |
fprintf(fp, "doubleAtoms table contents:\n"); |
924 |
JS_DHashTableEnumerate(&state->doubleAtoms, atom_dumper, fp); |
925 |
#ifdef JS_DHASHMETER |
926 |
JS_DHashTableDumpMeter(&state->doubleAtoms, atom_dumper, fp); |
927 |
#endif |
928 |
putc('\n', fp); |
929 |
} |
930 |
|
931 |
#endif |
932 |
|
933 |
static JSHashNumber |
934 |
js_hash_atom_ptr(const void *key) |
935 |
{ |
936 |
const JSAtom *atom = (const JSAtom *) key; |
937 |
return ATOM_HASH(atom); |
938 |
} |
939 |
|
940 |
#if JS_BITS_PER_WORD == 32 |
941 |
# define TEMP_SIZE_START_LOG2 5 |
942 |
#else |
943 |
# define TEMP_SIZE_START_LOG2 6 |
944 |
#endif |
945 |
#define TEMP_SIZE_LIMIT_LOG2 (TEMP_SIZE_START_LOG2 + NUM_TEMP_FREELISTS) |
946 |
|
947 |
#define TEMP_SIZE_START JS_BIT(TEMP_SIZE_START_LOG2) |
948 |
#define TEMP_SIZE_LIMIT JS_BIT(TEMP_SIZE_LIMIT_LOG2) |
949 |
|
950 |
JS_STATIC_ASSERT(TEMP_SIZE_START >= sizeof(JSHashTable)); |
951 |
|
952 |
static void * |
953 |
js_alloc_temp_space(void *priv, size_t size) |
954 |
{ |
955 |
JSCompiler *jsc = (JSCompiler *) priv; |
956 |
|
957 |
void *space; |
958 |
if (size < TEMP_SIZE_LIMIT) { |
959 |
int bin = JS_CeilingLog2(size) - TEMP_SIZE_START_LOG2; |
960 |
JS_ASSERT(unsigned(bin) < NUM_TEMP_FREELISTS); |
961 |
|
962 |
space = jsc->tempFreeList[bin]; |
963 |
if (space) { |
964 |
jsc->tempFreeList[bin] = *(void **)space; |
965 |
return space; |
966 |
} |
967 |
} |
968 |
|
969 |
JS_ARENA_ALLOCATE(space, &jsc->context->tempPool, size); |
970 |
if (!space) |
971 |
js_ReportOutOfScriptQuota(jsc->context); |
972 |
return space; |
973 |
} |
974 |
|
975 |
static void |
976 |
js_free_temp_space(void *priv, void *item, size_t size) |
977 |
{ |
978 |
if (size >= TEMP_SIZE_LIMIT) |
979 |
return; |
980 |
|
981 |
JSCompiler *jsc = (JSCompiler *) priv; |
982 |
int bin = JS_CeilingLog2(size) - TEMP_SIZE_START_LOG2; |
983 |
JS_ASSERT(unsigned(bin) < NUM_TEMP_FREELISTS); |
984 |
|
985 |
*(void **)item = jsc->tempFreeList[bin]; |
986 |
jsc->tempFreeList[bin] = item; |
987 |
} |
988 |
|
989 |
static JSHashEntry * |
990 |
js_alloc_temp_entry(void *priv, const void *key) |
991 |
{ |
992 |
JSCompiler *jsc = (JSCompiler *) priv; |
993 |
JSAtomListElement *ale; |
994 |
|
995 |
ale = jsc->aleFreeList; |
996 |
if (ale) { |
997 |
jsc->aleFreeList = ALE_NEXT(ale); |
998 |
return &ale->entry; |
999 |
} |
1000 |
|
1001 |
JS_ARENA_ALLOCATE_TYPE(ale, JSAtomListElement, &jsc->context->tempPool); |
1002 |
if (!ale) { |
1003 |
js_ReportOutOfScriptQuota(jsc->context); |
1004 |
return NULL; |
1005 |
} |
1006 |
return &ale->entry; |
1007 |
} |
1008 |
|
1009 |
static void |
1010 |
js_free_temp_entry(void *priv, JSHashEntry *he, uintN flag) |
1011 |
{ |
1012 |
JSCompiler *jsc = (JSCompiler *) priv; |
1013 |
JSAtomListElement *ale = (JSAtomListElement *) he; |
1014 |
|
1015 |
ALE_SET_NEXT(ale, jsc->aleFreeList); |
1016 |
jsc->aleFreeList = ale; |
1017 |
} |
1018 |
|
1019 |
static JSHashAllocOps temp_alloc_ops = { |
1020 |
js_alloc_temp_space, js_free_temp_space, |
1021 |
js_alloc_temp_entry, js_free_temp_entry |
1022 |
}; |
1023 |
|
1024 |
JSAtomListElement * |
1025 |
JSAtomList::rawLookup(JSAtom *atom, JSHashEntry **&hep) |
1026 |
{ |
1027 |
JSAtomListElement *ale; |
1028 |
|
1029 |
if (table) { |
1030 |
hep = JS_HashTableRawLookup(table, ATOM_HASH(atom), atom); |
1031 |
ale = *hep ? (JSAtomListElement *) *hep : NULL; |
1032 |
} else { |
1033 |
JSHashEntry **alep = &list; |
1034 |
hep = NULL; |
1035 |
while ((ale = (JSAtomListElement *)*alep) != NULL) { |
1036 |
if (ALE_ATOM(ale) == atom) { |
1037 |
/* Hit, move atom's element to the front of the list. */ |
1038 |
*alep = ale->entry.next; |
1039 |
ale->entry.next = list; |
1040 |
list = &ale->entry; |
1041 |
break; |
1042 |
} |
1043 |
alep = &ale->entry.next; |
1044 |
} |
1045 |
} |
1046 |
return ale; |
1047 |
} |
1048 |
|
1049 |
#define ATOM_LIST_HASH_THRESHOLD 12 |
1050 |
|
1051 |
JSAtomListElement * |
1052 |
JSAtomList::add(JSCompiler *jsc, JSAtom *atom, AddHow how) |
1053 |
{ |
1054 |
JS_ASSERT(!set); |
1055 |
|
1056 |
JSAtomListElement *ale, *ale2, *next; |
1057 |
JSHashEntry **hep; |
1058 |
|
1059 |
ale = rawLookup(atom, hep); |
1060 |
if (!ale || how != UNIQUE) { |
1061 |
if (count < ATOM_LIST_HASH_THRESHOLD && !table) { |
1062 |
/* Few enough for linear search and no hash table yet needed. */ |
1063 |
ale = (JSAtomListElement *)js_alloc_temp_entry(jsc, atom); |
1064 |
if (!ale) |
1065 |
return NULL; |
1066 |
ALE_SET_ATOM(ale, atom); |
1067 |
|
1068 |
if (how == HOIST) { |
1069 |
ale->entry.next = NULL; |
1070 |
hep = (JSHashEntry **) &list; |
1071 |
while (*hep) |
1072 |
hep = &(*hep)->next; |
1073 |
*hep = &ale->entry; |
1074 |
} else { |
1075 |
ale->entry.next = list; |
1076 |
list = &ale->entry; |
1077 |
} |
1078 |
} else { |
1079 |
/* |
1080 |
* We should hash, or else we already are hashing, but count was |
1081 |
* reduced by JSAtomList::rawRemove below ATOM_LIST_HASH_THRESHOLD. |
1082 |
* Check whether we should create the table. |
1083 |
*/ |
1084 |
if (!table) { |
1085 |
/* No hash table yet, so hep had better be null! */ |
1086 |
JS_ASSERT(!hep); |
1087 |
table = JS_NewHashTable(count + 1, js_hash_atom_ptr, |
1088 |
JS_CompareValues, JS_CompareValues, |
1089 |
&temp_alloc_ops, jsc); |
1090 |
if (!table) |
1091 |
return NULL; |
1092 |
|
1093 |
/* |
1094 |
* Set ht->nentries explicitly, because we are moving entries |
1095 |
* from list to ht, not calling JS_HashTable(Raw|)Add. |
1096 |
*/ |
1097 |
table->nentries = count; |
1098 |
|
1099 |
/* |
1100 |
* Insert each ale on list into the new hash table. Append to |
1101 |
* the hash chain rather than inserting at the bucket head, to |
1102 |
* preserve order among entries with the same key. |
1103 |
*/ |
1104 |
for (ale2 = (JSAtomListElement *)list; ale2; ale2 = next) { |
1105 |
next = ALE_NEXT(ale2); |
1106 |
ale2->entry.keyHash = ATOM_HASH(ALE_ATOM(ale2)); |
1107 |
hep = JS_HashTableRawLookup(table, ale2->entry.keyHash, |
1108 |
ale2->entry.key); |
1109 |
while (*hep) |
1110 |
hep = &(*hep)->next; |
1111 |
*hep = &ale2->entry; |
1112 |
ale2->entry.next = NULL; |
1113 |
} |
1114 |
list = NULL; |
1115 |
|
1116 |
/* Set hep for insertion of atom's ale, immediately below. */ |
1117 |
hep = JS_HashTableRawLookup(table, ATOM_HASH(atom), atom); |
1118 |
} |
1119 |
|
1120 |
/* Finally, add an entry for atom into the hash bucket at hep. */ |
1121 |
ale = (JSAtomListElement *) |
1122 |
JS_HashTableRawAdd(table, hep, ATOM_HASH(atom), atom, NULL); |
1123 |
if (!ale) |
1124 |
return NULL; |
1125 |
|
1126 |
/* |
1127 |
* If hoisting, move ale to the end of its chain after we called |
1128 |
* JS_HashTableRawAdd, since RawAdd may have grown the table and |
1129 |
* then recomputed hep to refer to the pointer to the first entry |
1130 |
* with the given key. |
1131 |
*/ |
1132 |
if (how == HOIST && ale->entry.next) { |
1133 |
JS_ASSERT(*hep == &ale->entry); |
1134 |
*hep = ale->entry.next; |
1135 |
ale->entry.next = NULL; |
1136 |
do { |
1137 |
hep = &(*hep)->next; |
1138 |
} while (*hep); |
1139 |
*hep = &ale->entry; |
1140 |
} |
1141 |
} |
1142 |
|
1143 |
ALE_SET_INDEX(ale, count++); |
1144 |
} |
1145 |
return ale; |
1146 |
} |
1147 |
|
1148 |
void |
1149 |
JSAtomList::rawRemove(JSCompiler *jsc, JSAtomListElement *ale, JSHashEntry **hep) |
1150 |
{ |
1151 |
JS_ASSERT(!set); |
1152 |
JS_ASSERT(count != 0); |
1153 |
|
1154 |
if (table) { |
1155 |
JS_ASSERT(hep); |
1156 |
JS_HashTableRawRemove(table, hep, &ale->entry); |
1157 |
} else { |
1158 |
JS_ASSERT(!hep); |
1159 |
hep = &list; |
1160 |
while (*hep != &ale->entry) { |
1161 |
JS_ASSERT(*hep); |
1162 |
hep = &(*hep)->next; |
1163 |
} |
1164 |
*hep = ale->entry.next; |
1165 |
js_free_temp_entry(jsc, &ale->entry, HT_FREE_ENTRY); |
1166 |
} |
1167 |
|
1168 |
--count; |
1169 |
} |
1170 |
|
1171 |
JSAtomListElement * |
1172 |
JSAtomListIterator::operator ()() |
1173 |
{ |
1174 |
JSAtomListElement *ale; |
1175 |
JSHashTable *ht; |
1176 |
|
1177 |
if (index == uint32(-1)) |
1178 |
return NULL; |
1179 |
|
1180 |
ale = next; |
1181 |
if (!ale) { |
1182 |
ht = list->table; |
1183 |
if (!ht) |
1184 |
goto done; |
1185 |
do { |
1186 |
if (index == JS_BIT(JS_HASH_BITS - ht->shift)) |
1187 |
goto done; |
1188 |
next = (JSAtomListElement *) ht->buckets[index++]; |
1189 |
} while (!next); |
1190 |
ale = next; |
1191 |
} |
1192 |
|
1193 |
next = ALE_NEXT(ale); |
1194 |
return ale; |
1195 |
|
1196 |
done: |
1197 |
index = uint32(-1); |
1198 |
return NULL; |
1199 |
} |
1200 |
|
1201 |
static intN |
1202 |
js_map_atom(JSHashEntry *he, intN i, void *arg) |
1203 |
{ |
1204 |
JSAtomListElement *ale = (JSAtomListElement *)he; |
1205 |
JSAtom **vector = (JSAtom **) arg; |
1206 |
|
1207 |
vector[ALE_INDEX(ale)] = ALE_ATOM(ale); |
1208 |
return HT_ENUMERATE_NEXT; |
1209 |
} |
1210 |
|
1211 |
#ifdef DEBUG |
1212 |
static jsrefcount js_atom_map_count; |
1213 |
static jsrefcount js_atom_map_hash_table_count; |
1214 |
#endif |
1215 |
|
1216 |
void |
1217 |
js_InitAtomMap(JSContext *cx, JSAtomMap *map, JSAtomList *al) |
1218 |
{ |
1219 |
JSAtom **vector; |
1220 |
JSAtomListElement *ale; |
1221 |
uint32 count; |
1222 |
|
1223 |
/* Map length must already be initialized. */ |
1224 |
JS_ASSERT(al->count == map->length); |
1225 |
#ifdef DEBUG |
1226 |
JS_ATOMIC_INCREMENT(&js_atom_map_count); |
1227 |
#endif |
1228 |
ale = (JSAtomListElement *)al->list; |
1229 |
if (!ale && !al->table) { |
1230 |
JS_ASSERT(!map->vector); |
1231 |
return; |
1232 |
} |
1233 |
|
1234 |
count = al->count; |
1235 |
vector = map->vector; |
1236 |
if (al->table) { |
1237 |
#ifdef DEBUG |
1238 |
JS_ATOMIC_INCREMENT(&js_atom_map_hash_table_count); |
1239 |
#endif |
1240 |
JS_HashTableEnumerateEntries(al->table, js_map_atom, vector); |
1241 |
} else { |
1242 |
do { |
1243 |
vector[ALE_INDEX(ale)] = ALE_ATOM(ale); |
1244 |
} while ((ale = ALE_NEXT(ale)) != NULL); |
1245 |
} |
1246 |
al->clear(); |
1247 |
} |