18cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/** 28cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @file unique_storage.h 38cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Unique storage of values 48cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 58cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Copyright 2002 OProfile authors 68cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Read the file COPYING 78cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 88cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @author Philippe Elie 98cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @author John Levon 108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#ifndef UNIQUE_STORAGE_H 138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#define UNIQUE_STORAGE_H 148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <vector> 168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <map> 178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <stdexcept> 188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/** 208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Store values such that only one copy of the value 218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * is ever stored. 228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * I is an arbitrary typename that's never 248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * used. 258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * It is a required parameter in order to enforce 278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * type-safety for a collection. 288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * The value type "V" must be default-constructible, 308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * and this is the value returned by a stored id_value 318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * where .set() is false 328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddtemplate <typename I, typename V> class unique_storage { 348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddpublic: 368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unique_storage() { 378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // id 0 388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd values.push_back(V()); 398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd virtual ~unique_storage() {} 428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef std::vector<V> stored_values; 448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// the actual ID type 468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct id_value { 478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// id == 0 means "empty" / "undefined" 488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd id_value() : id(0) {} 498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// does this ID map to a non-default value ? 518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd bool set() const { 528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return id; 538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd bool operator<(id_value const & rhs) const { 568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return id < rhs.id; 578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd bool operator==(id_value const & rhs) const { 608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return id == rhs.id; 618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd bool operator!=(id_value const & rhs) const { 648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return !(id == rhs.id); 658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd private: 688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd friend class unique_storage<I, V>; 698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef typename stored_values::size_type size_type; 718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd explicit id_value(size_type s) : id(s) {} 738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// actual ID value 758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd size_type id; 768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd }; 778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// ensure this value is available 808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd id_value const create(V const & value) { 818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename id_map::value_type val(value, id_value(values.size())); 828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd std::pair<typename id_map::iterator, bool> 838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd inserted = ids.insert(val); 848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (inserted.second) 858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd values.push_back(value); 868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return inserted.first->second; 888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// return the stored value for the given ID 928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd V const & get(id_value const & id) const { 938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // some stl lack at(), so we emulate it 948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (id.id < values.size()) 958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return values[id.id]; 968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd throw std::out_of_range("unique_storage::get(): out of bounds"); 988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddprivate: 1018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef std::map<V, id_value> id_map; 1028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// the contained values 1048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd stored_values values; 1058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// map from ID to value 1078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd id_map ids; 1088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd}; 1098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#endif /* !UNIQUE_STORAGE_H */ 111