Hello,
Within the scope of a small side project, I've experimented with
replacing catgirl's linear-searching completion code with a tree-based
approach.
This improves the time complexity of search queries to O(log n).
While this may have little noticable effect on newer CPUs due to the
vectorized strcmp implementations provided by glibc, it may be relevant
for older machines or small computers - especially on larger networks
(Libera etc).
The trees are fairly balanced as can be seen from the attached graphviz
visualization, and also retain the MRU-caching characteristics of the
original code (accepted completions are given a positive priority and
are bubbled up accordingly).
I've been running this patch for a few days now with no issues, so I
thought I might as well submit it here in case someone finds it
interesting.
Cheers,
-Alcor