* Makefile.am (BFD32_LIBS): Add arange-set.lo.

  (BFD32_LIBS_CFILES): Add arange-set.c.
  (SOURCE_HFILES): Add arange-set.h
  (dwarf2.lo): Add dependency upon arange-set.h.
  (arange-set.lo): New target.
* Makefile.in: Regenerate.
* arange-set.c: New file.
* arange-set.h: New file.
* dwarf2.c: Include arange-set.h.
  (struct dwarf2_debug) Add new fields comp_unit_count and comp_unit_arange_set.
  (struct comp_unit) Replace field arange with a new field arange_set.
  (dwarf2_arange_set_allocate, dwarf2_arange_set_deallocate,
  (dwarf2_combine_arange_value, dwarf2_arange_set_new,
  (dwarf2_arange_set_with_value_new, dwarf2_comp_unit_arange_add): New
  functions to utilize arange set in dwarf2.c.
  (arange_add): Formatting change for a line longer than 80 characters.
  (decode_line_info): Replace call target arange_add with
  (dwarf2_comp_unit_arange_add.
  (read_rangelist_insert_arange_list,
  (read_rangelist_comp_unit_arange_add): New functions used as callbacks
  for read_rangelist.
  (read_rangelist): Change interface to accept a callback and data to
  allow caller to select the action peformed on a new range list read.
  (scan_unit_for_symbols): Use new interface of read_rangelist.
  (parse_comp_unit): Create an arange set for each new comp unit.  Use new
  interface of read_rangelist.  Replace call to arange_add with that to
  dwarf2_comp_unit_arange_add.
  (comp_unit_contains_address): Replace sequential search with a call to
  arange_set_lookup_address, which can handles large set efficiently.
  (stash_copy_local_aranges, stash_maybe_enable_arange_set,
  (stash_find_nearest_line_fast): New functions maintaining and using a
  valued global arange set for all compilation units to speed up
  bfd_dwarf2_find_nearest_line.
  (find_line): Use global arange set.  Replace sequential search over all
  compilation units with a call to stash_find_nearest_line_fast.  Add
  book keeping to count number of compilation units.  Replace empty
  arange list test with a call to arange_set_empty_p.

1 files changed, 729 insertions, 0 deletions

diff --git a/bfd/arange-set.c b/bfd/arange-set.c
new file mode 100644
index 0000000..0a6c2f0
--- /dev/null
+++ b/bfd/arange-set.c
@@ -0,0 +1,729 @@
+/* DWARF 2 Arange-Set.
+   Copyright 2007 Free Software Foundation, Inc.
+   Contributed by Doug Kwan, Google Inc.
+ 
+   This file is part of BFD.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or (at
+   your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+   MA 02110-1301, USA.  */
+
+#include "sysdep.h"
+#include "bfd.h"
+#include "libiberty.h"
+#include "libbfd.h"
+#include "arange-set.h"
+#include "splay-tree.h"
+
+/* Implementation of an arange-set.  The set is implemented using the
+   splay tree support in libiberty.  The advantage of using this is
+   that it has been well tested and is relatively simple to use.  The
+   disadvantage is that it is too general and it does not fit our design
+   exactly.  So we waste a bit of memory for unneeded generality and work
+   around for mis-match between the splay tree API and the arange-set
+   internals.  A specialized implentation of a balanced tree type for
+   arange-set exclusively may speed up things a little and reduce memory
+   consumption.  Until there is a pressing need, we stick to the splay
+   tree in libiberty.  */
+
+struct arange_set_s
+{
+  /* Splay tree containing aranges.  */
+  splay_tree ranges;
+
+  /* Lowest address in set.  If set is empty, it is ~0.  */
+  bfd_vma lower_bound;
+
+  /* Highest address in set.  If set is empty, it is 0.  */
+  bfd_vma upper_bound;
+
+  /* TRUE if aranges in this set have values.  */
+  bfd_boolean value_p;
+
+  /* Function to compare arange values.  */
+  arange_value_equal_fn value_equal_fn;
+
+  /* Function to copy an arange value.  */
+  arange_value_copy_fn value_copy_fn;
+
+  /* Function to combine arange values.  */
+  arange_value_combine_fn value_combine_fn;
+
+  /* Function to delete an arange value.  */
+  arange_value_delete_fn value_delete_fn;
+
+  /* Function to allocate a piece of memory.  */
+  arange_set_allocate_fn allocate_fn;
+
+  /* Function to deallocate a piece of memory.  */
+  arange_set_deallocate_fn deallocate_fn;
+
+  /* Call back data shared by all callbacks.  */
+  void *data;
+};
+
+/* Structure for aranges with a value attached.  Since a splay tree
+   node can only hold one value,  we need to use the container struct
+   to store data associated with an arange and have the splay tree value
+   to be a pointer to this struct. */
+
+typedef struct
+{
+  /* High-pc of an arange.  This is different from the DWARF2 semantics that
+     the high-pc is really the last location in an arange.  */
+  bfd_vma high;
+
+  /* We need to store a pointer to the set because splay_tree_value_delete
+     only takes a pointer to the value deleted.  If we use a deallocator
+     that need extra information like a pointer to the memory pool, we need to
+     look up via the set pointer.  This adds one extra pointer per arange. */
+  arange_set set;
+
+  /* Value associated with this arange.  */
+  arange_value_type value;
+
+} arange_value_container_t;
+
+
+
+static void
+arange_set_delete_value (arange_set set, arange_value_type value)
+{
+  if (set->value_delete_fn)
+    (set->value_delete_fn) (value, set->data);
+}
+
+/* Compare two VMAs as keys of splay tree nodes.  */
+
+static int
+splay_tree_compare_bfd_vmas (splay_tree_key k1, splay_tree_key k2)
+{
+  if ((bfd_vma) k1 < (bfd_vma) k2)
+    return -1;
+  else if ((bfd_vma) k1 > (bfd_vma) k2)
+    return 1;
+
+  return 0;
+}
+
+/* Default memory allocator and deallocator.  */
+
+void *
+arange_set_allocate (arange_set set, int size)
+{
+  if (set->allocate_fn)
+    return (set->allocate_fn) (size, set->data); 
+
+  return xmalloc (size);
+}
+
+void
+arange_set_deallocate (arange_set set, void *object)
+{
+  if (set->deallocate_fn)
+    (set->deallocate_fn) (object, set->data); 
+  else
+    free (object);
+}
+
+static void
+arange_set_delete_value_container (splay_tree_value value)
+{
+  arange_value_container_t *container;
+
+  container = (arange_value_container_t*) value;
+  arange_set_delete_value (container->set, container->value);
+  arange_set_deallocate (container->set, container);
+}
+
+/* Create an arange set.  Return the new set of NULL if there is any
+   error.  
+
+   allocate_fn is the memory allocator function of this arange set. If
+   it is NULL, the default allocator will be used.
+
+   deallocate_fn is the memory deallocator function of this arange set. If
+   it is NULL, the default allocator will be used.
+
+   value_p specifies whether an arange set supports values.  If it is
+   TURE.  Each arange can be associated with a value of type arange_value_type.
+   If it is FALSE, the following parameters value_equal_fn, value_copy_fn,
+   value_combine_fn and value_delete_fn will be ignored.
+
+   value_equal_fn is the value equality function.  An arange uses it to
+   check if two values are the same.  If it is NULL, the default bit-wise
+   equality function will be used.
+
+   value_copy_fn is the value copy function.  An arange uses it to copy
+   values of type arange_value_type.  If it is NULL, the default bit-wise
+   copy function will be used.
+
+   value_combine_fn is the value combine function. An arange uses it to
+   combine values of two identical arange.  If it is NULL, the default
+   constant zero function will be used.
+
+   value_delete_fn is the value deletion function. If it is not NULL,
+   it will be called when an arange deletes a value.
+
+   data is pointer to an object, which will be passed to all allocate_fn,
+   deallocate_fn, value_equal_fn, value_copy_fn, value_combine_fn and
+   value_delete_fn.  */
+
+arange_set
+arange_set_new (arange_set_allocate_fn allocate_fn,
+		arange_set_deallocate_fn deallocate_fn,
+		bfd_boolean value_p,
+		arange_value_equal_fn value_equal_fn,
+		arange_value_copy_fn value_copy_fn,
+		arange_value_combine_fn value_combine_fn,
+		arange_value_delete_fn value_delete_fn,
+		void *data)
+{
+  arange_set set;
+  splay_tree sp;
+  splay_tree_delete_value_fn fn;
+
+  /* Allocate space for arange structure.  */
+  set = (arange_set)
+    (*allocate_fn) (sizeof (struct arange_set_s), data);
+  if (!set)
+    return set;
+  
+  fn = value_p ? arange_set_delete_value_container : NULL;
+  sp = splay_tree_new_with_allocator (splay_tree_compare_bfd_vmas, NULL,
+				      fn, allocate_fn, deallocate_fn,
+				      data);
+  if (!sp)
+    {
+      (deallocate_fn) (set, data);
+      return NULL;
+    }
+
+  set->ranges = sp;
+  set->lower_bound = ~0;
+  set->upper_bound = 0;
+  set->value_p = value_p;
+  set->allocate_fn = allocate_fn;
+  set->deallocate_fn = deallocate_fn;
+  set->value_equal_fn = value_equal_fn;
+  set->value_copy_fn = value_copy_fn;
+  set->value_combine_fn = value_combine_fn;
+  set->value_delete_fn = value_delete_fn;
+  set->data = data;
+  return set;
+}
+
+/*  Delete an arange set.  */
+
+void
+arange_set_delete (arange_set set)
+{
+  splay_tree_delete (set->ranges);
+  (*set->deallocate_fn) (set, set->data);
+}
+
+/* Return TRUE if and only if arange set is empty.  */
+
+bfd_boolean
+arange_set_empty_p (arange_set set)
+{
+  return set->lower_bound > set->upper_bound;
+}
+
+/* Accessors for low and high of an arange.
+ 
+   There is no arange_set_node_set_low since the low address is the
+   key of the splay tree node.  */
+
+/* Get the high VMA address of a node.  */
+
+static bfd_vma
+arange_set_node_high (arange_set set, splay_tree_node node)
+{
+  arange_value_container_t *container;
+
+  if (set->value_p)
+    {
+      container = (arange_value_container_t*) node->value;
+      return container->high;
+    }
+
+  return (bfd_vma) node->value;
+}
+
+/* Set the high VMA address of a node.  */
+
+static void
+arange_set_node_set_high (arange_set set, splay_tree_node node, bfd_vma address)
+{
+  arange_value_container_t *container;
+
+  if (set->value_p)
+    {
+      container = (arange_value_container_t*) node->value;
+      container->high = address;
+    }
+  else
+    node->value = (splay_tree_value) address;
+}
+
+/* Get the low VMA address of a node.  */
+
+static bfd_vma
+arange_set_node_low (splay_tree_node node)
+{
+  return (bfd_vma) node->key;
+}
+
+/* If arange set supports values, return value of an arange; otheriwse
+   always return 0 so that it appears that all aranges have the same value.  */
+
+static arange_value_type
+arange_set_node_value (arange_set set, splay_tree_node node)
+{
+  arange_value_container_t *container;
+
+  if (set->value_p)
+    {
+      container = (arange_value_container_t*) node->value;
+      return container->value;
+    }
+
+  return 0;
+}
+
+/* If arange set supports values, return value of an arange; otheriwse
+   always return 0 so that it appears that all aranges have the same value.  */
+
+static void
+arange_set_node_set_value (arange_set set,
+			   splay_tree_node node,
+			   arange_value_type value)
+{
+  arange_value_container_t *container;
+
+  if (set->value_p)
+    {
+      container = (arange_value_container_t*) node->value;
+      container->value = value;
+    }
+}
+
+/* Return TRUE if and only if arange set supports values.  */
+
+bfd_boolean
+arange_set_has_values_p (arange_set set)
+{
+  return set->value_p;
+}
+
+/* Copy a value using the value copying function of an arange set.  If
+   the set does not support values or if there is not value copying
+   function specified, it simply returns the input value.  */
+
+arange_value_type
+arange_set_copy_value (arange_set set, arange_value_type value)
+{
+  /* If no copy function is specified or set does not support values,
+     default is bit-wise copy.  */
+  if (set->value_p && set->value_copy_fn)
+    return (set->value_copy_fn) (value, set->data);
+
+  return value;
+}
+
+static arange_value_type
+arange_set_combine_value (arange_set set,
+			  arange_value_type value1,
+			  arange_value_type value2)
+{
+  /* If no combine function is specified or set does not support values,
+     default is returning 0.  */
+  if (set->value_p && set->value_combine_fn)
+    return (set->value_combine_fn) (value1, value2, set->data);
+
+  return (arange_value_type) 0;
+}
+
+/* Compares two values for equality.  If the arange set does not support values
+   or if no value equality function is specified, this function simply does
+   a bit-wise comparison.  */
+
+bfd_boolean
+arange_set_value_equal_p (arange_set set,
+			  arange_value_type value1,
+			  arange_value_type value2)
+{
+  /* If no equality function is specified or set does not support values,
+     default is bit-wise comparison.  */
+  if (set->value_p && set->value_equal_fn)
+    return (set->value_equal_fn) (value1, value2, set->data);
+
+  return value1 == value2;
+}
+
+/* Check to see if a given address is in an arange set.  Return TRUE if the
+   address is inside one of the aranges. If low_ptr, high_ptr and value_ptr are
+   used to return lower address, upper address and value associated with a
+   found arounge.  If anyone of them is NULL, the corresponding information
+   is not returned.  For arange set without values, no information is returned
+   through the pointer value_ptr.  */
+
+bfd_boolean
+arange_set_lookup_address (arange_set set, bfd_vma address,
+			   bfd_vma *low_ptr, bfd_vma *high_ptr,
+			   arange_value_type *value_ptr)
+{
+  splay_tree_node pred, node;
+
+  if (address < set->lower_bound || address > set->upper_bound)
+    return FALSE;
+
+  /* Find immediate predecessor.  */
+  pred = splay_tree_predecessor (set->ranges, (splay_tree_key) address);
+  if (pred
+      && arange_set_node_high (set, pred) >= address)
+    node = pred;
+  else
+    /* If the predecessor range does not cover this address, the address
+       is in the arange set only if itself starts an arange.  */
+    node = splay_tree_lookup (set->ranges, (splay_tree_key) address);
+
+  if (node)
+    {
+      /* Also return arange boundaries if caller supplies pointers.  */
+      if (low_ptr)
+	*low_ptr = arange_set_node_low (node);
+      if (high_ptr)
+	*high_ptr = arange_set_node_high (set, node);
+      if (set->value_p && value_ptr)
+	*value_ptr = arange_set_node_value (set, node);
+      return TRUE;
+    }
+
+  return FALSE;
+}
+
+/* Insert an arange [low, high] into a set's splay tree.  If the set supports
+   value, also insert with the given value.  Return the inserted node if there
+   is no error or NULL otherwise.  */
+
+static splay_tree_node
+arange_set_splay_tree_insert (arange_set set,
+			      bfd_vma low,
+			      bfd_vma high,
+			      arange_value_type value)
+{
+  splay_tree_value sp_value;
+  arange_value_container_t *container;
+   
+  if (set->value_p)
+    {
+      int size = sizeof (arange_value_container_t);
+      void *data = set->ranges->allocate_data;
+
+      container =
+	(arange_value_container_t*) (*set->ranges->allocate) (size, data);
+      if (!container)
+	return NULL;
+      container->high = high;
+
+      /* Due to the design of splay tree API, there is no way of passing
+	 callback data to the splay tree value delete function.  Hence we need
+	 to store a pointer to set in every containier!  */
+      container->set = set;
+
+      container->value = value;
+      sp_value = (splay_tree_value) container;
+    }
+  else
+    sp_value = (splay_tree_value) high;	
+
+  /* Currently splay_tree_insert does not return any status to tell if there
+     is an error.  */
+  return splay_tree_insert (set->ranges, (splay_tree_key) low, sp_value);
+}
+
+/* Split [low, high] to [low, address) & [address, high].  */
+
+static bfd_boolean
+arange_set_split_node (arange_set set, splay_tree_node node, bfd_vma address)
+{
+  splay_tree_node node2;
+  arange_value_type value;
+  bfd_vma low, high;
+
+  low = arange_set_node_low (node);
+  high = arange_set_node_high (set, node);
+
+  BFD_ASSERT (low < address && address <= high);
+  
+  value = arange_set_copy_value (set, arange_set_node_value (set, node));
+  node2 = arange_set_splay_tree_insert (set, address, high, value);
+  if (!node2)
+    return FALSE;
+
+  arange_set_node_set_high (set, node, address - 1);
+  return TRUE;
+}
+
+static splay_tree_node
+arange_set_maybe_merge_with_predecessor (arange_set set, splay_tree_node node)
+{
+  splay_tree_node pred;
+  bfd_vma low, high;
+
+  low = arange_set_node_low (node);
+  high = arange_set_node_high (set, node);
+
+  pred = splay_tree_predecessor (set->ranges, low);
+  if (! pred)
+    return node;
+
+  if (arange_set_node_high (set, pred) + 1 == low
+      && arange_set_value_equal_p (set,
+				   arange_set_node_value (set, pred),
+				   arange_set_node_value (set, node)))
+    {
+      splay_tree_remove (set->ranges, arange_set_node_low (node));
+      arange_set_node_set_high (set, pred, high);
+      return arange_set_maybe_merge_with_predecessor (set, pred);	
+    }
+
+  return node;
+}
+
+/* Insert an arange [low,high] into a set. Return TRUE if and only if there
+   is no error.  Note that the address high is also included where as in
+   DWARF2 an address range between low & high means [low,high).
+
+   This only handles sets with values. For the simpler case of sets without
+   value, it is handled in arange_set_insert().  This function is
+   tail-recurive.  It is guaranteed to terminate because it only recurses
+   with a smaller range than it is given.  */
+
+static bfd_boolean
+arange_set_insert_value (arange_set set,
+			 bfd_vma low,
+			 bfd_vma high,
+			 arange_value_type value)
+{
+  splay_tree_node succ, pred, node;
+  bfd_vma succ_high, succ_low;
+  arange_value_type combined, old_value;
+
+  if (low > high)
+    {
+      arange_set_delete_value (set, value);
+      return FALSE;
+    }
+
+  pred = splay_tree_predecessor (set->ranges, low);
+  if (pred && arange_set_node_high (set, pred) >= low)
+    arange_set_split_node (set, pred, low);
+
+  node = splay_tree_lookup (set->ranges, low);
+  if (node)
+    {
+      /* Split node if its arange is larger than inserted arange. */
+      if (arange_set_node_high (set, node) > high)
+	arange_set_split_node (set, node, high + 1);
+
+      old_value = arange_set_node_value (set, node);
+      combined = arange_set_combine_value (set, old_value, value); 
+      arange_set_node_set_value (set, node, combined);
+      node = arange_set_maybe_merge_with_predecessor (set, node);
+      arange_set_delete_value (set, old_value);
+
+      /* Insert remaining arange by tail-recursion.  */
+      if (high > arange_set_node_high (set, node))
+	return arange_set_insert_value (set,
+					arange_set_node_high (set, node) + 1,
+					high, value);
+      else
+	{
+	  /* Node must cover exactly the range. */
+	  BFD_ASSERT (high == arange_set_node_high (set, node));
+	  arange_set_delete_value (set, value);
+	  succ = splay_tree_successor (set->ranges, arange_set_node_low (node));
+	  if (succ)
+	    succ = arange_set_maybe_merge_with_predecessor (set, succ);	
+	  return TRUE;
+	}
+    }
+  
+  succ = splay_tree_successor (set->ranges, low);
+  if (succ)
+    {
+      succ_low = arange_set_node_low (succ);	
+      succ_high = arange_set_node_high (set, succ);
+
+      if (succ_low <= high)
+	{
+	  node = arange_set_splay_tree_insert (set, low, succ_low - 1, value); 
+	  if (!node)
+	    return FALSE;
+
+	  /* Update set lower bound only after insertion is successful.  */
+	  if (low < set->lower_bound)
+	    set->lower_bound = low;
+
+	  node = arange_set_maybe_merge_with_predecessor (set, node);
+
+	  /* Recurse to handle rest of insertion.  Note that we have to copy
+	     value here since it has already been used in the node above.  */
+	  return arange_set_insert_value (set, succ_low, high,
+					  arange_set_copy_value (set, value));
+	}
+     }
+  
+  node = arange_set_splay_tree_insert (set, low, high, value);
+  if (!node)
+    return FALSE;
+
+  /* Update set boundaries only after insertion is successful.  */
+  if (low < set->lower_bound)
+    set->lower_bound = low;
+  if (high > set->upper_bound)
+    set->upper_bound = high;
+
+  node = arange_set_maybe_merge_with_predecessor (set, node);
+
+  succ = splay_tree_successor (set->ranges, arange_set_node_low (node));
+  if (succ)
+    succ = arange_set_maybe_merge_with_predecessor (set, succ);	
+
+  return TRUE;
+}
+
+bfd_boolean
+arange_set_insert (arange_set set,
+		   bfd_vma low,
+		   bfd_vma high,
+		   arange_value_type value)
+{
+  splay_tree tree = set->ranges;
+  splay_tree_node pred, succ, node = NULL;
+  bfd_vma pred_high, node_low;
+
+  if (set->value_p)
+    return arange_set_insert_value (set, low, high, value);
+
+  if (low > high)
+    return FALSE;
+
+  pred = splay_tree_predecessor (tree, low);
+  if (pred)
+    {
+      pred_high = arange_set_node_high (set, pred);
+
+      /* Nothing to be done if predecessor contains new aranges.  */ 
+      if (pred_high >= high)
+	return TRUE;
+
+      /* If we can expand predecessor, do so.  Test for the case in which
+	 predecessor does not contain new arange but touches it.  */
+      if (pred_high >= low || pred_high + 1 == low)
+	{
+	  node = pred;
+	  arange_set_node_set_high (set, node, high);
+	}
+    }
+
+  /* Try to see if [low,something] is already in splay tree.  */ 
+  if (node == NULL)
+    {
+      node = splay_tree_lookup (tree, low); 	
+      if (node)
+	{
+	  /* Nothing to be done if node contains new aranges.  */ 
+	  if (arange_set_node_high (set, node) >= high)
+	    return TRUE;
+
+	  arange_set_node_set_high (set, node, high);
+	}
+    }
+
+  if (node == NULL)
+    {
+      node = arange_set_splay_tree_insert (set, low, high, 0);
+      if (!node)
+	return FALSE;
+    }
+
+  BFD_ASSERT (node
+	      && arange_set_node_low (node) <= low
+	      && arange_set_node_high (set, node) >= high);
+
+  /* Update set upper and lower bounds.  */
+  if (low < set->lower_bound)
+    set->lower_bound = low;
+  if (high > set->upper_bound)
+    set->upper_bound = high;
+
+  /* Merge successor if it overlaps or touches node.  */
+  node_low = arange_set_node_low (node);
+  while ((succ = splay_tree_successor (tree, node_low)) != NULL
+	 && ((arange_set_node_high (set, node) >= arange_set_node_low (succ))
+	     || (arange_set_node_high (set, node) + 1
+		 == arange_set_node_low (succ))))
+    {
+      if (arange_set_node_high (set, succ) > high)
+        arange_set_node_set_high (set, node, arange_set_node_high (set, succ));
+      splay_tree_remove (tree, arange_set_node_low (succ));
+    }
+  return TRUE;
+}
+
+struct arange_set_foreach_adapter_data
+{
+  void *data;
+  arange_set set;
+  arange_set_foreach_fn foreach_fn;
+};
+
+/* Adaptor to make arange_set_foreach works with splay_tree_foreach.  */
+
+static int
+arange_set_foreach_adapter (splay_tree_node node, void *data)
+{
+  struct arange_set_foreach_adapter_data *adapter_data;
+  arange_set set;
+
+  adapter_data = data;
+  set = adapter_data->set;
+  return (adapter_data->foreach_fn) (arange_set_node_low (node),
+				     arange_set_node_high (set, node),
+				     arange_set_node_value (set, node),
+				     adapter_data->data);
+}
+
+/* Traverse aranges in a set.  For each arange in ascending order of
+   low addresses, call foreach_fn with arange boundaries and data.
+   If any invocation of foreach_fn returns a non-zero value, stop traversal
+   and return that value. Otherwise, return 0.  */
+
+int
+arange_set_foreach (arange_set set,
+		    arange_set_foreach_fn foreach_fn,
+		    void *data)
+{
+  struct arange_set_foreach_adapter_data adapter_data;
+
+  adapter_data.data = data;
+  adapter_data.foreach_fn = foreach_fn;
+  adapter_data.set = set;
+  return splay_tree_foreach (set->ranges, arange_set_foreach_adapter,
+			     (void *) &adapter_data);
+}