Skip to content
  • Frank Reininghaus's avatar
    Store the selected items in a more efficient way · fc2ab478
    Frank Reininghaus authored
    Since Dolphin 2.0, we have stored the selected items in a QSet<int>,
    which is neither space-efficient nor particularly fast when inserting
    many items which are in a consecutive range.
    
    This commit replaces the QSet<int> by a new class "KItemSet", which
    stores the items in a sorted list of ranges. For each range, we only
    store the first index and the length of the range, so we need a lot
    less memory for most common selection patterns, and we also save quite
    a few CPU cycles in many situations, because adding an item to the
    KItemSet will in many cases not need a memory allocation at all, and
    it's particularly easy when inserting sorted items into the KItemSet in
    a row.
    
    KItemSet contains a minimal subset of QSet's API which makes it
    suitable as a drop-in replacement for our needs. It also has iterators,
    such that the items can be iterated through easily, also with foreach.
    One advantage of KItemSet compared to QSet<int> is that the items are
    always iterated through in ascending order.
    
    REVIEW: 113488
    fc2ab478