tree.c

wm PNE 3.3 source code, running at more than vxworks6.x version.

OIDC_T     *oidc;
int	    oidclen;
int	   *length;
#endif /* NO_PP */
{
int indx;
TREENODE_T *node;

/* make sure we have a tree to work with */
if ((node = root) == 0)
    return(0);

/* make sure we have an oid to work with */
if (((indx = oidclen) == 0) || (oidc == 0))
    return(0);

/* step through the oid */
while (1) {    
    /* search through this level for a match to the subid */
    for (;*oidc != node->name; node = node->sibling)
        /* about to run off the end of the list return what we have */
        if (node->sibling == 0) {
	    if ((*length = oidclen - indx) == 0)
	        return(0);
	    else
	        /* must have matched somewhere so return the parent */
	        return(node->parent);
	    }

    /* we have a match.  If we are out of subids or there are no 
       children break */
    indx--;
    oidc++;

    if ((indx == 0) || !(node->status & TREECHILD))
        break;

    node = (TREENODE_T *)node->child;
    }

*length = oidclen - indx;
return(node);
}

/*******************************************************************************
*
* TREE_GetPrev - find the leaf before the specified <node>
* SYNOPSIS
*
* \cs
* TREENODE_T * TREE_GetPrev 
*     ( 
*     TREENODE_T *  root, 
*     OIDC_T     *  oidc, 
*     int           oidclen 
*     )
* \ce
*
* DESCRIPTION
*
* This routine finds the node specified by <oidc> and <oidclen>. If that node 
* does not exist, it finds the last node before where the specified node would 
* exist in the tree. To walk the tree, use this function to find a starting 
* point followed by TREE_GetNext() calls to find the subsequent leaves.
*
* PARAMETERS
* \is
* \i <*root>
* Specify the <root> of the tree structure 'TREENODE_T'.
* \i <*oidc>
* Specify the 'OIDC' index.
* \i <oidclen>
* Specify the length of the 'OIDC'.
* \ie
*
* RETURNS: If successful, this routine returns a pointer to the node. If no 
* nodes meet the specification, it returns a 0. This can happen when <oidc> 
* specifies a node before the entire tree.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Delete(), TREE_Extract(), TREE_Get(), 
* TREE_GetNext(), TREE_Install(), TREE_Name()
*/
#if !defined(NO_PP)
TREENODE_T *
  TREE_GetPrev(TREENODE_T *root,
	       OIDC_T     *oidc,
	       int	   oidclen)
#else /* NO_PP */
TREENODE_T *
  TREE_GetPrev(root, oidc, oidclen)
TREENODE_T *root;
OIDC_T     *oidc;
int	    oidclen;
#endif /* NO_PP */
{
TREENODE_T *node;

/* make sure we have a root */
if ((node = root) == 0)
    return(0);

/* make sure we have an oid to work with */
if ((oidclen == 0) || (oidc == 0))
    return(0);

/* if the oid is before the root return (TREENODE_T *)0 */
if (*oidc < node->name)
    return(0);

/* step through the oid */
while(1) {
    
    /* search through this level for a match to the subid */
    for (;*oidc != node->name; node = node->sibling)
        /* check for end of list or about to pass the node */
        if ((node->sibling == 0) || (node->sibling->name > *oidc)) {
	    /* return the last node in the subtree rooted at node
	       if there aren't any children we return node
	       otherwise we go do one level and then start looping
	       - going to the end of the sibling list and descending */
	    if (!(node->status & TREECHILD))
		return(node);
	    node = (TREENODE_T *)node->child;
	    while(1) {
	        if (node->sibling == 0) {
		    if (node->status & TREECHILD) {
		        node = (TREENODE_T *)node->child;
			continue;
		        }
		    else
		        return(node);
		    }
		node = node->sibling;
		}
	    }

    /* we have a match, prepare to descend the tree.  adjust the 
       counters then check that we have more subids, we have a 
       child and that the the next subid wouldn't be before the
       child (the subid isn't less than the childs name) */
    oidclen--;
    oidc++;
    if ((oidclen == 0) || 
	(!(node->status & TREECHILD)) ||
	(*oidc < ((TREENODE_T *)node->child)->name))
        break;
    node = (TREENODE_T *)node->child;
    }

return(node);
}

/*******************************************************************************
*
* TREE_GetNext - find the first leaf after the specified <node>
* SYNOPSIS
*
* \cs
* TREENODE_T * TREE_GetNext 
*     ( 
*     TREENODE_T *  root, 
*     TREENODE_T *  node 
*     )
* \ce
*
* DESCRIPTION
*
* This routine finds the first leaf after the specified <node>. You can use 
* this routine or use 'GET NEXT' requests to walk through a tree. However, you 
* need to call another routine to find a starting point, for example 
* TREE_GetPrev().
* To perform a simple 'GET NEXT' request for an object Id, an application can 
* call TREE_GetPrev() with the object Id and call TREE_GetNext() with the node 
* returned by TREE_GetPrev().
*
* PARAMETERS
* \is
* \i <*root>
* Specify the <root> of the tree structure 'TREENODE_T'.
* \i <*node>
* Specify the <node>. To find the first leaf in a tree, set this value to 0.
* \ie
*
* RETURNS: If successful, this routine returns a pointer to the node that 
* contains the leaf. If there are no leaves following <node> in the tree, it 
* returns 0.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Delete(), TREE_Extract(), TREE_Get(), 
* TREE_GetPrev(), TREE_Install(), TREE_Name()
*/
#if !defined(NO_PP)
TREENODE_T *
  TREE_GetNext(TREENODE_T *root,
	       TREENODE_T *node)
#else /* NO_PP */
TREENODE_T *
  TREE_GetNext(root, node)
TREENODE_T *root;
TREENODE_T *node;
#endif /* NO_PP */
{
TREENODE_T *lnode;

/* get lnode pointing to the starting point. */
if ((lnode = node) == 0) {
    if ((lnode = root) == 0)
        return(0);
    else {
        if (lnode->status & (TREELEAF | TREETWIN))
	    return(lnode);
        }
    }

while(1) {
    if (lnode->status & TREECHILD)
        lnode = (TREENODE_T *)lnode->child;
    else {
        if (lnode->sibling != 0)
	    lnode = lnode->sibling;
	else
	    while (1) {
	        if ((lnode = lnode->parent) == 0)
		    return(0);
		if (lnode->status & TREETWIN)
		    lnode = lnode->sibling;
		if (lnode->sibling != 0) {
		    lnode = lnode->sibling;
		    break;
		    }
	        }
        }

    if (lnode->status & (TREELEAF | TREETWIN))
	return(lnode);
    }
}

/*******************************************************************************
*
* TREE_Extract - set the pointer to the leaf pointer from the specified node
* SYNOPSIS
*
* \cs
* int TREE_Extract 
*     (
*     TREENODE_T   *  node,
*     PTR_T        *  leaf
*     )
* \ce
*
* DESCRIPTION
*
* This routine sets pointer to the leaf pointer from the specified <node>.
*
* PARAMETERS
* \is
* \i <*node>
* Specify the <node>.
* \i <*leaf>
* Specify the <leaf> pointer.
* \ie
*
* RETURNS: If successful, this routine returns 0. Otherwise, it returns -1.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Delete(), TREE_Get(), TREE_GetNext(), 
* TREE_GetPrev(), TREE_Install(), TREE_Name()
*/
#if !defined(NO_PP)
int
  TREE_Extract(TREENODE_T *node,
	       PTR_T      *leaf)
#else /* NO_PP */
int
  TREE_Extract(node, leaf)
TREENODE_T *node;
PTR_T *leaf;
#endif /* NO_PP */
{
/* make sure we have a node */
if (node == 0)
    return(-1);

if (node->status & TREELEAF) {
    *leaf = node->child;
    return(0);
    }

if (node->status & TREETWIN) {
    *leaf = node->sibling->child;
    return(0);
    }

return(-1);
}

/*******************************************************************************
*
* TREE_Install - install a <leaf> in a <node>
* SYNOPSIS
*
* \cs
* int TREE_Install 
*     ( 
*     TREENODE_T *  node, 
*     PTR_T         leaf 
*     )
* \ce
*
* DESCRIPTION
*
* This routine installs the specified <leaf> in the specified <node>.
*
* \&NOTE: If the node already has a leaf, it is the caller\抯 responsibility to 
* free the leaf.
*
* PARAMETERS
* \is
* \i <*node>
* Specify a 'TREENODE_T' structure.
* \i <leaf>
* Specify the <leaf>.
* \ie
*
* RETURNS: If successful, this routine adds a leaf and returns 0. If <node> is 
* 0 or has a status of 'TREECHILD', there is no room to add a leaf and this 
* routine returns -1.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Delete(), TREE_Extract(), TREE_Get(), 
* TREE_GetNext(), TREE_GetPrev(), TREE_Name()
*/
#if !defined(NO_PP)
int
  TREE_Install(TREENODE_T *node,
	       PTR_T       leaf)
#else /* NO_PP */
int
  TREE_Install(node, leaf)
TREENODE_T *node;
PTR_T leaf;
#endif /* NO_PP */
{
/* make sure we have a node */
if (node == 0)
    return(-1);

/* if we have a leaf just stick the pointer in */
if (node->status & TREELEAF) {
    node->child = leaf;
    return(0);
    }

/* if we have a twin the next node had better be a leaf so stick 
   the pointer there */
if (node->status & TREETWIN) {
    node->sibling->child = leaf;
    return(0);
    }

/* if we have a child we have no place to put the pointer */
if (node->status & TREECHILD)
    return(-1);

/* we have a node that isn't tagged so make it a leaf node and put
   the pointer in */
node->child = leaf;
node->status |= TREELEAF;
return(0);
}

/*******************************************************************************
*
* TREE_Name - determine the node name
* SYNOPSIS
*
* \cs
* int TREE_Name 
*     ( 
*     TREENODE_T *  node, 
*     OIDC_T     *  oidc, 
*     int           len 
*     )
* \ce
*
* DESCRIPTION
*
* This routine walks the tree backward returning the node name.
*
* PARAMETERS
* \is
* \i <*node>
* Specify a 'TREENODE_T' structure.
* \i <*oidc>
* Specify the 'OIDC' index.
* \i <len>
* Specify the maximum number of sub IDs available in <oidc>.
* \ie
*
* RETURNS: If successful, this routine returns the node name in <oidc>. 
* Otherwise, it returns 0. If the name is longer than <oidc,> it returns the 
* number of sub IDs but does not write <oidc>.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Delete(), TREE_Extract(), TREE_Get(), 
* TREE_GetNext(), TREE_GetPrev(), TREE_Install()
*/
#if !defined(NO_PP)
int
  TREE_Name(TREENODE_T *node,
	    OIDC_T     *oidc,
	    int		len)
#else /* NO_PP */
int
  TREE_Name(node, oidc, len)
TREENODE_T *node;
OIDC_T     *oidc;
int	    len;
#endif /* NO_PP */
{
int i, j;
TREENODE_T *anc;

/* make sure we have a node */
if (node == 0)
    return(0);

/* count the number of subids */
for(i = 1, anc = node; anc->parent != 0; i++, anc = anc->parent)
    ;

if (i > len)
    return(i);

/* save the number of subids for return */
j = i;

/* build the objid, going up the levels */
for(anc = node; i > 0; i--, anc = anc->parent)
    oidc[i-1] = anc->name;

return(j);
}