1/**
2 * @file unique_storage.h
3 * Unique storage of values
4 *
5 * @remark Copyright 2002 OProfile authors
6 * @remark Read the file COPYING
7 *
8 * @author Philippe Elie
9 * @author John Levon
10 */
11
12#ifndef UNIQUE_STORAGE_H
13#define UNIQUE_STORAGE_H
14
15#include <vector>
16#include <map>
17#include <stdexcept>
18
19/**
20 * Store values such that only one copy of the value
21 * is ever stored.
22 *
23 * I is an arbitrary typename that's never
24 * used.
25 *
26 * It is a required parameter in order to enforce
27 * type-safety for a collection.
28 *
29 * The value type "V" must be default-constructible,
30 * and this is the value returned by a stored id_value
31 * where .set() is false
32 */
33template <typename I, typename V> class unique_storage {
34
35public:
36	unique_storage() {
37		// id 0
38		values.push_back(V());
39	}
40
41	virtual ~unique_storage() {}
42
43	typedef std::vector<V> stored_values;
44
45	/// the actual ID type
46	struct id_value {
47		/// id == 0 means "empty" / "undefined"
48		id_value() : id(0) {}
49
50		/// does this ID map to a non-default value ?
51		bool set() const {
52			return id;
53		}
54
55		bool operator<(id_value const & rhs) const {
56			return id < rhs.id;
57		}
58
59		bool operator==(id_value const & rhs) const {
60			return id == rhs.id;
61		}
62
63		bool operator!=(id_value const & rhs) const {
64			return !(id == rhs.id);
65		}
66
67	private:
68		friend class unique_storage<I, V>;
69
70		typedef typename stored_values::size_type size_type;
71
72		explicit id_value(size_type s) : id(s) {}
73
74		/// actual ID value
75		size_type id;
76	};
77
78
79	/// ensure this value is available
80	id_value const create(V const & value) {
81		typename id_map::value_type val(value, id_value(values.size()));
82		std::pair<typename id_map::iterator, bool>
83			inserted = ids.insert(val);
84		if (inserted.second)
85			values.push_back(value);
86
87		return inserted.first->second;
88	}
89
90
91	/// return the stored value for the given ID
92	V const & get(id_value const & id) const {
93		// some stl lack at(), so we emulate it
94		if (id.id < values.size())
95			return values[id.id];
96
97		throw std::out_of_range("unique_storage::get(): out of bounds");
98	}
99
100private:
101	typedef std::map<V, id_value> id_map;
102
103	/// the contained values
104	stored_values values;
105
106	/// map from ID to value
107	id_map ids;
108};
109
110#endif /* !UNIQUE_STORAGE_H */
111