OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 #include "vm/weak_table.h" | 5 #include "vm/weak_table.h" |
6 | 6 |
7 #include "platform/assert.h" | 7 #include "platform/assert.h" |
8 #include "vm/raw_object.h" | 8 #include "vm/raw_object.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
11 | 11 |
12 WeakTable* WeakTable::SetValue(RawObject* key, intptr_t val) { | 12 intptr_t WeakTable::SizeFor(intptr_t count, intptr_t size) { |
13 intptr_t sz = size(); | 13 intptr_t result = size; |
14 intptr_t idx = Hash(key) % sz; | 14 if (count <= (size / 4)) { |
| 15 // Reduce the capacity. |
| 16 result = size / 2; |
| 17 } else { |
| 18 // Increase the capacity. |
| 19 result = size * 2; |
| 20 if (result < size) { |
| 21 FATAL("Reached impossible state of having more weak table entries" |
| 22 " than memory available for heap objects."); |
| 23 } |
| 24 } |
| 25 if (result < kMinSize) { |
| 26 result = kMinSize; |
| 27 } |
| 28 return result; |
| 29 } |
| 30 |
| 31 |
| 32 void WeakTable::SetValue(RawObject* key, intptr_t val) { |
| 33 intptr_t mask = size() - 1; |
| 34 intptr_t idx = Hash(key) & mask; |
15 intptr_t empty_idx = -1; | 35 intptr_t empty_idx = -1; |
16 RawObject* obj = ObjectAt(idx); | 36 RawObject* obj = ObjectAt(idx); |
17 | 37 |
18 while (obj != NULL) { | 38 while (obj != NULL) { |
19 if (obj == key) { | 39 if (obj == key) { |
20 SetValueAt(idx, val); | 40 SetValueAt(idx, val); |
21 return this; | 41 return; |
22 } else if ((empty_idx < 0) && | 42 } else if ((empty_idx < 0) && |
23 (reinterpret_cast<intptr_t>(obj) == kDeletedEntry)) { | 43 (reinterpret_cast<intptr_t>(obj) == kDeletedEntry)) { |
24 empty_idx = idx; // Insert at this location if not found. | 44 empty_idx = idx; // Insert at this location if not found. |
25 } | 45 } |
26 idx = (idx + 1) % sz; | 46 idx = (idx + 1) & mask; |
27 obj = ObjectAt(idx); | 47 obj = ObjectAt(idx); |
28 } | 48 } |
29 | 49 |
30 if (val == 0) { | 50 if (val == 0) { |
31 // Do not enter an invalid value. Associating 0 with a key deletes it from | 51 // Do not enter an invalid value. Associating 0 with a key deletes it from |
32 // this weak table above in SetValueAt. If the key was not present in the | 52 // this weak table above in SetValueAt. If the key was not present in the |
33 // weak table we are done. | 53 // weak table we are done. |
34 return this; | 54 return; |
35 } | 55 } |
36 | 56 |
37 if (empty_idx >= 0) { | 57 if (empty_idx >= 0) { |
38 // We will be reusing a slot below. | 58 // We will be reusing a slot below. |
39 set_used(used() - 1); | 59 set_used(used() - 1); |
40 idx = empty_idx; | 60 idx = empty_idx; |
41 } | 61 } |
42 | 62 |
43 ASSERT(!IsValidEntryAt(idx)); | 63 ASSERT(!IsValidEntryAt(idx)); |
44 // Set the key and value. | 64 // Set the key and value. |
45 SetObjectAt(idx, key); | 65 SetObjectAt(idx, key); |
46 SetValueAt(idx, val); | 66 SetValueAt(idx, val); |
47 // Update the counts. | 67 // Update the counts. |
48 set_used(used() + 1); | 68 set_used(used() + 1); |
49 set_count(count() + 1); | 69 set_count(count() + 1); |
50 | 70 |
51 // Rehash if needed to ensure that there are empty slots available. | 71 // Rehash if needed to ensure that there are empty slots available. |
52 if (used_ >= limit()) { | 72 if (used_ >= limit()) { |
53 return Rehash(); | 73 Rehash(); |
54 } | 74 } |
55 return this; | |
56 } | 75 } |
57 | 76 |
58 | 77 |
59 WeakTable* WeakTable::Rehash() { | 78 void WeakTable::Rehash() { |
60 intptr_t sz = size(); | 79 intptr_t old_size = size(); |
61 WeakTable* result = NewFrom(this); | 80 intptr_t* old_data = data_; |
62 | 81 |
63 for (intptr_t i = 0; i < sz; i++) { | 82 intptr_t new_size = SizeFor(count(), size()); |
| 83 ASSERT(Utils::IsPowerOfTwo(new_size)); |
| 84 intptr_t* new_data = reinterpret_cast<intptr_t*>( |
| 85 calloc(new_size, kEntrySize * kWordSize)); |
| 86 |
| 87 intptr_t mask = new_size - 1; |
| 88 set_used(0); |
| 89 for (intptr_t i = 0; i < old_size; i++) { |
64 if (IsValidEntryAt(i)) { | 90 if (IsValidEntryAt(i)) { |
65 WeakTable* temp = result->SetValue(ObjectAt(i), ValueAt(i)); | 91 // Find the new hash location for this entry. |
66 ASSERT(temp == result); | 92 RawObject* key = ObjectAt(i); |
| 93 intptr_t idx = Hash(key) & mask; |
| 94 RawObject* obj = reinterpret_cast<RawObject*>(new_data[ObjectIndex(idx)]); |
| 95 while (obj != NULL) { |
| 96 ASSERT(obj != key); // Duplicate entry is not expected. |
| 97 idx = (idx + 1) & mask; |
| 98 obj = reinterpret_cast<RawObject*>(new_data[ObjectIndex(idx)]); |
| 99 } |
| 100 |
| 101 new_data[ObjectIndex(idx)] = reinterpret_cast<intptr_t>(key); |
| 102 new_data[ValueIndex(idx)] = ValueAt(i); |
| 103 set_used(used() + 1); |
67 } | 104 } |
68 } | 105 } |
69 return result; | 106 // We should only have used valid entries. |
| 107 ASSERT(used() == count()); |
| 108 |
| 109 // Switch to using the newly allocated backing store. |
| 110 size_ = new_size; |
| 111 data_ = new_data; |
| 112 free(old_data); |
70 } | 113 } |
71 | 114 |
72 } // namespace dart | 115 } // namespace dart |
OLD | NEW |