v8源码解析之Dictionary（v8 0.1.5）

本文主要是介绍v8源码解析之Dictionary（v8 0.1.5），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dictionary我们应该不陌生，他是HashTable的基类。我们看一下定义

// 字典基类，prefix大小为两个指针元素，数组中每个元素大小是3个指针
class DictionaryBase: public HashTable<2, 3> {};
class Dictionary: public DictionaryBase {}

由定义可以看到Dictionary的布局如下

Dictionary底层是数组实现的，每个元素的大小是三个指针（key、value、detail）。接着我们看一下类的具体实现。
1 value的存取

  // 一个元素是三个指针，第二个指针指向值，所以加一Object* ValueAt(int entry) { return get(EntryToIndex(entry)+1); }// 设置值void ValueAtPut(int entry, Object* value) {set(EntryToIndex(entry)+1, value);}

2 PropertyDetails存取
PropertyDetails是对属性细节的封装，比如是否可枚举，可读写。

 // 第三个指针是detailPropertyDetails DetailsAt(int entry) {return PropertyDetails(Smi::cast(get(EntryToIndex(entry) + 2)));}// 设置detailvoid DetailsAtPut(int entry, PropertyDetails value) {set(EntryToIndex(entry) + 2, value.AsSmi());}

3 RemoveNumberEntries
RemoveNumberEntries是删除key的值在from和to之间的元素。

void Dictionary::RemoveNumberEntries(uint32_t from, uint32_t to) {// Do nothing if the interval [from, to) is empty.if (from >= to) return;int removed_entries = 0;Object* sentinel = Heap::null_value();int capacity = Capacity();// 遍历所有元素for (int i = 0; i < capacity; i++) {// 找到元素的首地址，分为三个指针，分别是key、value、detailObject* key = KeyAt(i);if (key->IsNumber()) {uint32_t number = static_cast<uint32_t>(key->Number());// 命中则设置对应的索引的值，key、value、detail分别为null、null、0if (from <= number && number < to) {SetEntry(i, sentinel, sentinel, Smi::FromInt(0));// 记录被删除的元素个数removed_entries++;}}}// 重新设置已使用元素的个数SetNumberOfElements(NumberOfElements() - removed_entries);
}

4 RemoveHoles
RemoveHoles实现删除数组中的空元素，通过申请一个新的数组，然后把之前数据的有效值复制过去，完成无效元素的删除。

// 删除空的元素
Object* Dictionary::RemoveHoles() {int capacity = Capacity();// 当前已使用的元素个数，分配一个新的数组Object* obj = Allocate(NumberOfElements());if (obj->IsFailure()) return obj;Dictionary* dict = Dictionary::cast(obj);uint32_t pos = 0;for (int i = 0; i < capacity; i++) {Object* k = KeyAt(i);// 有效元素则追加到新的数组if (IsKey(k)) {dict->AddNumberEntry(pos++, ValueAt(i), DetailsAt(i));}}return dict;
}

5 CopyValuesTo
CopyValuesTo把对象中的有效值复制到另一个数组中

void Dictionary::CopyValuesTo(FixedArray* elements) {int pos = 0;int capacity = Capacity();for (int i = 0; i < capacity; i++) {Object* k = KeyAt(i);if (IsKey(k)) elements->set(pos++, ValueAt(i));}ASSERT(pos == elements->length());
}

6 DeleteProperty
DeleteProperty实现删除字典中的元素，如果可以的话。

Object* Dictionary::DeleteProperty(int entry) {// 获取该元素的属性信息PropertyDetails details = DetailsAt(entry);// 该元素是否可以删除if (details.IsDontDelete()) return Heap::false_value();// 可以删除则设置为无效元素SetEntry(entry, Heap::null_value(), Heap::null_value(), Smi::FromInt(0));// 已使用元素减一ElementRemoved();return Heap::true_value();
}

7 NumberOfElementsFilterAttributes
NumberOfElementsFilterAttributes找出不符合某属性的元素个数。

int Dictionary::NumberOfElementsFilterAttributes(PropertyAttributes filter) {int capacity = Capacity();int result = 0;for (int i = 0; i < capacity; i++) {Object* k = KeyAt(i);if (IsKey(k)) {PropertyAttributes attr = DetailsAt(i).attributes();if ((attr & filter) == 0) result++;}}return result;
}

比如找出可以枚举的元素个数。

int Dictionary::NumberOfEnumElements() {return NumberOfElementsFilterAttributes(static_cast<PropertyAttributes>(DONT_ENUM));
}

8 CopyKeysTo、CopyEnumKeysTo
CopyKeysTo、CopyEnumKeysTo实现复制符合条件的元素的key到另一个数组中。

void Dictionary::CopyKeysTo(FixedArray* storage, PropertyAttributes filter) {ASSERT(storage->length() >= NumberOfEnumElements());int capacity = Capacity();int index = 0;for (int i = 0; i < capacity; i++) {Object* k = KeyAt(i);if (IsKey(k)) {PropertyAttributes attr = DetailsAt(i).attributes();// 不符合filter的key复制到storage数组if ((attr & filter) == 0) storage->set(index++, k);}}ASSERT(storage->length() >= index);
}

// 复制可枚举元素的key和detail到新数组
void Dictionary::CopyEnumKeysTo(FixedArray* storage, FixedArray* sort_array) {ASSERT(storage->length() >= NumberOfEnumElements());int capacity = Capacity();int index = 0;for (int i = 0; i < capacity; i++) {Object* k = KeyAt(i);if (IsKey(k)) {PropertyDetails details = DetailsAt(i);// 可以枚举的元素if (!details.IsDontEnum()) {storage->set(index, k);sort_array->set(index, Smi::FromInt(details.index()));index++;}}}// 对sort_array的内容排序，storage的元素位置也发生相应的变化storage->SortPairs(sort_array);ASSERT(storage->length() >= index);
}

9 设置字典的内容
AtPut实现把键对值加入到字典，如果key已经存在则更新value。

Object* Dictionary::AtPut(Key* key, Object* value) {// 根据key判断是否可以找到对应的项int entry = FindEntry(key);// If the entry is present set the value;// 已经存在则更新值if (entry != -1) {ValueAtPut(entry, value);return this;}Object* obj = EnsureCapacity(1, key);if (obj->IsFailure()) return obj;// 拿到keyObject* k = key->GetObject();if (k->IsFailure()) return k;PropertyDetails details = PropertyDetails(NONE, NORMAL);// 新增一个元素到字典Dictionary::cast(obj)->AddEntry(k, value, details, key->Hash());return obj;
}

我们接着看一下AddEntry。

void Dictionary::AddEntry(Object* key,Object* value,PropertyDetails details,uint32_t hash) {// 找出插入的相对位置uint32_t entry = FindInsertionEntry(key, hash);// index记录元素枚举时的顺序，如果是0则赋值if (details.index() == 0 && key->IsString()) {// 获取下一个枚举序号int index = NextEnumerationIndex();details = PropertyDetails(details.attributes(), details.type(), index);// 更新下一个可用序号SetNextEnumerationIndex(index + 1);}// 真正设置内容SetEntry(entry, key, value, details);// 已使用元素加一ElementAdded();
}

我们再看一下SetEntry。

void Dictionary::SetEntry(int entry,Object* key,Object* value,PropertyDetails details) {ASSERT(!key->IsString() || details.index() > 0);// 算出真正的存储位置int index = EntryToIndex(entry);WriteBarrierMode mode = GetWriteBarrierMode();// 设置key、value、detailset(index, key, mode);set(index+1, value, mode);fast_set(this, index+2, details.AsSmi());
}

10 GenerateNewEnumerationIndices
GenerateNewEnumerationIndices实现序号的重新调整，字典中每个元素都有一个序号。新增元素的时候，序号会自增，但是删除元素的时候，元素对应的id是无法回收重新使用的，因为序号是有序的，所以序号会耗尽，这时候就需要重新排序，以利用删除元素的那些序号。

Object* Dictionary::GenerateNewEnumerationIndices() {// 当前有效元素个数int length = NumberOfElements();// Allocate and initialize iteration order array.// 分配新的数组Object* obj = Heap::AllocateFixedArray(length);if (obj->IsFailure()) return obj;FixedArray* iteration_order = FixedArray::cast(obj);// 按序存储0....length - 1for (int i = 0; i < length; i++) iteration_order->set(i, Smi::FromInt(i));// Allocate array with enumeration order.// 再分配一个数组obj = Heap::AllocateFixedArray(length);if (obj->IsFailure()) return obj;FixedArray* enumeration_order = FixedArray::cast(obj);// Fill the enumeration order array with property details.int capacity = Capacity();int pos = 0;// 存储有效元素的序号for (int i = 0; i < capacity; i++) {if (IsKey(KeyAt(i))) {enumeration_order->set(pos++, Smi::FromInt(DetailsAt(i).index()));}}// Sort the arrays wrt. enumeration order./*对enumeration_order进行排序,iteration_order元素的位置发生相应变化即按照枚举序号进行排序iteration_order = [0,1,2]enumeration_order = [5,6,4]排序后iteration_order = [2,0,1]enumeration_order = [4,5,6] iteration_order记录了原来的位置，所以2记录了4原来所在的相对位置（因为可能有空洞，所以不一定是绝对问题），4现在是最小的，所以原来第二个位置的元素序号最小 */iteration_order->SortPairs(enumeration_order);// Overwrite the enumeration_order with the enumeration indices.for (int i = 0; i < length; i++) {// 获取元素之前的相对位置int index = Smi::cast(iteration_order->get(i))->value();// 重新生成序号int enum_index = PropertyDetails::kInitialIndex + i;// 更新对应位置的序号enumeration_order->set(index, Smi::FromInt(enum_index));}// Update the dictionary with new indices.capacity = Capacity();/*pos用于处理字典中元素的绝对位置到相对位置的映射，如[1, null, 3] 和[1,2]，那么更新第三个元素的时候，得到的值是2*/pos = 0;// 遍历每个元素，更新有效元素的枚举序号for (int i = 0; i < capacity; i++) {if (IsKey(KeyAt(i))) {int enum_index = Smi::cast(enumeration_order->get(pos++))->value();PropertyDetails details = DetailsAt(i);PropertyDetails new_details =PropertyDetails(details.attributes(), details.type(), enum_index);DetailsAtPut(i, new_details);}}// Set the next enumeration index.// 下一个可用的序号SetNextEnumerationIndex(PropertyDetails::kInitialIndex+length);return this;
}

11 Allocate
Allocate用于分类一个字典

Object* Dictionary::Allocate(int at_least_space_for) {Object* obj = DictionaryBase::Allocate(at_least_space_for);// Initialize the next enumeration index.if (!obj->IsFailure()) {// 初始化序号Dictionary::cast(obj)->SetNextEnumerationIndex(PropertyDetails::kInitialIndex);}return obj;
}

12 EnsureCapacity
EnsureCapacity用于扩容

Object* Dictionary::EnsureCapacity(int n, Key* key) {// 序号不够用了，需要重新排序，利用没有被回收的序号if (key->IsStringKey() &&!PropertyDetails::IsValidIndex(NextEnumerationIndex() + n)) {Object* result = GenerateNewEnumerationIndices();if (result->IsFailure()) return result;}// 调用父类的方法return DictionaryBase::EnsureCapacity(n, key);
}

13 UpdateMaxNumberKey
UpdateMaxNumberKey用于更新字典中数字key的最大值。如果得到阈值就进入slow模式。具体的在后面应用的时候分析

void Dictionary::UpdateMaxNumberKey(uint32_t key) {// 已经是slow模式，不需要处理了if (requires_slow_elements()) return;// 数字大于阈值，则设置slow模式if (key > kRequiresSlowElementsLimit) {set(kPrefixStartIndex, Smi::FromInt(kRequiresSlowElementsMask));return;}// 更新最大值Object* max_index_object = get(kPrefixStartIndex);if (!max_index_object->IsSmi() || max_number_key() < key) {set(kPrefixStartIndex, Smi::FromInt(key << kRequiresSlowElementsTagSize));}
}bool Dictionary::requires_slow_elements() {Object* max_index_object = get(kPrefixStartIndex);if (!max_index_object->IsSmi()) return false;return 0 !=(Smi::cast(max_index_object)->value() & kRequiresSlowElementsMask);
}

这篇关于v8源码解析之Dictionary（v8 0.1.5）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---