Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(11)

Side by Side Diff: src/hashmap.cc

Issue 113449: Fix spelling errors in comment and rephrased it somewhat (Closed) Base URL: http://v8.googlecode.com/svn/branches/bleeding_edge/
Patch Set: '' Created 11 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698