binutils-pr-5755.patch

   1 diff -urN binutils-2.18.50.0.4.org/bfd/arange-set.c binutils-2.18.50.0.4/bfd/arange-set.c
   2 --- binutils-2.18.50.0.4.org/bfd/arange-set.c   2008-02-08 17:44:56.000000000 +0100
   3 +++ binutils-2.18.50.0.4/bfd/arange-set.c       1970-01-01 01:00:00.000000000 +0100
   4 @@ -1,737 +0,0 @@
   5 -/* DWARF 2 Arange-Set.
   6 -   Copyright 2007 Free Software Foundation, Inc.
   7 -   Contributed by Doug Kwan, Google Inc.
   8 -
   9 -   This file is part of BFD.
  10 -
  11 -   This program is free software; you can redistribute it and/or modify
  12 -   it under the terms of the GNU General Public License as published by
  13 -   the Free Software Foundation; either version 3 of the License, or (at
  14 -   your option) any later version.
  15 -
  16 -   This program is distributed in the hope that it will be useful, but
  17 -   WITHOUT ANY WARRANTY; without even the implied warranty of
  18 -   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19 -   General Public License for more details.
  20 -
  21 -   You should have received a copy of the GNU General Public License
  22 -   along with this program; if not, write to the Free Software
  23 -   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  24 -   MA 02110-1301, USA.  */
  25 -
  26 -#include "sysdep.h"
  27 -#include "bfd.h"
  28 -#include "libiberty.h"
  29 -#include "libbfd.h"
  30 -#include "arange-set.h"
  31 -#include "splay-tree.h"
  32 -
  33 -/* Implementation of an arange-set.  The set is implemented using the
  34 -   splay tree support in libiberty.  The advantage of using this is
  35 -   that it has been well tested and is relatively simple to use.  The
  36 -   disadvantage is that it is too general and it does not fit our design
  37 -   exactly.  So we waste a bit of memory for unneeded generality and work
  38 -   around for mis-match between the splay tree API and the arange-set
  39 -   internals.  A specialized implentation of a balanced tree type for
  40 -   arange-set exclusively may speed up things a little and reduce memory
  41 -   consumption.  Until there is a pressing need, we stick to the splay
  42 -   tree in libiberty.  */
  43 -
  44 -struct arange_set_s
  45 -{
  46 -  /* Splay tree containing aranges.  */
  47 -  splay_tree ranges;
  48 -
  49 -  /* Lowest address in set.  If set is empty, it is ~0.  */
  50 -  bfd_vma lower_bound;
  51 -
  52 -  /* Highest address in set.  If set is empty, it is 0.  */
  53 -  bfd_vma upper_bound;
  54 -
  55 -  /* TRUE if aranges in this set have values.  */
  56 -  bfd_boolean value_p;
  57 -
  58 -  /* Function to compare arange values.  */
  59 -  arange_value_equal_fn value_equal_fn;
  60 -
  61 -  /* Function to copy an arange value.  */
  62 -  arange_value_copy_fn value_copy_fn;
  63 -
  64 -  /* Function to combine arange values.  */
  65 -  arange_value_combine_fn value_combine_fn;
  66 -
  67 -  /* Function to delete an arange value.  */
  68 -  arange_value_delete_fn value_delete_fn;
  69 -
  70 -  /* Function to allocate a piece of memory.  */
  71 -  arange_set_allocate_fn allocate_fn;
  72 -
  73 -  /* Function to deallocate a piece of memory.  */
  74 -  arange_set_deallocate_fn deallocate_fn;
  75 -
  76 -  /* Call back data shared by all callbacks.  */
  77 -  void *data;
  78 -};
  79 -
  80 -/* Structure for aranges with a value attached.  Since a splay tree
  81 -   node can only hold one value,  we need to use the container struct
  82 -   to store data associated with an arange and have the splay tree value
  83 -   to be a pointer to this struct. */
  84 -
  85 -typedef struct
  86 -{
  87 -  /* High-pc of an arange.  This is different from the DWARF2 semantics that
  88 -     the high-pc is really the last location in an arange.  */
  89 -  bfd_vma high;
  90 -
  91 -  /* We need to store a pointer to the set because splay_tree_value_delete
  92 -     only takes a pointer to the value deleted.  If we use a deallocator
  93 -     that need extra information like a pointer to the memory pool, we need to
  94 -     look up via the set pointer.  This adds one extra pointer per arange. */
  95 -  arange_set set;
  96 -
  97 -  /* Value associated with this arange.  */
  98 -  arange_value_type value;
  99 -
 100 -} arange_value_container_t;
 101 -
 102 -
 103 -
 104 -static void
 105 -arange_set_delete_value (arange_set set, arange_value_type value)
 106 -{
 107 -  if (set->value_delete_fn)
 108 -    (set->value_delete_fn) (value, set->data);
 109 -}
 110 -
 111 -/* Compare two VMAs as keys of splay tree nodes.  */
 112 -
 113 -static int
 114 -splay_tree_compare_bfd_vmas (splay_tree_key k1, splay_tree_key k2)
 115 -{
 116 -  if ((bfd_vma) k1 < (bfd_vma) k2)
 117 -    return -1;
 118 -  else if ((bfd_vma) k1 > (bfd_vma) k2)
 119 -    return 1;
 120 -
 121 -  return 0;
 122 -}
 123 -
 124 -/* Default memory allocator and deallocator.  */
 125 -
 126 -void *
 127 -arange_set_allocate (arange_set set, int size)
 128 -{
 129 -  if (set->allocate_fn)
 130 -    return (set->allocate_fn) (size, set->data);
 131 -
 132 -  return xmalloc (size);
 133 -}
 134 -
 135 -void
 136 -arange_set_deallocate (arange_set set, void *object)
 137 -{
 138 -  if (set->deallocate_fn)
 139 -    (set->deallocate_fn) (object, set->data);
 140 -  else
 141 -    free (object);
 142 -}
 143 -
 144 -static void
 145 -arange_set_delete_value_container (splay_tree_value value)
 146 -{
 147 -  arange_value_container_t *container;
 148 -
 149 -  container = (arange_value_container_t*) value;
 150 -  arange_set_delete_value (container->set, container->value);
 151 -  arange_set_deallocate (container->set, container);
 152 -}
 153 -
 154 -/* Create an arange set.  Return the new set of NULL if there is any
 155 -   error.
 156 -
 157 -   allocate_fn is the memory allocator function of this arange set. If
 158 -   it is NULL, the default allocator will be used.
 159 -
 160 -   deallocate_fn is the memory deallocator function of this arange set. If
 161 -   it is NULL, the default allocator will be used.
 162 -
 163 -   value_p specifies whether an arange set supports values.  If it is
 164 -   TURE.  Each arange can be associated with a value of type arange_value_type.
 165 -   If it is FALSE, the following parameters value_equal_fn, value_copy_fn,
 166 -   value_combine_fn and value_delete_fn will be ignored.
 167 -
 168 -   value_equal_fn is the value equality function.  An arange uses it to
 169 -   check if two values are the same.  If it is NULL, the default bit-wise
 170 -   equality function will be used.
 171 -
 172 -   value_copy_fn is the value copy function.  An arange uses it to copy
 173 -   values of type arange_value_type.  If it is NULL, the default bit-wise
 174 -   copy function will be used.
 175 -
 176 -   value_combine_fn is the value combine function. An arange uses it to
 177 -   combine values of two identical arange.  If it is NULL, the default
 178 -   constant zero function will be used.
 179 -
 180 -   value_delete_fn is the value deletion function. If it is not NULL,
 181 -   it will be called when an arange deletes a value.
 182 -
 183 -   data is pointer to an object, which will be passed to all allocate_fn,
 184 -   deallocate_fn, value_equal_fn, value_copy_fn, value_combine_fn and
 185 -   value_delete_fn.  */
 186 -
 187 -arange_set
 188 -arange_set_new (arange_set_allocate_fn allocate_fn,
 189 -               arange_set_deallocate_fn deallocate_fn,
 190 -               bfd_boolean value_p,
 191 -               arange_value_equal_fn value_equal_fn,
 192 -               arange_value_copy_fn value_copy_fn,
 193 -               arange_value_combine_fn value_combine_fn,
 194 -               arange_value_delete_fn value_delete_fn,
 195 -               void *data)
 196 -{
 197 -  arange_set set;
 198 -  splay_tree sp;
 199 -  splay_tree_delete_value_fn fn;
 200 -
 201 -  if (sizeof (bfd_vma) > sizeof (splay_tree_key)
 202 -      || sizeof (bfd_vma) > sizeof (splay_tree_value))
 203 -    {
 204 -      (*_bfd_error_handler)
 205 -       (_("size of bfd_vma > size of splay_tree types"));
 206 -      abort ();
 207 -    }
 208 -
 209 -  /* Allocate space for arange structure.  */
 210 -  set = (arange_set)
 211 -    (*allocate_fn) (sizeof (struct arange_set_s), data);
 212 -  if (!set)
 213 -    return set;
 214 -
 215 -  fn = value_p ? arange_set_delete_value_container : NULL;
 216 -  sp = splay_tree_new_with_allocator (splay_tree_compare_bfd_vmas, NULL,
 217 -                                     fn, allocate_fn, deallocate_fn,
 218 -                                     data);
 219 -  if (!sp)
 220 -    {
 221 -      (deallocate_fn) (set, data);
 222 -      return NULL;
 223 -    }
 224 -
 225 -  set->ranges = sp;
 226 -  set->lower_bound = ~0;
 227 -  set->upper_bound = 0;
 228 -  set->value_p = value_p;
 229 -  set->allocate_fn = allocate_fn;
 230 -  set->deallocate_fn = deallocate_fn;
 231 -  set->value_equal_fn = value_equal_fn;
 232 -  set->value_copy_fn = value_copy_fn;
 233 -  set->value_combine_fn = value_combine_fn;
 234 -  set->value_delete_fn = value_delete_fn;
 235 -  set->data = data;
 236 -  return set;
 237 -}
 238 -
 239 -/*  Delete an arange set.  */
 240 -
 241 -void
 242 -arange_set_delete (arange_set set)
 243 -{
 244 -  splay_tree_delete (set->ranges);
 245 -  (*set->deallocate_fn) (set, set->data);
 246 -}
 247 -
 248 -/* Return TRUE if and only if arange set is empty.  */
 249 -
 250 -bfd_boolean
 251 -arange_set_empty_p (arange_set set)
 252 -{
 253 -  return set->lower_bound > set->upper_bound;
 254 -}
 255 -
 256 -/* Accessors for low and high of an arange.
 257 -
 258 -   There is no arange_set_node_set_low since the low address is the
 259 -   key of the splay tree node.  */
 260 -
 261 -/* Get the high VMA address of a node.  */
 262 -
 263 -static bfd_vma
 264 -arange_set_node_high (arange_set set, splay_tree_node node)
 265 -{
 266 -  arange_value_container_t *container;
 267 -
 268 -  if (set->value_p)
 269 -    {
 270 -      container = (arange_value_container_t*) node->value;
 271 -      return container->high;
 272 -    }
 273 -
 274 -  return (bfd_vma) node->value;
 275 -}
 276 -
 277 -/* Set the high VMA address of a node.  */
 278 -
 279 -static void
 280 -arange_set_node_set_high (arange_set set, splay_tree_node node, bfd_vma address)
 281 -{
 282 -  arange_value_container_t *container;
 283 -
 284 -  if (set->value_p)
 285 -    {
 286 -      container = (arange_value_container_t*) node->value;
 287 -      container->high = address;
 288 -    }
 289 -  else
 290 -    node->value = (splay_tree_value) address;
 291 -}
 292 -
 293 -/* Get the low VMA address of a node.  */
 294 -
 295 -static bfd_vma
 296 -arange_set_node_low (splay_tree_node node)
 297 -{
 298 -  return (bfd_vma) node->key;
 299 -}
 300 -
 301 -/* If arange set supports values, return value of an arange; otheriwse
 302 -   always return 0 so that it appears that all aranges have the same value.  */
 303 -
 304 -static arange_value_type
 305 -arange_set_node_value (arange_set set, splay_tree_node node)
 306 -{
 307 -  arange_value_container_t *container;
 308 -
 309 -  if (set->value_p)
 310 -    {
 311 -      container = (arange_value_container_t*) node->value;
 312 -      return container->value;
 313 -    }
 314 -
 315 -  return 0;
 316 -}
 317 -
 318 -/* If arange set supports values, return value of an arange; otheriwse
 319 -   always return 0 so that it appears that all aranges have the same value.  */
 320 -
 321 -static void
 322 -arange_set_node_set_value (arange_set set,
 323 -                          splay_tree_node node,
 324 -                          arange_value_type value)
 325 -{
 326 -  arange_value_container_t *container;
 327 -
 328 -  if (set->value_p)
 329 -    {
 330 -      container = (arange_value_container_t*) node->value;
 331 -      container->value = value;
 332 -    }
 333 -}
 334 -
 335 -/* Return TRUE if and only if arange set supports values.  */
 336 -
 337 -bfd_boolean
 338 -arange_set_has_values_p (arange_set set)
 339 -{
 340 -  return set->value_p;
 341 -}
 342 -
 343 -/* Copy a value using the value copying function of an arange set.  If
 344 -   the set does not support values or if there is not value copying
 345 -   function specified, it simply returns the input value.  */
 346 -
 347 -arange_value_type
 348 -arange_set_copy_value (arange_set set, arange_value_type value)
 349 -{
 350 -  /* If no copy function is specified or set does not support values,
 351 -     default is bit-wise copy.  */
 352 -  if (set->value_p && set->value_copy_fn)
 353 -    return (set->value_copy_fn) (value, set->data);
 354 -
 355 -  return value;
 356 -}
 357 -
 358 -static arange_value_type
 359 -arange_set_combine_value (arange_set set,
 360 -                         arange_value_type value1,
 361 -                         arange_value_type value2)
 362 -{
 363 -  /* If no combine function is specified or set does not support values,
 364 -     default is returning 0.  */
 365 -  if (set->value_p && set->value_combine_fn)
 366 -    return (set->value_combine_fn) (value1, value2, set->data);
 367 -
 368 -  return (arange_value_type) 0;
 369 -}
 370 -
 371 -/* Compares two values for equality.  If the arange set does not support values
 372 -   or if no value equality function is specified, this function simply does
 373 -   a bit-wise comparison.  */
 374 -
 375 -bfd_boolean
 376 -arange_set_value_equal_p (arange_set set,
 377 -                         arange_value_type value1,
 378 -                         arange_value_type value2)
 379 -{
 380 -  /* If no equality function is specified or set does not support values,
 381 -     default is bit-wise comparison.  */
 382 -  if (set->value_p && set->value_equal_fn)
 383 -    return (set->value_equal_fn) (value1, value2, set->data);
 384 -
 385 -  return value1 == value2;
 386 -}
 387 -
 388 -/* Check to see if a given address is in an arange set.  Return TRUE if the
 389 -   address is inside one of the aranges. If low_ptr, high_ptr and value_ptr are
 390 -   used to return lower address, upper address and value associated with a
 391 -   found arounge.  If anyone of them is NULL, the corresponding information
 392 -   is not returned.  For arange set without values, no information is returned
 393 -   through the pointer value_ptr.  */
 394 -
 395 -bfd_boolean
 396 -arange_set_lookup_address (arange_set set, bfd_vma address,
 397 -                          bfd_vma *low_ptr, bfd_vma *high_ptr,
 398 -                          arange_value_type *value_ptr)
 399 -{
 400 -  splay_tree_node pred, node;
 401 -
 402 -  if (address < set->lower_bound || address > set->upper_bound)
 403 -    return FALSE;
 404 -
 405 -  /* Find immediate predecessor.  */
 406 -  pred = splay_tree_predecessor (set->ranges, (splay_tree_key) address);
 407 -  if (pred
 408 -      && arange_set_node_high (set, pred) >= address)
 409 -    node = pred;
 410 -  else
 411 -    /* If the predecessor range does not cover this address, the address
 412 -       is in the arange set only if itself starts an arange.  */
 413 -    node = splay_tree_lookup (set->ranges, (splay_tree_key) address);
 414 -
 415 -  if (node)
 416 -    {
 417 -      /* Also return arange boundaries if caller supplies pointers.  */
 418 -      if (low_ptr)
 419 -       *low_ptr = arange_set_node_low (node);
 420 -      if (high_ptr)
 421 -       *high_ptr = arange_set_node_high (set, node);
 422 -      if (set->value_p && value_ptr)
 423 -       *value_ptr = arange_set_node_value (set, node);
 424 -      return TRUE;
 425 -    }
 426 -
 427 -  return FALSE;
 428 -}
 429 -
 430 -/* Insert an arange [low, high] into a set's splay tree.  If the set supports
 431 -   value, also insert with the given value.  Return the inserted node if there
 432 -   is no error or NULL otherwise.  */
 433 -
 434 -static splay_tree_node
 435 -arange_set_splay_tree_insert (arange_set set,
 436 -                             bfd_vma low,
 437 -                             bfd_vma high,
 438 -                             arange_value_type value)
 439 -{
 440 -  splay_tree_value sp_value;
 441 -  arange_value_container_t *container;
 442 -
 443 -  if (set->value_p)
 444 -    {
 445 -      int size = sizeof (arange_value_container_t);
 446 -      void *data = set->ranges->allocate_data;
 447 -
 448 -      container =
 449 -       (arange_value_container_t*) (*set->ranges->allocate) (size, data);
 450 -      if (!container)
 451 -       return NULL;
 452 -      container->high = high;
 453 -
 454 -      /* Due to the design of splay tree API, there is no way of passing
 455 -        callback data to the splay tree value delete function.  Hence we need
 456 -        to store a pointer to set in every containier!  */
 457 -      container->set = set;
 458 -
 459 -      container->value = value;
 460 -      sp_value = (splay_tree_value) container;
 461 -    }
 462 -  else
 463 -    sp_value = (splay_tree_value) high;
 464 -
 465 -  /* Currently splay_tree_insert does not return any status to tell if there
 466 -     is an error.  */
 467 -  return splay_tree_insert (set->ranges, (splay_tree_key) low, sp_value);
 468 -}
 469 -
 470 -/* Split [low, high] to [low, address) & [address, high].  */
 471 -
 472 -static bfd_boolean
 473 -arange_set_split_node (arange_set set, splay_tree_node node, bfd_vma address)
 474 -{
 475 -  splay_tree_node node2;
 476 -  arange_value_type value;
 477 -  bfd_vma low, high;
 478 -
 479 -  low = arange_set_node_low (node);
 480 -  high = arange_set_node_high (set, node);
 481 -
 482 -  BFD_ASSERT (low < address && address <= high);
 483 -
 484 -  value = arange_set_copy_value (set, arange_set_node_value (set, node));
 485 -  node2 = arange_set_splay_tree_insert (set, address, high, value);
 486 -  if (!node2)
 487 -    return FALSE;
 488 -
 489 -  arange_set_node_set_high (set, node, address - 1);
 490 -  return TRUE;
 491 -}
 492 -
 493 -static splay_tree_node
 494 -arange_set_maybe_merge_with_predecessor (arange_set set, splay_tree_node node)
 495 -{
 496 -  splay_tree_node pred;
 497 -  bfd_vma low, high;
 498 -
 499 -  low = arange_set_node_low (node);
 500 -  high = arange_set_node_high (set, node);
 501 -
 502 -  pred = splay_tree_predecessor (set->ranges, low);
 503 -  if (! pred)
 504 -    return node;
 505 -
 506 -  if (arange_set_node_high (set, pred) + 1 == low
 507 -      && arange_set_value_equal_p (set,
 508 -                                  arange_set_node_value (set, pred),
 509 -                                  arange_set_node_value (set, node)))
 510 -    {
 511 -      splay_tree_remove (set->ranges, arange_set_node_low (node));
 512 -      arange_set_node_set_high (set, pred, high);
 513 -      return arange_set_maybe_merge_with_predecessor (set, pred);
 514 -    }
 515 -
 516 -  return node;
 517 -}
 518 -
 519 -/* Insert an arange [low,high] into a set. Return TRUE if and only if there
 520 -   is no error.  Note that the address high is also included where as in
 521 -   DWARF2 an address range between low & high means [low,high).
 522 -
 523 -   This only handles sets with values. For the simpler case of sets without
 524 -   value, it is handled in arange_set_insert().  This function is
 525 -   tail-recurive.  It is guaranteed to terminate because it only recurses
 526 -   with a smaller range than it is given.  */
 527 -
 528 -static bfd_boolean
 529 -arange_set_insert_value (arange_set set,
 530 -                        bfd_vma low,
 531 -                        bfd_vma high,
 532 -                        arange_value_type value)
 533 -{
 534 -  splay_tree_node succ, pred, node;
 535 -  bfd_vma succ_high, succ_low;
 536 -  arange_value_type combined, old_value;
 537 -
 538 -  if (low > high)
 539 -    {
 540 -      arange_set_delete_value (set, value);
 541 -      return FALSE;
 542 -    }
 543 -
 544 -  pred = splay_tree_predecessor (set->ranges, low);
 545 -  if (pred && arange_set_node_high (set, pred) >= low)
 546 -    arange_set_split_node (set, pred, low);
 547 -
 548 -  node = splay_tree_lookup (set->ranges, low);
 549 -  if (node)
 550 -    {
 551 -      /* Split node if its arange is larger than inserted arange. */
 552 -      if (arange_set_node_high (set, node) > high)
 553 -       arange_set_split_node (set, node, high + 1);
 554 -
 555 -      old_value = arange_set_node_value (set, node);
 556 -      combined = arange_set_combine_value (set, old_value, value);
 557 -      arange_set_node_set_value (set, node, combined);
 558 -      node = arange_set_maybe_merge_with_predecessor (set, node);
 559 -      arange_set_delete_value (set, old_value);
 560 -
 561 -      /* Insert remaining arange by tail-recursion.  */
 562 -      if (high > arange_set_node_high (set, node))
 563 -       return arange_set_insert_value (set,
 564 -                                       arange_set_node_high (set, node) + 1,
 565 -                                       high, value);
 566 -      else
 567 -       {
 568 -         /* Node must cover exactly the range. */
 569 -         BFD_ASSERT (high == arange_set_node_high (set, node));
 570 -         arange_set_delete_value (set, value);
 571 -         succ = splay_tree_successor (set->ranges, arange_set_node_low (node));
 572 -         if (succ)
 573 -           succ = arange_set_maybe_merge_with_predecessor (set, succ);
 574 -         return TRUE;
 575 -       }
 576 -    }
 577 -
 578 -  succ = splay_tree_successor (set->ranges, low);
 579 -  if (succ)
 580 -    {
 581 -      succ_low = arange_set_node_low (succ);
 582 -      succ_high = arange_set_node_high (set, succ);
 583 -
 584 -      if (succ_low <= high)
 585 -       {
 586 -         node = arange_set_splay_tree_insert (set, low, succ_low - 1, value);
 587 -         if (!node)
 588 -           return FALSE;
 589 -
 590 -         /* Update set lower bound only after insertion is successful.  */
 591 -         if (low < set->lower_bound)
 592 -           set->lower_bound = low;
 593 -
 594 -         node = arange_set_maybe_merge_with_predecessor (set, node);
 595 -
 596 -         /* Recurse to handle rest of insertion.  Note that we have to copy
 597 -            value here since it has already been used in the node above.  */
 598 -         return arange_set_insert_value (set, succ_low, high,
 599 -                                         arange_set_copy_value (set, value));
 600 -       }
 601 -     }
 602 -
 603 -  node = arange_set_splay_tree_insert (set, low, high, value);
 604 -  if (!node)
 605 -    return FALSE;
 606 -
 607 -  /* Update set boundaries only after insertion is successful.  */
 608 -  if (low < set->lower_bound)
 609 -    set->lower_bound = low;
 610 -  if (high > set->upper_bound)
 611 -    set->upper_bound = high;
 612 -
 613 -  node = arange_set_maybe_merge_with_predecessor (set, node);
 614 -
 615 -  succ = splay_tree_successor (set->ranges, arange_set_node_low (node));
 616 -  if (succ)
 617 -    succ = arange_set_maybe_merge_with_predecessor (set, succ);
 618 -
 619 -  return TRUE;
 620 -}
 621 -
 622 -bfd_boolean
 623 -arange_set_insert (arange_set set,
 624 -                  bfd_vma low,
 625 -                  bfd_vma high,
 626 -                  arange_value_type value)
 627 -{
 628 -  splay_tree tree = set->ranges;
 629 -  splay_tree_node pred, succ, node = NULL;
 630 -  bfd_vma pred_high, node_low;
 631 -
 632 -  if (set->value_p)
 633 -    return arange_set_insert_value (set, low, high, value);
 634 -
 635 -  if (low > high)
 636 -    return FALSE;
 637 -
 638 -  pred = splay_tree_predecessor (tree, low);
 639 -  if (pred)
 640 -    {
 641 -      pred_high = arange_set_node_high (set, pred);
 642 -
 643 -      /* Nothing to be done if predecessor contains new aranges.  */
 644 -      if (pred_high >= high)
 645 -       return TRUE;
 646 -
 647 -      /* If we can expand predecessor, do so.  Test for the case in which
 648 -        predecessor does not contain new arange but touches it.  */
 649 -      if (pred_high >= low || pred_high + 1 == low)
 650 -       {
 651 -         node = pred;
 652 -         arange_set_node_set_high (set, node, high);
 653 -       }
 654 -    }
 655 -
 656 -  /* Try to see if [low,something] is already in splay tree.  */
 657 -  if (node == NULL)
 658 -    {
 659 -      node = splay_tree_lookup (tree, low);
 660 -      if (node)
 661 -       {
 662 -         /* Nothing to be done if node contains new aranges.  */
 663 -         if (arange_set_node_high (set, node) >= high)
 664 -           return TRUE;
 665 -
 666 -         arange_set_node_set_high (set, node, high);
 667 -       }
 668 -    }
 669 -
 670 -  if (node == NULL)
 671 -    {
 672 -      node = arange_set_splay_tree_insert (set, low, high, 0);
 673 -      if (!node)
 674 -       return FALSE;
 675 -    }
 676 -
 677 -  BFD_ASSERT (node
 678 -             && arange_set_node_low (node) <= low
 679 -             && arange_set_node_high (set, node) >= high);
 680 -
 681 -  /* Update set upper and lower bounds.  */
 682 -  if (low < set->lower_bound)
 683 -    set->lower_bound = low;
 684 -  if (high > set->upper_bound)
 685 -    set->upper_bound = high;
 686 -
 687 -  /* Merge successor if it overlaps or touches node.  */
 688 -  node_low = arange_set_node_low (node);
 689 -  while ((succ = splay_tree_successor (tree, node_low)) != NULL
 690 -        && ((arange_set_node_high (set, node) >= arange_set_node_low (succ))
 691 -            || (arange_set_node_high (set, node) + 1
 692 -                == arange_set_node_low (succ))))
 693 -    {
 694 -      if (arange_set_node_high (set, succ) > high)
 695 -        arange_set_node_set_high (set, node, arange_set_node_high (set, succ));
 696 -      splay_tree_remove (tree, arange_set_node_low (succ));
 697 -    }
 698 -  return TRUE;
 699 -}
 700 -
 701 -struct arange_set_foreach_adapter_data
 702 -{
 703 -  void *data;
 704 -  arange_set set;
 705 -  arange_set_foreach_fn foreach_fn;
 706 -};
 707 -
 708 -/* Adaptor to make arange_set_foreach works with splay_tree_foreach.  */
 709 -
 710 -static int
 711 -arange_set_foreach_adapter (splay_tree_node node, void *data)
 712 -{
 713 -  struct arange_set_foreach_adapter_data *adapter_data;
 714 -  arange_set set;
 715 -
 716 -  adapter_data = data;
 717 -  set = adapter_data->set;
 718 -  return (adapter_data->foreach_fn) (arange_set_node_low (node),
 719 -                                    arange_set_node_high (set, node),
 720 -                                    arange_set_node_value (set, node),
 721 -                                    adapter_data->data);
 722 -}
 723 -
 724 -/* Traverse aranges in a set.  For each arange in ascending order of
 725 -   low addresses, call foreach_fn with arange boundaries and data.
 726 -   If any invocation of foreach_fn returns a non-zero value, stop traversal
 727 -   and return that value. Otherwise, return 0.  */
 728 -
 729 -int
 730 -arange_set_foreach (arange_set set,
 731 -                   arange_set_foreach_fn foreach_fn,
 732 -                   void *data)
 733 -{
 734 -  struct arange_set_foreach_adapter_data adapter_data;
 735 -
 736 -  adapter_data.data = data;
 737 -  adapter_data.foreach_fn = foreach_fn;
 738 -  adapter_data.set = set;
 739 -  return splay_tree_foreach (set->ranges, arange_set_foreach_adapter,
 740 -                            (void *) &adapter_data);
 741 -}
 742 diff -urN binutils-2.18.50.0.4.org/bfd/arange-set.h binutils-2.18.50.0.4/bfd/arange-set.h
 743 --- binutils-2.18.50.0.4.org/bfd/arange-set.h   2007-10-03 17:52:57.000000000 +0200
 744 +++ binutils-2.18.50.0.4/bfd/arange-set.h       1970-01-01 01:00:00.000000000 +0100
 745 @@ -1,187 +0,0 @@
 746 -/* DWARF 2 Arange-Set.
 747 -   Copyright 2007 Free Software Foundation, Inc.
 748 -   Contributed by Doug Kwan, Google Inc.
 749 -
 750 -   This file is part of BFD.
 751 -
 752 -   This program is free software; you can redistribute it and/or modify
 753 -   it under the terms of the GNU General Public License as published by
 754 -   the Free Software Foundation; either version 3 of the License, or (at
 755 -   your option) any later version.
 756 -
 757 -   This program is distributed in the hope that it will be useful, but
 758 -   WITHOUT ANY WARRANTY; without even the implied warranty of
 759 -   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 760 -   General Public License for more details.
 761 -
 762 -   You should have received a copy of the GNU General Public License
 763 -   along with this program; if not, write to the Free Software
 764 -   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
 765 -   MA 02110-1301, USA.  */
 766 -
 767 -/* Scalable DWARF2 Arange Set.
 768 -
 769 -   The original code in dwarf2.c uses an unsorted singly-linked list to
 770 -   represent aranges in a compilation unit.  Looking up for an address
 771 -   became very in-efficient for extremely large binaries with many
 772 -   compilation units, each of which having long list of aranges.
 773 -
 774 -   The arange-set implemented here supports insertion and address
 775 -   containment queries for an arbitrary large collection of aranges in
 776 -   an efficient manner.  In addition, it also supports aranges with
 777 -   values.
 778 -
 779 -     Arange insertion with value.
 780 -
 781 -   For valued arange-set, we need to specify 4 operations during set
 782 -   creation.  If unspecified, reasonable default behaviours are assumed.
 783 -   The operations define how arange insertion merges two identical aranges
 784 -   with different values. The 4 operations are:
 785 -
 786 -       Equality
 787 -       Copy
 788 -       Combination
 789 -       Deletion
 790 -
 791 -   When arange_set_insert () inserts an arange. It breaks the to-be-inserted
 792 -   arange into smaller aranges using the boundaries of any overlapping
 793 -   aranges as cutting point.  In addition, arange_set_insert () may also
 794 -   splilt any existing arange that overlap the ends of the to-be-inserted
 795 -   arange.  After such splitting of the new and existing aranges, the
 796 -   to-be-inserted arange becomes a collection of smaller aranges, each of
 797 -   which either does not overlapping with any existing arange or overlapping
 798 -   completely with one existing arange.  While splitting aranges, values
 799 -   are copied using the Copy operation specified in the set.
 800 -
 801 -   The for each smaller new arange, arange_set_insert () inserts the new
 802 -   arange according to these rules:
 803 -
 804 -   1. If there is no overlapping existing arange, insert new arange.
 805 -
 806 -   2. If there is an overlapping existing arange and its value equals
 807 -      to the inserted value according to the value equality operation
 808 -      of the set, do nothing.
 809 -
 810 -   3. If there is an overlapping existing arange and its value is not
 811 -      the inserted value according to the value equality operation,
 812 -      combine the inserted value with that of the existing arange using
 813 -      the value combination operation of set.
 814 -
 815 -   If as a result of insertion, there are adjacent aranges with equal values,
 816 -   the adjacent aranges will be merge.  */
 817 -
 818 -#ifndef ARANGE_SET_H
 819 -#define ARANGE_SET_H
 820 -
 821 -#include "sysdep.h"
 822 -#include "bfd.h"
 823 -
 824 -/* An arange_set is a pointer to an arange_set_s struct, whose implementation
 825 -   is opaque to clients using the arange set.  */
 826 -typedef struct arange_set_s *arange_set;
 827 -
 828 -#ifndef _WIN64
 829 -  typedef unsigned long int arange_set_uhostptr_t;
 830 -#else
 831 -  typedef unsigned long long arange_set_uhostptr_t;
 832 -#endif
 833 -
 834 -/* Type of value attached to an arange.  This should be wide enough to be
 835 -   converted from and back to any type without loss.  */
 836 -typedef arange_set_uhostptr_t arange_value_type;
 837 -
 838 -/* Type of function that is used to allocate memory for an arange-set.  */
 839 -typedef void* (*arange_set_allocate_fn)(int, void*);
 840 -
 841 -/* Type of function that is used to deallocate memory of an arange-set.  */
 842 -typedef void (*arange_set_deallocate_fn)(void*, void*);
 843 -
 844 -/* Type of function that is called for each arange during a traversal of
 845 -   the set containing that arange.  */
 846 -typedef int (*arange_set_foreach_fn)(bfd_vma, bfd_vma, arange_value_type,
 847 -                                    void *);
 848 -
 849 -/* Type of function that is called to test equality of range values. */
 850 -typedef bfd_boolean (*arange_value_equal_fn)(arange_value_type,
 851 -                                            arange_value_type, void *);
 852 -
 853 -/* Type of function that is called to copy a range value. */
 854 -typedef arange_value_type (*arange_value_copy_fn)(arange_value_type, void *);
 855 -
 856 -/* Type of function that is called to combine two range values. */
 857 -typedef arange_value_type (*arange_value_combine_fn)(arange_value_type,
 858 -                                                    arange_value_type,
 859 -                                                    void *);
 860 -
 861 -/* Type of function that is called to delete a range value. */
 862 -typedef void (*arange_value_delete_fn)(arange_value_type, void *);
 863 -
 864 -/* Create an arange set.  Return the new set of NULL if there is any
 865 -   error.  */
 866 -extern arange_set arange_set_new (arange_set_allocate_fn,
 867 -                                 arange_set_deallocate_fn,
 868 -                                 bfd_boolean,
 869 -                                 arange_value_equal_fn,
 870 -                                 arange_value_copy_fn,
 871 -                                 arange_value_combine_fn,
 872 -                                 arange_value_delete_fn,
 873 -                                 void *);
 874 -
 875 -/*  Delete an arange set.  */
 876 -extern void arange_set_delete (arange_set);
 877 -
 878 -/* Return TRUE if an only if arange set is empty.  */
 879 -extern bfd_boolean arange_set_empty_p (arange_set);
 880 -
 881 -/* Check to see if a given address is in an arange set.  Return TRUE if the
 882 -   address is inside one of the aranges and if also low_ptr and high_ptr are
 883 -   not NULL, return the boundaries of the arange.
 884 -
 885 -   If the address is not in any arange in set, return FALSE. */
 886 -extern bfd_boolean arange_set_lookup_address (arange_set, bfd_vma, bfd_vma *,
 887 -                                             bfd_vma *, arange_value_type *);
 888 -
 889 -/* Insert an arange [low,high] into a set.  Note that the address high is
 890 -   also included where as in DWARF2 an address range between low & high means
 891 -   [low,high).
 892 -
 893 -   If the set is created with no capability of storing values, the value
 894 -   argument is ignored.  Otherwise, the value is stored in the inserted range.
 895 -   If there are overlapping ranges, values are combined according to
 896 -   value_combine_fn.
 897 -
 898 -   If value is an object, arange_set_insert () takes ownership of that objec.
 899 -   Caller should not deallocate objects that are passed to arange_set_insert().
 900 -
 901 -   Return TRUE if and only if there is no error.  */
 902 -extern bfd_boolean arange_set_insert (arange_set, bfd_vma, bfd_vma,
 903 -                                     arange_value_type);
 904 -
 905 -/* Return TRUE if and only if arange set supports arang evalues.  */
 906 -extern bfd_boolean arange_set_has_values_p (arange_set);
 907 -
 908 -/* Traverse aranges in a set.  For each arange in ascending order of
 909 -   low addresses, call foreach_fn with arange boundaries and data.
 910 -   If any invocation of foreach_fn returns a non-zero value, stop traversal
 911 -   and return that value. Otherwise, return 0.  */
 912 -extern int arange_set_foreach (arange_set, arange_set_foreach_fn, void *);
 913 -
 914 -/* Return TRUE if two values are considered equal by the value comparison
 915 -   function of an arange_set.  If the arange set does not support values or
 916 -   if it has no value equality function specified, this function performs
 917 -   a bit-wise comparison of its input.  */
 918 -extern bfd_boolean arange_set_value_equal_p (arange_set, arange_value_type,
 919 -                                            arange_value_type);
 920 -
 921 -/* Duplicate a value. If the arange set does not support values or if it
 922 -   has no value copying function specified, this function returns the input
 923 -   value.  */
 924 -extern arange_value_type arange_set_copy_value (arange_set, arange_value_type);
 925 -
 926 -/* Allocate memory using the allocator of an arange set.  */
 927 -extern void * arange_set_allocate (arange_set, int);
 928 -
 929 -/* Deallocate memory allocated from arange_set_allocate ().  */
 930 -extern void arange_set_deallocate (arange_set, void *);
 931 -
 932 -#endif /* ARANGE_SET_H */
 933 diff -urN binutils-2.18.50.0.4.org/bfd/dwarf2.c binutils-2.18.50.0.4/bfd/dwarf2.c
 934 --- binutils-2.18.50.0.4.org/bfd/dwarf2.c       2008-02-08 17:44:55.000000000 +0100
 935 +++ binutils-2.18.50.0.4/bfd/dwarf2.c   2008-02-16 21:39:52.643275415 +0100
 936 @@ -1,6 +1,6 @@
 937  /* DWARF 2 support.
 938     Copyright 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003,
 939 -   2004, 2005, 2006, 2007 Free Software Foundation, Inc.
 940 +   2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
 941
 942     Adapted from gdb/dwarf2read.c by Gavin Koch of Cygnus Solutions
 943     (gavin@cygnus.com).
 944 @@ -36,7 +36,6 @@
 945  #include "libbfd.h"
 946  #include "elf-bfd.h"
 947  #include "elf/dwarf2.h"
 948 -#include "arange-set.h"
 949
 950  /* The data in the .debug_line statement prologue looks like this.  */
 951
 952 @@ -90,9 +89,6 @@
 953    /* Last comp unit in list above.  */
 954    struct comp_unit *last_comp_unit;
 955
 956 -  /* Number of comp units. */
 957 -  int comp_unit_count;
 958 -
 959    /* The next unread compilation unit within the .debug_info section.
 960       Zero indicates that the .debug_info section has not been loaded
 961       into a buffer yet.  */
 962 @@ -167,33 +163,11 @@
 963  #define STASH_INFO_HASH_OFF        0
 964  #define STASH_INFO_HASH_ON         1
 965  #define STASH_INFO_HASH_DISABLED   2
 966 -
 967 -  /* Arange-set for fast lookup.  The aranges in this set have pointers
 968 -     to compilation units containing them.  In the unlikely case that there
 969 -     are multiple compilation units associated with an arange, the arange-set
 970 -     is a NULL pointer and we need to fall back to sequential search.  */
 971 -  arange_set comp_unit_arange_set;
 972 -
 973 -  /* Status of global arange set.  */
 974 -  int arange_set_status;
 975 -#define STASH_ARANGE_SET_OFF           0
 976 -#define STASH_ARANGE_SET_ON            1
 977 -#define STASH_ARANGE_SET_DISABLED      2
 978 -
 979 -  /* Build a whole binary arange-set for compilation unit look-up
 980 -     if there are at least this many compilation units.  */
 981 -#define STASH_ARANGE_SET_TRIGGER       500
 982  };
 983
 984 -/* Simple singly linked list for aranges.  We now use a more scalable
 985 -   arange-set for aranges in compilation units.  For functions, we still
 986 -   use this since it is more efficient for simple cases.  */
 987 -
 988  struct arange
 989  {
 990    struct arange *next;
 991 -  /* The lowest and highest addresses contained a compilation
 992 -     unit as specified in the compilation unit's header.  */
 993    bfd_vma low;
 994    bfd_vma high;
 995  };
 996 @@ -213,8 +187,9 @@
 997    /* Keep the bfd convenient (for memory allocation).  */
 998    bfd *abfd;
 999
1000 -  /* The set of aranges in a compilation unit.  */
1001 -  arange_set arange_set;
1002 +  /* The lowest and highest addresses contained in this compilation
1003 +     unit as specified in the compilation unit header.  */
1004 +  struct arange arange;
1005
1006    /* The DW_AT_name attribute (for error messages).  */
1007    char *name;
1008 @@ -895,8 +870,8 @@
1009    char *comp_dir;
1010    char **dirs;
1011    struct fileinfo* files;
1012 -  struct line_info* last_line;  /* Largest VMA.  */
1013 -  struct line_info* lcl_head;   /* Local head; used in 'add_line_info'.  */
1014 +  struct line_info* last_line;  /* largest VMA */
1015 +  struct line_info* lcl_head;   /* local head; used in 'add_line_info' */
1016  };
1017
1018  /* Remember some information about each function.  If the function is
1019 @@ -906,121 +881,35 @@
1020
1021  struct funcinfo
1022  {
1023 -  struct funcinfo *prev_func;          /* Pointer to previous function in list of all functions.  */
1024 -  struct funcinfo *caller_func;                /* Pointer to function one scope higher.  */
1025 -  char *caller_file;                   /* Source location file name where caller_func inlines this func.  */
1026 -  int caller_line;                     /* Source location line number where caller_func inlines this func.  */
1027 -  char *file;                          /* Source location file name.  */
1028 -  int line;                            /* Source location line number.  */
1029 +  struct funcinfo *prev_func;          /* Pointer to previous function in list of all functions */
1030 +  struct funcinfo *caller_func;                /* Pointer to function one scope higher */
1031 +  char *caller_file;                   /* Source location file name where caller_func inlines this func */
1032 +  int caller_line;                     /* Source location line number where caller_func inlines this func */
1033 +  char *file;                          /* Source location file name */
1034 +  int line;                            /* Source location line number */
1035    int tag;
1036    char *name;
1037    struct arange arange;
1038 -  asection *sec;                       /* Where the symbol is defined.  */
1039 +  asection *sec;                       /* Where the symbol is defined */
1040  };
1041
1042  struct varinfo
1043  {
1044 -  /* Pointer to previous variable in list of all variables.  */
1045 +  /* Pointer to previous variable in list of all variables */
1046    struct varinfo *prev_var;
1047 -  /* Source location file name.  */
1048 +  /* Source location file name */
1049    char *file;
1050 -  /* Source location line number.  */
1051 +  /* Source location line number */
1052    int line;
1053    int tag;
1054    char *name;
1055    bfd_vma addr;
1056 -  /* Where the symbol is defined.  */
1057 +  /* Where the symbol is defined */
1058    asection *sec;
1059 -  /* Is this a stack variable?  */
1060 +  /* Is this a stack variable? */
1061    unsigned int stack: 1;
1062  };
1063
1064 -/* Arange-sets:
1065 -
1066 -   To handle extremely large binaries, we want to use a more efficient data
1067 -   structure than a singly-linked list to represent aranges.  So instead we
1068 -   use an arange-set, which supports efficient insertions and queries.  We
1069 -   use a simple arange-set with no values attached to represent the aranges
1070 -   in a compilation unit and we also use a global arange-set to store all
1071 -   the aranges in all the compilation units.  The global arange-set stores
1072 -   values which are pointers to the compilation units.
1073 -
1074 -   Normally aranges in the global set do not overlap, but this can happen.
1075 -   To simplify things and to prevent excessive memory usage, an arange in
1076 -   the global set can only point to at most one compilation unit.  In case
1077 -   of an overlap, the pointer is set to NULL, meaning that there are more
1078 -   than one compilation units containing that arange.  Code that looks up
1079 -   the global set should fall back to searching all compilation units if
1080 -   that happens.  */
1081 -
1082 -/* Allocate memory for an arange set.  */
1083 -
1084 -static void *
1085 -dwarf2_arange_set_allocate (int size, void *data)
1086 -{
1087 -  return bfd_alloc ((bfd *) data, size);
1088 -}
1089 -
1090 -/* Deallocate memory of an arange set.  */
1091 -
1092 -static void
1093 -dwarf2_arange_set_deallocate (void *object ATTRIBUTE_UNUSED,
1094 -                             void *data ATTRIBUTE_UNUSED)
1095 -{
1096 -  /* Do nothing. Let BFD clean up when it's done.  */
1097 -}
1098 -
1099 -/* Combine two comp unit pointers.  If they are the same,
1100 -   return either one, otherwise return NULL.  */
1101 -
1102 -static arange_value_type
1103 -dwarf2_combine_arange_value (arange_value_type value1,
1104 -                            arange_value_type value2,
1105 -                            void *data ATTRIBUTE_UNUSED)
1106 -{
1107 -  return ((value1 == value2) ? value1 : 0);
1108 -}
1109 -
1110 -/* Create a simple arange set that does not store values.  */
1111 -
1112 -static arange_set
1113 -dwarf2_arange_set_new (bfd *abfd)
1114 -{
1115 -  return arange_set_new (dwarf2_arange_set_allocate,
1116 -                        dwarf2_arange_set_deallocate,
1117 -                        FALSE, NULL, NULL, NULL, NULL, (void *) abfd);
1118 -}
1119 -
1120 -/* Create an arange set that stores pointers to compilation units.  */
1121 -
1122 -static arange_set
1123 -dwarf2_arange_set_with_value_new (bfd *abfd)
1124 -{
1125 -  return arange_set_new (dwarf2_arange_set_allocate,
1126 -                        dwarf2_arange_set_deallocate,
1127 -                        TRUE, NULL, NULL, dwarf2_combine_arange_value,
1128 -                        NULL, (void *) abfd);
1129 -}
1130 -
1131 -/* Add an arange to a compilation unit.  Add the arange to both the
1132 -   unit's valueless arange set and the global arange set.  */
1133 -
1134 -static void
1135 -dwarf2_comp_unit_arange_add (struct comp_unit *unit,
1136 -                            bfd_vma low,
1137 -                            bfd_vma high)
1138 -{
1139 -  /* Add arange to unit's local arange set.  */
1140 -  arange_set_insert (unit->arange_set, low, high - 1, 0);
1141 -
1142 -  if (unit->stash->arange_set_status == STASH_ARANGE_SET_ON)
1143 -    {
1144 -      BFD_ASSERT (unit->stash->comp_unit_arange_set);
1145 -      arange_set_insert (unit->stash->comp_unit_arange_set, low, high - 1,
1146 -                        (arange_value_type) unit);
1147 -    }
1148 -}
1149 -
1150  /* Return TRUE if NEW_LINE should sort after LINE.  */
1151
1152  static inline bfd_boolean
1153 @@ -1046,7 +935,7 @@
1154                int end_sequence)
1155  {
1156    bfd_size_type amt = sizeof (struct line_info);
1157 -  struct line_info * info = bfd_alloc (table->abfd, amt);
1158 +  struct line_info* info = bfd_alloc (table->abfd, amt);
1159
1160    /* Set member data of 'info'.  */
1161    info->address = address;
1162 @@ -1090,9 +979,9 @@
1163        table->last_line = info;
1164      }
1165    else if (!table->last_line
1166 -          || new_line_sorts_after (info, table->last_line))
1167 +      || new_line_sorts_after (info, table->last_line))
1168      {
1169 -      /* Normal case: add 'info' to the beginning of the list.  */
1170 +      /* Normal case: add 'info' to the beginning of the list */
1171        info->prev_line = table->last_line;
1172        table->last_line = info;
1173
1174 @@ -1112,7 +1001,7 @@
1175      {
1176        /* Abnormal and hard: Neither 'last_line' nor 'lcl_head' are valid
1177          heads for 'info'.  Reset 'lcl_head'.  */
1178 -      struct line_info* li2 = table->last_line; /* Always non-NULL.  */
1179 +      struct line_info* li2 = table->last_line; /* always non-NULL */
1180        struct line_info* li1 = li2->prev_line;
1181
1182        while (li1)
1183 @@ -1121,7 +1010,7 @@
1184               && new_line_sorts_after (info, li1))
1185             break;
1186
1187 -         li2 = li1; /* Always non-NULL.  */
1188 +         li2 = li1; /* always non-NULL */
1189           li1 = li1->prev_line;
1190         }
1191        table->lcl_head = li2;
1192 @@ -1195,12 +1084,11 @@
1193  }
1194
1195  static void
1196 -arange_add (bfd *abfd, struct arange *first_arange, bfd_vma low_pc,
1197 -           bfd_vma high_pc)
1198 +arange_add (bfd *abfd, struct arange *first_arange, bfd_vma low_pc, bfd_vma high_pc)
1199  {
1200    struct arange *arange;
1201
1202 -  /* If the first arange is empty, use it.  */
1203 +  /* If the first arange is empty, use it. */
1204    if (first_arange->high == 0)
1205      {
1206        first_arange->low = low_pc;
1207 @@ -1227,7 +1115,7 @@
1208    while (arange);
1209
1210    /* Need to allocate a new arange and insert it into the arange list.
1211 -     Order isn't significant, so just insert after the first arange.  */
1212 +     Order isn't significant, so just insert after the first arange. */
1213    arange = bfd_zalloc (abfd, sizeof (*arange));
1214    arange->low = low_pc;
1215    arange->high = high_pc;
1216 @@ -1462,7 +1350,7 @@
1217                     low_pc = address;
1218                   if (address > high_pc)
1219                     high_pc = address;
1220 -                 dwarf2_comp_unit_arange_add (unit, low_pc, high_pc);
1221 +                 arange_add (unit->abfd, &unit->arange, low_pc, high_pc);
1222                   break;
1223                 case DW_LNE_set_address:
1224                   address = read_address (unit, line_ptr);
1225 @@ -1893,44 +1781,11 @@
1226             }
1227         }
1228      }
1229 -  return name;
1230 -}
1231 -
1232 -/* Type of callback function used in read_rangelist below.  */
1233 -
1234 -typedef void (*read_rangelist_callback_t)(struct comp_unit*, bfd_vma,
1235 -                                         bfd_vma, void*);
1236 -
1237 -/* Call back to add an arange to the old-style arange list.  */
1238 -
1239 -static void
1240 -read_rangelist_insert_arange_list (struct comp_unit *unit,
1241 -                                  bfd_vma low,
1242 -                                  bfd_vma high,
1243 -                                  void *data)
1244 -{
1245 -  arange_add (unit->abfd, (struct arange*) data, low, high);
1246 +  return (name);
1247  }
1248
1249 -/* Callback to add an arange in the arange set of a compilation unit.  */
1250 -
1251 -static void
1252 -read_rangelist_comp_unit_arange_add (struct comp_unit *unit,
1253 -                                    bfd_vma low,
1254 -                                    bfd_vma high,
1255 -                                    void *data ATTRIBUTE_UNUSED)
1256 -{
1257 -  dwarf2_comp_unit_arange_add (unit, low, high);
1258 -}
1259 -
1260 -/* Read ARANGE list of a compilation unit.  For each read arange,
1261 -   call the supplied callback function for further processing.  */
1262 -
1263  static void
1264 -read_rangelist (struct comp_unit *unit,
1265 -               bfd_uint64_t offset,
1266 -               read_rangelist_callback_t callback,
1267 -               void *callback_data)
1268 +read_rangelist (struct comp_unit *unit, struct arange *arange, bfd_uint64_t offset)
1269  {
1270    bfd_byte *ranges_ptr;
1271    bfd_vma base_address = unit->base_address;
1272 @@ -1966,9 +1821,7 @@
1273        if (low_pc == -1UL && high_pc != -1UL)
1274         base_address = high_pc;
1275        else
1276 -       /* Call callback to process new arange.  */
1277 -       (callback) (unit, base_address + low_pc, base_address + high_pc,
1278 -                   callback_data);
1279 +       arange_add (unit->abfd, arange, base_address + low_pc, base_address + high_pc);
1280      }
1281  }
1282
1283 @@ -2101,9 +1954,7 @@
1284                   break;
1285
1286                 case DW_AT_ranges:
1287 -                 read_rangelist (unit, attr.u.val,
1288 -                                 read_rangelist_insert_arange_list,
1289 -                                 & func->arange);
1290 +                 read_rangelist (unit, &func->arange, attr.u.val);
1291                   break;
1292
1293                 case DW_AT_decl_file:
1294 @@ -2305,7 +2156,6 @@
1295    unit->end_ptr = end_ptr;
1296    unit->stash = stash;
1297    unit->info_ptr_unit = info_ptr_unit;
1298 -  unit->arange_set = dwarf2_arange_set_new (abfd);
1299
1300    for (i = 0; i < abbrev->num_attrs; ++i)
1301      {
1302 @@ -2337,14 +2187,12 @@
1303           break;
1304
1305         case DW_AT_ranges:
1306 -         read_rangelist (unit, attr.u.val,
1307 -                         read_rangelist_comp_unit_arange_add, NULL);
1308 +         read_rangelist (unit, &unit->arange, attr.u.val);
1309           break;
1310
1311         case DW_AT_comp_dir:
1312           {
1313             char *comp_dir = attr.u.str;
1314 -
1315             if (comp_dir)
1316               {
1317                 /* Irix 6.2 native cc prepends <machine>.: to the compilation
1318 @@ -2362,9 +2210,10 @@
1319           break;
1320         }
1321      }
1322 -
1323    if (high_pc != 0)
1324 -    dwarf2_comp_unit_arange_add (unit, low_pc, high_pc);
1325 +    {
1326 +      arange_add (unit->abfd, &unit->arange, low_pc, high_pc);
1327 +    }
1328
1329    unit->first_child_die_ptr = info_ptr;
1330    return unit;
1331 @@ -2379,7 +2228,21 @@
1332  static bfd_boolean
1333  comp_unit_contains_address (struct comp_unit *unit, bfd_vma addr)
1334  {
1335 -  return arange_set_lookup_address (unit->arange_set, addr, NULL, NULL, NULL);
1336 +  struct arange *arange;
1337 +
1338 +  if (unit->error)
1339 +    return FALSE;
1340 +
1341 +  arange = &unit->arange;
1342 +  do
1343 +    {
1344 +      if (addr >= arange->low && addr < arange->high)
1345 +       return TRUE;
1346 +      arange = arange->next;
1347 +    }
1348 +  while (arange);
1349 +
1350 +  return FALSE;
1351  }
1352
1353  /* If UNIT contains ADDR, set the output parameters to the values for
1354 @@ -2951,107 +2814,6 @@
1355                                    filename_ptr, linenumber_ptr);
1356  }
1357
1358 -typedef struct
1359 -{
1360 -  struct dwarf2_debug * stash;
1361 -  arange_set            set;
1362 -  struct comp_unit *    unit;
1363 -} stash_copy_local_aranges_data_t;
1364 -
1365 -static int
1366 -stash_copy_local_aranges (bfd_vma low,
1367 -                         bfd_vma high,
1368 -                         arange_value_type data ATTRIBUTE_UNUSED,
1369 -                         void *info)
1370 -{
1371 -  bfd_boolean status;
1372 -
1373 -  stash_copy_local_aranges_data_t *copy_data = info;
1374 -  status = arange_set_insert (copy_data->set, low, high,
1375 -                             (arange_value_type) copy_data->unit);
1376 -
1377 -  return status ? 0 : 1;
1378 -}
1379 -
1380 -static bfd_boolean
1381 -stash_maybe_enable_arange_set (bfd *abfd, struct dwarf2_debug *stash)
1382 -{
1383 -  struct comp_unit *unit;
1384 -  stash_copy_local_aranges_data_t copy_data;
1385 -
1386 -  if (stash->arange_set_status != STASH_ARANGE_SET_OFF)
1387 -    return TRUE;
1388 -
1389 -  if (stash->comp_unit_count < STASH_ARANGE_SET_TRIGGER)
1390 -    return TRUE;
1391 -
1392 -  if (stash->comp_unit_arange_set == NULL)
1393 -    {
1394 -      stash->comp_unit_arange_set =
1395 -       dwarf2_arange_set_with_value_new (abfd);
1396 -      if (!stash->comp_unit_arange_set)
1397 -       {
1398 -         stash->arange_set_status = STASH_ARANGE_SET_DISABLED;
1399 -         return FALSE;
1400 -       }
1401 -    }
1402 -
1403 -  copy_data.stash = stash;
1404 -  copy_data.set = stash->comp_unit_arange_set;
1405 -  for (unit = stash->all_comp_units; unit; unit = unit->next_unit)
1406 -    {
1407 -      copy_data.unit = unit;
1408 -      if (arange_set_foreach (unit->arange_set, stash_copy_local_aranges,
1409 -                             & copy_data))
1410 -       {
1411 -         stash->arange_set_status = STASH_ARANGE_SET_DISABLED;
1412 -         return FALSE;
1413 -       }
1414 -    }
1415 -  stash->arange_set_status = STASH_ARANGE_SET_ON;
1416 -  return TRUE;
1417 -}
1418 -
1419 -/* Find the nearest line to a given address and record filename,
1420 -   function name and line number if found.  Return TRUE if a line is
1421 -   found or FALSE otherwise.  */
1422 -
1423 -static bfd_boolean ATTRIBUTE_UNUSED
1424 -stash_find_nearest_line_fast (struct dwarf2_debug *stash,
1425 -                             bfd_vma addr,
1426 -                             const char **filename_ptr,
1427 -                             const char **functionname_ptr,
1428 -                             unsigned int *linenumber_ptr)
1429 -{
1430 -  arange_value_type value;
1431 -  struct comp_unit *unit;
1432 -
1433 -  /* Try looking up global arange set first.  */
1434 -  if (stash->arange_set_status == STASH_ARANGE_SET_ON
1435 -      && arange_set_lookup_address (stash->comp_unit_arange_set, addr, NULL,
1436 -                                   NULL, &value))
1437 -    {
1438 -      if ((unit = (struct comp_unit *) value) != NULL)
1439 -       /* There is only one compilation unit containing this address.  */
1440 -       return comp_unit_find_nearest_line (unit, addr, filename_ptr,
1441 -                                           functionname_ptr, linenumber_ptr,
1442 -                                           stash);
1443 -    }
1444 -
1445 -  /* The arange set is not available or there are multiple compilation
1446 -     units containing this address.  Search all compilation units.  */
1447 -  for (unit = stash->all_comp_units; unit; unit = unit->next_unit)
1448 -    {
1449 -      if (comp_unit_contains_address (unit, addr)
1450 -         && comp_unit_find_nearest_line (unit, addr, filename_ptr,
1451 -                                         functionname_ptr,
1452 -                                         linenumber_ptr, stash))
1453 -         return TRUE;
1454 -    }
1455 -
1456 -  return FALSE;
1457 -}
1458 -
1459  /* Find the source code location of SYMBOL.  If SYMBOL is NULL
1460     then find the nearest source code location corresponding to
1461     the address SECTION + OFFSET.
1462 @@ -3306,13 +3068,17 @@
1463      }
1464    else
1465      {
1466 -      if (stash->arange_set_status == STASH_ARANGE_SET_OFF)
1467 -       stash_maybe_enable_arange_set (abfd, stash);
1468 -
1469 -      found = stash_find_nearest_line_fast (stash, addr, filename_ptr,
1470 -                                           functionname_ptr, linenumber_ptr);
1471 -      if (found)
1472 -       goto done;
1473 +      for (each = stash->all_comp_units; each; each = each->next_unit)
1474 +       {
1475 +         found = (comp_unit_contains_address (each, addr)
1476 +                  && comp_unit_find_nearest_line (each, addr,
1477 +                                                  filename_ptr,
1478 +                                                  functionname_ptr,
1479 +                                                  linenumber_ptr,
1480 +                                                  stash));
1481 +         if (found)
1482 +           goto done;
1483 +       }
1484      }
1485
1486    /* The DWARF2 spec says that the initial length field, and the
1487 @@ -3386,22 +3152,22 @@
1488
1489               each->next_unit = stash->all_comp_units;
1490               stash->all_comp_units = each;
1491 -             stash->comp_unit_count++;
1492
1493               /* DW_AT_low_pc and DW_AT_high_pc are optional for
1494 -                compilation units.  If we don't have them, we need to
1495 -                consult the line info table to see if a compilation unit
1496 -                contains the given address.  */
1497 +                compilation units.  If we don't have them (i.e.,
1498 +                unit->high == 0), we need to consult the line info
1499 +                table to see if a compilation unit contains the given
1500 +                address.  */
1501               if (do_line)
1502                 found = (((symbol->flags & BSF_FUNCTION) == 0
1503 -                         || arange_set_empty_p (each->arange_set)
1504 +                         || each->arange.high == 0
1505                           || comp_unit_contains_address (each, addr))
1506                          && comp_unit_find_line (each, symbol, addr,
1507                                                  filename_ptr,
1508                                                  linenumber_ptr,
1509                                                  stash));
1510               else
1511 -               found = ((arange_set_empty_p (each->arange_set)
1512 +               found = ((each->arange.high == 0
1513                           || comp_unit_contains_address (each, addr))
1514                          && comp_unit_find_nearest_line (each, addr,
1515                                                          filename_ptr,
1516 diff -urN binutils-2.18.50.0.4.org/bfd/Makefile.am binutils-2.18.50.0.4/bfd/Makefile.am
1517 --- binutils-2.18.50.0.4.org/bfd/Makefile.am    2008-02-08 17:44:09.000000000 +0100
1518 +++ binutils-2.18.50.0.4/bfd/Makefile.am        2008-02-16 21:39:52.643275415 +0100
1519 @@ -42,7 +42,7 @@
1520         format.lo init.lo libbfd.lo opncls.lo reloc.lo \
1521         section.lo syms.lo targets.lo hash.lo linker.lo \
1522         srec.lo binary.lo tekhex.lo ihex.lo stabs.lo stab-syms.lo \
1523 -       merge.lo dwarf2.lo simple.lo arange-set.lo
1524 +       merge.lo dwarf2.lo simple.lo
1525
1526  BFD64_LIBS = archive64.lo
1527
1528 @@ -52,7 +52,7 @@
1529         format.c init.c libbfd.c opncls.c reloc.c \
1530         section.c syms.c targets.c hash.c linker.c \
1531         srec.c binary.c tekhex.c ihex.c stabs.c stab-syms.c \
1532 -       merge.c dwarf2.c simple.c arange-set.c
1533 +       merge.c dwarf2.c simple.c
1534
1535  BFD64_LIBS_CFILES = archive64.c
1536
1537 @@ -665,8 +665,8 @@
1538
1539  ## This is a list of all .h files which are in the source tree.
1540  SOURCE_HFILES = \
1541 -       arange-set.h aout-target.h aoutf1.h aoutx.h coffcode.h coffswap.h \
1542 -       ecoffswap.h elf-bfd.h elf-hppa.h elf32-hppa.h \
1543 +       aout-target.h aoutf1.h aoutx.h coffcode.h coffswap.h ecoffswap.h \
1544 +       elf-bfd.h elf-hppa.h elf32-hppa.h \
1545         elf64-hppa.h elfcode.h elfcore.h \
1546         freebsd.h genlink.h go32stub.h \
1547         libaout.h libbfd.h libcoff.h libecoff.h libhppa.h libieee.h \
1548 @@ -1049,11 +1049,9 @@
1549  dwarf2.lo: dwarf2.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
1550    $(INCDIR)/hashtab.h elf-bfd.h $(INCDIR)/elf/common.h \
1551    $(INCDIR)/elf/internal.h $(INCDIR)/elf/external.h $(INCDIR)/bfdlink.h \
1552 -  $(INCDIR)/elf/dwarf2.h arange-set.h
1553 +  $(INCDIR)/elf/dwarf2.h
1554  simple.lo: simple.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \
1555    $(INCDIR)/bfdlink.h
1556 -arange-set.lo: arange-set.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
1557 -  $(INCDIR)/hashtab.h arange-set.h $(INCDIR)/splay-tree.h
1558  archive64.lo: archive64.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \
1559    $(INCDIR)/aout/ar.h
1560  cpu-alpha.lo: cpu-alpha.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h
1561 diff -urN binutils-2.18.50.0.4.org/bfd/po/SRC-POTFILES.in binutils-2.18.50.0.4/bfd/po/SRC-POTFILES.in
1562 --- binutils-2.18.50.0.4.org/bfd/po/SRC-POTFILES.in     2007-11-03 21:40:36.000000000 +0100
1563 +++ binutils-2.18.50.0.4/bfd/po/SRC-POTFILES.in 2008-02-16 21:39:52.643275415 +0100
1564 @@ -12,8 +12,6 @@
1565  aout-target.h
1566  aout-tic30.c
1567  aoutx.h
1568 -arange-set.c
1569 -arange-set.h
1570  archive64.c
1571  archive.c
1572  archures.c