1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
type ('a,'b) elt = {
key: 'a;
data: 'b;
time: float
}
type ('a, 'b) t = ('a, 'b) elt option array
let create size = Array.create size None
let find_pos t key =
let found = ref 0 in
try
for i = 0 to (Array.length t - 1) do
match t.(i) with
| None -> ()
| Some {key= key'} when key = key' ->
found := i; raise Exit
| _ -> ()
done;
raise Not_found
with
| Exit -> !found
;;
let find t key =
match t.(find_pos t key) with Some elt -> elt.data | _ -> assert false
;;
let rename t key newkey =
try
let pos = find_pos t key in
let data = match t.(pos) with Some d -> d | _ -> assert false in
t.(pos) <- Some {data with key= newkey}
with
| Not_found -> ()
;;
let find_empty_or_eldest t =
let found = ref None in
begin try
for i = 0 to (Array.length t - 1) do
match t.(i) with
| None -> found := Some (i,None); raise Exit
| Some elt ->
match !found with
| None ->
found := Some (i, Some elt)
| Some (j, Some elt') when elt.time < elt'.time ->
found := Some (i, Some elt)
| _ -> ()
done
with Exit -> () end;
match !found with
| Some (i,_) -> i
| None -> raise Not_found
;;
let add t key data =
let slot =
try find_pos t key with Not_found ->
try find_empty_or_eldest t with Not_found -> 0
in
t.(slot) <- Some {key= key; data= data; time= Unix.time ()}
;;
|
