LRU cache: get/put với thay thế phần tử lâu chưa dùng nhất

LRU (least recently used) là chính sách thay thế của cache, TLB và page table: khi đầy, bỏ phần tử lâu nhất chưa được dùng. Đây là câu phỏng vấn thuật toán kinh điển (LeetCode 146). Với kỹ sư DV, nó còn là mô hình tham chiếu cần viết khi verify một cache thật. Bài này viết nó bằng các cấu trúc dữ liệu của SystemVerilog.

class lru_cache;
  int evictions;                                 // số phần tử đã bị loại
  function new(int cap);                         // dung lượng ≥ 1
  function bit  get(int key, output int val);    // trúng: val = giá trị, trả 1, khoá thành "mới dùng nhất";
                                                 //   trượt: val = 0, trả 0
  function void put(int key, int val);           // khoá đã có: cập nhật giá trị, khoá thành mới dùng nhất;
                                                 //   khoá mới: thêm vào; nếu vượt dung lượng thì loại khoá lâu chưa dùng nhất
  function int  size();
  function bit  contains(int key);               // chỉ hỏi: KHÔNG tính là dùng
endclass

Ví dụ, dung lượng 2: