diff options
Diffstat (limited to 'src/3rdparty/harfbuzz-ng/src/graph/graph.hh')
| -rw-r--r-- | src/3rdparty/harfbuzz-ng/src/graph/graph.hh | 379 |
1 files changed, 294 insertions, 85 deletions
diff --git a/src/3rdparty/harfbuzz-ng/src/graph/graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/graph.hh index 38ca5db096..2a9d8346c0 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/graph.hh +++ b/src/3rdparty/harfbuzz-ng/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,27 +182,92 @@ 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_; + } + + unsigned incoming_edges_from_parent (unsigned parent_index) const { + if (single_parent != (unsigned) -1) { + return single_parent == parent_index ? 1 : 0; + } + + unsigned* count; + return parents.has(parent_index, &count) ? *count : 0; + } + + 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) { - for (unsigned i = 0; i < parents.length; i++) + if (parent_index == single_parent) { - if (parents[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 (); + } } } void remove_real_link (unsigned child_index, const void* offset) { - for (unsigned i = 0; i < obj.real_links.length; i++) + unsigned count = obj.real_links.length; + for (unsigned i = 0; i < count; i++) { auto& link = obj.real_links.arrayZ[i]; if (link.objidx != child_index) @@ -197,18 +281,53 @@ struct graph_t } } - void remap_parents (const hb_vector_t<unsigned>& id_map) + bool remap_parents (const hb_vector_t<unsigned>& id_map) { - for (unsigned i = 0; i < parents.length; i++) - parents[i] = id_map[parents[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 (parents.in_error() || new_parents.in_error ()) + return false; + + parents = std::move (new_parents); + return true; } void remap_parent (unsigned old_index, unsigned new_index) { - for (unsigned i = 0; i < parents.length; i++) + if (single_parent != (unsigned) -1) { - if (parents[i] == old_index) - parents[i] = new_index; + if (single_parent == old_index) + single_parent = new_index; + return; + } + + const unsigned *pv; + if (parents.has (old_index, &pv)) + { + unsigned v = *pv; + if (!parents.set (new_index, v)) + incoming_edges_ -= v; + parents.del (old_index); + + if (incoming_edges_ == 1) + { + single_parent = *parents.keys (); + parents.reset (); + } } } @@ -224,6 +343,16 @@ struct graph_t return true; } + bool give_max_priority () + { + bool result = false; + while (!has_max_priority()) { + result = true; + priority++; + } + return result; + } + bool has_max_priority () const { return priority >= 3; } @@ -328,11 +457,12 @@ struct graph_t bool removed_nil = false; vertices_.alloc (objects.length); vertices_scratch_.alloc (objects.length); - for (unsigned i = 0; i < objects.length; i++) + unsigned count = objects.length; + for (unsigned i = 0; i < count; i++) { // If this graph came from a serialization buffer object 0 is the // nil object. We don't need it for our purposes here so drop it. - if (i == 0 && !objects[i]) + if (i == 0 && !objects.arrayZ[i]) { removed_nil = true; continue; @@ -340,9 +470,9 @@ struct graph_t vertex_t* v = vertices_.push (); if (check_success (!vertices_.in_error ())) - v->obj = *objects[i]; + v->obj = *objects.arrayZ[i]; - check_success (v->link_positions_valid (objects.length, removed_nil)); + check_success (v->link_positions_valid (count, removed_nil)); if (!removed_nil) continue; // Fix indices to account for removed nil object. @@ -354,7 +484,6 @@ struct graph_t ~graph_t () { - vertices_.fini (); for (char* b : buffers) hb_free (b); } @@ -364,6 +493,18 @@ struct graph_t return root ().equals (other.root (), *this, other, 0); } + void print () const { + for (int i = vertices_.length - 1; i >= 0; i--) + { + const auto& v = vertices_[i]; + printf("%d: %u [", i, (unsigned int)v.table_size()); + for (const auto &l : v.obj.real_links) { + printf("%u, ", l.objidx); + } + printf("]\n"); + } + } + // Sorts links of all objects in a consistent manner and zeroes all offsets. void normalize () { @@ -396,9 +537,10 @@ struct graph_t return vertices_[i].obj; } - void add_buffer (char* buffer) + bool add_buffer (char* buffer) { buffers.push (buffer); + return !buffers.in_error (); } /* @@ -414,7 +556,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); } /* @@ -443,7 +585,8 @@ struct graph_t update_distances (); - hb_priority_queue_t queue; + hb_priority_queue_t<int64_t> queue; + queue.alloc (vertices_.length); hb_vector_t<vertex_t> &sorted_graph = vertices_scratch_; if (unlikely (!check_success (sorted_graph.resize (vertices_.length)))) return; hb_vector_t<unsigned> id_map; @@ -460,7 +603,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))) { @@ -488,8 +631,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 (); @@ -579,8 +722,8 @@ struct graph_t const auto& node = object (node_idx); if (offset < node.head || offset >= node.tail) return -1; - unsigned length = node.real_links.length; - for (unsigned i = 0; i < length; i++) + unsigned count = node.real_links.length; + for (unsigned i = 0; i < count; i++) { // Use direct access for increased performance, this is a hot method. const auto& link = node.real_links.arrayZ[i]; @@ -600,7 +743,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); @@ -683,12 +826,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; @@ -727,8 +873,7 @@ struct graph_t remap_obj_indices (index_map, parents.iter (), true); // Update roots set with new indices as needed. - uint32_t next = HB_SET_VALUE_INVALID; - while (roots.next (&next)) + for (auto next : roots) { const uint32_t *v; if (index_map.has (next, &v)) @@ -745,10 +890,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); @@ -820,7 +965,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); @@ -864,18 +1009,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 ()); @@ -897,6 +1042,11 @@ struct graph_t * Creates a copy of child and re-assigns the link from * parent to the clone. The copy is a shallow copy, objects * linked from child are not duplicated. + * + * Returns the index of the newly created duplicate. + * + * If the child_idx only has incoming edges from parent_idx, this + * will do nothing and return the original child_idx. */ unsigned duplicate_if_shared (unsigned parent_idx, unsigned child_idx) { @@ -910,18 +1060,20 @@ struct graph_t * Creates a copy of child and re-assigns the link from * parent to the clone. The copy is a shallow copy, objects * linked from child are not duplicated. + * + * Returns the index of the newly created duplicate. + * + * If the child_idx only has incoming edges from parent_idx, + * duplication isn't possible and this will return -1. */ unsigned duplicate (unsigned parent_idx, unsigned child_idx) { update_parents (); - unsigned links_to_child = 0; - for (const auto& l : vertices_[parent_idx].obj.all_links ()) - { - if (l.objidx == child_idx) links_to_child++; - } + const auto& child = vertices_[child_idx]; + unsigned links_to_child = child.incoming_edges_from_parent(parent_idx); - if (vertices_[child_idx].incoming_edges () <= links_to_child) + if (child.incoming_edges () <= links_to_child) { // Can't duplicate this node, doing so would orphan the original one as all remaining links // to child are from parent. @@ -934,7 +1086,7 @@ struct graph_t parent_idx, child_idx); unsigned clone_idx = duplicate (child_idx); - if (clone_idx == (unsigned) -1) return false; + if (clone_idx == (unsigned) -1) return -1; // duplicate shifts the root node idx, so if parent_idx was root update it. if (parent_idx == clone_idx) parent_idx++; @@ -950,6 +1102,62 @@ struct graph_t return clone_idx; } + /* + * Creates a copy of child and re-assigns the links from + * parents to the clone. The copy is a shallow copy, objects + * linked from child are not duplicated. + * + * Returns the index of the newly created duplicate. + * + * If the child_idx only has incoming edges from parents, + * duplication isn't possible or duplication fails and this will + * return -1. + */ + unsigned duplicate (const hb_set_t* parents, unsigned child_idx) + { + if (parents->is_empty()) { + return -1; + } + + update_parents (); + + const auto& child = vertices_[child_idx]; + unsigned links_to_child = 0; + unsigned last_parent = parents->get_max(); + unsigned first_parent = parents->get_min(); + for (unsigned parent_idx : *parents) { + links_to_child += child.incoming_edges_from_parent(parent_idx); + } + + if (child.incoming_edges () <= links_to_child) + { + // Can't duplicate this node, doing so would orphan the original one as all remaining links + // to child are from parent. + DEBUG_MSG (SUBSET_REPACK, nullptr, " Not duplicating %u, ..., %u => %u", first_parent, last_parent, child_idx); + return -1; + } + + DEBUG_MSG (SUBSET_REPACK, nullptr, " Duplicating %u, ..., %u => %u", first_parent, last_parent, child_idx); + + unsigned clone_idx = duplicate (child_idx); + if (clone_idx == (unsigned) -1) return false; + + for (unsigned parent_idx : *parents) { + // duplicate shifts the root node idx, so if parent_idx was root update it. + if (parent_idx == clone_idx) parent_idx++; + auto& parent = vertices_[parent_idx]; + for (auto& l : parent.obj.all_links_writer ()) + { + if (l.objidx != child_idx) + continue; + + reassign_link (l, parent_idx, clone_idx); + } + } + + return clone_idx; + } + /* * Adds a new node to the graph, not connected to anything. @@ -1004,13 +1212,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; @@ -1074,14 +1282,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); } } @@ -1113,6 +1321,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) { @@ -1121,22 +1331,24 @@ 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; } size_t total_size_in_bytes () const { size_t total_size = 0; - for (unsigned i = 0; i < vertices_.length; i++) { - size_t size = vertices_[i].obj.tail - vertices_[i].obj.head; + unsigned count = vertices_.length; + for (unsigned i = 0; i < count; i++) { + size_t size = vertices_.arrayZ[i].obj.tail - vertices_.arrayZ[i].obj.head; total_size += size; } return total_size; @@ -1151,12 +1363,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) { @@ -1183,21 +1391,21 @@ struct graph_t { if (!parents_invalid) return; - for (unsigned i = 0; i < vertices_.length; i++) - vertices_[i].parents.reset (); + unsigned count = vertices_.length; - for (unsigned p = 0; p < vertices_.length; p++) + for (unsigned i = 0; i < count; i++) + vertices_.arrayZ[i].reset_parents (); + + for (unsigned p = 0; p < count; p++) { - for (auto& l : vertices_[p].obj.all_links ()) - { - vertices_[l.objidx].parents.push (p); - } + for (auto& l : vertices_.arrayZ[p].obj.all_links ()) + vertices_[l.objidx].add_parent (p); } - for (unsigned i = 0; i < vertices_.length; i++) + 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_[i].parents.in_error ()); + check_success (!vertices_.arrayZ[i].in_error ()); parents_invalid = false; } @@ -1239,15 +1447,13 @@ struct graph_t // According to https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf // for practical performance this is faster then using a more advanced queue // (such as a fibonacci queue) with a fast decrease priority. - for (unsigned i = 0; i < vertices_.length; i++) - { - if (i == vertices_.length - 1) - vertices_[i].distance = 0; - else - vertices_[i].distance = hb_int_max (int64_t); - } + unsigned count = vertices_.length; + for (unsigned i = 0; i < count; i++) + vertices_.arrayZ[i].distance = hb_int_max (int64_t); + vertices_.tail ().distance = 0; - hb_priority_queue_t queue; + hb_priority_queue_t<int64_t> queue; + queue.alloc (count); queue.insert (0, vertices_.length - 1); hb_vector_t<bool> visited; @@ -1265,15 +1471,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); } } @@ -1301,7 +1507,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); } /* @@ -1329,17 +1535,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 { - for (unsigned i = 0; i < sorted_graph->length; i++) + unsigned count = sorted_graph->length; + for (unsigned i = 0; i < count; i++) { - (*sorted_graph)[i].remap_parents (id_map); - for (auto& link : (*sorted_graph)[i].obj.all_links_writer ()) + 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; } /* @@ -1370,7 +1579,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); } |