+/* Number of bits in a bfd_vma. */
+#define VMA_BITS (8 * sizeof (bfd_vma))
+
+/* Check whether [low1, high1) can be combined with [low2, high2),
+ i.e., they touch or overlap. */
+
+static bool
+ranges_overlap (bfd_vma low1,
+ bfd_vma high1,
+ bfd_vma low2,
+ bfd_vma high2)
+{
+ if (low1 == low2 || high1 == high2)
+ return true;
+
+ /* Sort so that low1 is below low2. */
+ if (low1 > low2)
+ {
+ bfd_vma tmp;
+
+ tmp = low1;
+ low1 = low2;
+ low2 = tmp;
+
+ tmp = high1;
+ high1 = high2;
+ high2 = tmp;
+ }
+
+ /* We touch iff low2 == high1.
+ We overlap iff low2 is within [low1, high1). */
+ return low2 <= high1;
+}
+
+/* Insert an address range in the trie mapping addresses to compilation units.
+ Will return the new trie node (usually the same as is being sent in, but
+ in case of a leaf-to-interior conversion, or expansion of a leaf, it may be
+ different), or NULL on failure. */
+
+static struct trie_node *
+insert_arange_in_trie (bfd *abfd,
+ struct trie_node *trie,
+ bfd_vma trie_pc,
+ unsigned int trie_pc_bits,
+ struct comp_unit *unit,
+ bfd_vma low_pc,
+ bfd_vma high_pc)
+{
+ bfd_vma clamped_low_pc, clamped_high_pc;
+ int ch, from_ch, to_ch;
+ bool is_full_leaf = false;
+
+ /* See if we can extend any of the existing ranges. This merging
+ isn't perfect (if merging opens up the possibility of merging two existing
+ ranges, we won't find them), but it takes the majority of the cases. */
+ if (trie->num_room_in_leaf > 0)
+ {
+ struct trie_leaf *leaf = (struct trie_leaf *) trie;
+ unsigned int i;
+
+ for (i = 0; i < leaf->num_stored_in_leaf; ++i)
+ {
+ if (leaf->ranges[i].unit == unit
+ && ranges_overlap (low_pc, high_pc,
+ leaf->ranges[i].low_pc,
+ leaf->ranges[i].high_pc))
+ {
+ if (low_pc < leaf->ranges[i].low_pc)
+ leaf->ranges[i].low_pc = low_pc;
+ if (high_pc > leaf->ranges[i].high_pc)
+ leaf->ranges[i].high_pc = high_pc;
+ return trie;
+ }
+ }
+
+ is_full_leaf = leaf->num_stored_in_leaf == trie->num_room_in_leaf;
+ }
+
+ /* If we're a leaf with no more room and we're _not_ at the bottom,
+ convert to an interior node. */
+ if (is_full_leaf && trie_pc_bits < VMA_BITS)
+ {
+ const struct trie_leaf *leaf = (struct trie_leaf *) trie;
+ unsigned int i;
+
+ trie = bfd_zalloc (abfd, sizeof (struct trie_interior));
+ if (!trie)
+ return NULL;
+ is_full_leaf = false;
+
+ /* TODO: If we wanted to save a little more memory at the cost of
+ complexity, we could have reused the old leaf node as one of the
+ children of the new interior node, instead of throwing it away. */
+ for (i = 0; i < leaf->num_stored_in_leaf; ++i)
+ {
+ if (!insert_arange_in_trie (abfd, trie, trie_pc, trie_pc_bits,
+ leaf->ranges[i].unit, leaf->ranges[i].low_pc,
+ leaf->ranges[i].high_pc))
+ return NULL;
+ }
+ }
+
+ /* If we're a leaf with no more room and we _are_ at the bottom,
+ we have no choice but to just make it larger. */
+ if (is_full_leaf)
+ {
+ const struct trie_leaf *leaf = (struct trie_leaf *) trie;
+ unsigned int new_room_in_leaf = trie->num_room_in_leaf * 2;
+ struct trie_leaf *new_leaf;
+ size_t amt = (sizeof (struct trie_leaf)
+ + ((new_room_in_leaf - TRIE_LEAF_SIZE)
+ * sizeof (leaf->ranges[0])));
+ new_leaf = bfd_zalloc (abfd, amt);
+ new_leaf->head.num_room_in_leaf = new_room_in_leaf;
+ new_leaf->num_stored_in_leaf = leaf->num_stored_in_leaf;
+
+ memcpy (new_leaf->ranges,
+ leaf->ranges,
+ leaf->num_stored_in_leaf * sizeof (leaf->ranges[0]));
+ trie = &new_leaf->head;
+ is_full_leaf = false;
+
+ /* Now the insert below will go through. */
+ }
+
+ /* If we're a leaf (now with room), we can just insert at the end. */
+ if (trie->num_room_in_leaf > 0)
+ {
+ struct trie_leaf *leaf = (struct trie_leaf *) trie;
+
+ unsigned int i = leaf->num_stored_in_leaf++;
+ leaf->ranges[i].unit = unit;
+ leaf->ranges[i].low_pc = low_pc;
+ leaf->ranges[i].high_pc = high_pc;
+ return trie;
+ }
+
+ /* Now we are definitely an interior node, so recurse into all
+ the relevant buckets. */
+
+ /* Clamp the range to the current trie bucket. */
+ clamped_low_pc = low_pc;
+ clamped_high_pc = high_pc;
+ if (trie_pc_bits > 0)
+ {
+ bfd_vma bucket_high_pc =
+ trie_pc + ((bfd_vma) -1 >> trie_pc_bits); /* Inclusive. */
+ if (clamped_low_pc < trie_pc)
+ clamped_low_pc = trie_pc;
+ if (clamped_high_pc > bucket_high_pc)
+ clamped_high_pc = bucket_high_pc;
+ }
+
+ /* Insert the ranges in all buckets that it spans. */
+ from_ch = (clamped_low_pc >> (VMA_BITS - trie_pc_bits - 8)) & 0xff;
+ to_ch = ((clamped_high_pc - 1) >> (VMA_BITS - trie_pc_bits - 8)) & 0xff;
+ for (ch = from_ch; ch <= to_ch; ++ch)
+ {
+ struct trie_interior *interior = (struct trie_interior *) trie;
+ struct trie_node *child = interior->children[ch];
+
+ if (child == NULL)
+ {
+ child = alloc_trie_leaf (abfd);
+ if (!child)
+ return NULL;
+ }
+ bfd_vma bucket = (bfd_vma) ch << (VMA_BITS - trie_pc_bits - 8);
+ child = insert_arange_in_trie (abfd,
+ child,
+ trie_pc + bucket,
+ trie_pc_bits + 8,
+ unit,
+ low_pc,
+ high_pc);
+ if (!child)
+ return NULL;
+
+ interior->children[ch] = child;
+ }
+
+ return trie;
+}
+
+static bool
+arange_add (struct comp_unit *unit, struct arange *first_arange,
+ struct trie_node **trie_root, bfd_vma low_pc, bfd_vma high_pc)