IDs - Ranges¶

vtr_range¶

namespace vtr

Functions

template<typename T> constexpr 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> inline 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 constexpr Range(T b, T e)¶: constructor

inline constexpr T begin()¶: Return an iterator to the start of the range.

inline constexpr T end()¶: Return an iterator to the end of the range.

inline constexpr const T begin() const¶: Return an iterator to the start of the range (immutable)

inline constexpr const T end() const¶: Return an iterator to the end of the range (immutable)

inline constexpr bool empty()¶: Return true if empty.

inline constexpr size_t size() const¶: 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:

Tag - the unique type used to identify this type of Ids [Required]
T - the underlying integral id type (default: int) [Optional]
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 StrongId¶

Class template definition with default template parameters.

Public Functions

inline constexpr StrongId() noexcept¶: Default to the sentinel value.

inline explicit constexpr StrongId(T id) noexcept¶: Only allow explicit constructions from a raw Id (no automatic conversions)

inline explicit constexpr operator bool() const¶: Allow explicit conversion to bool (e.g. if(id))

inline constexpr bool is_valid() const¶: Another name for the bool cast.

inline explicit constexpr operator std::size_t() const¶: Allow explicit conversion to size_t (e.g. my_vector[size_t(strong_id)])

inline explicit constexpr operator int() const¶: Allow explicit conversion to int (int(RRNodeId::INVALID()) == -1)

Public Static Functions

static inline constexpr StrongId INVALID() noexcept¶: Gets the invalid Id.

Friends

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

To enable comparisons between Ids.

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

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

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

friend std::ostream &operator<<(std::ostream &out, const StrongId<tag, T, sentinel> &rhs)¶: to be able to print them out

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

Functions

template<typename IdType> inline StrongIdIterator<IdType> operator+(const StrongIdIterator<IdType> &lhs, ssize_t n)¶

operator

template<typename IdType> inline StrongIdIterator<IdType> operator-(const StrongIdIterator<IdType> &lhs, ssize_t n)¶

operator

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*() const¶: Dereference operator (*)

inline StrongIdIterator &operator+=(ssize_t n)¶: += operator

inline StrongIdIterator &operator-=(ssize_t n)¶: -= operator

inline StrongIdIterator &operator++()¶: ++ operator

inline StrongIdIterator operator++(int)¶: Post-increment operator.

inline StrongIdIterator &operator--()¶: Decremment operator.

inline StrongId operator[](ssize_t offset) const¶: Indexing operator [].

template<typename IdType> inline ssize_t operator-(const StrongIdIterator<IdType> &other) const¶: ~ operator

template<typename IdType> inline bool operator==(const StrongIdIterator<IdType> &other) const¶: == operator

template<typename IdType> inline bool operator!=(const StrongIdIterator<IdType> &other) const¶: != operator

template<typename IdType> inline bool operator<(const StrongIdIterator<IdType> &other) const¶: < 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.