For the ones who didn’t find the LRU in Tracker’s code (and for the ones who where lazy).
Let’s say we will have instances of something called a Statement. Each of those instances is relatively big. But we can recreate them relatively cheap. We will have a huge amount of them. But at any time we only need a handful of them.
The ones that are most recently used are most likely to be needed again soon.
First you make a structure that will hold some administration of the LRU:
typedef struct { Statement *head; Statement *tail; unsigned int size; unsigned int max; } StatementLru;
Then we make the user of a Statement (a view or a model). I’ll be using a Map here. You can in Qt for example use QMap for this. Usually I want relatively fast access based on a key. You could also each time loop the stmt_lru to find the instance you want in useStatement based on something in Statement itself. That would rid yourself of the overhead of a map.
class StatementUser { StatementUser(); ~StatementUser(); void useStatement(KeyType key); private: StatementLru stmt_lru; Map<KeyType, Statement*> stmts; StatementFactory stmt_factory; }
Then we will add to the private fields of the Statement class the members prev and next: We’ll make a circular doubly linked list.
class Statement: QObject { Q_OBJECT ... private: Statement *next; Statement *prev; };
Next we initialize the LRU:
StatementUser::StatementUser() { stmt_lru.max = 500; stmt_lru.size = 0; }
Then we implement using the statements
void StatementUser::useStatement(KeyType key) { Statement *stmt; if (!stmts.get (key, &stmt)) { stmt = stmt_factory.createStatement(key); stmts.insert (key, stmt); /* So the ring looks a bit like this: * * * * .--tail .--head * * | | * * [p-n] -> [p-n] -> [p-n] -> [p-n] * * ^ | * * `- [n-p] <- [n-p] <--------' */ if (stmt_lru.size >= stmt_lru.max) { Statement *new_head; /* We reached max-size of the LRU stmt cache. Destroy current * least recently used (stmt_lru.head) and fix the ring. For * that we take out the current head, and close the ring. * Then we assign head->next as new head. */ new_head = stmt_lru.head->next; auto to_del = stmts.find (stmt_lru.head); stmts.remove (to_del); delete stmt_lru.head; stmt_lru.size--; stmt_lru.head = new_head; } else { if (stmt_lru.size == 0) { stmt_lru.head = stmt; stmt_lru.tail = stmt; } } /* Set the current stmt (which is always new here) as the new tail * (new most recent used). We insert current stmt between head and * current tail, and we set tail to current stmt. */ stmt_lru.size++; stmt->next = stmt_lru.head; stmt_lru.head->prev = stmt; stmt_lru.tail->next = stmt; stmt->prev = stmt_lru.tail; stmt_lru.tail = stmt; } else { if (stmt == stmt_lru.head) { /* Current stmt is least recently used, shift head and tail * of the ring to efficiently make it most recently used. */ stmt_lru.head = stmt_lru.head->next; stmt_lru.tail = stmt_lru.tail->next; } else if (stmt != stmt_lru.tail) { /* Current statement isn't most recently used, make it most * recently used now (less efficient way than above). */ /* Take stmt out of the list and close the ring */ stmt->prev->next = stmt->next; stmt->next->prev = stmt->prev; /* Put stmt as tail (most recent used) */ stmt->next = stmt_lru.head; stmt_lru.head->prev = stmt; stmt->prev = stmt_lru.tail; stmt_lru.tail->next = stmt; stmt_lru.tail = stmt; } /* if (stmt == tail), it's already the most recently used in the * ring, so in this case we do nothing of course */ } /* Use stmt */ return; }
In case StatementUser and Statement form a composition (StatementUser owns Statement, which is what makes most sense), don’t forget to delete the instances in the destructor of StatementUser. In the example’s case we used heap objects. You can loop the stmt_lru or the map here.
StatementUser::~StatementUser() { Map<KeyType, Statement*>::iterator i; for (i = stmts.begin(); i != stmts.end(); ++i) { delete i.value(); } }
