Bugzilla

The LRU tracker re-implements the idea of a free list so it works the same way for cells that are not in use.

Cells that _are_ in use implement a doubly linked list.  Each cell has a `next` and `prev` field plus a payload. The list can be traversed in both directions starting at `head` or `tail`; `head` is the oldest, least recently used item, and `tail` the most recently used.  Thus to `touch` an element and make it the MRU, it's unlinked from the double list and re-linked as the new `tail`.

To be able to do this, you need to know where the item that you want to touch currently is, so for this reason the `entries` array holds both the data that we're trying to manage in LRU fashion, and an index into the LRU tracker's items. (`entries` is a FreeList as well).

In the other direction, removing LRU items means starting a traversal at `head` and removing elements. They also need to be removed from the actual `entries`, so there's a pointer in the other direction: the `free list handle` payload in each LRU tracker element is a handle that points back to the `entries`.

The LRU tracker re-implements the idea of a free list so it works the same way for cells that are not in use.

Cells that _are_ in use implement a doubly linked list.  Each cell has a `next` and `prev` field plus a payload. The list can be traversed in both directions starting at `head` or `tail`; `head` is the oldest, least recently used item, and `tail` the most recently used.  Thus to `touch` an element and make it the MRU, it's unlinked from the double list and re-linked as the new `tail`.

To be able to do this, you need to know where the item that you want to touch currently is, so for this reason the `entries` array holds both the data that we're trying to manage in LRU fashion, and an index into the LRU tracker's items. (`entries` is a FreeList as well).

In the other direction, removing LRU items means starting a traversal at `head` and removing elements. They also need to be removed from the actual `entries`, so there's a pointer in the other direction: the `free list handle` payload in each LRU tracker element is a handle that points back to the `entries`.

To be clear: to implement its FreeList behavior, the LRU tracker re-uses the `next` field from the free-so-unused-next/prev pair.  The "free list handle" that makes up the payload of each element, is only meant to refer back to the `entries` FreeList when LRU items are being popped; it is not itself part of internal list management.