Debian Codegraph @

vendor/re/src/hash_set.ml

raw
1 open Import
2
3 module Array = struct
4 type nonrec t = Bytes.t
5
6 let words = 8
7 let[@inline] length t = Bytes.length t / words
8 let[@inline] unsafe_get t i = Int64.to_int (Bytes.get_int64_ne t (i * words))
9 let[@inline] unsafe_set t i x = Bytes.set_int64_ne t (i * words) (Int64.of_int x)
10
11 let[@inline] make len x =
12 let t = Bytes.create (len * words) in
13 for i = 0 to length t - 1 do
14 unsafe_set t i x
15 done;
16 t
17 ;;
18
19 let[@inline] make_absent len = Bytes.make (len * words) '\255'
20 let clear t = Bytes.fill t 0 (Bytes.length t) '\255'
21
22 let fold_left t ~init ~f =
23 let init = ref init in
24 for i = 0 to length t - 1 do
25 init := f !init (unsafe_get t i)
26 done;
27 !init
28 ;;
29 end
30
31 (* A specialized hash table that makes the following trade-offs:
32 - Open addresing. Bucketing is quite memory intensive and dune is already
33 a memory hog.
34 - No boxing for empty slots. We make use of the fact that id's are never
35 negative to achieve this.
36 - No saving of the hash. Recomputing the hash for id's is a no-op.
37 *)
38
39 type nonrec table =
40 { mutable table : Array.t
41 ; mutable size : int
42 }
43
44 type t = table Option.t ref
45
46 let init t =
47 if Option.is_none !t then t := Option.some { size = 0; table = Array.make 0 (-1) };
48 Option.get !t
49 ;;
50
51 let[@inline] should_grow t =
52 let slots = Array.length t.table in
53 slots = 0 || (t.size > 0 && slots / t.size < 2)
54 ;;
55
56 let absent = -1
57
58 let () =
59 let x = Array.make_absent 1 in
60 assert (Array.unsafe_get x 0 = absent)
61 ;;
62
63 let create () = ref Option.none
64
65 let[@inline] index_of_offset slots index i =
66 let i = index + !i in
67 if i >= slots then i - slots else i
68 ;;
69
70 let clear t =
71 match !t with
72 | None -> ()
73 | Some t ->
74 t.size <- 0;
75 Array.clear t.table
76 ;;
77
78 let add t x =
79 let hash = Int.hash x in
80 let slots = Array.length t.table in
81 let index = hash land (slots - 1) in
82 let inserting = ref true in
83 let i = ref 0 in
84 while !inserting do
85 let idx = index_of_offset slots index i in
86 let elem = Array.unsafe_get t.table idx in
87 if elem = absent
88 then (
89 Array.unsafe_set t.table idx x;
90 inserting := false)
91 else incr i
92 done;
93 t.size <- t.size + 1
94 ;;
95
96 let resize t =
97 let old_table = t.table in
98 let slots = Array.length old_table in
99 let table = Array.make_absent (if slots = 0 then 1 else slots lsl 1) in
100 t.table <- table;
101 for i = 0 to slots - 1 do
102 let elem = Array.unsafe_get old_table i in
103 if elem <> absent then add t elem
104 done
105 ;;
106
107 let add t x =
108 let t = init t in
109 if should_grow t then resize t;
110 add t x
111 ;;
112
113 let[@inline] is_empty t =
114 let t = !t in
115 if Option.is_none t
116 then true
117 else (
118 let t = Option.get t in
119 t.size = 0)
120 ;;
121
122 let mem t x =
123 let t = !t in
124 if Option.is_none t || (Option.get t).size = 0
125 then false
126 else (
127 let t = Option.get t in
128 let hash = Int.hash x in
129 let slots = Array.length t.table in
130 let index = hash land (slots - 1) in
131 let i = ref 0 in
132 let found = ref false in
133 while (not !found) && !i < slots do
134 let idx = index_of_offset slots index i in
135 let elem = Array.unsafe_get t.table idx in
136 if Int.equal elem x
137 then found := true
138 else if Int.equal elem absent
139 then i := slots
140 else incr i
141 done;
142 !found)
143 ;;
144
145 let pp fmt t =
146 let { table; size } = init t in
147 let table =
148 Array.fold_left table ~init:[] ~f:(fun acc i -> if i = absent then acc else i :: acc)
149 |> List.rev
150 |> Stdlib.Array.of_list
151 in
152 let table fmt () = Fmt.sexp fmt "table" Fmt.(array int) table in
153 let size fmt () = Fmt.sexp fmt "size" Fmt.int size in
154 Format.fprintf fmt "%a@.%a@." table () size ()
155 ;;