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 | #include "sysdep.h" | |
23 | #include "bfd.h" | |
24 | #include "libiberty.h" | |
25 | #include "libbfd.h" | |
26 | #include "arange-set.h" | |
27 | #include "splay-tree.h" | |
28 | ||
29 | /* Implementation of an arange-set. The set is implemented using the | |
30 | splay tree support in libiberty. The advantage of using this is | |
31 | that it has been well tested and is relatively simple to use. The | |
32 | disadvantage is that it is too general and it does not fit our design | |
33 | exactly. So we waste a bit of memory for unneeded generality and work | |
34 | around for mis-match between the splay tree API and the arange-set | |
35 | internals. A specialized implentation of a balanced tree type for | |
36 | arange-set exclusively may speed up things a little and reduce memory | |
37 | consumption. Until there is a pressing need, we stick to the splay | |
38 | tree in libiberty. */ | |
39 | ||
40 | struct arange_set_s | |
41 | { | |
42 | /* Splay tree containing aranges. */ | |
43 | splay_tree ranges; | |
44 | ||
45 | /* Lowest address in set. If set is empty, it is ~0. */ | |
46 | bfd_vma lower_bound; | |
47 | ||
48 | /* Highest address in set. If set is empty, it is 0. */ | |
49 | bfd_vma upper_bound; | |
50 | ||
51 | /* TRUE if aranges in this set have values. */ | |
52 | bfd_boolean value_p; | |
53 | ||
54 | /* Function to compare arange values. */ | |
55 | arange_value_equal_fn value_equal_fn; | |
56 | ||
57 | /* Function to copy an arange value. */ | |
58 | arange_value_copy_fn value_copy_fn; | |
59 | ||
60 | /* Function to combine arange values. */ | |
61 | arange_value_combine_fn value_combine_fn; | |
62 | ||
63 | /* Function to delete an arange value. */ | |
64 | arange_value_delete_fn value_delete_fn; | |
65 | ||
66 | /* Function to allocate a piece of memory. */ | |
67 | arange_set_allocate_fn allocate_fn; | |
68 | ||
69 | /* Function to deallocate a piece of memory. */ | |
70 | arange_set_deallocate_fn deallocate_fn; | |
71 | ||
72 | /* Call back data shared by all callbacks. */ | |
73 | void *data; | |
74 | }; | |
75 | ||
76 | /* Structure for aranges with a value attached. Since a splay tree | |
77 | node can only hold one value, we need to use the container struct | |
78 | to store data associated with an arange and have the splay tree value | |
79 | to be a pointer to this struct. */ | |
80 | ||
81 | typedef struct | |
82 | { | |
83 | /* High-pc of an arange. This is different from the DWARF2 semantics that | |
84 | the high-pc is really the last location in an arange. */ | |
85 | bfd_vma high; | |
86 | ||
87 | /* We need to store a pointer to the set because splay_tree_value_delete | |
88 | only takes a pointer to the value deleted. If we use a deallocator | |
89 | that need extra information like a pointer to the memory pool, we need to | |
90 | look up via the set pointer. This adds one extra pointer per arange. */ | |
91 | arange_set set; | |
92 | ||
93 | /* Value associated with this arange. */ | |
94 | arange_value_type value; | |
95 | ||
96 | } arange_value_container_t; | |
97 | ||
98 | ||
99 | ||
100 | static void | |
101 | arange_set_delete_value (arange_set set, arange_value_type value) | |
102 | { | |
103 | if (set->value_delete_fn) | |
104 | (set->value_delete_fn) (value, set->data); | |
105 | } | |
106 | ||
107 | /* Compare two VMAs as keys of splay tree nodes. */ | |
108 | ||
109 | static int | |
110 | splay_tree_compare_bfd_vmas (splay_tree_key k1, splay_tree_key k2) | |
111 | { | |
112 | if ((bfd_vma) k1 < (bfd_vma) k2) | |
113 | return -1; | |
114 | else if ((bfd_vma) k1 > (bfd_vma) k2) | |
115 | return 1; | |
116 | ||
117 | return 0; | |
118 | } | |
119 | ||
120 | /* Default memory allocator and deallocator. */ | |
121 | ||
122 | void * | |
123 | arange_set_allocate (arange_set set, int size) | |
124 | { | |
125 | if (set->allocate_fn) | |
126 | return (set->allocate_fn) (size, set->data); | |
127 | ||
128 | return xmalloc (size); | |
129 | } | |
130 | ||
131 | void | |
132 | arange_set_deallocate (arange_set set, void *object) | |
133 | { | |
134 | if (set->deallocate_fn) | |
135 | (set->deallocate_fn) (object, set->data); | |
136 | else | |
137 | free (object); | |
138 | } | |
139 | ||
140 | static void | |
141 | arange_set_delete_value_container (splay_tree_value value) | |
142 | { | |
143 | arange_value_container_t *container; | |
144 | ||
145 | container = (arange_value_container_t*) value; | |
146 | arange_set_delete_value (container->set, container->value); | |
147 | arange_set_deallocate (container->set, container); | |
148 | } | |
149 | ||
150 | /* Create an arange set. Return the new set of NULL if there is any | |
151 | error. | |
152 | ||
153 | allocate_fn is the memory allocator function of this arange set. If | |
154 | it is NULL, the default allocator will be used. | |
155 | ||
156 | deallocate_fn is the memory deallocator function of this arange set. If | |
157 | it is NULL, the default allocator will be used. | |
158 | ||
159 | value_p specifies whether an arange set supports values. If it is | |
160 | TURE. Each arange can be associated with a value of type arange_value_type. | |
161 | If it is FALSE, the following parameters value_equal_fn, value_copy_fn, | |
162 | value_combine_fn and value_delete_fn will be ignored. | |
163 | ||
164 | value_equal_fn is the value equality function. An arange uses it to | |
165 | check if two values are the same. If it is NULL, the default bit-wise | |
166 | equality function will be used. | |
167 | ||
168 | value_copy_fn is the value copy function. An arange uses it to copy | |
169 | values of type arange_value_type. If it is NULL, the default bit-wise | |
170 | copy function will be used. | |
171 | ||
172 | value_combine_fn is the value combine function. An arange uses it to | |
173 | combine values of two identical arange. If it is NULL, the default | |
174 | constant zero function will be used. | |
175 | ||
176 | value_delete_fn is the value deletion function. If it is not NULL, | |
177 | it will be called when an arange deletes a value. | |
178 | ||
179 | data is pointer to an object, which will be passed to all allocate_fn, | |
180 | deallocate_fn, value_equal_fn, value_copy_fn, value_combine_fn and | |
181 | value_delete_fn. */ | |
182 | ||
183 | arange_set | |
184 | arange_set_new (arange_set_allocate_fn allocate_fn, | |
185 | arange_set_deallocate_fn deallocate_fn, | |
186 | bfd_boolean value_p, | |
187 | arange_value_equal_fn value_equal_fn, | |
188 | arange_value_copy_fn value_copy_fn, | |
189 | arange_value_combine_fn value_combine_fn, | |
190 | arange_value_delete_fn value_delete_fn, | |
191 | void *data) | |
192 | { | |
193 | arange_set set; | |
194 | splay_tree sp; | |
195 | splay_tree_delete_value_fn fn; | |
196 | ||
197 | /* Allocate space for arange structure. */ | |
198 | set = (arange_set) | |
199 | (*allocate_fn) (sizeof (struct arange_set_s), data); | |
200 | if (!set) | |
201 | return set; | |
202 | ||
203 | fn = value_p ? arange_set_delete_value_container : NULL; | |
204 | sp = splay_tree_new_with_allocator (splay_tree_compare_bfd_vmas, NULL, | |
205 | fn, allocate_fn, deallocate_fn, | |
206 | data); | |
207 | if (!sp) | |
208 | { | |
209 | (deallocate_fn) (set, data); | |
210 | return NULL; | |
211 | } | |
212 | ||
213 | set->ranges = sp; | |
214 | set->lower_bound = ~0; | |
215 | set->upper_bound = 0; | |
216 | set->value_p = value_p; | |
217 | set->allocate_fn = allocate_fn; | |
218 | set->deallocate_fn = deallocate_fn; | |
219 | set->value_equal_fn = value_equal_fn; | |
220 | set->value_copy_fn = value_copy_fn; | |
221 | set->value_combine_fn = value_combine_fn; | |
222 | set->value_delete_fn = value_delete_fn; | |
223 | set->data = data; | |
224 | return set; | |
225 | } | |
226 | ||
227 | /* Delete an arange set. */ | |
228 | ||
229 | void | |
230 | arange_set_delete (arange_set set) | |
231 | { | |
232 | splay_tree_delete (set->ranges); | |
233 | (*set->deallocate_fn) (set, set->data); | |
234 | } | |
235 | ||
236 | /* Return TRUE if and only if arange set is empty. */ | |
237 | ||
238 | bfd_boolean | |
239 | arange_set_empty_p (arange_set set) | |
240 | { | |
241 | return set->lower_bound > set->upper_bound; | |
242 | } | |
243 | ||
244 | /* Accessors for low and high of an arange. | |
245 | ||
246 | There is no arange_set_node_set_low since the low address is the | |
247 | key of the splay tree node. */ | |
248 | ||
249 | /* Get the high VMA address of a node. */ | |
250 | ||
251 | static bfd_vma | |
252 | arange_set_node_high (arange_set set, splay_tree_node node) | |
253 | { | |
254 | arange_value_container_t *container; | |
255 | ||
256 | if (set->value_p) | |
257 | { | |
258 | container = (arange_value_container_t*) node->value; | |
259 | return container->high; | |
260 | } | |
261 | ||
262 | return (bfd_vma) node->value; | |
263 | } | |
264 | ||
265 | /* Set the high VMA address of a node. */ | |
266 | ||
267 | static void | |
268 | arange_set_node_set_high (arange_set set, splay_tree_node node, bfd_vma address) | |
269 | { | |
270 | arange_value_container_t *container; | |
271 | ||
272 | if (set->value_p) | |
273 | { | |
274 | container = (arange_value_container_t*) node->value; | |
275 | container->high = address; | |
276 | } | |
277 | else | |
278 | node->value = (splay_tree_value) address; | |
279 | } | |
280 | ||
281 | /* Get the low VMA address of a node. */ | |
282 | ||
283 | static bfd_vma | |
284 | arange_set_node_low (splay_tree_node node) | |
285 | { | |
286 | return (bfd_vma) node->key; | |
287 | } | |
288 | ||
289 | /* If arange set supports values, return value of an arange; otheriwse | |
290 | always return 0 so that it appears that all aranges have the same value. */ | |
291 | ||
292 | static arange_value_type | |
293 | arange_set_node_value (arange_set set, splay_tree_node node) | |
294 | { | |
295 | arange_value_container_t *container; | |
296 | ||
297 | if (set->value_p) | |
298 | { | |
299 | container = (arange_value_container_t*) node->value; | |
300 | return container->value; | |
301 | } | |
302 | ||
303 | return 0; | |
304 | } | |
305 | ||
306 | /* If arange set supports values, return value of an arange; otheriwse | |
307 | always return 0 so that it appears that all aranges have the same value. */ | |
308 | ||
309 | static void | |
310 | arange_set_node_set_value (arange_set set, | |
311 | splay_tree_node node, | |
312 | arange_value_type value) | |
313 | { | |
314 | arange_value_container_t *container; | |
315 | ||
316 | if (set->value_p) | |
317 | { | |
318 | container = (arange_value_container_t*) node->value; | |
319 | container->value = value; | |
320 | } | |
321 | } | |
322 | ||
323 | /* Return TRUE if and only if arange set supports values. */ | |
324 | ||
325 | bfd_boolean | |
326 | arange_set_has_values_p (arange_set set) | |
327 | { | |
328 | return set->value_p; | |
329 | } | |
330 | ||
331 | /* Copy a value using the value copying function of an arange set. If | |
332 | the set does not support values or if there is not value copying | |
333 | function specified, it simply returns the input value. */ | |
334 | ||
335 | arange_value_type | |
336 | arange_set_copy_value (arange_set set, arange_value_type value) | |
337 | { | |
338 | /* If no copy function is specified or set does not support values, | |
339 | default is bit-wise copy. */ | |
340 | if (set->value_p && set->value_copy_fn) | |
341 | return (set->value_copy_fn) (value, set->data); | |
342 | ||
343 | return value; | |
344 | } | |
345 | ||
346 | static arange_value_type | |
347 | arange_set_combine_value (arange_set set, | |
348 | arange_value_type value1, | |
349 | arange_value_type value2) | |
350 | { | |
351 | /* If no combine function is specified or set does not support values, | |
352 | default is returning 0. */ | |
353 | if (set->value_p && set->value_combine_fn) | |
354 | return (set->value_combine_fn) (value1, value2, set->data); | |
355 | ||
356 | return (arange_value_type) 0; | |
357 | } | |
358 | ||
359 | /* Compares two values for equality. If the arange set does not support values | |
360 | or if no value equality function is specified, this function simply does | |
361 | a bit-wise comparison. */ | |
362 | ||
363 | bfd_boolean | |
364 | arange_set_value_equal_p (arange_set set, | |
365 | arange_value_type value1, | |
366 | arange_value_type value2) | |
367 | { | |
368 | /* If no equality function is specified or set does not support values, | |
369 | default is bit-wise comparison. */ | |
370 | if (set->value_p && set->value_equal_fn) | |
371 | return (set->value_equal_fn) (value1, value2, set->data); | |
372 | ||
373 | return value1 == value2; | |
374 | } | |
375 | ||
376 | /* Check to see if a given address is in an arange set. Return TRUE if the | |
377 | address is inside one of the aranges. If low_ptr, high_ptr and value_ptr are | |
378 | used to return lower address, upper address and value associated with a | |
379 | found arounge. If anyone of them is NULL, the corresponding information | |
380 | is not returned. For arange set without values, no information is returned | |
381 | through the pointer value_ptr. */ | |
382 | ||
383 | bfd_boolean | |
384 | arange_set_lookup_address (arange_set set, bfd_vma address, | |
385 | bfd_vma *low_ptr, bfd_vma *high_ptr, | |
386 | arange_value_type *value_ptr) | |
387 | { | |
388 | splay_tree_node pred, node; | |
389 | ||
390 | if (address < set->lower_bound || address > set->upper_bound) | |
391 | return FALSE; | |
392 | ||
393 | /* Find immediate predecessor. */ | |
394 | pred = splay_tree_predecessor (set->ranges, (splay_tree_key) address); | |
395 | if (pred | |
396 | && arange_set_node_high (set, pred) >= address) | |
397 | node = pred; | |
398 | else | |
399 | /* If the predecessor range does not cover this address, the address | |
400 | is in the arange set only if itself starts an arange. */ | |
401 | node = splay_tree_lookup (set->ranges, (splay_tree_key) address); | |
402 | ||
403 | if (node) | |
404 | { | |
405 | /* Also return arange boundaries if caller supplies pointers. */ | |
406 | if (low_ptr) | |
407 | *low_ptr = arange_set_node_low (node); | |
408 | if (high_ptr) | |
409 | *high_ptr = arange_set_node_high (set, node); | |
410 | if (set->value_p && value_ptr) | |
411 | *value_ptr = arange_set_node_value (set, node); | |
412 | return TRUE; | |
413 | } | |
414 | ||
415 | return FALSE; | |
416 | } | |
417 | ||
418 | /* Insert an arange [low, high] into a set's splay tree. If the set supports | |
419 | value, also insert with the given value. Return the inserted node if there | |
420 | is no error or NULL otherwise. */ | |
421 | ||
422 | static splay_tree_node | |
423 | arange_set_splay_tree_insert (arange_set set, | |
424 | bfd_vma low, | |
425 | bfd_vma high, | |
426 | arange_value_type value) | |
427 | { | |
428 | splay_tree_value sp_value; | |
429 | arange_value_container_t *container; | |
430 | ||
431 | if (set->value_p) | |
432 | { | |
433 | int size = sizeof (arange_value_container_t); | |
434 | void *data = set->ranges->allocate_data; | |
435 | ||
436 | container = | |
437 | (arange_value_container_t*) (*set->ranges->allocate) (size, data); | |
438 | if (!container) | |
439 | return NULL; | |
440 | container->high = high; | |
441 | ||
442 | /* Due to the design of splay tree API, there is no way of passing | |
443 | callback data to the splay tree value delete function. Hence we need | |
444 | to store a pointer to set in every containier! */ | |
445 | container->set = set; | |
446 | ||
447 | container->value = value; | |
448 | sp_value = (splay_tree_value) container; | |
449 | } | |
450 | else | |
451 | sp_value = (splay_tree_value) high; | |
452 | ||
453 | /* Currently splay_tree_insert does not return any status to tell if there | |
454 | is an error. */ | |
455 | return splay_tree_insert (set->ranges, (splay_tree_key) low, sp_value); | |
456 | } | |
457 | ||
458 | /* Split [low, high] to [low, address) & [address, high]. */ | |
459 | ||
460 | static bfd_boolean | |
461 | arange_set_split_node (arange_set set, splay_tree_node node, bfd_vma address) | |
462 | { | |
463 | splay_tree_node node2; | |
464 | arange_value_type value; | |
465 | bfd_vma low, high; | |
466 | ||
467 | low = arange_set_node_low (node); | |
468 | high = arange_set_node_high (set, node); | |
469 | ||
470 | BFD_ASSERT (low < address && address <= high); | |
471 | ||
472 | value = arange_set_copy_value (set, arange_set_node_value (set, node)); | |
473 | node2 = arange_set_splay_tree_insert (set, address, high, value); | |
474 | if (!node2) | |
475 | return FALSE; | |
476 | ||
477 | arange_set_node_set_high (set, node, address - 1); | |
478 | return TRUE; | |
479 | } | |
480 | ||
481 | static splay_tree_node | |
482 | arange_set_maybe_merge_with_predecessor (arange_set set, splay_tree_node node) | |
483 | { | |
484 | splay_tree_node pred; | |
485 | bfd_vma low, high; | |
486 | ||
487 | low = arange_set_node_low (node); | |
488 | high = arange_set_node_high (set, node); | |
489 | ||
490 | pred = splay_tree_predecessor (set->ranges, low); | |
491 | if (! pred) | |
492 | return node; | |
493 | ||
494 | if (arange_set_node_high (set, pred) + 1 == low | |
495 | && arange_set_value_equal_p (set, | |
496 | arange_set_node_value (set, pred), | |
497 | arange_set_node_value (set, node))) | |
498 | { | |
499 | splay_tree_remove (set->ranges, arange_set_node_low (node)); | |
500 | arange_set_node_set_high (set, pred, high); | |
501 | return arange_set_maybe_merge_with_predecessor (set, pred); | |
502 | } | |
503 | ||
504 | return node; | |
505 | } | |
506 | ||
507 | /* Insert an arange [low,high] into a set. Return TRUE if and only if there | |
508 | is no error. Note that the address high is also included where as in | |
509 | DWARF2 an address range between low & high means [low,high). | |
510 | ||
511 | This only handles sets with values. For the simpler case of sets without | |
512 | value, it is handled in arange_set_insert(). This function is | |
513 | tail-recurive. It is guaranteed to terminate because it only recurses | |
514 | with a smaller range than it is given. */ | |
515 | ||
516 | static bfd_boolean | |
517 | arange_set_insert_value (arange_set set, | |
518 | bfd_vma low, | |
519 | bfd_vma high, | |
520 | arange_value_type value) | |
521 | { | |
522 | splay_tree_node succ, pred, node; | |
523 | bfd_vma succ_high, succ_low; | |
524 | arange_value_type combined, old_value; | |
525 | ||
526 | if (low > high) | |
527 | { | |
528 | arange_set_delete_value (set, value); | |
529 | return FALSE; | |
530 | } | |
531 | ||
532 | pred = splay_tree_predecessor (set->ranges, low); | |
533 | if (pred && arange_set_node_high (set, pred) >= low) | |
534 | arange_set_split_node (set, pred, low); | |
535 | ||
536 | node = splay_tree_lookup (set->ranges, low); | |
537 | if (node) | |
538 | { | |
539 | /* Split node if its arange is larger than inserted arange. */ | |
540 | if (arange_set_node_high (set, node) > high) | |
541 | arange_set_split_node (set, node, high + 1); | |
542 | ||
543 | old_value = arange_set_node_value (set, node); | |
544 | combined = arange_set_combine_value (set, old_value, value); | |
545 | arange_set_node_set_value (set, node, combined); | |
546 | node = arange_set_maybe_merge_with_predecessor (set, node); | |
547 | arange_set_delete_value (set, old_value); | |
548 | ||
549 | /* Insert remaining arange by tail-recursion. */ | |
550 | if (high > arange_set_node_high (set, node)) | |
551 | return arange_set_insert_value (set, | |
552 | arange_set_node_high (set, node) + 1, | |
553 | high, value); | |
554 | else | |
555 | { | |
556 | /* Node must cover exactly the range. */ | |
557 | BFD_ASSERT (high == arange_set_node_high (set, node)); | |
558 | arange_set_delete_value (set, value); | |
559 | succ = splay_tree_successor (set->ranges, arange_set_node_low (node)); | |
560 | if (succ) | |
561 | succ = arange_set_maybe_merge_with_predecessor (set, succ); | |
562 | return TRUE; | |
563 | } | |
564 | } | |
565 | ||
566 | succ = splay_tree_successor (set->ranges, low); | |
567 | if (succ) | |
568 | { | |
569 | succ_low = arange_set_node_low (succ); | |
570 | succ_high = arange_set_node_high (set, succ); | |
571 | ||
572 | if (succ_low <= high) | |
573 | { | |
574 | node = arange_set_splay_tree_insert (set, low, succ_low - 1, value); | |
575 | if (!node) | |
576 | return FALSE; | |
577 | ||
578 | /* Update set lower bound only after insertion is successful. */ | |
579 | if (low < set->lower_bound) | |
580 | set->lower_bound = low; | |
581 | ||
582 | node = arange_set_maybe_merge_with_predecessor (set, node); | |
583 | ||
584 | /* Recurse to handle rest of insertion. Note that we have to copy | |
585 | value here since it has already been used in the node above. */ | |
586 | return arange_set_insert_value (set, succ_low, high, | |
587 | arange_set_copy_value (set, value)); | |
588 | } | |
589 | } | |
590 | ||
591 | node = arange_set_splay_tree_insert (set, low, high, value); | |
592 | if (!node) | |
593 | return FALSE; | |
594 | ||
595 | /* Update set boundaries only after insertion is successful. */ | |
596 | if (low < set->lower_bound) | |
597 | set->lower_bound = low; | |
598 | if (high > set->upper_bound) | |
599 | set->upper_bound = high; | |
600 | ||
601 | node = arange_set_maybe_merge_with_predecessor (set, node); | |
602 | ||
603 | succ = splay_tree_successor (set->ranges, arange_set_node_low (node)); | |
604 | if (succ) | |
605 | succ = arange_set_maybe_merge_with_predecessor (set, succ); | |
606 | ||
607 | return TRUE; | |
608 | } | |
609 | ||
610 | bfd_boolean | |
611 | arange_set_insert (arange_set set, | |
612 | bfd_vma low, | |
613 | bfd_vma high, | |
614 | arange_value_type value) | |
615 | { | |
616 | splay_tree tree = set->ranges; | |
617 | splay_tree_node pred, succ, node = NULL; | |
618 | bfd_vma pred_high, node_low; | |
619 | ||
620 | if (set->value_p) | |
621 | return arange_set_insert_value (set, low, high, value); | |
622 | ||
623 | if (low > high) | |
624 | return FALSE; | |
625 | ||
626 | pred = splay_tree_predecessor (tree, low); | |
627 | if (pred) | |
628 | { | |
629 | pred_high = arange_set_node_high (set, pred); | |
630 | ||
631 | /* Nothing to be done if predecessor contains new aranges. */ | |
632 | if (pred_high >= high) | |
633 | return TRUE; | |
634 | ||
635 | /* If we can expand predecessor, do so. Test for the case in which | |
636 | predecessor does not contain new arange but touches it. */ | |
637 | if (pred_high >= low || pred_high + 1 == low) | |
638 | { | |
639 | node = pred; | |
640 | arange_set_node_set_high (set, node, high); | |
641 | } | |
642 | } | |
643 | ||
644 | /* Try to see if [low,something] is already in splay tree. */ | |
645 | if (node == NULL) | |
646 | { | |
647 | node = splay_tree_lookup (tree, low); | |
648 | if (node) | |
649 | { | |
650 | /* Nothing to be done if node contains new aranges. */ | |
651 | if (arange_set_node_high (set, node) >= high) | |
652 | return TRUE; | |
653 | ||
654 | arange_set_node_set_high (set, node, high); | |
655 | } | |
656 | } | |
657 | ||
658 | if (node == NULL) | |
659 | { | |
660 | node = arange_set_splay_tree_insert (set, low, high, 0); | |
661 | if (!node) | |
662 | return FALSE; | |
663 | } | |
664 | ||
665 | BFD_ASSERT (node | |
666 | && arange_set_node_low (node) <= low | |
667 | && arange_set_node_high (set, node) >= high); | |
668 | ||
669 | /* Update set upper and lower bounds. */ | |
670 | if (low < set->lower_bound) | |
671 | set->lower_bound = low; | |
672 | if (high > set->upper_bound) | |
673 | set->upper_bound = high; | |
674 | ||
675 | /* Merge successor if it overlaps or touches node. */ | |
676 | node_low = arange_set_node_low (node); | |
677 | while ((succ = splay_tree_successor (tree, node_low)) != NULL | |
678 | && ((arange_set_node_high (set, node) >= arange_set_node_low (succ)) | |
679 | || (arange_set_node_high (set, node) + 1 | |
680 | == arange_set_node_low (succ)))) | |
681 | { | |
682 | if (arange_set_node_high (set, succ) > high) | |
683 | arange_set_node_set_high (set, node, arange_set_node_high (set, succ)); | |
684 | splay_tree_remove (tree, arange_set_node_low (succ)); | |
685 | } | |
686 | return TRUE; | |
687 | } | |
688 | ||
689 | struct arange_set_foreach_adapter_data | |
690 | { | |
691 | void *data; | |
692 | arange_set set; | |
693 | arange_set_foreach_fn foreach_fn; | |
694 | }; | |
695 | ||
696 | /* Adaptor to make arange_set_foreach works with splay_tree_foreach. */ | |
697 | ||
698 | static int | |
699 | arange_set_foreach_adapter (splay_tree_node node, void *data) | |
700 | { | |
701 | struct arange_set_foreach_adapter_data *adapter_data; | |
702 | arange_set set; | |
703 | ||
704 | adapter_data = data; | |
705 | set = adapter_data->set; | |
706 | return (adapter_data->foreach_fn) (arange_set_node_low (node), | |
707 | arange_set_node_high (set, node), | |
708 | arange_set_node_value (set, node), | |
709 | adapter_data->data); | |
710 | } | |
711 | ||
712 | /* Traverse aranges in a set. For each arange in ascending order of | |
713 | low addresses, call foreach_fn with arange boundaries and data. | |
714 | If any invocation of foreach_fn returns a non-zero value, stop traversal | |
715 | and return that value. Otherwise, return 0. */ | |
716 | ||
717 | int | |
718 | arange_set_foreach (arange_set set, | |
719 | arange_set_foreach_fn foreach_fn, | |
720 | void *data) | |
721 | { | |
722 | struct arange_set_foreach_adapter_data adapter_data; | |
723 | ||
724 | adapter_data.data = data; | |
725 | adapter_data.foreach_fn = foreach_fn; | |
726 | adapter_data.set = set; | |
727 | return splay_tree_foreach (set->ranges, arange_set_foreach_adapter, | |
728 | (void *) &adapter_data); | |
729 | } |