Source file Belt_HashSet.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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
module Int = Belt_HashSetInt
module String = Belt_HashSetString
module N = Belt_internalSetBuckets
module C = Belt_internalBucketsType
module A = Belt_Array

type ('a, 'id) eq = ('a, 'id) Belt_Id.eq
type ('a, 'id) hash = ('a, 'id) Belt_Id.hash
type ('a, 'id) id = ('a, 'id) Belt_Id.hashable
type ('a, 'id) t = (('a, 'id) hash, ('a, 'id) eq, 'a) N.t

let rec copyBucket ~hash ~h_buckets ~ndata_tail old_bucket =
  match C.toOpt old_bucket with
  | None -> ()
  | Some cell ->
      let nidx = (Belt_Id.getHashInternal hash) (N.key cell) land (A.length h_buckets - 1) in
      let v = C.return cell in
      (match C.toOpt (A.getUnsafe ndata_tail nidx) with
      | None -> A.setUnsafe h_buckets nidx v
      | Some tail -> N.nextSet tail v);
      A.setUnsafe ndata_tail nidx v;
      copyBucket ~hash ~h_buckets ~ndata_tail (N.next cell)

let tryDoubleResize ~hash h =
  let odata = C.buckets h in
  let osize = A.length odata in
  let nsize = osize * 2 in
  if nsize >= osize then (
    let h_buckets = A.makeUninitialized nsize in
    C.bucketsSet h h_buckets;
    let rec reinsertBucket bucket =
      match C.toOpt bucket with
      | None -> ()
      | Some cell ->
          let next = N.next cell in
          let index = (Belt_Id.getHashInternal hash) (N.key cell) land (nsize - 1) in
          A.setUnsafe h_buckets index (C.return @@ N.bucket ~key:(N.key cell) ~next:(A.getUnsafe h_buckets index));
          reinsertBucket next
    in
    for i = 0 to osize - 1 do
      reinsertBucket (A.getUnsafe odata i)
    done)

let rec removeBucket ~eq h h_buckets i key prec cell =
  let cell_next = N.next cell in
  if (Belt_Id.getEqInternal eq) (N.key cell) key then (
    N.nextSet prec cell_next;
    C.sizeSet h (C.size h - 1))
  else match C.toOpt cell_next with None -> () | Some cell_next -> removeBucket ~eq h h_buckets i key cell cell_next

let remove h key =
  let eq = C.eq h in
  let h_buckets = C.buckets h in
  let i = (Belt_Id.getHashInternal (C.hash h)) key land (A.length h_buckets - 1) in
  let l = A.getUnsafe h_buckets i in
  match C.toOpt l with
  | None -> ()
  | Some cell -> (
      let next_cell = N.next cell in
      if (Belt_Id.getEqInternal eq) (N.key cell) key then (
        C.sizeSet h (C.size h - 1);
        A.setUnsafe h_buckets i next_cell)
      else
        match C.toOpt next_cell with None -> () | Some next_cell -> removeBucket ~eq h h_buckets i key cell next_cell)

let rec missingInBucket ~eq key cell =
  if (Belt_Id.getEqInternal eq) (N.key cell) key then false
  else match C.toOpt (N.next cell) with None -> true | Some next -> missingInBucket ~eq key next

let add0 h key ~hash ~eq =
  let h_buckets = C.buckets h in
  let buckets_len = A.length h_buckets in
  let i = (Belt_Id.getHashInternal hash) key land (buckets_len - 1) in
  let l = A.getUnsafe h_buckets i in
  (match C.toOpt l with
  | None ->
      C.sizeSet h (C.size h + 1);
      A.setUnsafe h_buckets i (C.return @@ N.bucket ~key ~next:C.emptyOpt)
  | Some cell when missingInBucket ~eq key cell ->
      C.sizeSet h (C.size h + 1);
      A.setUnsafe h_buckets i (C.return @@ N.bucket ~key ~next:l)
  | Some _ -> ());
  if C.size h > buckets_len lsl 1 then tryDoubleResize ~hash h

let add h key = add0 ~hash:(C.hash h) ~eq:(C.eq h) h key

let rec memInBucket ~eq key cell =
  (Belt_Id.getEqInternal eq) (N.key cell) key
  || match C.toOpt (N.next cell) with None -> false | Some nextCell -> memInBucket ~eq key nextCell

let has h key =
  let eq, h_buckets = (C.eq h, C.buckets h) in
  let nid = (Belt_Id.getHashInternal (C.hash h)) key land (A.length h_buckets - 1) in
  let bucket = A.getUnsafe h_buckets nid in
  match C.toOpt bucket with None -> false | Some bucket -> memInBucket ~eq key bucket

let make (type value identity) ~hintSize ~(id : (value, identity) id) =
  let module M = (val id) in
  C.make ~hintSize ~hash:M.hash ~eq:M.eq

let clear = C.clear
let size = C.size
let forEachU = N.forEachU
let forEach = N.forEach
let reduceU = N.reduceU
let reduce = N.reduce
let logStats = N.logStats
let toArray = N.toArray
let copy = N.copy
let getBucketHistogram = N.getBucketHistogram
let isEmpty = C.isEmpty

let fromArray (type a identity) arr ~(id : (a, identity) id) =
  let module M = (val id) in
  let eq, hash = (M.eq, M.hash) in
  let len = A.length arr in
  let v = C.make ~hintSize:len ~hash ~eq in
  for i = 0 to len - 1 do
    add0 ~eq ~hash v (A.getUnsafe arr i)
  done;
  v

let mergeMany h arr =
  let eq, hash = (C.eq h, C.hash h) in
  let len = A.length arr in
  for i = 0 to len - 1 do
    add0 h ~eq ~hash (A.getUnsafe arr i)
  done