xref: /netbsd-src/regress/sys/uvm/pdsim/lru.hs (revision dbdfc1f67718729a46cdc36c25659089c7795e78)
1*dbdfc1f6Syamt{-
2*dbdfc1f6Syamt/*	$NetBSD: lru.hs,v 1.1 2006/10/09 12:32:46 yamt Exp $	*/
3*dbdfc1f6Syamt
4*dbdfc1f6Syamt/*-
5*dbdfc1f6Syamt * Copyright (c)2005 YAMAMOTO Takashi,
6*dbdfc1f6Syamt * All rights reserved.
7*dbdfc1f6Syamt *
8*dbdfc1f6Syamt * Redistribution and use in source and binary forms, with or without
9*dbdfc1f6Syamt * modification, are permitted provided that the following conditions
10*dbdfc1f6Syamt * are met:
11*dbdfc1f6Syamt * 1. Redistributions of source code must retain the above copyright
12*dbdfc1f6Syamt *    notice, this list of conditions and the following disclaimer.
13*dbdfc1f6Syamt * 2. Redistributions in binary form must reproduce the above copyright
14*dbdfc1f6Syamt *    notice, this list of conditions and the following disclaimer in the
15*dbdfc1f6Syamt *    documentation and/or other materials provided with the distribution.
16*dbdfc1f6Syamt *
17*dbdfc1f6Syamt * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18*dbdfc1f6Syamt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19*dbdfc1f6Syamt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20*dbdfc1f6Syamt * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21*dbdfc1f6Syamt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22*dbdfc1f6Syamt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23*dbdfc1f6Syamt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24*dbdfc1f6Syamt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25*dbdfc1f6Syamt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26*dbdfc1f6Syamt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27*dbdfc1f6Syamt * SUCH DAMAGE.
28*dbdfc1f6Syamt */
29*dbdfc1f6Syamt-}
30*dbdfc1f6Syamt
31*dbdfc1f6Syamtimport System.Environment
32*dbdfc1f6Syamtimport System.IO
33*dbdfc1f6Syamtimport List
34*dbdfc1f6Syamtimport Maybe
35*dbdfc1f6Syamt
36*dbdfc1f6Syamtcontain x xs = isJust $ find (== x) xs
37*dbdfc1f6Syamt
38*dbdfc1f6Syamtdo_lru1 npg n q qlen [] = (reverse n, q)
39*dbdfc1f6Syamtdo_lru1 npg n q qlen rs@(r:rs2) =
40*dbdfc1f6Syamt	if contain r q then
41*dbdfc1f6Syamt		let
42*dbdfc1f6Syamt			nq = delete r q
43*dbdfc1f6Syamt		in
44*dbdfc1f6Syamt		do_lru1 npg n (r:nq) qlen rs2
45*dbdfc1f6Syamt	else if qlen < npg then
46*dbdfc1f6Syamt		do_lru1 npg (r:n) (r:q) (qlen+1) rs2
47*dbdfc1f6Syamt	else
48*dbdfc1f6Syamt		let
49*dbdfc1f6Syamt			nq = take (qlen-1) q
50*dbdfc1f6Syamt		in
51*dbdfc1f6Syamt		do_lru1 npg (r:n) (r:nq) qlen rs2
52*dbdfc1f6Syamt
53*dbdfc1f6Syamtdo_lru npg rs = fst $ do_lru1 npg [] [] 0 rs
54*dbdfc1f6Syamt
55*dbdfc1f6Syamtmain = do
56*dbdfc1f6Syamt	xs <- getContents
57*dbdfc1f6Syamt	args <- getArgs
58*dbdfc1f6Syamt	let
59*dbdfc1f6Syamt		ls = lines xs
60*dbdfc1f6Syamt		npgs::Int
61*dbdfc1f6Syamt		npgs = read $ args !! 0
62*dbdfc1f6Syamt		pgs::[Int]
63*dbdfc1f6Syamt		pgs = map read ls
64*dbdfc1f6Syamt	mapM_ print $ do_lru npgs pgs
65