solution

Trong thực tế, một đối tượng thường chứa các trường trỏ tới đối tượng khác. Khi một đối tượng bị giải phóng, nó phải giảm refcount của TẤT CẢ các đối tượng con mà nó tham chiếu — có thể kéo theo một dây chuyền giải phóng khác (cascading free).

Xét $n$ biến gốc (root) đánh số $1..n$, ban đầu tất cả NULL. Có $q$ câu lệnh:

• NEW v x m c_1 c_2 ... c_m: tạo đối tượng mới định danh x (số nguyên dương chưa từng xuất hiện) có $m$ trường, trỏ lần lượt tới các đối tượng ĐANG TỒN TẠI $c_1,\dots,c_m$ (refcount của mỗi $c_i$ tăng 1 do trường này), sau đó gán biến gốc v trỏ tới x (refcount(x) tăng 1 do gán gốc). Nếu v trước đó trỏ tới đối tượng y, refcount(y) giảm 1.
• SET v x: gán biến gốc v trỏ tới đối tượng ĐANG TỒN TẠI x (refcount(x) tăng 1 TRƯỚC), sau đó refcount đối tượng cũ của v (nếu có) giảm 1.
• CLEAR v: gán v = NULL; refcount đối tượng cũ (nếu có) giảm 1.

Mỗi khi refcount của một đối tượng $o$ giảm về $0$: $o$ bị giải phóng; ngay sau đó, với MỖI trường (con) của $o$, refcount của con giảm 1 theo — nếu con nào cũng về $0$ thì lại tiếp tục giải phóng dây chuyền. Khi lan truyền, xét các con theo thứ tự định danh TĂNG DẦN, và xử lý theo cơ chế hàng đợi FIFO (đối tượng được xác định giải phóng trước được xử lý lan truyền trước đối tượng được thêm vào sau).

Đề bảo đảm đồ thị tham chiếu tĩnh cha→con (hình thành khi NEW) không có chu trình (là DAG), và mọi đối tượng được tham chiếu trong $c_i$ hoặc trong SET đảm bảo tại thời điểm đó ĐANG TỒN TẠI (đã tạo và chưa bị giải phóng).

Ví dụ: $n=1$, lệnh NEW 1 1 0 (tạo đối tượng 1, không con), NEW 1 2 1 1 (tạo đối tượng 2 có con là đối tượng 1, root 1 chuyển sang trỏ đối tượng 2), CLEAR 1. Khi CLEAR 1, đối tượng 2 về refcount $0$ nên bị giải phóng, kéo theo refcount đối tượng 1 giảm về $0$ nên cũng bị giải phóng. Thứ tự giải phóng: 2 1.