rtree.c

基于h323协议的软phone

  if (!destH || !srcH) return RV_ERROR_UNKNOWN;
  if (destRootId<0 || srcRootId <0) return RV_ERROR_UNKNOWN;
  if (raElemSize(destRH) != raElemSize(srcRH)) return RV_ERROR_UNKNOWN;
  if (rtTreeSize(destH, destRootId) != rtTreeSize(srcH, srcRootId)) return RV_ERROR_UNKNOWN;

  for (destCur = destRootId, srcCur = srcRootId;
       destCur >=0 && srcCur >=0;
       destCur = rtNext(destH, destRootId, destCur), srcCur = rtNext(srcH, srcRootId, srcCur)) {
    if (rtNumChilds(destH, destCur) != rtNumChilds(srcH, srcCur)) return RV_ERROR_UNKNOWN;
    if (fcompare) {
      if (!fcompare(rtGetByPath(destH, destCur), rtGetByPath(srcH, srcCur), param))
    return RV_ERROR_UNKNOWN;
    }
    else {
      if (memcmp(rtGetByPath(destH, destCur), rtGetByPath(srcH, srcCur),
                 (RvSize_t)raElemSize(destRH) - sizeof(rtNode) + sizeof(void*)))
    return RV_ERROR_UNKNOWN;
    }
  }

  return RV_TRUE;
}



/*___________________________________move________________________________*/

/*___________________________________Family Relocations________________________________*/
int /* RV_TRUE or negative value on failure */
rtAdoptChild(
         /* Child is adopted by its new family. new brother is a child of new parent. */
         IN  HRTREE rtH,
         IN  int adoptedChildId, /* child to be adopted by the new family */
         IN  int newParentId, /* parent of adopted child. -1: become root */
         IN  int newBrotherId /* previously born child (left brother). -1: first born */
         )
{
  HRA raH = (HRA)rtH;
  rtNode *adoptedNode;
  int parent; /* adoptedChild current parent */


  if (!rtH) return RV_ERROR_UNKNOWN;
  if (newParentId<0) newParentId=RV_ERROR_UNKNOWN;
  if (newBrotherId<0) newBrotherId=RV_ERROR_UNKNOWN;
  if ( (adoptedNode = (rtNode *)raGet(raH, adoptedChildId)) == NULL) return RV_ERROR_UNKNOWN;

  /* -- check legitimacy of new parent and brother and relations */
  if (newParentId >=0) {
    if (raGet(raH, newParentId) == NULL) return RV_ERROR_UNKNOWN;
    if (newBrotherId >=0) {
      if ( raGet(raH, newBrotherId) == NULL) return RV_ERROR_UNKNOWN;
      if ( rtParent(rtH, newBrotherId) != newParentId) return RV_ERROR_UNKNOWN;
    }
  }

  /* -- remove former relations */
  parent = rtParent(rtH, adoptedChildId);
  if (parent >=0)  { /* update parent links */
    if (rtHead(rtH, parent) == adoptedChildId) /* leftmost child */
      rtSetChild(rtH, parent, rtBrother(rtH, adoptedChildId));
    else { /* has left brother */
      int cur;
      for (cur=rtHead(rtH, parent); rtBrother(rtH, cur) != adoptedChildId; cur=rtBrother(rtH, cur));
      rtSetBrother(rtH, cur, rtBrother(rtH, adoptedChildId));
    }
  }

  /* -- join your new family */
  adoptedNode->parent = newParentId;
  adoptedNode->brother = rtBrother(rtH, newBrotherId); /* apart your younger brother */

  if (newParentId<0) return RV_TRUE; /* become head of the family. I.e. root */

  if (newBrotherId<0) { /* become first born child */
    adoptedNode->brother = rtHead(rtH, newParentId);
    rtSetChild(rtH, newParentId, adoptedChildId);
    return RV_TRUE;
  }

  rtSetBrother(rtH, newBrotherId, adoptedChildId);
  return RV_TRUE;
}



/*___________________________________Delete________________________________*/

int /* RV_TRUE or negative value on failure */
rtDeleteNode(
         /* delete this node and update links (parent or brother) */
         /* Must be a leaf (no childs) */
         IN  HRTREE rtH,
         IN  int location,  /* this node id */
         IN  RTEFunc fdelete, /* delete function */
         IN  void *param
         )
{
  int parent;

  if (!rtGetByPath(rtH, location))
    return RV_ERROR_UNKNOWN; /* delete root node */


  if (rtHead(rtH, location) >=0)  /* no childs allowed */
    return RV_ERROR_UNKNOWN; /* delete root node */


  /* -- user delete node */
  if (fdelete)
    if (!(param = fdelete(rtH, location, param)))
      return RV_ERROR_UNKNOWN; /* delete root node */


  parent = rtParent(rtH, location);
  if (parent >=0)  { /* update parent links */
    if (rtHead(rtH, parent) == location) /* leftmost child */
      rtSetChild(rtH, parent, rtBrother(rtH, location));
    else { /* has left brother */
      int cur;
      for (cur=rtHead(rtH, parent); rtBrother(rtH, cur) != location; cur=rtBrother(rtH, cur));
      rtSetBrother(rtH, cur, rtBrother(rtH, location));
    }
  }

  return raDeleteLocation((HRA)rtH, location);
}


int /* RV_TRUE or negative value on failure */
rtDelete(
     /* delete subtree from rootId. Iterative preorder deleting */
     IN  HRTREE rtH,
     IN  int rootId, /* subtree root id */
     IN  RTEFunc fdelete, /* delete function */
     IN  void *param
     )
{
  int cur, nextCur;

  if (rootId <0) return RV_ERROR_UNKNOWN;
  if (SANITY_CHECK(rootId)) return RV_ERROR_UNKNOWN;
  for (cur=rtLeftMostChild(rtH, rootId); cur>=0 && cur != rootId; ) {
    if (SANITY_CHECK(cur)) return RV_ERROR_UNKNOWN;
    nextCur = rtNextPreorder(rtH, rootId, cur);
    /*if (rtDeleteNode(rtH, cur, fdelete, param) <0) return RV_ERROR_UNKNOWN;*/
    if (fdelete) if (!(param = fdelete(rtH, cur, param)))
      return RV_ERROR_UNKNOWN;  /*user delete function*/

    if (raDeleteLocation((HRA)rtH, cur) <0)
      return RV_ERROR_UNKNOWN;


    cur = nextCur;
  }

  if (!raElemIsVacant((HRA)rtH, rootId)) rtSetChild(rtH, rootId, RV_ERROR_UNKNOWN);
  if (rtDeleteNode(rtH, rootId, fdelete, param) <0)
    return RV_ERROR_UNKNOWN; /* delete root node */

  return RV_TRUE;
}


int /* RV_TRUE or negative value on failure */
rtDeleteChilds(
           /* delete all child-sub-trees of rootId. Iterative preorder deleting */
           IN  HRTREE rtH,
           IN  int rootId, /* subtree root id */
           IN  RTEFunc fdelete, /* delete function */
           IN  void *param
           )
{
  if (rootId <0) return RV_ERROR_UNKNOWN;
  while (rtDelete(rtH, rtHead(rtH, rootId), fdelete, param) >0);
  return RV_TRUE;
}


/*___________________________________Search________________________________*/

/*
  Desc: get path of child by key and index.
  Returns: path to child or RV_ERROR_UNKNOWN.
  Note: index >=1

  -> finds the index'th child matching the criteria
  */
int
rtGetChild(HRTREE rtH, int parent, void *param, int index)
{
    HRA raH = (HRA)rtH;
    rtNode *pNode;
    int cur, lastCur=0;
    int found = 0;
    RTECompare compare = (RTECompare)raFCompare(raH);

    if ((index < 1) || (parent < 0))
        return RV_ERROR_UNKNOWN;

    /* scan child list and search for child */
    if ( (pNode = (rtNode *)raGet(raH, parent)) == NULL)
        return RV_ERROR_UNKNOWN;

    cur = pNode->child;
    found = 0;

    if (compare)
    {
        for (; ( (found < index) && rtVALID_NODE(cur) );
             cur = pNode->brother)
        {
            pNode = (rtNode *)raGet(raH, cur);
            lastCur = cur; /* save this location */
            if ( (compare(&(pNode->data), param)) )
                found++;
        }
    }
    else
    {
        for (; ( (found < index) && rtVALID_NODE(cur) );
             cur = pNode->brother)
        {
            pNode = (rtNode *)raGet(raH, cur);
            lastCur = cur; /* save this location */
            if ( pNode->data == param )
                found++;
        }
    }

    /* found! */
    if (found == index)
    {
        return lastCur;
    }

    /* not found... */
    return RV_ERROR_UNKNOWN;
}




int
rtFind(HRTREE rtH, int subTreeRoot, void *param, int index)
{
  HRA raH = (HRA)rtH;
  RTECompare compare = (RTECompare)raFCompare(raH);
  rtNode *pNode;
  int curNode, lastCur=0;
  int hits = 0; /* number of successfull find operations */

  for (curNode = subTreeRoot;
       curNode>=0 && hits<index;
       curNode = rtNext(rtH, subTreeRoot, curNode)) {
    lastCur = curNode;
    pNode = (rtNode *)raGet(raH, curNode);
    if ((compare && compare(&(pNode->data), param)) ||
    pNode->data == param) hits++;
  }

  if (hits == index) return lastCur;
  else return RV_ERROR_UNKNOWN;
}

int
rtCompare(HRTREE rtH, int subTreeRoot, void *param, int index, RTECompare compare)
{
  HRA raH = (HRA)rtH;
  rtNode *pNode;
  int curNode, lastCur=0;
  int hits = 0; /* number of successfull find operations */

  for (curNode = subTreeRoot;
       curNode>=0 && hits<index;
       curNode = rtNext(rtH, subTreeRoot, curNode)) {
    lastCur = curNode;
    pNode = (rtNode *)raGet(raH, curNode);
    if ((compare && compare(&(pNode->data), param)) ||
    pNode->data == param) hits++;
  }

  if (hits == index) return lastCur;
  else return RV_ERROR_UNKNOWN;
}












/*_____________________________________overall__________________________________*/


/************************************************************************
 * rtDoAll
 * purpose: Execute a given function on all of the roots inside RTREE.
 *          Note that this function will only be called on the roots and
 *          not on all the allocated nodes.
 * input  : rtH         - Handle to RTREE
 *          operation   - Function to call on all roots
 *          param       - Context parameter to use on calls
 * output : none
 * return : none
 ************************************************************************/
void rtDoAll(
    IN HRTREE   rtH,
    IN RTEFunc  operation,
    IN void*    param)
{
    int i;
    void* context = param;

    if ((!rtH) || (operation == NULL)) return;

    /* Pass through all the elements, executing the functions on those
       which are used roots */
    for (i = 0; i < raMaxSize((HRA)rtH); i++)
        if (!raElemIsVacant((HRA)rtH, i))
        {
            /* The sanity check is here to make sure the node is RTREE, since
               RTREE and RPOOL reside on the same memory space in the PVT */
            if (!SANITY_CHECK(i) && (rtParent(rtH, i) < 0)) /* only roots */
            {
                /* We change the context by the return value of the function */
                context = operation(rtH, i, context);
            }
        }
}




/*_____________________________________Display__________________________________*/


static int
rtFuncPrintLayer(
         HRTREE rtH,
         int parent,
         int maxLevel, /* -1=infinite */
         void *param,
         void * msa,
         RTEPFunc fpr,
         unsigned int layer
         )
{
  int cur;

  if (parent <0) return RV_TRUE;

  fpr(rtH, parent, (int)layer, param);
  if (maxLevel>=0 && (int)layer>=maxLevel) return RV_TRUE;

  for (cur = rtHead(rtH, parent);
       cur >=0;
       cur = rtBrother(rtH, cur))
    rtFuncPrintLayer(rtH, cur, maxLevel, param, msa, fpr, layer+1);

  return RV_TRUE;
}


int
rtPrint(
          /* Recursive print of tree. */
          IN  HRTREE rtH,
          IN  int parent,
          IN  unsigned int layer, /* start printing layer */
          IN  int maxLevel, /* -1=infinite, 0==>parent node */
          IN  void *param,
          IN  void * msa)
{
    return rtFuncPrintLayer(rtH, parent, maxLevel, param, msa, (RTEPFunc)raGetPrintFunc((HRA)rtH), layer);
}



/*
  Return: path of first root node
  */
int
rtRoot(HRTREE rtH)
{
    HRA raH = (HRA)rtH;
    int hits, cur;

    for (hits=0, cur=0; hits<1 && cur<raMaxSize(raH); cur++)
        if ((raElemIsVacant(raH, cur) == RV_FALSE) && (rtParent(rtH, cur) <0)) hits++;

    return (hits==1)?(cur-1):(RV_ERROR_UNKNOWN);
}


int /* current number of elements */
rtCurSize(HRTREE rtH)
{
  return raCurSize((HRA)rtH);
}

int /* returns maximum number of elements. */
rtMaxSize(HRTREE rtH)
{
  return raMaxSize((HRA)rtH);
}

int /* tree max usage */
rtMaxUsage(HRTREE rtH)
{  return raMaxUsage((HRA)rtH); }



#ifdef __cplusplus
}
#endif