For me it helped to rather think about 'visited' as a special case of a counter called 'valuation' (or something like that). New objects come in with valuation 1, on cache hits a objects valuation is set to 2, and when the hand moves left it decreases objects valuations until it reaches one that gets valuation 0, then it's evicted immediately. One could easily imagine a modified algorithm where 'valuation' could be increased further than 2 if an object got visited many times (but then eviction would be much slower in some cases).
Then this is all optimized by using a bool instead of an int since we truncate 'valuation' at max 2.
Idk why they choose to call it 'visited' though.
Really handy for tracking potentially abusive ips, if your table is big enough; on a request, check if it's in the table - if so increase the count and if it's above the theshold mark it. If it's not in the list, decrement the current item and move current to the next item.
An agressive user will clear out a slot for itself, and rapidly hit the threshold. Other users will come and go. You can iterate through and try to always clear a spot for a new entry, but it might not be necessary, depending on what you're caching.
It uses a list that's treated as a ring buffer to keep track of keys currently in the cache.
The "hand" is a pointer that points to a given node in that ring buffer.
When the cache is full and a space is needed, the "hand" moves through that buffer (possibly wrapping around). Whenever it points at a node that hasn't been touched since the last time it was seen, that node is evicted and you're done for this time, otherwise it clears the visited bit for that node and keeps going.
(You're always guaranteed to find a node to evict, because worst case you scan through the entire set of nodes, and find the first node you cleared the visited bit of)
If you're familiar with LRU/LFU, ring buffers (though this isn't such), and data structures this will probably make a lot more sense.
A rigorous course in data structures is fantastic for any engineer. Everything is data structures and algorithms at the end of the day.
Dude, what?