js/src/jsatom.cpp

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