/[jscoverage]/trunk/js/jsatom.cpp
ViewVC logotype

Diff of /trunk/js/jsatom.cpp

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 459 by siliconforks, Tue Dec 9 03:37:47 2008 UTC revision 460 by siliconforks, Sat Sep 26 23:15:22 2009 UTC
# Line 49  Line 49 
49  #include "jsprf.h"  #include "jsprf.h"
50  #include "jsapi.h"  #include "jsapi.h"
51  #include "jsatom.h"  #include "jsatom.h"
52    #include "jsbit.h"
53  #include "jscntxt.h"  #include "jscntxt.h"
 #include "jsversion.h"  
54  #include "jsgc.h"  #include "jsgc.h"
55  #include "jslock.h"  #include "jslock.h"
56  #include "jsnum.h"  #include "jsnum.h"
57    #include "jsparse.h"
58  #include "jsscan.h"  #include "jsscan.h"
59  #include "jsstr.h"  #include "jsstr.h"
60    #include "jsversion.h"
61    
62    /*
63     * ATOM_HASH assumes that JSHashNumber is 32-bit even on 64-bit systems.
64     */
65    JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4);
66    JS_STATIC_ASSERT(sizeof(JSAtom *) == JS_BYTES_PER_WORD);
67    
68    /*
69     * Start and limit offsets for atom pointers in JSAtomState must be aligned
70     * on the word boundary.
71     */
72    JS_STATIC_ASSERT(ATOM_OFFSET_START % sizeof(JSAtom *) == 0);
73    JS_STATIC_ASSERT(ATOM_OFFSET_LIMIT % sizeof(JSAtom *) == 0);
74    
75    /*
76     * JS_BOOLEAN_STR and JS_TYPE_STR assume that boolean names starts from the
77     * index 1 and type name starts from the index 1+2 atoms in JSAtomState.
78     */
79    JS_STATIC_ASSERT(1 * sizeof(JSAtom *) ==
80                     offsetof(JSAtomState, booleanAtoms) - ATOM_OFFSET_START);
81    JS_STATIC_ASSERT((1 + 2) * sizeof(JSAtom *) ==
82                     offsetof(JSAtomState, typeAtoms) - ATOM_OFFSET_START);
83    
84  const char *  const char *
85  js_AtomToPrintableString(JSContext *cx, JSAtom *atom)  js_AtomToPrintableString(JSContext *cx, JSAtom *atom)
# Line 78  Line 102 
102   * asserts check these relations.   * asserts check these relations.
103   */   */
104  JS_STATIC_ASSERT(JSTYPE_LIMIT == 8);  JS_STATIC_ASSERT(JSTYPE_LIMIT == 8);
 JS_STATIC_ASSERT(JSVAL_TO_BOOLEAN(JSVAL_VOID) == 2);  
105  JS_STATIC_ASSERT(JSTYPE_VOID == 0);  JS_STATIC_ASSERT(JSTYPE_VOID == 0);
106    
107  const char *const js_common_atom_names[] = {  const char *const js_common_atom_names[] = {
# Line 912  Line 935 
935      return ATOM_HASH(atom);      return ATOM_HASH(atom);
936  }  }
937    
938    #if JS_BITS_PER_WORD == 32
939    # define TEMP_SIZE_START_LOG2   5
940    #else
941    # define TEMP_SIZE_START_LOG2   6
942    #endif
943    #define TEMP_SIZE_LIMIT_LOG2    (TEMP_SIZE_START_LOG2 + NUM_TEMP_FREELISTS)
944    
945    #define TEMP_SIZE_START         JS_BIT(TEMP_SIZE_START_LOG2)
946    #define TEMP_SIZE_LIMIT         JS_BIT(TEMP_SIZE_LIMIT_LOG2)
947    
948    JS_STATIC_ASSERT(TEMP_SIZE_START >= sizeof(JSHashTable));
949    
950  static void *  static void *
951  js_alloc_temp_space(void *priv, size_t size)  js_alloc_temp_space(void *priv, size_t size)
952  {  {
953      JSContext *cx = (JSContext *) priv;      JSCompiler *jsc = (JSCompiler *) priv;
954    
955      void *space;      void *space;
956        if (size < TEMP_SIZE_LIMIT) {
957            int bin = JS_CeilingLog2(size) - TEMP_SIZE_START_LOG2;
958            JS_ASSERT(unsigned(bin) < NUM_TEMP_FREELISTS);
959    
960            space = jsc->tempFreeList[bin];
961            if (space) {
962                jsc->tempFreeList[bin] = *(void **)space;
963                return space;
964            }
965        }
966    
967      JS_ARENA_ALLOCATE(space, &cx->tempPool, size);      JS_ARENA_ALLOCATE(space, &jsc->context->tempPool, size);
968      if (!space)      if (!space)
969          js_ReportOutOfScriptQuota(cx);          js_ReportOutOfScriptQuota(jsc->context);
970      return space;      return space;
971  }  }
972    
973  static void  static void
974  js_free_temp_space(void *priv, void *item)  js_free_temp_space(void *priv, void *item, size_t size)
975  {  {
976        if (size >= TEMP_SIZE_LIMIT)
977            return;
978    
979        JSCompiler *jsc = (JSCompiler *) priv;
980        int bin = JS_CeilingLog2(size) - TEMP_SIZE_START_LOG2;
981        JS_ASSERT(unsigned(bin) < NUM_TEMP_FREELISTS);
982    
983        *(void **)item = jsc->tempFreeList[bin];
984        jsc->tempFreeList[bin] = item;
985  }  }
986    
987  static JSHashEntry *  static JSHashEntry *
988  js_alloc_temp_entry(void *priv, const void *key)  js_alloc_temp_entry(void *priv, const void *key)
989  {  {
990      JSContext *cx = (JSContext *) priv;      JSCompiler *jsc = (JSCompiler *) priv;
991      JSAtomListElement *ale;      JSAtomListElement *ale;
992    
993      JS_ARENA_ALLOCATE_TYPE(ale, JSAtomListElement, &cx->tempPool);      ale = jsc->aleFreeList;
994        if (ale) {
995            jsc->aleFreeList = ALE_NEXT(ale);
996            return &ale->entry;
997        }
998    
999        JS_ARENA_ALLOCATE_TYPE(ale, JSAtomListElement, &jsc->context->tempPool);
1000      if (!ale) {      if (!ale) {
1001          js_ReportOutOfScriptQuota(cx);          js_ReportOutOfScriptQuota(jsc->context);
1002          return NULL;          return NULL;
1003      }      }
1004      return &ale->entry;      return &ale->entry;
# Line 946  Line 1007 
1007  static void  static void
1008  js_free_temp_entry(void *priv, JSHashEntry *he, uintN flag)  js_free_temp_entry(void *priv, JSHashEntry *he, uintN flag)
1009  {  {
1010        JSCompiler *jsc = (JSCompiler *) priv;
1011        JSAtomListElement *ale = (JSAtomListElement *) he;
1012    
1013        ALE_SET_NEXT(ale, jsc->aleFreeList);
1014        jsc->aleFreeList = ale;
1015  }  }
1016    
1017  static JSHashAllocOps temp_alloc_ops = {  static JSHashAllocOps temp_alloc_ops = {
# Line 954  Line 1020 
1020  };  };
1021    
1022  JSAtomListElement *  JSAtomListElement *
1023  js_IndexAtom(JSContext *cx, JSAtom *atom, JSAtomList *al)  JSAtomList::rawLookup(JSAtom *atom, JSHashEntry **&hep)
1024  {  {
1025        JSAtomListElement *ale;
1026    
1027        if (table) {
1028            hep = JS_HashTableRawLookup(table, ATOM_HASH(atom), atom);
1029            ale = *hep ? (JSAtomListElement *) *hep : NULL;
1030        } else {
1031            JSHashEntry **alep = &list;
1032            hep = NULL;
1033            while ((ale = (JSAtomListElement *)*alep) != NULL) {
1034                if (ALE_ATOM(ale) == atom) {
1035                    /* Hit, move atom's element to the front of the list. */
1036                    *alep = ale->entry.next;
1037                    ale->entry.next = list;
1038                    list = &ale->entry;
1039                    break;
1040                }
1041                alep = &ale->entry.next;
1042            }
1043        }
1044        return ale;
1045    }
1046    
1047    #define ATOM_LIST_HASH_THRESHOLD        12
1048    
1049    JSAtomListElement *
1050    JSAtomList::add(JSCompiler *jsc, JSAtom *atom, AddHow how)
1051    {
1052        JS_ASSERT(!set);
1053    
1054      JSAtomListElement *ale, *ale2, *next;      JSAtomListElement *ale, *ale2, *next;
1055      JSHashEntry **hep;      JSHashEntry **hep;
1056    
1057      ATOM_LIST_LOOKUP(ale, hep, al, atom);      ale = rawLookup(atom, hep);
1058      if (!ale) {      if (!ale || how != UNIQUE) {
1059          if (al->count < 10) {          if (count < ATOM_LIST_HASH_THRESHOLD && !table) {
1060              /* Few enough for linear search, no hash table needed. */              /* Few enough for linear search and no hash table yet needed. */
1061              JS_ASSERT(!al->table);              ale = (JSAtomListElement *)js_alloc_temp_entry(jsc, atom);
             ale = (JSAtomListElement *)js_alloc_temp_entry(cx, atom);  
1062              if (!ale)              if (!ale)
1063                  return NULL;                  return NULL;
1064              ALE_SET_ATOM(ale, atom);              ALE_SET_ATOM(ale, atom);
1065              ale->entry.next = al->list;  
1066              al->list = &ale->entry;              if (how == HOIST) {
1067                    ale->entry.next = NULL;
1068                    hep = (JSHashEntry **) &list;
1069                    while (*hep)
1070                        hep = &(*hep)->next;
1071                    *hep = &ale->entry;
1072                } else {
1073                    ale->entry.next = list;
1074                    list = &ale->entry;
1075                }
1076          } else {          } else {
1077              /* We want to hash.  Have we already made a hash table? */              /*
1078              if (!al->table) {               * We should hash, or else we already are hashing, but count was
1079                 * reduced by JSAtomList::rawRemove below ATOM_LIST_HASH_THRESHOLD.
1080                 * Check whether we should create the table.
1081                 */
1082                if (!table) {
1083                  /* No hash table yet, so hep had better be null! */                  /* No hash table yet, so hep had better be null! */
1084                  JS_ASSERT(!hep);                  JS_ASSERT(!hep);
1085                  al->table = JS_NewHashTable(al->count + 1, js_hash_atom_ptr,                  table = JS_NewHashTable(count + 1, js_hash_atom_ptr,
1086                                              JS_CompareValues, JS_CompareValues,                                          JS_CompareValues, JS_CompareValues,
1087                                              &temp_alloc_ops, cx);                                          &temp_alloc_ops, jsc);
1088                  if (!al->table)                  if (!table)
1089                      return NULL;                      return NULL;
1090    
1091                  /*                  /*
1092                   * Set ht->nentries explicitly, because we are moving entries                   * Set ht->nentries explicitly, because we are moving entries
1093                   * from al to ht, not calling JS_HashTable(Raw|)Add.                   * from list to ht, not calling JS_HashTable(Raw|)Add.
1094                   */                   */
1095                  al->table->nentries = al->count;                  table->nentries = count;
1096    
1097                  /* Insert each ale on al->list into the new hash table. */                  /*
1098                  for (ale2 = (JSAtomListElement *)al->list; ale2; ale2 = next) {                   * Insert each ale on list into the new hash table. Append to
1099                     * the hash chain rather than inserting at the bucket head, to
1100                     * preserve order among entries with the same key.
1101                     */
1102                    for (ale2 = (JSAtomListElement *)list; ale2; ale2 = next) {
1103                      next = ALE_NEXT(ale2);                      next = ALE_NEXT(ale2);
1104                      ale2->entry.keyHash = ATOM_HASH(ALE_ATOM(ale2));                      ale2->entry.keyHash = ATOM_HASH(ALE_ATOM(ale2));
1105                      hep = JS_HashTableRawLookup(al->table, ale2->entry.keyHash,                      hep = JS_HashTableRawLookup(table, ale2->entry.keyHash,
1106                                                  ale2->entry.key);                                                  ale2->entry.key);
1107                      ale2->entry.next = *hep;                      while (*hep)
1108                            hep = &(*hep)->next;
1109                      *hep = &ale2->entry;                      *hep = &ale2->entry;
1110                        ale2->entry.next = NULL;
1111                  }                  }
1112                  al->list = NULL;                  list = NULL;
1113    
1114                  /* Set hep for insertion of atom's ale, immediately below. */                  /* Set hep for insertion of atom's ale, immediately below. */
1115                  hep = JS_HashTableRawLookup(al->table, ATOM_HASH(atom), atom);                  hep = JS_HashTableRawLookup(table, ATOM_HASH(atom), atom);
1116              }              }
1117    
1118              /* Finally, add an entry for atom into the hash bucket at hep. */              /* Finally, add an entry for atom into the hash bucket at hep. */
1119              ale = (JSAtomListElement *)              ale = (JSAtomListElement *)
1120                    JS_HashTableRawAdd(al->table, hep, ATOM_HASH(atom), atom,                    JS_HashTableRawAdd(table, hep, ATOM_HASH(atom), atom, NULL);
                                      NULL);  
1121              if (!ale)              if (!ale)
1122                  return NULL;                  return NULL;
1123    
1124                /*
1125                 * If hoisting, move ale to the end of its chain after we called
1126                 * JS_HashTableRawAdd, since RawAdd may have grown the table and
1127                 * then recomputed hep to refer to the pointer to the first entry
1128                 * with the given key.
1129                 */
1130                if (how == HOIST && ale->entry.next) {
1131                    *hep = ale->entry.next;
1132                    ale->entry.next = NULL;
1133                    do {
1134                        hep = &(*hep)->next;
1135                    } while (*hep);
1136                    *hep = &ale->entry;
1137                }
1138            }
1139    
1140            ALE_SET_INDEX(ale, count++);
1141        }
1142        return ale;
1143    }
1144    
1145    void
1146    JSAtomList::rawRemove(JSCompiler *jsc, JSAtomListElement *ale, JSHashEntry **hep)
1147    {
1148        JS_ASSERT(!set);
1149        JS_ASSERT(count != 0);
1150    
1151        if (table) {
1152            JS_ASSERT(hep);
1153            JS_HashTableRawRemove(table, hep, &ale->entry);
1154        } else {
1155            JS_ASSERT(!hep);
1156            hep = &list;
1157            while (*hep != &ale->entry) {
1158                JS_ASSERT(*hep);
1159                hep = &(*hep)->next;
1160          }          }
1161            *hep = ale->entry.next;
1162            js_free_temp_entry(jsc, &ale->entry, HT_FREE_ENTRY);
1163        }
1164    
1165          ALE_SET_INDEX(ale, al->count++);      --count;
1166    }
1167    
1168    JSAtomListElement *
1169    JSAtomListIterator::operator ()()
1170    {
1171        JSAtomListElement *ale;
1172        JSHashTable *ht;
1173    
1174        if (index == uint32(-1))
1175            return NULL;
1176    
1177        ale = next;
1178        if (!ale) {
1179            ht = list->table;
1180            if (!ht)
1181                goto done;
1182            do {
1183                if (index == JS_BIT(JS_HASH_BITS - ht->shift))
1184                    goto done;
1185                next = (JSAtomListElement *) ht->buckets[index++];
1186            } while (!next);
1187            ale = next;
1188      }      }
1189    
1190        next = ALE_NEXT(ale);
1191      return ale;      return ale;
1192    
1193      done:
1194        index = uint32(-1);
1195        return NULL;
1196  }  }
1197    
1198  static intN  static intN
# Line 1060  Line 1240 
1240              vector[ALE_INDEX(ale)] = ALE_ATOM(ale);              vector[ALE_INDEX(ale)] = ALE_ATOM(ale);
1241          } while ((ale = ALE_NEXT(ale)) != NULL);          } while ((ale = ALE_NEXT(ale)) != NULL);
1242      }      }
1243      ATOM_LIST_INIT(al);      al->clear();
1244  }  }
Legend:
Removed from v.459  
changed lines
  Added in v.460
  ViewVC Help
Powered by ViewVC 1.1.24