Lines Matching refs:Entry
15 #include "src/base/hashmap-entry.h"
30 typedef TemplateHashMapEntry<Key, Value> Entry;
50 // If an entry with matching key is found, returns that entry.
52 Entry* Lookup(const Key& key, uint32_t hash) const;
54 // If an entry with matching key is found, returns that entry.
55 // If no matching entry is found, a new entry is inserted with
57 Entry* LookupOrInsert(const Key& key, uint32_t hash,
60 // If an entry with matching key is found, returns that entry.
61 // If no matching entry is found, a new entry is inserted with
64 Entry* LookupOrInsert(const Key& key, uint32_t hash, const Func& value_func,
67 Entry* InsertNew(const Key& key, uint32_t hash,
70 // Removes the entry with matching key.
71 // It returns the value of the deleted entry
96 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) {
102 Entry* Start() const;
103 Entry* Next(Entry* entry) const;
114 Entry* map_;
121 Entry* map_end() const { return map_ + capacity_; }
122 Entry* Probe(const Key& key, uint32_t hash) const;
123 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value,
148 map_ = reinterpret_cast<Entry*>(allocator.New(capacity_ * sizeof(Entry)));
149 memcpy(map_, original->map_, capacity_ * sizeof(Entry));
161 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
164 Entry* entry = Probe(key, hash);
165 return entry->exists() ? entry : nullptr;
170 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
179 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
183 // Find a matching entry.
184 Entry* entry = Probe(key, hash);
185 if (entry->exists()) {
186 return entry;
189 return FillEmptyEntry(entry, key, value_func(), hash, allocator);
194 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
197 Entry* entry = Probe(key, hash);
198 return FillEmptyEntry(entry, key, Value(), hash, allocator);
205 // Lookup the entry for the key to remove.
206 Entry* p = Probe(key, hash);
213 // To remove an entry we need to ensure that it does not create an empty
214 // entry that will cause the search for another entry to stop too soon. If all
215 // the entries between the entry to remove and the next empty slot have their
216 // initial position inside this interval, clearing the entry to remove will
217 // not break the search. If, while searching for the next empty entry, an
218 // entry is encountered which does not have its initial position between the
219 // entry to remove and the position looked at, then this entry can be moved to
220 // the place of the entry to remove without breaking the search for it. The
221 // entry made vacant by this move is now the entry to remove and the process
225 // This guarantees loop termination as there is at least one empty entry so
226 // eventually the removed entry will have an empty entry after it.
229 // p is the candidate entry to clear. q is used to scan forwards.
230 Entry* q = p; // Start at the entry to remove.
232 // Move q to the next entry.
239 // and the entry p can be cleared without breaking the search for these
245 // Find the initial position for the entry at position q.
246 Entry* r = map_ + (q->hash & (capacity_ - 1));
248 // If the entry at position q has its initial position outside the range
250 // found. There is now a new candidate entry for clearing.
257 // Clear the entry which is allowed to en emptied.
275 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
282 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
284 Entry* entry) const {
285 const Entry* end = map_end();
286 DCHECK(map_ - 1 <= entry && entry < end);
287 for (entry++; entry < end; entry++) {
288 if (entry->exists()) {
289 return entry;
297 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
314 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
316 Entry* entry, const Key& key, const Value& value, uint32_t hash,
318 DCHECK(!entry->exists());
320 new (entry) Entry(key, value, hash);
326 entry = Probe(key, hash);
329 return entry;
337 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
350 Entry* map = map_;
357 for (Entry* entry = map; n > 0; entry++) {
358 if (entry->exists()) {
359 Entry* new_entry = Probe(entry->key, entry->hash);
360 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value,
361 entry->hash, allocator);
474 Iterator(const Base* map, typename Base::Entry* entry)
475 : map_(map), entry_(entry) {}
478 typename Base::Entry* entry_;
