OLD | NEW |
1 // Copyright 2008 the V8 project authors. All rights reserved. | 1 // Copyright 2008 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 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
85 | 85 |
86 | 86 |
87 void HashMap::Remove(void* key, uint32_t hash) { | 87 void HashMap::Remove(void* key, uint32_t hash) { |
88 // Lookup the entry for the key to remove. | 88 // Lookup the entry for the key to remove. |
89 Entry *p = Probe(key, hash); | 89 Entry *p = Probe(key, hash); |
90 if (p->key == NULL) { | 90 if (p->key == NULL) { |
91 // Key not found nothing to remove. | 91 // Key not found nothing to remove. |
92 return; | 92 return; |
93 } | 93 } |
94 | 94 |
95 // To remove the entry we need to ensure that it does not create an empty | 95 // To remove an entry we need to ensure that it does not create an empty |
96 // entry that will cause search for an entry to stop to soon. If all the | 96 // entry that will cause the search for another entry to stop too soon. If all |
97 // entries between the entry to remove and the next empty slot have their | 97 // the entries between the entry to remove and the next empty slot have their |
98 // initial position inside this interval clearing the entry to remove will not | 98 // initial position inside this interval, clearing the entry to remove will |
99 // break the search. If while searching for the next empty entry an entry is | 99 // not break the search. If, while searching for the next empty entry, an |
100 // encountered which does not have its initial position between the entry to | 100 // entry is encountered which does not have its initial position between the |
101 // remove and the position looked at this entry can be moved to the place of | 101 // entry to remove and the position looked at, then this entry can be moved to |
102 // the entry to remove without breaking the search for it and the new entry to | 102 // the place of the entry to remove without breaking the search for it. The |
103 // remove will be its previous position. | 103 // entry made vacant by this move is now the entry to remove and the process |
| 104 // starts over. |
104 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. | 105 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. |
105 | 106 |
106 // This guarantees loop termination as there is at least one empty entry so | 107 // This guarantees loop termination as there is at least one empty entry so |
107 // eventually the removed entyr will have an empty entry after it. | 108 // eventually the removed entry will have an empty entry after it. |
108 ASSERT(occupancy_ < capacity_); | 109 ASSERT(occupancy_ < capacity_); |
109 | 110 |
110 // p is the candidate entry to clear. q is used to scan forwards. | 111 // p is the candidate entry to clear. q is used to scan forwards. |
111 Entry* q = p; // Start at the entry to remove. | 112 Entry* q = p; // Start at the entry to remove. |
112 while (true) { | 113 while (true) { |
113 // Move q to the next entry. | 114 // Move q to the next entry. |
114 q = q + 1; | 115 q = q + 1; |
115 if (q == map_end()) { | 116 if (q == map_end()) { |
116 q = map_; | 117 q = map_; |
117 } | 118 } |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
212 n--; | 213 n--; |
213 } | 214 } |
214 } | 215 } |
215 | 216 |
216 // Delete old map. | 217 // Delete old map. |
217 allocator_->Delete(map); | 218 allocator_->Delete(map); |
218 } | 219 } |
219 | 220 |
220 | 221 |
221 } } // namespace v8::internal | 222 } } // namespace v8::internal |
OLD | NEW |