← Back to branch summary

~ubuntu-branches/ubuntu/vivid/aptitude/vivid

« back to all changes in this revision

Viewing changes to .pc/0001-Fix-build-with-g-4.7.patch/src/generic/util/dynamic_list_collection.h

  • Committer: Package Import Robot
  • Author(s): Dmitrijs Ledkovs
  • Date: 2012-06-29 01:48:31 UTC
  • Revision ID: package-import@ubuntu.com-20120629014831-7yxujv9gswyo2hac
Tags: 0.6.6-1ubuntu2
https://launchpad.net/bugs/1007969
Fix FTBFS with gcc-4.7 (LP: #1007969)

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/0001-Fix-build-with-g-4.7.patch/src/generic/util/dynamic_list_collection.h
 
1
/** \file dynamic_list_collection.h */ // -*-c++-*-
 
2
 
 
3
// Copyright (C) 2010 Daniel Burrows
 
4
//
 
5
// This program is free software; you can redistribute it and/or
 
6
// modify it under the terms of the GNU General Public License as
 
7
// published by the Free Software Foundation; either version 2 of the
 
8
// License, or (at your option) any later version.
 
9
//
 
10
// This program is distributed in the hope that it will be useful, but
 
11
// WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
// General Public License for more details.
 
14
//
 
15
// You should have received a copy of the GNU General Public License
 
16
// along with this program; see the file COPYING.  If not, write to
 
17
// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 
18
// Boston, MA 02111-1307, USA.
 
19
 
 
20
#ifndef DYNAMIC_LIST_COLLECTION_H
 
21
#define DYNAMIC_LIST_COLLECTION_H
 
22
 
 
23
#include "dynamic_list.h"
 
24
#include "dynamic_list_impl.h"
 
25
 
 
26
#include <boost/functional/hash.hpp>
 
27
#include <boost/make_shared.hpp>
 
28
#include <boost/multi_index_container.hpp>
 
29
#include <boost/multi_index/hashed_index.hpp>
 
30
#include <boost/multi_index/member.hpp>
 
31
#include <boost/multi_index/mem_fun.hpp>
 
32
#include <boost/multi_index/random_access_index.hpp>
 
33
#include <boost/shared_ptr.hpp>
 
34
#include <boost/unordered_map.hpp>
 
35
 
 
36
#include <cwidget/generic/util/eassert.h>
 
37
 
 
38
#include <sigc++/bind.h>
 
39
#include <sigc++/connection.h>
 
40
 
 
41
namespace aptitude
 
42
{
 
43
  namespace util
 
44
  {
 
45
    /** \brief Assembles multiple dynamic lists into a single dynamic list.
 
46
     *
 
47
     *  The elements of any single list are placed in order, but the
 
48
     *  elements from different lists are interleaved according to the
 
49
     *  order in which they were appended.  If an element occurs in
 
50
     *  two separate lists, it will be added to this list twice.
 
51
     */
 
52
    template<typename T>
 
53
    class dynamic_list_collection : public dynamic_list<T>
 
54
    {
 
55
      typedef boost::unordered_multimap<boost::shared_ptr<dynamic_list<T> >,
 
56
                                        sigc::connection>
 
57
      sub_list_connections;
 
58
 
 
59
      /** \brief A dual-purpose collection.  It keeps the contained
 
60
       *  lists alive, and holds signal connections that need to be
 
61
       *  deleted when each sub-list is removed.
 
62
       */
 
63
      sub_list_connections connections_by_list;
 
64
 
 
65
      class cell
 
66
      {
 
67
        boost::shared_ptr<dynamic_list<T> > parent_list;
 
68
        std::size_t index_within_parent_list;
 
69
        T value;
 
70
 
 
71
      public:
 
72
        cell(const boost::shared_ptr<dynamic_list<T> > &_parent_list,
 
73
             std::size_t _index_within_parent_list,
 
74
             const T &_value);
 
75
 
 
76
        const boost::shared_ptr<dynamic_list<T> > &get_parent_list() const
 
77
        {
 
78
          return parent_list;
 
79
        }
 
80
 
 
81
        std::size_t get_index_within_parent_list() const
 
82
        {
 
83
          return index_within_parent_list;
 
84
        }
 
85
 
 
86
        const T &get_value() const { return value; }
 
87
 
 
88
        bool operator==(const cell &other) const
 
89
        {
 
90
          return
 
91
            parent_list == other.parent_list &&
 
92
            index_within_parent_list == other.index_within_parent_list &&
 
93
            value == other.value;
 
94
        }
 
95
 
 
96
        std::size_t hash() const
 
97
        {
 
98
          std::size_t rval = 1836;
 
99
          boost::hash_combine(rval, parent_list);
 
100
          boost::hash_combine(rval, index_within_parent_list);
 
101
          boost::hash_combine(rval, value);
 
102
 
 
103
          return rval;
 
104
        }
 
105
      };
 
106
 
 
107
      // The cells are stored in a multi-indexed container.
 
108
      //
 
109
      // The indices are:
 
110
      //   concrete_view  -> the cells in the order that they appear to
 
111
      //                     clients.
 
112
      //   by_parent_list -> the cells grouped by their parent list.
 
113
 
 
114
      class concrete_view_tag;
 
115
      class by_parent_list_tag;
 
116
 
 
117
      typedef boost::multi_index_container<
 
118
        cell,
 
119
        boost::multi_index::indexed_by<
 
120
          boost::multi_index::random_access<boost::multi_index::tag<concrete_view_tag> >,
 
121
          boost::multi_index::hashed_non_unique<
 
122
            boost::multi_index::tag<by_parent_list_tag>,
 
123
            boost::multi_index::const_mem_fun<cell,
 
124
                                              const boost::shared_ptr<dynamic_list<T> > &,
 
125
                                              &cell::get_parent_list> > > >
 
126
      cells_collection;
 
127
 
 
128
      typedef typename cells_collection::template index<concrete_view_tag>::type concrete_view_index;
 
129
      typedef typename cells_collection::template index<by_parent_list_tag>::type by_parent_list_index;
 
130
 
 
131
      cells_collection cells;
 
132
 
 
133
      void handle_insert(const T &value, std::size_t idx,
 
134
                         const boost::shared_ptr<dynamic_list<T> > &list);
 
135
      void handle_remove(const T &value, std::size_t idx,
 
136
                         const boost::shared_ptr<dynamic_list<T> > &list);
 
137
      void handle_move(const T &value, std::size_t from, std::size_t to,
 
138
                       const boost::shared_ptr<dynamic_list<T> > &list);
 
139
 
 
140
    public:
 
141
      // Only public for make_shared.
 
142
      dynamic_list_collection();
 
143
 
 
144
      std::size_t size();
 
145
      T get_at(std::size_t idx);
 
146
 
 
147
      void add_list(const boost::shared_ptr<dynamic_list<T> > &lst);
 
148
      void remove_list(const boost::shared_ptr<dynamic_list<T> > &lst);
 
149
 
 
150
      static boost::shared_ptr<dynamic_list_collection> create();
 
151
    };
 
152
 
 
153
    template<typename T>
 
154
    dynamic_list_collection<T>::cell::cell(const boost::shared_ptr<dynamic_list<T> > &_parent_list,
 
155
                                           std::size_t _index_within_parent_list,
 
156
                                           const T &_value)
 
157
      : parent_list(_parent_list),
 
158
        index_within_parent_list(_index_within_parent_list),
 
159
        value(_value)
 
160
    {
 
161
    }
 
162
 
 
163
    template<typename T>
 
164
    dynamic_list_collection<T>::dynamic_list_collection()
 
165
      : cells()
 
166
    {
 
167
    }
 
168
 
 
169
    template<typename T>
 
170
    boost::shared_ptr<dynamic_list_collection<T> >
 
171
    dynamic_list_collection<T>::create()
 
172
    {
 
173
      return boost::make_shared<dynamic_list_collection>();
 
174
    }
 
175
 
 
176
    template<typename T>
 
177
    std::size_t dynamic_list_collection<T>::size()
 
178
    {
 
179
      return cells.size();
 
180
    }
 
181
 
 
182
    template<typename T>
 
183
    T dynamic_list_collection<T>::get_at(std::size_t idx)
 
184
    {
 
185
      concrete_view_index &concrete_view = cells.template get<concrete_view_tag>();
 
186
      return concrete_view[idx].get_value();
 
187
    }
 
188
 
 
189
    template<typename T>
 
190
    void dynamic_list_collection<T>::handle_insert(const T &value, std::size_t idx,
 
191
                                                   const boost::shared_ptr<dynamic_list<T> > &list)
 
192
    {
 
193
      concrete_view_index &concrete_view = cells.template get<concrete_view_tag>();
 
194
 
 
195
      // If it was inserted at the end, insert into the end of this
 
196
      // list too.
 
197
      //
 
198
      // If it was inserted at another position, insert into the
 
199
      // corresponding slot in this list.
 
200
 
 
201
 
 
202
      // The procedure:
 
203
      //
 
204
      // 1. Grab the cells belonging to this list.
 
205
      // 2. Increment cell indices to account for the new entry (all
 
206
      //    cells at or above idx will have their within-parent index
 
207
      //    incremented).
 
208
      //    2.a. When we see the element in the target location, save
 
209
      //         its iterator.
 
210
      // 3. Insert at the iterator saved in 2.a.
 
211
      //
 
212
      // Note the reliance on multi_index's iterator stability in 2.a.
 
213
      //
 
214
      // Note that it's step 2 that forces a linear scan -- if we have
 
215
      // to save indices (and we do), then we have to update indices
 
216
      // when an item is dropped.  This could be avoided by passing
 
217
      // opaque cookies around that are unique over the lifetime of a
 
218
      // list to get O(1) operations in all cases...but that's
 
219
      // overengineering for lists that have a few dozen entries, max.
 
220
      // (I write this note in case it becomes justifiable)
 
221
 
 
222
      by_parent_list_index &by_parent_list = cells.template get<by_parent_list_tag>();
 
223
 
 
224
      // 1. Find the parent list's cells.
 
225
      std::pair<
 
226
        typename by_parent_list_index::iterator,
 
227
        typename by_parent_list_index::iterator > parent_range =
 
228
        by_parent_list.equal_range(list);
 
229
 
 
230
      // 2.a. If no insert position exists, insert at end.
 
231
      typename concrete_view_index::const_iterator
 
232
        insert_location = concrete_view.end();
 
233
      for(typename by_parent_list_index::iterator it =
 
234
            parent_range.first; it != parent_range.second; ++it)
 
235
        {
 
236
          const std::size_t it_idx = it->get_index_within_parent_list();
 
237
 
 
238
          // 2.a. Save the insert position.
 
239
          if(it_idx == idx)
 
240
            insert_location = cells.template project<concrete_view_tag>(it);
 
241
 
 
242
          // 2. Update the parent-index of each old cell.
 
243
          //
 
244
          // Note that for the iteration to be correct, I rely on
 
245
          // the multi-index guaranteeing that the element isn't
 
246
          // reordered if its key doesn't change.  Since only the
 
247
          // index changes and that isn't part of the key, we
 
248
          // should be OK.
 
249
          if(it_idx >= idx)
 
250
            by_parent_list.replace(it, cell(it->get_parent_list(),
 
251
                                            it_idx + 1,
 
252
                                            it->get_value()));
 
253
        }
 
254
 
 
255
      const std::size_t insert_idx = insert_location - concrete_view.begin();
 
256
      concrete_view.insert(insert_location, cell(list, idx, value));
 
257
      signal_inserted(value, insert_idx);
 
258
    }
 
259
 
 
260
    template<typename T>
 
261
    void dynamic_list_collection<T>::handle_remove(const T &value, std::size_t idx,
 
262
                                                   const boost::shared_ptr<dynamic_list<T> > &list)
 
263
    {
 
264
      concrete_view_index &concrete_view = cells.template get<concrete_view_tag>();
 
265
 
 
266
      // The procedure:
 
267
      //
 
268
      // 1. Grab the cells belonging to this list.
 
269
      // 2. Decrement cell indices to account for the removed entry (all
 
270
      //    cells above idx will have their within-parent index
 
271
      //    decremented).
 
272
      //    2.a. When we see the element in the target location, save
 
273
      //         that iterator.
 
274
      // 3. Remove the iterator saved in 2.a.
 
275
      //
 
276
      // Note the reliance on multi_index's iterator stability in 2.a.
 
277
 
 
278
      by_parent_list_index &by_parent_list = cells.template get<by_parent_list_tag>();
 
279
 
 
280
      // 1. Find the parent list's cells.
 
281
      std::pair<
 
282
        typename by_parent_list_index::iterator,
 
283
        typename by_parent_list_index::iterator > parent_range =
 
284
        by_parent_list.equal_range(list);
 
285
 
 
286
      // 2.a. Initialize the remove location to an invalid value.
 
287
      typename concrete_view_index::iterator remove_location =
 
288
        concrete_view.end();
 
289
      for(typename by_parent_list_index::iterator it =
 
290
            parent_range.first; it != parent_range.second; ++it)
 
291
        {
 
292
          const std::size_t it_idx = it->get_index_within_parent_list();
 
293
 
 
294
          // 2.a. Save the insert position.
 
295
          if(it_idx == idx)
 
296
            remove_location = cells.template project<concrete_view_tag>(it);
 
297
 
 
298
          // 2. Update the parent-index of each old cell.
 
299
          //
 
300
          // Note that for the iteration to be correct, I rely on
 
301
          // the multi-index guaranteeing that the element isn't
 
302
          // reordered if its key doesn't change.  Since only the
 
303
          // index changes and that isn't part of the key, we
 
304
          // should be OK.
 
305
          if(it_idx > idx)
 
306
            by_parent_list.replace(it, cell(it->get_parent_list(),
 
307
                                            it_idx - 1,
 
308
                                            it->get_value()));
 
309
        }
 
310
 
 
311
      if(remove_location == concrete_view.end())
 
312
        ; // TODO: log an error.
 
313
      else
 
314
        {
 
315
          // 3. Remove the old cell.  Compute the location of the
 
316
          // removal BEFORE removing it!
 
317
          const std::size_t remove_idx = remove_location - concrete_view.begin();
 
318
          concrete_view.erase(remove_location);
 
319
          signal_removed(value, remove_idx);
 
320
        }
 
321
    }
 
322
 
 
323
    template<typename T>
 
324
    void dynamic_list_collection<T>::handle_move(const T &value,
 
325
                                                 std::size_t from, std::size_t to,
 
326
                                                 const boost::shared_ptr<dynamic_list<T> > &list)
 
327
    {
 
328
      if(from == to)
 
329
        return; // TODO: log a warning?  This should not happen.
 
330
 
 
331
      concrete_view_index &concrete_view = cells.template get<concrete_view_tag>();
 
332
 
 
333
      // The procedure:
 
334
      //
 
335
      // 1. Grab the cells belonging to this list.
 
336
      // 2. Adjust cell indices to account for the moved entry (all
 
337
      //    cells between from and to will be either decremented or
 
338
      //    incremented).
 
339
      //    2.a. When we see the elements with indices "from" and "to",
 
340
      //         save their iterators.
 
341
      // 3. Move the iterators saved in 2.a.
 
342
      //
 
343
      // Note the reliance on multi_index's iterator stability in 2.a.
 
344
 
 
345
      by_parent_list_index &by_parent_list = cells.template get<by_parent_list_tag>();
 
346
 
 
347
      // 1. Find the parent list's cells.
 
348
      std::pair<
 
349
        typename by_parent_list_index::iterator,
 
350
        typename by_parent_list_index::iterator > parent_range =
 
351
        by_parent_list.equal_range(list);
 
352
 
 
353
      // 2.a. Prepare locations to store the from and to locations.
 
354
      //      Note that both locations should exist!
 
355
      typename concrete_view_index::iterator
 
356
        from_location = concrete_view.end(),
 
357
        to_location = concrete_view.end();
 
358
      for(typename by_parent_list_index::iterator it =
 
359
            parent_range.first; it != parent_range.second; ++it)
 
360
        {
 
361
          const std::size_t it_idx = it->get_index_within_parent_list();
 
362
 
 
363
          if(it_idx == from)
 
364
            from_location = cells.template project<concrete_view_tag>(it);
 
365
 
 
366
          if(it_idx == to)
 
367
            to_location = cells.template project<concrete_view_tag>(it);
 
368
 
 
369
          // 2. Update the parent-index of each old cell.
 
370
          //
 
371
          // Note that for the iteration to be correct, I rely on
 
372
          // the multi-index guaranteeing that the element isn't
 
373
          // reordered if its key doesn't change.  Since only the
 
374
          // index changes and that isn't part of the key, we
 
375
          // should be OK.
 
376
          //
 
377
          // If the current index is above "from" and less than or
 
378
          // equal to "to", shift left (decrement the index).
 
379
          //
 
380
          // If the current index is below "from" and greater than or
 
381
          // equal to "to", shift right (increment the index).
 
382
          //
 
383
          // If the current index *is* from, set it to "to".
 
384
          if(it_idx == from)
 
385
            by_parent_list.replace(it, cell(it->get_parent_list(),
 
386
                                            to,
 
387
                                            it->get_value()));
 
388
          else if(it_idx > from && it_idx <= to)
 
389
            by_parent_list.replace(it, cell(it->get_parent_list(),
 
390
                                            it_idx - 1,
 
391
                                            it->get_value()));
 
392
          else if(it_idx < from && it_idx >= to)
 
393
            by_parent_list.replace(it, cell(it->get_parent_list(),
 
394
                                            it_idx + 1,
 
395
                                            it->get_value()));
 
396
        }
 
397
 
 
398
      // 3. Move the cell.
 
399
      const std::size_t
 
400
        from_idx = from_location - concrete_view.begin(),
 
401
        to_idx   = to_location - concrete_view.begin();
 
402
 
 
403
      // If we're moving an element to the right, we need to relocate
 
404
      // just past the target, since relocate() inserts the entry
 
405
      // being moved just *before* the target iterator.  If we're
 
406
      // moving to the left, on the other hand, the behavior is
 
407
      // exactly correct.
 
408
      typename concrete_view_index::iterator relocate_target;
 
409
      if(to_idx > from_idx)
 
410
        relocate_target = to_location + 1;
 
411
      else
 
412
        relocate_target = to_location;
 
413
 
 
414
      concrete_view.relocate(relocate_target, from_location);
 
415
      signal_moved(value, from_idx, to_idx);
 
416
    }
 
417
 
 
418
    template<typename T>
 
419
    void dynamic_list_collection<T>::add_list(const boost::shared_ptr<dynamic_list<T> > &lst)
 
420
    {
 
421
      // Insert all the list's items at the end of this collection.
 
422
      //
 
423
      // Could do this more efficiently, but normally new lists are
 
424
      // empty and/or very small.
 
425
      for(std::size_t idx = 0; idx < lst->size(); ++idx)
 
426
        handle_insert(lst->get_at(idx), idx, lst);
 
427
 
 
428
      const sigc::connection inserted_connection =
 
429
        lst->signal_inserted.connect(sigc::bind(sigc::mem_fun(*this,
 
430
                                                              &dynamic_list_collection::handle_insert),
 
431
                                                lst));
 
432
 
 
433
      const sigc::connection removed_connection =
 
434
        lst->signal_removed.connect(sigc::bind(sigc::mem_fun(*this,
 
435
                                                             &dynamic_list_collection::handle_remove),
 
436
                                               lst));
 
437
 
 
438
      const sigc::connection moved_connection =
 
439
        lst->signal_moved.connect(sigc::bind(sigc::mem_fun(*this,
 
440
                                                           &dynamic_list_collection::handle_move),
 
441
                                             lst));
 
442
 
 
443
      connections_by_list.insert(std::make_pair(lst, inserted_connection));
 
444
      connections_by_list.insert(std::make_pair(lst, removed_connection));
 
445
      connections_by_list.insert(std::make_pair(lst, moved_connection));
 
446
    }
 
447
 
 
448
    template<typename T>
 
449
    void dynamic_list_collection<T>::remove_list(const boost::shared_ptr<dynamic_list<T> > &lst)
 
450
    {
 
451
      // First remove all the list's entries from the concrete view.
 
452
      // I'm avoiding the temptation to optimize this, with
 
453
      // difficulty. (we don't need to do all the reindexing, so a
 
454
      // linear scan would be O(n) instead of O(n**2) -- same with
 
455
      // add_list)
 
456
      for(std::size_t idx = 0; idx < lst->size(); ++idx)
 
457
        // Pretend the list was removed from the front, so each
 
458
        // element has index 0 when it dies.
 
459
        handle_remove(lst->get_at(idx), 0, lst);
 
460
 
 
461
      // Disconnect all the list's connections.
 
462
      std::pair<
 
463
        typename sub_list_connections::iterator,
 
464
        typename sub_list_connections::iterator>
 
465
        connections = connections_by_list.equal_range(lst);
 
466
 
 
467
      for(typename sub_list_connections::iterator it = connections.first;
 
468
          it != connections.second; ++it)
 
469
        it->second.disconnect();
 
470
 
 
471
      // Drop the list from the connections map.
 
472
      connections_by_list.erase(connections.first, connections.second);
 
473
    }
 
474
  }
 
475
}
 
476
 
 
477
#endif // DYNAMIC_LIST_COLLECTION_H