<commit_before>use mut = "collections"

type _MapCollisions[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  is Array[_MapLeaf[K, V, H]] val

type _MapLeaf[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  is (K, V)

type _MapEntry[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  is (_MapNode[K, V, H] | _MapCollisions[K, V, H] | _MapLeaf[K, V, H])

class val _MapNode[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  let _entries: Array[_MapEntry[K, V, H]] val
  let _nodemap: U32
  let _datamap: U32
  let _level: U8

  new val empty(l: U8) =>
    _entries = recover val
      match l
      | 6 => Array[_MapEntry[K, V, H]](4)
      else
        Array[_MapEntry[K, V, H]](32)
      end
    end
    _nodemap = 0
    _datamap = 0
    _level = l

  new val create(es: Array[_MapEntry[K, V, H]] iso, nm: U32, dm: U32, l: U8) =>
    _entries = consume es
    _nodemap = nm
    _datamap = dm
    _level = l

  fun val apply(hash: U32, key: K): V ? =>
    let idx = _Bits.mask(hash, _level)
    let i = _compressed_index(_nodemap, _datamap, idx)
    if i == -1 then error end
    match _entries(i.usize_unsafe())
    | (_, let v: V) => v
    | let sn: _MapNode[K, V, H] => sn(hash, key)
    | let cn: _MapCollisions[K, V, H] =>
      for l in cn.values() do
        if H.eq(l._1, key) then return l._2 end
      end
      error
    end

  fun val update(
    hash: U32,
    leaf: _MapLeaf[K, V, H])
    : (_MapNode[K, V, H], Bool) ?
  =>
    let idx = _Bits.mask(hash, _level)
    let i = _compressed_index(_nodemap, _datamap, idx)
    if i == -1 then
      let es = recover _entries.clone() end
      let dm = _Bits.set_bit(_datamap, idx)
      let i' = _compressed_index(_nodemap, dm, idx)
      es.insert(i'.usize_unsafe(), leaf)
      (create(consume es, _nodemap, dm, _level), true)
    elseif _Bits.has_bit(_nodemap, idx) then
      if _level == 6 then
        // insert into collision node
        let es = recover _entries.clone() end
        let cs = _entries(i.usize_unsafe()) as _MapCollisions[K, V, H]
        let cs' = recover cs.clone() end
        for (k, v) in cs.pairs() do
          if H.eq(v._1, leaf._1) then
          // update collision
            cs'(k) = leaf
            es(i.usize_unsafe()) = consume cs'
            return (create(consume es, _nodemap, _datamap, _level), false)
          end
        end
        cs'.push(leaf)
        es(i.usize_unsafe()) = consume cs'
        (create(consume es, _nodemap, _datamap, _level), true)
      else
        // insert into sub-node
        let sn = _entries(i.usize_unsafe()) as _MapNode[K, V, H]
        let es = recover _entries.clone() end
        (let sn', _) = sn.update(hash, leaf) as (_MapNode[K, V, H], Bool)
        es(i.usize_unsafe()) = sn'
        (create(consume es, _nodemap, _datamap, _level), true)
      end
    else
      let old = _entries(i.usize_unsafe()) as _MapLeaf[K, V, H]
      if H.eq(old._1, leaf._1) then
        // update leaf
        let es = recover _entries.clone() end
        es(i.usize()) = leaf
        (create(consume es, _nodemap, _datamap, _level), false)<commit_msg>track insert flag on recursive update (#1974)<commit_after>use mut = "collections"

type _MapCollisions[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  is Array[_MapLeaf[K, V, H]] val

type _MapLeaf[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  is (K, V)

type _MapEntry[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  is (_MapNode[K, V, H] | _MapCollisions[K, V, H] | _MapLeaf[K, V, H])

class val _MapNode[K: Any #share, V: Any #share, H: mut.HashFunction[K] val]
  let _entries: Array[_MapEntry[K, V, H]] val
  let _nodemap: U32
  let _datamap: U32
  let _level: U8

  new val empty(l: U8) =>
    _entries = recover val
      match l
      | 6 => Array[_MapEntry[K, V, H]](4)
      else
        Array[_MapEntry[K, V, H]](32)
      end
    end
    _nodemap = 0
    _datamap = 0
    _level = l

  new val create(es: Array[_MapEntry[K, V, H]] iso, nm: U32, dm: U32, l: U8) =>
    _entries = consume es
    _nodemap = nm
    _datamap = dm
    _level = l

  fun val apply(hash: U32, key: K): V ? =>
    let idx = _Bits.mask(hash, _level)
    let i = _compressed_index(_nodemap, _datamap, idx)
    if i == -1 then error end
    match _entries(i.usize_unsafe())
    | (_, let v: V) => v
    | let sn: _MapNode[K, V, H] => sn(hash, key)
    | let cn: _MapCollisions[K, V, H] =>
      for l in cn.values() do
        if H.eq(l._1, key) then return l._2 end
      end
      error
    end

  fun val update(
    hash: U32,
    leaf: _MapLeaf[K, V, H])
    : (_MapNode[K, V, H], Bool) ?
  =>
    let idx = _Bits.mask(hash, _level)
    let i = _compressed_index(_nodemap, _datamap, idx)
    if i == -1 then
      let es = recover _entries.clone() end
      let dm = _Bits.set_bit(_datamap, idx)
      let i' = _compressed_index(_nodemap, dm, idx)
      es.insert(i'.usize_unsafe(), leaf)
      (create(consume es, _nodemap, dm, _level), true)
    elseif _Bits.has_bit(_nodemap, idx) then
      if _level == 6 then
        // insert into collision node
        let es = recover _entries.clone() end
        let cs = _entries(i.usize_unsafe()) as _MapCollisions[K, V, H]
        let cs' = recover cs.clone() end
        for (k, v) in cs.pairs() do
          if H.eq(v._1, leaf._1) then
          // update collision
            cs'(k) = leaf
            es(i.usize_unsafe()) = consume cs'
            return (create(consume es, _nodemap, _datamap, _level), false)
          end
        end
        cs'.push(leaf)
        es(i.usize_unsafe()) = consume cs'
        (create(consume es, _nodemap, _datamap, _level), true)
      else
        // update sub-node
        let sn = _entries(i.usize_unsafe()) as _MapNode[K, V, H]
        let es = recover _entries.clone() end
        (let sn', let u) = sn.update(hash, leaf) as (_MapNode[K, V, H], Bool)
        es(i.usize_unsafe()) = sn'
        (create(consume es, _nodemap, _datamap, _level), u)
      end
    else
      let old = _entries(i.usize_unsafe()) as _MapLeaf[K, V, H]
      if H.eq(old._1, leaf._1) then
        // update leaf
        let es = recover _entries.clone() end
        es(i.usize()) = leaf
        (create(consume es, _nodemap, _datamap, _level), false)
{'fraction_non_alphanumeric': 0.13676986913501438, 'fraction_numerical': 0.01021385253750399, 'mean_word_length': 2.385737439222042, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6880100', 'n_tokens_mistral': 2454, 'n_tokens_neox': 2382, 'n_words': 712}