1 // Copyright 2021 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef SRC_GN_BUILDER_RECORD_MAP_H_ 6 #define SRC_GN_BUILDER_RECORD_MAP_H_ 7 8 #include "gn/builder_record.h" 9 #include "gn/hash_table_base.h" 10 11 // This header implements a custom Label -> BuilderRecord map that is critical 12 // for performance of the Builder class. 13 // 14 // Measurements show it performs better than 15 // std::unordered_map<Label, BuilderRecord>, which itself performs much better 16 // than base::flat_map<Label, BuilderRecord> or std::map<Label, BuilderRecord> 17 // 18 // NOTE: This only implements the features required by the Builder class. 19 // 20 21 struct BuilderRecordNode { 22 BuilderRecord* record; is_nullBuilderRecordNode23 bool is_null() const { return !record; } is_tombstoneBuilderRecordNode24 static constexpr bool is_tombstone() { return false; } is_validBuilderRecordNode25 bool is_valid() const { return !is_null() && !is_tombstone(); } hash_valueBuilderRecordNode26 size_t hash_value() const { return record->label().hash(); } 27 }; 28 29 class BuilderRecordMap : public HashTableBase<BuilderRecordNode> { 30 public: 31 using NodeType = BuilderRecordNode; 32 ~BuilderRecordMap()33 ~BuilderRecordMap() { 34 for (auto it = NodeBegin(); it.valid(); ++it) { 35 delete it->record; 36 } 37 } 38 39 // Find BuilderRecord matching |label| or return nullptr. find(const Label & label)40 BuilderRecord* find(const Label& label) const { 41 return Lookup(label)->record; 42 } 43 44 // Try to find BuilderRecord matching |label|, and create one if 45 // none is found. result.first will be true to indicate that a new 46 // record was created. try_emplace(const Label & label,const ParseNode * request_from,BuilderRecord::ItemType type)47 std::pair<bool, BuilderRecord*> try_emplace(const Label& label, 48 const ParseNode* request_from, 49 BuilderRecord::ItemType type) { 50 NodeType* node = Lookup(label); 51 if (node->is_valid()) { 52 return {false, node->record}; 53 } 54 BuilderRecord* record = new BuilderRecord(type, label, request_from); 55 node->record = record; 56 UpdateAfterInsert(); 57 return {true, record}; 58 } 59 60 // Iteration support 61 struct const_iterator : public NodeIterator { 62 const BuilderRecord& operator*() const { return *node_->record; } 63 BuilderRecord& operator*() { return *node_->record; } 64 65 const BuilderRecord* operator->() const { return node_->record; } 66 BuilderRecord* operator->() { return node_->record; } 67 }; 68 begin()69 const_iterator begin() const { return {NodeBegin()}; } end()70 const_iterator end() const { return {NodeEnd()}; } 71 72 private: Lookup(const Label & label)73 NodeType* Lookup(const Label& label) const { 74 return NodeLookup(label.hash(), [&label](const NodeType* node) { 75 return node->record->label() == label; 76 }); 77 } 78 }; 79 80 #endif // SRC_GN_BUILDER_RECORD_MAP_H_ 81