replicode
list.h
Go to the documentation of this file.
1 // list.h
2 //
3 // Author: Eric Nivel
4 //
5 // BSD license:
6 // Copyright (c) 2010, Eric Nivel
7 // All rights reserved.
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are met:
10 //
11 // - Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // - Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // - Neither the name of Eric Nivel nor the
17 // names of their contributors may be used to endorse or promote products
18 // derived from this software without specific prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
21 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
22 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
23 // DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
24 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
27 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31 #ifndef r_code_list_h
32 #define r_code_list_h
33 
34 #include <vector>
35 #include <inttypes.h>
36 
37 namespace r_code {
38 
39 // Minimalist list implemented as a vector.
40 // Possible optimization: get rid of the std::vector and manage allocation oneself.
41 // Insertion not needed for now; not implemented.
42 template<typename T> class list {
43 protected:
44  static const int64_t null = -1;
45 
46  class cell { // int64: to be robust WRT realloc(); this means that Ts can hold a cell index to speed up erasure.
47  public:
48  int64_t next;
49  int64_t prev;
50  T data;
51  cell(): next(null), prev(null) {}
52  };
53 
54  std::vector<cell> cells;
55 
56  int64_t used_cells_head;
57  int64_t used_cells_tail;
58  int64_t free_cells; // backward links unused.
61 
62  void push_back_free_cell(const T &t) {
63 
64  int64_t free = free_cells;
65  free_cells = cells[free_cells].next;
67  cells[free].data = t;
68  cells[free].next = null;
69  cells[free].prev = used_cells_tail;
70  used_cells_tail = free;
71  }
72 
73  void push_back_new_cell(const T &t) {
74 
75  cell c;
76  c.data = t;
77  c.next = null;
78  c.prev = used_cells_tail;
79  cells.push_back(c);
80  used_cells_tail = cells.size() - 1;
81  }
82 
84 
85  if (cells[used_cells_tail].prev != null)
86  cells[cells[used_cells_tail].prev].next = used_cells_tail;
87  if (used_cells_head == null)
88  used_cells_head = used_cells_tail;
90  }
91 
92  void push_front_free_cell(const T &t) {
93 
94  int64_t free = free_cells;
95  free_cells = cells[free_cells].next;
97  cells[free].data = t;
98  cells[free].next = used_cells_head;
99  cells[free].prev = null;
100  used_cells_head = free;
101  }
102 
103  void push_front_new_cell(const T &t) {
104 
105  cell c;
106  c.data = t;
107  c.next = used_cells_head;
108  c.prev = null;
109  cells.push_back(c);
110  used_cells_head = cells.size() - 1;
111  }
112 
114 
115  if (cells[used_cells_head].next != null)
116  cells[cells[used_cells_head].next].prev = used_cells_head;
117  if (used_cells_tail == null)
118  used_cells_tail = used_cells_head;
119  ++used_cell_count;
120  }
121 
122  void __erase(int64_t c) {
123 
124  if (cells[c].prev != null)
125  cells[cells[c].prev].next = cells[c].next;
126  else
127  used_cells_head = cells[c].next;
128  if (cells[c].next != null)
129  cells[cells[c].next].prev = cells[c].prev;
130  else
131  used_cells_tail = cells[c].prev;
132  cells[c].next = free_cells;
133  free_cells = c;
134  ++free_cell_count;
135  --used_cell_count;
136  }
137  int64_t _erase(int64_t c) {
138 
139  int64_t next = cells[c].next;
140  __erase(c);
141  return next;
142  }
143 public:
144  list(): used_cells_head(null), used_cells_tail(null), free_cells(null), used_cell_count(0), free_cell_count(0) {}
145 
146  uint64_t size() const {
147  return used_cell_count;
148  }
150  cells.reserve(size);
151  }
152  void clear() {
153 
154  used_cells_head = used_cells_tail = free_cells = null;
155  used_cell_count = free_cell_count = 0;
156  cells.clear();
157  }
158  void push_back(const T &t) {
159 
160  if (free_cell_count)
162  else
165  }
166  void push_back(const T &t, int64_t &location) {
167 
168  if (free_cell_count) {
169 
170  location = free_cells;
172  } else {
173 
175  location = used_cells_tail;
176  }
178  }
179  void push_front(const T &t) {
180 
181  if (free_cell_count)
183  else
186  }
187  void push_front(const T &t, int64_t &location) {
188 
189  if (free_cell_count) {
190 
191  location = free_cells;
193  } else {
194 
196  location = used_cells_tail;
197  }
199  }
200 
201  class _iterator {
202  protected:
203  int64_t _cell;
204  _iterator(int64_t c): _cell(c) {}
205  _iterator(): _cell(null) {}
206  public:
207  bool operator ==(const _iterator &i) const {
208  return _cell == i._cell;
209  }
210  bool operator !=(const _iterator &i) const {
211  return _cell != i._cell;
212  }
213  };
214 
215  class iterator;
217  public _iterator {
218  friend class list;
219  private:
220  const list *_list;
221  const_iterator(const list *l, int64_t c): _iterator(c), _list(l) {}
222  public:
223  const_iterator(): _iterator(), _list(nullptr) {}
224  const T &operator *() const {
225  return _list->cells[_cell].data;
226  }
227  const T *operator ->() const {
228  return &(_list->cells[_cell].data);
229  }
231 
232  _cell = _list->cells[_cell].next;
233  return *this;
234  }
236 
237  _list = i._list;
238  _cell = i._cell;
239  return *this;
240  }
242 
243  _list = i._list;
244  _cell = i._cell;
245  return *this;
246  }
247  protected:
248  using _iterator::_cell;
249  };
250 
251  class iterator:
252  public _iterator {
253  friend class list;
254  friend class const_iterator;
255  protected:
256  using _iterator::_cell;
258  iterator(list *l, int64_t c): _iterator(c), _list(l) {}
259  public:
260  iterator(): _iterator(), _list(nullptr) {}
261  T &operator *() const {
262  return _list->cells[_cell].data;
263  }
264  T *operator ->() const {
265  return &(_list->cells[_cell].data);
266  }
268 
269  _cell = _list->cells[_cell].next;
270  return *this;
271  }
273 
274  _list = i._list;
275  _cell = i._cell;
276  return *this;
277  }
278  };
279 private:
280  static const_iterator end_iterator;
281 public:
282  iterator begin() {
283  return iterator(this, used_cells_head);
284  }
285  const_iterator begin() const {
286  return const_iterator(this, used_cells_head);
287  }
288  const_iterator &end() const {
289  return end_iterator;
290  }
291  iterator erase(iterator &i) {
292  return iterator(this, _erase(i._cell)); // no check for i._cell==null.
293  }
294  const_iterator erase(const_iterator &i) {
295  return const_iterator(this, _erase(i._cell)); // no check for i._cell==null.
296  }
297  void erase(int64_t c) {
298  __erase(c); // use for random object deletion.
299  }
300  void remove(const T &t) {
301 
302  const_iterator i(this, used_cells_head);
303  for (; i != end_iterator; ++i) {
304 
305  if ((*i) == t) {
306 
307  erase(i);
308  return;
309  }
310  }
311  }
312  T &front() {
313  return cells[used_cells_head].data;
314  }
315  T &back() {
316  return cells[used_cells_tail].data;
317  }
318 };
319 
320 template<typename T> typename list<T>::const_iterator list<T>::end_iterator;
321 }
322 
323 
324 #endif
void __erase(int64_t c)
Definition: list.h:122
const_iterator & end() const
Definition: list.h:288
_iterator()
Definition: list.h:205
std::vector< cell > cells
Definition: list.h:54
void push_front_free_cell(const T &t)
Definition: list.h:92
iterator & operator++()
Definition: list.h:267
const_iterator()
Definition: list.h:223
int64_t _cell
Definition: list.h:203
int64_t free_cells
Definition: list.h:58
const_iterator(const list *l, int64_t c)
Definition: list.h:221
const T * operator->() const
Definition: list.h:227
T & front()
Definition: list.h:312
void reserve(uint64_t size)
Definition: list.h:149
void push_front_new_cell(const T &t)
Definition: list.h:103
const_iterator begin() const
Definition: list.h:285
void push_back(const T &t)
Definition: list.h:158
void update_used_cells_head_state()
Definition: list.h:113
void erase(int64_t c)
Definition: list.h:297
void update_used_cells_tail_state()
Definition: list.h:83
iterator & operator=(const iterator &i)
Definition: list.h:272
const_iterator erase(const_iterator &i)
Definition: list.h:294
const_iterator & operator=(const const_iterator &i)
Definition: list.h:235
void push_back_new_cell(const T &t)
Definition: list.h:73
list()
Definition: list.h:144
Definition: atom.cpp:36
uint64_t used_cell_count
Definition: list.h:59
void push_front(const T &t)
Definition: list.h:179
int64_t next
Definition: list.h:48
int64_t _erase(int64_t c)
Definition: list.h:137
T data
Definition: list.h:50
void push_front(const T &t, int64_t &location)
Definition: list.h:187
Definition: list.h:46
iterator begin()
Definition: list.h:282
iterator()
Definition: list.h:260
list * _list
Definition: list.h:257
uint64_t size() const
Definition: list.h:146
cell()
Definition: list.h:51
bool operator==(const _iterator &i) const
Definition: list.h:207
Definition: list.h:251
const list * _list
Definition: list.h:220
uint64_t free_cell_count
Definition: list.h:60
const T & operator*() const
Definition: list.h:224
static const_iterator end_iterator
Definition: list.h:280
Definition: list.h:216
int64_t prev
Definition: list.h:49
const_iterator & operator++()
Definition: list.h:230
int64_t used_cells_tail
Definition: list.h:57
iterator erase(iterator &i)
Definition: list.h:291
int64_t used_cells_head
Definition: list.h:56
Definition: list.h:42
T & operator*() const
Definition: list.h:261
void push_back_free_cell(const T &t)
Definition: list.h:62
Definition: list.h:201
T * operator->() const
Definition: list.h:264
iterator(list *l, int64_t c)
Definition: list.h:258
T & back()
Definition: list.h:315
_iterator(int64_t c)
Definition: list.h:204
static const int64_t null
Definition: list.h:44
void push_back(const T &t, int64_t &location)
Definition: list.h:166
void clear()
Definition: list.h:152
bool operator!=(const _iterator &i) const
Definition: list.h:210