Lines Matching refs:Entry
37 struct Entry {
44 // If an entry with matching key is found, returns that entry.
46 Entry* Lookup(void* key, uint32_t hash) const;
48 // If an entry with matching key is found, returns that entry.
49 // If no matching entry is found, a new entry is inserted with
51 Entry* LookupOrInsert(void* key, uint32_t hash,
54 // Removes the entry with matching key.
55 // It returns the value of the deleted entry
72 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
78 Entry* Start() const;
79 Entry* Next(Entry* p) const;
88 Entry* map_;
92 Entry* map_end() const { return map_ + capacity_; }
93 Entry* Probe(void* key, uint32_t hash) const;
115 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
117 Entry* p = Probe(key, hash);
123 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
126 // Find a matching entry.
127 Entry* p = Probe(key, hash);
132 // No entry found; insert one.
151 // Lookup the entry for the key to remove.
152 Entry* p = Probe(key, hash);
159 // To remove an entry we need to ensure that it does not create an empty
160 // entry that will cause the search for another entry to stop too soon. If all
161 // the entries between the entry to remove and the next empty slot have their
162 // initial position inside this interval, clearing the entry to remove will
163 // not break the search. If, while searching for the next empty entry, an
164 // entry is encountered which does not have its initial position between the
165 // entry to remove and the position looked at, then this entry can be moved to
166 // the place of the entry to remove without breaking the search for it. The
167 // entry made vacant by this move is now the entry to remove and the process
171 // This guarantees loop termination as there is at least one empty entry so
172 // eventually the removed entry will have an empty entry after it.
175 // p is the candidate entry to clear. q is used to scan forwards.
176 Entry* q = p; // Start at the entry to remove.
178 // Move q to the next entry.
185 // and the entry p can be cleared without breaking the search for these
191 // Find the initial position for the entry at position q.
192 Entry* r = map_ + (q->hash & (capacity_ - 1));
194 // If the entry at position q has its initial position outside the range
196 // found. There is now a new candidate entry for clearing.
204 // Clear the entry which is allowed to en emptied.
214 const Entry* end = map_end();
215 for (Entry* p = map_; p < end; p++) {
223 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
230 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
231 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const {
232 const Entry* end = map_end();
244 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
249 Entry* p = map_ + (hash & (capacity_ - 1));
250 const Entry* end = map_end();
269 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
281 Entry* map = map_;
288 for (Entry* p = map; n > 0; p++) {
290 Entry* entry = LookupOrInsert(p->key, p->hash, allocator);
291 entry->value = p->value;
292 entry->order = p->order;
325 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) :
326 map_(map), entry_(entry) { }
329 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_;
