27 #ifndef HB_REPACKER_HH
28 #define HB_REPACKER_HH
66 if (
parents[
i] != parent_index)
continue;
89 return !
obj.real_links.length && !
obj.virtual_links.length;
120 int64_t table_size =
obj.tail -
obj.head;
123 return -table_size / 2;
144 : parents_invalid (
true),
145 distance_invalid (
true),
146 positions_invalid (
true),
149 num_roots_for_space_.
push (1);
150 bool removed_nil =
false;
151 for (
unsigned i = 0;
i < objects.length;
i++)
157 if (
i == 0 && !objects[
i])
164 if (check_success (!
vertices_.in_error ()))
165 v->obj = *objects[
i];
166 if (!removed_nil)
continue;
168 for (
auto&
l :
v->obj.all_links_writer ()) {
181 return !successful ||
210 size_t size = serialized_length ();
212 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Unable to allocate output buffer.");
217 c.start_serialize<
void> ();
224 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Buffer out of space.");
232 serialize_link (link,
start, &
c);
241 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Error during serialization. Err flag: %d",
246 return c.copy_blob ();
255 positions_invalid =
true;
277 unsigned next_id =
queue[0];
281 sorted_graph[new_id] =
next;
282 id_map[next_id] = new_id--;
284 for (
const auto& link :
next.obj.all_links ()) {
285 removed_edges[link.objidx]++;
286 if (!(
vertices_[link.objidx].incoming_edges () - removed_edges[link.objidx]))
287 queue.push (link.objidx);
291 check_success (!
queue.in_error ());
292 check_success (!sorted_graph.
in_error ());
293 if (!check_success (new_id == -1))
296 remap_all_obj_indices (id_map, &sorted_graph);
299 sorted_graph.
fini ();
308 positions_invalid =
true;
330 while (!
queue.in_error () && !
queue.is_empty ())
332 unsigned next_id =
queue.pop_minimum().second;
335 sorted_graph[new_id] =
next;
336 id_map[next_id] = new_id--;
338 for (
const auto& link :
next.obj.all_links ()) {
339 removed_edges[link.objidx]++;
340 if (!(
vertices_[link.objidx].incoming_edges () - removed_edges[link.objidx]))
351 check_success (!
queue.in_error ());
352 check_success (!sorted_graph.
in_error ());
353 if (!check_success (new_id == -1))
356 remap_all_obj_indices (id_map, &sorted_graph);
359 sorted_graph.
fini ();
370 for (
unsigned i = 0;
i <= root_index;
i++)
375 if (
l.width == 4 && !
l.is_signed)
377 roots.
add (
l.objidx);
387 if (!roots)
return false;
396 find_connected_nodes (
next, roots, visited, connected_roots);
403 num_roots_for_space_.
push (0);
404 for (
unsigned root : connected_roots)
409 distance_invalid =
true;
410 positions_invalid =
true;
443 unsigned original_root_idx =
root_idx ();
445 bool made_changes =
false;
449 unsigned subgraph_incoming_edges =
entry.second;
451 if (subgraph_incoming_edges <
node.incoming_edges ())
462 if (original_root_idx !=
root_idx ()
463 && parents.
has (original_root_idx))
467 parents.
del (original_root_idx);
472 |
hb_map([&] (
unsigned node_idx) {
473 if (index_map.
has (node_idx))
return index_map[node_idx];
478 remap_obj_indices (index_map, new_subgraph);
479 remap_obj_indices (index_map, parents.
iter (),
true);
497 for (
const auto& link :
vertices_[node_idx].
obj.all_links ())
499 if (subgraph.
has (link.objidx))
501 subgraph.
set (link.objidx, subgraph[link.objidx] + 1);
504 subgraph.
set (link.objidx, 1);
511 if (subgraph.
has (node_idx))
return;
512 subgraph.
add (node_idx);
513 for (
const auto& link :
vertices_[node_idx].
obj.all_links ())
524 if (index_map.
has (node_idx))
528 for (
const auto&
l :
object (node_idx).all_links ()) {
538 positions_invalid =
true;
539 distance_invalid =
true;
547 clone->obj.head =
child.obj.head;
548 clone->obj.tail =
child.obj.tail;
549 clone->distance =
child.distance;
550 clone->space =
child.space;
551 clone->parents.reset ();
553 unsigned clone_idx =
vertices_.length - 2;
554 for (
const auto&
l :
child.obj.real_links)
556 clone->obj.real_links.push (
l);
559 for (
const auto&
l :
child.obj.virtual_links)
561 clone->obj.virtual_links.push (
l);
565 check_success (!clone->obj.real_links.in_error ());
566 check_success (!clone->obj.virtual_links.in_error ());
587 bool duplicate (
unsigned parent_idx,
unsigned child_idx)
591 unsigned links_to_child = 0;
594 if (
l.objidx == child_idx) links_to_child++;
597 if (
vertices_[child_idx].incoming_edges () <= links_to_child)
601 DEBUG_MSG (SUBSET_REPACK,
nullptr,
" Not duplicating %d => %d",
602 parent_idx, child_idx);
606 DEBUG_MSG (SUBSET_REPACK,
nullptr,
" Duplicating %d => %d",
607 parent_idx, child_idx);
609 unsigned clone_idx =
duplicate (child_idx);
610 if (clone_idx == (
unsigned) -1)
return false;
612 if (parent_idx == clone_idx) parent_idx++;
615 for (
auto&
l :
parent.obj.all_links_writer ())
617 if (
l.objidx != child_idx)
620 reassign_link (
l, parent_idx, clone_idx);
631 DEBUG_MSG (SUBSET_REPACK,
nullptr,
" Raising priority of all children of %d",
637 bool made_change =
false;
638 for (
auto&
l :
parent.all_links_writer ())
639 made_change |=
vertices_[
l.objidx].raise_priority ();
648 if (overflows) overflows->resize (0);
651 for (
int parent_idx =
vertices_.length - 1; parent_idx >= 0; parent_idx--)
654 for (
const auto& link :
vertices_[parent_idx].
obj.real_links)
656 int64_t
offset = compute_offset (parent_idx, link);
657 if (is_valid_offset (
offset, link))
660 if (!overflows)
return true;
663 r.parent = parent_idx;
664 r.child = link.objidx;
669 if (!overflows)
return false;
670 return overflows->length;
677 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Graph is not fully connected.");
678 parents_invalid =
true;
685 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Node %u is orphaned.",
i);
695 for (
const auto&
o : overflows)
702 "%4d (%4d in, %4d out, space %2d) => "
703 "%4d (%4d in, %4d out, space %2d)",
706 parent.obj.real_links.length +
parent.obj.virtual_links.length,
709 child.incoming_edges (),
710 child.obj.real_links.length +
child.obj.virtual_links.length,
713 if (overflows.
length > 10) {
714 DEBUG_MSG (SUBSET_REPACK,
nullptr,
" ... plus %d more overflows.", overflows.
length - 10);
720 return num_roots_for_space_[space];
725 return num_roots_for_space_.
length;
730 num_roots_for_space_.
push (0);
731 unsigned new_space = num_roots_for_space_.
length - 1;
735 num_roots_for_space_[
node.space] = num_roots_for_space_[
node.space] - 1;
736 num_roots_for_space_[new_space] = num_roots_for_space_[new_space] + 1;
737 node.space = new_space;
738 distance_invalid =
true;
739 positions_invalid =
true;
767 size_t serialized_length ()
const {
768 size_t total_size = 0;
779 unsigned wide_parents (
unsigned node_idx,
hb_set_t& parents)
const
783 for (
unsigned p :
vertices_[node_idx].parents)
785 if (visited.
has (
p))
continue;
791 if (
l.objidx == node_idx &&
l.width == 4 && !
l.is_signed)
801 bool check_success (
bool success)
802 {
return this->successful && (success || (
err_other_error (),
false)); }
807 void update_parents ()
809 if (!parents_invalid)
return;
822 parents_invalid =
false;
828 void update_positions ()
830 if (!positions_invalid)
return;
832 unsigned current_pos = 0;
836 v.start = current_pos;
837 current_pos +=
v.obj.tail -
v.obj.head;
841 positions_invalid =
false;
848 void update_distances ()
850 if (!distance_invalid)
return;
876 while (!
queue.in_error () && !
queue.is_empty ())
878 unsigned next_idx =
queue.pop_minimum ().second;
879 if (visited[next_idx])
continue;
881 int64_t next_distance =
vertices_[next_idx].distance;
882 visited[next_idx] =
true;
884 for (
const auto& link :
next.obj.all_links ())
886 if (visited[link.objidx])
continue;
889 unsigned link_width = link.width ? link.width : 4;
890 int64_t child_weight = (
child.tail -
child.head) +
891 ((int64_t) 1 << (link_width * 8)) * (
vertices_[link.objidx].space + 1);
892 int64_t child_distance = next_distance + child_weight;
894 if (child_distance <
vertices_[link.objidx].distance)
896 vertices_[link.objidx].distance = child_distance;
897 queue.insert (child_distance, link.objidx);
902 check_success (!
queue.in_error ());
903 if (!check_success (
queue.is_empty ()))
909 distance_invalid =
false;
912 int64_t compute_offset (
920 case hb_serialize_context_t::whence_t::Head:
922 case hb_serialize_context_t::whence_t::Tail:
924 case hb_serialize_context_t::whence_t::Absolute:
933 bool is_valid_offset (int64_t
offset,
943 return offset >= -((int64_t) 1 << 31) &&
offset < ((int64_t) 1 << 31);
951 else if (link.
width == 3)
966 unsigned old_idx = link.
objidx;
968 vertices_[old_idx].remove_parent (parent_idx);
969 vertices_[new_idx].parents.push (parent_idx);
975 template<
typename Iterator, hb_requires (hb_is_iterator (Iterator))>
978 bool only_wide =
false)
981 for (
unsigned i : subgraph)
988 reassign_link (link,
i, id_map[link.
objidx]);
999 for (
unsigned i = 0;
i < sorted_graph->
length;
i++)
1001 (*sorted_graph)[
i].remap_parents (id_map);
1002 for (
auto& link : (*sorted_graph)[
i].
obj.all_links_writer ())
1009 template <
typename O>
void
1036 serialize_link_of_type<OT::HBINT32> (link, head,
c);
1038 serialize_link_of_type<OT::HBUINT32> (link, head,
c);
1044 serialize_link_of_type<OT::HBINT16> (link, head,
c);
1046 serialize_link_of_type<OT::HBUINT16> (link, head,
c);
1050 serialize_link_of_type<OT::HBUINT24> (link, head,
c);
1065 void find_connected_nodes (
unsigned start_idx,
1071 if (visited.
has (start_idx))
return;
1072 visited.
add (start_idx);
1074 if (targets.
has (start_idx))
1076 targets.
del (start_idx);
1077 connected.
add (start_idx);
1083 for (
const auto&
l :
v.obj.all_links ())
1084 find_connected_nodes (
l.objidx, targets, visited, connected);
1086 for (
unsigned p :
v.parents)
1087 find_connected_nodes (
p, targets, visited, connected);
1094 bool parents_invalid;
1095 bool distance_invalid;
1096 bool positions_invalid;
1108 for (
int i = overflows.
length - 1;
i >= 0;
i--)
1113 unsigned overflow_space = sorted_graph.
space_for (
r.parent, &root);
1114 if (!overflow_space)
continue;
1118 space = overflow_space;
1121 if (space == overflow_space)
1122 roots_to_isolate.
add(root);
1125 if (!roots_to_isolate)
return false;
1130 unsigned extra = roots_to_isolate.
get_population () - maximum_to_move;
1134 roots_to_isolate.
del (root);
1139 "Overflow in space %d (%d roots). Moving %d roots to space %d.",
1156 bool resolution_attempted =
false;
1159 for (
int i = overflows.
length - 1;
i >= 0;
i--)
1163 if (
child.is_shared ())
1167 if (!sorted_graph.
duplicate (
r.parent,
r.child))
continue;
1171 if (
child.is_leaf () && !priority_bumped_parents.
has (
r.parent))
1185 priority_bumped_parents.
add (
r.parent);
1186 resolution_attempted =
true;
1196 return resolution_attempted;
1212 template<
typename T>
1216 unsigned max_rounds = 20) {
1232 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Assigning spaces to 32 bit subgraphs.");
1242 && round++ < max_rounds) {
1243 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"=== Overflow resolution round %d ===", round);
1248 if (!_try_isolating_subgraphs (overflows, sorted_graph))
1250 if (!_process_overflows (overflows, priority_bumped_parents, sorted_graph))
1252 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"No resolution available :(");
1262 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Sorted graph in error state.");
1268 DEBUG_MSG (SUBSET_REPACK,
nullptr,
"Offset overflow resolution failed.");
small capitals from c petite p scientific i
[1]
#define DEBUG_MSG(WHAT, OBJ,...)
#define DEBUG_ENABLED(WHAT)
auto it hb_map(hb_second)) template< typename Type > inline hb_array_t< Type > operator()(hb_array_t< Type > array
HB_EXTERN hb_tag_t table_tag
hb_blob_t * hb_resolve_overflows(const T &packed, hb_tag_t table_tag, unsigned max_rounds=20)
GLsizei const GLfloat * v
[13]
GLenum GLuint GLintptr GLsizeiptr size
[1]
GLenum GLenum GLsizei count
GLsizei GLsizei GLfloat distance
GLenum GLuint GLintptr offset
GLsizei GLenum const void * indices
GLfixed GLfixed GLint GLint order
GLuint GLenum GLsizei GLsizei GLint GLint GLboolean packed
#define HB_SET_VALUE_INVALID
int64_t modified_distance(unsigned order) const
bool has_max_priority() const
int64_t distance_modifier() const
void remap_parents(const hb_vector_t< unsigned > &id_map)
void remove_parent(unsigned parent_index)
hb_vector_t< unsigned > parents
hb_serialize_context_t::object_t obj
void remap_parent(unsigned old_index, unsigned new_index)
unsigned incoming_edges() const
void print_orphaned_nodes()
bool will_overflow(hb_vector_t< overflow_record_t > *overflows=nullptr)
graph_t(const T &objects)
unsigned num_roots_for_space(unsigned space) const
void move_to_new_space(const hb_set_t &indices)
void duplicate_subgraph(unsigned node_idx, hb_hashmap_t< unsigned, unsigned > &index_map)
void sort_shortest_distance()
unsigned space_for(unsigned index, unsigned *root=nullptr) const
unsigned next_space() const
void find_subgraph(unsigned node_idx, hb_hashmap_t< unsigned, unsigned > &subgraph)
const vertex_t & root() const
hb_blob_t * serialize() const
bool isolate_subgraph(hb_set_t &roots)
unsigned duplicate(unsigned node_idx)
bool duplicate(unsigned parent_idx, unsigned child_idx)
bool raise_childrens_priority(unsigned parent_idx)
unsigned root_idx() const
bool assign_32bit_spaces()
void print_overflows(const hb_vector_t< overflow_record_t > &overflows)
const hb_serialize_context_t::object_t & object(unsigned i) const
void find_subgraph(unsigned node_idx, hb_set_t &subgraph)
hb_vector_t< vertex_t > vertices_
auto iter() const HB_AUTO_RETURN(+hb_array(items
bool set(K key, const V &value)
bool has(K k, V *vp=nullptr) const
auto all_links() const HB_AUTO_RETURN((hb_concat(this -> real_links, this->virtual_links)))
bool previous(hb_codepoint_t *codepoint) const
bool next(hb_codepoint_t *codepoint) const
bool has(hb_codepoint_t k) const
unsigned int get_population() const
void del(hb_codepoint_t g)
void add(hb_codepoint_t g)
void remove(unsigned int i)
IUIAutomationTreeWalker __RPC__deref_out_opt IUIAutomationElement ** parent