package codex

You can search for identifiers within the package.

in-package search v0.2.0

The Codex library for building static analysers based on abstract interpretation

Install

dune-project

Dependency

codex.top Edit opam file Versions (1)

Authors

Maintainers

M

Matthieu Lemerre <matthieu.lemerre@cea.fr>

Sources

1.0-rc4.tar.gz

md5=bc7266a140c6886add673ede90e335d3

sha512=8da42c0ff2c1098c5f9cb2b5b43b306faf7ac93b8f5ae00c176918cee761f249ff45b29309f31a05bbcf6312304f86a0d5a000eb3f1094d3d3c2b9b4c7f5c386

doc/src/codex.smallmap/smallmap.ml.html

Source file `smallmap.ml`

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
(**************************************************************************)
(*  This file is part of the Codex semantics library.                     *)
(*                                                                        *)
(*  Copyright (C) 2013-2025                                               *)
(*    CEA (Commissariat à l'énergie atomique et aux énergies              *)
(*         alternatives)                                                  *)
(*                                                                        *)
(*  you can redistribute it and/or modify it under the terms of the GNU   *)
(*  Lesser General Public License as published by the Free Software       *)
(*  Foundation, version 2.1.                                              *)
(*                                                                        *)
(*  It is distributed in the hope that it will be useful,                 *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *)
(*  GNU Lesser General Public License for more details.                   *)
(*                                                                        *)
(*  See the GNU Lesser General Public License version 2.1                 *)
(*  for more details (enclosed in the file LICENSE).                      *)
(*                                                                        *)
(**************************************************************************)

(* Memory-efficient replacement for maps, useful when we have a lot of
   small maps. *)
module Make(Key:Map.OrderedType) = struct
  module M = Map.Make(Key)

  type key = Key.t
           
  (* Small maps, with keys in increasing order.*)
  type 'a t =
    | Empty
    | One of {key1:Key.t;value1:'a}
    | Two of {key1:Key.t;value1:'a;key2:Key.t;value2:'a}
    | Three of {key1:Key.t;value1:'a;
                key2:Key.t;value2:'a;
                key3:Key.t;value3:'a;                
               }
    | Large of 'a M.t
  ;;

  let find key map = match map with
    | Empty -> raise Not_found
    | One{key1;value1} ->
       if Key.compare key key1 = 0 then value1
       else raise Not_found
    | Two{key1;value1;key2;value2} ->
       begin match Key.compare key key1 with
       | 0 -> value1
       | x when (* x > 0 && *) Key.compare key key2 = 0 -> value2
       | _ -> raise Not_found
       end
    | Three{key1;value1;key2;value2;key3;value3} ->
       begin match Key.compare key key2 with
       | 0 -> value2
       | x when x < 0 ->
          if Key.compare key key1 = 0 then value1 else raise Not_found
       | _ ->
          if Key.compare key key3 = 0 then value3 else raise Not_found
       end
       (* begin
        * if Key.compare key key1 = 0 then value1
        * else if Key.compare key key2 = 0 then value2
        * else if Key.compare key key3 = 0 then value3
        * else raise Not_found *)
    | Large m -> M.find key m
  ;;

  let bindings = function
    | Empty -> []
    | One{key1;value1} -> [(key1,value1)]
    | Two{key1;value1;key2;value2} -> [(key1,value1);(key2,value2)]
    | Three{key1;value1;key2;value2;key3;value3} -> [(key1,value1);(key2,value2);(key3,value3)]
    | Large m -> M.bindings m

  let fold f m init = match m with
    | Empty -> init
    | One{key1;value1} -> f key1 value1 init
    | Two{key1;value1;key2;value2} -> f key2 value2 @@ f key1 value1 init
    | Three{key1;value1;key2;value2;key3;value3} ->
       f key3 value3 @@ f key2 value2 @@ f key1 value1 init
    | Large m -> M.fold f m init

  let add key value map = match map with
    | Empty -> One{key1=key;value1=value}
    | One{key1;value1} -> begin
       match Key.compare key key1 with
       | 0 -> One{key1;value1=value}
       | x when x < 0 -> Two{key1=key;value1=value;key2=key1;value2=value1}
       | _ -> Two{key1;value1;key2=key;value2=value}
      end
    | Two{key1;value1;key2;value2} -> begin
        match Key.compare key key1 with
        | 0 -> Two{key1;value1=value;key2;value2}
        | x when x < 0 -> Three{key1=key;value1=value;key2=key1;value2=value1;key3=key2;value3=value2}
        | _ -> begin match Key.compare key key2 with
               | 0 -> Two{key1;value1;key2;value2=value}
               | x when x < 0 -> Three{key1;value1;key2=key;value2=value;key3=key2;value3=value2}
               | _ -> Three{key1;value1;key2;value2;key3=key;value3=value}
               end
      end
    | Three{key1;value1;key2;value2;key3;value3} -> begin
        match Key.compare key key2 with
        | 0 -> Three{key1;value1;key2;value2=value;key3;value3}
        | x when x < 0 && Key.compare key key1 = 0 -> Three{key1;value1=value;key2;value2;key3;value3}
        | x when x > 0 && Key.compare key key3 = 0 -> Three{key1;value1;key2;value2;key3;value3=value}
        | _ ->
           Large (M.add key value @@ M.add key3 value3 @@ M.add key2 value2 @@ M.singleton key1 value1)
      end
    | Large m -> Large (M.add key value m)
  ;;

  let empty = Empty
               
end