node.c File Reference

#include <assert.h>
#include <cgraph/cghdr.h>
#include <cgraph/node_set.h>
#include <stdbool.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/unreachable.h>

Include dependency graph for node.c:

Go to the source code of this file.

Data Structures
struct	graphviz_node_set

Functions
Agnode_t *	agfindnode_by_id (Agraph_t *g, IDTYPE id)
static Agnode_t *	agfindnode_by_name (Agraph_t *g, char *name)
Agnode_t *	agfstnode (Agraph_t *g)
Agnode_t *	agnxtnode (Agraph_t *g, Agnode_t *n)
Agnode_t *	aglstnode (Agraph_t *g)
Agnode_t *	agprvnode (Agraph_t *g, Agnode_t *n)
static Agnode_t *	newnode (Agraph_t *g, IDTYPE id, uint64_t seq)
static void	installnode (Agraph_t *g, Agnode_t *n)
static void	installnodetoroot (Agraph_t *g, Agnode_t *n)
static void	initnode (Agraph_t *g, Agnode_t *n)
Agnode_t *	agidnode (Agraph_t *g, IDTYPE id, int cflag)
Agnode_t *	agnode (Agraph_t *g, char *name, int cflag)
void	agdelnodeimage (Agraph_t *g, Agnode_t *n, void *ignored)
int	agdelnode (Agraph_t *g, Agnode_t *n)
	removes a node from a graph or subgraph.
static void	dict_relabel (Agraph_t *ignored, Agnode_t *n, void *arg)
int	agrelabel_node (Agnode_t *n, char *newname)
Agnode_t *	agsubnode (Agraph_t *g, Agnode_t *n0, int cflag)
static bool	agsubnodeideq (const Agsubnode_t *sn0, IDTYPE id)
static int	agsubnodeseqcmpf (void *arg0, void *arg1)
static void	free_subnode (void *subnode)
static void	agnodesetfinger (Agraph_t *g, Agnode_t *n, void *ignored)
static void	agnoderenew (Agraph_t *g, Agnode_t *n, void *ignored)
int	agnodebefore (Agnode_t *fst, Agnode_t *snd)
static size_t	node_set_get_capacity (const node_set_t *self)
node_set_t *	node_set_new (void)
static size_t	node_set_hash (IDTYPE id)
void	node_set_add (node_set_t *self, Agsubnode_t *item)
Agsubnode_t *	node_set_find (node_set_t *self, IDTYPE key)
void	node_set_remove (node_set_t *self, IDTYPE item)
size_t	node_set_size (const node_set_t *self)
void	node_set_free (node_set_t **self)

Variables
Dtdisc_t	Ag_subnode_seq_disc
static Agsubnode_t *const	TOMBSTONE = (Agsubnode_t *)-1
	a sentinel, marking a set slot from which an element has been deleted

Function Documentation

agdelnodeimage()

void agdelnodeimage	(	Agraph_t *	g,
		Agnode_t *	n,
		void *	ignored
	)

Definition at line 177 of file node.c.

References agdeledgeimage(), agfstedge(), agnxtedge(), Agnode_s::base, dtdelete, Agtag_s::id, Agraph_s::n_id, Agraph_s::n_seq, Agsubnode_s::node, node_set_remove(), and Agobj_s::tag.

Referenced by agdelnode().

Here is the call graph for this function:

Here is the caller graph for this function:

agfindnode_by_id()

Agnode_t * agfindnode_by_id	(	Agraph_t *	g,
		IDTYPE	id
	)

Definition at line 22 of file node.c.

References Agraph_s::n_id, Agsubnode_s::node, node_set_find(), and NULL.

Referenced by agdelnode(), agfindnode_by_name(), agidnode(), agnode(), agrelabel_node(), and agsubnode().

Here is the call graph for this function:

Here is the caller graph for this function:

agfindnode_by_name()

static Agnode_t * agfindnode_by_name ( Agraph_t *  g, char *  name  )

static

Definition at line 30 of file node.c.

References agfindnode_by_id(), agmapnametoid(), AGNODE, id, and NULL.

Referenced by agrelabel_node().

Here is the call graph for this function:

Here is the caller graph for this function:

agnoderenew()

static void agnoderenew ( Agraph_t *  g, Agnode_t *  n, void *  ignored  )

static

Definition at line 325 of file node.c.

References dtfinger, dtrenew(), and Agraph_s::n_seq.

Referenced by agnodebefore().

Here is the call graph for this function:

Here is the caller graph for this function:

agnodesetfinger()

static void agnodesetfinger ( Agraph_t *  g, Agnode_t *  n, void *  ignored  )

static

Definition at line 317 of file node.c.

References dtsearch, Agraph_s::n_seq, and Agsubnode_s::node.

Referenced by agnodebefore().

Here is the caller graph for this function:

agsubnodeideq()

static bool agsubnodeideq ( const Agsubnode_t *  sn0, IDTYPE  id  )

static

compare a subnode to an identifier for equality

Parameters

sn0	Operand 1
sn1	Operand 2

Returns

True if nodes are equal

Definition at line 284 of file node.c.

References AGID, id, and Agsubnode_s::node.

Referenced by node_set_find(), and node_set_remove().

Here is the caller graph for this function:

agsubnodeseqcmpf()

static int agsubnodeseqcmpf ( void *  arg0, void *  arg1  )

static

Definition at line 288 of file node.c.

References AGSEQ, and Agsubnode_s::node.

dict_relabel()

static void dict_relabel ( Agraph_t *  ignored, Agnode_t *  n, void *  arg  )

static

Definition at line 220 of file node.c.

References AGID, agraphof(), agsubrep(), Agnode_s::base, Agtag_s::id, Agraph_s::n_id, Agsubnode_s::node, node_set_add(), node_set_remove(), NULL, and Agobj_s::tag.

Referenced by agrelabel_node().

Here is the call graph for this function:

Here is the caller graph for this function:

free_subnode()

static void free_subnode ( void *  subnode )

static

Definition at line 305 of file node.c.

References AGSNMAIN, and free().

Here is the call graph for this function:

initnode()

static void initnode ( Agraph_t *  g, Agnode_t *  n  )

static

Definition at line 114 of file node.c.

References agmethod_init(), agnodeattr_init(), and agroot().

Referenced by agidnode(), and agnode().

Here is the call graph for this function:

Here is the caller graph for this function:

installnode()

static void installnode ( Agraph_t *  g, Agnode_t *  n  )

static

Definition at line 89 of file node.c.

References agroot(), dtinsert, dtsize(), gv_alloc(), Agnode_s::mainsub, Agraph_s::n_id, Agraph_s::n_seq, Agsubnode_s::node, node_set_add(), and node_set_size().

Referenced by agsubnode(), and installnodetoroot().

Here is the call graph for this function:

Here is the caller graph for this function:

installnodetoroot()

static void installnodetoroot ( Agraph_t *  g, Agnode_t *  n  )

static

Definition at line 106 of file node.c.

References agparent(), installnode(), and installnodetoroot().

Referenced by agidnode(), agnode(), and installnodetoroot().

Here is the call graph for this function:

Here is the caller graph for this function:

newnode()

static Agnode_t * newnode ( Agraph_t *  g, IDTYPE  id, uint64_t  seq  )

static

Definition at line 72 of file node.c.

References agbindrec(), AgDataRecName, AGID, AGNODE, agroot(), AGSEQ, AGTYPE, gv_alloc(), id, Agnode_s::root, and SEQ_MASK.

Referenced by agidnode(), agnode(), and RTreeInsert().

Here is the call graph for this function:

Here is the caller graph for this function:

node_set_add()

void node_set_add	(	node_set_t *	self,
		Agsubnode_t *	item
	)

add an item to the set

If the backing store is not large enough, it is expanded on demand. On allocation failure, exit is called.

Parameters

self	Set to add to
item	Element to add

Definition at line 425 of file node.c.

References graphviz_node_set::capacity_exp, free(), gv_calloc(), hash, graphviz_node_set::max, graphviz_node_set::min, graphviz_node_set::min_initialized, node_set_add(), node_set_get_capacity(), node_set_hash(), NULL, graphviz_node_set::size, graphviz_node_set::slots, TOMBSTONE, and UNREACHABLE.

Referenced by dict_relabel(), installnode(), and node_set_add().

Here is the call graph for this function:

Here is the caller graph for this function:

node_set_find()

Agsubnode_t * node_set_find	(	node_set_t *	self,
		IDTYPE	key
	)

lookup an existing item in a set

Parameters

self	Set to search
key	Identifier of node to look for

Returns

The found corresponding subnode or NULL if it was not in the set

Definition at line 489 of file node.c.

References agsubnodeideq(), hash, graphviz_node_set::max, graphviz_node_set::min_initialized, node_set_get_capacity(), node_set_hash(), NULL, graphviz_node_set::slots, and TOMBSTONE.

Referenced by agfindnode_by_id(), and agsubrep().

Here is the call graph for this function:

Here is the caller graph for this function:

node_set_free()

void node_set_free

(

node_set_t **

self

)

destruct a set

*self is NULL on return.

Parameters

self	Set to destroy

Definition at line 557 of file node.c.

References free(), and NULL.

Referenced by agclose().

Here is the call graph for this function:

Here is the caller graph for this function:

node_set_get_capacity()

static size_t node_set_get_capacity ( const node_set_t *  self )

static

get the allocated size of the backing storage of a node set

The capacity of a set is represented as its base-2 exponent, to make clearer to the compiler that it can implement % capacity as a mask, avoiding the expense of a modulo operation.

Parameters

self	Set to inspect

Returns

Capacity of the given set

Definition at line 408 of file node.c.

References graphviz_node_set::capacity_exp, NULL, and graphviz_node_set::slots.

Referenced by node_set_add(), node_set_find(), and node_set_remove().

Here is the caller graph for this function:

node_set_hash()

static size_t node_set_hash ( IDTYPE  id )

static

compute a hash of a node

If the suboptimal choice of using the ID here turns out to be bad for performance, this could be converted to a more sophisticated hashing algorithm. None of the callers depend on the exact implementation.

Parameters

id	Identifier of element being sought/added

Returns

Hash digest of the target node

Definition at line 423 of file node.c.

References id.

Referenced by node_set_add(), node_set_find(), and node_set_remove().

Here is the caller graph for this function:

node_set_new()

node_set_t * node_set_new

(

void

)

construct a new set

Calls exit on failure (out-of-memory).

Returns

A constructed set

Definition at line 413 of file node.c.

References gv_alloc().

Referenced by agopen1().

Here is the call graph for this function:

Here is the caller graph for this function:

node_set_remove()

void node_set_remove	(	node_set_t *	self,
		IDTYPE	item
	)

remove an item from a set

If the given item was not in the set, this is a no-op.

Parameters

self	Set to remove from
item	Identifier of element to remove

Definition at line 524 of file node.c.

References agsubnodeideq(), hash, node_set_get_capacity(), node_set_hash(), NULL, graphviz_node_set::size, graphviz_node_set::slots, and TOMBSTONE.

Referenced by agdelnodeimage(), and dict_relabel().

Here is the call graph for this function:

Here is the caller graph for this function:

node_set_size()

size_t node_set_size

(

const node_set_t *

self

)

get the number of items in a set

Parameters

self	Set to query

Returns

Number of elements in the set

Definition at line 552 of file node.c.

References NULL, and graphviz_node_set::size.

Referenced by agnnodes(), installnode(), and node_set_is_empty().

Here is the caller graph for this function:

Variable Documentation

Ag_subnode_seq_disc

Dtdisc_t Ag_subnode_seq_disc

Initial value:

= {
    .link = offsetof(Agsubnode_t, seq_link), 
    .freef = free_subnode,
    .comparf = agsubnodeseqcmpf,
}

Definition at line 311 of file node.c.

Referenced by agopen1().

TOMBSTONE

Agsubnode_t* const TOMBSTONE = (Agsubnode_t *)-1

static

Definition at line 398 of file node.c.

Referenced by node_set_add(), node_set_find(), and node_set_remove().