| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef VM_HASH_TABLE_H_ | 5 #ifndef VM_HASH_TABLE_H_ |
| 6 #define VM_HASH_TABLE_H_ | 6 #define VM_HASH_TABLE_H_ |
| 7 | 7 |
| 8 // Temporarily used when sorting the indices in EnumIndexHashTable. | 8 // Temporarily used when sorting the indices in EnumIndexHashTable. |
| 9 // TODO(koda): Remove these dependencies before using in production. | 9 // TODO(koda): Remove these dependencies before using in production. |
| 10 #include <map> | 10 #include <map> |
| (...skipping 26 matching lines...) Expand all Loading... |
| 37 // - UnorderedHashSet | 37 // - UnorderedHashSet |
| 38 // - EnumIndexHashSet | 38 // - EnumIndexHashSet |
| 39 // - LinkedListHashSet | 39 // - LinkedListHashSet |
| 40 // Each of these can be finally specialized with KeyTraits to support any set of | 40 // Each of these can be finally specialized with KeyTraits to support any set of |
| 41 // lookup key types (e.g., look up a char* in a set of String objects), and | 41 // lookup key types (e.g., look up a char* in a set of String objects), and |
| 42 // any equality and hash code computation. | 42 // any equality and hash code computation. |
| 43 // | 43 // |
| 44 // The classes all wrap an Array handle, and metods like HashSet::Insert can | 44 // The classes all wrap an Array handle, and metods like HashSet::Insert can |
| 45 // trigger growth into a new RawArray, updating the handle. Debug mode asserts | 45 // trigger growth into a new RawArray, updating the handle. Debug mode asserts |
| 46 // that 'Release' was called once to access the final array before destruction. | 46 // that 'Release' was called once to access the final array before destruction. |
| 47 // NOTE: The handle returned by 'Release' is cleared by ~HashTable. |
| 47 // | 48 // |
| 48 // Example use: | 49 // Example use: |
| 49 // typedef UnorderedHashMap<FooTraits> FooMap; | 50 // typedef UnorderedHashMap<FooTraits> FooMap; |
| 50 // ... | 51 // ... |
| 51 // FooMap cache(get_foo_cache()); | 52 // FooMap cache(get_foo_cache()); |
| 52 // cache.UpdateOrInsert(name0, obj0); | 53 // cache.UpdateOrInsert(name0, obj0); |
| 53 // cache.UpdateOrInsert(name1, obj1); | 54 // cache.UpdateOrInsert(name1, obj1); |
| 54 // ... | 55 // ... |
| 55 // set_foo_cache(cache.Release()); | 56 // set_foo_cache(cache.Release()); |
| 56 // | 57 // |
| (...skipping 26 matching lines...) Expand all Loading... |
| 83 template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize> | 84 template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize> |
| 84 class HashTable : public ValueObject { | 85 class HashTable : public ValueObject { |
| 85 public: | 86 public: |
| 86 typedef KeyTraits Traits; | 87 typedef KeyTraits Traits; |
| 87 // Uses 'isolate' for handle allocation. 'Release' must be called at the end | 88 // Uses 'isolate' for handle allocation. 'Release' must be called at the end |
| 88 // to obtain the final table after potential growth/shrinkage. | 89 // to obtain the final table after potential growth/shrinkage. |
| 89 HashTable(Isolate* isolate, RawArray* data) | 90 HashTable(Isolate* isolate, RawArray* data) |
| 90 : isolate_(isolate), | 91 : isolate_(isolate), |
| 91 key_handle_(Object::Handle(isolate_)), | 92 key_handle_(Object::Handle(isolate_)), |
| 92 smi_handle_(Smi::Handle(isolate_)), | 93 smi_handle_(Smi::Handle(isolate_)), |
| 93 data_(&Array::Handle(isolate_, data)) {} | 94 data_(&Array::Handle(isolate_, data)), |
| 95 released_data_(NULL) {} |
| 94 // Like above, except uses current isolate. | 96 // Like above, except uses current isolate. |
| 95 explicit HashTable(RawArray* data) | 97 explicit HashTable(RawArray* data) |
| 96 : isolate_(Isolate::Current()), | 98 : isolate_(Isolate::Current()), |
| 97 key_handle_(Object::Handle(isolate_)), | 99 key_handle_(Object::Handle(isolate_)), |
| 98 smi_handle_(Smi::Handle(isolate_)), | 100 smi_handle_(Smi::Handle(isolate_)), |
| 99 data_(&Array::Handle(isolate_, data)) {} | 101 data_(&Array::Handle(isolate_, data)), |
| 102 released_data_(NULL) {} |
| 100 | 103 |
| 104 // Returns the final table. The handle is cleared when this HashTable is |
| 105 // destroyed. |
| 101 Array& Release() { | 106 Array& Release() { |
| 102 ASSERT(data_ != NULL); | 107 ASSERT(data_ != NULL); |
| 103 Array* result = data_; | 108 ASSERT(released_data_ == NULL); |
| 104 // Ensure that no methods are called after 'Release'. | 109 // Ensure that no methods are called after 'Release'. |
| 110 released_data_ = data_; |
| 105 data_ = NULL; | 111 data_ = NULL; |
| 106 return *result; | 112 return *released_data_; |
| 107 } | 113 } |
| 108 | 114 |
| 109 ~HashTable() { | 115 ~HashTable() { |
| 110 // Ensure that 'Release' was called. | 116 // In DEBUG mode, calling 'Release' is mandatory. |
| 111 ASSERT(data_ == NULL); | 117 ASSERT(data_ == NULL); |
| 118 if (released_data_ != NULL) { |
| 119 *released_data_ = Array::null(); |
| 120 } |
| 112 } | 121 } |
| 113 | 122 |
| 114 // Returns a backing storage size such that 'num_occupied' distinct keys can | 123 // Returns a backing storage size such that 'num_occupied' distinct keys can |
| 115 // be inserted into the table. | 124 // be inserted into the table. |
| 116 static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied) { | 125 static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied) { |
| 117 // The current invariant requires at least one unoccupied entry. | 126 // The current invariant requires at least one unoccupied entry. |
| 118 // TODO(koda): Adjust if moving to quadratic probing. | 127 // TODO(koda): Adjust if moving to quadratic probing. |
| 119 intptr_t num_entries = num_occupied + 1; | 128 intptr_t num_entries = num_occupied + 1; |
| 120 return kFirstKeyIndex + (kEntrySize * num_entries); | 129 return kFirstKeyIndex + (kEntrySize * num_entries); |
| 121 } | 130 } |
| (...skipping 176 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 298 | 307 |
| 299 void AdjustSmiValueAt(intptr_t index, intptr_t delta) const { | 308 void AdjustSmiValueAt(intptr_t index, intptr_t delta) const { |
| 300 SetSmiValueAt(index, (GetSmiValueAt(index) + delta)); | 309 SetSmiValueAt(index, (GetSmiValueAt(index) + delta)); |
| 301 } | 310 } |
| 302 | 311 |
| 303 Isolate* isolate() const { return isolate_; } | 312 Isolate* isolate() const { return isolate_; } |
| 304 | 313 |
| 305 Isolate* isolate_; | 314 Isolate* isolate_; |
| 306 Object& key_handle_; | 315 Object& key_handle_; |
| 307 Smi& smi_handle_; | 316 Smi& smi_handle_; |
| 308 // This is a pointer rather than a reference, to enable Release nulling it, | 317 // Exactly one of these is non-NULL, depending on whether Release was called. |
| 309 // preventing post-Release modification. | |
| 310 Array* data_; | 318 Array* data_; |
| 319 Array* released_data_; |
| 311 | 320 |
| 312 friend class HashTables; | 321 friend class HashTables; |
| 313 }; | 322 }; |
| 314 | 323 |
| 315 | 324 |
| 316 // Table with unspecified iteration order. No payload overhead or metadata. | 325 // Table with unspecified iteration order. No payload overhead or metadata. |
| 317 template<typename KeyTraits, intptr_t kUserPayloadSize> | 326 template<typename KeyTraits, intptr_t kUserPayloadSize> |
| 318 class UnorderedHashTable : public HashTable<KeyTraits, kUserPayloadSize, 0> { | 327 class UnorderedHashTable : public HashTable<KeyTraits, kUserPayloadSize, 0> { |
| 319 public: | 328 public: |
| 320 typedef HashTable<KeyTraits, kUserPayloadSize, 0> BaseTable; | 329 typedef HashTable<KeyTraits, kUserPayloadSize, 0> BaseTable; |
| (...skipping 361 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 682 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > { | 691 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > { |
| 683 public: | 692 public: |
| 684 typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet; | 693 typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet; |
| 685 explicit EnumIndexHashSet(RawArray* data) : BaseSet(data) {} | 694 explicit EnumIndexHashSet(RawArray* data) : BaseSet(data) {} |
| 686 EnumIndexHashSet(Isolate* isolate, RawArray* data) : BaseSet(isolate, data) {} | 695 EnumIndexHashSet(Isolate* isolate, RawArray* data) : BaseSet(isolate, data) {} |
| 687 }; | 696 }; |
| 688 | 697 |
| 689 } // namespace dart | 698 } // namespace dart |
| 690 | 699 |
| 691 #endif // VM_HASH_TABLE_H_ | 700 #endif // VM_HASH_TABLE_H_ |
| OLD | NEW |