diff options
Diffstat (limited to 'thirdparty/harfbuzz/src/graph/graph.hh')
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/graph.hh | 215 |
1 files changed, 156 insertions, 59 deletions
diff --git a/thirdparty/harfbuzz/src/graph/graph.hh b/thirdparty/harfbuzz/src/graph/graph.hh index 53d0bc94e1..0680958190 100644 --- a/thirdparty/harfbuzz/src/graph/graph.hh +++ b/thirdparty/harfbuzz/src/graph/graph.hh @@ -43,12 +43,28 @@ struct graph_t { hb_serialize_context_t::object_t obj; int64_t distance = 0 ; - int64_t space = 0 ; - hb_vector_t<unsigned> parents; + unsigned space = 0 ; unsigned start = 0; unsigned end = 0; unsigned priority = 0; - + private: + unsigned incoming_edges_ = 0; + unsigned single_parent = (unsigned) -1; + hb_hashmap_t<unsigned, unsigned> parents; + public: + + auto parents_iter () const HB_AUTO_RETURN + ( + hb_concat ( + hb_iter (&single_parent, single_parent != (unsigned) -1), + parents.keys_ref () + ) + ) + + bool in_error () const + { + return parents.in_error (); + } bool link_positions_valid (unsigned num_objects, bool removed_nil) { @@ -143,7 +159,9 @@ struct graph_t hb_swap (a.obj, b.obj); hb_swap (a.distance, b.distance); hb_swap (a.space, b.space); + hb_swap (a.single_parent, b.single_parent); hb_swap (a.parents, b.parents); + hb_swap (a.incoming_edges_, b.incoming_edges_); hb_swap (a.start, b.start); hb_swap (a.end, b.end); hb_swap (a.priority, b.priority); @@ -154,6 +172,7 @@ struct graph_t { hb_hashmap_t<unsigned, unsigned> result; + result.alloc (obj.real_links.length); for (const auto& l : obj.real_links) { result.set (l.position, l.objidx); } @@ -163,22 +182,76 @@ struct graph_t bool is_shared () const { - return parents.length > 1; + return parents.get_population () > 1; } unsigned incoming_edges () const { - return parents.length; + if (HB_DEBUG_SUBSET_REPACK) + { + assert (incoming_edges_ == (single_parent != (unsigned) -1) + + (parents.values_ref () | hb_reduce (hb_add, 0))); + } + return incoming_edges_; + } + + void reset_parents () + { + incoming_edges_ = 0; + single_parent = (unsigned) -1; + parents.reset (); + } + + void add_parent (unsigned parent_index) + { + assert (parent_index != (unsigned) -1); + if (incoming_edges_ == 0) + { + single_parent = parent_index; + incoming_edges_ = 1; + return; + } + else if (single_parent != (unsigned) -1) + { + assert (incoming_edges_ == 1); + if (!parents.set (single_parent, 1)) + return; + single_parent = (unsigned) -1; + } + + unsigned *v; + if (parents.has (parent_index, &v)) + { + (*v)++; + incoming_edges_++; + } + else if (parents.set (parent_index, 1)) + incoming_edges_++; } void remove_parent (unsigned parent_index) { - unsigned count = parents.length; - for (unsigned i = 0; i < count; i++) + if (parent_index == single_parent) { - if (parents.arrayZ[i] != parent_index) continue; - parents.remove_unordered (i); - break; + single_parent = (unsigned) -1; + incoming_edges_--; + return; + } + + unsigned *v; + if (parents.has (parent_index, &v)) + { + incoming_edges_--; + if (*v > 1) + (*v)--; + else + parents.del (parent_index); + + if (incoming_edges_ == 1) + { + single_parent = *parents.keys (); + parents.reset (); + } } } @@ -199,20 +272,46 @@ struct graph_t } } - void remap_parents (const hb_vector_t<unsigned>& id_map) + bool remap_parents (const hb_vector_t<unsigned>& id_map) { - unsigned count = parents.length; - for (unsigned i = 0; i < count; i++) - parents.arrayZ[i] = id_map[parents.arrayZ[i]]; + if (single_parent != (unsigned) -1) + { + assert (single_parent < id_map.length); + single_parent = id_map[single_parent]; + return true; + } + + hb_hashmap_t<unsigned, unsigned> new_parents; + new_parents.alloc (parents.get_population ()); + for (auto _ : parents) + { + assert (_.first < id_map.length); + assert (!new_parents.has (id_map[_.first])); + new_parents.set (id_map[_.first], _.second); + } + + if (new_parents.in_error ()) + return false; + + parents = std::move (new_parents); + return true; } void remap_parent (unsigned old_index, unsigned new_index) { - unsigned count = parents.length; - for (unsigned i = 0; i < count; i++) + if (single_parent != (unsigned) -1) + { + if (single_parent == old_index) + single_parent = new_index; + return; + } + + const unsigned *pv; + if (parents.has (old_index, &pv)) { - if (parents.arrayZ[i] == old_index) - parents.arrayZ[i] = new_index; + unsigned v = *pv; + parents.set (new_index, v); + parents.del (old_index); } } @@ -419,7 +518,7 @@ struct graph_t link->width = 2; link->objidx = child_id; link->position = (char*) offset - (char*) v.obj.head; - vertices_[child_id].parents.push (parent_id); + vertices_[child_id].add_parent (parent_id); } /* @@ -465,7 +564,7 @@ struct graph_t { unsigned next_id = queue.pop_minimum().second; - hb_swap (sorted_graph[new_id], vertices_[next_id]); + sorted_graph[new_id] = std::move (vertices_[next_id]); const vertex_t& next = sorted_graph[new_id]; if (unlikely (!check_success(new_id >= 0))) { @@ -493,8 +592,8 @@ struct graph_t check_success (!queue.in_error ()); check_success (!sorted_graph.in_error ()); - remap_all_obj_indices (id_map, &sorted_graph); - hb_swap (vertices_, sorted_graph); + check_success (remap_all_obj_indices (id_map, &sorted_graph)); + vertices_ = std::move (sorted_graph); if (!check_success (new_id == -1)) print_orphaned_nodes (); @@ -605,7 +704,7 @@ struct graph_t { unsigned child_idx = index_for_offset (node_idx, offset); auto& child = vertices_[child_idx]; - for (unsigned p : child.parents) + for (unsigned p : child.parents_iter ()) { if (p != node_idx) { return duplicate (node_idx, child_idx); @@ -688,12 +787,15 @@ struct graph_t subgraph.set (root_idx, wide_parents (root_idx, parents)); find_subgraph (root_idx, subgraph); } + if (subgraph.in_error ()) + return false; unsigned original_root_idx = root_idx (); hb_map_t index_map; bool made_changes = false; for (auto entry : subgraph.iter ()) { + assert (entry.first < vertices_.length); const auto& node = vertices_[entry.first]; unsigned subgraph_incoming_edges = entry.second; @@ -749,10 +851,10 @@ struct graph_t { for (const auto& link : vertices_[node_idx].obj.all_links ()) { - const uint32_t *v; + hb_codepoint_t *v; if (subgraph.has (link.objidx, &v)) { - subgraph.set (link.objidx, *v + 1); + (*v)++; continue; } subgraph.set (link.objidx, 1); @@ -824,7 +926,7 @@ struct graph_t new_link->position = (const char*) new_offset - (const char*) new_v.obj.head; auto& child = vertices_[child_id]; - child.parents.push (new_parent_idx); + child.add_parent (new_parent_idx); old_v.remove_real_link (child_id, old_offset); child.remove_parent (old_parent_idx); @@ -868,18 +970,18 @@ struct graph_t clone->obj.tail = child.obj.tail; clone->distance = child.distance; clone->space = child.space; - clone->parents.reset (); + clone->reset_parents (); unsigned clone_idx = vertices_.length - 2; for (const auto& l : child.obj.real_links) { clone->obj.real_links.push (l); - vertices_[l.objidx].parents.push (clone_idx); + vertices_[l.objidx].add_parent (clone_idx); } for (const auto& l : child.obj.virtual_links) { clone->obj.virtual_links.push (l); - vertices_[l.objidx].parents.push (clone_idx); + vertices_[l.objidx].add_parent (clone_idx); } check_success (!clone->obj.real_links.in_error ()); @@ -1008,13 +1110,13 @@ struct graph_t { update_parents(); - if (root().parents) + if (root().incoming_edges ()) // Root cannot have parents. return false; for (unsigned i = 0; i < root_idx (); i++) { - if (!vertices_[i].parents) + if (!vertices_[i].incoming_edges ()) return false; } return true; @@ -1078,14 +1180,14 @@ struct graph_t parents_invalid = true; update_parents(); - if (root().parents) { + if (root().incoming_edges ()) { DEBUG_MSG (SUBSET_REPACK, nullptr, "Root node has incoming edges."); } for (unsigned i = 0; i < root_idx (); i++) { const auto& v = vertices_[i]; - if (!v.parents) + if (!v.incoming_edges ()) DEBUG_MSG (SUBSET_REPACK, nullptr, "Node %u is orphaned.", i); } } @@ -1117,6 +1219,8 @@ struct graph_t unsigned space_for (unsigned index, unsigned* root = nullptr) const { + loop: + assert (index < vertices_.length); const auto& node = vertices_[index]; if (node.space) { @@ -1125,14 +1229,15 @@ struct graph_t return node.space; } - if (!node.parents) + if (!node.incoming_edges ()) { if (root) *root = index; return 0; } - return space_for (node.parents[0], root); + index = *node.parents_iter (); + goto loop; } void err_other_error () { this->successful = false; } @@ -1156,12 +1261,8 @@ struct graph_t unsigned wide_parents (unsigned node_idx, hb_set_t& parents) const { unsigned count = 0; - hb_set_t visited; - for (unsigned p : vertices_[node_idx].parents) + for (unsigned p : vertices_[node_idx].parents_iter ()) { - if (visited.has (p)) continue; - visited.add (p); - // Only real links can be wide for (const auto& l : vertices_[p].obj.real_links) { @@ -1191,20 +1292,18 @@ struct graph_t unsigned count = vertices_.length; for (unsigned i = 0; i < count; i++) - vertices_.arrayZ[i].parents.reset (); + vertices_.arrayZ[i].reset_parents (); for (unsigned p = 0; p < count; p++) { for (auto& l : vertices_.arrayZ[p].obj.all_links ()) - { - vertices_[l.objidx].parents.push (p); - } + vertices_[l.objidx].add_parent (p); } for (unsigned i = 0; i < count; i++) // parents arrays must be accurate or downstream operations like cycle detection // and sorting won't work correctly. - check_success (!vertices_.arrayZ[i].parents.in_error ()); + check_success (!vertices_.arrayZ[i].in_error ()); parents_invalid = false; } @@ -1248,12 +1347,8 @@ struct graph_t // (such as a fibonacci queue) with a fast decrease priority. unsigned count = vertices_.length; for (unsigned i = 0; i < count; i++) - { - if (i == vertices_.length - 1) - vertices_.arrayZ[i].distance = 0; - else - vertices_.arrayZ[i].distance = hb_int_max (int64_t); - } + vertices_.arrayZ[i].distance = hb_int_max (int64_t); + vertices_.tail ().distance = 0; hb_priority_queue_t queue; queue.insert (0, vertices_.length - 1); @@ -1273,15 +1368,15 @@ struct graph_t { if (visited[link.objidx]) continue; - const auto& child = vertices_[link.objidx].obj; + const auto& child = vertices_.arrayZ[link.objidx].obj; unsigned link_width = link.width ? link.width : 4; // treat virtual offsets as 32 bits wide int64_t child_weight = (child.tail - child.head) + - ((int64_t) 1 << (link_width * 8)) * (vertices_[link.objidx].space + 1); + ((int64_t) 1 << (link_width * 8)) * (vertices_.arrayZ[link.objidx].space + 1); int64_t child_distance = next_distance + child_weight; - if (child_distance < vertices_[link.objidx].distance) + if (child_distance < vertices_.arrayZ[link.objidx].distance) { - vertices_[link.objidx].distance = child_distance; + vertices_.arrayZ[link.objidx].distance = child_distance; queue.insert (child_distance, link.objidx); } } @@ -1309,7 +1404,7 @@ struct graph_t unsigned old_idx = link.objidx; link.objidx = new_idx; vertices_[old_idx].remove_parent (parent_idx); - vertices_[new_idx].parents.push (parent_idx); + vertices_[new_idx].add_parent (parent_idx); } /* @@ -1337,18 +1432,20 @@ struct graph_t /* * Updates all objidx's in all links using the provided mapping. */ - void remap_all_obj_indices (const hb_vector_t<unsigned>& id_map, + bool remap_all_obj_indices (const hb_vector_t<unsigned>& id_map, hb_vector_t<vertex_t>* sorted_graph) const { unsigned count = sorted_graph->length; for (unsigned i = 0; i < count; i++) { - (*sorted_graph)[i].remap_parents (id_map); + if (!(*sorted_graph)[i].remap_parents (id_map)) + return false; for (auto& link : sorted_graph->arrayZ[i].obj.all_links_writer ()) { link.objidx = id_map[link.objidx]; } } + return true; } /* @@ -1379,7 +1476,7 @@ struct graph_t for (const auto& l : v.obj.all_links ()) find_connected_nodes (l.objidx, targets, visited, connected); - for (unsigned p : v.parents) + for (unsigned p : v.parents_iter ()) find_connected_nodes (p, targets, visited, connected); } |