Lumiera  0.pre.03
»edit your freedom«
path-array.hpp
Go to the documentation of this file.
1 /*
2  PATH-ARRAY.hpp - sequence of path-like component-IDs in fixed storage
3 
4  Copyright (C) Lumiera.org
5  2017, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 */
22 
23 
48 #ifndef LIB_PATH_ARRAY_H
49 #define LIB_PATH_ARRAY_H
50 
51 #include "lib/error.hpp"
52 #include "lib/symbol.hpp"
53 #include "lib/iter-adapter.hpp"
55 #include "lib/format-obj.hpp"
56 #include "lib/util.hpp"
57 
58 #include <algorithm>
59 #include <utility>
60 #include <string>
61 #include <memory>
62 #include <array>
63 
64 
65 namespace lib {
66  namespace error = lumiera::error;
67 
68  using std::string;
69  using std::forward;
70  using lib::Literal;
71  using util::unConst;
72  using util::isnil;
73 
74  namespace con { // Implementation helper: flexible heap based extension storage....
75 
83  class Extension
84  {
85  using PStorage = Literal*;
86 
87  PStorage storage_;
88 
89 
90  static size_t&
91  size (PStorage& p)
92  {
93  REQUIRE (p);
94  return reinterpret_cast<size_t&> (p[0]);
95  }
96 
101  PStorage
102  newCopy() const
103  {
104  size_t siz = 1 + size (unConst(this)->storage_);
105  const char** alloc = new const char*[siz];
106  std::copy (storage_, storage_+siz, alloc);
107  return reinterpret_cast<PStorage> (alloc);
108  }
109 
110 
111  public:
112  ~Extension()
113  {
114  if (storage_)
115  delete[] storage_;
116  }
117 
118  Extension() noexcept
119  : storage_{nullptr}
120  { }
121 
122  template<typename...ELMS>
123  explicit
124  Extension (ELMS&& ...elms)
125  : storage_{new Literal[1 + sizeof...(ELMS)]} // proper alignment maintained here (TICKET #1204)
126  {
127  size(storage_) = sizeof...(ELMS);
128  new(storage_+1) Literal[sizeof...(ELMS)] {forward<ELMS>(elms)...};
129  }
130 
131  Extension (Extension const& r)
132  : storage_{r.storage_? r.newCopy() : nullptr}
133  { }
134 
135  Extension (Extension&& rr) noexcept
136  : storage_{nullptr}
137  {
138  if (rr.storage_)
139  std::swap (storage_, rr.storage_);
140  }
141 
142  Extension& operator= (Extension const& o)
143  {
144  if (this != &o)
145  {
146  std::unique_ptr<Literal[]> cp;
147  if (o.storage_)
148  cp.reset (o.newCopy());
149  if (storage_)
150  delete[] storage_;
151  storage_ = cp.release();
152  }
153  return *this;
154  }
155 
156  Extension& operator= (Extension&& rr) noexcept
157  {
158  if (this != &rr)
159  {
160  std::swap (storage_, rr.storage_);
161  }
162  return *this;
163  }
164 
165 
166 
167  operator bool() const { return not empty(); }
168  bool empty() const { return not storage_;}
169 
170  size_t
171  size() const
172  {
173  return storage_? size(unConst(this)->storage_)
174  : 0;
175  }
176 
177  Literal const&
178  operator[] (size_t idx) const
179  {
180  REQUIRE (storage_ and idx < size());
181  return storage_[1+idx];
182  }
183 
184  size_t
185  indexOf (Literal const* pos) const
186  {
187  REQUIRE (isValid (pos));
188  return pos - (storage_+1);
189  }
190 
191 
192  bool
193  isValid (Literal const* pos) const
194  {
195  return storage_
196  and storage_ < pos
197  and pos < storage_ + (1 + size (unConst(this)->storage_));
198  }
199 
200  void
201  resizeTo (size_t cnt)
202  {
203  if (cnt > size())
204  { // need more storage
205  if (storage_)
206  { // copy content to new expanded storage
207  auto target = new const char* [cnt+1];
208  auto pos = std::copy (storage_, storage_+1+size(), target);
209  for ( ; pos < target+1+cnt; ++pos)
210  *pos = nullptr;
211  delete[] storage_;
212  storage_ = reinterpret_cast<PStorage> (target);
213  }
214  else // allocate and init empty
215  storage_ = new Literal [cnt+1];
216 
217  size (storage_) = cnt;
218  return;
219  }
220  if (not storage_) return;
221  if (cnt == 0)
222  {
223  delete[] storage_;
224  storage_ = nullptr;
225  }
226  else
227  size(storage_) = cnt;
228  // excess elements now unreachable
229  // note: delete[] knows original size
230  }
231  };
232  }//(End)Implementation helper
233 
234 
235 
236  using meta::pickArg;
237  using meta::pickInit;
238  using meta::IndexSeq;
239 
250  template<size_t chunk_size>
251  class PathArray
252  {
253  static_assert (0 < chunk_size, "PathArray chunk_size must be nonempty");
254 
255  using CcP = const char*;
256  using LiteralArray = std::array<Literal, chunk_size>;
257 
258  LiteralArray elms_;
259  con::Extension tail_;
260 
270  template<size_t...prefix, size_t...rest, typename...ARGS>
273  ,ARGS&& ...args)
274  : elms_{pickInit<prefix,CcP> (forward<ARGS>(args)...) ...}
275  , tail_{pickArg<rest> (forward<ARGS>(args)...) ...}
276  {
277  this->normalise();
278  }
279 
286  template<typename...ARGS>
287  struct Split
288  {
289  using Prefix = typename meta::BuildIndexSeq<chunk_size>::Ascending;
290  using Rest = typename meta::BuildIdxIter<ARGS...>::template After<chunk_size>;
291  };
292 
293  public:
294  template<typename...ARGS>
295  explicit
296  PathArray (ARGS&& ...args)
297  : PathArray(typename Split<ARGS...>::Prefix()
298  ,typename Split<ARGS...>::Rest()
299  ,forward<ARGS> (args)...)
300  { }
301 
302  PathArray(PathArray&&) = default;
303  PathArray(PathArray const&) = default;
304  PathArray(PathArray& o) : PathArray((PathArray const&)o) { }
305  PathArray& operator= (PathArray const&) = default;
306  PathArray& operator= (PathArray &&) = default;
308 
309 
310  size_t
311  size() const
312  {
313  return tail_? chunk_size + tail_.size()
314  : findInlineEnd() - elms_.begin();
315  }
316 
317  size_t
318  leafLevel() const
319  {
320  return empty()? 0 : size()-1;
321  }
322 
323  bool
324  empty() const
325  {
326  return not elms_[0]; // normalise() ensures nonnull unless completely empty
327  }
328 
330  operator string() const;
331 
332 
339  Literal const&
340  operator[] (size_t idx) const
341  {
342  Literal* elm = unConst(this)->getPosition (idx);
343  if (not elm)
344  throw error::Invalid ("Accessing index "+util::toString(idx)
345  +" on PathArray of size "+ util::toString(size())
346  ,error::LUMIERA_ERROR_INDEX_BOUNDS);
347  return *elm;
348  }
349 
356  size_t
357  indexOf (Literal const& content) const
358  {
359  if (elms_.begin() <= &content and &content < elms_.end())
360  return &content - elms_.begin();
361  if (tail_.isValid (&content))
362  return chunk_size + tail_.indexOf (&content);
363 
364  throw error::Invalid ("Referred content "+util::toString(&content)
365  +" is not located within the storage of PathArray "
366  +string(*this));
367  }
368 
369 
370  protected: /* ==== Iteration control API for IterAdapter ==== */
371 
373  friend void
374  iterNext (const PathArray*, const Literal*& pos)
375  {
376  ++pos;
377  }
378 
380  friend bool
381  checkPoint (const PathArray* src, const Literal*& pos)
382  {
383  REQUIRE (src);
384  if (pos == src->elms_.end() and src->tail_)
385  pos = &src->tail_[0];
386  else
387  if (not src->isValid (pos))
388  {
389  pos = nullptr;
390  return false;
391  }
392  ENSURE ( (src->elms_.begin() <= pos and pos < src->elms_.end())
393  or src->tail_.isValid(pos));
394  return true;
395  }
396 
397  public:
399  using iterator = const_iterator;
400 
401  using value_type = Literal;
402  using reference = Literal&;
403  using const_reference = Literal const&;
404 
406  iterator begin() const { return firstNonempty(); }
407  iterator end() const { return iterator{}; }
408 
409  friend iterator begin(PathArray const& pa) { return pa.begin();}
410  friend iterator end (PathArray const& pa) { return pa.end(); }
411 
412 
413 
414  private: /* ===== implementation details ===== */
415 
416  bool
417  isValid (Literal const* pos) const
418  {
419  return pos
420  and (tail_.isValid(pos)
421  or (elms_.begin() <= pos and pos < elms_.end()
422  and *pos));
423  }
424 
425  iterator
426  firstNonempty () const
427  {
428  iterator startPos{this, elms_.begin()};
429  while (startPos && isnil (*startPos))
430  ++startPos;
431  return startPos;
432  }
433 
438  Literal const*
440  {
441  Literal const* lastPos = elms_.begin() + chunk_size-1;
442  Literal const* beforeStart = elms_.begin() - 1;
443  while (lastPos != beforeStart and not *lastPos)
444  --lastPos;
445  return ++lastPos; // at start if empty, else one behind the last
446  }
447 
448 
449  /* ===== manipulation by UICoord and Builder subclasses ===== */
450  protected:
455  Literal*
456  getPosition (size_t idx)
457  {
458  Literal const* elm =nullptr;
459  if (idx < chunk_size)
460  elm = elms_[idx]? &elms_[idx] : nullptr;
461  else
462  if (idx-chunk_size < tail_.size())
463  elm = &tail_[idx-chunk_size];
464 
465  return const_cast<Literal*> (elm);
466  }
467 
472  Literal*
473  expandPosition (size_t idx)
474  {
475  if (chunk_size <= idx and size() <= idx)
476  tail_.resizeTo(idx+1 - chunk_size);
477  if (idx < chunk_size)
478  return elms_.begin() + idx;
479 
480  ENSURE (idx-chunk_size < tail_.size());
481  return const_cast<Literal*> (&tail_[idx-chunk_size]);
482  }
483 
485  void
486  setContent (Literal* pos, const char* val)
487  {
488  REQUIRE (pos);
489  *reinterpret_cast<const char**> (pos) = val;
490  }
491 
492  void
493  truncateTo (size_t newSize)
494  {
495  if (newSize < chunk_size)
496  {
497  Literal* end = elms_.end();
498  Literal* pos = getPosition(newSize);
499  if (pos)
500  for ( ; pos!=end; ++pos)
501  setContent (pos, nullptr);
502  tail_.resizeTo (0);
503  }
504  else
505  if (newSize-chunk_size < tail_.size())
506  tail_.resizeTo (newSize - chunk_size);
507  // otherwise: keep current size, don't grow
508  }
509 
517  void
519  {
520  if (size() == 0) return;
521  const char* fill = Symbol::EMPTY;
522 
523  Literal* end = elms_.end();
524  Literal* pos = elms_.begin();
525  for ( ; pos!=end; ++pos)
526  if (isnil (*pos))
527  setContent (pos, fill);
528  else
529  if (fill==Symbol::EMPTY)
530  fill = Symbol::ANY;
531 
532  if (tail_)
533  {
534  // normalise data in extension storage
535  pos = getPosition (chunk_size);
536  end = pos + tail_.size();
537  for ( ; pos!=end; ++pos)
538  if (isnil (*pos))
539  setContent (pos, fill);
540  else
541  if (fill==Symbol::EMPTY)
542  fill = Symbol::ANY;
543  }
544 
545  size_t idx = size();
546  // trim trailing fill
547  while (idx and fill == *getPosition (--idx))
548  setContent (getPosition(idx), nullptr);
549 
550  if (idx >= chunk_size-1)
551  tail_.resizeTo (idx+1 - chunk_size);
552  else
553  tail_.resizeTo (0);
554  }
555  };
556 
557 
558 
559 
560  template<size_t chunk_size>
561  inline
563  {
564  if (this->empty()) return "";
565 
566  string buff;
567  size_t expectedLen = this->size() * 10;
568  buff.reserve (expectedLen); // heuristic
569  for (Literal elm : *this)
570  buff += elm + "/";
571 
572  // chop off last delimiter
573  size_t len = buff.length();
574  ASSERT (len >= 1);
575  buff.resize(len-1);
576  return buff;
577  }
578 
579 
580 
584  template<size_t cl, size_t cr>
585  bool
587  {
588  if (l.size() != r.size()) return false;
589 
590  typename PathArray<cl>::iterator lp = l.begin();
591  typename PathArray<cl>::iterator rp = r.begin();
592  while (lp and rp)
593  {
594  if (*lp != *rp) return false;
595  ++lp;
596  ++rp;
597  }
598  return isnil(lp) and isnil(rp);
599  }
600 
601  template<size_t cl, size_t cr>
602  bool
603  operator!= (PathArray<cl> const& l, PathArray<cr> const& r)
604  {
605  return not (l == r);
606  }
607 
608 
609 
610 }// namespace lib
611 #endif /*LIB_PATH_ARRAY_H*/
Literal * expandPosition(size_t idx)
Definition: path-array.hpp:473
Hold a sequence of index numbers as template parameters.
build a sequence of index numbers based on a type sequence
Helper template(s) for creating Lumiera Forward Iterators.
PStorage newCopy() const
allocate a copy.
Definition: path-array.hpp:102
inline string literal This is a marker type to indicate that
Definition: symbol.hpp:75
bool operator==(PtrDerefIter< I1 > const &il, PtrDerefIter< I2 > const &ir)
Supporting equality comparisons...
Literal const * findInlineEnd() const
find effective end of data in the inline array, i.e.
Definition: path-array.hpp:439
Implementation namespace for support and library code.
Derived specific exceptions within Lumiera&#39;s exception hierarchy.
Definition: error.hpp:196
Abstraction for path-like topological coordinates.
Definition: path-array.hpp:251
Marker types to indicate a literal string and a Symbol.
void normalise()
establish the contract of PathArray
Definition: path-array.hpp:518
iterator begin() const
Definition: path-array.hpp:406
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
friend void iterNext(const PathArray *, const Literal *&pos)
Implementation of Iteration-logic: pull next element.
Definition: path-array.hpp:374
friend bool checkPoint(const PathArray *src, const Literal *&pos)
Implementation of Iteration-logic: detect iteration end.
Definition: path-array.hpp:381
PathArray(IndexSeq< prefix... >, IndexSeq< rest... >, ARGS &&...args)
Definition: path-array.hpp:271
Lumiera error handling (C++ interface).
Simple functions to represent objects, for debugging and diagnostics.
void setContent(Literal *pos, const char *val)
Definition: path-array.hpp:486
Literal * getPosition(size_t idx)
Definition: path-array.hpp:456
Heap-allocated extension storage for an immutable sequence of literal strings.
Definition: path-array.hpp:83
size_t indexOf(Literal const &content) const
reverse lookup of actual path content
Definition: path-array.hpp:357
Adapter for building an implementation of the »Lumiera Forward Iterator« concept. ...
Metaprogramming with type sequences based on variadic template parameters.