IDs - Ranges

vtr_range

namespace vtr

Functions

template<typename T>
auto make_range(T b, T e)

Creates a vtr::Range from a pair of iterators.

Unlike using the vtr::Range() constructor (which requires specifying the template type T, using vtr::make_range() infers T from the arguments.

Example usage: auto my_range = vtr::make_range(my_vec.begin(), my_vec.end());

template<typename Container>
auto make_range(const Container &c)

Creates a vtr::Range from a container.

template<typename T>
class Range
#include <vtr_range.h>

The vtr::Range template models a range defined by two iterators of type T.

It allows conveniently returning a range from a single function call without having to explicity expose the underlying container, or make two explicit calls to retrieve the associated begin and end iterators. It also enables the easy use of range-based-for loops.

For example:

 class My Data {
     public:
         typdef std::vector<int>::const_iterator my_iter;
         vtr::Range<my_iter> data();
     ...
     private:
         std::vector<int> data_;
 };

 ...

 MyDat my_data;

 //fill my_data

 for(int val : my_data.data()) {
     //work with values stored in my_data
 }

The empty() and size() methods are convenience wrappers around the relevant iterator comparisons.

Note that size() is only constant time if T is a random-access iterator!

Public Functions

inline Range(T b, T e)

constructor

inline T begin()

Return an iterator to the start of the range.

inline T end()

Return an iterator to the end of the range.

inline const T begin() const

Return an iterator to the start of the range (immutable)

inline const T end() const

Return an iterator to the end of the range (immutable)

inline bool empty()

Return true if empty.

inline size_t size()

Return the range size.

vtr_strong_id

This header provides the StrongId class.

It is template which can be used to create strong Id’s which avoid accidental type conversions (generating compiler errors when they occur).

Motivation

It is common to use an Id (typically an integer) to identify and represent a component. A basic example (poor style):

 size_t count_net_terminals(int net_id);

Where a plain int is used to represent the net identifier. Using a plain basic type is poor style since it makes it unclear that the parameter is an Id.

A better example is to use a typedef:

 typedef int NetId;

 size_t count_net_teriminals(NetId net_id);

It is now clear that the parameter is expecting an Id.

However this approach has some limitations. In particular, typedef’s only create type aliases, and still allow conversions. This is problematic if there are multiple types of Ids. For example:

 typedef int NetId;
 typedef int BlkId;

 size_t count_net_teriminals(NetId net_id);

 BlkId blk_id = 10;
 NetId net_id = 42;

 count_net_teriminals(net_id); //OK
 count_net_teriminals(blk_id); //Bug: passed a BlkId as a NetId

Since typdefs are aliases the compiler issues no errors or warnings, and silently passes the BlkId where a NetId is expected. This results in hard to diagnose bugs.

We can avoid this issue by using a StrongId:

 struct net_id_tag; //Phantom tag for NetId
 struct blk_id_tag; //Phantom tag for BlkId

 typedef StrongId<net_id_tag> NetId;
 typedef StrongId<blk_id_tag> BlkId;

 size_t count_net_teriminals(NetId net_id);

 BlkId blk_id = 10;
 NetId net_id = 42;

 count_net_teriminals(net_id); //OK
 count_net_teriminals(blk_id); //Compiler Error: NetId expected!

StrongId is a template which implements the basic features of an Id, but disallows silent conversions between different types of Ids. It uses another ‘tag’ type (passed as the first template parameter) to uniquely identify the type of the Id (preventing conversions between different types of Ids).

Usage

The StrongId template class takes one required and three optional template parameters:

  1. Tag - the unique type used to identify this type of Ids [Required]

  2. T - the underlying integral id type (default: int) [Optional]

  3. T sentinel - a value representing an invalid Id (default: -1) [Optional]

If no value is supllied during construction the StrongId is initialized to the invalid/sentinel value.

Example 1: default definition

 struct net_id_tag;
 typedef StrongId<net_id_tag> NetId; //Internally stores an integer Id, -1 represents invalid

Example 2: definition with custom underlying type

 struct blk_id_tag;
 typedef StrongId<net_id_tag,size_t> BlkId; //Internally stores a size_t Id, -1 represents invalid

Example 3: definition with custom underlying type and custom sentinel value

 struct pin_id_tag;
 typedef StrongId<net_id_tag,size_t,0> PinId; //Internally stores a size_t Id, 0 represents invalid

Example 4: Creating Ids

 struct net_id_tag;
 typedef StrongId<net_id_tag> MyId; //Internally stores an integer Id, -1 represents invalid

 MyId my_id;           //Defaults to the sentinel value (-1 by default)
 MyId my_other_id = 5; //Explicit construction
 MyId my_thrid_id(25); //Explicit construction

Example 5: Comparing Ids

 struct net_id_tag;
 typedef StrongId<net_id_tag> MyId; //Internally stores an integer Id, -1 represents invalid

 MyId my_id;           //Defaults to the sentinel value (-1 by default)
 MyId my_id_one = 1;
 MyId my_id_two = 2;
 MyId my_id_also_one = 1;

 my_id_one == my_id_also_one; //True
 my_id_one == my_id; //False
 my_id_one == my_id_two; //False
 my_id_one != my_id_two; //True

Example 5: Checking for invalid Ids

 struct net_id_tag;
 typedef StrongId<net_id_tag> MyId; //Internally stores an integer Id, -1 represents invalid

 MyId my_id;           //Defaults to the sentinel value
 MyId my_id_one = 1;

 //Comparison against a constructed invalid id
 my_id == MyId::INVALID(); //True
 my_id_one == MyId::INVALID(); //False
 my_id_one != MyId::INVALID(); //True

 //The Id can also be evaluated in a boolean context against the sentinel value
 if(my_id) //False, my_id is invalid
 if(!my_id) //True my_id is valid
 if(my_id_one) //True my_id_one is valid

Example 6: Indexing data structures

 struct my_id_tag;
 typedef StrongId<net_id_tag> MyId; //Internally stores an integer Id, -1 represents invalid

 std::vector<int> my_vec = {0, 1, 2, 3, 4, 5};

 MyId my_id = 2;

 my_vec[size_t(my_id)]; //Access the third element via explicit conversion

namespace vtr
namespace std

Specialize std::hash for StrongId’s (needed for std::unordered_map-like containers)

template<typename tag, typename T = int, T sentinel = T(-1)>
class vtr::StrongId

Class template definition with default template parameters.

Public Functions

inline constexpr StrongId()

Default to the sentinel value.

inline explicit constexpr StrongId(T id)

Only allow explict constructions from a raw Id (no automatic conversions)

inline explicit operator bool() const

Allow explicit conversion to bool (e.g. if(id))

inline explicit operator std::size_t() const

Allow explicit conversion to size_t (e.g. my_vector[size_t(strong_id)])

Public Static Functions

static inline constexpr StrongId INVALID()

Gets the invalid Id.

Friends

friend friend bool operator== (const StrongId< tag, T, sentinel > &lhs, const StrongId< tag, T, sentinel > &rhs)

To enable comparisions between Ids.

Note that since these are templated functions we provide an empty set of template parameters after the function name (i.e. <>)

friend friend bool operator!= (const StrongId< tag, T, sentinel > &lhs, const StrongId< tag, T, sentinel > &rhs)

!= operator

friend friend bool operator< (const StrongId< tag, T, sentinel > &lhs, const StrongId< tag, T, sentinel > &rhs)

< operator

vtr_strong_id_range

This header defines a utility class for StrongId’s.

StrongId’s are described in vtr_strong_id.h. In some cases, StrongId’s be considered like random access iterators, but not all StrongId’s have this property. In addition, there is utility in refering to a range of id’s, and being able to iterator over that range.

namespace vtr
template<typename StrongId>
class StrongIdIterator
#include <vtr_strong_id_range.h>

StrongIdIterator class.

StrongIdIterator allows a StrongId to be treated like a random access iterator. Whether this is a correct use of the abstraction is up to the called.

Public Functions

StrongIdIterator() = default

constructor

StrongIdIterator &operator=(const StrongIdIterator &other) = default

copy constructor

StrongIdIterator(const StrongIdIterator &other) = default

copy constructor

inline explicit StrongIdIterator(StrongId id)

constructor

inline StrongId &operator*()

Dereference operator (*)

inline StrongIdIterator &operator+=(ssize_t n)

+= operator

inline StrongIdIterator &operator-=(ssize_t n)

-= operator

inline StrongIdIterator &operator++()

++ operator

inline StrongIdIterator &operator--()

Decremment operator.

inline StrongId operator[](ssize_t offset) const

Indexing operator [].

template<typename StrongId>
class StrongIdRange
#include <vtr_strong_id_range.h>

StrongIdRange class.

StrongIdRange allows a pair of StrongId’s to defines a continguous range of ids. The “end” StrongId is excluded from this range.

Public Functions

inline StrongIdRange(StrongId b, StrongId e)

constructor

inline StrongIdIterator<StrongId> begin() const

Returns a StrongIdIterator to the first strongId in the range.

inline StrongIdIterator<StrongId> end() const

Returns a StrongIdIterator referring to the past-the-end element in the vector container.

inline bool empty()

Returns true if the range is empty.

inline size_t size()

Reurns the size of the range.