<p>At the moment tags with identical names are stored into a linked list in<br>
tags_table and parents_table. This however leads to quadratic complexity<br>
when looking up the nearest parent or tag in tree because the whole list<br>
has to be traversed.</p>

<p>Use binary trees indexed by line number instead of lists so the lookup can<br>
be performed in log(N) time and the overall complexity is N*log(N) instead<br>
of N^2.</p>

<p>The GTree API is a little stupid because during the search it doesn't give<br>
access to the value and it doesn't tell when a leaf node was reached. For<br>
this reason the lookup has to be made in two steps - first, the best line<br>
number is found (returned in user_data) and then a normal search for the<br>
found line number is made to get the value stored in the tree.</p>

<p>This patch fixes the problem described in <a href="https://github.com/geany/geany/issues/577" class="issue-link" title=" For a long time to open JSON files 37mb">#577</a> when e.g. a big json export<br>
file contains many identically named tags.</p>

<hr>

<h4>You can view, comment on, or merge this pull request online at:</h4>
<p>  <a href='https://github.com/geany/geany/pull/797'>https://github.com/geany/geany/pull/797</a></p>

<h4>Commit Summary</h4>
<ul>
  <li>Store "equal" tags into binary trees instead of lists in Symbol tree</li>
</ul>

<h4>File Changes</h4>
<ul>
  <li>
    <strong>M</strong>
    <a href="https://github.com/geany/geany/pull/797/files#diff-0">src/symbols.c</a>
    (249)
  </li>
</ul>

<h4>Patch Links:</h4>
<ul>
  <li><a href='https://github.com/geany/geany/pull/797.patch'>https://github.com/geany/geany/pull/797.patch</a></li>
  <li><a href='https://github.com/geany/geany/pull/797.diff'>https://github.com/geany/geany/pull/797.diff</a></li>
</ul>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<br>Reply to this email directly or <a href="https://github.com/geany/geany/pull/797">view it on GitHub</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/ABDrJ4FNTCpa-Hb44E8k8lJ18wNd-HSvks5pPFG0gaJpZM4G0Ju3.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
  <link itemprop="url" href="https://github.com/geany/geany/pull/797"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>