+/* Test if an address is the target address of a jump. */
+
+static bfd_boolean
+jump_info_is_end_address (const struct jump_info *ji, bfd_vma address)
+{
+ return (address == ji->end);
+}
+
+/* Get the difference between the smallest and largest address of a jump. */
+
+static bfd_vma
+jump_info_size (const struct jump_info *ji)
+{
+ return jump_info_max_address (ji) - jump_info_min_address (ji);
+}
+
+/* Unlink a jump object from a list. */
+
+static void
+jump_info_unlink (struct jump_info *node,
+ struct jump_info **base)
+{
+ if (node->next)
+ node->next->prev = node->prev;
+ if (node->prev)
+ node->prev->next = node->next;
+ else
+ *base = node->next;
+ node->next = NULL;
+ node->prev = NULL;
+}
+
+/* Insert unlinked jump info node into a list. */
+
+static void
+jump_info_insert (struct jump_info *node,
+ struct jump_info *target,
+ struct jump_info **base)
+{
+ node->next = target;
+ node->prev = target->prev;
+ target->prev = node;
+ if (node->prev)
+ node->prev->next = node;
+ else
+ *base = node;
+}
+
+/* Add unlinked node to the front of a list. */
+
+static void
+jump_info_add_front (struct jump_info *node,
+ struct jump_info **base)
+{
+ node->next = *base;
+ if (node->next)
+ node->next->prev = node;
+ node->prev = NULL;
+ *base = node;
+}
+
+/* Move linked node to target position. */
+
+static void
+jump_info_move_linked (struct jump_info *node,
+ struct jump_info *target,
+ struct jump_info **base)
+{
+ /* Unlink node. */
+ jump_info_unlink (node, base);
+ /* Insert node at target position. */
+ jump_info_insert (node, target, base);
+}
+
+/* Test if two jumps intersect. */
+
+static bfd_boolean
+jump_info_intersect (const struct jump_info *a,
+ const struct jump_info *b)
+{
+ return ((jump_info_max_address (a) >= jump_info_min_address (b))
+ && (jump_info_min_address (a) <= jump_info_max_address (b)));
+}
+
+/* Merge two compatible jump info objects. */
+
+static void
+jump_info_merge (struct jump_info **base)
+{
+ struct jump_info *a;
+
+ for (a = *base; a; a = a->next)
+ {
+ struct jump_info *b;
+
+ for (b = a->next; b; b = b->next)
+ {
+ /* Merge both jumps into one. */
+ if (a->end == b->end)
+ {
+ /* Reallocate addresses. */
+ size_t needed_size = a->start.count + b->start.count;
+ size_t i;
+
+ if (needed_size > a->start.max_count)
+ {
+ a->start.max_count += b->start.max_count;
+ a->start.addresses =
+ xrealloc (a->start.addresses,
+ a->start.max_count * sizeof (bfd_vma *));
+ }
+
+ /* Append start addresses. */
+ for (i = 0; i < b->start.count; ++i)
+ a->start.addresses[a->start.count++] =
+ b->start.addresses[i];
+
+ /* Remove and delete jump. */
+ struct jump_info *tmp = b->prev;
+ jump_info_unlink (b, base);
+ jump_info_free (b);
+ b = tmp;
+ }
+ }
+ }
+}
+
+/* Sort jumps by their size and starting point using a stable
+ minsort. This could be improved if sorting performance is
+ an issue, for example by using mergesort. */
+
+static void
+jump_info_sort (struct jump_info **base)
+{
+ struct jump_info *current_element = *base;
+
+ while (current_element)
+ {
+ struct jump_info *best_match = current_element;
+ struct jump_info *runner = current_element->next;
+ bfd_vma best_size = jump_info_size (best_match);
+
+ while (runner)
+ {
+ bfd_vma runner_size = jump_info_size (runner);
+
+ if ((runner_size < best_size)
+ || ((runner_size == best_size)
+ && (jump_info_min_address (runner)
+ < jump_info_min_address (best_match))))
+ {
+ best_match = runner;
+ best_size = runner_size;
+ }
+
+ runner = runner->next;
+ }
+
+ if (best_match == current_element)
+ current_element = current_element->next;
+ else
+ jump_info_move_linked (best_match, current_element, base);
+ }
+}
+
+/* Visualize all jumps at a given address. */
+
+static void
+jump_info_visualize_address (bfd_vma address,
+ int max_level,
+ char *line_buffer,
+ uint8_t *color_buffer)
+{
+ struct jump_info *ji = detected_jumps;
+ size_t len = (max_level + 1) * 3;
+
+ /* Clear line buffer. */
+ memset (line_buffer, ' ', len);
+ memset (color_buffer, 0, len);
+
+ /* Iterate over jumps and add their ASCII art. */
+ while (ji)
+ {
+ /* Discard jumps that are never needed again. */
+ if (jump_info_max_address (ji) < address)
+ {
+ struct jump_info *tmp = ji;
+
+ ji = ji->next;
+ jump_info_unlink (tmp, &detected_jumps);
+ jump_info_free (tmp);
+ continue;
+ }
+
+ /* This jump intersects with the current address. */
+ if (jump_info_min_address (ji) <= address)
+ {
+ /* Hash target address to get an even
+ distribution between all values. */
+ bfd_vma hash_address = jump_info_end_address (ji);
+ uint8_t color = iterative_hash_object (hash_address, 0);
+ /* Fetch line offset. */
+ int offset = (max_level - ji->level) * 3;
+
+ /* Draw start line. */
+ if (jump_info_is_start_address (ji, address))
+ {
+ size_t i = offset + 1;
+
+ for (; i < len - 1; ++i)
+ if (line_buffer[i] == ' ')
+ {
+ line_buffer[i] = '-';
+ color_buffer[i] = color;
+ }
+
+ if (line_buffer[i] == ' ')
+ {
+ line_buffer[i] = '-';
+ color_buffer[i] = color;
+ }
+ else if (line_buffer[i] == '>')
+ {
+ line_buffer[i] = 'X';
+ color_buffer[i] = color;
+ }
+
+ if (line_buffer[offset] == ' ')
+ {
+ if (address <= ji->end)
+ line_buffer[offset] =
+ (jump_info_min_address (ji) == address) ? '/': '+';
+ else
+ line_buffer[offset] =
+ (jump_info_max_address (ji) == address) ? '\\': '+';
+ color_buffer[offset] = color;
+ }
+ }
+ /* Draw jump target. */
+ else if (jump_info_is_end_address (ji, address))
+ {
+ size_t i = offset + 1;
+
+ for (; i < len - 1; ++i)
+ if (line_buffer[i] == ' ')
+ {
+ line_buffer[i] = '-';
+ color_buffer[i] = color;
+ }
+
+ if (line_buffer[i] == ' ')
+ {
+ line_buffer[i] = '>';
+ color_buffer[i] = color;
+ }
+ else if (line_buffer[i] == '-')
+ {
+ line_buffer[i] = 'X';
+ color_buffer[i] = color;
+ }
+
+ if (line_buffer[offset] == ' ')
+ {
+ if (jump_info_min_address (ji) < address)
+ line_buffer[offset] =
+ (jump_info_max_address (ji) > address) ? '>' : '\\';
+ else
+ line_buffer[offset] = '/';
+ color_buffer[offset] = color;
+ }
+ }
+ /* Draw intermediate line segment. */
+ else if (line_buffer[offset] == ' ')
+ {
+ line_buffer[offset] = '|';
+ color_buffer[offset] = color;
+ }
+ }
+
+ ji = ji->next;
+ }