rtree.c

基于h323协议的软phone

/************************************************************************
 * rtNumChilds
 * purpose: Get the number of child nodes under a given node
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Node ID of the parent
 * output : none
 * return : Number of child nodes under the parent
 *          Negative value on failure
 ************************************************************************/
int rtNumChilds(IN HRTREE rtH, IN int parent)
{
    HRA raH = (HRA)rtH;
    rtNode* pNode;
    int numChilds = 0;
    int cur=0; /* current location of child node */

    /* Get the parent */
    pNode = (rtNode *)raGet(raH, parent);
    if (!pNode) return RV_ERROR_UNKNOWN;

    /* scan child list and search for child */
    for (cur = pNode->child; rtVALID_NODE(cur); cur = pNode->brother)
    {
        pNode = (rtNode *)raGet(raH, cur);
        numChilds++;
    }

    return numChilds;
}


/************************************************************************
 * rtNext
 * purpose: Get the next node for a given node ID
 *          This function can be used to traverse the tree, each time
 *          returning another node ID inside the tree.
 *          This function uses POST-ORDER traversal of the tree
 * input  : rtH         - Handle of the RTREE object
 *          root        - Root node ID of the sub-tree we're traversing
 *          location    - Current node ID
 * output : none
 * return : Next node ID in the tree on success
 *          Negative value when done or on failure
 ************************************************************************/
int rtNext(
    IN  HRTREE  rtH,
    IN  int     root,
    IN  int     location)
{
    return rtNextPostorder(rtH, root, location);
}


/************************************************************************
 * rtAddRoot
 * purpose: Add a new root node as a tree to RTREE
 * input  : rtH     - Handle of the RTREE object
 *          elem    - Element to add as root
 *                    If given as NULL, an empty element is added
 * output : none
 * return : Node ID of the new root on success
 *          Negative value on failure
 ************************************************************************/
int rtAddRoot(
    IN  HRTREE      rtH,
    IN  RTElement   elem)
{
    return rtAddNode(rtH, elem, RV_ERROR_UNKNOWN, RV_ERROR_UNKNOWN);
}


/************************************************************************
 * rtAddHead
 * purpose: Add a new node as the first child, before any other of a given
 *          parent node
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Parent's node ID
 *          elem    - Element to add
 *                    If given as NULL, an empty element is added
 * output : none
 * return : Node ID of the added node on success
 *          Negative value on failure
 ************************************************************************/
int rtAddHead(
    IN  HRTREE      rtH,
    IN  int         parent,
    IN  RTElement   elem)
{
    rtNode* pNode;
    int location;
    HRA raH = (HRA)rtH;

    /* Get the parent */
    pNode = (rtNode *)raGet(raH, parent);
    if (!pNode) return RV_ERROR_UNKNOWN;

    /* Add the element as the first child */
    location = rtAddNode(rtH, elem, parent, pNode->child);
    if (location < 0) return location;

    /* Make sure the parent knows it's first born */
    pNode->child = location;

    return location;
}


/************************************************************************
 * rtAddTail
 * purpose: Add a new node as the last child of a parent
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Parent's node ID
 *          elem    - Element to add
 *                    If given as NULL, an empty element is added
 * output : none
 * return : Node ID of the added node on success
 *          Negative value on failure
 ************************************************************************/
int rtAddTail(
    IN  HRTREE      rtH,
    IN  int         parent,
    IN  RTElement   elem)
{
    rtNode* pNode;
    rtNode* lastChild;
    int location, tailNode;
    HRA raH = (HRA)rtH;

    /* Get the parent */
    pNode = (rtNode *)raGet(raH, parent);
    if (!pNode) return RV_ERROR_UNKNOWN;

    /* Find the last child of this parent if we have to */
    tailNode = rtTail(rtH, parent);
    if (tailNode >= 0)
        lastChild = (rtNode *)raGet(raH, tailNode);
    else
        lastChild = NULL;

    /* Add the node after the last child */
    location = rtAddNode(rtH, elem, parent, RV_ERROR_UNKNOWN);
    if (location < 0) return location;

    if (lastChild != NULL)
    {
        /* There's a last child - make sure it's connects the new one as it's brother */
        lastChild->brother = location;
    }
    else
    {
        /* There are no children to this parent - it's the first born */
        pNode->child = location;
    }

    return location;
}



/************************************************************************
 * rtAddBrother
 * purpose: Add a new node as the closest (right) brother of a given node
 * input  : rtH     - Handle of the RTREE object
 *          brother - Brother node we're joining to the right
 *          elem    - Element to add
 *                    If given as NULL, an empty element is added
 * output : none
 * return : Node ID of the added node on success
 *          Negative value on failure
 ************************************************************************/
int rtAddBrother(
    IN  HRTREE      rtH,
    IN  int         brother,
    IN  RTElement   elem)
{
    rtNode* pNode;
    int location;
    HRA raH = (HRA)rtH;

    /* Get the brother */
    pNode = (rtNode *)raGet(raH, brother);
    if (!pNode) return RV_ERROR_UNKNOWN;

    /* Add this element after our given bro' */
    location = rtAddNode(rtH, elem, pNode->parent, pNode->brother);
    if (location < 0) return location;

    /* Make sure the older brother knows of this new brother */
    pNode->brother = location;

    return location;
}


/************************************************************************
 * rtAdd
 * 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 rtAdd.
 *                            can be set to NULL
 *          param           - Context parameter to use on calls to fadd
 * output : none
 * return : Node ID of the added node on success
 *          Negative value on failure
 ************************************************************************/
int rtAdd(
    IN  HRTREE  destH,
    IN  int     destParentId,
    IN  HRTREE  srcH,
    IN  int     srcRootId,
    IN  RTEFunc fadd,
    IN  void*   param)
{
    return rtAddTree(destH, destParentId, srcH, srcRootId, fadd, param, RV_TRUE);
}


/************************************************************************
 * rtAdd
 * purpose: Iterative copy of all the children of a source node under a
 *          destination parent node as its last children.
 *          - 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 whose children
 *                            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 rtAddChilds.
 *                            can be set to NULL
 *          param           - Context parameter to use on calls to fadd
 * output : none
 * return : Non-negative value on success
 *          Negative value on failure
 ************************************************************************/
int rtAddChilds(
    IN  HRTREE  destH,
    IN  int     destParentId,
    IN  HRTREE  srcH,
    IN  int     srcRootId,
    IN  RTEFunc fadd,
    IN  void*   param)
{
    int cur, result;

    if ((destParentId < 0) || (srcRootId < 0)) return RV_ERROR_UNKNOWN;

    /* Go throught the source root's children and copy them one by one */
    for (cur = rtHead(srcH, srcRootId); cur >= 0; cur = rtBrother(srcH, cur))
    {
        result = rtAdd(destH, destParentId, srcH, cur, fadd, param);
        if (result < 0) return result;
    }

    return 0;
}


/************************************************************************
 * rtSet
 * purpose: Copy a source sub-tree onto destParentId, deleting any previous
 *          content and nodes under destParentId
 *          - 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 delete
 *                            it and copy srcRootId onto it
 *          srcH            - Handle to source RTREE
 *          srcRootId       - The node ID of the source tree we'll copy
 *          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 rtAddChilds.
 *                            can be set to NULL
 *          fdelete         - User's delete function - caled for every
 *                            deleted node under destParentId, including destParentId
 *          param           - Context parameter to use on calls to fadd and fdelete
 * output : none
 * return : Non-negative value on success
 *          Negative value on failure
 ************************************************************************/
int rtSet(
    IN  HRTREE  destH,
    IN  int     destParentId,
    IN  HRTREE  srcH,
    IN  int     srcRootId,
    IN  RTEFunc fadd,
    IN  RTEFunc fdelete,
    IN  void*   param)
{
    HRA destRH = (HRA)destH;
    HRA srcRH = (HRA)srcH;
    int cur;
    rtNode* destNode;
    rtNode* srcNode;

    if (!destH || !srcH) return RV_ERROR_UNKNOWN;
    if (destParentId < 0 || srcRootId < 0) return RV_ERROR_UNKNOWN;
    if (raElemSize(destRH) != raElemSize(srcRH)) return RV_ERROR_UNKNOWN;
/*  if (raFreeSize(destRH) < rtTreeSize(srcH, srcRootId)) return RV_ERROR_UNKNOWN;*/

    /* -- delete all children sub-trees */
    while (rtDelete(destH, rtHead(destH, destParentId), fdelete, param) >= 0);

    /* -- delete destination root node */
    if (fdelete)
        if (!(param = fdelete(destH, destParentId, param))) return RV_ERROR_UNKNOWN;

    /* -- set dest parent */
    srcNode = (rtNode *)raGet(srcRH, srcRootId);
    destNode = (rtNode *)raGet(destRH, destParentId);
    if (!destNode || !srcNode) return RV_ERROR_UNKNOWN;

    memcpy((void *)&(destNode->data), (void *)&(srcNode->data),
           (RvSize_t)raElemSize(destRH) - sizeof(rtNode) + sizeof(void*));

    if (fadd)
        if (!(param = fadd(destH, destParentId, param))) return RV_ERROR_UNKNOWN;

    /* -- add all src childs under dest parent */
    for (cur = rtHead(srcH, srcRootId); cur >= 0; cur = rtBrother(srcH, cur))
        if (rtAddTree(destH, destParentId, srcH, cur, fadd, param, RV_FALSE) < 0)
            return RV_ERROR_UNKNOWN;

    return 0;
}


/* move sub-tree to another sub-tree, NO restriction */
int rtMove(
    IN  HRTREE  rtH,
    IN  int     destNodeId,
    IN  int     srcRootId,
    IN  RvBool  keepSrcRoot, /* true==> srcRoot node not deleted */
    IN  RTEFunc fdelete,  /* user delete node function */
    IN  void*   param       /* for add and delete user functions */
    )
  /* using temporary node (R) */
{
  HRA raH = (HRA)rtH;
  int R;

  if (!rtH) return RV_ERROR_UNKNOWN;
  if (destNodeId<0 || srcRootId <0) return RV_ERROR_UNKNOWN;
  if (raFreeSize(raH) < 1 /*rtTreeSize(rtH, srcRootId)+1*/) return RV_ERROR_UNKNOWN;

  R = rtAddRoot(rtH, NULL);
  rtMove2Other(rtH, R, srcRootId, keepSrcRoot, fdelete, param);
  rtMove2Other(rtH, destNodeId, R, RV_FALSE, fdelete, param);
  return 0;
}









int /* number of nodes in sub-tree */
rtTreeSize(
       /* calc. num of nodes in subtree */
       IN  HRTREE rtH,
       IN  int rootId
       )
{
  int cur, count;

  if (!rtH) return RV_ERROR_UNKNOWN;

  for (count=0, cur=rtHead(rtH, rootId); cur>=0; cur = rtNext(rtH, rootId, cur))
    count++;
  return count+1;
}








/*_________________________________two trees operations________________________________*/



int /* RV_TRUE or negative value on failure */
rtCompareTrees(
           /* Compare between two trees.
          The trees must be structure identical.
          The compare function check node content.
          */
           IN  HRTREE destH,
           IN  int destRootId,
           IN  HRTREE srcH,
           IN  int srcRootId,
           IN  RTECompareTwo fcompare, /* compare two nodes */
           IN  void *param /* for compare function */
           )
{
  HRA destRH = (HRA)destH;
  HRA srcRH = (HRA)srcH;
  int destCur, srcCur;