MorphoGraphX
Vertex.hpp
Go to the documentation of this file.
1 //
2 // This file is part of MorphoGraphX - http://www.MorphoGraphX.org
3 // Copyright (C) 2012-2015 Richard S. Smith and collaborators.
4 //
5 // If you use MorphoGraphX in your work, please cite:
6 // http://dx.doi.org/10.7554/eLife.05864
7 //
8 // MorphoGraphX is free software, and is licensed under under the terms of the
9 // GNU General (GPL) Public License version 2.0, http://www.gnu.org/licenses.
10 //
11 #ifndef VERTEX_HPP
12 #define VERTEX_HPP
13 
22 #include <Config.hpp>
23 
24 #include <Mangling.hpp>
25 #include <Thrust.hpp>
26 #include <UnorderedMap.hpp>
27 
28 #include <iostream>
29 #include <map>
30 #include <memory>
31 #ifndef _MSC_VER
32 # include <stdint.h>
33 #endif
34 #include <typeinfo>
35 #include <utility>
36 
37 namespace mgx {
38 namespace graph {
42 typedef intptr_t vertex_identity_t;
43 
47 extern mgx_EXPORT size_t vertex_counter;
48 
49 template <typename VertexContent, typename Alloc> class WeakVertex;
50 
67 template <typename VertexContent, typename Alloc> class Vertex {
68  friend class WeakVertex<VertexContent, Alloc>;
69 
70 protected:
74  struct CountedContent : public VertexContent {
75 private:
77  : VertexContent()
78  , num(vertex_counter++)
79  {
80  count = 1u; // To be used with tbb::atomic
81  }
82 
83  CountedContent(const CountedContent& copy)
84  : VertexContent(copy)
85  , count(copy.count)
86  , num(vertex_counter++)
87  {
88  }
89 
90  CountedContent(const VertexContent& copy)
91  : VertexContent(copy)
92  , num(vertex_counter++)
93  {
94  count = 1u; // To be used with tbb::atomic
95  }
96 
97 public:
98  typedef typename Alloc::template rebind<CountedContent>::other alloc_t;
99  static alloc_t alloc;
100 
101  static CountedContent* New()
102  {
103  CountedContent* cc = alloc.allocate(1);
104  ::new (cc) CountedContent();
105  return cc;
106  }
107 
108  static CountedContent* New(const VertexContent& copy)
109  {
110  CountedContent* cc = alloc.allocate(1);
111  ::new (cc) CountedContent(copy);
112  return cc;
113  }
114 
115  static void Delete(CountedContent* cc)
116  {
117  cc->~CountedContent();
118  alloc.deallocate(cc, 1);
119  }
120 
124  unsigned int count;
125 
126  size_t num;
127  };
128 
129 public:
133  typedef vertex_identity_t identity_t;
134 
138  typedef VertexContent content_t;
139 
141 
145  typedef VertexContent* pointer;
146 
158  Vertex();
159 
178  explicit Vertex(identity_t id);
179 
186  Vertex(const Vertex& copy);
187 
191  explicit Vertex(const weak_ref_t& w);
192 
196  ~Vertex();
197 
203  VertexContent* operator->() const {
204  return content;
205  }
211  VertexContent& operator*() const {
212  return *content;
213  }
214 
224  Vertex& operator=(const Vertex& other);
225 
226  Vertex& operator=(const identity_t& id);
227 
228  Vertex& operator=(const weak_ref_t& other);
229 
230  Vertex& operator=(const VertexContent* value);
231 
237  bool operator==(const Vertex& other) const {
238  return id() == other.id();
239  }
245  bool operator!=(const Vertex& other) const {
246  return id() != other.id();
247  }
253  bool operator>(const Vertex& other) const {
254  return id() > other.id();
255  }
261  bool operator<(const Vertex& other) const {
262  return id() < other.id();
263  }
269  bool operator>=(const Vertex& other) const {
270  return id() >= other.id();
271  }
277  bool operator<=(const Vertex& other) const {
278  return id() <= other.id();
279  }
280 
284  bool isNull() const {
285  return content == 0;
286  }
287 
291  identity_t id() const {
292  return (identity_t)content;
293  }
294 
298  size_t num() const {
299  return content->num;
300  }
301 
305  operator bool() const { return content; }
306 
310  bool isWeakRef() const {
311  return false;
312  }
313 
317  weak_ref_t weakRef() const;
318 
335  static Vertex null;
336 
343  // bool serialize(storage::VVEStorage&);
344 
345  unsigned int count() const
346  {
347  if(content)
348  return content->count;
349  return 0;
350  }
351 
352 protected:
360  mutable CountedContent* content;
361 
365  void release();
366 
370  void acquire();
371 };
372 
373 template <typename VertexContent, typename Alloc>
374 typename Vertex<VertexContent, Alloc>::CountedContent::alloc_t Vertex<VertexContent, Alloc>::CountedContent::alloc;
375 
376 template <typename VertexContent, typename Alloc> Vertex<VertexContent, Alloc> Vertex<VertexContent, Alloc>::null(0);
377 
378 template <typename VertexContent, typename Alloc> class WeakVertex : public Vertex<VertexContent, Alloc> {
379  typedef typename Vertex<VertexContent, Alloc>::CountedContent CountedContent;
380 
381 public:
385  typedef vertex_identity_t identity_t;
386 
390  typedef VertexContent content_t;
391 
396 
400  typedef VertexContent* pointer;
401 
409  : Vertex<VertexContent, Alloc>(0)
410  {
411  }
412 
416  WeakVertex(const strong_ref& v)
417  : Vertex<VertexContent, Alloc>(0)
418  {
419  this->content = v.content;
420  }
421 
425  WeakVertex(const WeakVertex& copy)
426  : Vertex<VertexContent, Alloc>(0)
427  {
428  this->content = copy.content;
429  }
430 
434  explicit WeakVertex(const identity_t& id)
435  : Vertex<VertexContent, Alloc>(0)
436  {
437  this->content = reinterpret_cast<CountedContent*>(id);
438  if(this->content and this->content->count == 0)
439  this->content = 0;
440  }
441 
446  {
447  this->content = other.content;
448  return *this;
449  }
450 
451  WeakVertex& operator=(const identity_t& id)
452  {
453  this->content = reinterpret_cast<CountedContent*>(id);
454  return *this;
455  }
456 
457  WeakVertex& operator=(const strong_ref& other)
458  {
459  this->content = other.content;
460  return *this;
461  }
462 
463  ~WeakVertex() {
464  this->content = 0;
465  }
466 
467  bool isNull() const {
468  return this->content == 0 or this->content->count == 0;
469  }
470 
471 protected:
472 };
473 
474 template <typename VertexContent, typename Alloc> Vertex<VertexContent, Alloc>::~Vertex() {
475  this->release();
476 }
477 
478 template <typename VertexContent, typename Alloc>
480  : content(0)
481 {
482  content = CountedContent::New();
483 }
484 
485 template <typename VertexContent, typename Alloc>
487  : content(reinterpret_cast<CountedContent*>(id))
488 {
489  acquire();
490 }
491 
492 // template <typename VertexContent, typename Alloc>
493 // Vertex<VertexContent,Alloc>::Vertex( VertexContent* data )
494 // : content(0)
495 // {
496 // CountedContent *cdata = dynamic_cast<CountedContent*>(data);
497 // if(cdata != 0)
498 // {
499 // content = cdata;
500 // ++(content->count);
501 // }
502 // else
503 // {
504 // content = CountedContent::New();
505 // *(VertexContent*)content = *data;
506 // }
507 // }
508 
509 template <typename VertexContent, typename Alloc>
511  : content(copy.content)
512 {
513  acquire();
514 }
515 
516 template <typename VertexContent, typename Alloc>
518  : content(copy.content)
519 {
520  acquire();
521 }
522 
523 template <typename VertexContent, typename Alloc>
525 {
526  if((identity_t)content == id)
527  return *this;
528  this->release();
529  content = reinterpret_cast<CountedContent*>(id);
530  acquire();
531  return *this;
532 }
533 
534 template <typename VertexContent, typename Alloc>
536 {
537  const CountedContent* cid = dynamic_cast<const CountedContent*>(id);
538  if(cid != 0)
539  return *this = (const identity_t&)cid;
540  else {
541  return *this = (const identity_t&)(*(CountedContent::New(*id)));
542  }
543 }
544 
545 template <typename VertexContent, typename Alloc>
547 {
548  if(content == copy.content)
549  return *this;
550  this->release();
551  content = copy.content;
552  acquire();
553  return *this;
554 }
555 
556 template <typename VertexContent, typename Alloc> void Vertex<VertexContent, Alloc>::acquire()
557 {
558  if(content) {
559  if(content->count == 0)
560  content = 0;
561  else
562 #pragma omp atomic
563  ++(content->count);
564  }
565 }
566 
567 template <typename VertexContent, typename Alloc> void Vertex<VertexContent, Alloc>::release()
568 {
569  if(content) {
570 #pragma omp atomic
571  --(content->count);
572  if(content->count == 0) {
573  CountedContent::Delete(content);
574  }
575  }
576 }
577 
578 template <typename VertexContent, typename Alloc>
580 {
581  return weak_ref_t(*this);
582 }
583 
584 template <typename VertexContent, typename Alloc>
586 {
587  if(content == other.content) {
588  return *this;
589  } else
590  this->release();
591  content = other.content;
592  acquire();
593  return *this;
594 }
595 
596 template <typename VertexContent, typename Alloc, typename charT>
597 std::basic_ostream<charT>& operator<<(std::basic_ostream<charT>& ss, const Vertex<VertexContent, Alloc>& v)
598 {
599  ss << "Vertex<" << util::demangle(typeid(VertexContent).name()) << ">(" << v.id() << ")";
600  return ss;
601 }
602 } // namespace graph
603 } // namespace mgx
604 
605 namespace std {
606 #ifdef HASH_NEED_TR1
607 namespace tr1 {
608 #endif
609 template <typename VertexContent, typename Alloc>
610 struct hash<mgx::graph::Vertex<VertexContent, Alloc> > {
611  size_t operator()(const mgx::graph::Vertex<VertexContent, Alloc>& v) const
612  {
613  return ((size_t)v.id()) >> 2; // Shift to consider memory alignment!
614  }
615 };
616 
617 template <typename VertexContent, typename Alloc>
618 struct hash<mgx::graph::WeakVertex<VertexContent, Alloc> > {
619  size_t operator()(const mgx::graph::WeakVertex<VertexContent, Alloc>& v) const
620  {
621  return ((size_t)v.id()) >> 2; // Shift to consider memory alignment!
622  }
623 };
624 #ifdef HASH_NEED_TR1
625 } // namespace tr1
626 #endif
627 } // namespace std
628 
629 #endif // VERTEX_HPP
identity_t id() const
Return the identifier of a vertex.
Definition: Vertex.hpp:291
void release()
Release the current pointer.
Definition: Vertex.hpp:567
bool operator!=(const Vertex &other) const
Comparison operators.
Definition: Vertex.hpp:245
unsigned int count
Reference count on the vertex.
Definition: Vertex.hpp:124
bool operator==(const Vertex &other) const
Comparison operators.
Definition: Vertex.hpp:237
bool operator<(const Vertex &other) const
Comparison operators.
Definition: Vertex.hpp:261
Vertex< VertexContent, Alloc > strong_ref
Strong reference corresponding to the weak one.
Definition: Vertex.hpp:395
WeakVertex(const identity_t &id)
Construct a weak reference from an id.
Definition: Vertex.hpp:434
VertexContent * pointer
Type of the equivalent pointer.
Definition: Vertex.hpp:145
WeakVertex()
Construct an empty weak vertex.
Definition: Vertex.hpp:408
weak_ref_t weakRef() const
Construct a weak reference on the current vertex.
Definition: Vertex.hpp:579
STL namespace.
Vertex()
Creates a new vertex with a new content.
Definition: Vertex.hpp:479
Type of the reference counted content.
Definition: Vertex.hpp:74
VertexContent content_t
Type of the content of the vertex.
Definition: Vertex.hpp:138
size_t num() const
Return a number unique to each vertex, globally.
Definition: Vertex.hpp:298
Definition: Vertex.hpp:49
vertex_identity_t identity_t
Type of the identifier of the vertex.
Definition: Vertex.hpp:133
vertex_identity_t identity_t
Type of the identifier of the vertex.
Definition: Vertex.hpp:385
CountedContent * content
Content of the vertex.
Definition: Vertex.hpp:360
VertexContent & operator*() const
Access to the data.
Definition: Vertex.hpp:211
VertexContent * operator->() const
Access to the data.
Definition: Vertex.hpp:203
intptr_t vertex_identity_t
Type of the identifier of a vertex.
Definition: Vertex.hpp:42
Vertex & operator=(const Vertex &other)
Change the vertex held by the current object.
Definition: Vertex.hpp:585
void acquire()
Acquire the current pointer.
Definition: Vertex.hpp:556
bool operator<=(const Vertex &other) const
Comparison operators.
Definition: Vertex.hpp:277
mgx_EXPORT size_t vertex_counter
Number used to enumerate the vertices of all types.
This namespace contains all the API of MorphoGraphX.
Definition: Assert.hpp:26
Vertex of a vv graph.
Definition: Vertex.hpp:67
WeakVertex(const strong_ref &v)
Construct a weak reference from a strong one.
Definition: Vertex.hpp:416
bool isWeakRef() const
Return true if the current object hold a weak reference on a vertex.
Definition: Vertex.hpp:310
unsigned int count() const
Serialization method.
Definition: Vertex.hpp:345
VertexContent * pointer
Type of the equivalent pointer.
Definition: Vertex.hpp:400
bool operator>=(const Vertex &other) const
Comparison operators.
Definition: Vertex.hpp:269
WeakVertex & operator=(const WeakVertex &other)
Set the content of the weak reference.
Definition: Vertex.hpp:445
WeakVertex(const WeakVertex &copy)
Copy constructor.
Definition: Vertex.hpp:425
bool isNull() const
Test if a vertex is a null vertex.
Definition: Vertex.hpp:284
VertexContent content_t
Type of the content of the vertex.
Definition: Vertex.hpp:390
bool operator>(const Vertex &other) const
Comparison operators.
Definition: Vertex.hpp:253
static Vertex null
Null vertex.
Definition: Vertex.hpp:335
~Vertex()
Desctructor.
Definition: Vertex.hpp:474