comparison src/intervals.c @ 39851:a535a2e3b5c4

(traverse_intervals): Use less stack space. (traverse_intervals_noorder): New function. (search_for_interval, count_intervals): Use it.

39850:80b844540f64

  return 1;
}


/* Traverse an interval tree TREE, performing FUNCTION on each node.
   Pass FUNCTION two args: an interval, and ARG.  */

void
traverse_intervals (tree, position, depth, function, arg)
     INTERVAL tree;
     int position, depth;
     void (* function) P_ ((INTERVAL, Lisp_Object));
     Lisp_Object arg;
{
  if (NULL_INTERVAL_P (tree))
    return;

  traverse_intervals (tree->left, position, depth + 1, function, arg);
  position += LEFT_TOTAL_LENGTH (tree);
  tree->position = position;
  (*function) (tree, arg);
  position += LENGTH (tree);
  traverse_intervals (tree->right, position, depth + 1,  function, arg);
}

#if 0

static int icount;

     register INTERVAL i, tree;
{
  icount = 0;
  search_interval = i;
  found_interval = NULL_INTERVAL;
  traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
  return found_interval;
}

static void
inc_interval_count (i)

     register INTERVAL i;
{
  icount = 0;
  idepth = 0;
  zero_length = 0;
  traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);

  return icount;
}

static INTERVAL

   B       =>       A
  / \		   / \
     c		  c
*/

static INTERVAL
rotate_right (interval)
     INTERVAL interval;
{
  INTERVAL i;
  INTERVAL B = interval->left;

      B	   =>     A
     / \         / \    
    c               c
*/

static INTERVAL
rotate_left (interval)
     INTERVAL interval;
{
  INTERVAL i;
  INTERVAL B = interval->right;

39851:a535a2e3b5c4

  return 1;
}


/* Traverse an interval tree TREE, performing FUNCTION on each node.
   No guarantee is made about the order of traversal.
   Pass FUNCTION two args: an interval, and ARG.  */

void
traverse_intervals_noorder (tree, function, arg)
     INTERVAL tree;
     void (* function) P_ ((INTERVAL, Lisp_Object));
     Lisp_Object arg;
{
  /* Minimize stack usage.  */
  while (!NULL_INTERVAL_P (tree))
    {
      (*function) (tree, arg);
      if (NULL_INTERVAL_P (tree->right))
	tree = tree->left;
      else
	{
	  traverse_intervals_noorder (tree->left, function, arg);
	  tree = tree->right;
	}
    }
}

/* Traverse an interval tree TREE, performing FUNCTION on each node.
   Pass FUNCTION two args: an interval, and ARG.  */

void
traverse_intervals (tree, position, depth, function, arg)
     INTERVAL tree;
     int position, depth;
     void (* function) P_ ((INTERVAL, Lisp_Object));
     Lisp_Object arg;
{
  while (!NULL_INTERVAL_P (tree))
    {
      traverse_intervals (tree->left, position, depth + 1, function, arg);
      position += LEFT_TOTAL_LENGTH (tree);
      tree->position = position;
      (*function) (tree, arg);
      position += LENGTH (tree); tree = tree->right; depth++;
    }
}

#if 0

static int icount;

     register INTERVAL i, tree;
{
  icount = 0;
  search_interval = i;
  found_interval = NULL_INTERVAL;
  traverse_intervals_noorder (tree, &check_for_interval, Qnil);
  return found_interval;
}

static void
inc_interval_count (i)

     register INTERVAL i;
{
  icount = 0;
  idepth = 0;
  zero_length = 0;
  traverse_intervals_noorder (i, &inc_interval_count, Qnil);

  return icount;
}

static INTERVAL

   B       =>       A
  / \		   / \
     c		  c
*/

static INLINE INTERVAL
rotate_right (interval)
     INTERVAL interval;
{
  INTERVAL i;
  INTERVAL B = interval->left;

      B	   =>     A
     / \         / \    
    c               c
*/

static INLINE INTERVAL
rotate_left (interval)
     INTERVAL interval;
{
  INTERVAL i;
  INTERVAL B = interval->right;