graph.h File Reference

Graph implementation. More...

#include <stddef.h>
#include <stdio.h>
#include "libsapling/idiom.h"
#include "libsapling/dm/logic.h"

Go to the source code of this file.

Data Structures
struct	info_stack
	Means of passing arbitrary user and implementation information between function calls. More...
struct	info_insert
	Information required to perform insertion. More...

Typedefs
typedef struct edge_storage *	node_t
typedef int(*	predicate_t) (const node_t *ref, const struct info_stack *info)
	Decides whether to run the apply function on an item. Behavior is modified by quantifiers. More...
typedef void(*	apply_t) (node_t *ref, const struct info_stack *info)
	Performs a user-defined operation on the node.
typedef int(*	next_t) (node_t **ref, const struct info_stack *info)
	Chooses the next node to visit. More...
typedef void(*	edge_management_t) (node_t *ref, const node_t node, void *impl_ptr)
	Called upon the insertion and deletion protocols. More...
typedef void(*	fpfdata_t) (FILE *stream, const void *data)
	File print format data function prototype.
typedef void(*	fpfnode_t) (FILE *stream, const node_t node, fpfdata_t fpfdata, void *impl_ptr)
	File print format node function prototype.
typedef void(*	all_access_adapter_fn) (node_t *ref, void *info, apply_t apply)
	Generic access all nodes adapter function prototype. More...

Functions
int	predicate_0 (UNUSED const node_t *ref, UNUSED const struct info_stack *info)
	Trivial predicate function that always returns 0. More...
int	predicate_1 (UNUSED const node_t *ref, UNUSED const struct info_stack *info)
	Trivial predicate function that always returns 1. More...
void *	graph__data (const node_t node, size_t edge_storage)
	Returns a pointer to the data storage of a node. More...
void	graph__access (enum qt qt, node_t *ref, const struct info_stack *info, predicate_t predicate, apply_t apply, next_t next)
	Access protocol. Traverses the graph according to a quantifier modifier and specific implementation workings. More...
void	graph__insert (node_t *ref, const struct info_stack *info, edge_management_t edge_management, size_t edge_storage)
	Insertion protocol. More...
void	graph__delete (node_t *ref, const struct info_stack *info, edge_management_t edge_management)
	Deletion protocol. More...
void	graph__print (FILE *stream, node_t *ref, all_access_adapter_fn access_adapter, fpfnode_t fpfnode, fpfdata_t fpfdata)
	Prints all the data contained in the set.
void	graph__dump_dot (FILE *stream, node_t *ref, all_access_adapter_fn access_adapter, fpfnode_t fpfnode, fpfdata_t fpfdata, const char *graph_attributes)
	Dumps the graph in the DOT graph description language.
int	graph__length (const node_t *ref, all_access_adapter_fn access_adapter)
	Returns the number of items contained in the set. More...

Detailed Description

Graph implementation.

This implementation serves as the basis for implementing other dynamic data structures (DDS). The general idea behind this implementation is to represent a set using a graph, taking advantage of the graph's structure to speed up operations, like all data structures aim to do. The hope is that someday it will be possible to automatically determine and implement an optimal graph structure for a set by only analyzing the properties of the data fields of the set's elements and its actual usage in a program, using this implementation as the basis. For now it serves as an abstraction to implement them manually. Implementation for binary set operations is currently neither provided nor the focus, instead the focus of this implementation lies in providing first-order logic data manipulation. For this purpose it provides three elemental operations: insertion, deletion and access, the two latter accepting first-order logic quantifiers, since they manipulate what is already in the set. Insertion is regarded as being existentially quantified, since it searches for the most appropiate location in the graph's structure where a new node must be appended to the overall graph, perhaps according to some attribute of the data to be inserted in the set. Aside from that, some convenience and debugging functions are also provided.

Inspired by the implementation of the C style null-terminated string, which defines a string as a pointer to the first character, this implementation defines a graph as an edge (pointer) to a starting node. Whereas in a string the next character can be accessed by incrementing the pointer by the size of a character, in this graph implementation each node stores the edges that sprout from it to other nodes, referred to as the edge storage of the node. This may be a just an edge to the next node, or several of them, even edge management information such as the balance factor of an AVL node, which is not an edge in itself, it may be a dynamic number of edges with the number of edges stored at the beginning of the storage, it may be another dynamic data structure (another graph), which may store attributed edges sorted by that attribute... In conclusion: as long as the particular implementations can interpret the contents of this storage anything goes.

The edge storage may be followed by a data storage, which combined account for the whole contiguous block of memory allocated at the node's address. Like with the edge storage, anything can go in the data storage as long as the user can interpret the contents. Edge management data must no be mixed with the data storage, edge management information need not be edges exclusively. Particular implementations may, however, appropiate the data storage away from the user, and impose their own interfaces to interact with the data if the use case warrants it. For example, in a lexer graph, accepting states might store an identifier of a terminal class as a pointer to an integer, and decide that a state is not an accepting state if the value of that pointer is NULL.

An important thing to keep in mind is that all defined operations and function prototypes actually accept an edge (pointer) that leads to the node, rather than the node itself, as this simplifies the implementation of insertion and deletion. For example, upon deleting an AVL node with only one child it is sufficient to promote the child to the parent's position by dereferencing the edge and replacing the parent node's address with that of the child.

Typedef Documentation

all_access_adapter_fn

typedef void(* all_access_adapter_fn) (node_t *ref, void *info, apply_t apply)

Generic access all nodes adapter function prototype.

Remarks

Originally created for use with the generic graph printing functions which invokes the particular DDS' implementation's access function without having to know the implementation of the next function.

edge_management_t

typedef void(* edge_management_t) (node_t *ref, const node_t node, void *impl_ptr)

Called upon the insertion and deletion protocols.

On insertion node contains the address of the newly created node and ref the position in the graph where it was determined for it to be inserted, so usually edge management functions should assign *ref = node at some point. This is however, not enforced with any language construct to account for the case of the AVL tree rotations, where instead of the newly created node being directly appended to the graph at ref, it may become a child of its child and the former child is instead appended at ref.

On deletion node is the same as *ref. Likewise it takes care of restructuring the graph at ref upon deleting a node.

It also may perform the task of initializing the data of the edge storage.

Attention

The insertion and deletion protocols take care of allocating and freeing the node, so that task must not be performed within the edge management function.

next_t

typedef int(* next_t) (node_t **ref, const struct info_stack *info)

Chooses the next node to visit.

Returns

A boolean value that indicates whether traversal should continue.

predicate_t

typedef int(* predicate_t) (const node_t *ref, const struct info_stack *info)

Decides whether to run the apply function on an item. Behavior is modified by quantifiers.

When modified with universal quantification the predicate decides whether to run the apply function on the current node.

When modified with existential quantification if the predicate is satisfied then the apply function is run on the current node and the traversal ends.

Returns

A boolean value that indicates whether the predicate was satisfied.

Function Documentation

graph__access()

void graph__access	(	enum qt	qt,
		node_t *	ref,
		const struct info_stack *	info,
		predicate_t	predicate,
		apply_t	apply,
		next_t	next
	)

Access protocol. Traverses the graph according to a quantifier modifier and specific implementation workings.

Visits all the reachable nodes starting from the specified node. Equivalent to traversal and associated with the universal quantifier.

Visits the minimum number of nodes in the graph until reaching a target node. Equivalent to search and associated with the existential quantifier.

graph__data()

void* graph__data	(	const node_t	node,
		size_t	edge_storage
	)

Returns a pointer to the data storage of a node.

Returns

a pointer to the data storage of a node.

graph__delete()

void graph__delete	(	node_t *	ref,
		const struct info_stack *	info,
		edge_management_t	edge_management
	)

Deletion protocol.

Attention

Deleting a node will also deallocate the memory previously allocated for its data so make sure to keep track of dangling pointers to data storage.

graph__insert()

void graph__insert	(	node_t *	ref,
		const struct info_stack *	info,
		edge_management_t	edge_management,
		size_t	edge_storage
	)

Insertion protocol.

Attention

The protocol expects the contents of the user information of the info_stack to be a size_t indicating the size of the data followed by that number of bytes of data. That size will be allocated for the data storage of the node and the data copied over as is. Extra information may follow.

graph__length()

int graph__length	(	const node_t *	ref,
		all_access_adapter_fn	access_adapter
	)

Returns the number of items contained in the set.

Returns

the number of items contained in the set.

predicate_0()

int predicate_0	(	UNUSED const node_t *	ref,
		UNUSED const struct info_stack *	info
	)

Trivial predicate function that always returns 0.

Return values

0

predicate_1()

int predicate_1	(	UNUSED const node_t *	ref,
		UNUSED const struct info_stack *	info
	)

Trivial predicate function that always returns 1.

Return values

1