bfd/arange-set.h

   1 /* DWARF 2 Arange-Set.
   2    Copyright 2007 Free Software Foundation, Inc.
   3    Contributed by Doug Kwan, Google Inc.
   4
   5    This file is part of BFD.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or (at
  10    your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  20    MA 02110-1301, USA.  */
  21
  22 /* Scalable DWARF2 Arange Set.
  23
  24    The original code in dwarf2.c uses an unsorted singly-linked list to
  25    represent aranges in a compilation unit.  Looking up for an address
  26    became very in-efficient for extremely large binaries with many
  27    compilation units, each of which having long list of aranges.
  28
  29    The arange-set implemented here supports insertion and address
  30    containment queries for an arbitrary large collection of aranges in
  31    an efficient manner.  In addition, it also supports aranges with
  32    values.
  33
  34      Arange insertion with value.
  35
  36    For valued arange-set, we need to specify 4 operations during set
  37    creation.  If unspecified, reasonable default behaviours are assumed.
  38    The operations define how arange insertion merges two identical aranges
  39    with different values. The 4 operations are:
  40
  41         Equality
  42         Copy
  43         Combination
  44         Deletion
  45
  46    When arange_set_insert () inserts an arange. It breaks the to-be-inserted
  47    arange into smaller aranges using the boundaries of any overlapping
  48    aranges as cutting point.  In addition, arange_set_insert () may also
  49    splilt any existing arange that overlap the ends of the to-be-inserted
  50    arange.  After such splitting of the new and existing aranges, the
  51    to-be-inserted arange becomes a collection of smaller aranges, each of
  52    which either does not overlapping with any existing arange or overlapping
  53    completely with one existing arange.  While splitting aranges, values
  54    are copied using the Copy operation specified in the set.
  55
  56    The for each smaller new arange, arange_set_insert () inserts the new
  57    arange according to these rules:
  58
  59    1. If there is no overlapping existing arange, insert new arange.
  60
  61    2. If there is an overlapping existing arange and its value equals
  62       to the inserted value according to the value equality operation
  63       of the set, do nothing.
  64
  65    3. If there is an overlapping existing arange and its value is not
  66       the inserted value according to the value equality operation,
  67       combine the inserted value with that of the existing arange using
  68       the value combination operation of set.
  69
  70    If as a result of insertion, there are adjacent aranges with equal values,
  71    the adjacent aranges will be merge.  */
  72
  73 #ifndef ARANGE_SET_H
  74 #define ARANGE_SET_H
  75
  76 #include "sysdep.h"
  77 #include "bfd.h"
  78
  79 /* An arange_set is a pointer to an arange_set_s struct, whose implementation
  80    is opaque to clients using the arange set.  */
  81 typedef struct arange_set_s *arange_set;
  82
  83 #ifndef _WIN64
  84   typedef unsigned long int arange_set_uhostptr_t;
  85 #else
  86   typedef unsigned long long arange_set_uhostptr_t;
  87 #endif
  88
  89 /* Type of value attached to an arange.  This should be wide enough to be
  90    converted from and back to any type without loss.  */
  91 typedef arange_set_uhostptr_t arange_value_type;
  92
  93 /* Type of function that is used to allocate memory for an arange-set.  */
  94 typedef void* (*arange_set_allocate_fn)(int, void*);
  95
  96 /* Type of function that is used to deallocate memory of an arange-set.  */
  97 typedef void (*arange_set_deallocate_fn)(void*, void*);
  98
  99 /* Type of function that is called for each arange during a traversal of
 100    the set containing that arange.  */
 101 typedef int (*arange_set_foreach_fn)(bfd_vma, bfd_vma, arange_value_type,
 102                                      void *);
 103
 104 /* Type of function that is called to test equality of range values. */
 105 typedef bfd_boolean (*arange_value_equal_fn)(arange_value_type,
 106                                              arange_value_type, void *);
 107
 108 /* Type of function that is called to copy a range value. */
 109 typedef arange_value_type (*arange_value_copy_fn)(arange_value_type, void *);
 110
 111 /* Type of function that is called to combine two range values. */
 112 typedef arange_value_type (*arange_value_combine_fn)(arange_value_type,
 113                                                      arange_value_type,
 114                                                      void *);
 115
 116 /* Type of function that is called to delete a range value. */
 117 typedef void (*arange_value_delete_fn)(arange_value_type, void *);
 118
 119 /* Create an arange set.  Return the new set of NULL if there is any
 120    error.  */
 121 extern arange_set arange_set_new (arange_set_allocate_fn,
 122                                   arange_set_deallocate_fn,
 123                                   bfd_boolean,
 124                                   arange_value_equal_fn,
 125                                   arange_value_copy_fn,
 126                                   arange_value_combine_fn,
 127                                   arange_value_delete_fn,
 128                                   void *);
 129
 130 /*  Delete an arange set.  */
 131 extern void arange_set_delete (arange_set);
 132
 133 /* Return TRUE if an only if arange set is empty.  */
 134 extern bfd_boolean arange_set_empty_p (arange_set);
 135
 136 /* Check to see if a given address is in an arange set.  Return TRUE if the
 137    address is inside one of the aranges and if also low_ptr and high_ptr are
 138    not NULL, return the boundaries of the arange.
 139
 140    If the address is not in any arange in set, return FALSE. */
 141 extern bfd_boolean arange_set_lookup_address (arange_set, bfd_vma, bfd_vma *,
 142                                               bfd_vma *, arange_value_type *);
 143
 144 /* Insert an arange [low,high] into a set.  Note that the address high is
 145    also included where as in DWARF2 an address range between low & high means
 146    [low,high).
 147
 148    If the set is created with no capability of storing values, the value
 149    argument is ignored.  Otherwise, the value is stored in the inserted range.
 150    If there are overlapping ranges, values are combined according to
 151    value_combine_fn.
 152
 153    If value is an object, arange_set_insert () takes ownership of that objec.
 154    Caller should not deallocate objects that are passed to arange_set_insert().
 155
 156    Return TRUE if and only if there is no error.  */
 157 extern bfd_boolean arange_set_insert (arange_set, bfd_vma, bfd_vma,
 158                                       arange_value_type);
 159
 160 /* Return TRUE if and only if arange set supports arang evalues.  */
 161 extern bfd_boolean arange_set_has_values_p (arange_set);
 162
 163 /* Traverse aranges in a set.  For each arange in ascending order of
 164    low addresses, call foreach_fn with arange boundaries and data.
 165    If any invocation of foreach_fn returns a non-zero value, stop traversal
 166    and return that value. Otherwise, return 0.  */
 167 extern int arange_set_foreach (arange_set, arange_set_foreach_fn, void *);
 168
 169 /* Return TRUE if two values are considered equal by the value comparison
 170    function of an arange_set.  If the arange set does not support values or
 171    if it has no value equality function specified, this function performs
 172    a bit-wise comparison of its input.  */
 173 extern bfd_boolean arange_set_value_equal_p (arange_set, arange_value_type,
 174                                              arange_value_type);
 175
 176 /* Duplicate a value. If the arange set does not support values or if it
 177    has no value copying function specified, this function returns the input
 178    value.  */
 179 extern arange_value_type arange_set_copy_value (arange_set, arange_value_type);
 180
 181 /* Allocate memory using the allocator of an arange set.  */
 182 extern void * arange_set_allocate (arange_set, int);
 183
 184 /* Deallocate memory allocated from arange_set_allocate ().  */
 185 extern void arange_set_deallocate (arange_set, void *);
 186
 187 #endif /* ARANGE_SET_H */