tree.c

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

/* tree.c - tree.c routines */

/*
 *  Copyright 2000-2005 Wind River Systems, Inc.
 *  All rights reserved.  Provided under license only.
 *  Distribution or other use of this software is only
 *  permitted pursuant to the terms of a license agreement
 *  from Wind River Systems (and is otherwise prohibited).
 *  Refer to that license agreement for terms of use.
 */

/*
 *  Copyright 1993-1997 Epilogue Technology Corporation.
 *  Copyright 1998 Integrated Systems, Inc.
 *  All rights reserved.
 */

/*
 * $Log: tree.c,v $
 * Revision 1.2  2001/11/06 21:20:29  josh
 * revised new path hacking
 *
 * Revision 1.1.1.1  2001/11/05 17:47:43  tneale
 * Tornado shuffle
 *
 * Revision 9.2  2001/01/19 22:22:28  paul
 * Update copyright.
 *
 * Revision 9.1  2000/03/17 00:19:26  meister
 * Update copyright message
 *
 * Revision 9.0  1998/10/16 22:12:24  sar
 * Update version stamp to match release
 *
 * Revision 8.3  1998/06/19 20:13:55  sar
 * make sure all files include asn1conf.h and snmp.h to pick up all of
 * the common code
 *
 * Revision 8.2  1998/06/05 18:53:24  sra
 * "#include <foo.h>" => "#include <envoy/h/foo.h>".
 *
 * Revision 8.1  1998/02/25 04:52:46  sra
 * Update copyrights.
 *
 * Revision 8.0  1997/11/18 00:57:04  sar
 * Updated revision to 8.0
 *
 * Revision 7.3  1997/10/16 00:48:09  sar
 * In tree_add make sure we set the parent pointer for all cases
 *
 * Revision 7.2  1997/03/20 06:49:23  sra
 * DFARS-safe copyright text.  Zap!
 *
 * Revision 7.1  1997/02/25 10:49:26  sra
 * Update copyright notice, dust under the bed.
 *
 * Revision 7.0  1996/03/18 20:01:11  sar
 * Updated revision to 7.0 and copyright to 96
 *
 * Revision 6.0  1995/05/31  21:48:24  sra
 * Release 6.0.
 *
 * Revision 5.1  1994/07/27  18:30:06  sar
 * Modified TREE_GetPrev.  Previously after finding a node whose next
 * sibling's name was greater than the current oid we would stop and
 * were supposed to descend the subtree starting at the first node.
 * Instead we would follow the sibling chain and then descend the last
 * siblings subtree.
 *
 * Revision 5.0  1994/05/16  15:42:42  sar
 * Updated revision to 5.0 and copyright to include 1994
 *
 * Revision 4.1  1994/05/10  20:16:03  sar
 * Remvoed the #if for version 2 as we can use trees with v1 (sub agent stuff)
 *
 * Revision 4.0  1993/06/24  15:45:46  sar
 * Updated revision to 4.0 and copyright to 93
 *
 * Revision 1.12  1993/06/02  23:09:24  dab
 * Changed #ifdef's to #if's for things from install.h
 *
 * Revision 1.11  1993/05/10  14:22:04  sar
 * Modfied Get and Get_Prev to return the current node when reaching the end
 * of the oid list.  (Previously we would do one extra child decesnt under some
 * conditions.
 *
 * Revision 1.10  1993/04/30  22:54:08  sar
 * Added mechanism for minimial proxies and coarse grained locks.  The
 * latter required the addition of routines to get the name of a leaf given
 * a pointer to the leaf.
 *
 * Revision 1.9  1993/04/22  20:06:36  sar
 * Much updating of macros and install options, mostly we now use
 * ISNTALL_ENVOY_SNMP_VERSION_1 or _2, VERSION_RFCXXXX is now SNMP_VERSION_2
 * and other similiar items.
 *
 */

/* [clearcase]
modification history
-------------------
01e,12may05,job  fix apigen comments
01d,18apr05,job  update copyright notices
01c,04mar05,job  apigen update
01b,23feb05,job  apigen for documented APIs
01a,24nov03,job  update copyright information
*/

/*
DESCRIPTION
This library contains tree.c routines.

INCLUDE FILES: snmp.h, tree.h
*/

#include <wrn/wm/snmp/engine/asn1conf.h>
#include <wrn/wm/snmp/engine/snmp.h>
#include <wrn/wm/snmp/engine/tree.h>

/*******************************************************************************
*
* TREE_Add - add a leaf to the tree
* SYNOPSIS
*
* \cs
* int TREE_Add 
*     ( 
*     TREENODE_T **  root, 
*     OIDC_T      *  oidc, 
*     int            oidclen, 
*     PTR_T          leaf, 
*     TREENODE_T **  retnode 
*     )
* \ce
*
* DESCRIPTION
*
* This routine adds a leaf to the specified tree at the position indicated by 
* <oidc> and <oidclen>. If necessary, this routine creates any missing 
* intermediate nodes.
*
* \&NOTE: To make a leaf self-identifying, you can include space for the 
* back-pointer in the leaf\抯 structure.
*
* 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'.
* \i <leaf>
* Specify the <leaf> node.
* \i <**retnode>
* Specify a pointer to the 'TREENODE_T' that has a pointer to <leaf>.
* \ie
*
* RETURNS: If successful, this routine returns 0 and fills <retnode> with a 
* pointer to the 'TREENODE_T' that has a pointer to <leaf>. Otherwise, it 
* returns -1. Failures can occur when space cannot be allocated for a node or 
* when a <leaf> already exists at the specified node.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Delete(), TREE_Extract(), TREE_Get(), TREE_GetNext(), 
* TREE_GetPrev(), TREE_Install(), TREE_Name()
*/
#if !defined(NO_PP)
int
  TREE_Add(TREENODE_T **root,
	   OIDC_T      *oidc,
	   int		oidclen,
	   PTR_T        leaf,
	   TREENODE_T **retnode)
#else /* NO_PP */
int
  TREE_Add(root, oidc, oidclen, leaf, retnode)
TREENODE_T **root;
OIDC_T      *oidc;
int	     oidclen;
PTR_T	     leaf;
TREENODE_T **retnode;
#endif /* NO_PP */
{
UINT_32_T status = 0;
TREENODE_T *node, *newnode, **prevnodeptr, *parent = 0;;

/* make sure there is something to the oid */
if ((oidclen == 0) || (oidc == 0))
    return(-1);

/* match the given oid against the tree until we can't match a subid
   or run out of components */
for(node = *root, prevnodeptr = root; (node != 0) && (node->name <= *oidc); ){ 
    if (node->name != *oidc) {
	prevnodeptr = &(node->sibling);
	node = node->sibling;
	continue;
	}

    if (oidclen == 1) {
        /* Out of subids so the leaf node goes on this level */
        /* if we have a leaf or twin return an error */
        if (node->status & (TREELEAF | TREETWIN))
	    return(-1);

        /* If we don't have a child install the leaf here. */
	if (!(node->status & TREECHILD)) {
	    node->status |= TREELEAF;
	    node->child = leaf;
	    *retnode = node;
	    return(0);
	    }

	/* We have a child so install the leaf after the child */
	newnode = (TREENODE_T *)SNMP_memory_alloc(sizeof(TREENODE_T));
	if (newnode == 0)
	    return(-1);
	newnode->parent  = parent;
	newnode->name    = node->name;
	newnode->status  = TREELEAF;
	newnode->sibling = node->sibling;
	newnode->child   = leaf;
	*retnode = newnode;

	node->status  |= TREETWIN;
	node->sibling  = newnode;
	return(0);
        }
	    
    /* More subids to go so this is a child level */
    /* If the current node is a leaf node we need to add a child node before 
       the leaf node and prepare for twining */
    if (node->status & TREELEAF) {
        status = TREETWIN;
        break;
        }

    /* Normal conditions, follow the child */
    oidc++;
    oidclen--;
    parent = node;
    prevnodeptr = (TREENODE_T **)&(node->child);
    node = (TREENODE_T *)node->child;
    }

/* build nodes for the part of the oid that wasn't in the tree */
/* create the node that gets linked into the current tree */
newnode = (TREENODE_T *)SNMP_memory_alloc(sizeof(TREENODE_T));
if (newnode == 0)
    return(-1);
newnode->parent  = parent;
newnode->name    = *oidc;
newnode->status  = status | TREECHILD;
newnode->sibling = node;
/* mostly set to be linked in we made need to update the status if this is
   the leaf pointer.  save it in case something fails */
node = newnode;

for(parent = node, oidclen--, oidc++; oidclen > 0; oidclen--, oidc++) {
    newnode = (TREENODE_T *)SNMP_memory_alloc(sizeof(TREENODE_T));
    if (newnode == 0) {
	/* free the chain */
        while(node->child != 0) {
	    node = (TREENODE_T *)node->child;
	    SNMP_memory_free(node->parent);
	    }
	SNMP_memory_free(node);
        return(-1);
        }
    newnode->parent  = parent;
    newnode->name    = *oidc;
    newnode->status  = TREECHILD;
    newnode->sibling = 0;
    /* link the child to the parent and step the parent down */
    parent->child    = (PTR_T)newnode;
    parent 	     = newnode;
    }

/* declare the last structure a leaf structure and put the leaf pointer in */
newnode->child = leaf;
newnode->status = (newnode->status & ~TREECHILD) | TREELEAF;
*retnode = newnode;

/* link the chain into the tree */
*prevnodeptr = node;
return(0);
}

/*******************************************************************************
*
* TREE_Delete - delete a node and any ancestors without other descendants
* SYNOPSIS
*
* \cs
* int TREE_Delete 
*     ( 
*     TREENODE_T   **  root, 
*     TREENODE_T    *  node 
*     )
* \ce
*
* DESCRIPTION
*
* This routine deletes the specified node and any ancestors that do not have 
* other descendants or leaves from the tree with the root of <root>.
*
* \&NOTE: The node must not have any children. If it has a leaf, it is the 
* responsibility of the calling routine to move or free the leaf.
*
* PARAMETERS
* \is
* \i <**root>
* Specify the <root> of the tree structure 'TREENODE_T'.
* \i <*node>
* Specify the <node> to delete.
* \ie
*
* RETURNS: If successful, this routine returns 0. Otherwise, it returns -1.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Extract(), TREE_Get(), TREE_GetNext(), 
* TREE_GetPrev(), TREE_Install(), TREE_Name()
*/
#if !defined(NO_PP)
int
  TREE_Delete(TREENODE_T **root,
	      TREENODE_T  *node)
#else /* NO_PP */
int
  TREE_Delete(root, node)
TREENODE_T **root;
TREENODE_T  *node;
#endif /* NO_PP */
{
TREENODE_T *parent;

/* make sure we have a node to work with and a tree to put delete it from */
if ((node == 0) || (*root == 0))
    return(-1);

/* if we have a twin unlink and free the node that points to the leaf */
/* we don't have any other work as we know we have another sibling */
if (node->status & TREETWIN) {
    parent = node->sibling;
    if (parent->status & TREESTATIC)
        return(-1);
    node->status &= ~TREETWIN;
    node->sibling = parent->sibling;
    SNMP_memory_free(parent);
    return(0);
    }

/* the node has children or is static */
if (node->status & (TREECHILD || TREESTATIC))
    return(-1);

/* walk up the parent chain until we have other siblings, run out of parents
   or run into a parent that isn't dynamic */
for(parent = node->parent; ;node = parent, parent = node->parent) {

    /* if we are at the top of the tree clean up the root pointers */
    if (parent == 0) {
        if (*root == node)
	    *root = node->sibling;
	else {
	    for(parent = *root;
		 parent->sibling != node;
		 parent = parent->sibling)
	         ;
	    parent->sibling = node->sibling;
	    }
	break;
        }

    /* does this node have siblings or is the parent static */
    if ((node->sibling != 0) ||
	(parent->child != (PTR_T) node) ||
	(parent->status & TREESTATIC)) {
        if (parent->child == (PTR_T) node)
	    parent->child = (PTR_T)node->sibling;
	else {
	    for(parent = (TREENODE_T *)parent->child;
		 parent->sibling != node;
		 parent = parent->sibling)
	        ;
	    parent->sibling = node->sibling;
	    }
        break;
        }
  }

/* we have removed a chain from the tree now free the chain */
while(node->status & TREECHILD) {
    node = (TREENODE_T *)node->child;
    SNMP_memory_free(node->parent);
    }
SNMP_memory_free(node);
return(0);
}

/*******************************************************************************
*
* TREE_Get - search a tree for a specified <node>
* SYNOPSIS
*
* \cs
* TREENODE_T * TREE_Get 
*     ( 
*     TREENODE_T *  root, 
*     OIDC_T     *  oidc, 
*     int           oidclen, 
*     int        *  length 
*     )
* \ce
*
* DESCRIPTION
*
* This routine searches a tree starting from <root> for the node specified by 
* <oidc> and <oidclen>.
*
* 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'.
* \i <*length>
* Specify the number of 'OIDC_Ts' consumed from <oidc>.
* \ie
*
* RETURNS: If successful, this routine returns a pointer to the last node 
* matched. Otherwise, it returns a pointer to 0.
*
* ERRNO: N/A
*
* SEE ALSO: TREE_Add(), TREE_Delete(), TREE_Extract(), TREE_GetNext(), 
* TREE_GetPrev(), TREE_Install(), TREE_Name()
*/
#if !defined(NO_PP)
TREENODE_T *
  TREE_Get(TREENODE_T *root,
	   OIDC_T     *oidc,
	   int	       oidclen,
	   int	      *length)
#else /* NO_PP */
TREENODE_T *
  TREE_Get(root, oidc, oidclen, length)
TREENODE_T *root;