IDs - Ranges

vtr_range

namespace vtr

std::optional-like interface with optional references. currently: import TartanLlama’s optional into the vtr namespace documentation at https://tl.tartanllama.xyz/en/latest/api/optional.html there are three main uses of this:

  1. replace pointers when refactoring legacy code optional<T&> (reference) is in many ways a pointer, it even has * and -> operators, but it can’t be allocated or freed. this property is very helpful in refactoring.

  2. explicit alternative for containers optional<T> (non-reference) allows you to put non-empty-initializable objects into a container which owns them. it is an alternative to unique_ptr<T> in that sense, but with a cleaner interface.

  3. function return types returning an optional<T> gives the caller a clear hint to check the return value.

Q: why not use std::optional? A: std::optional doesn’t allow optional<T&> due to a disagreement about what it means to assign to an optional reference. tl::optional permits this, with “rebind on assignment” behavior. this means opt<T&> acts very similarly to a pointer. Q: why do we need opt<T&>? there’s already T*. A: in an ideal world where all pointers are aliases to existing values and nothing else, opt<T&> wouldn’t be that necessary. however VPR is full of legacy code where the usual C++ conventions about pointers don’t apply. when refactoring such code, turning all pointers into opt<T&> helps a lot. it can’t be allocated or freed and doesn’t allow pointer arithmetic. in that aspect it acts as a “enforced proper C++ ptr”. that’s why I think it’s worth keeping around in the codebase.

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()

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

std::optional-like interface with optional references. currently: import TartanLlama’s optional into the vtr namespace documentation at https://tl.tartanllama.xyz/en/latest/api/optional.html there are three main uses of this:

  1. replace pointers when refactoring legacy code optional<T&> (reference) is in many ways a pointer, it even has * and -> operators, but it can’t be allocated or freed. this property is very helpful in refactoring.

  2. explicit alternative for containers optional<T> (non-reference) allows you to put non-empty-initializable objects into a container which owns them. it is an alternative to unique_ptr<T> in that sense, but with a cleaner interface.

  3. function return types returning an optional<T> gives the caller a clear hint to check the return value.

Q: why not use std::optional? A: std::optional doesn’t allow optional<T&> due to a disagreement about what it means to assign to an optional reference. tl::optional permits this, with “rebind on assignment” behavior. this means opt<T&> acts very similarly to a pointer. Q: why do we need opt<T&>? there’s already T*. A: in an ideal world where all pointers are aliases to existing values and nothing else, opt<T&> wouldn’t be that necessary. however VPR is full of legacy code where the usual C++ conventions about pointers don’t apply. when refactoring such code, turning all pointers into opt<T&> helps a lot. it can’t be allocated or freed and doesn’t allow pointer arithmetic. in that aspect it acts as a “enforced proper C++ ptr”. that’s why I think it’s worth keeping around in the codebase.

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()

Default to the sentinel value.

inline explicit constexpr StrongId(T id)

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)])

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)

< 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

std::optional-like interface with optional references. currently: import TartanLlama’s optional into the vtr namespace documentation at https://tl.tartanllama.xyz/en/latest/api/optional.html there are three main uses of this:

  1. replace pointers when refactoring legacy code optional<T&> (reference) is in many ways a pointer, it even has * and -> operators, but it can’t be allocated or freed. this property is very helpful in refactoring.

  2. explicit alternative for containers optional<T> (non-reference) allows you to put non-empty-initializable objects into a container which owns them. it is an alternative to unique_ptr<T> in that sense, but with a cleaner interface.

  3. function return types returning an optional<T> gives the caller a clear hint to check the return value.

Q: why not use std::optional? A: std::optional doesn’t allow optional<T&> due to a disagreement about what it means to assign to an optional reference. tl::optional permits this, with “rebind on assignment” behavior. this means opt<T&> acts very similarly to a pointer. Q: why do we need opt<T&>? there’s already T*. A: in an ideal world where all pointers are aliases to existing values and nothing else, opt<T&> wouldn’t be that necessary. however VPR is full of legacy code where the usual C++ conventions about pointers don’t apply. when refactoring such code, turning all pointers into opt<T&> helps a lot. it can’t be allocated or freed and doesn’t allow pointer arithmetic. in that aspect it acts as a “enforced proper C++ ptr”. that’s why I think it’s worth keeping around in the codebase.

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*()

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 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.