ceph/src/boost/boost/signals2/detail/slot_groups.hpp

   1 // Boost.Signals2 library
   2
   3 // Copyright Frank Mori Hess 2007-2008.
   4 // Use, modification and
   5 // distribution is subject to the Boost Software License, Version
   6 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 // For more information, see http://www.boost.org
  10
  11 #ifndef BOOST_SIGNALS2_SLOT_GROUPS_HPP
  12 #define BOOST_SIGNALS2_SLOT_GROUPS_HPP
  13
  14 #include <boost/signals2/connection.hpp>
  15 #include <boost/optional.hpp>
  16 #include <list>
  17 #include <map>
  18 #include <utility>
  19
  20 namespace boost {
  21   namespace signals2 {
  22     namespace detail {
  23       enum slot_meta_group {front_ungrouped_slots, grouped_slots, back_ungrouped_slots};
  24       template<typename Group>
  25       struct group_key
  26       {
  27         typedef std::pair<enum slot_meta_group, boost::optional<Group> > type;
  28       };
  29       template<typename Group, typename GroupCompare>
  30       class group_key_less
  31       {
  32       public:
  33         group_key_less()
  34         {}
  35         group_key_less(const GroupCompare &group_compare): _group_compare(group_compare)
  36         {}
  37         bool operator ()(const typename group_key<Group>::type &key1, const typename group_key<Group>::type &key2) const
  38         {
  39           if(key1.first != key2.first) return key1.first < key2.first;
  40           if(key1.first != grouped_slots) return false;
  41           return _group_compare(key1.second.get(), key2.second.get());
  42         }
  43       private:
  44         GroupCompare _group_compare;
  45       };
  46       template<typename Group, typename GroupCompare, typename ValueType>
  47       class grouped_list
  48       {
  49       public:
  50         typedef group_key_less<Group, GroupCompare> group_key_compare_type;
  51       private:
  52         typedef std::list<ValueType> list_type;
  53         typedef std::map
  54           <
  55             typename group_key<Group>::type,
  56             typename list_type::iterator,
  57             group_key_compare_type
  58           > map_type;
  59         typedef typename map_type::iterator map_iterator;
  60         typedef typename map_type::const_iterator const_map_iterator;
  61       public:
  62         typedef typename list_type::iterator iterator;
  63         typedef typename list_type::const_iterator const_iterator;
  64         typedef typename group_key<Group>::type group_key_type;
  65
  66         grouped_list(const group_key_compare_type &group_key_compare):
  67           _group_key_compare(group_key_compare)
  68         {}
  69         grouped_list(const grouped_list &other): _list(other._list),
  70           _group_map(other._group_map), _group_key_compare(other._group_key_compare)
  71         {
  72           // fix up _group_map
  73           typename map_type::const_iterator other_map_it;
  74           typename list_type::iterator this_list_it = _list.begin();
  75           typename map_type::iterator this_map_it = _group_map.begin();
  76           for(other_map_it = other._group_map.begin();
  77             other_map_it != other._group_map.end();
  78             ++other_map_it, ++this_map_it)
  79           {
  80             BOOST_ASSERT(this_map_it != _group_map.end());
  81             this_map_it->second = this_list_it;
  82             typename list_type::const_iterator other_list_it = other.get_list_iterator(other_map_it);
  83             typename map_type::const_iterator other_next_map_it = other_map_it;
  84             ++other_next_map_it;
  85             typename list_type::const_iterator other_next_list_it = other.get_list_iterator(other_next_map_it);
  86             while(other_list_it != other_next_list_it)
  87             {
  88               ++other_list_it;
  89               ++this_list_it;
  90             }
  91           }
  92         }
  93         iterator begin()
  94         {
  95           return _list.begin();
  96         }
  97         iterator end()
  98         {
  99           return _list.end();
 100         }
 101         iterator lower_bound(const group_key_type &key)
 102         {
 103           map_iterator map_it = _group_map.lower_bound(key);
 104           return get_list_iterator(map_it);
 105         }
 106         iterator upper_bound(const group_key_type &key)
 107         {
 108           map_iterator map_it = _group_map.upper_bound(key);
 109           return get_list_iterator(map_it);
 110         }
 111         void push_front(const group_key_type &key, const ValueType &value)
 112         {
 113           map_iterator map_it;
 114           if(key.first == front_ungrouped_slots)
 115           {// optimization
 116             map_it = _group_map.begin();
 117           }else
 118           {
 119             map_it = _group_map.lower_bound(key);
 120           }
 121           m_insert(map_it, key, value);
 122         }
 123         void push_back(const group_key_type &key, const ValueType &value)
 124         {
 125           map_iterator map_it;
 126           if(key.first == back_ungrouped_slots)
 127           {// optimization
 128             map_it = _group_map.end();
 129           }else
 130           {
 131             map_it = _group_map.upper_bound(key);
 132           }
 133           m_insert(map_it, key, value);
 134         }
 135         void erase(const group_key_type &key)
 136         {
 137           map_iterator map_it = _group_map.lower_bound(key);
 138           iterator begin_list_it = get_list_iterator(map_it);
 139           iterator end_list_it = upper_bound(key);
 140           if(begin_list_it != end_list_it)
 141           {
 142             _list.erase(begin_list_it, end_list_it);
 143             _group_map.erase(map_it);
 144           }
 145         }
 146         iterator erase(const group_key_type &key, const iterator &it)
 147         {
 148           BOOST_ASSERT(it != _list.end());
 149           map_iterator map_it = _group_map.lower_bound(key);
 150           BOOST_ASSERT(map_it != _group_map.end());
 151           BOOST_ASSERT(weakly_equivalent(map_it->first, key));
 152           if(map_it->second == it)
 153           {
 154             iterator next = it;
 155             ++next;
 156             // if next is in same group
 157             if(next != upper_bound(key))
 158             {
 159               _group_map[key] = next;
 160             }else
 161             {
 162               _group_map.erase(map_it);
 163             }
 164           }
 165           return _list.erase(it);
 166         }
 167         void clear()
 168         {
 169           _list.clear();
 170           _group_map.clear();
 171         }
 172       private:
 173         /* Suppress default assignment operator, since it has the wrong semantics. */
 174         grouped_list& operator=(const grouped_list &other);
 175
 176         bool weakly_equivalent(const group_key_type &arg1, const group_key_type &arg2)
 177         {
 178           if(_group_key_compare(arg1, arg2)) return false;
 179           if(_group_key_compare(arg2, arg1)) return false;
 180           return true;
 181         }
 182         void m_insert(const map_iterator &map_it, const group_key_type &key, const ValueType &value)
 183         {
 184           iterator list_it = get_list_iterator(map_it);
 185           iterator new_it = _list.insert(list_it, value);
 186           if(map_it != _group_map.end() && weakly_equivalent(key, map_it->first))
 187           {
 188             _group_map.erase(map_it);
 189           }
 190           map_iterator lower_bound_it = _group_map.lower_bound(key);
 191           if(lower_bound_it == _group_map.end() ||
 192             weakly_equivalent(lower_bound_it->first, key) == false)
 193           {
 194             /* doing the following instead of just
 195               _group_map[key] = new_it;
 196               to avoid bogus error when enabling checked iterators with g++ */
 197             _group_map.insert(typename map_type::value_type(key, new_it));
 198           }
 199         }
 200         iterator get_list_iterator(const const_map_iterator &map_it)
 201         {
 202           iterator list_it;
 203           if(map_it == _group_map.end())
 204           {
 205             list_it = _list.end();
 206           }else
 207           {
 208             list_it = map_it->second;
 209           }
 210           return list_it;
 211         }
 212         const_iterator get_list_iterator(const const_map_iterator &map_it) const
 213         {
 214           const_iterator list_it;
 215           if(map_it == _group_map.end())
 216           {
 217             list_it = _list.end();
 218           }else
 219           {
 220             list_it = map_it->second;
 221           }
 222           return list_it;
 223         }
 224
 225         list_type _list;
 226         // holds iterators to first list item in each group
 227         map_type _group_map;
 228         group_key_compare_type _group_key_compare;
 229       };
 230     } // end namespace detail
 231     enum connect_position { at_back, at_front };
 232   } // end namespace signals2
 233 } // end namespace boost
 234
 235 #endif // BOOST_SIGNALS2_SLOT_GROUPS_HPP