Re: LRU algorithm

["Peter A. Friend" <octavian@corp.earthlink.net>]

Well, that depends on how fancy you want to get. I use LRU for a cache
of log file descriptors in Apache. It is simply a doubly linked list of
structures. The basic operation is:

o If an oldest item is needed (to be re-used, or whatever), take it from
  the tail of the list.
o Move the old item you just grabbed to the head of the list.
o If you are re-using at item from somewhere in the middle of the list,
  also move it to the head of the list before using it.

The idea is the the items that get "hit" most are going to be at the
head of the list, and the oldest at the tail. This approach may or may
not work for you, as you may not want to do all of the pointer juggling.

As for implementing this in gcc, all that you really have to do is
manipulate the doubly linked list. This structure is discussed at length
in numerous texts, I can suggest some if you like.

BTW, this isn't really a gcc specific question, as this can be done in
any language. Any further discussion should be done privately or on one
of the comp.lang newsgroups.

HTH,

Peter

---
Software Engineer
EarthLink Network

On Thu, 2 Dec 1999, Ben A. Abderrazek wrote:

> 
> Hi all,
> 
> Is any one has a hint  about how to write an LRU algorithm in gcc ?
> 
> I have some variables and I want to find the least recently used.
> 
> 
> Thank you for any help,
> 
> Ben,