Skip to content

Draft: util/addon: use AVL trees

Kirill Primak requested to merge vyivel/wlroots:addon-tree into master

Just a proof of concept which replaces linked lists with AVL trees. Might be useful if wlr_addon_find() performance will ever end up being a bottleneck.

The implementation is largely based on the corresponding Wikipedia article.

  • Lookup is now O(log n) instead of O(n)
  • Insertion is now O(log n) instead of O(1)
  • Deletion is now O(log n) instead of O(1)
  • Set cleanup is now O(n log n) instead of O(n)
    • Due to unnecessary rebalancing; this can probably be optimized
  • None of this was benchmarked

Merge request reports