Commit | Line | Data |
---|---|---|
4ab20029 NC |
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 */ |