view release on metacpan or  search on metacpan

src/subversion/subversion/libsvn_delta/compose_delta.c  view on Meta::CPAN

    return;

  scratch_node.left = scratch_node.right = NULL;
  left = right = &scratch_node;

  for (;;)
    {
      if (offset < tree->offset)
        {
          if (tree->left != NULL
              && offset < tree->left->offset)
            {
              /* Right rotation */
              range_index_node_t *const node = tree->left;
              tree->left = node->right;
              node->right = tree;
              tree = node;
            }
          if (tree->left == NULL)
            break;

          /* Remember the right subtree */
          right->left = tree;
          right = tree;
          tree = tree->left;
        }
      else if (offset > tree->offset)
        {
          if (tree->right != NULL
              && offset > tree->right->offset)
            {
              /* Left rotation */
              range_index_node_t *const node = tree->right;
              tree->right = node->left;
              node->left = tree;
              tree = node;
            }
          if (tree->right == NULL)
            break;

          /* Remember the left subtree */
          left->right = tree;
          left = tree;
          tree = tree->right;
        }
      else
        break;
    }

  /* Link in the left and right subtrees */
  left->right = tree->left;
  right->left = tree->right;
  tree->left  = scratch_node.right;
  tree->right = scratch_node.left;

  /* The basic top-down splay is finished, but we may still need to
     turn the tree around. What we want is to put the node with the
     largest offset where node->offset <= offset at the top of the
     tree, so that we can insert the new data (or search for existing
     ranges) to the right of the root. This makes cleaning up the
     tree after an insert much simpler, and -- incidentally -- makes
     the whole range index magic work. */
  if (offset < tree->offset && tree->left != NULL)
    {
      if (tree->left->right == NULL)
        {
          /* A single right rotation is enough. */
          range_index_node_t *const node = tree->left;
          tree->left = node->right; /* Which is always NULL. */
          node->right = tree;
          tree = node;
        }
      else
        {
          /* Slide down to the rightmost node in the left subtree. */
          range_index_node_t **nodep = &tree->left;
          while ((*nodep)->right != NULL)
            nodep = &(*nodep)->right;

          /* Now move this node to root in one giant promotion. */
          right = tree;
          left = tree->left;
          tree = *nodep;
          *nodep = tree->left;
          right->left = tree->right; /* Which is always NULL, too. */
          tree->left = left;
          tree->right = right;
        }
    }

  /* Sanity check ... */
  assert((offset >= tree->offset)
         || ((tree->left == NULL)
             && (tree->prev == NULL)));
  ndx->tree = tree;
}


/* Remove all ranges from NDX that fall into the root's range.  To
   keep the range index as small as possible, we must also remove
   nodes that don't fall into the new range, but have become redundant
   because the new range overlaps the beginning of the next range.
   Like this:

       new-range: |-----------------|
         range-1:         |-----------------|
         range-2:                |--------------------|

   Before new-range was inserted, range-1 and range-2 were both
   necessary. Now the union of new-range and range-2 completely covers
   range-1, which has become redundant now.

   FIXME: But, of course, there's a catch. range-1 must still remain
   in the tree if we want to optimize the number of target copy ops in
   the case were a copy falls within range-1, but starts before
   range-2 and ends after new-range. */

static void
delete_subtree(range_index_t *ndx, range_index_node_t *node)
{
  if (node != NULL)