OLD | NEW |
---|---|
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 15876 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
15887 } | 15887 } |
15888 | 15888 |
15889 | 15889 |
15890 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) { | 15890 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) { |
15891 set(EntryToIndex(entry), key); | 15891 set(EntryToIndex(entry), key); |
15892 set(EntryToValueIndex(entry), value); | 15892 set(EntryToValueIndex(entry), value); |
15893 ElementAdded(); | 15893 ElementAdded(); |
15894 } | 15894 } |
15895 | 15895 |
15896 | 15896 |
15897 template<class Derived, int entrysize> | |
15898 Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate( | |
15899 Isolate* isolate, int capacity, PretenureFlag pretenure) { | |
15900 // capacity must be a factor of two | |
Michael Starzinger
2014/04/04 09:38:13
nit: Comment says "factor", code says "power". Als
adamk
2014/04/04 20:18:35
Done and explained why. In a follow-up I'll probab
| |
15901 const int kMinCapacity = 4; | |
15902 capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity)); | |
15903 if (capacity > kMaxCapacity) { | |
15904 v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true); | |
15905 } | |
15906 int num_buckets = capacity / kLoadFactor; | |
15907 Handle<Derived> table = | |
15908 Handle<Derived>::cast( | |
15909 isolate->factory()->NewFixedArray( | |
15910 kHashTableStartIndex + num_buckets + (capacity * kEntrySize), | |
15911 pretenure)); | |
15912 for (int i = 0; i < num_buckets; ++i) { | |
15913 table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound)); | |
15914 } | |
15915 table->SetNumberOfBuckets(num_buckets); | |
15916 table->SetNumberOfElements(0); | |
15917 table->SetNumberOfDeletedElements(0); | |
15918 return table; | |
15919 } | |
15920 | |
15921 | |
15922 template<class Derived, int entrysize> | |
15923 Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable( | |
15924 Handle<Derived> table) { | |
15925 int nof = table->NumberOfElements(); | |
15926 int nod = table->NumberOfDeletedElements(); | |
15927 int capacity = table->Capacity(); | |
15928 if ((nof + nod) < capacity) return table; | |
15929 // Don't need to grow if we can simply clear out deleted entries instead. | |
15930 // Note that we can't compact in place, though, so we always allocate | |
15931 // a new table. | |
15932 return Rehash(table, (nod < (capacity >> 1)) ? capacity << 1 : capacity); | |
15933 } | |
15934 | |
15935 | |
15936 template<class Derived, int entrysize> | |
15937 Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink( | |
15938 Handle<Derived> table) { | |
15939 int nof = table->NumberOfElements(); | |
15940 int capacity = table->Capacity(); | |
15941 if (nof > (capacity >> 2)) return table; | |
15942 return Rehash(table, capacity / 2); | |
15943 } | |
15944 | |
15945 | |
15946 template<class Derived, int entrysize> | |
15947 Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash( | |
15948 Handle<Derived> table, int new_capacity) { | |
15949 Handle<Derived> new_table = | |
15950 Allocate(table->GetIsolate(), | |
15951 new_capacity, | |
15952 table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED); | |
15953 int nof = table->NumberOfElements(); | |
15954 int nod = table->NumberOfDeletedElements(); | |
15955 int new_buckets = new_table->NumberOfBuckets(); | |
15956 int new_entry = 0; | |
15957 for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { | |
15958 Object* key = table->KeyAt(old_entry); | |
15959 if (key->IsTheHole()) continue; | |
15960 Object* hash = key->GetHash(); | |
15961 int bucket = Smi::cast(hash)->value() & (new_buckets - 1); | |
15962 Object* chain_entry = new_table->get(kHashTableStartIndex + bucket); | |
15963 new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); | |
15964 int new_index = new_table->EntryToIndex(new_entry); | |
15965 int old_index = table->EntryToIndex(old_entry); | |
15966 for (int i = 0; i < entrysize; ++i) { | |
15967 Object* value = table->get(old_index + i); | |
15968 new_table->set(new_index + i, value); | |
15969 } | |
15970 new_table->set(new_index + kChainOffset, chain_entry); | |
15971 ++new_entry; | |
15972 } | |
15973 new_table->SetNumberOfElements(nof); | |
15974 return new_table; | |
15975 } | |
15976 | |
15977 | |
15978 template<class Derived, int entrysize> | |
15979 int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) { | |
15980 ASSERT(!key->IsTheHole()); | |
15981 Object* hash = key->GetHash(); | |
15982 if (hash->IsUndefined()) return kNotFound; | |
15983 for (int entry = HashToEntry(Smi::cast(hash)->value()); | |
15984 entry != kNotFound; | |
15985 entry = ChainAt(entry)) { | |
15986 Object* candidate = KeyAt(entry); | |
15987 if (candidate->SameValue(key)) | |
15988 return entry; | |
15989 } | |
15990 return kNotFound; | |
15991 } | |
15992 | |
15993 | |
15994 template<class Derived, int entrysize> | |
15995 int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) { | |
15996 int entry = NumberOfElements() + NumberOfDeletedElements(); | |
15997 int bucket = HashToBucket(hash); | |
15998 int index = EntryToIndex(entry); | |
15999 Object* chain_entry = get(kHashTableStartIndex + bucket); | |
16000 set(kHashTableStartIndex + bucket, Smi::FromInt(entry)); | |
16001 set(index + kChainOffset, chain_entry); | |
16002 SetNumberOfElements(NumberOfElements() + 1); | |
16003 return index; | |
16004 } | |
16005 | |
16006 | |
16007 template<class Derived, int entrysize> | |
16008 void OrderedHashTable<Derived, entrysize>::RemoveEntry(int entry) { | |
16009 int index = EntryToIndex(entry); | |
16010 for (int i = 0; i < entrysize; ++i) { | |
16011 set_the_hole(index + i); | |
16012 } | |
16013 SetNumberOfElements(NumberOfElements() - 1); | |
16014 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); | |
16015 } | |
16016 | |
16017 | |
16018 template class OrderedHashTable<OrderedHashSet, 1>; | |
16019 template class OrderedHashTable<OrderedHashMap, 2>; | |
16020 | |
16021 | |
16022 bool OrderedHashSet::Contains(Object* key) { | |
16023 return FindEntry(key) != kNotFound; | |
16024 } | |
16025 | |
16026 | |
16027 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table, | |
16028 Handle<Object> key) { | |
16029 if (table->FindEntry(*key) != kNotFound) return table; | |
16030 | |
16031 table = EnsureGrowable(table); | |
16032 | |
16033 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | |
16034 int index = table->AddEntry(Smi::cast(*hash)->value()); | |
16035 table->set(index, *key); | |
16036 return table; | |
16037 } | |
16038 | |
16039 | |
16040 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, | |
16041 Handle<Object> key) { | |
16042 int entry = table->FindEntry(*key); | |
16043 if (entry == kNotFound) return table; | |
16044 table->RemoveEntry(entry); | |
16045 // TODO(adamk): Don't shrink if we're being iterated over | |
16046 return Shrink(table); | |
16047 } | |
16048 | |
16049 | |
16050 Object* OrderedHashMap::Lookup(Object* key) { | |
16051 int entry = FindEntry(key); | |
16052 if (entry == kNotFound) return GetHeap()->the_hole_value(); | |
16053 return ValueAt(entry); | |
16054 } | |
16055 | |
16056 | |
16057 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, | |
16058 Handle<Object> key, | |
16059 Handle<Object> value) { | |
16060 int entry = table->FindEntry(*key); | |
16061 | |
16062 if (value->IsTheHole()) { | |
16063 if (entry == kNotFound) return table; | |
16064 table->RemoveEntry(entry); | |
16065 // TODO(adamk): Only shrink if not iterating | |
16066 return Shrink(table); | |
16067 } | |
16068 | |
16069 if (entry != kNotFound) { | |
16070 table->set(table->EntryToIndex(entry) + kValueOffset, *value); | |
16071 return table; | |
16072 } | |
16073 | |
16074 table = EnsureGrowable(table); | |
16075 | |
16076 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | |
16077 int index = table->AddEntry(Smi::cast(*hash)->value()); | |
16078 table->set(index, *key); | |
16079 table->set(index + kValueOffset, *value); | |
16080 return table; | |
16081 } | |
16082 | |
16083 | |
15897 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( | 16084 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( |
15898 DeclaredAccessorDescriptor* descriptor) | 16085 DeclaredAccessorDescriptor* descriptor) |
15899 : array_(descriptor->serialized_data()->GetDataStartAddress()), | 16086 : array_(descriptor->serialized_data()->GetDataStartAddress()), |
15900 length_(descriptor->serialized_data()->length()), | 16087 length_(descriptor->serialized_data()->length()), |
15901 offset_(0) { | 16088 offset_(0) { |
15902 } | 16089 } |
15903 | 16090 |
15904 | 16091 |
15905 const DeclaredAccessorDescriptorData* | 16092 const DeclaredAccessorDescriptorData* |
15906 DeclaredAccessorDescriptorIterator::Next() { | 16093 DeclaredAccessorDescriptorIterator::Next() { |
(...skipping 512 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
16419 #define ERROR_MESSAGES_TEXTS(C, T) T, | 16606 #define ERROR_MESSAGES_TEXTS(C, T) T, |
16420 static const char* error_messages_[] = { | 16607 static const char* error_messages_[] = { |
16421 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) | 16608 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) |
16422 }; | 16609 }; |
16423 #undef ERROR_MESSAGES_TEXTS | 16610 #undef ERROR_MESSAGES_TEXTS |
16424 return error_messages_[reason]; | 16611 return error_messages_[reason]; |
16425 } | 16612 } |
16426 | 16613 |
16427 | 16614 |
16428 } } // namespace v8::internal | 16615 } } // namespace v8::internal |
OLD | NEW |