15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef BASE_ID_MAP_H_ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BASE_ID_MAP_H_ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 117d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#include "base/containers/hash_tables.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/threading/non_thread_safe.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Ownership semantics - own pointer means the pointer is deleted in Remove() 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// & during destruction 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)enum IDMapOwnershipSemantics { 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IDMapExternalPointer, 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IDMapOwnPointer 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This object maintains a list of IDs that can be quickly converted to 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pointers to objects. It is implemented as a hash table, optimized for 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// relatively small data sets (in the common case, there will be exactly one 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// item in the list). 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Items can be inserted into the container with arbitrary ID, but the caller 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// must ensure they are unique. Inserting IDs and relying on automatically 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// generated ones is not allowed because they can collide. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class does not have a virtual destructor, do not inherit from it when 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ownership semantics are set to own because pointers will leak. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename T, IDMapOwnershipSemantics OS = IDMapExternalPointer> 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class IDMap : public base::NonThreadSafe { 35cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) public: 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef int32 KeyType; 37cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 38cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) private: 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef base::hash_map<KeyType, T*> HashTable; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) { 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // A number of consumers of IDMap create it on one thread but always access 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it from a different, but consitent, thread post-construction. 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DetachFromThread(); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~IDMap() { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Many IDMap's are static, and hence will be destroyed on the main thread. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // However, all the accesses may take place on another thread, such as the 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // IO thread. Detaching again to clean this up. 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DetachFromThread(); 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Releaser<OS, 0>::release_all(&data_); 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets whether Add should CHECK if passed in NULL data. Default is false. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void set_check_on_null_data(bool value) { check_on_null_data_ = value; } 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds a view with an automatically generated unique ID. See AddWithID. 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KeyType Add(T* data) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(!check_on_null_data_ || data); 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KeyType this_id = next_id_; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item"; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data_[this_id] = data; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_id_++; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this_id; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds a new data member with the specified ID. The ID must not be in 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the list. The caller either must generate all unique IDs itself and use 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this function, or allow this object to generate IDs and call Add. These 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // two methods may not be mixed, or duplicate IDs may be generated 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void AddWithID(T* data, KeyType id) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(!check_on_null_data_ || data); 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item"; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data_[id] = data; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Remove(KeyType id) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename HashTable::iterator i = data_.find(id); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i == data_.end()) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NOTREACHED() << "Attempting to remove an item not in the list"; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (iteration_depth_ == 0) { 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Releaser<OS, 0>::release(i->second); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data_.erase(i); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) removed_ids_.insert(id); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Clear() { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (iteration_depth_ == 0) { 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Releaser<OS, 0>::release_all(&data_); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (typename HashTable::iterator i = data_.begin(); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i != data_.end(); ++i) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) removed_ids_.insert(i->first); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsEmpty() const { 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return size() == 0u; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) T* Lookup(KeyType id) const { 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename HashTable::const_iterator i = data_.find(id); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i == data_.end()) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return i->second; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t size() const { 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return data_.size() - removed_ids_.size(); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(UNIT_TEST) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iteration_depth() const { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iteration_depth_; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // defined(UNIT_TEST) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // It is safe to remove elements from the map during iteration. All iterators 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will remain valid. 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<class ReturnType> 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class Iterator { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Iterator(IDMap<T, OS>* map) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : map_(map), 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iter_(map_->data_.begin()) { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Init(); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Iterator(const Iterator& iter) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : map_(iter.map_), 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iter_(iter.iter_) { 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Init(); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Iterator& operator=(const Iterator& iter) { 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_ = iter.map; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iter_ = iter.iter; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Init(); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return *this; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~Iterator() { 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(map_->CalledOnValidThread()); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We're going to decrement iteration depth. Make sure it's greater than 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // zero so that it doesn't become negative. 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(0, map_->iteration_depth_); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (--map_->iteration_depth_ == 0) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_->Compact(); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsAtEnd() const { 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(map_->CalledOnValidThread()); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iter_ == map_->data_.end(); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KeyType GetCurrentKey() const { 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(map_->CalledOnValidThread()); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iter_->first; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReturnType* GetCurrentValue() const { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(map_->CalledOnValidThread()); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iter_->second; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Advance() { 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(map_->CalledOnValidThread()); 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++iter_; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkipRemovedEntries(); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Init() { 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(map_->CalledOnValidThread()); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++map_->iteration_depth_; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkipRemovedEntries(); 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SkipRemovedEntries() { 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (iter_ != map_->data_.end() && 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_->removed_ids_.find(iter_->first) != 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_->removed_ids_.end()) { 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++iter_; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IDMap<T, OS>* map_; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename HashTable::const_iterator iter_; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Iterator<T> iterator; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Iterator<const T> const_iterator; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The dummy parameter is there because C++ standard does not allow 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // explicitly specialized templates inside classes 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<IDMapOwnershipSemantics OI, int dummy> struct Releaser { 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline void release(T* ptr) {} 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline void release_all(HashTable* table) {} 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<int dummy> struct Releaser<IDMapOwnPointer, dummy> { 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline void release(T* ptr) { delete ptr;} 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline void release_all(HashTable* table) { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (typename HashTable::iterator i = table->begin(); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i != table->end(); ++i) { 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete i->second; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) table->clear(); 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Compact() { 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(0, iteration_depth_); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::set<KeyType>::const_iterator i = removed_ids_.begin(); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i != removed_ids_.end(); ++i) { 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Remove(*i); 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) removed_ids_.clear(); 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Keep track of how many iterators are currently iterating on us to safely 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // handle removing items during iteration. 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iteration_depth_; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Keep set of IDs that should be removed after the outermost iteration has 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // finished. This way we manage to not invalidate the iterator when an element 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is removed. 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<KeyType> removed_ids_; 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The next ID that we will return from Add() 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KeyType next_id_; 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashTable data_; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See description above setter. 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool check_on_null_data_; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(IDMap); 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // BASE_ID_MAP_H_ 260