rtree.c

基于h323协议的软phone

#ifdef __cplusplus
extern "C" {
#endif



/*
***********************************************************************************

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.

***********************************************************************************
*/

/*
  rtree.c

  Ron S. 29 Jan. 1996

  Tree implementation over array.

  node structure:

                      --------
                ----> | node |
               /      --------
              /
  -------------------------------------------                  --------
  | Child | Parent |     Data     | Brother |  --------------> | node | ------> NULL
  -------------------------------------------                  --------
     |
     |
     |
  --------     --------          --------
  | node |---> | node |   . . .->| node | -> NULL
  --------     --------          --------



  Child:   points to first child or NULL.
  Parent:  points to parent or NULL (if root).
  Brother: points to next brother or NULL (if last brother).
  Data:    contains node information.


  Schema of a tree:

      NULL
       |
     -----
 1  |  1  |--> NULL
     -----
       |
     -----                                   -----
 2  |  2  |-------------------------------->|  3  |--> NULL
     -----       ^         ^                 -----
       |         |         |                   |
     -----     -----     -----               -----
 3  |  4  |-->|  5  |-->|  6  |--> NULL     |  7  |--> NULL
     -----     -----     -----               -----
                 |
               -----
 4            |  8  |--> NULL
               -----

  Node 1: Root node of the tree. Points to <Node 2> as its Child.
  Node 2: Parent is <node 1>. Borther is <node 3>.
          It has 3 children, from them, it points to <node 4> as its Child.
  Node 3: Parent is <node 1>. Borther is NULL. Points to <node 7> as its child.
  Node 4: Parent is <node 2>. Brother is <node 5>. Child is NULL.
  Node 5: Parent is <node 2>. Brother is <node 6>. Child is <node 8>.
  Node 6: Parent is <node 2>. Brother is NULL. Child is NULL.
  Node 7: Parent is <node 3>. Brother is NULL. Child is NULL.
  Node 8: Parent is <node 5>. Brother is NULL, Child is NULL.


  Array Fields Description
  ------------------------

  The following parameters are used for reserving traveling knowlage. The tree
  travel is PREORDER.
  FirstNode: Root node of travel.
  CurNode: Current node in travel. This is the last node being traveled.


  Tree Description:
  -----------------

  A path is a unique identifier of a node in the tree.

  A node can also be identified as a child of parent. However, the key for
  a child might not be unique and so an *index* must be used to identify
  multiple appearences of a key in a child list.


  Parameters:
  -----------
  parent: path of a node. Serves as the root of the operation.
  elem: data content of an element in list. (node data).
  index: of key in the child list. index >= 1. index=1 is the first child of
  parent that match the key.

  */

#include "rtree.h"


/************************************************************************
 * rtNode
 * Node structure, holding the informatino for a tree node.
 * child    - First child node of current node.
 *            Negative value if current node is a leaf
 * parent   - Parent of the current node in the tree.
 *            Negative value if the node is the root of a tree
 * brother  - Next node with the same parent as this node.
 *            Negative value if this node is the last node of the same parent
 * data     - Actual node information, stored here by the user of RTREE
 ************************************************************************/
typedef struct
{
    int     child;
    int     parent;
    int     brother;
    void*   data;
} rtNode;


/* Check if the given node is a valid one */
#define rtVALID_NODE(cur)  ((cur) >= 0)


/* RTREE and RPOOL can live in the same memory space. This is the way things are done
   in the PVT.
   To allow this, and to know which of the two are occupying a specified node, the
   first 4 bytes in each node are slightly different in RTREE and RPOOL.
   An RPOOL's node always has 0x40000000 used.
   An RTREE node never has this bit on.
   We don't use 0x80000000 as this bit to allow 0xffffffff to be used in RTREE as an invalid
   child node.
 */
#define MUCH_BIGGER_THEN_VALID_RT_LOCATION 0x1ffffffU
#define SANITY_CHECK(nodeId) ((RvUint32)(rtHead(rtH,nodeId)- RV_ERROR_UNKNOWN)>MUCH_BIGGER_THEN_VALID_RT_LOCATION)
/* SANITY_CHECK makes sure that the node's child is an RTREE node by making sure that
   the nodes' value is small enough (meaning bit 0x40000000 is not used), and taking into
   account that it's value can be RV_ERROR_UNKNOWN (-1)
 */
    /* if there is no children this gives false    :: (RV_ERROR_UNKNOWN - RV_ERROR_UNKNOWN)>MUCH_BIGGER_THEN_VALID_RT_LOCATION */
    /* if there is valid child this gives false too:: (VALID_LOCATION - RV_ERROR_UNKNOWN)==VALID_LOCATION+1 >MUCH_BIGGER_THEN_VALID_RT_LOCATION */
    /* only if the child value is really invalid (the rpool NODE) this is RV_TRUE  */






/************************************************************************
 *
 *                              Private functions
 *
 ************************************************************************/


/************************************************************************
 * rtAddNode
 * purpose: Add a node into RTREE
 * input  : rtH     - Handle to RTREE
 *          elem    - Element data to add
 *                    If NULL, then an empty element is added
 *          parent  - Added node's parent
 *                    Negative value if it's an added root
 *          brother - Added node's brother
 *                    Negative value if there's no brother to the right
 *                    of the current node
 * output : none
 * return : Added node's ID on success
 *          Negative value on failure
 ************************************************************************/
static int rtAddNode(
    IN HRTREE       rtH,
    IN RTElement    elem,
    IN int          parent,
    IN int          brother)
{
    HRA raH = (HRA)rtH;
    rtNode* node;
    int location;
    RvSize_t size = (RvSize_t)(raElemSize(raH) - sizeof(rtNode) + sizeof(void*));

    /* Add the node */
    location = raAdd(raH, (RAElement *)&node);
    if (location < 0) return location;

    /* Set all of the family :-) */
    node->child     = RV_ERROR_UNKNOWN; /* no children */
    node->parent    = parent;
    node->brother   = brother;

    /* Set the data itself */
    if (elem != NULL)
        memcpy((void *)&(node->data), (void *)elem, size);
    else
        memset((void *)&(node->data), 0, size);

    return location;
}


/************************************************************************
 * rtSetChild
 * purpose: Set a node as the first child of another node
 *          This function doesn't fix anything in the tree. It will unlink
 *          the previous child of the given parent node
 * input  : rtH     - Handle to RTREE
 *          parent  - Parent ID whose child we're going to set
 *          child   - Child ID to set
 * output : none
 * return : Non-negative value on success
 *          Negative value on failure
 ************************************************************************/
static int rtSetChild(
    IN  HRTREE  rtH,
    IN  int     parent,
    IN  int     child)
{
    rtNode* node;

    /* Get the parent */
    node = (rtNode *)raGet((HRA)rtH, parent);
    if (!node) return RV_ERROR_UNKNOWN;

    node->child = child;
    return 0;
}


/************************************************************************
 * rtSetBrother
 * purpose: Set a node as the right brother of another node
 *          This function doesn't fix anything in the tree. It will unlink
 *          the previous brother of the given node
 * input  : rtH         - Handle to RTREE
 *          location    - Node ID whose brother we're changing
 *          brother     - New brother ID to set
 * output : none
 * return : Non-negative value on success
 *          Negative value on failure
 ************************************************************************/
static int rtSetBrother(
    IN  HRTREE  rtH,
    IN  int     location,
    IN  int     brother)
{
    rtNode* node;

    /* Get the node */
    node = (rtNode *)raGet((HRA)rtH, location);
    if (!node) return RV_ERROR_UNKNOWN;

    node->brother = brother;
    return 0;
}


/************************************************************************
 * rtAddTree
 * purpose: Iterative copy of a source subtree under a destination parent
 *          node as its last child.
 *          - The source and destination RTREE elements must have the same size
 *          - There should be enough room in the destination for the source
 *            subtree
 * input  : destH           - Handle to destination RTREE
 *          destParentId    - Destination parent node. We're going to add
 *                            a new child to it (a last child)
 *          srcH            - Handle to source RTREE
 *          srcRootId       - The node ID of the source tree we're adding
 *                            under the destination parent node.
 *          fadd            - User's add function - called for every
 *                            added node in the tree.
 *                            If this function returns NULL, it is considered
 *                            an error in the execution of rtAddTree.
 *                            can be set to NULL
 *          param           - Context parameter to use on calls to fadd
 *          check           - Indicate if we want some sanity checks or not
 * output : none
 * return : Node ID of the new subtree in the destination tree on success
 *          Negative value on failure
 ************************************************************************/
static int rtAddTree(
    IN  HRTREE  destH,
    IN  int     destParentId,
    IN  HRTREE  srcH,
    IN  int     srcRootId,
    IN  RTEFunc fadd, /* user add node function */
    IN  void*   param,
    IN  RvBool  check /* false==> no checks */
      )
{
    HRA destRH = (HRA)destH;
    HRA srcRH = (HRA)srcH;
    int destParent, destNewSubTree, srcNode;

    if (check)
    {
        /* Make sure we've got everything right */
        if ((destH == NULL) || (srcH == NULL)) return RV_ERROR_UNKNOWN;
        if ((destParentId < 0) || (srcRootId < 0)) return RV_ERROR_UNKNOWN;

        /* Make sure element sizes are the same in both RTREEs */
        if (raElemSize(destRH) != raElemSize(srcRH)) return RV_ERROR_UNKNOWN;

        /* Make sure we've got enough room in the destination RTREE */
        if (raFreeSize(destRH) < rtTreeSize(srcH, srcRootId)) return RV_ERROR_UNKNOWN;
    }

    /* Add the new subtree as the last child of the given destination node */
    destNewSubTree = rtAddTail(destH, destParentId, rtGetByPath(srcH, srcRootId));

    /* See if we're done already */
    if (rtHead(srcH, srcRootId) < 0)
    {
        /* The source root node is a leaf in the tree */
        if (fadd)
            if (!(param = fadd(destH, destNewSubTree, param))) return RV_ERROR_UNKNOWN;
        return destNewSubTree;
    }


    /* Let's prepare for an iterative copy */
    srcNode = srcRootId;
    destParent = destNewSubTree;

    /* Copy all nodes in PRE-ORDER */
    while ((srcNode >= 0) && (destParent >= 0))
    {
        /* Call the add function of the user on the current destination parent */
        if (fadd)
            if (!(param = fadd(destH, destParent, param))) return RV_ERROR_UNKNOWN;

        /* 1. CHILD - copy any first born and go on through the first-borns first */
        if (rtHead(srcH, srcNode) >= 0)
        {
            /* Add the child to the destination */
            srcNode = rtHead(srcH, srcNode);
            destParent = rtAddTail(destH, destParent, rtGetByPath(srcH, srcNode));

            /* Skip everything and check the child first */
            continue;
        }

        /* 2. BROTHER - copy any close brother and check the brother for first-borns first */
        if (rtBrother(srcH, srcNode) >= 0)
        {
            /* Add the brother to the destination */
            srcNode = rtBrother(srcH, srcNode);
            destParent = rtAddTail(destH, rtParent(destH, destParent), rtGetByPath(srcH, srcNode));

            /* Skip everything and check the brother first */
            continue;
        }

        /* 3. If we're here, then we're now going up the tree up to its source root,
              each time covering all of the brothers of each level and their sub-trees
         */

        for (srcNode = rtParent(srcH, srcNode), destParent = rtParent(destH, destParent);
             (srcNode >= 0) && (srcNode != srcRootId);
             srcNode = rtParent(srcH, srcNode), destParent = rtParent(destH, destParent))
        {
            /* We'll stop on the first node that has a brother, since we haven't
               dealt with that brother yet */
            if (rtBrother(srcH, srcNode) >= 0)
            {
                /* Stop on this brother */
                srcNode = rtBrother(srcH, srcNode);
                break;
            }
        }

        /* See if we're done */
        if ((srcNode < 0) || (srcNode == srcRootId))
            break; /* completed */

        /* Add the node to the destination */
        destParent = rtAddTail(destH, rtParent(destH, destParent), rtGetByPath(srcH, srcNode));

    } /* while */

    if(destParent >= 0)
        return destNewSubTree;
    return destParent;
}


/************************************************************************
 * rtAddTree
 * purpose: Get the next node in post order for a given sub-tree.
 * input  : rtH         - Handle of RTREE
 *          root        - Root node ID of the sub-tree to traverse
 *          location    - Current location in sub-tree
 * output : none
 * return : Next node ID on success
 *          Negative value when done or on failure
 ************************************************************************/
static int rtNextPostorder(
    IN HRTREE   rtH,
    IN int      root,
    IN int      location)
{
    int cur, tmp;

    /*
    Algorithm:
        if (child) return child;
        while (parent != root) {
          if (parent->brother) return parent->brother;
          parent = parent->parent;
        }
        return Completed!
     */