| 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 |