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<int entrysize> | |
15898 MaybeObject* OrderedHashTable<entrysize>::Allocate(Heap* heap, int capacity) { | |
arv (Not doing code reviews)
2014/04/01 15:22:45
We should probably have a pretenure flag here too.
adamk
2014/04/03 22:53:38
Added a PretenureFlag, though I wonder if I need t
| |
15899 // capacity must be a factor of two | |
15900 const int kMinCapacity = 4; | |
15901 capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity)); | |
15902 if (capacity > kMaxCapacity) { | |
15903 v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true); | |
15904 } | |
15905 int num_buckets = capacity / kLoadFactor; | |
15906 OrderedHashTable* table; | |
15907 { MaybeObject* maybe_obj = | |
15908 heap->AllocateFixedArray( | |
15909 kHashTableStartIndex + num_buckets | |
15910 + (capacity * kEntrySize)); | |
15911 if (!maybe_obj->To(&table)) return maybe_obj; | |
15912 } | |
15913 for (int i = 0; i < num_buckets; ++i) { | |
15914 table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound)); | |
15915 } | |
15916 table->SetNumberOfBuckets(num_buckets); | |
15917 table->SetNumberOfElements(0); | |
15918 table->SetNumberOfDeletedElements(0); | |
15919 return table; | |
15920 } | |
15921 | |
15922 | |
15923 template<int entrysize> | |
15924 MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable() { | |
Michael Starzinger
2014/04/02 12:09:37
Is there a particular reason why this implementati
Michael Starzinger
2014/04/02 12:12:18
... [to declare them explicitly] in the concrete s
rossberg
2014/04/02 13:09:12
More concretely, something like
template<class De
adamk
2014/04/02 22:01:10
Done and done. This code was so-structured because
Michael Starzinger
2014/04/04 09:38:12
I definitely prefer handlified as you did in your
| |
15925 int nof = NumberOfElements(); | |
15926 int nod = NumberOfDeletedElements(); | |
15927 int capacity = Capacity(); | |
15928 if ((nof + nod) < capacity) return this; | |
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 int new_capacity = (nod < (capacity >> 1)) ? capacity << 1 : capacity; | |
15933 OrderedHashTable* new_table; | |
15934 { MaybeObject* maybe_obj = Allocate(GetHeap(), new_capacity); | |
15935 if (!maybe_obj->To(&new_table)) return maybe_obj; | |
15936 } | |
15937 return Rehash(new_table); | |
15938 } | |
15939 | |
15940 | |
15941 template<int entrysize> | |
15942 MaybeObject* OrderedHashTable<entrysize>::Shrink() { | |
Michael Starzinger
2014/04/02 12:09:37
Likewise.
| |
15943 int nof = NumberOfElements(); | |
15944 int capacity = Capacity(); | |
15945 if (nof > (capacity >> 2)) return this; | |
15946 int new_capacity = capacity / 2; | |
15947 OrderedHashTable* new_table; | |
15948 { MaybeObject* maybe_obj = Allocate(GetHeap(), new_capacity); | |
15949 if (!maybe_obj->To(&new_table)) return maybe_obj; | |
15950 } | |
15951 return Rehash(new_table); | |
15952 } | |
15953 | |
15954 | |
15955 template<int entrysize> | |
15956 MaybeObject* OrderedHashTable<entrysize>::Rehash(OrderedHashTable* new_table) { | |
Michael Starzinger
2014/04/02 12:09:37
AFAICT, addressing the above two comments would al
| |
15957 int nof = NumberOfElements(); | |
15958 int nod = NumberOfDeletedElements(); | |
15959 int new_buckets = new_table->NumberOfBuckets(); | |
15960 int new_entry = 0; | |
15961 for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { | |
15962 Object* key = KeyAt(old_entry); | |
15963 if (key->IsTheHole()) continue; | |
15964 Object* hash = key->GetHash(); | |
15965 int bucket = Smi::cast(hash)->value() & (new_buckets - 1); | |
15966 Object* chain_entry = new_table->get(kHashTableStartIndex + bucket); | |
15967 new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); | |
15968 int new_index = new_table->EntryToIndex(new_entry); | |
15969 int old_index = EntryToIndex(old_entry); | |
15970 for (int i = 0; i < entrysize; ++i) { | |
15971 Object* value = get(old_index + i); | |
15972 new_table->set(new_index + i, value); | |
15973 } | |
15974 new_table->set(new_index + kChainOffset, chain_entry); | |
15975 ++new_entry; | |
15976 } | |
15977 new_table->SetNumberOfElements(nof); | |
15978 return new_table; | |
15979 } | |
15980 | |
15981 | |
15982 template<int entrysize> | |
15983 int OrderedHashTable<entrysize>::FindEntry(Object* key) { | |
15984 ASSERT(!key->IsTheHole()); | |
15985 Object* hash = key->GetHash(); | |
15986 if (hash->IsUndefined()) return kNotFound; | |
15987 for (int entry = HashToEntry(Smi::cast(hash)->value()); | |
15988 entry != kNotFound; | |
15989 entry = ChainAt(entry)) { | |
15990 Object* candidate = KeyAt(entry); | |
15991 if (candidate->SameValue(key)) | |
15992 return entry; | |
15993 } | |
15994 return kNotFound; | |
15995 } | |
15996 | |
15997 | |
15998 template<int entrysize> | |
15999 int OrderedHashTable<entrysize>::AddEntry(int hash) { | |
16000 int entry = NumberOfElements() + NumberOfDeletedElements(); | |
16001 int bucket = HashToBucket(hash); | |
16002 int index = EntryToIndex(entry); | |
16003 Object* chain_entry = get(kHashTableStartIndex + bucket); | |
16004 set(kHashTableStartIndex + bucket, Smi::FromInt(entry)); | |
16005 set(index + kChainOffset, chain_entry); | |
16006 SetNumberOfElements(NumberOfElements() + 1); | |
16007 return index; | |
16008 } | |
16009 | |
16010 | |
16011 template<int entrysize> | |
16012 void OrderedHashTable<entrysize>::RemoveEntry(int entry) { | |
16013 int index = EntryToIndex(entry); | |
16014 for (int i = 0; i < entrysize; ++i) { | |
16015 set_the_hole(index + i); | |
16016 } | |
16017 SetNumberOfElements(NumberOfElements() - 1); | |
16018 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); | |
16019 } | |
16020 | |
16021 | |
16022 template class OrderedHashTable<1>; | |
16023 template class OrderedHashTable<2>; | |
16024 | |
16025 | |
16026 bool OrderedHashSet::Contains(Object* key) { | |
16027 return FindEntry(key) != kNotFound; | |
16028 } | |
16029 | |
16030 | |
16031 Handle<OrderedHashSet> OrderedHashSet::EnsureGrowable( | |
Michael Starzinger
2014/04/02 12:09:37
Obsolete if above comments are addressed, I think.
| |
16032 Handle<OrderedHashSet> table) { | |
16033 Handle<OrderedHashTable<1> > table_base = table; | |
16034 CALL_HEAP_FUNCTION(table_base->GetIsolate(), | |
16035 table_base->EnsureGrowable(), | |
16036 OrderedHashSet); | |
16037 } | |
16038 | |
16039 | |
16040 Handle<OrderedHashSet> OrderedHashSet::Shrink(Handle<OrderedHashSet> table) { | |
Michael Starzinger
2014/04/02 12:09:37
Likewise.
| |
16041 Handle<OrderedHashTable<1> > table_base = table; | |
16042 CALL_HEAP_FUNCTION(table_base->GetIsolate(), | |
16043 table_base->Shrink(), | |
16044 OrderedHashSet); | |
16045 } | |
16046 | |
16047 | |
16048 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table, | |
16049 Handle<Object> key) { | |
16050 if (table->FindEntry(*key) != kNotFound) return table; | |
16051 | |
16052 table = EnsureGrowable(table); | |
16053 | |
16054 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | |
16055 int index = table->AddEntry(Smi::cast(*hash)->value()); | |
16056 table->set(index, *key); | |
16057 return table; | |
16058 } | |
16059 | |
16060 | |
16061 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, | |
16062 Handle<Object> key) { | |
16063 int entry = table->FindEntry(*key); | |
16064 if (entry == kNotFound) return table; | |
16065 table->RemoveEntry(entry); | |
16066 // TODO(adamk): Don't shrink if we're being iterated over | |
16067 return Shrink(table); | |
16068 } | |
16069 | |
16070 | |
16071 Object* OrderedHashMap::Lookup(Object* key) { | |
16072 int entry = FindEntry(key); | |
16073 if (entry == kNotFound) return GetHeap()->the_hole_value(); | |
16074 return ValueAt(entry); | |
16075 } | |
16076 | |
16077 | |
16078 Handle<OrderedHashMap> OrderedHashMap::EnsureGrowable( | |
Michael Starzinger
2014/04/02 12:09:37
Likewise.
| |
16079 Handle<OrderedHashMap> table) { | |
16080 Handle<OrderedHashTable<2> > table_base = table; | |
16081 CALL_HEAP_FUNCTION(table_base->GetIsolate(), | |
16082 table_base->EnsureGrowable(), | |
16083 OrderedHashMap); | |
16084 } | |
16085 | |
16086 | |
16087 Handle<OrderedHashMap> OrderedHashMap::Shrink(Handle<OrderedHashMap> table) { | |
Michael Starzinger
2014/04/02 12:09:37
Likewise.
| |
16088 Handle<OrderedHashTable<2> > table_base = table; | |
16089 CALL_HEAP_FUNCTION(table_base->GetIsolate(), | |
16090 table_base->Shrink(), | |
16091 OrderedHashMap); | |
16092 } | |
16093 | |
16094 | |
16095 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, | |
16096 Handle<Object> key, | |
16097 Handle<Object> value) { | |
16098 int entry = table->FindEntry(*key); | |
16099 | |
16100 if (value->IsTheHole()) { | |
16101 if (entry == kNotFound) return table; | |
16102 table->RemoveEntry(entry); | |
16103 // TODO(adamk): Only shrink if not iterating | |
16104 return Shrink(table); | |
16105 } | |
16106 | |
16107 if (entry != kNotFound) { | |
16108 table->set(table->EntryToIndex(entry) + kValueOffset, *value); | |
16109 return table; | |
16110 } | |
16111 | |
16112 table = EnsureGrowable(table); | |
16113 | |
16114 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | |
16115 int index = table->AddEntry(Smi::cast(*hash)->value()); | |
16116 table->set(index, *key); | |
16117 table->set(index + kValueOffset, *value); | |
16118 return table; | |
16119 } | |
16120 | |
16121 | |
15897 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( | 16122 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( |
15898 DeclaredAccessorDescriptor* descriptor) | 16123 DeclaredAccessorDescriptor* descriptor) |
15899 : array_(descriptor->serialized_data()->GetDataStartAddress()), | 16124 : array_(descriptor->serialized_data()->GetDataStartAddress()), |
15900 length_(descriptor->serialized_data()->length()), | 16125 length_(descriptor->serialized_data()->length()), |
15901 offset_(0) { | 16126 offset_(0) { |
15902 } | 16127 } |
15903 | 16128 |
15904 | 16129 |
15905 const DeclaredAccessorDescriptorData* | 16130 const DeclaredAccessorDescriptorData* |
15906 DeclaredAccessorDescriptorIterator::Next() { | 16131 DeclaredAccessorDescriptorIterator::Next() { |
(...skipping 512 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
16419 #define ERROR_MESSAGES_TEXTS(C, T) T, | 16644 #define ERROR_MESSAGES_TEXTS(C, T) T, |
16420 static const char* error_messages_[] = { | 16645 static const char* error_messages_[] = { |
16421 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) | 16646 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) |
16422 }; | 16647 }; |
16423 #undef ERROR_MESSAGES_TEXTS | 16648 #undef ERROR_MESSAGES_TEXTS |
16424 return error_messages_[reason]; | 16649 return error_messages_[reason]; |
16425 } | 16650 } |
16426 | 16651 |
16427 | 16652 |
16428 } } // namespace v8::internal | 16653 } } // namespace v8::internal |
OLD | NEW |