rvgraph.c

h.248协议源码

/******************************************************************************
Filename:    rvgraph.c
Description: graph class
*******************************************************************************
                Copyright (c) 2000 RADVision Inc.
*******************************************************************************
NOTICE:
This document contains information that is proprietary to RADVision LTD.
No part of this publication may be reproduced in any form whatsoever 
without written prior approval by RADVision LTD..

RADVision LTD. reserves the right to revise this publication and make 
changes without obligation to notify any person of such revisions or 
changes.
******************************************************************************/

#include "rvgraph.h"

static RvGraphLink *rvGraphLinkConstruct(RvGraphLink *link, RvGraphNode *node, void *data)
{
	link->node = node;
	link->data = data;
	return link;
}

#define rvGraphLinkConstructCopy rvDefaultConstructCopy
#define rvGraphLinkDestruct rvDefaultDestruct

static RvBool rvGraphLinkEqual(const RvGraphLink *a, const RvGraphLink *b)
{
	return a->node == b->node && a->data == b->data;
}

#define rvGraphLinkGetNode(x) ((x)->node)
#define rvGraphLinkGetData(x) ((x)->data)
#define RvGraphLinkConstructCopy rvGraphLinkConstructCopy
#define RvGraphLinkDestruct rvGraphLinkDestruct
#define RvGraphLinkEqual rvGraphLinkEqual

rvDefineList(RvGraphLink)

static RvGraphNode *rvGraphNodeConstruct(RvGraphNode *node, void *item, RvAlloc *alloc)
{
	node->item = item;
	rvListConstruct(RvGraphLink)(&node->out, alloc);
	rvListConstruct(RvGraphLink)(&node->in, alloc);
	return node;
}

static RvGraphNode *rvGraphNodeConstructCopy(RvGraphNode *d, const RvGraphNode *s, RvAlloc *alloc)
{
	d->item = s->item;
	rvListConstructCopy(RvGraphLink)(&d->out, &s->out, alloc);
	rvListConstructCopy(RvGraphLink)(&d->in, &s->in, alloc);
	return d;
}

static void rvGraphNodeDestruct(RvGraphNode *node)
{
	rvListDestruct(RvGraphLink)(&node->out);
	rvListDestruct(RvGraphLink)(&node->in);
}

static RvBool rvGraphNodeEqual(const RvGraphNode *a, const RvGraphNode *b)
{
	return a == b;
}

#define RvGraphNodeConstructCopy rvGraphNodeConstructCopy
#define RvGraphNodeDestruct rvGraphNodeDestruct
#define RvGraphNodeEqual rvGraphNodeEqual

rvDefineList(RvGraphNode)

RvGraph *rvGraphConstructA(RvGraph *graph, RvAlloc *alloc)
{
	rvListConstruct(RvGraphNode)(&graph->nodes, alloc);
	return graph;
}

static RvBool addLinkToGraph(void *head, void *tail, void *link, void *data)
{
	rvGraphAddLink((RvGraph *)data, head, tail, link);
	return rvFalse;
}

RvGraph *rvGraphConstructCopy(RvGraph *d, const RvGraph *s, RvAlloc *alloc)
{
	rvGraphConstructA(d, alloc);
	rvGraphForEachLink((RvGraph *)s, addLinkToGraph, d);
	return d;
}

void rvGraphDestruct(RvGraph *graph)
{
	rvListDestruct(RvGraphNode)(&graph->nodes);
}

RvGraph *rvGraphCopy(RvGraph *d, const RvGraph *s)
{
	rvGraphClear(d);
	rvGraphForEachLink((RvGraph *)s, addLinkToGraph, d);
	return d;
}

void rvGraphAddNode(RvGraph *graph, void *node)
{
	RvGraphNode n;
	rvGraphNodeConstruct(&n, node, rvGraphGetAllocator(graph));
	rvListPushBack(RvGraphNode)(&graph->nodes, &n);
	rvGraphNodeDestruct(&n);
}

static RvBool linkCmp(void *link, void *data) {
	return (link==data);
}

static void removeLinkCmp(RvList(RvGraphLink) *list, void *node,RvGraphLinkCmpFunc f,void *data)
{
	RvGraphLinkIter i;
	for(i=rvListBegin(list); i!=rvListEnd(list); i=rvListIterNext(i))
	{
		if(rvGraphLinkIterGetNode(i) == node && f(rvGraphLinkIterGetData(i),data)==rvTrue )
		{
			rvListErase(RvGraphLink)(list, i);
			return;
		}
	}
}

static void removeLink(RvList(RvGraphLink) *list, void *node, void *data)
{
	removeLinkCmp(list,node,linkCmp,data);
}

void rvGraphRemoveNodeIter(RvGraph *graph, RvGraphNodeIter nodeIter,RvGraphLinkFunc f,void * data)
{
	void * node = rvGraphNodeIterGetNode(nodeIter);
	if(nodeIter != rvGraphEnd(graph))
	{
		RvGraphLinkIter i;
		for(i=rvGraphNodeOutLinksBegin(nodeIter); i!=rvGraphNodeOutLinksEnd(nodeIter); i=rvGraphLinkIterNext(i))
		{
			RvGraphLink *link = rvListIterData(i);
			void * linkData = rvGraphLinkGetData(link);
			removeLink(&rvGraphLinkGetNode(link)->in, node,linkData ); 
			/* Post-process the link data (i.e.,release */
			f(node,&rvGraphLinkGetNode(link)->in,linkData,data);
		}
		for(i=rvGraphNodeInLinksBegin(nodeIter); i!=rvGraphNodeInLinksEnd(nodeIter); i=rvGraphLinkIterNext(i))
		{
			RvGraphLink *link = rvListIterData(i);
			void * linkData = rvGraphLinkGetData(link);
			removeLink(&rvGraphLinkGetNode(link)->out, node, linkData); 
			/* Post-process the link data (i.e.,release */
			f(&rvGraphLinkGetNode(link)->out,node,linkData,data);
		}
		rvListErase(RvGraphNode)(&graph->nodes, nodeIter);
	}
}

static RvBool nullLinkFunc(void *head, void *tail, void *link, void *data) {
	return rvTrue;
}

void rvGraphRemoveNode(RvGraph *graph, void *node)
{
	rvGraphRemoveNodeExt(graph,node,nullLinkFunc,0);
}

void rvGraphRemoveNodeExt(RvGraph *graph, void *node,RvGraphLinkFunc f,void * data)
{
	RvGraphNodeIter nodeIter = rvGraphFindNode(graph, node);
	rvGraphRemoveNodeIter(graph,nodeIter,f,data);
}

void rvGraphClear(RvGraph *graph)
{
	rvListClear(RvGraphNode)(&graph->nodes);
}

void rvGraphAddLink(RvGraph *graph, void *head, void *tail, void *data)
{
	RvGraphNodeIter headIter, tailIter;
	RvGraphLink fwlink, bwlink;
	if((headIter = rvGraphFindNode(graph, head)) == rvGraphEnd(graph))
	{
		rvGraphAddNode(graph, head);
		headIter = rvGraphNodeIterPrev(rvGraphEnd(graph));
	}
	if((tailIter = rvGraphFindNode(graph, tail)) == rvGraphEnd(graph))
	{
		rvGraphAddNode(graph, tail);
		tailIter = rvGraphNodeIterPrev(rvGraphEnd(graph));
	}
	rvGraphLinkConstruct(&fwlink, rvListIterData(tailIter), data);
	rvGraphLinkConstruct(&bwlink, rvListIterData(headIter), data);
	rvListPushBack(RvGraphLink)(&rvListIterData(headIter)->out, &fwlink);
	rvListPushBack(RvGraphLink)(&rvListIterData(tailIter)->in, &bwlink);
	rvGraphLinkDestruct(&fwlink);
	rvGraphLinkDestruct(&bwlink);
}

void rvGraphRemoveLinkCmp(RvGraph *graph, void *head, void *tail,RvGraphLinkCmpFunc f,void *data) 
{
	RvGraphNodeIter headIter = rvGraphFindNode(graph, head);
	RvGraphNodeIter tailIter = rvGraphFindNode(graph, tail);
	if(headIter != rvGraphEnd(graph) && tailIter != rvGraphEnd(graph))
	{
		removeLinkCmp(&rvListIterData(headIter)->out, tail,f,data);
		removeLinkCmp(&rvListIterData(tailIter)->in, head,f,data);
	}
}

void rvGraphRemoveLink(RvGraph *graph, void *head, void *tail, void *data)
{
	rvGraphRemoveLinkCmp(graph,head,tail,linkCmp,data);
}

void rvGraphClearLinks(RvGraph *graph)
{
	RvGraphNodeIter i;
	for(i=rvGraphBegin(graph); i!=rvGraphEnd(graph); i=rvGraphNodeIterNext(i))
	{
		RvGraphNode *node = rvListIterData(i);
		rvListClear(RvGraphLink)(&node->out);
		rvListClear(RvGraphLink)(&node->in);
	}
}

size_t rvGraphGetNumNodes(RvGraph *graph)
{
	return rvListSize(&graph->nodes);
}

RvGraphNodeIter rvGraphBegin(RvGraph *graph)
{
	return rvListBegin(&graph->nodes);
}

RvGraphNodeIter rvGraphTail(RvGraph *graph)
{
	return rvListRevBegin(&graph->nodes);
}

RvGraphNodeIter rvGraphEnd(RvGraph *graph)
{
	return rvListEnd(&graph->nodes);
}


RvGraphNodeIter rvGraphFindNodeIterCmp(RvGraph *graph, RvGraphNodeFunc f,void * data)
{
	RvGraphNodeIter i;
	for(i=rvGraphBegin(graph);i!=rvGraphEnd(graph);i=rvGraphNodeIterNext(i)) {
		if(	f(rvGraphNodeIterGetNode(i),data)== rvTrue )
			return i;
	}
		;
	return i;
}

static RvBool nodeCmp(void *node, void *data) 
{
	return (node==data);
}

RvGraphNodeIter rvGraphFindNode(RvGraph *graph, void *node)
{
	return rvGraphFindNodeIterCmp(graph,nodeCmp,node);
}

void * rvGraphFindNodeCmp(RvGraph *graph, RvGraphNodeFunc f,void * data) {
	RvGraphNodeIter i = rvGraphFindNodeIterCmp(graph,f,data);
	if( i==rvGraphEnd(graph) )
		return NULL;
	return rvGraphNodeIterGetNode(i);
}

RvGraphLinkIter rvGraphNodeOutLinksBegin(RvGraphNodeIter i)
{
	return rvListBegin(&rvListIterData(i)->out);
}

RvGraphLinkIter rvGraphNodeOutLinksEnd(RvGraphNodeIter i)
{
	return rvListEnd(&rvListIterData(i)->out);
}

RvGraphLinkIter rvGraphNodeInLinksBegin(RvGraphNodeIter i)
{
	return rvListBegin(&rvListIterData(i)->in);
}

RvGraphLinkIter rvGraphNodeInLinksEnd(RvGraphNodeIter i)
{
	return rvListEnd(&rvListIterData(i)->in);
}


size_t rvGraphNodeGetNumOutLinks(RvGraphNodeIter i)
{
	return rvListSize(&rvListIterData(i)->out);
}

size_t rvGraphNodeGetNumInLinks(RvGraphNodeIter i)
{
	return rvListSize(&rvListIterData(i)->in);
}

RvBool rvGraphForEachNode(RvGraph *graph, RvGraphNodeFunc f, void *data)
{
	RvGraphNodeIter i , nextIter;
	for(i=rvGraphBegin(graph); i!=rvGraphEnd(graph); i=nextIter) {
		nextIter = rvGraphNodeIterNext(i);
		if(f(rvGraphNodeIterGetNode(i), data))
			return rvTrue;
	}
	return rvFalse;
}

RvBool rvGraphForEachLink(RvGraph *graph, RvGraphLinkFunc f, void *data)
{
	RvGraphNodeIter nodeIter,nextIter;
	for(nodeIter=rvGraphBegin(graph); nodeIter!=rvGraphEnd(graph); nodeIter=nextIter)
	{
		RvGraphLinkIter link,nextLink;
		nextIter = rvGraphNodeIterNext(nodeIter);
		for(link=rvGraphNodeOutLinksBegin(nodeIter);
		    link!=rvGraphNodeOutLinksEnd(nodeIter);
			link=nextLink)
		{
			nextLink = rvGraphLinkIterNext(link);
			if(f(rvGraphNodeIterGetNode(nodeIter), rvGraphLinkIterGetNode(link),
				rvGraphLinkIterGetData(link), data))
				return rvTrue;
		}
	}
	return rvFalse;
}

RvBool rvGraphForEachLinkFromNode(RvGraph *graph, void *node, RvGraphLinkFunc f, void *data)
{
	RvGraphNodeIter nodeIter = rvGraphFindNode(graph, node);
	if(nodeIter != rvGraphEnd(graph))
	{
		RvGraphLinkIter link,nextLink;
		for(link=rvGraphNodeOutLinksBegin(nodeIter);
		    link!=rvGraphNodeOutLinksEnd(nodeIter);
			link=nextLink)
		{
			nextLink = rvGraphLinkIterNext(link);
			if(f(rvGraphNodeIterGetNode(nodeIter), rvGraphLinkIterGetNode(link),
				rvGraphLinkIterGetData(link), data))
				return rvTrue;
		}
	}
	return rvFalse;
}

/* The function is always called in the order: head, tail */
RvBool rvGraphForEachLinkToNode(RvGraph *graph, void *node, RvGraphLinkFunc f, void *data)
{
	RvGraphNodeIter nodeIter = rvGraphFindNode(graph, node);
	if(nodeIter != rvGraphEnd(graph))
	{
		RvGraphLinkIter link,nextLink;
		for(link=rvGraphNodeInLinksBegin(nodeIter);
		    link!=rvGraphNodeInLinksEnd(nodeIter);
			link=nextLink)
		{
			nextLink = rvGraphLinkIterNext(link);
			if(f(rvGraphLinkIterGetNode(link),rvGraphNodeIterGetNode(nodeIter), 
				rvGraphLinkIterGetData(link), data))
				return rvTrue;
		}
	}
	return rvFalse;
}

void * rvGraphFindLinkFromNodeIter(RvGraph *graph, RvGraphNodeIter nodeIter,RvGraphNodeIter tailIter,RvGraphLinkCmpFunc f, void *data) {
/* 	void * node = rvGraphNodeIterGetNode(nodeIter); */
	if(nodeIter != rvGraphEnd(graph))
	{
		RvGraphLinkIter link;
		for(link=rvGraphNodeOutLinksBegin(nodeIter);
		    link!=rvGraphNodeOutLinksEnd(nodeIter);
			link=rvGraphLinkIterNext(link))
		{
			void * tail = rvGraphNodeIterGetNode(tailIter);
			if(rvGraphLinkIterGetNode(link)==tail && f(rvGraphLinkIterGetData(link),data) == rvTrue) 
				return rvGraphLinkIterGetData(link);
		}
	}
	return NULL;
}


void * rvGraphFindLinkFromNode(RvGraph *graph, void *node,void * tail,RvGraphLinkCmpFunc f, void *data) {
	return rvGraphFindLinkFromNodeIter(graph,rvGraphFindNode(graph,node),rvGraphFindNode(graph,tail),f,data);
}

void * rvGraphFindLinkToNode(RvGraph *graph, RvGraphNodeIter nodeIter,RvGraphNodeIter headIter,RvGraphLinkCmpFunc f, void *data) {
/*	void * node = rvGraphNodeIterGetNode(nodeIter); */
	if(nodeIter != rvGraphEnd(graph))
	{
		RvGraphLinkIter link;
		for(link=rvGraphNodeInLinksBegin(nodeIter);
		    link!=rvGraphNodeInLinksEnd(nodeIter);
			link=rvGraphLinkIterNext(link))
		{
			void * head = rvGraphNodeIterGetNode(headIter);
			if(rvGraphLinkIterGetNode(link)==head && f(rvGraphLinkIterGetData(link),data) == rvTrue) 
				return rvGraphLinkIterGetData(link);
		}
	}
	return NULL;
}

RvAlloc *rvGraphGetAllocator(const RvGraph *graph)
{
	return rvListGetAllocator(&graph->nodes);
}