URL
https://opencores.org/ocsvn/ao486/ao486/trunk
Subversion Repositories ao486
[/] [ao486/] [trunk/] [ao486_tool/] [src/] [ao486/] [utils/] [TreePseudoLRU.java] - Rev 2
Compare with Previous | Blame | View Log
/* * Copyright (c) 2014, Aleksander Osman * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ package ao486.utils; public class TreePseudoLRU { static class Node { Node(Node l, Node r, int index) { this.l = l; this.r = r; this.index = index; } boolean left; int index; Node l, r; } static int find(Node n) { if(n.index != -1) return n.index; if(n.left) { n.left = false; return find(n.l); } else { n.left = true; return find(n.r); } } public static void main(String args[]) throws Exception { long vals[] = new long[32]; long idx = 0; for(int i=0; i<vals.length; i++) vals[i] = idx++; Node n1 = new Node(new Node(null,null, 0), new Node(null,null, 1), -1); Node n2 = new Node(new Node(null,null, 2), new Node(null,null, 3), -1); Node n3 = new Node(new Node(null,null, 4), new Node(null,null, 5), -1); Node n4 = new Node(new Node(null,null, 6), new Node(null,null, 7), -1); Node n5 = new Node(new Node(null,null, 8), new Node(null,null, 9), -1); Node n6 = new Node(new Node(null,null, 10), new Node(null,null, 11), -1); Node n7 = new Node(new Node(null,null, 12), new Node(null,null, 13), -1); Node n8 = new Node(new Node(null,null, 14), new Node(null,null, 15), -1); Node n9 = new Node(new Node(null,null, 16), new Node(null,null, 17), -1); Node n10 = new Node(new Node(null,null, 18), new Node(null,null, 19), -1); Node n11 = new Node(new Node(null,null, 20), new Node(null,null, 21), -1); Node n12 = new Node(new Node(null,null, 22), new Node(null,null, 23), -1); Node n13 = new Node(new Node(null,null, 24), new Node(null,null, 25), -1); Node n14 = new Node(new Node(null,null, 26), new Node(null,null, 27), -1); Node n15 = new Node(new Node(null,null, 28), new Node(null,null, 29), -1); Node n16 = new Node(new Node(null,null, 30), new Node(null,null, 31), -1); Node m1 = new Node(n1,n2, -1); Node m2 = new Node(n3,n4, -1); Node m3 = new Node(n5,n6, -1); Node m4 = new Node(n7,n8, -1); Node m5 = new Node(n9,n10, -1); Node m6 = new Node(n11,n12, -1); Node m7 = new Node(n13,n14, -1); Node m8 = new Node(n15,n16, -1); Node o1 = new Node(m1,m2, -1); Node o2 = new Node(m3,m4, -1); Node o3 = new Node(m5,m6, -1); Node o4 = new Node(m7,m8, -1); Node p1 = new Node(o1,o2, -1); Node p2 = new Node(o3,o4, -1); Node q1 = new Node(p1,p2, -1); int found = 0; int count = 10000; for(int i=0; i<count; i++) { // find minimal long min = Long.MAX_VALUE; for(int j=0; j<vals.length; j++) if(vals[j] < min) min = vals[j]; int index = find(q1); if(vals[index] == min) found++; vals[index] = idx++; } System.out.println((double)found / (double)count); } }