Lock-free ordered list

There is a method for inserting an item into an ordered list. Will it be correct for lock-free?

template< typename _Pred >
inline void lock_free_push( sll_node*tail, sll_node*n, _Pred Pred ){
    std::list< sll_node* >Local;
    sll_node*head,*next;
    //
    for( Local.push_back( n ) ; !Local.empty() ; ){
        n   = Local.back();
        head    = tail->next;
        if( ( head == tail ) || Pred( n, head ) ){
            n->next = head;
            if( _InterlockedCompareExchangePtr( &tail->next, n, head ) == head ){
                Local.pop_back();
            }
        }else if( head != tail ){
            next    = head->next;
            if( _InterlockedCompareExchangePtr( &tail->next, next, head ) == head ){
                Local.insert(
                    std::find_if(
                        Local.begin(), Local.end(), [ = ]( sll_node*e ){
                            return Pred( head, e );
                        }
                    ), head
                );
            }
        }
    }
}

In a nutshell: here, the local element n is recursively inserted into the head of the ring interlocked list with the boundary element tail, provided that n <= head. If n > head, an attempt is made to extract the head element. If it works, it is placed in the local list Local. Iterations continue until Local is non-empty. As a result, we should get an ordered list from the stack lock-free lock-free.

tail - tail (head) border element of the lock-free-stack
sll_node - single-linked list node
Pred( a, b ) - an arbitrary method that returns TRUE if a <= b

You can do without the STL, the container is taken to simplify the implementation. Does anyone see the errors?

UPD1: removed the transformations so as not to break the strings.
UPD2: implementation of the same, but already without STL:

template< typename _Pred >
inline void lock_free_push( sll_node*tail, sll_node*n, _Pred Pred ){
    sll_node**p,*head,*next, local;
    // вставляем в `local` узел `n` и повторяем итерации,
    // пока `local` непустой
    for( n->next = &local, local.next = n ; local.next != &local ; ){
        // берем из `local` максимальный элемент (первый)
        n   = local.next;
        // запоминаем головной элемент стека в `head`
        head    = tail->next;
        if( ( head == tail ) || Pred( n, head ) ){
            // список пуст или `n <= head` - запоминаем локальный хвост, после `n`
            next    = n->next;
            // пытаемся атомарно разместить `n` на вершине стека,
            // если она не изменилась
            n->next = head;
            if( _InterlockedCompareExchangePtr( &tail->next, n, head ) == head ){
                // получилось - удаляем `n` из `local`
                local.next  = next;
            }else{
                // не получилось - восстанавливаем локальный хвост
                // и продолжаем lock-free итерации    
                n->next = next;
            }
        }else if( head != tail ){
            // список не пуст и `n > head` - запоминаем хвост, после `head` в `next`
            // и пытаемся атомарно вытолкнуть вершину стека `head`,
            // если она не изменилась
            next    = head->next;
            if( _InterlockedCompareExchangePtr( &tail->next, next, head ) == head ){
                // получилось - ищем позицию для `head` в `local`:
                // сортировка по убыванию
                for( p = &local.next ; ( *p != &local ) && Pred( head, *p ) ; p = &(*p)->next );
                // размещаем `head` в `local`
                head->next  = *p;
                *p          = head;
            }
        }
    }
}

In the worst case , a single thread will take all the elements, arrange them, and insert them back.

Comments:

Do I understand correctly that in the process, some of the items from the tail list are moved to local?

If so, then they (elements) will become invisible to other threads (and not just to threads that list new elements).

This is provided in the general processing algorithm data?

I am trying to use such an object when distributing tasks on SMP, i.e. yes, it is implied that there are other means to provide the flow with information that there are other list items that just need to "wait".

In general, this is done in an elementary way: just start interlocked - the node counter in the list. If the node is deleted, the counter decreases the value. If it is simply blocked (exclusively used in the body of the thread), the counter stores a value about it on the node, without releasing the other threads. Something like that.:)

Just imagine the situation with the assignment of tasks to different programmers for data processing in such a system.

One - receive from the outside, add and organize. It will call this lock_free_push ().

Another is to search in sorted lists and count the sums (or something else).

Here the customer will be surprised when he sees that the amount is growing, then decreasing (and according to the physics of the process, it can only grow).

@avp , I mean here to work only in the usual stack pardigma lock-free, but with a small addition that may be key: such a stack can have a "minimum" element removed from the top. I.e., of course, it can be ordered in any direction, but from all the currently available nodes, from the point of view of the algorithm - the minimum will always be at the top of the stack.

P. s.: strange all the same regulations on the Hash Code about comments, why can't you control their number individually?