diff options
Diffstat (limited to 'bfd/arange-set.c')
| -rw-r--r-- | bfd/arange-set.c | 729 |
1 files changed, 729 insertions, 0 deletions
diff --git a/bfd/arange-set.c b/bfd/arange-set.c new file mode 100644 index 0000000..0a6c2f0 --- /dev/null +++ b/bfd/arange-set.c @@ -0,0 +1,729 @@ +/* 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. */ + +#include "sysdep.h" +#include "bfd.h" +#include "libiberty.h" +#include "libbfd.h" +#include "arange-set.h" +#include "splay-tree.h" + +/* Implementation of an arange-set. The set is implemented using the + splay tree support in libiberty. The advantage of using this is + that it has been well tested and is relatively simple to use. The + disadvantage is that it is too general and it does not fit our design + exactly. So we waste a bit of memory for unneeded generality and work + around for mis-match between the splay tree API and the arange-set + internals. A specialized implentation of a balanced tree type for + arange-set exclusively may speed up things a little and reduce memory + consumption. Until there is a pressing need, we stick to the splay + tree in libiberty. */ + +struct arange_set_s +{ + /* Splay tree containing aranges. */ + splay_tree ranges; + + /* Lowest address in set. If set is empty, it is ~0. */ + bfd_vma lower_bound; + + /* Highest address in set. If set is empty, it is 0. */ + bfd_vma upper_bound; + + /* TRUE if aranges in this set have values. */ + bfd_boolean value_p; + + /* Function to compare arange values. */ + arange_value_equal_fn value_equal_fn; + + /* Function to copy an arange value. */ + arange_value_copy_fn value_copy_fn; + + /* Function to combine arange values. */ + arange_value_combine_fn value_combine_fn; + + /* Function to delete an arange value. */ + arange_value_delete_fn value_delete_fn; + + /* Function to allocate a piece of memory. */ + arange_set_allocate_fn allocate_fn; + + /* Function to deallocate a piece of memory. */ + arange_set_deallocate_fn deallocate_fn; + + /* Call back data shared by all callbacks. */ + void *data; +}; + +/* Structure for aranges with a value attached. Since a splay tree + node can only hold one value, we need to use the container struct + to store data associated with an arange and have the splay tree value + to be a pointer to this struct. */ + +typedef struct +{ + /* High-pc of an arange. This is different from the DWARF2 semantics that + the high-pc is really the last location in an arange. */ + bfd_vma high; + + /* We need to store a pointer to the set because splay_tree_value_delete + only takes a pointer to the value deleted. If we use a deallocator + that need extra information like a pointer to the memory pool, we need to + look up via the set pointer. This adds one extra pointer per arange. */ + arange_set set; + + /* Value associated with this arange. */ + arange_value_type value; + +} arange_value_container_t; + + + +static void +arange_set_delete_value (arange_set set, arange_value_type value) +{ + if (set->value_delete_fn) + (set->value_delete_fn) (value, set->data); +} + +/* Compare two VMAs as keys of splay tree nodes. */ + +static int +splay_tree_compare_bfd_vmas (splay_tree_key k1, splay_tree_key k2) +{ + if ((bfd_vma) k1 < (bfd_vma) k2) + return -1; + else if ((bfd_vma) k1 > (bfd_vma) k2) + return 1; + + return 0; +} + +/* Default memory allocator and deallocator. */ + +void * +arange_set_allocate (arange_set set, int size) +{ + if (set->allocate_fn) + return (set->allocate_fn) (size, set->data); + + return xmalloc (size); +} + +void +arange_set_deallocate (arange_set set, void *object) +{ + if (set->deallocate_fn) + (set->deallocate_fn) (object, set->data); + else + free (object); +} + +static void +arange_set_delete_value_container (splay_tree_value value) +{ + arange_value_container_t *container; + + container = (arange_value_container_t*) value; + arange_set_delete_value (container->set, container->value); + arange_set_deallocate (container->set, container); +} + +/* Create an arange set. Return the new set of NULL if there is any + error. + + allocate_fn is the memory allocator function of this arange set. If + it is NULL, the default allocator will be used. + + deallocate_fn is the memory deallocator function of this arange set. If + it is NULL, the default allocator will be used. + + value_p specifies whether an arange set supports values. If it is + TURE. Each arange can be associated with a value of type arange_value_type. + If it is FALSE, the following parameters value_equal_fn, value_copy_fn, + value_combine_fn and value_delete_fn will be ignored. + + value_equal_fn is the value equality function. An arange uses it to + check if two values are the same. If it is NULL, the default bit-wise + equality function will be used. + + value_copy_fn is the value copy function. An arange uses it to copy + values of type arange_value_type. If it is NULL, the default bit-wise + copy function will be used. + + value_combine_fn is the value combine function. An arange uses it to + combine values of two identical arange. If it is NULL, the default + constant zero function will be used. + + value_delete_fn is the value deletion function. If it is not NULL, + it will be called when an arange deletes a value. + + data is pointer to an object, which will be passed to all allocate_fn, + deallocate_fn, value_equal_fn, value_copy_fn, value_combine_fn and + value_delete_fn. */ + +arange_set +arange_set_new (arange_set_allocate_fn allocate_fn, + arange_set_deallocate_fn deallocate_fn, + bfd_boolean value_p, + arange_value_equal_fn value_equal_fn, + arange_value_copy_fn value_copy_fn, + arange_value_combine_fn value_combine_fn, + arange_value_delete_fn value_delete_fn, + void *data) +{ + arange_set set; + splay_tree sp; + splay_tree_delete_value_fn fn; + + /* Allocate space for arange structure. */ + set = (arange_set) + (*allocate_fn) (sizeof (struct arange_set_s), data); + if (!set) + return set; + + fn = value_p ? arange_set_delete_value_container : NULL; + sp = splay_tree_new_with_allocator (splay_tree_compare_bfd_vmas, NULL, + fn, allocate_fn, deallocate_fn, + data); + if (!sp) + { + (deallocate_fn) (set, data); + return NULL; + } + + set->ranges = sp; + set->lower_bound = ~0; + set->upper_bound = 0; + set->value_p = value_p; + set->allocate_fn = allocate_fn; + set->deallocate_fn = deallocate_fn; + set->value_equal_fn = value_equal_fn; + set->value_copy_fn = value_copy_fn; + set->value_combine_fn = value_combine_fn; + set->value_delete_fn = value_delete_fn; + set->data = data; + return set; +} + +/* Delete an arange set. */ + +void +arange_set_delete (arange_set set) +{ + splay_tree_delete (set->ranges); + (*set->deallocate_fn) (set, set->data); +} + +/* Return TRUE if and only if arange set is empty. */ + +bfd_boolean +arange_set_empty_p (arange_set set) +{ + return set->lower_bound > set->upper_bound; +} + +/* Accessors for low and high of an arange. + + There is no arange_set_node_set_low since the low address is the + key of the splay tree node. */ + +/* Get the high VMA address of a node. */ + +static bfd_vma +arange_set_node_high (arange_set set, splay_tree_node node) +{ + arange_value_container_t *container; + + if (set->value_p) + { + container = (arange_value_container_t*) node->value; + return container->high; + } + + return (bfd_vma) node->value; +} + +/* Set the high VMA address of a node. */ + +static void +arange_set_node_set_high (arange_set set, splay_tree_node node, bfd_vma address) +{ + arange_value_container_t *container; + + if (set->value_p) + { + container = (arange_value_container_t*) node->value; + container->high = address; + } + else + node->value = (splay_tree_value) address; +} + +/* Get the low VMA address of a node. */ + +static bfd_vma +arange_set_node_low (splay_tree_node node) +{ + return (bfd_vma) node->key; +} + +/* If arange set supports values, return value of an arange; otheriwse + always return 0 so that it appears that all aranges have the same value. */ + +static arange_value_type +arange_set_node_value (arange_set set, splay_tree_node node) +{ + arange_value_container_t *container; + + if (set->value_p) + { + container = (arange_value_container_t*) node->value; + return container->value; + } + + return 0; +} + +/* If arange set supports values, return value of an arange; otheriwse + always return 0 so that it appears that all aranges have the same value. */ + +static void +arange_set_node_set_value (arange_set set, + splay_tree_node node, + arange_value_type value) +{ + arange_value_container_t *container; + + if (set->value_p) + { + container = (arange_value_container_t*) node->value; + container->value = value; + } +} + +/* Return TRUE if and only if arange set supports values. */ + +bfd_boolean +arange_set_has_values_p (arange_set set) +{ + return set->value_p; +} + +/* Copy a value using the value copying function of an arange set. If + the set does not support values or if there is not value copying + function specified, it simply returns the input value. */ + +arange_value_type +arange_set_copy_value (arange_set set, arange_value_type value) +{ + /* If no copy function is specified or set does not support values, + default is bit-wise copy. */ + if (set->value_p && set->value_copy_fn) + return (set->value_copy_fn) (value, set->data); + + return value; +} + +static arange_value_type +arange_set_combine_value (arange_set set, + arange_value_type value1, + arange_value_type value2) +{ + /* If no combine function is specified or set does not support values, + default is returning 0. */ + if (set->value_p && set->value_combine_fn) + return (set->value_combine_fn) (value1, value2, set->data); + + return (arange_value_type) 0; +} + +/* Compares two values for equality. If the arange set does not support values + or if no value equality function is specified, this function simply does + a bit-wise comparison. */ + +bfd_boolean +arange_set_value_equal_p (arange_set set, + arange_value_type value1, + arange_value_type value2) +{ + /* If no equality function is specified or set does not support values, + default is bit-wise comparison. */ + if (set->value_p && set->value_equal_fn) + return (set->value_equal_fn) (value1, value2, set->data); + + return value1 == value2; +} + +/* Check to see if a given address is in an arange set. Return TRUE if the + address is inside one of the aranges. If low_ptr, high_ptr and value_ptr are + used to return lower address, upper address and value associated with a + found arounge. If anyone of them is NULL, the corresponding information + is not returned. For arange set without values, no information is returned + through the pointer value_ptr. */ + +bfd_boolean +arange_set_lookup_address (arange_set set, bfd_vma address, + bfd_vma *low_ptr, bfd_vma *high_ptr, + arange_value_type *value_ptr) +{ + splay_tree_node pred, node; + + if (address < set->lower_bound || address > set->upper_bound) + return FALSE; + + /* Find immediate predecessor. */ + pred = splay_tree_predecessor (set->ranges, (splay_tree_key) address); + if (pred + && arange_set_node_high (set, pred) >= address) + node = pred; + else + /* If the predecessor range does not cover this address, the address + is in the arange set only if itself starts an arange. */ + node = splay_tree_lookup (set->ranges, (splay_tree_key) address); + + if (node) + { + /* Also return arange boundaries if caller supplies pointers. */ + if (low_ptr) + *low_ptr = arange_set_node_low (node); + if (high_ptr) + *high_ptr = arange_set_node_high (set, node); + if (set->value_p && value_ptr) + *value_ptr = arange_set_node_value (set, node); + return TRUE; + } + + return FALSE; +} + +/* Insert an arange [low, high] into a set's splay tree. If the set supports + value, also insert with the given value. Return the inserted node if there + is no error or NULL otherwise. */ + +static splay_tree_node +arange_set_splay_tree_insert (arange_set set, + bfd_vma low, + bfd_vma high, + arange_value_type value) +{ + splay_tree_value sp_value; + arange_value_container_t *container; + + if (set->value_p) + { + int size = sizeof (arange_value_container_t); + void *data = set->ranges->allocate_data; + + container = + (arange_value_container_t*) (*set->ranges->allocate) (size, data); + if (!container) + return NULL; + container->high = high; + + /* Due to the design of splay tree API, there is no way of passing + callback data to the splay tree value delete function. Hence we need + to store a pointer to set in every containier! */ + container->set = set; + + container->value = value; + sp_value = (splay_tree_value) container; + } + else + sp_value = (splay_tree_value) high; + + /* Currently splay_tree_insert does not return any status to tell if there + is an error. */ + return splay_tree_insert (set->ranges, (splay_tree_key) low, sp_value); +} + +/* Split [low, high] to [low, address) & [address, high]. */ + +static bfd_boolean +arange_set_split_node (arange_set set, splay_tree_node node, bfd_vma address) +{ + splay_tree_node node2; + arange_value_type value; + bfd_vma low, high; + + low = arange_set_node_low (node); + high = arange_set_node_high (set, node); + + BFD_ASSERT (low < address && address <= high); + + value = arange_set_copy_value (set, arange_set_node_value (set, node)); + node2 = arange_set_splay_tree_insert (set, address, high, value); + if (!node2) + return FALSE; + + arange_set_node_set_high (set, node, address - 1); + return TRUE; +} + +static splay_tree_node +arange_set_maybe_merge_with_predecessor (arange_set set, splay_tree_node node) +{ + splay_tree_node pred; + bfd_vma low, high; + + low = arange_set_node_low (node); + high = arange_set_node_high (set, node); + + pred = splay_tree_predecessor (set->ranges, low); + if (! pred) + return node; + + if (arange_set_node_high (set, pred) + 1 == low + && arange_set_value_equal_p (set, + arange_set_node_value (set, pred), + arange_set_node_value (set, node))) + { + splay_tree_remove (set->ranges, arange_set_node_low (node)); + arange_set_node_set_high (set, pred, high); + return arange_set_maybe_merge_with_predecessor (set, pred); + } + + return node; +} + +/* Insert an arange [low,high] into a set. Return TRUE if and only if there + is no error. Note that the address high is also included where as in + DWARF2 an address range between low & high means [low,high). + + This only handles sets with values. For the simpler case of sets without + value, it is handled in arange_set_insert(). This function is + tail-recurive. It is guaranteed to terminate because it only recurses + with a smaller range than it is given. */ + +static bfd_boolean +arange_set_insert_value (arange_set set, + bfd_vma low, + bfd_vma high, + arange_value_type value) +{ + splay_tree_node succ, pred, node; + bfd_vma succ_high, succ_low; + arange_value_type combined, old_value; + + if (low > high) + { + arange_set_delete_value (set, value); + return FALSE; + } + + pred = splay_tree_predecessor (set->ranges, low); + if (pred && arange_set_node_high (set, pred) >= low) + arange_set_split_node (set, pred, low); + + node = splay_tree_lookup (set->ranges, low); + if (node) + { + /* Split node if its arange is larger than inserted arange. */ + if (arange_set_node_high (set, node) > high) + arange_set_split_node (set, node, high + 1); + + old_value = arange_set_node_value (set, node); + combined = arange_set_combine_value (set, old_value, value); + arange_set_node_set_value (set, node, combined); + node = arange_set_maybe_merge_with_predecessor (set, node); + arange_set_delete_value (set, old_value); + + /* Insert remaining arange by tail-recursion. */ + if (high > arange_set_node_high (set, node)) + return arange_set_insert_value (set, + arange_set_node_high (set, node) + 1, + high, value); + else + { + /* Node must cover exactly the range. */ + BFD_ASSERT (high == arange_set_node_high (set, node)); + arange_set_delete_value (set, value); + succ = splay_tree_successor (set->ranges, arange_set_node_low (node)); + if (succ) + succ = arange_set_maybe_merge_with_predecessor (set, succ); + return TRUE; + } + } + + succ = splay_tree_successor (set->ranges, low); + if (succ) + { + succ_low = arange_set_node_low (succ); + succ_high = arange_set_node_high (set, succ); + + if (succ_low <= high) + { + node = arange_set_splay_tree_insert (set, low, succ_low - 1, value); + if (!node) + return FALSE; + + /* Update set lower bound only after insertion is successful. */ + if (low < set->lower_bound) + set->lower_bound = low; + + node = arange_set_maybe_merge_with_predecessor (set, node); + + /* Recurse to handle rest of insertion. Note that we have to copy + value here since it has already been used in the node above. */ + return arange_set_insert_value (set, succ_low, high, + arange_set_copy_value (set, value)); + } + } + + node = arange_set_splay_tree_insert (set, low, high, value); + if (!node) + return FALSE; + + /* Update set boundaries only after insertion is successful. */ + if (low < set->lower_bound) + set->lower_bound = low; + if (high > set->upper_bound) + set->upper_bound = high; + + node = arange_set_maybe_merge_with_predecessor (set, node); + + succ = splay_tree_successor (set->ranges, arange_set_node_low (node)); + if (succ) + succ = arange_set_maybe_merge_with_predecessor (set, succ); + + return TRUE; +} + +bfd_boolean +arange_set_insert (arange_set set, + bfd_vma low, + bfd_vma high, + arange_value_type value) +{ + splay_tree tree = set->ranges; + splay_tree_node pred, succ, node = NULL; + bfd_vma pred_high, node_low; + + if (set->value_p) + return arange_set_insert_value (set, low, high, value); + + if (low > high) + return FALSE; + + pred = splay_tree_predecessor (tree, low); + if (pred) + { + pred_high = arange_set_node_high (set, pred); + + /* Nothing to be done if predecessor contains new aranges. */ + if (pred_high >= high) + return TRUE; + + /* If we can expand predecessor, do so. Test for the case in which + predecessor does not contain new arange but touches it. */ + if (pred_high >= low || pred_high + 1 == low) + { + node = pred; + arange_set_node_set_high (set, node, high); + } + } + + /* Try to see if [low,something] is already in splay tree. */ + if (node == NULL) + { + node = splay_tree_lookup (tree, low); + if (node) + { + /* Nothing to be done if node contains new aranges. */ + if (arange_set_node_high (set, node) >= high) + return TRUE; + + arange_set_node_set_high (set, node, high); + } + } + + if (node == NULL) + { + node = arange_set_splay_tree_insert (set, low, high, 0); + if (!node) + return FALSE; + } + + BFD_ASSERT (node + && arange_set_node_low (node) <= low + && arange_set_node_high (set, node) >= high); + + /* Update set upper and lower bounds. */ + if (low < set->lower_bound) + set->lower_bound = low; + if (high > set->upper_bound) + set->upper_bound = high; + + /* Merge successor if it overlaps or touches node. */ + node_low = arange_set_node_low (node); + while ((succ = splay_tree_successor (tree, node_low)) != NULL + && ((arange_set_node_high (set, node) >= arange_set_node_low (succ)) + || (arange_set_node_high (set, node) + 1 + == arange_set_node_low (succ)))) + { + if (arange_set_node_high (set, succ) > high) + arange_set_node_set_high (set, node, arange_set_node_high (set, succ)); + splay_tree_remove (tree, arange_set_node_low (succ)); + } + return TRUE; +} + +struct arange_set_foreach_adapter_data +{ + void *data; + arange_set set; + arange_set_foreach_fn foreach_fn; +}; + +/* Adaptor to make arange_set_foreach works with splay_tree_foreach. */ + +static int +arange_set_foreach_adapter (splay_tree_node node, void *data) +{ + struct arange_set_foreach_adapter_data *adapter_data; + arange_set set; + + adapter_data = data; + set = adapter_data->set; + return (adapter_data->foreach_fn) (arange_set_node_low (node), + arange_set_node_high (set, node), + arange_set_node_value (set, node), + adapter_data->data); +} + +/* 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. */ + +int +arange_set_foreach (arange_set set, + arange_set_foreach_fn foreach_fn, + void *data) +{ + struct arange_set_foreach_adapter_data adapter_data; + + adapter_data.data = data; + adapter_data.foreach_fn = foreach_fn; + adapter_data.set = set; + return splay_tree_foreach (set->ranges, arange_set_foreach_adapter, + (void *) &adapter_data); +} |