questions about LRU implementation

Hi,

I am very enthusiastic about the internal operations of Squid.
I did try to know more about that by looking into the Squid source but
it is really difficult for me to achieve it.

From the Squid Programmers Guide I know that, to implement the LRU, a
hash table and a double link list are used.
I just want to clarify the operations of the LRU. Are the operations
like these:

When Squid receives a request, it first checks whether the requested
object is cached or not by looking at the hash table.
If not, then ask for the remote site.
Otherwise, the node of requested object in the link list is moved to the
head of the LRU list.

Here my question arises. How does Squid know the position of the
requested object in the link list?
Are there address pointers stored in the hash table?
If it is true, that means each time the link list changes, the hash
table has to be updated?

On the other hand, when squid needs to replace cached objects, it takes
objects from the tail of the LRU list.
Is it correct that each time it takes objects from the list, the
corresponding entries in the hash table has to be deleted?

Thanks a lot,
Regards,
Angus Wong
Received on Sun Jan 16 2000 - 19:06:57 MST