class GcingPage implements Comparable<GcingPage> {
        PageReference ref;
        PageInfo pInfo;

        GcingPage(PageReference ref, PageInfo pInfo) {
            this.ref = ref;
            this.pInfo = pInfo;
        }

        long getLastTime() {
            return pInfo.getLastTime();
        }

        @Override
        public int compareTo(GcingPage o) {
            // 不能直接相减，否则可能抛异常: Comparison method violates its general contract!
            return Long.compare(getLastTime(), o.getLastTime());
        }
    }

    private void lru(TransactionEngine te, MemoryManager memoryManager) {
        // 按层级收集node page，单独收集leaf page
        HashMap<Integer, ArrayList<GcingPage>> nodePageMap = new HashMap<>();
        ArrayList<GcingPage> leafPages = new ArrayList<>();
        collect(te, map.getRootPageRef(), leafPages, nodePageMap, 1);

        // leaf page按LastTime从小到大释放
        releaseLeafPages(leafPages, memoryManager);

        // 从最下层的node page开始释放
        if (gcNodePages)
            releaseNodePages(nodePageMap, memoryManager);
    }

    private void collect(TransactionEngine te, PageReference ref, ArrayList<GcingPage> leafPages,
            HashMap<Integer, ArrayList<GcingPage>> nodePageMap, int level) {
        PageInfo pInfo = ref.getPageInfo();
        Page p = pInfo.page;
        if (p != null && p.isNode()) {
            forEachPage(p, childRef -> {
                collect(te, childRef, leafPages, nodePageMap, level + 1);
            });
        }
        if (ref.canGc(te)) {
            if (ref.isNodePage()) {
                if (gcNodePages) {
                    ArrayList<GcingPage> nodePages = nodePageMap.get(level);
                    if (nodePages == null) {
                        nodePages = new ArrayList<>();
                        nodePageMap.put(level, nodePages);
                    }
                    nodePages.add(new GcingPage(ref, pInfo));
                }
            } else {
                leafPages.add(new GcingPage(ref, pInfo));
            }
        }
    }

    private void releaseLeafPages(ArrayList<GcingPage> leafPages, MemoryManager memoryManager) {
        int size = leafPages.size();
        if (size == 0)
            return;
        Collections.sort(leafPages);

        int index = size / 2 + 1;
        // 先释放前一半的page字段和buff字段
        release(leafPages, 0, index, 0);
        // 再释放后一半
        if (memoryManager.needGc()) {
            release(leafPages, index, size, 1); // 先释放page字段
            if (memoryManager.needGc())
                release(leafPages, index, size, 2); // 如果内存依然紧张再释放buff字段
        }
    }

    private void releaseNodePages(HashMap<Integer, ArrayList<GcingPage>> nodePageMap,
            MemoryManager memoryManager) {
        if (!nodePageMap.isEmpty() && memoryManager.needGc()) {
            ArrayList<Integer> levelList = new ArrayList<>(nodePageMap.keySet());
            Collections.sort(levelList);
            for (int i = levelList.size() - 1; i >= 0; i--) {
                ArrayList<GcingPage> nodePages = nodePageMap.get(levelList.get(i));
                int size = nodePages.size();
                if (size > 0) {
                    release(nodePages, 0, size, 1); // 先释放page字段
                    if (memoryManager.needGc())
                        release(nodePages, 0, size, 2); // 如果内存依然紧张再释放buff字段
                }
                if (!memoryManager.needGc())
                    break;
            }
        }
    }

    private void release(ArrayList<GcingPage> list, int startIndex, int endIndex, int gcType) {
        for (int i = startIndex; i < endIndex; i++) {
            GcingPage gp = list.get(i);
            PageInfo pInfoNew = gp.ref.gcPage(gp.pInfo, gcType);
            if (pInfoNew != null)
                gp.pInfo = pInfoNew;
        }
    }

    private void forEachPage(Page p, Consumer<PageReference> action) {<FILL_FUNCTION_BODY>

        PageReference[] children = p.getChildren();
        for (int i = 0, len = children.length; i < len; i++) {
            PageReference childRef = children[i];
            if (childRef != null) {
                action.accept(childRef);
            }
        }
    
<no_super_class>