1 /*
2     Copyright (c) 2007-2016 Contributors as noted in the AUTHORS file
3 
4     This file is part of libzmq, the ZeroMQ core engine in C++.
5 
6     libzmq is free software; you can redistribute it and/or modify it under
7     the terms of the GNU Lesser General Public License (LGPL) as published
8     by the Free Software Foundation; either version 3 of the License, or
9     (at your option) any later version.
10 
11     As a special exception, the Contributors give you permission to link
12     this library with independent modules to produce an executable,
13     regardless of the license terms of these independent modules, and to
14     copy and distribute the resulting executable under terms of your choice,
15     provided that you also meet, for each linked independent module, the
16     terms and conditions of the license of that module. An independent
17     module is a module which is not derived from or based on this library.
18     If you modify this library, you must extend this exception to your
19     version of the library.
20 
21     libzmq is distributed in the hope that it will be useful, but WITHOUT
22     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
23     FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
24     License for more details.
25 
26     You should have received a copy of the GNU Lesser General Public License
27     along with this program.  If not, see <http://www.gnu.org/licenses/>.
28 */
29 
30 #ifndef __ZMQ_ARRAY_INCLUDED__
31 #define __ZMQ_ARRAY_INCLUDED__
32 
33 #include <vector>
34 #include <algorithm>
35 
36 #include "macros.hpp"
37 
38 namespace zmq
39 {
40 //  Implementation of fast arrays with O(1) access, insertion and
41 //  removal. The array stores pointers rather than objects.
42 //  O(1) is achieved by making items inheriting from
43 //  array_item_t<ID> class which internally stores the position
44 //  in the array.
45 //  The ID template argument is used to differentiate among arrays
46 //  and thus let an object be stored in different arrays.
47 
48 //  Base class for objects stored in the array. If you want to store
49 //  same object in multiple arrays, each of those arrays has to have
50 //  different ID. The item itself has to be derived from instantiations of
51 //  array_item_t template for all relevant IDs.
52 
53 template <int ID = 0> class array_item_t
54 {
55   public:
array_item_t()56     array_item_t () : _array_index (-1) {}
57 
58     //  The destructor doesn't have to be virtual. It is made virtual
59     //  just to keep ICC and code checking tools from complaining.
60     virtual ~array_item_t () ZMQ_DEFAULT;
61 
set_array_index(int index_)62     void set_array_index (int index_) { _array_index = index_; }
63 
get_array_index() const64     int get_array_index () const { return _array_index; }
65 
66   private:
67     int _array_index;
68 
69     ZMQ_NON_COPYABLE_NOR_MOVABLE (array_item_t)
70 };
71 
72 
73 template <typename T, int ID = 0> class array_t
74 {
75   private:
76     typedef array_item_t<ID> item_t;
77 
78   public:
79     typedef typename std::vector<T *>::size_type size_type;
80 
81     array_t () ZMQ_DEFAULT;
82 
size()83     size_type size () { return _items.size (); }
84 
empty()85     bool empty () { return _items.empty (); }
86 
operator [](size_type index_)87     T *&operator[] (size_type index_) { return _items[index_]; }
88 
push_back(T * item_)89     void push_back (T *item_)
90     {
91         if (item_)
92             static_cast<item_t *> (item_)->set_array_index (
93               static_cast<int> (_items.size ()));
94         _items.push_back (item_);
95     }
96 
erase(T * item_)97     void erase (T *item_)
98     {
99         erase (static_cast<item_t *> (item_)->get_array_index ());
100     }
101 
erase(size_type index_)102     void erase (size_type index_)
103     {
104         if (_items.empty ())
105             return;
106         static_cast<item_t *> (_items.back ())
107           ->set_array_index (static_cast<int> (index_));
108 
109         _items[index_] = _items.back ();
110         _items.pop_back ();
111     }
112 
swap(size_type index1_,size_type index2_)113     void swap (size_type index1_, size_type index2_)
114     {
115         if (_items[index1_])
116             static_cast<item_t *> (_items[index1_])
117               ->set_array_index (static_cast<int> (index2_));
118         if (_items[index2_])
119             static_cast<item_t *> (_items[index2_])
120               ->set_array_index (static_cast<int> (index1_));
121         std::swap (_items[index1_], _items[index2_]);
122     }
123 
clear()124     void clear () { _items.clear (); }
125 
index(T * item_)126     static size_type index (T *item_)
127     {
128         return static_cast<size_type> (
129           static_cast<item_t *> (item_)->get_array_index ());
130     }
131 
132   private:
133     typedef std::vector<T *> items_t;
134     items_t _items;
135 
136     ZMQ_NON_COPYABLE_NOR_MOVABLE (array_t)
137 };
138 }
139 
140 #endif
141