[subset-perf] remove sort_kahn from repacker.
Without an optimized FIFO queue implementation it's nearly as slow as the now optimized sort_shortest_distance.
diff --git a/src/hb-repacker.hh b/src/hb-repacker.hh
index 6af802f..aefa7c8 100644
--- a/src/hb-repacker.hh
+++ b/src/hb-repacker.hh
@@ -249,58 +249,6 @@
}
/*
- * Generates a new topological sorting of graph using Kahn's
- * algorithm: https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
- */
- void sort_kahn ()
- {
- positions_invalid = true;
-
- if (vertices_.length <= 1) {
- // Graph of 1 or less doesn't need sorting.
- return;
- }
-
- hb_vector_t<unsigned> queue;
- 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;
- if (unlikely (!check_success (id_map.resize (vertices_.length)))) return;
-
- hb_vector_t<unsigned> removed_edges;
- if (unlikely (!check_success (removed_edges.resize (vertices_.length)))) return;
- update_parents ();
-
- queue.push (root_idx ());
- int new_id = vertices_.length - 1;
-
- while (!queue.in_error () && queue.length)
- {
- unsigned next_id = queue[0];
- queue.remove (0);
-
- vertex_t& next = vertices_[next_id];
- sorted_graph[new_id] = next;
- id_map[next_id] = new_id--;
-
- for (const auto& link : next.obj.all_links ()) {
- removed_edges[link.objidx]++;
- if (!(vertices_[link.objidx].incoming_edges () - removed_edges[link.objidx]))
- queue.push (link.objidx);
- }
- }
-
- check_success (!queue.in_error ());
- check_success (!sorted_graph.in_error ());
- if (!check_success (new_id == -1))
- print_orphaned_nodes ();
-
- remap_all_obj_indices (id_map, &sorted_graph);
-
- hb_swap (vertices_, sorted_graph);
- }
-
- /*
* Generates a new topological sorting of graph ordered by the shortest
* distance to each node.
*/
@@ -1218,7 +1166,6 @@
// Kahn sort is ~twice as fast as shortest distance sort and works for many fonts
// so try it first to save time.
graph_t sorted_graph (packed);
- sorted_graph.sort_kahn ();
if (!sorted_graph.will_overflow ())
{
return sorted_graph.serialize ();
diff --git a/src/test-repacker.cc b/src/test-repacker.cc
index 3a2536a..17e0d26 100644
--- a/src/test-repacker.cc
+++ b/src/test-repacker.cc
@@ -729,26 +729,6 @@
}
static void
-populate_serializer_complex_1 (hb_serialize_context_t* c)
-{
- c->start_serialize<char> ();
-
- unsigned obj_4 = add_object ("jkl", 3, c);
- unsigned obj_3 = add_object ("ghi", 3, c);
-
- start_object ("def", 3, c);
- add_offset (obj_3, c);
- unsigned obj_2 = c->pop_pack (false);
-
- start_object ("abc", 3, c);
- add_offset (obj_2, c);
- add_offset (obj_4, c);
- c->pop_pack (false);
-
- c->end_serialize();
-}
-
-static void
populate_serializer_complex_2 (hb_serialize_context_t* c)
{
c->start_serialize<char> ();
@@ -831,68 +811,6 @@
c->end_serialize();
}
-static void test_sort_kahn_1 ()
-{
- size_t buffer_size = 100;
- void* buffer = malloc (buffer_size);
- hb_serialize_context_t c (buffer, buffer_size);
- populate_serializer_complex_1 (&c);
-
- graph_t graph (c.object_graph ());
- graph.sort_kahn ();
-
- assert(strncmp (graph.object (3).head, "abc", 3) == 0);
- assert(graph.object (3).real_links.length == 2);
- assert(graph.object (3).real_links[0].objidx == 2);
- assert(graph.object (3).real_links[1].objidx == 1);
-
- assert(strncmp (graph.object (2).head, "def", 3) == 0);
- assert(graph.object (2).real_links.length == 1);
- assert(graph.object (2).real_links[0].objidx == 0);
-
- assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
- assert(graph.object (1).real_links.length == 0);
-
- assert(strncmp (graph.object (0).head, "ghi", 3) == 0);
- assert(graph.object (0).real_links.length == 0);
-
- free (buffer);
-}
-
-static void test_sort_kahn_2 ()
-{
- size_t buffer_size = 100;
- void* buffer = malloc (buffer_size);
- hb_serialize_context_t c (buffer, buffer_size);
- populate_serializer_complex_2 (&c);
-
- graph_t graph (c.object_graph ());
- graph.sort_kahn ();
-
-
- assert(strncmp (graph.object (4).head, "abc", 3) == 0);
- assert(graph.object (4).real_links.length == 3);
- assert(graph.object (4).real_links[0].objidx == 3);
- assert(graph.object (4).real_links[1].objidx == 0);
- assert(graph.object (4).real_links[2].objidx == 2);
-
- assert(strncmp (graph.object (3).head, "def", 3) == 0);
- assert(graph.object (3).real_links.length == 1);
- assert(graph.object (3).real_links[0].objidx == 1);
-
- assert(strncmp (graph.object (2).head, "mn", 2) == 0);
- assert(graph.object (2).real_links.length == 0);
-
- assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
- assert(graph.object (1).real_links.length == 1);
- assert(graph.object (1).real_links[0].objidx == 0);
-
- assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
- assert(graph.object (0).real_links.length == 0);
-
- free (buffer);
-}
-
static void test_sort_shortest ()
{
size_t buffer_size = 100;
@@ -1336,8 +1254,6 @@
main (int argc, char **argv)
{
test_serialize ();
- test_sort_kahn_1 ();
- test_sort_kahn_2 ();
test_sort_shortest ();
test_will_overflow_1 ();
test_will_overflow_2 ();
