node.c File Reference

#include <assert.h>
#include <cgraph/alloc.h>
#include <cgraph/cghdr.h>
#include <cgraph/node_set.h>
#include <cgraph/unreachable.h>
#include <stdbool.h>
#include <stdlib.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)
node_set_t *	node_set_new (void)
static size_t	node_set_index (const node_set_t *self, 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 179 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 327 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 319 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 286 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 290 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 222 of file node.c.

References AGID, agraphof(), agsubrep(), key, Agraph_s::n_id, node_set_add(), node_set_remove(), and NULL.

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 307 of file node.c.

References agfree(), AGSNMAIN, Agsubnode_s::node, and Agnode_s::root.

Here is the call graph for this function:

initnode()

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

static

Definition at line 116 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 91 of file node.c.

References agalloc(), agroot(), dtinsert, dtsize(), 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 108 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 agalloc(), agbindrec(), AgDataRecName, AGID, AGNODE, agroot(), AGSEQ, AGTYPE, 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 412 of file node.c.

References graphviz_node_set::capacity, free(), gv_calloc(), node_set_add(), node_set_index(), 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 475 of file node.c.

References agsubnodeideq(), graphviz_node_set::capacity, key, node_set_index(), NULL, graphviz_node_set::size, 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 545 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_index()

static size_t node_set_index ( const node_set_t *  self, IDTYPE  id  )

static

compute initial index to attempt to store/find an item in

This function only returns the first index to be examined. node_set_t is implemented using linear probing, so steps sequentially through indices following this.

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

self	Set to compute with respect to
item	Element being sought/added

Returns

Initial index to examine

Definition at line 406 of file node.c.

References graphviz_node_set::capacity, and NULL.

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 391 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 507 of file node.c.

References agsubnodeideq(), graphviz_node_set::capacity, node_set_index(), 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 540 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 313 of file node.c.

Referenced by agopen1().

TOMBSTONE

Agsubnode_t* const TOMBSTONE = (Agsubnode_t *)-1

static

Definition at line 389 of file node.c.

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