Utility functions and data structures (C code)

General utility functions

Generic utility functions.

Typedefs

typedef int64_t ct_long

Universal “long” integer, used for tensor dimensions.

Functions

static inline int imin(const int a, const int b)

Minimum of two integers.

static inline int imax(const int a, const int b)

Maximum of two integers.

static inline ct_long lmin(const ct_long a, const ct_long b)

Minimum of two long integers.

static inline ct_long lmax(const ct_long a, const ct_long b)

Maximum of two long integers.

static inline double square(const double x)

Square function x -> x^2.

ct_long integer_product(const ct_long *x, const int n)

Calculate the product of a list of integer numbers.

ct_long ipow(ct_long base, int exp)

Compute the integer power base^exp.

bool is_permutation(const int *map, const int n)

Test whether an integer map is a permutation of the list [0, …, n - 1].

bool is_identity_permutation(const int *perm, const int n)

Whether a permutation is the identity permutation.

double uniform_distance(const enum numeric_type dtype, const ct_long n, const void *x, const void *y)

Uniform distance (infinity norm) between ‘x’ and ‘y’.

The result is cast to double format (even if the actual entries are of single precision).

double norm2(const enum numeric_type dtype, const ct_long n, const void *x)

Euclidean norm of a vector.

Queues

Queue data structure.

Functions

void enqueue(struct queue *q, void *d)

Enqueue an item.

void *dequeue(struct queue *q)

Dequeue an item and return a pointer to it.

void *peek_queue(const struct queue *q)

Return the value of the front item without dequeuing it.

bool queue_is_empty(const struct queue *q)

Indicate whether the queue is empty.

void free_queue(struct queue *q, void (*free_func)(void*))

Delete a queue (free memory).

The function ‘free_func’ is called for each value pointer stored in the queue.

struct queue_node

#include <queue.h>

Node of a queue data structure.

Public Members

void *data

pointer to data entry

struct queue_node *next

pointer to next node

struct queue

#include <queue.h>

Queue data structure.

Public Members

struct queue_node *head

pointer to head node

struct queue_node *tail

pointer to tail node

Linked lists

Doubly linked list.

Functions

static inline bool linked_list_is_empty(const struct linked_list *list)

Indicate whether the linked list is empty.

void linked_list_append(struct linked_list *list, void *d)

Append the item pointed to by ‘d’ to the end of the linked list.

void linked_list_prepend(struct linked_list *list, void *d)

Prepend the item pointed to by ‘d’ to the beginning of the linked list.

void linked_list_insert_after_node(struct linked_list *list, struct linked_list_node *node, void *d)

Insert the item pointed to by ‘d’ after ‘node’ into the linked list.

void linked_list_insert_before_node(struct linked_list *list, struct linked_list_node *node, void *d)

Insert the item pointed to by ‘d’ before ‘node’ into the linked list.

void *linked_list_remove_node(struct linked_list *list, struct linked_list_node *node)

Remove ‘node’ from the linked list (assuming that it is actually part of the linked list), free its memory and return data pointer stored in the node.

void delete_linked_list(struct linked_list *list, void (*free_func)(void*))

Delete a linked list (free memory).

The function ‘free_func’ is called for each data pointer.

bool linked_list_is_consistent(const struct linked_list *list)

Internal consistency check of the doubly linked list structure.

struct linked_list_node

#include <linked_list.h>

Doubly linked list node.

Public Members

void *data

pointer to data entry

struct linked_list_node *prev

pointer to previous node

struct linked_list_node *next

pointer to next node

struct linked_list

#include <linked_list.h>

Doubly linked list data structure.

Public Members

struct linked_list_node *head

pointer to head node

struct linked_list_node *tail

pointer to tail node

ct_long size

number of entries

Hash tables

Separate chaining hash table.

Typedefs

typedef bool hash_table_key_comp(const void *k1, const void *k2)

Key equality test function for a hash table.

typedef uint64_t hash_type

Hash value data type (unsigned integer to ensure that bucket index is non-negative).

typedef hash_type hash_function_type(const void *key)

Hash function type.

Functions

void create_hash_table(hash_table_key_comp *key_equal, hash_function_type *hash_func, const size_t key_size, const ct_long num_buckets, struct hash_table *ht)

Initialize and allocate memory for a hash table.

void delete_hash_table(struct hash_table *ht, void (*free_func)(void*))

Delete a hash table (free memory).

The function ‘free_func’ is called for each value pointer stored in the hash table.

void *hash_table_insert(struct hash_table *ht, void *key, void *val)

Insert an entry into the hash table; if key already exists, replace previous value and return pointer to old value, otherwise return NULL.

void *hash_table_get(const struct hash_table *ht, void *key)

Return a pointer to the value corresponding to ‘key’; if the key is not found, return NULL.

void *hash_table_remove(struct hash_table *ht, void *key)

Remove entry with given key from hash table and return corresponding value; if the key cannot be found, return NULL.

void init_hash_table_iterator(const struct hash_table *table, struct hash_table_iterator *iter)

Initialize a hash table iterator.

bool hash_table_iterator_next(struct hash_table_iterator *iter)

Advance the iterator, returning true if a next element exists.

bool hash_table_iterator_is_valid(const struct hash_table_iterator *iter)

Whether the iterator is still valid, i.e., iteration did not proceed beyond last element.

const void *hash_table_iterator_get_key(struct hash_table_iterator *iter)

Get a pointer to the key of the current iterator element, or NULL if the iterator is invalid.

void *hash_table_iterator_get_value(struct hash_table_iterator *iter)

Get a pointer to the value of the current iterator element, or NULL if the iterator is invalid.

struct hash_table_entry

#include <hash_table.h>

Hash table entry, forming a linked list.

Public Members

struct hash_table_entry *next

pointer to next entry

void *key

pointer to key

void *val

pointer to corresponding value

struct hash_table

#include <hash_table.h>

Associative array using a hash function and linked lists for collisions.

Public Members

hash_table_key_comp *key_equal

key equality test function

hash_function_type *hash_func

hash function

size_t key_size

size of a key, in bytes

struct hash_table_entry **buckets

each bucket is a linked list of entries

ct_long num_buckets

number of buckets

ct_long num_entries

number of entries

struct hash_table_iterator

#include <hash_table.h>

Iterator over the entries of a hash table.

Public Members

const struct hash_table *table

reference to hash table

ct_long i_bucket

bucket index

struct hash_table_entry *entry

pointer to current entry

Abstract (symbolic) graphs

Abstract (symbolic) graph data structure and utility functions.

Functions

void copy_abstract_graph(const struct abstract_graph *src, struct abstract_graph *dst)

Copy an abstract graph.

void delete_abstract_graph(struct abstract_graph *graph)

Delete an abstract graph (free memory).

bool abstract_graph_is_consistent(const struct abstract_graph *graph)

Determine whether the neighborhood map of an abstract graph is consistent.

bool abstract_graph_equal(const struct abstract_graph *graph0, const struct abstract_graph *graph1)

Whether two graphs are logically identical.

bool abstract_graph_is_connected_tree(const struct abstract_graph *graph)

Determine whether an abstract graph is a connected tree.

void enumerate_graph_node_distance_tuples(const struct abstract_graph *graph, const int i_root, struct graph_node_distance_tuple *tuples)

Enumerate node-distance tuples by a recursive tree traversal.

struct abstract_graph

#include <abstract_graph.h>

Abstract undirected graph, defined by neighborhood map.

Public Members

int **neighbor_map

neighborhood map (ordered list of neighbors of each node), defining undirected graph topology

int *num_neighbors

number of neighbors for each node

int num_nodes

number of nodes

struct graph_node_distance_tuple

#include <abstract_graph.h>

Temporary data structure for enumerating graph nodes and their distances to a designated root node.

Public Members

int i_node

node index

int i_parent

parent node index

int distance

distance from root

Bipartite graphs and Hopcroft-Karp algorithm

Bipartite graph utility functions, including an implementation of the Hopcroft-Karp algorithm based on https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm.

Functions

void init_bipartite_graph(const int num_u, const int num_v, const struct bipartite_graph_edge *edges, const int nedges, struct bipartite_graph *graph)

Allocate and initialize a bipartite graph based on the provided edge list.

void delete_bipartite_graph(struct bipartite_graph *graph)

Delete a bipartite graph (free memory).

void bipartite_graph_maximum_cardinality_matching(const struct bipartite_graph *graph, struct bipartite_graph_matching *matching)

Run the Hopcroft-Karp algorithm to find a maximum-cardinality matching.

void bipartite_graph_minimum_vertex_cover(const struct bipartite_graph *graph, bool *u_cover, bool *v_cover)

Find a minimum vertex cover based on Kőnig’s theorem.

struct bipartite_graph

#include <bipartite_graph.h>

Data structure representing a bipartite graph G = ((U, V), E), where ‘U’ and ‘V’ are the vertices in the left and right partition, respectively, and ‘E’ the edges.

Vertices in ‘U’ and ‘V’ are assumed to be sequentially indexed: 0, 1, …

Public Members

int **adj_u

adjacent ‘V’ vertices for each ‘U’ vertex

int **adj_v

adjacent ‘U’ vertices for each ‘V’ vertex

int *num_adj_u

number of adjacent ‘V’ vertices for each ‘U’ vertex

int *num_adj_v

number of adjacent ‘U’ vertices for each ‘V’ vertex

int num_u

number of ‘U’ vertices

int num_v

number of ‘V’ vertices

struct bipartite_graph_edge

#include <bipartite_graph.h>

Bipartite graph edge.

Public Members

int u

‘U’ vertex

int v

‘V’ vertex

struct bipartite_graph_matching

#include <bipartite_graph.h>

Bipartite graph matching.

Public Members

struct bipartite_graph_edge *edges

edges of the matching

int nedges

number of edges

Integer linear algebra operations

Linear algebra operations for integer matrix and vector entries.

Functions

void integer_gemv(const int m, const int n, const int *a, const int *x, int *b)

Compute the matrix-vector product a @ x and store the result in ‘b’.

int integer_hermite_normal_form(const int n, const int *a, int *h, int *u)

Compute the Hermite normal form and the associated unimodular matrix of a square matrix, returning 0 if successful, and interrupting the algorithm if the matrix is singular with return value -1.

int integer_backsubstitute(const int *a, const int n, const int *b, int *x)

Solve the integer linear system ‘a @ x = b’ for ‘x’ by back-substutution, assuming that ‘a’ is an upper triangular matrix with non-zero diagonal entries. Returns 0 if successful, and -1 of no integer solution can be found.

Krylov subspace algorithms

Krylov subspace algorithms.

Typedefs

typedef void lanczos_linear_func_d(const ct_long n, const void *data, const double *v, double *ret)

typedef void lanczos_linear_func_z(const ct_long n, const void *data, const dcomplex *v, dcomplex *ret)

Functions

void lanczos_iteration_d(const ct_long n, lanczos_linear_func_d afunc, const void *adata, const double *vstart, const int maxiter, double *alpha, double *beta, double *v, int *numiter)

Perform a “matrix free” Lanczos iteration for real-valued double precision vectors.

void lanczos_iteration_z(const ct_long n, lanczos_linear_func_z afunc, const void *adata, const dcomplex *vstart, const int maxiter, double *alpha, double *beta, dcomplex *v, int *numiter)

Perform a “matrix free” Lanczos iteration for complex-valued double precision vectors.

int eigensystem_krylov_symmetric(const ct_long n, lanczos_linear_func_d afunc, const void *adata, const double *vstart, const int maxiter, const int numeig, double *lambda, double *u_ritz)

Compute Krylov subspace approximation of eigenvalues and vectors, real symmetric case.

int eigensystem_krylov_hermitian(const ct_long n, lanczos_linear_func_z afunc, const void *adata, const dcomplex *vstart, const int maxiter, const int numeig, double *lambda, dcomplex *u_ritz)

Compute Krylov subspace approximation of eigenvalues and vectors, complex Hermitian case.

Random number generation

Pseudo-random number generation.

Functions

void seed_rng_state(const uint64_t seed, struct rng_state *state)

Seed the random number generator state.

uint32_t rand_uint32(struct rng_state *state)

Generate a uniformly distributed 32-bit random number.

uint64_t rand_uint64(struct rng_state *state)

Generate a uniformly distributed 64-bit random number.

uint64_t rand_interval(const uint64_t bound, struct rng_state *state)

Generate a uniformly distributed integer random number from the interval [0, bound).

void rand_choice(const uint64_t bound, const uint64_t num_samples, struct rng_state *state, uint64_t *ret)

Draw ‘num_samples’ random numbers from the interval [0, bound) without replacement.

double randu(struct rng_state *state)

Generate a uniformly distributed pseudo-random number from the interval [0, 1) that has been rounded down to the nearest multiple of 1/2^{64}.

float randuf(struct rng_state *state)

Generate a uniformly distributed pseudo-random number from the interval [0, 1) that has been rounded down to the nearest multiple of 1/2^{32}.

double randn(struct rng_state *state)

Draw a standard normal (Gaussian) random number, using the Box-Muller transform.

Real double precision version.

float randnf(struct rng_state *state)

Draw a standard normal (Gaussian) random number, using the Box-Muller transform.

Real single precision version.

double complex crandn(struct rng_state *state)

Draw a standard complex normal (Gaussian) random number.

Complex double precision version.

float complex crandnf(struct rng_state *state)

Draw a standard complex normal (Gaussian) random number.

Complex single precision version.

struct rng_state

#include <rng.h>

Random number generator state.

Public Members

struct pcg32x2_random pcgstate

PCG random number generator state.

HDF5 utility functions

HDF5 utility functions.

Functions

herr_t get_hdf5_dataset_ndims(const hid_t file, const char *name, int *ndims)

Get the number of dimensions (degree) of an HDF5 dataset.

herr_t get_hdf5_dataset_dims(const hid_t file, const char *name, hsize_t *dims)

Get the dimensions of an HDF5 dataset.

herr_t read_hdf5_dataset(const hid_t file, const char *name, hid_t mem_type, void *data)

Read an HDF5 dataset from a file.

herr_t write_hdf5_dataset(const hid_t file, const char *name, int degree, const hsize_t dims[], hid_t mem_type_store, hid_t mem_type_input, const void *data)

Write an HDF5 dataset to a file.

herr_t get_hdf5_attribute_dims(const hid_t file, const char *name, hsize_t *dims)

Get the dimensions of an HDF5 attribute.

herr_t read_hdf5_attribute(const hid_t file, const char *name, hid_t mem_type, void *data)

Read an HDF5 attribute from a file.

herr_t write_hdf5_scalar_attribute(const hid_t file, const char *name, hid_t mem_type_store, hid_t mem_type_input, const void *data)

Write an HDF5 scalar attribute to a file.

herr_t write_hdf5_vector_attribute(const hid_t file, const char *name, hid_t mem_type_store, hid_t mem_type_input, const ct_long length, const void *data)

Write an HDF5 vector attribute to a file.

hid_t construct_hdf5_single_complex_dtype(const bool storage)

Construct the identifier of the HDF5 compound type for single precision complex numbers, or -1 on failure. ‘storage’ indicates whether the data type is used for storage (fixed endian convention) or as a memory type used in a program.

hid_t construct_hdf5_double_complex_dtype(const bool storage)

Construct the identifier of the HDF5 compound type for double precision complex numbers, or -1 on failure. ‘storage’ indicates whether the data type is used for storage (fixed endian convention) or as a memory type used in a program.

enum numeric_type hdf5_to_numeric_dtype(const hid_t dtype)

Convert an HDF5 data type identifier to the corresponding numeric type.

Returns:

numeric data type, or -1 on failure

hid_t numeric_to_hdf5_dtype(const enum numeric_type dtype, const bool storage)

Convert a numeric type to the corresponding HDF5 data type. ‘storage’ indicates whether the data type is used for storage (fixed endian convention) or as a memory type used in a program.

Returns:

HDF5 data type identifier, or -1 on failure

Timing utility functions

Timing utility functions.

Functions

int64_t get_time_ticks()

Get the current time as number of clock ticks.

int64_t get_tick_resolution()

Get the performance timer resolution.