[LC++]Threading and shared STL containers.

[Carlo Wood]

Does anyone know a tutorial, howto or even a white-paper
on this topic?  It must have been done before :/

I am mostly interested in the locking strategies
for containers where iterators are not invalidated
by insertion or erasure (for example a map<> or list<>).

There seem to be four types of operations in this case:
1) Changing the internal structure of the container
   (1a) insertion or 1b) erasure).
2) Reading the internal structure of the container
   (for example doing a find()).
3) Writing to elements (iterator).
4) Reading elements (const_iterator).

Obviously, the best thing to use for 1) and 2) are
read/write locks.  Also, 2) reading the internal
structure of a container, doesn't inhibit 4).

Moreover, 3) writing to elements, is already implemented
in a way that protects the internal tree structure of
the STL containers: For example, a map<>::iterator
doesn't allow you to change the key (the key is const).
Hence, operations 3) and 4) do not need to inhibbit
operation 1) or 2).  Finding elements involves reading
elements however, so 2) finding elements, also blocks
whatever operator 4) does block.

Insertion of a new element always involves a different
element then elements that we might already have iterators
for.

This "analysis" seems to give me the following demands:

1a) insertion blocks:
	1a) other insertions
	1b) erasures
	2)  find
1b) erasure blocks:
	1a) insertions
	1b) other erasures
	2) find
	Note: it makes no sense to block
	concurrent reads of iterators (to this
	element) because that block would be lifted
	directly after erasure completes and the program
	would still crash (since the assumed iterator
	would point to cyber space).
2) finding elements blocks:
	1) insertion or erasure of elements
	3) writing to elements
3) writing to iterators blocks:
	3) writing to the same element
	4) reading the same element
4) reading iterators blocks:
	3) writing to the same element

This seems therefore to involve one rwlock per element,
one global lock for 'writing to elements' and one global
rwlock per container.

I'd like to have comments on this analysis.

-- 
Carlo Wood <carlo at alinoe.com>