void
Dag_Dfs(
Dag_Vertex_t* dfsRoot,
Dag_DfsFunctions_t* dfsFun,
char* dfsData
)
- The parameters are:
- dfsRoot, the dag vertex where to start the DFS
- dfsFun, the functions to perform the DFS steps
- dfsData, a reference to generic data
The function increments the DFS code for the dag
manager owning dfsRoot and starts the DFS. Increment of
the code guarantees that each node is visited once and
only once. dfsFun -> Set() may change the default behaviour by
forcing to DFS to visit nodes more than once, or by preventing
DFS to do a complete visit.
- Side Effects none
Dag_Vertex_t*
Dag_Ennarize(
Dag_Vertex_t* dfsRoot
)
- The parameters are:
- dfsRoot, the dag vertex of the binary dag to transform into
ennary dag
- Side Effects none
Dag_Manager_t *
Dag_ManagerAlloc(
)
- Allocates the unique table (vTable) and the free list (gcList).
Initializes the counters for various statistics (stats).
Returns the pointer to the dag manager.
- Side Effects none
- See Also
Dag_ManagerAllocWithParams
Dag_ManagerFree
void
Dag_ManagerFree(
Dag_Manager_t * dagManager,
Dag_ProcPtr_t freeData,
Dag_ProcPtr_t freeGen
)
- Forces a total garbage collection and then deallocates the
dag manager. `freeData' can be used to deallocate `data'
fields (user data pointers) in the nodes, while `freeGen'
is applied to `gRef' fields (user generic pointers).
`freeData' and `freeGen' are in the form `void f(char * r)'.
- Side Effects none
- See Also
Dag_ManagerGC
void
Dag_ManagerGC(
Dag_Manager_t * dagManager,
Dag_ProcPtr_t freeData,
Dag_ProcPtr_t freeGen
)
- Sweeps out useless vertices, i.e., vertices that are not
marked as permanent, that are not descendants
of permanent vertices, or whose brother (if any) is neither
permanent nor descendant of a permanent vertex.
The search starts from vertices that are in the garbage
bin and whose mark is 0.
`freeData' can be used to deallocate `data'
fields (user data pointers) in the nodes, while `freeGen'
is applied to `gRef' fields (user generic pointers).
`freeData' and `freeGen' are in the form `void f(char * r)'.
- Side Effects none
- See Also
Dag_ManagerFree
void
Dag_PrintStats(
Dag_Manager_t * dagManager,
int clustSz,
FILE * outFile
)
- Prints the following:
- the number of entries found in every chunk of
`clustSz' bins (if `clustSz' is 1 then the number
of entries per bin is given, if `clustSz' is 0 no
such information is displayed);
- the number of shared vertices, i.e., the number
of v's such that v -> mark > 1;
- the average entries per bin and the variance;
- min and max entries per bin.
- Side Effects none
Dag_Vertex_t *
Dag_VertexInsert(
Dag_Manager_t * dagManager,
int vSymb,
char * vData,
lsList vSons
)
- Adds a vertex into the DAG and returns a
reference to it:
- vSymb is an integer code (vertex label);
- vData is a generic annotation;
- vSons must be a list of vertices (the intended sons).
Returns NIL(Dag_vertex_t) if there is no dagManager and
if vSymb is negative.
- Side Effects none
Dag_Vertex_t *
Dag_VertexLookup(
Dag_Manager_t * dagManager,
int vSymb,
char * vData,
lsList vSons
)
- Uniquely adds a new vertex into the DAG and returns a
reference to it:
- vSymb is a NON-NEGATIVE integer (vertex label);
- vData is a pointer to generic user data;
- vSons is a list of vertices (possibly NULL).
Returns NIL(Dag_vertex_t) if there is no dagManager and
if vSymb is negative.
- Side Effects none
void
Dag_VertexMark(
Dag_Vertex_t * v
)
- Increments the vertex mark by one, so it cannot be
deleted by garbage collection unless unmarked.
- Side Effects none
void
Dag_VertexUnmark(
Dag_Vertex_t * v
)
- Decrements the vertex mark by one, so it can be
deleted by garbage collection when fatherless.
- Side Effects none