Containers

vtr_vector

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.

template<typename K, typename V, typename Allocator = std::allocator<V>>
class vector : private std::vector<V, std::allocator<V>>

#include <vtr_vector.h>

A std::vector container which is indexed by K (instead of size_t).

The main use of this container is to behave like a std::vector which is indexed by a vtr::StrongId. It assumes that K is explicitly convertable to size_t (i.e. via operator size_t()), and can be explicitly constructed from a size_t.

It includes all the following std::vector functions:

• begin

• cbegin

• cend

• crbegin

• crend

• end

• rbegin

• rend

• capacity

• empty

• max_size

• reserve

• resize

• shrink_to_fit

• size

• back

• front

• assign

• clear

• emplace

• emplace_back

• erase

• get_allocator

• insert

• pop_back

• push_back

If you need more std::map-like (instead of std::vector-like) behaviour see vtr::vector_map.

class key_iterator : public std::iterator<std::bidirectional_iterator_tag, key_type>

#include <vtr_vector.h>

Iterator class which is convertable to the key_type.

This allows end-users to call the parent class’s keys() member to iterate through the keys with a range-based for loop

Public Functions

inline key_iterator(key_iterator::value_type init)

constructor

inline key_iterator operator++()

++ operator

inline key_iterator operator--()

decrement operator

inline reference operator*()

dereference oeprator

inline pointer operator->()

-> operator

Public Functions

inline V *data()

Returns a pointer to the vector’s data.

inline const V *data() const

Returns a pointer to the vector’s data (immutable)

inline reference operator[](const key_type id)

[] operator

inline const_reference operator[](const key_type id) const

[] operator immutable

inline reference at(const key_type id)

at() operator

inline const_reference at(const key_type id) const

at() operator immutable

inline void swap(vector<K, V, Allocator> &other)

swap function

inline key_range keys() const

Returns a range containing the keys.

vtr_small_vector

template<class T, class S = uint32_t>
class small_vector

vtr::small_vector is a std::vector like container which:

• consumes less memory: sizeof(vtr::small_vector) < sizeof(std::vector)

• possibly stores elements in-place (i.e. within the object)

On a typical LP64 system a vtr::small_vector consumes 16 bytes by default and supports vectors up to ~2^32 elements long, while a std::vector consumes 24 bytes and supports up to ~2^64 elements. The type used to store the size and capacity is configurable, and set by the second template parameter argument. Setting it to size_t will replicate std::vector’s characteristics.

For short vectors vtr::small_vector will try to store elements in-place (i.e. within the vtr::small_vector object) instead of dynamically allocating an array (by re-using the internal storage for the pointer, size and capacity). Whether this is possible depends on the size and alignment requirements of the value type, as compared to vtr::small_vector. If in-place storage is not possible (e.g. due to a large value type, or a large number of elements) a dynamic buffer is allocated (similar to std::vector).

This is a highly specialized container. Unless you have specifically measured it’s usefulness you should use std::vector.

Public Functions

inline small_vector()

constructor

inline small_vector(size_type nelem)

constructor

inline const_iterator begin() const

Return a const_iterator to the first element.

inline const_iterator end() const

Return a const_iterator pointing to the past-the-end element in the container.

inline const_reverse_iterator rbegin() const

Return a const_reverse_iterator pointing to the last element in the container (i.e., its reverse beginning).

inline const_reverse_iterator rend() const

Return a const_reverse_iterator pointing to the theoretical element preceding the first element in the container (which is considered its reverse end).

inline const_iterator cbegin() const

Return a const_iterator pointing to the first element in the container.

inline const_iterator cend() const

a const_iterator pointing to the past-the-end element in the container.

inline const_reverse_iterator crbegin() const

Return a const_reverse_iterator pointing to the last element in the container (i.e., its reverse beginning).

inline const_reverse_iterator crend() const

Return a const_reverse_iterator pointing to the theoretical element preceding the first element in the container (which is considered its reverse end).

inline size_type size() const

return the vector size (Padding ensures long/short format sizes are always aligned)

inline size_t max_size() const

Return the maximum size.

inline size_type capacity() const

Return the vector capacity.

inline bool empty() const

Return true if empty.

inline const_reference operator[](size_t i) const

Immutable indexing operator [].

inline const_reference at(size_t i) const

Immutable at() operator.

inline const_reference front() const

Return a constant reference to the first element.

inline const_reference back() const

Return a constant reference to the last element.

inline const_pointer data() const

Return a constant pointer to the vector data.

inline iterator begin()

Return an iterator pointing to the first element in the sequence.

inline iterator end()

Return an iterator referring to the past-the-end element in the vector container.

inline reverse_iterator rbegin()

Return a reverse iterator pointing to the last element in the vector (i.e., its reverse beginning).

inline reverse_iterator rend()

Return a reverse iterator pointing to the theoretical element preceding the first element in the vector (which is considered its reverse end).

inline void resize(size_type n)

Resizes the container so that it contains n elements.

inline void resize(size_type n, value_type val)

Resizes the container so that it contains n elements and fills it with val.

inline void reserve(size_type num_elems)

Reserve memory for a spicific number of elemnts.

Don’t change capacity unless requested number of elements is both:

• More than the short capacity (no need to reserve up to short capacity)

• Greater than the current size (capacity can never be below size)

inline void shrink_to_fit()

Requests the container to reduce its capacity to fit its size.

inline reference operator[](size_t i)

Indexing operator [].

inline reference at(size_t i)

at() operator

inline reference front()

Returns a reference to the first element in the vector.

inline reference back()

Returns a reference to the last element in the vector.

template<class InputIterator>
inline void assign(InputIterator first, InputIterator last)

Assigns new contents to the vector, replacing its current contents, and modifying its size accordingly.

Input iterators to the initial and final positions in a sequence. The range used is [first,last), which includes all the elements between first and last, including the element pointed by first but not the element pointed by last.

inline void assign(size_type n, const value_type &val)

Assigns new contents to the vector, replacing its current contents, and modifying its size accordingly.

Resize the vector to n and fill it with val

inline void assign(std::initializer_list<value_type> il)

Assigns new contents to the vector, replacing its current contents, and modifying its size accordingly.

The compiler will automatically construct such objects from initializer list declarators (il)

inline void push_back(value_type value)

Construct default value_type at new location.

inline void pop_back()

Removes the last element in the vector, effectively reducing the container size by one.

inline iterator insert(const_iterator position, const value_type &val)

The vector is extended by inserting new elements before the element at the specified position, effectively increasing the container size by the number of elements inserted.

inline iterator insert(const_iterator position, size_type n, const value_type &val)

Insert a new value.

Location of position as an index, which will be unchanged if the underlying storage is reallocated

inline iterator insert(const_iterator position, size_type n, value_type &&val)

Insert n elements at position position and fill them with value val.

inline iterator erase(const_iterator position)

Removes from the vector a single element (position).

inline iterator erase(const_iterator first, const_iterator last)

Removes from the vector either a range of elements ([first,last)).

inline void swap(small_vector<T, S> &other)

Exchanges the content of the container by the content of x, which is another vector object of the same type. Sizes may differ.

inline void clear()

Removes all elements from the vector (which are destroyed), leaving the container with a size of 0.

template<typename ...Args>
inline void emplace_back(Args&&... args)

Inserts a new element at the end of the vector, right after its current last element. This new element is constructed in place using args as the arguments for its constructor.

inline ~small_vector()

destructor

inline small_vector(const small_vector &other)

copy constructor

inline small_vector(small_vector &&other)

copy and swap constructor

Friends

inline friend void swap(small_vector<T, S> &lhs, small_vector<T, S> &rhs)

swaps two vectors

inline friend bool operator==(const small_vector<T, S> &lhs, const small_vector<T, S> &rhs)

== p[erator

inline friend bool operator<(const small_vector<T, S> &lhs, const small_vector<T, S> &rhs)

< operator

inline friend bool operator!=(const small_vector<T, S> &lhs, const small_vector<T, S> &rhs)

!= operator

inline friend bool operator>(const small_vector<T, S> &lhs, const small_vector<T, S> &rhs)

> operator

inline friend bool operator<=(const small_vector<T, S> &lhs, const small_vector<T, S> &rhs)

<= operator

inline friend bool operator>=(const small_vector<T, S> &lhs, const small_vector<T, S> &rhs)

>= operator

vtr_vector_map

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.

template<typename K, typename V, typename Sentinel = DefaultSentinel<V>>
class vector_map

#include <vtr_vector_map.h>

A vector-like container which is indexed by K (instead of size_t as in std::vector).

The main use of this container is to behave like a std::vector which is indexed by vtr::StrongId.

Requires that K be convertable to size_t with the size_t operator (i.e. size_t()), and that the conversion results in a linearly increasing index into the underlying vector.

This results in a container that is somewhat similar to a std::map (i.e. converts from one type to another), but requires contiguously ascending (i.e. linear) keys. Unlike std::map only the values are stored (at the specified index/key), reducing memory usage and improving cache locality. Furthermore, operator[] and find() return the value or iterator directly associated with the value (like std::vector) rather than a std::pair (like std::map). insert() takes both the key and value as separate arguments and has no return value.

Additionally, vector_map will silently create values for ‘gaps’ in the index range (i.e. those elements are initialized with Sentinel::INVALID()).

If you need a fully featured std::map like container without the above differences see vtr::linear_map.

If you do not need std::map-like features see vtr::vector. Note that vtr::vector_map is very similar to vtr::vector. Unless there is a specific reason that vtr::vector_map is needed, it is better to use vtr::vector.

Note that it is possible to use vector_map with sparse/non-contiguous keys, but this is typically memory inefficient as the underlying vector will allocate space for [0..size_t(max_key)-1], where max_key is the largest key that has been inserted.

As with a std::vector, it is the caller’s responsibility to ensure there is sufficient space when a given index/key before it is accessed. The exception to this are the find(), insert() and update() methods which handle non-existing keys gracefully.

Public Functions

template<typename ...Args>
inline vector_map(Args&&... args)

Constructor.

inline const_iterator begin() const

Returns an iterator referring to the first element in the map container.

inline const_iterator end() const

Returns an iterator referring to the past-the-end element in the map container.

inline const_reverse_iterator rbegin() const

@begin Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).

inline const_reverse_iterator rend() const

Returns a reverse iterator pointing to the theoretical element right before the first element in the map container (which is considered its reverse end).

inline const_reference operator[](const K n) const

[] operator immutable

inline const_iterator find(const K key) const

Searches the container for an element with a key equivalent to k and returns an iterator to it if found, otherwise it returns an iterator to vector_map::end.

inline std::size_t size() const

Returns the number of elements in the container.

inline bool empty() const

Returns true if the container is empty.

inline bool contains(const K key) const

Returns true if the container contains key.

inline size_t count(const K key) const

Returns 1 if the container contains key, 0 otherwise.

template<typename ...Args>
inline void push_back(Args&&... args)

push_back function

template<typename ...Args>
inline void emplace_back(Args&&... args)

emplace_back function

template<typename ...Args>
inline void resize(Args&&... args)

resize function

inline void clear()

clears the container

inline size_t capacity() const

Returns the capacity of the container.

inline void shrink_to_fit()

Requests the container to reduce its capacity to fit its size.

inline iterator begin()

Returns an iterator referring to the first element in the map container.

inline iterator end()

Returns an iterator referring to the past-the-end element in the map container.

inline reference operator[](const K n)

Indexing.

inline iterator find(const K key)

Returns an iterator to the first element in the container that compares equal to val. If no such element is found, the function returns end().

inline void insert(const K key, const V value)

Extends the container by inserting new elements, effectively increasing the container size by the number of elements inserted.

inline void update(const K key, const V value)

Inserts the new key value pair in the container.

vtr_linear_map

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.

template<class K, class T, class Sentinel = DefaultSentinel<K>>
class linear_map

#include <vtr_linear_map.h>

A std::map-like container which is indexed by K.

The main use of this container is to behave like a std::map which is optimized to hold mappings between a dense linear range of keys (e.g. vtr::StrongId).

Requires that K be convertable to size_t with the size_t operator (i.e. size_t()), and that the conversion results in a linearly increasing index into the underlying vector. Also requires that K() return the sentinel value used to mark invalid entries.

If you only need to access the value associated with the key consider using vtr::vector_map instead, which provides a similar but more std::vector-like interface.

Note that it is possible to use linear_map with sparse/non-contiguous keys, but this is typically memory inefficient as the underlying vector will allocate space for [0..size_t(max_key)-1], where max_key is the largest key that has been inserted.

As with a std::vector, it is the caller’s responsibility to ensure there is sufficient space when a given index/key before it is accessed. The exception to this are the find() and insert() methods which handle non-existing keys gracefully.

Public Functions

linear_map() = default

Standard big 5 constructors.

linear_map(const linear_map&) = default

linear_map(linear_map&&) = default

linear_map &operator=(const linear_map&) = default

linear_map &operator=(linear_map&&) = default

inline linear_map(size_t num_keys)

inline iterator begin()

Return an iterator to the first element.

inline const_iterator begin() const

Return a constant iterator to the first element.

inline iterator end()

Return an iterator to the last element.

inline const_iterator end() const

Return a constant iterator to the last element.

inline reverse_iterator rbegin()

Return a reverse iterator to the last element.

inline const_reverse_iterator rbegin() const

Return a constant reverse iterator to the last element.

inline reverse_iterator rend()

Return a reverse iterator pointing to the theoretical element preceding the first element.

inline const_reverse_iterator rend() const

Return a constant reverse iterator pointing to the theoretical element preceding the first element.

inline const_iterator cbegin() const

Return a const iterator to the first element.

inline const_iterator cend() const

Return a const_iterator pointing to the past-the-end element in the container.

inline const_reverse_iterator crbegin() const

Return a const_reverse_iterator pointing to the last element in the container (i.e., its reverse beginning).

inline const_reverse_iterator crend() const

Return a const_reverse_iterator pointing to the theoretical element preceding the first element in the container (which is considered its reverse end).

inline bool empty() const

Return true if the container is empty.

inline size_type size() const

Return the size of the container.

inline size_type max_size() const

Return the maximum size of the container.

inline mapped_type &operator[](const key_type &key)

[] operator

inline mapped_type &at(const key_type &key)

at() operator

inline const mapped_type &at(const key_type &key) const

constant at() operator

inline std::pair<iterator, bool> insert(const value_type &value)

Insert value.

template<class InputIterator>
inline void insert(InputIterator first, InputIterator last)

Insert range.

inline void erase(const key_type &key)

Erase by key.

inline void erase(const_iterator position)

Erase at iterator.

inline void erase(const_iterator first, const_iterator last)

Erase range.

inline void swap(linear_map &other)

Swap two linear maps.

inline void clear()

Clear the container.

template<class ...Args>
inline std::pair<iterator, bool> emplace(const key_type &key, Args&&... args)

Emplace.

inline void reserve(size_type n)

Requests that the underlying vector capacity be at least enough to contain n elements.

inline void shrink_to_fit()

Reduces the capacity of the container to fit its size and destroys all elements beyond the capacity.

inline iterator find(const key_type &key)

Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.

inline const_iterator find(const key_type &key) const

Returns a constant iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.

inline size_type count(const key_type &key) const

Returns the number of elements in the range [first,last) that compare equal to val.

inline iterator lower_bound(const key_type &key)

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

inline const_iterator lower_bound(const key_type &key) const

Returns a constant iterator pointing to the first element in the range [first,last) which does not compare less than val.

inline iterator upper_bound(const key_type &key)

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

inline const_iterator upper_bound(const key_type &key) const

Returns a constant iterator pointing to the first element in the range [first,last) which compares greater than val.

inline std::pair<iterator, iterator> equal_range(const key_type &key)

Returns the bounds of the subrange that includes all the elements of the range [first,last) with values equivalent to val.

inline std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const

Returns constant bounds of the subrange that includes all the elements of the range [first,last) with values equivalent to val.

inline size_type valid_size() const

Return the size of valid elements.

vtr_flat_map

template<class K, class T, class Compare, class Storage>
class flat_map

flat_map is a (nearly) std::map compatible container

It uses a vector as it’s underlying storage. Internally the stored elements are kept sorted allowing efficient look-up in O(logN) time via binary search.

This container is typically useful in the following scenarios:

• Reduced memory usage if key/value are small (std::map needs to store pointers to other BST nodes which can add substantial overhead for small keys/values)

• Faster search/iteration by exploiting data locality (all elments are in continguous memory enabling better spatial locality)

The container deviates from the behaviour of std::map in the following important ways:

• Insertion/erase takes O(N) instead of O(logN) time

• Iterators may be invalidated on insertion/erase (i.e. if the vector is reallocated)

The slow insertion/erase performance makes this container poorly suited to maps that frequently add/remove new keys. If this is required you likely want std::map or std::unordered_map. However if the map is constructed once and then repeatedly quieried, consider using the range or vector-based constructors which initializes the flat_map in O(NlogN) time.

Subclassed by vtr::flat_map2< K, T, Compare, Storage >

Public Functions

flat_map() = default

Standard constructors.

template<class InputIterator>
inline flat_map(InputIterator first, InputIterator last)

range constructor

inline explicit flat_map(Storage &&values)

direct vector constructor

inline void assign(Storage &&values)

Move the values.

Should be more efficient than the range constructor which must copy each element

inline void assign_sorted(Storage &&values)

By moving the values this should be more efficient than the range constructor which must copy each element.

inline iterator begin()

Return an iterator pointing to the first element in the sequence:

inline const_iterator begin() const

Return a constant iterator pointing to the first element in the sequence:

inline iterator end()

Returns an iterator referring to the past-the-end element in the vector container.

inline const_iterator end() const

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

inline reverse_iterator rbegin()

Returns a reverse iterator which points to the last element of the map.

inline const_reverse_iterator rbegin() const

Returns a constant reverse iterator which points to the last element of the map.

inline reverse_iterator rend()

Returns a reverse iterator pointing to the theoretical element preceding the first element in the vector (which is considered its reverse end).

inline const_reverse_iterator rend() const

Returns a constant reverse iterator pointing to the theoretical element preceding the first element in the vector (which is considered its reverse end).

inline const_iterator cbegin() const

Returns a constant_iterator to the first element in the underlying vector.

inline const_iterator cend() const

Returns a const_iterator pointing to the past-the-end element in the container.

inline const_reverse_iterator crbegin() const

Returns a const_reverse_iterator pointing to the last element in the container (i.e., its reverse beginning).

inline const_reverse_iterator crend() const

Returns a const_reverse_iterator pointing to the theoretical element preceding the first element in the container (which is considered its reverse end).

inline bool empty() const

Return true if the underlying vector is empty.

inline size_type size() const

Return the container size.

inline size_type max_size() const

Return the underlying vector’s max size.

inline const mapped_type &operator[](const key_type &key) const

The constant version of operator [].

inline mapped_type &operator[](const key_type &key)

operator []

inline mapped_type &at(const key_type &key)

operator at()

inline const mapped_type &at(const key_type &key) const

The constant version of at() operator.

inline std::pair<iterator, bool> insert(const value_type &value)

Insert value.

inline std::pair<iterator, bool> emplace(const value_type &&value)

Emplace function.

inline iterator insert(const_iterator position, const value_type &value)

Insert value with position hint.

inline iterator emplace(const_iterator position, const value_type &value)

Emplace value with position hint.

template<class InputIterator>
inline void insert(InputIterator first, InputIterator last)

Insert range.

inline void erase(const key_type &key)

Erase by key.

inline void erase(const_iterator position)

Erase at iterator.

inline void erase(const_iterator first, const_iterator last)

Erase range.

inline void swap(flat_map &other)

swap two flat maps

inline void clear()

clear the flat map

template<class ...Args>
inline iterator emplace(const key_type &key, Args&&... args)

templated emplace function

template<class ...Args>
inline iterator emplace_hint(const_iterator position, Args&&... args)

templated emplace_hint function

inline void reserve(size_type n)

Reserve a minimum capacity for the underlying vector.

inline void shrink_to_fit()

Reduce the capacity of the underlying vector to fit its size.

inline iterator find(const key_type &key)

Find a key and return an iterator to the found key.

inline const_iterator find(const key_type &key) const

Find a key and return a constant iterator to the found key.

inline size_type count(const key_type &key) const

Return the count of occurances of a key.

inline iterator lower_bound(const key_type &key)

lower bound function

inline const_iterator lower_bound(const key_type &key) const

Return a constant iterator to the lower bound.

inline iterator upper_bound(const key_type &key)

upper bound function

inline const_iterator upper_bound(const key_type &key) const

Return a constant iterator to the upper bound.

inline std::pair<iterator, iterator> equal_range(const key_type &key)

Returns a range containing all elements equivalent to “key”.

inline std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const

Returns a constant range containing all elements equivalent to “key”.

Friends

inline friend void swap(flat_map &lhs, flat_map &rhs)

Swaps 2 flat maps.

class value_compare

A class to perform the comparison operation for the flat map.

template<class K, class T, class Compare, class Storage>
class flat_map2 : public vtr::flat_map<K, T, Compare, Storage>

Another flat_map container.

Like flat_map, but operator[] never inserts and directly returns the mapped value

Public Functions

inline flat_map2()

Constructor.

inline const T &operator[](const K &key) const

const [] operator

inline T &operator[](const K &key)

[] operator

namespace vtr

Functions

template<class K, class V>
flat_map<K, V> make_flat_map(std::vector<std::pair<K, V>> &&vec)

A function to create a flat map.

Helper function to create a flat map from a vector of pairs without haveing to explicity specify the key and value types

template<class K, class V>
flat_map2<K, V> make_flat_map2(std::vector<std::pair<K, V>> &&vec)

Same as make_flat_map but for flat_map2.

vtr_bimap

The vtr_bimap.h header provides a bi-directonal mapping between key and value which means that it can be addressed by either the key or the value.

It provides this bi-directional feature for all the map-like containers defined in vtr:

• unordered map

• flat map

• linear map

One example where this container might be so useful is the mapping between the atom and clustered net Id. See atom_lookup.h

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.

template<class K, class V, template<typename...> class Map = std::map, template<typename...> class InvMap = std::map>
class bimap

#include <vtr_bimap.h>

A map-like class which provides a bi-directonal mapping between key and value.

Keys and values can be looked up directly by passing either the key or value. the indexing operator will throw if the key/value does not exist.

Public Functions

inline iterator begin() const

Return an iterator to the begin of the map.

inline iterator end() const

Return an iterator to the end of the map.

inline inverse_iterator inverse_begin() const

Return an iterator to the begin of the inverse map.

inline inverse_iterator inverse_end() const

Return an iterator to the end of the inverse map.

inline iterator find(const K key) const

Return an iterator to the key-value pair matching key, or end() if not found.

inline inverse_iterator find(const V value) const

Return an iterator to the value-key pair matching value, or inverse_end() if not found.

inline const V &operator[](const K key) const

Return an immutable reference to the value matching key (throw an exception if key is not found)

inline const K &operator[](const V value) const

Return an immutable reference to the key matching value (throw an exception if value is not found)

inline std::size_t size() const

Return the number of key-value pairs stored.

inline bool empty() const

Return true if there are no key-value pairs stored.

inline bool contains(const K key) const

Return true if the specified key exists.

inline bool contains(const V value) const

Return true if the specified value exists.

bimap() = default

default constructor required by compiler

inline bimap(std::initializer_list<value_type> il)

construct the bimap using initializer list with value_type

inline bimap(std::initializer_list<inverse_value_type> il)

construct the bimap using initializer list with inverse_value_type

inline void clear()

Drop all stored key-values.

inline std::pair<iterator, bool> insert(const K key, const V value)

Insert a key-value pair, if not already in map.

inline void update(const K key, const V value)

Update a key-value pair, will insert if not already in map.

inline void erase(const K key)

Remove the specified key (and it’s associated value)

inline void erase(const V val)

Remove the specified value (and it’s associated key)

Typedefs

template<class K, class V>
using unordered_bimap = bimap<K, V, std::unordered_map, std::unordered_map>

template<class K, class V>
using flat_bimap = bimap<K, V, vtr::flat_map, vtr::flat_map>

template<class K, class V>
using linear_bimap = bimap<K, V, vtr::linear_map, vtr::linear_map>

vtr_vec_id_set

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.

template<typename T>
class vec_id_set

#include <vtr_vec_id_set.h>

Implements a set-like interface which supports multiple operations.

The supported operations are:

• insertion

• iteration

• membership test all in constant time.

It assumes the element type (T) is convertable to size_t. Usually, elements are vtr::StrongIds.

Iteration through the elements is not strictly ordered, usually insertion order, unless sort() has been previously called.

The underlying implementation uses a vector for element storage (for iteration), and a bit-set for membership tests.

Public Functions

inline auto begin() const

Returns an iterator to the first element in the sequence.

inline auto end() const

Returns an iterator referring to the past-the-end element in the vector container.

inline auto cbegin() const

Returns a constant iterator to the first element in the sequence.

inline auto cend() const

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

inline bool insert(T val)

Insert val in the set.

template<typename Iter>
inline void insert(Iter first, Iter last)

Iterators specifying a range of elements. Copies of the elements in the range [first,last) are inserted in the container.

inline size_t count(T val) const

Count elements with a specific value.

inline size_t size() const

Returns the size of the container.

inline void sort()

Sort elements in the container.

inline void clear()

@bried Clears the container

vtr_list

Linked lists of void pointers and integers, respectively.

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.

struct t_linked_vptr

#include <vtr_list.h>

Linked list node struct.

t_linked_vptr *vtr::insert_in_vptr_list(t_linked_vptr *head, void *vptr_to_add)

Inserts a node to a list.

t_linked_vptr *vtr::delete_in_vptr_list(t_linked_vptr *head)

Delete a list.

vtr_ragged_matrix

template<typename T, typename Index0 = size_t, typename Index1 = size_t>
class FlatRaggedMatrix

A 2 dimensional ‘ragged’ matrix with rows indexed by Index0, and each row of variable length (indexed by Index1)

Example:

  std::vector<int> row_sizes = {1, 5, 3, 10};
  FlatRaggedMatrix<float> matrix(row_sizes);

  //Fill in all entries with ascending values
  float value = 1.;
  for (size_t irow = 0; irow < row_sizes.size(); ++irow) {
      for (size_t icol = 0; icol < row_sizes[irow]; ++icoll) {
          matrix[irow][icol] = value;
          value += 1.;
      }
  }

For efficiency, this class uses a flat memory layout, where all elements are laid out contiguiously (one row after another).

Expects Index0 and Index1 to be convertable to size_t.

Public Functions

FlatRaggedMatrix() = default

default constructor

template<class Callback>
inline FlatRaggedMatrix(size_t nrows, Callback &row_length_callback, T default_value = T())

Constructs matrix with ‘nrows’ rows.

The row length is determined by calling ‘row_length_callback’ with the associated row index.

template<class Container>
inline FlatRaggedMatrix(Container container, T default_value = T())

Constructs matrix from a container of row lengths.

template<class Iter>
inline FlatRaggedMatrix(Iter row_size_first, Iter row_size_last, T default_value = T())

Constructs matrix from an iterator range.

The length of the range is the number of rows, and iterator values are the row lengths.

inline auto begin()

Iterators to all elements.

inline auto end()

Iterator to the last element of the matrix.

inline auto begin() const

Iterator to the first element of the matrix (immutable)

inline auto end() const

Iterator to the last element of the matrix (immutable)

inline size_t size() const

Return the size of the matrix.

inline bool empty() const

Return true if empty.

inline vtr::array_view<T> operator[](Index0 i)

Indexing operators for the first dimension.

inline vtr::array_view<const T> operator[](Index0 i) const

Indexing operators for the first dimension (immutable)

inline void clear()

Clears the matrix.

inline void swap(FlatRaggedMatrix<T, Index0, Index1> &other)

Swaps two matrices.

Friends

inline friend void swap(FlatRaggedMatrix<T, Index0, Index1> &lhs, FlatRaggedMatrix<T, Index0, Index1> &rhs)

Swaps two matrices.

template<typename U>
class ProxyRow

Proxy class used to represent a ‘row’ in the matrix.

Public Functions

inline ProxyRow(U *first, U *last)

constructor

inline U *begin()

Return iterator to the first element.

inline U *end()

Return iterator to the last element.

inline const U *begin() const

Return iterator to the first element (immutable)

inline const U *end() const

Return iterator to the last element (immutable)

inline size_t size() const

Return the size of the row.

inline U &operator[](Index1 j)

indexing [] operator

inline const U &operator[](Index1 j) const

indexing [] operator (immutable)

inline U *data()

Return iterator to the first element.

inline U *data() const

Return iterator to the first element (immutable)

vtr_ndmatrix

namespace vtr

template<typename T, size_t N>
class NdMatrixProxy

#include <vtr_ndmatrix.h>

Proxy class for a sub-matrix of a NdMatrix class.

This is used to allow chaining of array indexing [] operators in a natural way.

Each instance of this class peels off one-dimension and returns a NdMatrixProxy representing the resulting sub-matrix. This is repeated recursively until we hit the 1-dimensional base-case.

Since this expansion happens at compiler time all the proxy classes get optimized away, yielding both high performance and generality.

Recursive case: N-dimensional array

Public Functions

inline NdMatrixProxy(const size_t *dim_sizes, const size_t *dim_strides, T *start)

Construct a matrix proxy object.

Parameters:

• dim_sizes – Array of dimension sizes

• idim – The dimension associated with this proxy

• dim_stride – The stride of this dimension (i.e. how many element in memory between indicies of this dimension)

• start – Pointer to the start of the sub-matrix this proxy represents

NdMatrixProxy<T, N> &operator=(const NdMatrixProxy<T, N> &other) = delete

inline const NdMatrixProxy<T, N - 1> operator[](size_t index) const

const [] operator

inline NdMatrixProxy<T, N - 1> operator[](size_t index)

[] operator

template<typename T>
class NdMatrixProxy<T, 1>

#include <vtr_ndmatrix.h>

Base case: 1-dimensional array.

Public Functions

inline NdMatrixProxy(const size_t *dim_sizes, const size_t *dim_stride, T *start)

Construct a 1-d matrix proxy object.

Parameters:

• dim_sizes – Array of dimension sizes

• dim_stride – The stride of this dimension (i.e. how many element in memory between indicies of this dimension)

• start – Pointer to the start of the sub-matrix this proxy represents

NdMatrixProxy<T, 1> &operator=(const NdMatrixProxy<T, 1> &other) = delete

inline const T &operator[](size_t index) const

const [] operator

inline T &operator[](size_t index)

[] operator

inline const T *data() const

Backward compitability.

For legacy compatibility (i.e. code expecting a pointer) we allow this base dimension case to retrieve a raw pointer to the last dimension elements.

Note that it is the caller’s responsibility to use this correctly; care must be taken not to clobber elements in other dimensions

inline T *data()

same as above but allow update the value

template<typename T, size_t N>
class NdMatrixBase

#include <vtr_ndmatrix.h>

Base class for an N-dimensional matrix.

Base class for an N-dimensional matrix supporting arbitrary index ranges per dimension. This class implements all of the matrix handling (lifetime etc.) except for indexing (which is implemented in the NdMatrix class). Indexing is split out to allows specialization (of indexing for N = 1.

Implementation:

This class uses a single linear array to store the matrix in c-style (row major) order. That is, the right-most index is laid out contiguous memory.

This should improve memory usage (no extra pointers to store for each dimension), and cache locality (less indirection via pointers, predictable strides).

The indicies are calculated based on the dimensions to access the appropriate elements. Since the indexing calculations are visible to the compiler at compile time they can be optimized to be efficient.

Public Functions

inline NdMatrixBase()

An empty matrix (all dimensions size zero)

inline NdMatrixBase(std::array<size_t, N> dim_sizes, T value = T())

Specified dimension sizes:

 [0..dim_sizes[0])
 [0..dim_sizes[1])
 ...
 with optional fill value

inline size_t size() const

Returns the size of the matrix (number of elements)

inline bool empty() const

Returns true if there are no elements in the matrix.

inline size_t ndims() const

Returns the number of dimensions (i.e. N)

inline size_t dim_size(size_t i) const

Returns the size of the ith dimension.

inline size_t begin_index(size_t i) const

Returns the starting index of ith dimension.

inline size_t end_index(size_t i) const

Returns the one-past-the-end index of the ith dimension.

inline const T &get(size_t i) const

const Flat accessors of NdMatrix

inline T &get(size_t i)

Flat accessors of NdMatrix.

inline void fill(T value)

Set all elements to ‘value’.

inline void resize(std::array<size_t, N> dim_sizes, T value = T())

Resize the matrix to the specified dimension ranges.

If ‘value’ is specified all elements will be initialized to it, otherwise they will be default constructed.

inline void clear()

Reset the matrix to size zero.

inline NdMatrixBase(const NdMatrixBase &other)

Copy constructor.

inline NdMatrixBase(NdMatrixBase &&other)

Move constructor.

inline NdMatrixBase &operator=(NdMatrixBase rhs)

Copy/move assignment.

Note that rhs is taken by value (copy-swap idiom)

template<typename T, size_t N>
class NdMatrix : public vtr::NdMatrixBase<T, N>

#include <vtr_ndmatrix.h>

An N-dimensional matrix supporting arbitrary (continuous) index ranges per dimension.

Examples:

  //A 2-dimensional matrix with indicies [0..4][0..9]
  NdMatrix<int,2> m1({5,10});

  //Accessing an element
  int i = m1[3][5];

  //Setting an element
  m1[2][8] = 0;

  //A 3-dimensional matrix with indicies [0..4][0..9][0..19]
  NdMatrix<int,3> m2({5,10,20});

  //A 2-dimensional matrix with indicies [0..4][0..9], with all entries
  //initialized to 42
  NdMatrix<int,2> m3({5,10}, 42);

  //Filling all entries with value 101
  m3.fill(101);

  //Resizing an existing matrix (all values reset to default constucted value)
  m3.resize({5,5})

  //Resizing an existing matrix (all elements set to value 88)
  m3.resize({15,55}, 88)

Public Functions

inline const NdMatrixProxy<T, N - 1> operator[](size_t index) const

Access an element.

Returns a proxy-object to allow chained array-style indexing (N >= 2 case)

inline NdMatrixProxy<T, N - 1> operator[](size_t index)

Access an element.

Returns a proxy-object to allow chained array-style indexing

template<typename T>
class NdMatrix<T, 1> : public vtr::NdMatrixBase<T, 1>

#include <vtr_ndmatrix.h>

A 1-dimensional matrix supporting arbitrary (continuous) index ranges per dimension.

This is considered a specialization for N=1

Public Functions

inline const T &operator[](size_t index) const

Access an element (immutable)

inline T &operator[](size_t index)

Access an element (mutable)

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.

Typedefs

template<typename T>
using Matrix = NdMatrix<T, 2>

Convenient short forms for common NdMatricies.

vtr_ndoffsetmatrix

namespace vtr

class DimRange

#include <vtr_ndoffsetmatrix.h>

A half-open range specification for a matrix dimension [begin_index, last_index)

It comes with valid indicies from [begin_index() … end_index()-1], provided size() > 0.

Public Functions

DimRange() = default

default constructor

inline DimRange(size_t begin, size_t end)

a constructor with begin_index, end_index

inline size_t begin_index() const

Return the begin index.

inline size_t end_index() const

Return the end index.

inline size_t size() const

Return the size.

template<typename T, size_t N>
class NdOffsetMatrixProxy

#include <vtr_ndoffsetmatrix.h>

Proxy class for a sub-matrix of a NdOffsetMatrix class.

This is used to allow chaining of array indexing [] operators in a natural way.

Each instance of this class peels off one-dimension and returns a NdOffsetMatrixProxy representing the resulting sub-matrix. This is repeated recursively until we hit the 1-dimensional base-case.

Since this expansion happens at compiler time all the proxy classes get optimized away, yielding both high performance and generality.

Recursive case: N-dimensional array

Public Functions

inline NdOffsetMatrixProxy(const DimRange *dim_ranges, size_t idim, size_t dim_stride, T *start)

Construct a matrix proxy object.

dim_ranges: Array of DimRange objects idim: The dimension associated with this proxy dim_stride: The stride of this dimension (i.e. how many element in memory between indicies of this dimension) start: Pointer to the start of the sub-matrix this proxy represents

inline const NdOffsetMatrixProxy<T, N - 1> operator[](size_t index) const

const [] operator

inline NdOffsetMatrixProxy<T, N - 1> operator[](size_t index)

[] operator

template<typename T>
class NdOffsetMatrixProxy<T, 1>

#include <vtr_ndoffsetmatrix.h>

Base case: 1-dimensional array.

Public Functions

inline NdOffsetMatrixProxy(const DimRange *dim_ranges, size_t idim, size_t dim_stride, T *start)

Construct a matrix proxy object.

- dim_ranges: Array of DimRange objects
- dim_stride: The stride of this dimension (i.e. how many element in memory between indicies of this dimension)
- start: Pointer to the start of the sub-matrix this proxy represents

inline const T &operator[](size_t index) const

const [] operator

inline T &operator[](size_t index)

[] operator

template<typename T, size_t N>
class NdOffsetMatrixBase

#include <vtr_ndoffsetmatrix.h>

Base class for an N-dimensional matrix supporting arbitrary index ranges per dimension.

This class implements all of the matrix handling (lifetime etc.) except for indexing (which is implemented in the NdOffsetMatrix class). Indexing is split out to allows specialization of indexing for N = 1.

Implementation:

This class uses a single linear array to store the matrix in c-style (row major) order. That is, the right-most index is laid out contiguous memory.

This should improve memory usage (no extra pointers to store for each dimension), and cache locality (less indirection via pointers, predictable strides).

The indicies are calculated based on the dimensions to access the appropriate elements. Since the indexing calculations are visible to the compiler at compile time they can be optimized to be efficient.

Public Functions

inline NdOffsetMatrixBase()

An empty matrix (all dimensions size zero)

inline NdOffsetMatrixBase(std::array<size_t, N> dim_sizes, T value = T())

Specified dimension sizes:

 [0..dim_sizes[0])
 [0..dim_sizes[1])
 ...

with optional fill value

inline NdOffsetMatrixBase(std::array<DimRange, N> dim_ranges, T value = T())

Specified dimension index ranges:

 [dim_ranges[0].begin_index() ... dim_ranges[1].end_index())
 [dim_ranges[1].begin_index() ... dim_ranges[1].end_index())
 ...

with optional fill value

inline size_t size() const

Returns the size of the matrix (number of elements)

inline bool empty() const

Returns true if there are no elements in the matrix.

inline size_t ndims() const

Returns the number of dimensions (i.e. N)

inline size_t dim_size(size_t i) const

Returns the size of the ith dimension.

inline size_t begin_index(size_t i) const

Returns the starting index of ith dimension.

inline size_t end_index(size_t i) const

Returns the one-past-the-end index of the ith dimension.

inline void fill(T value)

Set all elements to ‘value’.

inline void resize(std::array<size_t, N> dim_sizes, T value = T())

Resize the matrix to the specified dimensions.

If ‘value’ is specified all elements will be initialized to it, otherwise they will be default constructed.

inline void resize(std::array<DimRange, N> dim_ranges, T value = T())

Resize the matrix to the specified dimension ranges.

If ‘value’ is specified all elements will be initialized to it, otherwise they will be default constructed.

inline void clear()

Reset the matrix to size zero.

inline NdOffsetMatrixBase(const NdOffsetMatrixBase &other)

Copy constructor.

inline NdOffsetMatrixBase(NdOffsetMatrixBase &&other)

Move constructor.

inline NdOffsetMatrixBase &operator=(NdOffsetMatrixBase rhs)

Copy/move assignment.

Note that rhs is taken by value (copy-swap idiom)

template<typename T, size_t N>
class NdOffsetMatrix : public vtr::NdOffsetMatrixBase<T, N>

#include <vtr_ndoffsetmatrix.h>

An N-dimensional matrix supporting arbitrary (continuous) index ranges per dimension.

If no second template parameter is provided defaults to a 2-dimensional matrix

Examples:

  //A 2-dimensional matrix with indicies [0..4][0..9]
  NdOffsetMatrix<int,2> m1({5,10});

  //Accessing an element
  int i = m4[3][5];

  //Setting an element
  m4[6][20] = 0;

  //A 2-dimensional matrix with indicies [2..6][5..9]
  // Note that C++ requires one more set of curly brace than you would expect
  NdOffsetMatrix<int,2> m2({{{2,7},{5,10}}});

  //A 3-dimensional matrix with indicies [0..4][0..9][0..19]
  NdOffsetMatrix<int,3> m3({5,10,20});

  //A 3-dimensional matrix with indicies [2..6][1..19][50..89]
  NdOffsetMatrix<int,3> m4({{{2,7}, {1,20}, {50,90}}});

  //A 2-dimensional matrix with indicies [2..6][1..20], with all entries
  //intialized to 42
  NdOffsetMatrix<int,2> m4({{{2,7}, {1,21}}}, 42);

  //A 2-dimensional matrix with indicies [0..4][0..9], with all entries
  //initialized to 42
  NdOffsetMatrix<int,2> m1({5,10}, 42);

  //Filling all entries with value 101
  m1.fill(101);

  //Resizing an existing matrix (all values reset to default constucted value)
  m1.resize({5,5})

  //Resizing an existing matrix (all elements set to value 88)
  m1.resize({15,55}, 88)

Public Functions

inline const NdOffsetMatrixProxy<T, N - 1> operator[](size_t index) const

Access an element.

Returns a proxy-object to allow chained array-style indexing (N >= 2 case) template<typename = typename std::enable_if<N >= 2>::type, typename T1=T>

inline NdOffsetMatrixProxy<T, N - 1> operator[](size_t index)

Access an element.

Returns a proxy-object to allow chained array-style indexing

template<typename T>
class NdOffsetMatrix<T, 1> : public vtr::NdOffsetMatrixBase<T, 1>

#include <vtr_ndoffsetmatrix.h>

A 1-dimensional matrix supporting arbitrary (continuous) index ranges per dimension.

This is considered a specialization for N=1

Public Functions

inline const T &operator[](size_t index) const

Access an element (immutable)

inline T &operator[](size_t index)

Access an element (mutable)

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.

Typedefs

template<typename T>
using OffsetMatrix = NdOffsetMatrix<T, 2>

Convenient short forms for common NdMatricies.

vtr_array_view

template<typename K, typename V>
class array_view_id : private vtr::array_view<V>

Implements a fixed length view to an array which is indexed by vtr::StrongId.

The main use of this container is to behave like a std::span which is indexed by a vtr::StrongId instead of size_t. It assumes that K is explicitly convertable to size_t (i.e. via operator size_t()), and can be explicitly constructed from a size_t.

Public Functions

inline V &operator[](const key_type id)

[] operator

inline const V &operator[](const key_type id) const

constant [] operator

inline V &at(const key_type id)

at() operator

inline const V &at(const key_type id) const

constant at() operator

inline key_range keys() const

Returns a range containing the keys.

class key_iterator : public std::iterator<std::bidirectional_iterator_tag, key_type>

Iterator class which is convertable to the key_type.

This allows end-users to call the parent class’s keys() member to iterate through the keys with a range-based for loop

Public Types

using my_iter = typename std::iterator<std::bidirectional_iterator_tag, K>

Intermediate type my_iter.

We use the intermediate type my_iter to avoid a potential ambiguity for which clang generates errors and warnings

Public Functions

inline key_iterator operator++()

Note.

vtr::vector assumes that the key time is convertable to size_t and that all the underlying IDs are zero-based and contiguous. That means we can just increment the underlying Id to build the next key.

increment the iterator

inline key_iterator operator--()

decrement the iterator

inline reference operator*()

dereference operator (*)

inline pointer operator->()

-> operator

template<typename T>
class array_view

An array view class to avoid copying data.

Public Functions

inline explicit constexpr array_view()

default constructor

inline explicit constexpr array_view(T *str, size_t size)

A constructor with data initialization.

inline constexpr T &operator[](size_t pos)

[] operator

inline constexpr const T &operator[](size_t pos) const

constant [] operator

inline T &at(size_t pos)

at() operator

inline const T &at(size_t pos) const

const at() operator

inline constexpr T &front()

get the first element of the array

inline constexpr const T &front() const

get the first element of the array (can’t update it)

inline constexpr T &back()

get the last element of the array

inline constexpr const T &back() const

get the last element of the array (can’t update it)

inline constexpr T *data()

return the underlying pointer

inline constexpr const T *data() const

return the underlying pointer (constant pointer)

inline constexpr size_t size() const noexcept

return thr array size

inline constexpr size_t length() const noexcept

return the array size

inline constexpr bool empty() const noexcept

check if the array is empty

inline constexpr T *begin() noexcept

return a pointer to the first element of the array

inline constexpr const T *begin() const noexcept

return a constant pointer to the first element of the array

inline constexpr const T *cbegin() const noexcept

return a constant pointer to the first element of the array

inline constexpr T *end() noexcept

return a pointer to the last element of the array

inline constexpr const T *end() const noexcept

return a constant pointer to the last element of the array

inline constexpr const T *cend() const noexcept

return a constant pointer to the last element of the array

vtr_string_view

class string_view

Implements a view to a fixed length string (similar to std::basic_string_view).

The underlying string does not need to be NULL terminated.

Public Functions

inline explicit constexpr string_view()

constructor

inline explicit string_view(const char *str)

constructor

inline explicit constexpr string_view(const char *str, size_t size)

constructor

inline constexpr string_view &operator=(const string_view &view) noexcept

copy constructor

inline constexpr char operator[](size_t pos) const

indexing [] operator (immutable)

inline const char &at(size_t pos) const

aT() operator (immutable)

inline constexpr const char &front() const

Returns the first character of the string.

inline constexpr const char &back() const

Returns the last character of the string.

inline constexpr const char *data() const

Returns a pointer to the string data.

inline constexpr size_t size() const noexcept

Returns the string size.

inline constexpr size_t length() const noexcept

Returns the string size.

inline constexpr bool empty() const noexcept

Returns true if empty.

inline constexpr const char *begin() const noexcept

Returns a pointer to the begin of the string.

inline constexpr const char *cbegin() const noexcept

Same as begin()

inline constexpr const char *end() const noexcept

Returns a pointer to the end of the string.

inline constexpr const char *cend() const noexcept

Same as end()

inline void swap(string_view &v) noexcept

Swaps two string views.

inline string_view substr(size_t pos = 0, size_t count = npos)

Returns a newly constructed string object with its value initialized to a copy of a substring of this object.

vtr_cache

template<typename CacheKey, typename CacheValue>
class Cache

An implementation of a simple cache.

Public Functions

inline void clear()

Clear cache.

inline const CacheValue *get(const CacheKey &key) const

Check if the cache is valid.

Returns the cached value if present and valid. Returns nullptr if the cache is invalid.

inline const CacheValue *set(const CacheKey &key, std::unique_ptr<CacheValue> value)

Update the cache.

vtr_dynamic_bitset

template<typename Index = size_t, typename Storage = unsigned int>
class dynamic_bitset

A container to represent a set of flags either they are set or reset.

It allocates any required length of bit at runtime. It is very useful in bit manipulation

Public Functions

inline void resize(size_t size)

Reize to the determined size.

inline void clear()

Clear all the bits.

inline size_t size() const

Return the size of the bitset (total number of bits)

inline void fill(bool set)

Fill the whole bitset with a specific value (0 or 1)

inline void set(Index index, bool val)

Set a specific bit in the bit set to a specific value (0 or 1)

inline bool get(Index index) const

Return the value of a specific bit in the bitset.

inline constexpr size_t count(void) const

Return count of set bits.

inline constexpr dynamic_bitset<Index, Storage> &operator|=(const dynamic_bitset<Index, Storage> &x)

Bitwise OR with rhs. Truncate the operation if one operand is smaller.

inline constexpr dynamic_bitset<Index, Storage> &operator&=(const dynamic_bitset<Index, Storage> &x)

Bitwise AND with rhs. Truncate the operation if one operand is smaller.

inline dynamic_bitset<Index, Storage> operator~(void) const

Return inverted bitset.

Public Static Attributes

static constexpr size_t kWidth = std::numeric_limits<Storage>::digits

Bits in underlying storage.