changeset 39851:a535a2e3b5c4

(traverse_intervals): Use less stack space. (traverse_intervals_noorder): New function. (search_for_interval, count_intervals): Use it.
author Stefan Monnier <monnier@iro.umontreal.ca>
date Fri, 12 Oct 2001 21:53:44 +0000
parents 80b844540f64
children 00ea1715c90a
files src/intervals.c
diffstat 1 files changed, 36 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
--- a/src/intervals.c	Fri Oct 12 21:42:09 2001 +0000
+++ b/src/intervals.c	Fri Oct 12 21:53:44 2001 +0000
@@ -188,6 +188,30 @@
 
 
 /* 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
@@ -197,15 +221,14 @@
      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);
+  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
@@ -236,7 +259,7 @@
   icount = 0;
   search_interval = i;
   found_interval = NULL_INTERVAL;
-  traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
+  traverse_intervals_noorder (tree, &check_for_interval, Qnil);
   return found_interval;
 }
 
@@ -258,7 +281,7 @@
   icount = 0;
   idepth = 0;
   zero_length = 0;
-  traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
+  traverse_intervals_noorder (i, &inc_interval_count, Qnil);
 
   return icount;
 }
@@ -285,7 +308,7 @@
      c		  c
 */
 
-static INTERVAL
+static INLINE INTERVAL
 rotate_right (interval)
      INTERVAL interval;
 {
@@ -331,7 +354,7 @@
     c               c
 */
 
-static INTERVAL
+static INLINE INTERVAL
 rotate_left (interval)
      INTERVAL interval;
 {