Back to index

lightning-sunbird  0.9+nobinonly
jsatom.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is Mozilla Communicator client code, released
00017  * March 31, 1998.
00018  *
00019  * The Initial Developer of the Original Code is
00020  * Netscape Communications Corporation.
00021  * Portions created by the Initial Developer are Copyright (C) 1998
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either of the GNU General Public License Version 2 or later (the "GPL"),
00028  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 /*
00041  * JS atom table.
00042  */
00043 #include "jsstddef.h"
00044 #include <stdlib.h>
00045 #include <string.h>
00046 #include "jstypes.h"
00047 #include "jsutil.h" /* Added by JSIFY */
00048 #include "jshash.h" /* Added by JSIFY */
00049 #include "jsprf.h"
00050 #include "jsapi.h"
00051 #include "jsatom.h"
00052 #include "jscntxt.h"
00053 #include "jsconfig.h"
00054 #include "jsgc.h"
00055 #include "jslock.h"
00056 #include "jsnum.h"
00057 #include "jsscan.h"
00058 #include "jsstr.h"
00059 
00060 JS_FRIEND_API(const char *)
00061 js_AtomToPrintableString(JSContext *cx, JSAtom *atom)
00062 {
00063     return js_ValueToPrintableString(cx, ATOM_KEY(atom));
00064 }
00065 
00066 /*
00067  * Keep this in sync with jspubtd.h -- an assertion below will insist that
00068  * its length match the JSType enum's JSTYPE_LIMIT limit value.
00069  */
00070 const char *js_type_strs[] = {
00071     "undefined",
00072     js_object_str,
00073     "function",
00074     "string",
00075     "number",
00076     "boolean",
00077     "null",
00078     "xml",
00079 };
00080 
00081 JS_STATIC_ASSERT(JSTYPE_LIMIT ==
00082                  sizeof js_type_strs / sizeof js_type_strs[0]);
00083 
00084 const char *js_boolean_strs[] = {
00085     js_false_str,
00086     js_true_str
00087 };
00088 
00089 #define JS_PROTO(name,code,init) const char js_##name##_str[] = #name;
00090 #include "jsproto.tbl"
00091 #undef JS_PROTO
00092 
00093 const char *js_proto_strs[JSProto_LIMIT] = {
00094 #define JS_PROTO(name,code,init) js_##name##_str,
00095 #include "jsproto.tbl"
00096 #undef JS_PROTO
00097 };
00098 
00099 const char js_anonymous_str[]       = "anonymous";
00100 const char js_arguments_str[]       = "arguments";
00101 const char js_arity_str[]           = "arity";
00102 const char js_callee_str[]          = "callee";
00103 const char js_caller_str[]          = "caller";
00104 const char js_class_prototype_str[] = "prototype";
00105 const char js_constructor_str[]     = "constructor";
00106 const char js_count_str[]           = "__count__";
00107 const char js_each_str[]            = "each";
00108 const char js_eval_str[]            = "eval";
00109 const char js_fileName_str[]        = "fileName";
00110 const char js_get_str[]             = "get";
00111 const char js_getter_str[]          = "getter";
00112 const char js_index_str[]           = "index";
00113 const char js_input_str[]           = "input";
00114 const char js_iterator_str[]        = "__iterator__";
00115 const char js_length_str[]          = "length";
00116 const char js_lineNumber_str[]      = "lineNumber";
00117 const char js_message_str[]         = "message";
00118 const char js_name_str[]            = "name";
00119 const char js_next_str[]            = "next";
00120 const char js_noSuchMethod_str[]    = "__noSuchMethod__";
00121 const char js_object_str[]          = "object";
00122 const char js_parent_str[]          = "__parent__";
00123 const char js_proto_str[]           = "__proto__";
00124 const char js_setter_str[]          = "setter";
00125 const char js_set_str[]             = "set";
00126 const char js_stack_str[]           = "stack";
00127 const char js_toSource_str[]        = "toSource";
00128 const char js_toString_str[]        = "toString";
00129 const char js_toLocaleString_str[]  = "toLocaleString";
00130 const char js_valueOf_str[]         = "valueOf";
00131 
00132 #if JS_HAS_XML_SUPPORT
00133 const char js_etago_str[]           = "</";
00134 const char js_namespace_str[]       = "namespace";
00135 const char js_ptagc_str[]           = "/>";
00136 const char js_qualifier_str[]       = "::";
00137 const char js_space_str[]           = " ";
00138 const char js_stago_str[]           = "<";
00139 const char js_star_str[]            = "*";
00140 const char js_starQualifier_str[]   = "*::";
00141 const char js_tagc_str[]            = ">";
00142 const char js_xml_str[]             = "xml";
00143 #endif
00144 
00145 #if JS_HAS_GENERATORS
00146 const char js_close_str[]           = "close";
00147 const char js_send_str[]            = "send";
00148 #endif
00149 
00150 #ifdef NARCISSUS
00151 const char js_call_str[]             = "__call__";
00152 const char js_construct_str[]        = "__construct__";
00153 const char js_hasInstance_str[]      = "__hasInstance__";
00154 const char js_ExecutionContext_str[] = "ExecutionContext";
00155 const char js_current_str[]          = "current";
00156 #endif
00157 
00158 #define HASH_OBJECT(o)  (JS_PTR_TO_UINT32(o) >> JSVAL_TAGBITS)
00159 #define HASH_INT(i)     ((JSHashNumber)(i))
00160 #define HASH_DOUBLE(dp) ((JSDOUBLE_HI32(*dp) ^ JSDOUBLE_LO32(*dp)))
00161 #define HASH_BOOLEAN(b) ((JSHashNumber)(b))
00162 
00163 JS_STATIC_DLL_CALLBACK(JSHashNumber)
00164 js_hash_atom_key(const void *key)
00165 {
00166     jsval v;
00167     jsdouble *dp;
00168 
00169     /* Order JSVAL_IS_* tests by likelihood of success. */
00170     v = (jsval)key;
00171     if (JSVAL_IS_STRING(v))
00172         return js_HashString(JSVAL_TO_STRING(v));
00173     if (JSVAL_IS_INT(v))
00174         return HASH_INT(JSVAL_TO_INT(v));
00175     if (JSVAL_IS_DOUBLE(v)) {
00176         dp = JSVAL_TO_DOUBLE(v);
00177         return HASH_DOUBLE(dp);
00178     }
00179     if (JSVAL_IS_OBJECT(v))
00180         return HASH_OBJECT(JSVAL_TO_OBJECT(v));
00181     if (JSVAL_IS_BOOLEAN(v))
00182         return HASH_BOOLEAN(JSVAL_TO_BOOLEAN(v));
00183     return (JSHashNumber)v;
00184 }
00185 
00186 JS_STATIC_DLL_CALLBACK(intN)
00187 js_compare_atom_keys(const void *k1, const void *k2)
00188 {
00189     jsval v1, v2;
00190 
00191     v1 = (jsval)k1, v2 = (jsval)k2;
00192     if (JSVAL_IS_STRING(v1) && JSVAL_IS_STRING(v2))
00193         return js_EqualStrings(JSVAL_TO_STRING(v1), JSVAL_TO_STRING(v2));
00194     if (JSVAL_IS_DOUBLE(v1) && JSVAL_IS_DOUBLE(v2)) {
00195         double d1 = *JSVAL_TO_DOUBLE(v1);
00196         double d2 = *JSVAL_TO_DOUBLE(v2);
00197         if (JSDOUBLE_IS_NaN(d1))
00198             return JSDOUBLE_IS_NaN(d2);
00199 #if defined(XP_WIN)
00200         /* XXX MSVC miscompiles such that (NaN == 0) */
00201         if (JSDOUBLE_IS_NaN(d2))
00202             return JS_FALSE;
00203 #endif
00204         return d1 == d2;
00205     }
00206     return v1 == v2;
00207 }
00208 
00209 JS_STATIC_DLL_CALLBACK(int)
00210 js_compare_stub(const void *v1, const void *v2)
00211 {
00212     return 1;
00213 }
00214 
00215 /* These next two are exported to jsscript.c and used similarly there. */
00216 void * JS_DLL_CALLBACK
00217 js_alloc_table_space(void *priv, size_t size)
00218 {
00219     return malloc(size);
00220 }
00221 
00222 void JS_DLL_CALLBACK
00223 js_free_table_space(void *priv, void *item)
00224 {
00225     free(item);
00226 }
00227 
00228 JS_STATIC_DLL_CALLBACK(JSHashEntry *)
00229 js_alloc_atom(void *priv, const void *key)
00230 {
00231     JSAtomState *state = (JSAtomState *) priv;
00232     JSAtom *atom;
00233 
00234     atom = (JSAtom *) malloc(sizeof(JSAtom));
00235     if (!atom)
00236         return NULL;
00237 #ifdef JS_THREADSAFE
00238     state->tablegen++;
00239 #endif
00240     atom->entry.key = key;
00241     atom->entry.value = NULL;
00242     atom->flags = 0;
00243     atom->number = state->number++;
00244     return &atom->entry;
00245 }
00246 
00247 JS_STATIC_DLL_CALLBACK(void)
00248 js_free_atom(void *priv, JSHashEntry *he, uintN flag)
00249 {
00250     if (flag != HT_FREE_ENTRY)
00251         return;
00252 #ifdef JS_THREADSAFE
00253     ((JSAtomState *)priv)->tablegen++;
00254 #endif
00255     free(he);
00256 }
00257 
00258 static JSHashAllocOps atom_alloc_ops = {
00259     js_alloc_table_space,   js_free_table_space,
00260     js_alloc_atom,          js_free_atom
00261 };
00262 
00263 #define JS_ATOM_HASH_SIZE   1024
00264 
00265 JSBool
00266 js_InitAtomState(JSContext *cx, JSAtomState *state)
00267 {
00268     state->table = JS_NewHashTable(JS_ATOM_HASH_SIZE, js_hash_atom_key,
00269                                    js_compare_atom_keys, js_compare_stub,
00270                                    &atom_alloc_ops, state);
00271     if (!state->table) {
00272         JS_ReportOutOfMemory(cx);
00273         return JS_FALSE;
00274     }
00275 
00276     state->runtime = cx->runtime;
00277 #ifdef JS_THREADSAFE
00278     js_InitLock(&state->lock);
00279     state->tablegen = 0;
00280 #endif
00281 
00282     if (!js_InitPinnedAtoms(cx, state)) {
00283         js_FreeAtomState(cx, state);
00284         return JS_FALSE;
00285     }
00286     return JS_TRUE;
00287 }
00288 
00289 JSBool
00290 js_InitPinnedAtoms(JSContext *cx, JSAtomState *state)
00291 {
00292     uintN i;
00293 
00294 #define FROB(lval,str)                                                        \
00295     JS_BEGIN_MACRO                                                            \
00296         if (!(state->lval = js_Atomize(cx, str, strlen(str), ATOM_PINNED)))   \
00297             return JS_FALSE;                                                  \
00298     JS_END_MACRO
00299 
00300     for (i = 0; i < JSTYPE_LIMIT; i++)
00301         FROB(typeAtoms[i],        js_type_strs[i]);
00302 
00303     for (i = 0; i < JSProto_LIMIT; i++)
00304         FROB(classAtoms[i],       js_proto_strs[i]);
00305 
00306     FROB(booleanAtoms[0],         js_false_str);
00307     FROB(booleanAtoms[1],         js_true_str);
00308     FROB(nullAtom,                js_null_str);
00309 
00310     FROB(anonymousAtom,           js_anonymous_str);
00311     FROB(argumentsAtom,           js_arguments_str);
00312     FROB(arityAtom,               js_arity_str);
00313     FROB(calleeAtom,              js_callee_str);
00314     FROB(callerAtom,              js_caller_str);
00315     FROB(classPrototypeAtom,      js_class_prototype_str);
00316     FROB(constructorAtom,         js_constructor_str);
00317     FROB(countAtom,               js_count_str);
00318     FROB(eachAtom,                js_each_str);
00319     FROB(evalAtom,                js_eval_str);
00320     FROB(fileNameAtom,            js_fileName_str);
00321     FROB(getAtom,                 js_get_str);
00322     FROB(getterAtom,              js_getter_str);
00323     FROB(indexAtom,               js_index_str);
00324     FROB(inputAtom,               js_input_str);
00325     FROB(iteratorAtom,            js_iterator_str);
00326     FROB(lengthAtom,              js_length_str);
00327     FROB(lineNumberAtom,          js_lineNumber_str);
00328     FROB(messageAtom,             js_message_str);
00329     FROB(nameAtom,                js_name_str);
00330     FROB(nextAtom,                js_next_str);
00331     FROB(noSuchMethodAtom,        js_noSuchMethod_str);
00332     FROB(parentAtom,              js_parent_str);
00333     FROB(protoAtom,               js_proto_str);
00334     FROB(setAtom,                 js_set_str);
00335     FROB(setterAtom,              js_setter_str);
00336     FROB(stackAtom,               js_stack_str);
00337     FROB(toSourceAtom,            js_toSource_str);
00338     FROB(toStringAtom,            js_toString_str);
00339     FROB(toLocaleStringAtom,      js_toLocaleString_str);
00340     FROB(valueOfAtom,             js_valueOf_str);
00341 
00342 #if JS_HAS_XML_SUPPORT
00343     FROB(etagoAtom,               js_etago_str);
00344     FROB(namespaceAtom,           js_namespace_str);
00345     FROB(ptagcAtom,               js_ptagc_str);
00346     FROB(qualifierAtom,           js_qualifier_str);
00347     FROB(spaceAtom,               js_space_str);
00348     FROB(stagoAtom,               js_stago_str);
00349     FROB(starAtom,                js_star_str);
00350     FROB(starQualifierAtom,       js_starQualifier_str);
00351     FROB(tagcAtom,                js_tagc_str);
00352     FROB(xmlAtom,                 js_xml_str);
00353 #endif
00354 
00355 #if JS_HAS_GENERATORS
00356     FROB(closeAtom,               js_close_str);
00357 #endif
00358 
00359 #ifdef NARCISSUS
00360     FROB(callAtom,                js_call_str);
00361     FROB(constructAtom,           js_construct_str);
00362     FROB(hasInstanceAtom,         js_hasInstance_str);
00363     FROB(ExecutionContextAtom,    js_ExecutionContext_str);
00364     FROB(currentAtom,             js_current_str);
00365 #endif
00366 
00367 #undef FROB
00368 
00369     memset(&state->lazy, 0, sizeof state->lazy);
00370     return JS_TRUE;
00371 }
00372 
00373 /* NB: cx unused; js_FinishAtomState calls us with null cx. */
00374 void
00375 js_FreeAtomState(JSContext *cx, JSAtomState *state)
00376 {
00377     if (state->table)
00378         JS_HashTableDestroy(state->table);
00379 #ifdef JS_THREADSAFE
00380     js_FinishLock(&state->lock);
00381 #endif
00382     memset(state, 0, sizeof *state);
00383 }
00384 
00385 typedef struct UninternArgs {
00386     JSRuntime   *rt;
00387     jsatomid    leaks;
00388 } UninternArgs;
00389 
00390 JS_STATIC_DLL_CALLBACK(intN)
00391 js_atom_uninterner(JSHashEntry *he, intN i, void *arg)
00392 {
00393     JSAtom *atom;
00394     UninternArgs *args;
00395 
00396     atom = (JSAtom *)he;
00397     args = (UninternArgs *)arg;
00398     if (ATOM_IS_STRING(atom))
00399         js_FinalizeStringRT(args->rt, ATOM_TO_STRING(atom));
00400     else if (ATOM_IS_OBJECT(atom))
00401         args->leaks++;
00402     return HT_ENUMERATE_NEXT;
00403 }
00404 
00405 void
00406 js_FinishAtomState(JSAtomState *state)
00407 {
00408     UninternArgs args;
00409 
00410     if (!state->table)
00411         return;
00412     args.rt = state->runtime;
00413     args.leaks = 0;
00414     JS_HashTableEnumerateEntries(state->table, js_atom_uninterner, &args);
00415 #ifdef DEBUG
00416     if (args.leaks != 0) {
00417         fprintf(stderr,
00418 "JS engine warning: %lu atoms remain after destroying the JSRuntime.\n"
00419 "                   These atoms may point to freed memory. Things reachable\n"
00420 "                   through them have not been finalized.\n",
00421                 (unsigned long) args.leaks);
00422     }
00423 #endif
00424     js_FreeAtomState(NULL, state);
00425 }
00426 
00427 typedef struct MarkArgs {
00428     JSBool          keepAtoms;
00429     JSGCThingMarker mark;
00430     void            *data;
00431 } MarkArgs;
00432 
00433 JS_STATIC_DLL_CALLBACK(intN)
00434 js_atom_marker(JSHashEntry *he, intN i, void *arg)
00435 {
00436     JSAtom *atom;
00437     MarkArgs *args;
00438     jsval key;
00439 
00440     atom = (JSAtom *)he;
00441     args = (MarkArgs *)arg;
00442     if ((atom->flags & (ATOM_PINNED | ATOM_INTERNED)) || args->keepAtoms) {
00443         atom->flags |= ATOM_MARK;
00444         key = ATOM_KEY(atom);
00445         if (JSVAL_IS_GCTHING(key))
00446             args->mark(JSVAL_TO_GCTHING(key), args->data);
00447     }
00448     return HT_ENUMERATE_NEXT;
00449 }
00450 
00451 void
00452 js_MarkAtomState(JSAtomState *state, JSBool keepAtoms, JSGCThingMarker mark,
00453                  void *data)
00454 {
00455     MarkArgs args;
00456 
00457     if (!state->table)
00458         return;
00459     args.keepAtoms = keepAtoms;
00460     args.mark = mark;
00461     args.data = data;
00462     JS_HashTableEnumerateEntries(state->table, js_atom_marker, &args);
00463 }
00464 
00465 JS_STATIC_DLL_CALLBACK(intN)
00466 js_atom_sweeper(JSHashEntry *he, intN i, void *arg)
00467 {
00468     JSAtom *atom;
00469     JSAtomState *state;
00470 
00471     atom = (JSAtom *)he;
00472     if (atom->flags & ATOM_MARK) {
00473         atom->flags &= ~ATOM_MARK;
00474         state = (JSAtomState *)arg;
00475         state->liveAtoms++;
00476         return HT_ENUMERATE_NEXT;
00477     }
00478     JS_ASSERT((atom->flags & (ATOM_PINNED | ATOM_INTERNED)) == 0);
00479     atom->entry.key = atom->entry.value = NULL;
00480     atom->flags = 0;
00481     return HT_ENUMERATE_REMOVE;
00482 }
00483 
00484 void
00485 js_SweepAtomState(JSAtomState *state)
00486 {
00487     state->liveAtoms = 0;
00488     if (state->table)
00489         JS_HashTableEnumerateEntries(state->table, js_atom_sweeper, state);
00490 }
00491 
00492 JS_STATIC_DLL_CALLBACK(intN)
00493 js_atom_unpinner(JSHashEntry *he, intN i, void *arg)
00494 {
00495     JSAtom *atom;
00496 
00497     atom = (JSAtom *)he;
00498     atom->flags &= ~ATOM_PINNED;
00499     return HT_ENUMERATE_NEXT;
00500 }
00501 
00502 void
00503 js_UnpinPinnedAtoms(JSAtomState *state)
00504 {
00505     if (state->table)
00506         JS_HashTableEnumerateEntries(state->table, js_atom_unpinner, NULL);
00507 }
00508 
00509 static JSAtom *
00510 js_AtomizeHashedKey(JSContext *cx, jsval key, JSHashNumber keyHash, uintN flags)
00511 {
00512     JSAtomState *state;
00513     JSHashTable *table;
00514     JSHashEntry *he, **hep;
00515     JSAtom *atom;
00516 
00517     state = &cx->runtime->atomState;
00518     JS_LOCK(&state->lock, cx);
00519     table = state->table;
00520     hep = JS_HashTableRawLookup(table, keyHash, (void *)key);
00521     if ((he = *hep) == NULL) {
00522         he = JS_HashTableRawAdd(table, hep, keyHash, (void *)key, NULL);
00523         if (!he) {
00524             JS_ReportOutOfMemory(cx);
00525             atom = NULL;
00526             goto out;
00527         }
00528     }
00529 
00530     atom = (JSAtom *)he;
00531     atom->flags |= flags;
00532     cx->weakRoots.lastAtom = atom;
00533 out:
00534     JS_UNLOCK(&state->lock,cx);
00535     return atom;
00536 }
00537 
00538 JSAtom *
00539 js_AtomizeObject(JSContext *cx, JSObject *obj, uintN flags)
00540 {
00541     jsval key;
00542     JSHashNumber keyHash;
00543 
00544     /* XXX must be set in the following order or MSVC1.52 will crash */
00545     keyHash = HASH_OBJECT(obj);
00546     key = OBJECT_TO_JSVAL(obj);
00547     return js_AtomizeHashedKey(cx, key, keyHash, flags);
00548 }
00549 
00550 JSAtom *
00551 js_AtomizeBoolean(JSContext *cx, JSBool b, uintN flags)
00552 {
00553     jsval key;
00554     JSHashNumber keyHash;
00555 
00556     key = BOOLEAN_TO_JSVAL(b);
00557     keyHash = HASH_BOOLEAN(b);
00558     return js_AtomizeHashedKey(cx, key, keyHash, flags);
00559 }
00560 
00561 JSAtom *
00562 js_AtomizeInt(JSContext *cx, jsint i, uintN flags)
00563 {
00564     jsval key;
00565     JSHashNumber keyHash;
00566 
00567     key = INT_TO_JSVAL(i);
00568     keyHash = HASH_INT(i);
00569     return js_AtomizeHashedKey(cx, key, keyHash, flags);
00570 }
00571 
00572 /* Worst-case alignment grain and aligning macro for 2x-sized buffer. */
00573 #define ALIGNMENT(t)    JS_MAX(JSVAL_ALIGN, sizeof(t))
00574 #define ALIGN(b,t)      ((t*) &(b)[ALIGNMENT(t) - (jsuword)(b) % ALIGNMENT(t)])
00575 
00576 JSAtom *
00577 js_AtomizeDouble(JSContext *cx, jsdouble d, uintN flags)
00578 {
00579     jsdouble *dp;
00580     JSHashNumber keyHash;
00581     jsval key;
00582     JSAtomState *state;
00583     JSHashTable *table;
00584     JSHashEntry *he, **hep;
00585     JSAtom *atom;
00586     char buf[2 * ALIGNMENT(double)];
00587 
00588     dp = ALIGN(buf, double);
00589     *dp = d;
00590     keyHash = HASH_DOUBLE(dp);
00591     key = DOUBLE_TO_JSVAL(dp);
00592     state = &cx->runtime->atomState;
00593     JS_LOCK(&state->lock, cx);
00594     table = state->table;
00595     hep = JS_HashTableRawLookup(table, keyHash, (void *)key);
00596     if ((he = *hep) == NULL) {
00597 #ifdef JS_THREADSAFE
00598         uint32 gen = state->tablegen;
00599 #endif
00600         JS_UNLOCK(&state->lock,cx);
00601         if (!js_NewDoubleValue(cx, d, &key))
00602             return NULL;
00603         JS_LOCK(&state->lock, cx);
00604 #ifdef JS_THREADSAFE
00605         if (state->tablegen != gen) {
00606             hep = JS_HashTableRawLookup(table, keyHash, (void *)key);
00607             if ((he = *hep) != NULL) {
00608                 atom = (JSAtom *)he;
00609                 goto out;
00610             }
00611         }
00612 #endif
00613         he = JS_HashTableRawAdd(table, hep, keyHash, (void *)key, NULL);
00614         if (!he) {
00615             JS_ReportOutOfMemory(cx);
00616             atom = NULL;
00617             goto out;
00618         }
00619     }
00620 
00621     atom = (JSAtom *)he;
00622     atom->flags |= flags;
00623     cx->weakRoots.lastAtom = atom;
00624 out:
00625     JS_UNLOCK(&state->lock,cx);
00626     return atom;
00627 }
00628 
00629 /*
00630  * To put an atom into the hidden subspace. XOR its keyHash with this value,
00631  * which is (sqrt(2)-1) in 32-bit fixed point.
00632  */
00633 #define HIDDEN_ATOM_SUBSPACE_KEYHASH    0x6A09E667
00634 
00635 JSAtom *
00636 js_AtomizeString(JSContext *cx, JSString *str, uintN flags)
00637 {
00638     JSHashNumber keyHash;
00639     jsval key;
00640     JSAtomState *state;
00641     JSHashTable *table;
00642     JSHashEntry *he, **hep;
00643     JSAtom *atom;
00644 
00645     keyHash = js_HashString(str);
00646     if (flags & ATOM_HIDDEN)
00647         keyHash ^= HIDDEN_ATOM_SUBSPACE_KEYHASH;
00648     key = STRING_TO_JSVAL(str);
00649     state = &cx->runtime->atomState;
00650     JS_LOCK(&state->lock, cx);
00651     table = state->table;
00652     hep = JS_HashTableRawLookup(table, keyHash, (void *)key);
00653     if ((he = *hep) == NULL) {
00654 #ifdef JS_THREADSAFE
00655         uint32 gen = state->tablegen;
00656         JS_UNLOCK(&state->lock, cx);
00657 #endif
00658 
00659         if (flags & ATOM_TMPSTR) {
00660             str = (flags & ATOM_NOCOPY)
00661                   ? js_NewString(cx, str->chars, str->length, 0)
00662                   : js_NewStringCopyN(cx, str->chars, str->length, 0);
00663             if (!str)
00664                 return NULL;
00665             key = STRING_TO_JSVAL(str);
00666         } else {
00667             if (!JS_MakeStringImmutable(cx, str))
00668                 return NULL;
00669         }
00670 
00671 #ifdef JS_THREADSAFE
00672         JS_LOCK(&state->lock, cx);
00673         if (state->tablegen != gen) {
00674             hep = JS_HashTableRawLookup(table, keyHash, (void *)key);
00675             if ((he = *hep) != NULL) {
00676                 atom = (JSAtom *)he;
00677                 if (flags & ATOM_NOCOPY)
00678                     str->chars = NULL;
00679                 goto out;
00680             }
00681         }
00682 #endif
00683 
00684         he = JS_HashTableRawAdd(table, hep, keyHash, (void *)key, NULL);
00685         if (!he) {
00686             JS_ReportOutOfMemory(cx);
00687             atom = NULL;
00688             goto out;
00689         }
00690     }
00691 
00692     atom = (JSAtom *)he;
00693     atom->flags |= flags & (ATOM_PINNED | ATOM_INTERNED | ATOM_HIDDEN);
00694     cx->weakRoots.lastAtom = atom;
00695 out:
00696     JS_UNLOCK(&state->lock,cx);
00697     return atom;
00698 }
00699 
00700 JS_FRIEND_API(JSAtom *)
00701 js_Atomize(JSContext *cx, const char *bytes, size_t length, uintN flags)
00702 {
00703     jschar *chars;
00704     JSString *str;
00705     JSAtom *atom;
00706     char buf[2 * ALIGNMENT(JSString)];
00707 
00708     /*
00709      * Avoiding the malloc in js_InflateString on shorter strings saves us
00710      * over 20,000 malloc calls on mozilla browser startup. This compares to
00711      * only 131 calls where the string is longer than a 31 char (net) buffer.
00712      * The vast majority of atomized strings are already in the hashtable. So
00713      * js_AtomizeString rarely has to copy the temp string we make.
00714      */
00715 #define ATOMIZE_BUF_MAX 32
00716     jschar inflated[ATOMIZE_BUF_MAX];
00717     size_t inflatedLength = ATOMIZE_BUF_MAX - 1;
00718 
00719     if (length < ATOMIZE_BUF_MAX) {
00720         js_InflateStringToBuffer(cx, bytes, length, inflated, &inflatedLength);
00721         inflated[inflatedLength] = 0;
00722         chars = inflated;
00723     } else {
00724         inflatedLength = length;
00725         chars = js_InflateString(cx, bytes, &inflatedLength);
00726         if (!chars)
00727             return NULL;
00728         flags |= ATOM_NOCOPY;
00729     }
00730 
00731     str = ALIGN(buf, JSString);
00732 
00733     str->chars = chars;
00734     str->length = inflatedLength;
00735     atom = js_AtomizeString(cx, str, ATOM_TMPSTR | flags);
00736     if (chars != inflated && (!atom || ATOM_TO_STRING(atom)->chars != chars))
00737         JS_free(cx, chars);
00738     return atom;
00739 }
00740 
00741 JS_FRIEND_API(JSAtom *)
00742 js_AtomizeChars(JSContext *cx, const jschar *chars, size_t length, uintN flags)
00743 {
00744     JSString *str;
00745     char buf[2 * ALIGNMENT(JSString)];
00746 
00747     str = ALIGN(buf, JSString);
00748     str->chars = (jschar *)chars;
00749     str->length = length;
00750     return js_AtomizeString(cx, str, ATOM_TMPSTR | flags);
00751 }
00752 
00753 JSAtom *
00754 js_GetExistingStringAtom(JSContext *cx, const jschar *chars, size_t length)
00755 {
00756     JSString *str;
00757     char buf[2 * ALIGNMENT(JSString)];
00758     JSHashNumber keyHash;
00759     jsval key;
00760     JSAtomState *state;
00761     JSHashTable *table;
00762     JSHashEntry **hep;
00763 
00764     str = ALIGN(buf, JSString);
00765     str->chars = (jschar *)chars;
00766     str->length = length;
00767     keyHash = js_HashString(str);
00768     key = STRING_TO_JSVAL(str);
00769     state = &cx->runtime->atomState;
00770     JS_LOCK(&state->lock, cx);
00771     table = state->table;
00772     hep = JS_HashTableRawLookup(table, keyHash, (void *)key);
00773     JS_UNLOCK(&state->lock, cx);
00774     return (hep) ? (JSAtom *)*hep : NULL;
00775 }
00776 
00777 JSAtom *
00778 js_AtomizeValue(JSContext *cx, jsval value, uintN flags)
00779 {
00780     if (JSVAL_IS_STRING(value))
00781         return js_AtomizeString(cx, JSVAL_TO_STRING(value), flags);
00782     if (JSVAL_IS_INT(value))
00783         return js_AtomizeInt(cx, JSVAL_TO_INT(value), flags);
00784     if (JSVAL_IS_DOUBLE(value))
00785         return js_AtomizeDouble(cx, *JSVAL_TO_DOUBLE(value), flags);
00786     if (JSVAL_IS_OBJECT(value))
00787         return js_AtomizeObject(cx, JSVAL_TO_OBJECT(value), flags);
00788     if (JSVAL_IS_BOOLEAN(value))
00789         return js_AtomizeBoolean(cx, JSVAL_TO_BOOLEAN(value), flags);
00790     return js_AtomizeHashedKey(cx, value, (JSHashNumber)value, flags);
00791 }
00792 
00793 JSAtom *
00794 js_ValueToStringAtom(JSContext *cx, jsval v)
00795 {
00796     JSString *str;
00797 
00798     str = js_ValueToString(cx, v);
00799     if (!str)
00800         return NULL;
00801     return js_AtomizeString(cx, str, 0);
00802 }
00803 
00804 JS_STATIC_DLL_CALLBACK(JSHashNumber)
00805 js_hash_atom_ptr(const void *key)
00806 {
00807     const JSAtom *atom = key;
00808     return atom->number;
00809 }
00810 
00811 JS_STATIC_DLL_CALLBACK(void *)
00812 js_alloc_temp_space(void *priv, size_t size)
00813 {
00814     JSContext *cx = priv;
00815     void *space;
00816 
00817     JS_ARENA_ALLOCATE(space, &cx->tempPool, size);
00818     if (!space)
00819         JS_ReportOutOfMemory(cx);
00820     return space;
00821 }
00822 
00823 JS_STATIC_DLL_CALLBACK(void)
00824 js_free_temp_space(void *priv, void *item)
00825 {
00826 }
00827 
00828 JS_STATIC_DLL_CALLBACK(JSHashEntry *)
00829 js_alloc_temp_entry(void *priv, const void *key)
00830 {
00831     JSContext *cx = priv;
00832     JSAtomListElement *ale;
00833 
00834     JS_ARENA_ALLOCATE_TYPE(ale, JSAtomListElement, &cx->tempPool);
00835     if (!ale) {
00836         JS_ReportOutOfMemory(cx);
00837         return NULL;
00838     }
00839     return &ale->entry;
00840 }
00841 
00842 JS_STATIC_DLL_CALLBACK(void)
00843 js_free_temp_entry(void *priv, JSHashEntry *he, uintN flag)
00844 {
00845 }
00846 
00847 static JSHashAllocOps temp_alloc_ops = {
00848     js_alloc_temp_space,    js_free_temp_space,
00849     js_alloc_temp_entry,    js_free_temp_entry
00850 };
00851 
00852 JSAtomListElement *
00853 js_IndexAtom(JSContext *cx, JSAtom *atom, JSAtomList *al)
00854 {
00855     JSAtomListElement *ale, *ale2, *next;
00856     JSHashEntry **hep;
00857 
00858     ATOM_LIST_LOOKUP(ale, hep, al, atom);
00859     if (!ale) {
00860         if (al->count < 10) {
00861             /* Few enough for linear search, no hash table needed. */
00862             JS_ASSERT(!al->table);
00863             ale = (JSAtomListElement *)js_alloc_temp_entry(cx, atom);
00864             if (!ale)
00865                 return NULL;
00866             ALE_SET_ATOM(ale, atom);
00867             ALE_SET_NEXT(ale, al->list);
00868             al->list = ale;
00869         } else {
00870             /* We want to hash.  Have we already made a hash table? */
00871             if (!al->table) {
00872                 /* No hash table yet, so hep had better be null! */
00873                 JS_ASSERT(!hep);
00874                 al->table = JS_NewHashTable(al->count + 1, js_hash_atom_ptr,
00875                                             JS_CompareValues, JS_CompareValues,
00876                                             &temp_alloc_ops, cx);
00877                 if (!al->table)
00878                     return NULL;
00879 
00880                 /*
00881                  * Set ht->nentries explicitly, because we are moving entries
00882                  * from al to ht, not calling JS_HashTable(Raw|)Add.
00883                  */
00884                 al->table->nentries = al->count;
00885 
00886                 /* Insert each ale on al->list into the new hash table. */
00887                 for (ale2 = al->list; ale2; ale2 = next) {
00888                     next = ALE_NEXT(ale2);
00889                     ale2->entry.keyHash = ALE_ATOM(ale2)->number;
00890                     hep = JS_HashTableRawLookup(al->table, ale2->entry.keyHash,
00891                                                 ale2->entry.key);
00892                     ALE_SET_NEXT(ale2, *hep);
00893                     *hep = &ale2->entry;
00894                 }
00895                 al->list = NULL;
00896 
00897                 /* Set hep for insertion of atom's ale, immediately below. */
00898                 hep = JS_HashTableRawLookup(al->table, atom->number, atom);
00899             }
00900 
00901             /* Finally, add an entry for atom into the hash bucket at hep. */
00902             ale = (JSAtomListElement *)
00903                   JS_HashTableRawAdd(al->table, hep, atom->number, atom, NULL);
00904             if (!ale)
00905                 return NULL;
00906         }
00907 
00908         ALE_SET_INDEX(ale, al->count++);
00909     }
00910     return ale;
00911 }
00912 
00913 JS_FRIEND_API(JSAtom *)
00914 js_GetAtom(JSContext *cx, JSAtomMap *map, jsatomid i)
00915 {
00916     JSAtom *atom;
00917     static JSAtom dummy;
00918 
00919     JS_ASSERT(map->vector && i < map->length);
00920     if (!map->vector || i >= map->length) {
00921         char numBuf[12];
00922         JS_snprintf(numBuf, sizeof numBuf, "%lu", (unsigned long)i);
00923         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
00924                              JSMSG_BAD_ATOMIC_NUMBER, numBuf);
00925         return &dummy;
00926     }
00927     atom = map->vector[i];
00928     JS_ASSERT(atom);
00929     return atom;
00930 }
00931 
00932 JS_STATIC_DLL_CALLBACK(intN)
00933 js_map_atom(JSHashEntry *he, intN i, void *arg)
00934 {
00935     JSAtomListElement *ale = (JSAtomListElement *)he;
00936     JSAtom **vector = arg;
00937 
00938     vector[ALE_INDEX(ale)] = ALE_ATOM(ale);
00939     return HT_ENUMERATE_NEXT;
00940 }
00941 
00942 #ifdef DEBUG
00943 static jsrefcount js_atom_map_count;
00944 static jsrefcount js_atom_map_hash_table_count;
00945 #endif
00946 
00947 JS_FRIEND_API(JSBool)
00948 js_InitAtomMap(JSContext *cx, JSAtomMap *map, JSAtomList *al)
00949 {
00950     JSAtom **vector;
00951     JSAtomListElement *ale;
00952     uint32 count;
00953 
00954 #ifdef DEBUG
00955     JS_ATOMIC_INCREMENT(&js_atom_map_count);
00956 #endif
00957     ale = al->list;
00958     if (!ale && !al->table) {
00959         map->vector = NULL;
00960         map->length = 0;
00961         return JS_TRUE;
00962     }
00963 
00964     count = al->count;
00965     if (count >= ATOM_INDEX_LIMIT) {
00966         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
00967                              JSMSG_TOO_MANY_LITERALS);
00968         return JS_FALSE;
00969     }
00970     vector = (JSAtom **) JS_malloc(cx, (size_t) count * sizeof *vector);
00971     if (!vector)
00972         return JS_FALSE;
00973 
00974     if (al->table) {
00975 #ifdef DEBUG
00976         JS_ATOMIC_INCREMENT(&js_atom_map_hash_table_count);
00977 #endif
00978         JS_HashTableEnumerateEntries(al->table, js_map_atom, vector);
00979     } else {
00980         do {
00981             vector[ALE_INDEX(ale)] = ALE_ATOM(ale);
00982         } while ((ale = ALE_NEXT(ale)) != NULL);
00983     }
00984     ATOM_LIST_INIT(al);
00985 
00986     map->vector = vector;
00987     map->length = (jsatomid)count;
00988     return JS_TRUE;
00989 }
00990 
00991 JS_FRIEND_API(void)
00992 js_FreeAtomMap(JSContext *cx, JSAtomMap *map)
00993 {
00994     if (map->vector) {
00995         JS_free(cx, map->vector);
00996         map->vector = NULL;
00997     }
00998     map->length = 0;
00999 }