[fpc-devel] LockFree Queue algorithm

Michael Schnell mschnell at lumino.de
Mon Jan 28 10:12:31 CET 2008

I just finished a unit that provides a FIFO and similar stuff, so I'm 
very interested.

IMHO you should not use "push" and "put" as this suggests a LiFo 
("Stack"). With my unit I mostly intended to recreate the putc() and 
getc() functions in glibc (though I did neither use them nor took a look 
at their implementations). Thus IMHO for a "FiFo" you should use a "put" 
and "get"  notation.

My unit provides an (optionally automatically growing and shrinking) 
FiFo fast byte handling. It has putc and getc (with the same parameters 
(Integer!) as it's done in glibc), plus unget() and unput() for revers 
operations (which in fact implements FiFo behavior). Moreover it 
provides a TStream based interface handling blocks of bytes for all 
these operations.

It does not yet have any locking mechanism ! I have been thinking about 
this but did not start to implement it.

Moreover I do like that your component provides a "generic" interface. 
(finally a good use for this paradigm <g> ).

I have to think a bit more about the locking mechanism you suggest.

I intended to use a single word as a semaphore to protect the access to 
the structure and fall back to an OS-based wait (e.g. by 
TCriticalSection) if it can't be acquired. This is how a FUTEX works in 
Linux (maybe TCriticalSection even already uses such algorithm)


More information about the fpc-devel mailing list