****table eventcount (try 2)

I take into account feedback from Anthony Williams and Chris Thomasson
after my first try:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/9461b41709e4063a

Here is claimed properties:
1. No memory allocation/deallocation
2. No kernel object creation/destruction
3. Broadcasting with single syscall
4. No mutex acquisition after wait on semaphore
5. ****table because based on semaphore
6. No spurious wakeups by design
7. You can easily transform this algorithm into condition variable

Brief comments on algorithm:
1. Every thread has associated node which it uses in eventcount
operations
2. Threads exchange of their nodes
3. Mutex acquisition, which must be after wait on semaphore, executed
before next wait (it's just deferred).

Here is the code:

struct thread_node
{
    thread_node*            next;
    size_t                  count;
    size_t                  unconsumed;
    HANDLE                  sema;
    CRITICAL_SECTION        mtx;
};

__declspec(thread) thread_node* t_thread_node;

void on_thread_exit()
{
    thread_node* head = t_thread_node;
    thread_node* my = 0;
    if (head)
    {
        EnterCriticalSection(&head->mtx);
        if (head->next)
        {
            my = head->next;
            head->next = my->next;
        }
        else
        {
            my = head;
        }
        LeaveCriticalSection(&head->mtx);
        DeleteCriticalSection(&my->mtx);
        CloseHandle(my->sema);
        delete my;
    }
}

struct eventcount
{
    eventcount()
    {
        root = 0;
        InitializeCriticalSection(&mtx);
    }

    ~eventcount()
    {
        DeleteCriticalSection(&mtx);
    }

    void prepare_wait()
    {
        thread_node* my = 0;
        thread_node* head = t_thread_node;
        if (head)
        {
            EnterCriticalSection(&head->mtx);
            if (head->next)
            {
                my = head->next;
                head->next = my->next;
                my->next = 0;
            }
            else
            {
                my = head;
            }
            LeaveCriticalSection(&head->mtx);
        }
        else
        {
            my = new thread_node;
            my->next = 0;
            my->count = 0;
            my->unconsumed = 0;
            my->sema = CreateSemaphoreW(0, 0, LONG_MAX, 0);
            InitializeCriticalSection(&my->mtx);
        }

        while (my->unconsumed)
        {
            WaitForSingleObject(my->sema, 0);
            my->unconsumed -= 1;
        }

        EnterCriticalSection(&mtx);
        if (root)
        {
            my->next = root->next;
            root->next = my;
            my = root;
        }
        else
        {
            root = my;
        }
        root->count += 1;
        LeaveCriticalSection(&mtx);
        t_thread_node = my;
    }

    void wait()
    {
        thread_node* head = t_thread_node;
        if (head == root)
        {
            WaitForSingleObject(head->sema, INFINITE);
        }
        else
        {
            EnterCriticalSection(&head->mtx);
            head->unconsumed += 1;
            LeaveCriticalSection(&head->mtx);
        }
    }

    void retire_wait()
    {
        thread_node* head = t_thread_node;
        if (head == root)
        {
            EnterCriticalSection(&mtx);
            if (head == root)
            {
                thread_node* my = 0;
                head->count -= 1;
                if (head->next)
                {
                    my = head->next;
                    head->next = my->next;
                    my->next = 0;
                }
                else
                {
                    my = head;
                }
                LeaveCriticalSection(&mtx);
                t_thread_node = my;
                return;
            }
            LeaveCriticalSection(&mtx);
        }
        EnterCriticalSection(&head->mtx);
        head->unconsumed += 1;
        LeaveCriticalSection(&head->mtx);
    }

    void signal_all()
    {
        _mm_mfence();
        thread_node* head = root;
        if (0 == head)
            return;
        EnterCriticalSection(&mtx);
        if (head != root)
        {
            LeaveCriticalSection(&mtx);
            return;
        }
        root = 0;
        LeaveCriticalSection(&mtx);
        size_t count = head->count;
        head->count = 0;
        ReleaseSemaphore(head->sema, count, 0);
    }

    void signal_one()
    {
        _mm_mfence();
        thread_node* head = root;
        if (0 == head)
            return;
        EnterCriticalSection(&mtx);
        if (head != root)
        {
            LeaveCriticalSection(&mtx);
            return;
        }
        head->count -= 1;
        if (0 == head->count)
            root = 0;
        LeaveCriticalSection(&mtx);
        ReleaseSemaphore(head->sema, 1, 0);
    }

    thread_node* volatile   root;
    CRITICAL_SECTION        mtx;
};


Dmitriy V'jukov
--
Relacy Race Detector: Make your synchronization correct!
http://groups.google.ru/group/relacy/web