[concurrency-interest] Concurrent Bidirectional Map

Martin Buchholz martinrb at google.com
Sun Nov 22 23:01:07 EST 2009


On Sun, Nov 22, 2009 at 18:37, Norman Elton <normelton at gmail.com> wrote:
>> From how you describe it, it sounds like there is no consistency issue. If
>> no thread can ever expect to find that:
>>
>> v->k => k->v
>>
>> then the fact that the above can fail to hold during a modification to the
>> bi-map seems of little consequence.
>
> Just to clarify... yes, at any given instant, k -> v does imply v ->
> k. But there is no way, that I can see, to atomically access both
> get(k) and get(v).

Suppose
thread 1 is trying to set k -> v1
while
thread 2 is trying to set k -> v2

Because the updates of the two maps are independent,
and you can't control the scheduler, there is a risk of
ending up with
k -> v1
in the first map, and
v2 -> k
in the reverse map
in the quiescent state.

Martin


More information about the Concurrency-interest mailing list