[PATCH 1/1] Improve performance of package list expansion.

Matthew Hanna (BLOOMBERG/ 731 LEX) mhanna21 at bloomberg.net
Sat Jun 18 13:23:00 UTC 2016

In practice, for library sets with a high degree of dependency, iteration over the tree with revisiting results in significant slow down at best and pkg-config failure due to memory exhaustion at worst.  This patch replaces the 'in_requires_chain' flag that halted circular dependencies with a hash table that marks visited package nodes.  The resulting algorithm is equivalent to a topological sort.  Although a boolean flag on each node could be used to implement the algorithm, resetting the flag to false can only be done after the algorithm is complete, creating a bit of extra bookkeeping.  Instead, I chose to use a new hash table to record the visits, reducing the bookkeeping to a call to 'g_hash_table_destroy'.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/pkg-config/attachments/20160618/8d1efee2/attachment.html>

More information about the pkg-config mailing list