Method insertSorted

kdevplatform/util/embeddedfreetree.h:697–755

Inserts the given data item into position @p pos, and updates the sorting @param data can be another empty item, that together with @p pos represents the closest enclosure of the target position @return Whether the item could be inserted. It is not inserted if

    ///@param data can be another empty item, that together with @p pos represents the closest enclosure of the target position
    ///@return Whether the item could be inserted. It is not inserted if
    bool insertSorted(const Data& data, int pos, int start, int end, bool force)
    {

        if (pos < start)
            start = pos;
        if (pos >= end)
            end = pos + 1;

/*               for(int a = start; a < end; ++a) {
                   if(a != pos) {
                       Q_ASSERT(!ItemHandler::isFree(m_items[a]));
                   }
               }*/
        EmbeddedTreeAlgorithms<Data, ItemHandler> alg(m_items, m_itemCount, *m_centralFreeItem);
        int bound = alg.lowerBound(data, start, end);
        //Now find the position that should be taken
        if (bound == -1)
            bound = end;

        //Now our item should end up right before bound

        int target;
        //bound cannot be pos, because pos is invalid
        Q_ASSERT(bound != pos);

#if defined(__GNUC__) && !defined(__INTEL_COMPILER) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 800)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wclass-memaccess"
#endif
        //Shuffle around the item at the free pos, so reference counting in constructors/destructors is not screwed up
        char backup[sizeof(Data)];
        memcpy(backup, m_items + pos, sizeof(Data));

        if (bound < pos) {
            if (!force && pos - bound > maxMoveAround()) {
//                         qCDebug(UTIL) << "increasing because" << pos-bound << ">" << maxMoveAround() << "left free items:" << countFreeItems(*m_centralFreeItem) << "target free items:" << (m_itemCount-countFreeItems(*m_centralFreeItem))/increaseFraction;
                return false;
            }
            //Move [bound, pos) one to right, and insert at bound
            memmove(m_items + bound + 1, m_items + bound, sizeof(Data) * (pos - bound));
            target = bound;
        } else {
            Q_ASSERT(bound > pos);
            if (!force && bound - pos - 1 > maxMoveAround()) {
//                         qCDebug(UTIL) << "increasing because" << bound-pos-1 << ">" << maxMoveAround() << "left free items:" << countFreeItems(*m_centralFreeItem)<< "target free items:" << (m_itemCount-countFreeItems(*m_centralFreeItem))/increaseFraction;
                return false;
            }
            //Move (pos, bound) one to left, and insert at bound-1
            memmove(m_items + pos, m_items + pos + 1, sizeof(Data) * (bound - pos - 1));
            target = bound - 1;
        }
        memcpy(m_items + target, backup, sizeof(Data));
#if defined(__GNUC__) && !defined(__INTEL_COMPILER) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 800)
#pragma GCC diagnostic pop
#endif

        ItemHandler::copyTo(data, m_items[target]);
        return true;