My copy of Hacker's Delight is at home, and the web resources I've found aren't clear on this detail.
I have written the following 8-level LRU, using the well-known "row-column square" algorithm. (Is there a better name?).
#include <stdint.h>
typedef union {
uint8_t rows[8];
uint64_t cols;
} lru_state;
void lru_init(lru_state *this) {
this->cols=0;
}
void lru_up(lru_state *this, int used /* in 0..7 */) {
this->rows[used]=0xff;
this->cols &= ~(0x0101010101010101 << used);
}
int lru_get(lru_state *this) {
int i;
for (i=1; i<8 ; i++) {
if (0==(this->rows[i])) return i;
}
return 0;
}
I would like confirmation of my assumption that the least-recently-used row will be all zeroes. It seems to work, but I don't have the math to prove it to my satisfaction.
So, is this right? Or do I need to compute the minimum Hamming weight for each row?