| 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 |
;; |