| /* 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. */ |
| |
| /* Scalable DWARF2 Arange Set. |
| |
| The original code in dwarf2.c uses an unsorted singly-linked list to |
| represent aranges in a compilation unit. Looking up for an address |
| became very in-efficient for extremely large binaries with many |
| compilation units, each of which having long list of aranges. |
| |
| The arange-set implemented here supports insertion and address |
| containment queries for an arbitrary large collection of aranges in |
| an efficient manner. In addition, it also supports aranges with |
| values. |
| |
| Arange insertion with value. |
| |
| For valued arange-set, we need to specify 4 operations during set |
| creation. If unspecified, reasonable default behaviours are assumed. |
| The operations define how arange insertion merges two identical aranges |
| with different values. The 4 operations are: |
| |
| Equality |
| Copy |
| Combination |
| Deletion |
| |
| When arange_set_insert () inserts an arange. It breaks the to-be-inserted |
| arange into smaller aranges using the boundaries of any overlapping |
| aranges as cutting point. In addition, arange_set_insert () may also |
| splilt any existing arange that overlap the ends of the to-be-inserted |
| arange. After such splitting of the new and existing aranges, the |
| to-be-inserted arange becomes a collection of smaller aranges, each of |
| which either does not overlapping with any existing arange or overlapping |
| completely with one existing arange. While splitting aranges, values |
| are copied using the Copy operation specified in the set. |
| |
| The for each smaller new arange, arange_set_insert () inserts the new |
| arange according to these rules: |
| |
| 1. If there is no overlapping existing arange, insert new arange. |
| |
| 2. If there is an overlapping existing arange and its value equals |
| to the inserted value according to the value equality operation |
| of the set, do nothing. |
| |
| 3. If there is an overlapping existing arange and its value is not |
| the inserted value according to the value equality operation, |
| combine the inserted value with that of the existing arange using |
| the value combination operation of set. |
| |
| If as a result of insertion, there are adjacent aranges with equal values, |
| the adjacent aranges will be merge. */ |
| |
| #ifndef ARANGE_SET_H |
| #define ARANGE_SET_H |
| |
| #include "sysdep.h" |
| #include "bfd.h" |
| |
| /* An arange_set is a pointer to an arange_set_s struct, whose implementation |
| is opaque to clients using the arange set. */ |
| typedef struct arange_set_s *arange_set; |
| |
| #ifndef _WIN64 |
| typedef unsigned long int arange_set_uhostptr_t; |
| #else |
| typedef unsigned long long arange_set_uhostptr_t; |
| #endif |
| |
| /* Type of value attached to an arange. This should be wide enough to be |
| converted from and back to any type without loss. */ |
| typedef arange_set_uhostptr_t arange_value_type; |
| |
| /* Type of function that is used to allocate memory for an arange-set. */ |
| typedef void* (*arange_set_allocate_fn)(int, void*); |
| |
| /* Type of function that is used to deallocate memory of an arange-set. */ |
| typedef void (*arange_set_deallocate_fn)(void*, void*); |
| |
| /* Type of function that is called for each arange during a traversal of |
| the set containing that arange. */ |
| typedef int (*arange_set_foreach_fn)(bfd_vma, bfd_vma, arange_value_type, |
| void *); |
| |
| /* Type of function that is called to test equality of range values. */ |
| typedef bfd_boolean (*arange_value_equal_fn)(arange_value_type, |
| arange_value_type, void *); |
| |
| /* Type of function that is called to copy a range value. */ |
| typedef arange_value_type (*arange_value_copy_fn)(arange_value_type, void *); |
| |
| /* Type of function that is called to combine two range values. */ |
| typedef arange_value_type (*arange_value_combine_fn)(arange_value_type, |
| arange_value_type, |
| void *); |
| |
| /* Type of function that is called to delete a range value. */ |
| typedef void (*arange_value_delete_fn)(arange_value_type, void *); |
| |
| /* Create an arange set. Return the new set of NULL if there is any |
| error. */ |
| extern arange_set arange_set_new (arange_set_allocate_fn, |
| arange_set_deallocate_fn, |
| bfd_boolean, |
| arange_value_equal_fn, |
| arange_value_copy_fn, |
| arange_value_combine_fn, |
| arange_value_delete_fn, |
| void *); |
| |
| /* Delete an arange set. */ |
| extern void arange_set_delete (arange_set); |
| |
| /* Return TRUE if an only if arange set is empty. */ |
| extern bfd_boolean arange_set_empty_p (arange_set); |
| |
| /* Check to see if a given address is in an arange set. Return TRUE if the |
| address is inside one of the aranges and if also low_ptr and high_ptr are |
| not NULL, return the boundaries of the arange. |
| |
| If the address is not in any arange in set, return FALSE. */ |
| extern bfd_boolean arange_set_lookup_address (arange_set, bfd_vma, bfd_vma *, |
| bfd_vma *, arange_value_type *); |
| |
| /* Insert an arange [low,high] into a set. Note that the address high is |
| also included where as in DWARF2 an address range between low & high means |
| [low,high). |
| |
| If the set is created with no capability of storing values, the value |
| argument is ignored. Otherwise, the value is stored in the inserted range. |
| If there are overlapping ranges, values are combined according to |
| value_combine_fn. |
| |
| If value is an object, arange_set_insert () takes ownership of that objec. |
| Caller should not deallocate objects that are passed to arange_set_insert(). |
| |
| Return TRUE if and only if there is no error. */ |
| extern bfd_boolean arange_set_insert (arange_set, bfd_vma, bfd_vma, |
| arange_value_type); |
| |
| /* Return TRUE if and only if arange set supports arang evalues. */ |
| extern bfd_boolean arange_set_has_values_p (arange_set); |
| |
| /* 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. */ |
| extern int arange_set_foreach (arange_set, arange_set_foreach_fn, void *); |
| |
| /* Return TRUE if two values are considered equal by the value comparison |
| function of an arange_set. If the arange set does not support values or |
| if it has no value equality function specified, this function performs |
| a bit-wise comparison of its input. */ |
| extern bfd_boolean arange_set_value_equal_p (arange_set, arange_value_type, |
| arange_value_type); |
| |
| /* Duplicate a value. If the arange set does not support values or if it |
| has no value copying function specified, this function returns the input |
| value. */ |
| extern arange_value_type arange_set_copy_value (arange_set, arange_value_type); |
| |
| /* Allocate memory using the allocator of an arange set. */ |
| extern void * arange_set_allocate (arange_set, int); |
| |
| /* Deallocate memory allocated from arange_set_allocate (). */ |
| extern void arange_set_deallocate (arange_set, void *); |
| |
| #endif /* ARANGE_SET_H */ |