Iteration Order

[cburroughs]

LinkedHashMap allows insertion-order iteration. I know issue #21 was
to allow iteration related to access order (yeah!) and the code looks
like the default iteration order is CHM's guarantee-free order. Is
this an accurate reading? Is there an insertion order (or I suppose
equivalently a LRW configuration) iterator available that I have
missed? I know this doesn't really jibe with the common LRU cache use
case.

[Ben Manes]

I've tried to avoid expectations on iteration order, since that adds
complexity that diverges from the caching use-case. The snapshot
ordering isn't guaranteed to be access-ordered, since this is an
artifact of the LRU policy currently used (LIRS won't be access-
ordered).

The insertion-order is a simpler problem than access-order, but makes
less sense for caches. I've tried to avoid scope creep since the
complexity overhead is fairly high already.

Most often a LHM guarded by a lock and snapshotting the iterator is
good enough. If its read-centric, then writes to a CHM can be guarded
by lock to also insert into a LHM. That would allow reads to served by
CHM, while writes/iteration are penalized. Either of these would be
simple code and I suspect be satisfactory for your use-case. A more
complicated but low-penalty solution would be to record the writes in
a buffer and replay them in a non-blocking fashion on a link chain
(e.g. how CLHM works), and make the _next_ field volatile so that
iteration doesn't require snapshotting (not done in CLHM due to
reordering).

[cburroughs]

Thanks. CHM+LHM sounds simple enough. I just wanted to make sure
there wasn't something in CLHM already I was missing.