[Windows Phone 7 Development and Hacking] Martin7Pro:
Hi friends.

I must solve big problem to finish HaRET (and other native applications) managed wrapper and UI (i. e. for example managed Silverlight UI controlled from unmanaged code), safe WP7 FTP client, interprocess cooperation on WP7, etc.

I know it is a basic issue, which is probably solved many time in operating systems (windows messages etc.) and many other examples.

But, I could find no any source code for queue, which is:

1. safe for more writers (threads from more processes) and for one reader,

2. unblocking for all writers,

3. unblocking for reader.

I found only very much unblocking ringbuffers or blocking queues, no one unblocking unlimited queue. Please, send corrections if I am bad looking.

Then, I tried code it...

First I want use std::queue with Thread Local Storage identifications (one subqueue for all writer and one abqueue for reader). But, TLS is very limited on CE based systems and I am not sure, if it solve interprocess safety too.

Finally, I tried to write the following code. It is designed for interthread queue only still, but interprocess can be added by safe named filemapping probably. Tell your opinion, it will be the basis for many complex applications here. For many years I have not worked with low-level synchronisation, I could make a fundamental mistake. So far I've missed templates and any wrapper, it's just the basic idea, usable in both C/C++ with very little changes:

// This queue is unblocking and thread safe, when:
// 1. more writers are allowed,
// 2. one reader is allowed only.

// Motto: Pointers queue is both-directional, but frontal direction is changed by writers, backward direction by reader only!

#ifndef InterlockedExchangePointer
#define InterlockedExchangePointer(Target, Value) ((PVOID)InterlockedExchange((PLONG)(Target), (LONG)(Value)))
#endif

#ifndef InterlockedCompareExchangePointer
#define InterlockedCompareExchangePointer(Destination, ExChange, Comperand) ((PVOID)InterlockedCompareExchange((PLONG)(Destination), (LONG)(ExChange), (LONG)(Comperand)))
#endif

typedef struct SQItem
{
SQItem * pNext;
SQItem * pPrev;
void * pValue;
} * PItem;

SQItem EmptyItem = {NULL, NULL, NULL};
PItem pFront = &EmptyItem;
PItem pBack = &EmptyItem;
// Empty queue contains one item with both directions pointers nulled.

bool push_front(void * pNewValue) // nonblocking push, but theoretically forever cycle is possible for low priority thread! Practically improbable.
{
if (!pNewValue)
{
return false;
}
PItem pNewFront = new SQItem;
if (pNewFront)
{
PItem pProbablyFront;
InterlockedExchangePointer(&pProbablyFront, pFront);
pNewFront->pNext = pProbablyFront;
pNewFront->pPrev = NULL;
pNewFront->pValue = pNewValue;
while (InterlockedCompareExchangePointer(&pFront, pNewFront, pProbablyFront) != pProbablyFront)
{ // Another writer changed front pointer, active writer must try it again.
InterlockedExchangePointer(&pProbablyFront, pFront);
pNewFront->pNext = pProbablyFront;
}
return true; // Success allways.
}
return false; // Insufficient memory.
}

void * pop_back() // one reader allowed only!!!
{
PItem pBackward;
InterlockedExchangePointer(&pBackward, pFront); // Safe copy of actual front pointer
if (pBackward == pBack) // Queue is empty in time of interlocked attempt.
{
return NULL;
}
if (!pBack->pPrev)
{ //	If backward queue is not continued here, reconstruct it from safe front pointer.
while (pBackward != pBack && !pBackward->pNext->pPrev)
{
pBackward->pNext->pPrev = pBackward;
pBackward = pBackward->pNext;
}
}
//	One reader can safe read from back and manipulate with backward queue.
PItem pDelete = pBack;
pBack->pPrev->pNext = NULL;
pBack = pBack->pPrev;
delete pDelete;
return pBack->pValue;
/* // This is not necessary, but it is more clean:
void * pResult = pBack->pValue;
pBack->pValue = NULL;
return pResult;
*/
}

I am not sure, if heap allocation is not more "blocking" operation due to swapping and mm priorities, then object/signal waiting. What do you mean about it?

Mirror principle can be used to OneToMore queue making. Thanks unblocking, MoreToOne and OneToMore can be immeditelly piped to MoreToMore one.

But, when CE systems do not support two coupled pointers interlocked functions, there is no possibility to identify allowed reader safely, then this has not great significance.

As well, MoreToOne is much more needed now.