Support bitmap_copy across representations
Commit Message
The following started as making the backward threader m_imports
use the tree representation. Since that interfaces to a list
representation bitmap in ranger by copying rewriting the tree
to list to perform the copy is inefficient in that it loses
balancing. The following adds bitmap_copy_tree_to_list and
integrates it with the generic bitmap_copy routine. For symmetry
I also added list to tree copy, relying on auto-balancing, and
tree to tree copy which I didn't optimize to preserve the
source balancing but instead use bitmap_copy_tree_to_list and
have the result auto-balanced again.
I've only exercised the tree to list path and I won't actually
end up using it but it's at least worth posting.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Worth pushing?
* bitmap.h: Document set_copy aka bitmap_copy as usable
for tree representation.
* bitmap.cc (bitmap_copy_tree_to_list): New helper.
(bitmap_copy): Support copying all bitmap representation
combinations.
---
gcc/bitmap.cc | 78 +++++++++++++++++++++++++++++++++++++++++++++++++--
gcc/bitmap.h | 6 +++-
2 files changed, 81 insertions(+), 3 deletions(-)
@@ -847,6 +847,58 @@ bitmap_element_zerop (const bitmap_element *element)
#endif
}
+/* Copy bitmap FROM which is in tree form to bitmap TO in list form. */
+
+static void
+bitmap_copy_tree_to_list (bitmap to, const_bitmap from)
+{
+ bitmap_element *to_ptr = nullptr;
+
+ gcc_checking_assert (!to->tree_form && from->tree_form);
+
+ /* Do like bitmap_tree_to_vec but populate the destination bitmap
+ instead of a vector. */
+ auto_vec<bitmap_element *, 32> stack;
+ bitmap_element *e = from->first;
+ while (true)
+ {
+ while (e != NULL)
+ {
+ stack.safe_push (e);
+ e = e->prev;
+ }
+ if (stack.is_empty ())
+ break;
+
+ bitmap_element *from_ptr = stack.pop ();
+ {
+ bitmap_element *to_elt = bitmap_element_allocate (to);
+
+ to_elt->indx = from_ptr->indx;
+ memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
+
+ /* Here we have a special case of bitmap_list_link_element,
+ for the case where we know the links are being entered
+ in sequence. */
+ if (to_ptr == nullptr)
+ {
+ to->first = to->current = to_elt;
+ to->indx = from_ptr->indx;
+ to_elt->next = to_elt->prev = nullptr;
+ }
+ else
+ {
+ to_elt->prev = to_ptr;
+ to_elt->next = nullptr;
+ to_ptr->next = to_elt;
+ }
+
+ to_ptr = to_elt;
+ }
+ e = from_ptr->next;
+ }
+}
+
/* Copy a bitmap to another bitmap. */
void
@@ -854,11 +906,29 @@ bitmap_copy (bitmap to, const_bitmap from)
{
const bitmap_element *from_ptr;
bitmap_element *to_ptr = 0;
-
- gcc_checking_assert (!to->tree_form && !from->tree_form);
+ bool to_tree = to->tree_form;
bitmap_clear (to);
+ /* From tree form first copy to list form, avoiding debalancing from,
+ then if the result is in tree form have it rebalance itself. */
+ if (from->tree_form)
+ {
+ if (to_tree)
+ bitmap_list_view (to);
+ bitmap_copy_tree_to_list (to, from);
+ if (to_tree)
+ bitmap_tree_view (to);
+ return;
+ }
+
+ /* We are copying from list form - first copy the list representation
+ so temporarily switch the destination to list form. */
+ if (to_tree)
+ bitmap_list_view (to);
+
+ gcc_checking_assert (!to->tree_form && !from->tree_form);
+
/* Copy elements in forward direction one at a time. */
for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
{
@@ -885,6 +955,10 @@ bitmap_copy (bitmap to, const_bitmap from)
to_ptr = to_elt;
}
+
+ /* To tree, result will balance itself. */
+ if (to_tree)
+ bitmap_tree_view (to);
}
/* Move a bitmap to another bitmap. */
@@ -139,11 +139,15 @@ along with GCC; see the file COPYING3. If not see
* add_member
* remove_member
+ Additionally both representations support enumeration of the
+ members in O(E) time for the following operations:
+
+ * set_copy : bitmap_copy
+
Additionally, the linked-list sparse set representation supports
enumeration of the members in O(E) time:
* forall : EXECUTE_IF_SET_IN_BITMAP
- * set_copy : bitmap_copy
* set_intersection : bitmap_intersect_p /
bitmap_and / bitmap_and_into /
EXECUTE_IF_AND_IN_BITMAP