libutil++/unique_storage.h

   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  */
  33 template <typename I, typename V> class unique_storage {
  34
  35 public:
  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
 100 private:
 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 */