While researching the subject matter - lock-free and wait-free data structures - I'm seeing a worrying amount of mention of patents with this area. I've hobby-researched compression algorithms years ago and by comparison the situation seems worse as hard as that is to imagine.
Background
I have a project in progress that at this stage is personal / private but eventually is intended to be profitable targeting western markets (Europe, US, Australia etc). I understand software patents are not so much an issue in Eu, but definitely in US and by extension in Aus to a degree if not as much.
The Issue
With any computational process there are basic units that one can use. I would consider for this purpose that something like an array or list would be a fundamental unit - there are already optimal algorithms & structures researched tried and tested for longer than I've lived, but these are (as far as I know) not subject to any patents or conditional use. Perhaps not in the really extreme case like criminal offenses (in the sense that it isn't a copyright / royalty issue but actual crimes being committed but I digress).
Enter lock-free / wait-free (LFWF).
I could be wrong but it seems to me that introducing such fundamental algorithmic units to thread-safety methodology (any) would be an enhancement in the general case and probably able to be patented. However what if there is a most-simple or most-straightforward way to 'enhance' a structure for parallel processing? Would there not be such 'trivial' algorithms or structures for parallel processing?
The Question
Basically, at what point would a LFWF enhancement to something like a list or map or vector or queue etc, begin to 'stand out' enough as to be patentable or at least 'risky' to use without consulting a patent office / lawyer?
Unrelated but appreciated for consideration - would this not hamper development efforts in this area if the bar is set too low for what is a patentable enhancement to an established free-use concept via LFWF?
I understand LFWF itself is not going to be a concern because the operations themselves - the raw functions' implementations - are compiler / hardware / vendor headaches that a programmer generally would not be involved with anyway.
An Example
Most commonly I've found reference to single-linked list (SLL) structures and algorithms exhaustively patented - is this actually the situation, can I not use my own LFWF SLL ideas for fear of existing patents?
Now, considering something as simple as SLL has only so many ways it could be implemented with LFWF improvements, what sort of implementation am I limited to in order to avoid making something potentially patented already? Or is there no such limit and only specific methodologies are covered?
For analogy, one cannot patent the wheel but one could patent a new sort of wheel that has distinct features / advantages and/or disadvantages. At what point do algorithmic primitives cross the line from wheel to 'new idea' through LFWF implementations thereof?
