rtree.c

基于h323协议的软phone

    if (!rtH || (location < 0)) return RV_ERROR_UNKNOWN;

    /* If we've got any child, then we return the child */
    if ((tmp = rtHead(rtH, location)) >= 0) return tmp;

    /* Go up the tree until we find a brother for one of the nodes */
    for (cur = location; (cur >= 0) && (cur != root); cur = rtParent(rtH, cur))
        if ((tmp = rtBrother(rtH, cur)) >= 0)
            return tmp;

    /* Looks like we're done */
    return RV_ERROR_UNKNOWN;
}


static int /* node id of the leftmost deepest child of parent */
rtLeftMostChild(
        HRTREE rtH,
        int parent)
{
  int cur, prev;

  if (!rtH || parent<0) return RV_ERROR_UNKNOWN;
  /*for (cur=parent; rtHead(rtH, cur) >=0; cur = rtHead(rtH, cur)); return cur;*/

  prev=cur=parent;
  while (cur>=0) {
    prev=cur;
    cur=rtHead(rtH, cur);
  }

  return prev;
}


static int /* Next node in preorder or negative value if travel is completed. */
rtNextPreorder(
           /*
         PRE ORDER traveling. Iterative implementation using 'location' as current pointer.
         */
           IN  HRTREE rtH,
           IN  int root, /* root of sub-tree */
           IN  int location)
{
  int tmp;

  if (location == root) return RV_ERROR_UNKNOWN;
  if ((tmp=rtBrother(rtH, location)) <0) return rtParent(rtH, location);

  return rtLeftMostChild(rtH, tmp);
}


static int /* RV_TRUE or negative value on failure */
rtMove2Other(
         /* move sub-tree to another sub-tree, when not on the same tree. */
         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 */
         )
{
  HRA raH = (HRA)rtH;
  rtNode *destNode, *srcNode;
  int cur;

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

  /* -- delete dest childs */
  while (rtDelete(rtH, rtHead(rtH, destNodeId), fdelete, param) == RV_TRUE);

  /* -- move src root to dest root (+pointers) */
  srcNode = (rtNode *)raGet(raH, srcRootId);
  destNode = (rtNode *)raGet(raH, destNodeId);
  destNode->child = srcNode->child;

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

  /* -- update childrens parent reference */
  for (cur=destNode->child; cur >=0; cur=rtBrother(rtH, cur)) {
    rtNode *childNode = (rtNode *)raGet(raH, cur);
    childNode->parent = destNodeId;
  }

  /* -- delete src root node */
  srcNode->child = RV_ERROR_UNKNOWN;
  /*srcNode->brother = RV_ERROR_UNKNOWN;*/
  if (!keepSrcRoot) rtDeleteNode(rtH, srcRootId, NULL, NULL);

  return RV_TRUE;
}










/************************************************************************
 *
 *                              Public functions
 *
 ************************************************************************/


/************************************************************************
 * rtConstruct
 * purpose: Create an RTREE object
 * input  : elemSize            - Size of elements in the RTREE in bytes
 *          maxNumOfElements    - Number of elements in RTREE
 *          logMgr              - Log manager to use
 *          name                - Name of RTREE (used in log messages)
 * output : none
 * return : Handle to RTREE constructed on success
 *          NULL on failure
 ************************************************************************/
HRTREE rtConstruct(
    IN int          elemSize,
    IN int          maxNumOfElements,
    IN const char*  name)
{
    HRA raH;

    /* Create the RA pool used by RTREE */
    raH = raConstruct((int)(elemSize + sizeof(rtNode) - sizeof(void*)), maxNumOfElements, RV_FALSE, name);

    return (HRTREE)raH;
}


/************************************************************************
 * rtDestruct
 * purpose: Deallocates an RTREE object
 * input  : rtH - RTREE handle
 * output : none
 * return : none
 ************************************************************************/
void rtDestruct(IN HRTREE rtH)
{
    raDestruct((HRA)rtH);
}


/************************************************************************
 * rtClear
 * purpose: Clear an RTREE object for any allocated nodes
 * input  : rtH - RTREE handle
 * output : none
 * return : none
 ************************************************************************/
void rtClear(IN HRTREE rtH)
{
    raClear((HRA)rtH);
}


/************************************************************************
 * rtSetCompareFunc
 * purpose: Set the compare function to use
 * input  : rtH     - Handle of the RTREE object
 *          func    - Compare function to use
 * output : none
 * return : none
 ************************************************************************/
void rtSetCompareFunc(IN HRTREE rtH, IN RTECompare func)
{
    raSetCompareFunc((HRA)rtH, (RAECompare)func);
}


/************************************************************************
 * rtSetPrintFunc
 * purpose: Set the print function to use
 * input  : rtH     - Handle of the RTREE object
 *          func    - Print function to use
 * output : none
 * return : none
 ************************************************************************/
void rtSetPrintFunc(IN HRTREE rtH, IN RTEPFunc func)
{
    raSetPrintFunc((HRA)rtH, (RAEFunc)func);
}


/************************************************************************
 * rtGetByPath
 * purpose: Return the element stored in a node ID
 * input  : rtH     - Handle of the RTREE object
 *          path    - Node ID to get from
 * output : none
 * return : element on success
 *          NULL on failure
 ************************************************************************/
RTElement rtGetByPath(IN HRTREE rtH, IN int path)
{
    rtNode* pNode;

    if (path >= 0)
    {
        pNode = (rtNode *)raGet((HRA)rtH, path);
        if (pNode != NULL)
            return (RTElement)(&(pNode->data));
    }

    return NULL;
}


/************************************************************************
 * rtGetRoot
 * purpose: Get the root node of the tree for the given node
 * input  : rtH     - Handle of the RTREE object
 *          nodeId  - Node ID whose root we're looking for
 * output : none
 * return : Root node ID on success
 *          Negative value on failure
 * This function returns a negative value if the given nodeId is the root
 * itself
 ************************************************************************/
int rtGetRoot(
    IN  HRTREE  rtH,
    IN  int     nodeId)
{
    int curNode = nodeId;
    int prevNode = RV_ERROR_UNKNOWN;

    if (rtH == NULL) return RV_ERROR_UNKNOWN;

    /* Search the root until we find it */
    while (curNode >= 0)
    {
        prevNode = curNode;

        /* Get the current node's parent */
        curNode = rtParent(rtH, curNode);
    }

    return prevNode;
}


/************************************************************************
 * rtGetByIndex
 * purpose: Find one of the children of a parent node by its index
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Parent's node ID
 *          index   - Index of searched child (1-based)
 * output : none
 * return : Child's Node id on success
 *          Negative value on failure
 ************************************************************************/
int rtGetByIndex(
    IN HRTREE   rtH,
    IN int      parent,
    IN int      index)
{
    HRA raH = (HRA)rtH;
    rtNode* pNode;
    int cur, i;

    if (index < 1) return RV_ERROR_UNKNOWN;

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

    for (i = 1, cur = pNode->child; (i < index) && rtVALID_NODE(cur); i++)
    {
        pNode = (rtNode *)raGet(raH, cur);
        cur = pNode->brother;
    }

    return cur;
}


/************************************************************************
 * rtParent
 * purpose: Get the parent node of the given node
 * input  : rtH     - Handle of the RTREE object
 *          node    - Node ID whose parent we're looking for
 * output : none
 * return : Parent node ID on success
 *          Negative value on failure
 ************************************************************************/
int rtParent(IN HRTREE rtH, IN int node)
{
    rtNode* pNode;

    if (node >= 0)
    {
        pNode = (rtNode *)raGet((HRA)rtH, node);
        if (pNode == NULL)
            return RV_ERROR_UNKNOWN;

        return pNode->parent;
    }

    return RV_ERROR_UNKNOWN;
}


/************************************************************************
 * rtBrother
 * purpose: Get the next node in the same level of the current node.
 *          This is referred to as the brother of the current node.
 * input  : rtH     - Handle of the RTREE object
 *          node    - Node ID whose brother we're looking for
 * output : none
 * return : Brother's node ID on success
 *          Negative value on failure
 ************************************************************************/
int rtBrother(IN HRTREE rtH, IN int node)
{
    rtNode* pNode;

    pNode = (rtNode *)raGet((HRA)rtH, node);
    if (!pNode) return RV_ERROR_UNKNOWN;

    return pNode->brother;
}


/************************************************************************
 * rtHead
 * purpose: Get the first child node of the current parent node
 *          If we want to get all of the child nodes, we can call
 *          rtBrother() from hear on until we get an error
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Node ID whose first child we're looking for
 * output : none
 * return : First child's node ID on success
 *          Negative value on failure
 ************************************************************************/
int rtHead(IN HRTREE rtH, IN int parent)
{
    rtNode* node;

    if (parent >= 0)
    {
        node = (rtNode *)raGet((HRA)rtH, parent);
        if (node != NULL)
            return node->child;
    }

    return RV_ERROR_UNKNOWN;
}


/************************************************************************
 * rtTail
 * purpose: Get the last child node of the current parent node
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Node ID whose last child we're looking for
 * output : none
 * return : Last child's node ID on success
 *          Negative value on failure
 ************************************************************************/
int rtTail(IN HRTREE rtH, IN int parent)
{
    HRA raH = (HRA)rtH;
    rtNode* pNode;
    int cur;
    int lastCur = RV_ERROR_UNKNOWN;

    /* Get the parent's node before we begin */
    pNode = (rtNode *)raGet(raH, parent);
    if (!pNode) return RV_ERROR_UNKNOWN;

    /* Travel through the nodes by the brothers until we're done */
    for (cur = pNode->child; rtVALID_NODE(cur); cur = pNode->brother)
    {
        lastCur = cur;

        /* Check the next node for its brother */
        pNode = (rtNode *)raGet(raH, cur);
    }

    return lastCur;
}


/************************************************************************
 * rtIndex
 * purpose: Get the index of the given child under the parent node
 * input  : rtH     - Handle of the RTREE object
 *          parent  - Node ID of the parent
 *          child   - Child's node ID
 * output : none
 * return : Index of the child inside the parent (1-based)
 *          Negative value on failure
 ************************************************************************/
int rtIndex(IN HRTREE rtH, IN int parent, IN int child)
{
    HRA raH = (HRA)rtH;
    rtNode* pNode;
    int cur;
    int index = 1;

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

    /* Search through the children until we find the one matching the one we're looking for */
    for (cur = pNode->child; (cur != child) && rtVALID_NODE(cur); cur = pNode->brother)
    {
        pNode = (rtNode *)raGet(raH, cur);
        index++;
    }

    if (cur == child)
        return index;
    else
        return RV_ERROR_UNKNOWN;
}