I know its not possible to edit a HashMap or LinkedHashMap content during iteration without throwing a ConcurrentModificationException. However, I have a situation where I need to apply that. I am writing a virtual memory simulation using the Clock implementation of the Second Chance algorithm. Note: RAM is a LinkedHashMap so that the iteration order follows insertion order. This is my current approach (where tmp, hand, and entry are variables declared outside the main loop logic:
PTE tmp; // A tmp PageTableEntry reference used for shuffling PTEs across RAM and the Page Table
Iterator<Entry<Integer, PTE>> hand; // Iterator that represents the clock hand
Map.Entry<Integer, PTE> entry = null; // A tmp Map Entry ref that is used to store the return of the hand Iterator
hand = RAM.entrySet().iterator(); // Set the Clock hand to the oldest PTE in RAM
entry = hand.next(); // Advance the iterator to the first RAM entry
tmp = entry.getValue(); // Get the PTE the Clock hand is pointing at
while (tmp.ref && hand.hasNext()) { // Advance the clock hand through RAM until finding an unreferenced PTE
debugPrint(String.format("while:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);
tmp.ref = false; // Set the ref bit to false to give the PTE a second chance
entry = hand.next(); // Select next PTE in RAM
tmp = entry.getValue();
}
if (tmp.ref && !hand.hasNext()) { // Corner Case: The clock hand has found all PTEs in RAM to be referenced, must follow FIFO
debugPrint(String.format("!HasNext:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);
tmp.ref = false; // Marked for eviction, must be set to unreferenced
hand = RAM.entrySet().iterator(); // Reset the clock hand to point back to the first PTE inserted.
entry = hand.next();
tmp = entry.getValue();
}
This produces nearly correct output, but my problem is that the iterator should not be recereated each time the algorithm is used. I need a way to store the next element the iterator would be pointing to so that I can remove tmp from the LinkedHashMap and replace it with the new PageTableEntry that goes there so that next time the iterator runs it resumes from where it left off, not seeing the newly added entry until it reaches the end and has to loop back around.
Iterator interface does not have an API to add elements to it and prevent concurrent modifications was one of its objectives, so I'm afraid that optimisation is very difficult unless you write your own implementation of LinkedHashMap.
I can't see any usage of the key of the map, so If LinkedHashMap could be changed, then may be your can avoid such complexity by using a queue is you always wanted sequential processing or a priority queue also could be used if you have some lookups