container/hash_map.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation 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 General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature hash_map
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# hash_map -- an immutable hash map from keys HK to values V
#
public hash_map(
        public HK type : property.hashable,
        public V  type,
        ks Sequence HK,
        vs Sequence V) : container.Map HK V
  pre
    debug   : ks.count        = vs.count
    debug 2 : ks.unique.count = ks.count
    debug   : ks.count.as_u64 <= (hash_map HK V).max_size  # we impose a max. size due to our collision avoidance algorithm
is

  # maximum size
  #
  public type.max_size u64 => 100_000_000_000_000_000

  # number of entries in this map
  #
  public redef size i32 := ks.count


  # size of allocated contents array, allows for some empty slots
  #
  allocated_size => size * 2


  # calculate the index of k within contents array in case of no conflict
  #
  at (h u64) => h % allocated_size.as_u64


  # in case of a collision at given position,
  # return the next alternative position to check
  #
  collision (at u64, h u64) =>
    # a simple collision avoidance would just advance to the next cell. This, however, is problematic
    # in case the hash function produces values that are close to one another: Assume
    #
    #  hash k1 = 7
    #  hash k2 = 7
    #  hash k3 = 8
    #  hash k4 = 7
    #  hash k5 = 8
    #
    # then, we have collisions for 7 and 8, but adding 1 results in k1/k2/k3 colliding also with k3/k5.
    #
    # To avoid this, we instead advance by p that depends on `h`:
    #
    # In case of a collision, we advance by a prime number p of cells which p > allocated_size.  Then,
    # since p % allocated_size != 0, repeated addition of p will not return to the same cell before all
    # cells were visited.
    #
    # And, neighboring hash values like `7` and `8` as above would not result in clusters of collisions.
    #
    # However, neighboring hash values that differ by `primes.count` will cause collisions.  This is
    # why we chose a prime for `primes.count` (31) to keep this unlikely.
    #
    p := prime h
    check
      debug: size.as_u64 <= p
    (at + p) % allocated_size.as_u64


  # for a given hash code, return a prime number larger than `max_size`
  #
  prime(h) => primes[h % primes.count.as_u64]


  # 31 primes that are all larger than `max_size`, for use in collision handling
  #
  primes
    post
      # NYI: OPTIMIZATION: this post-conditions causes sever performance degradation in the example from #5885, need to check why.
      #
      # debug: result.min.or_panic > (hash_map HK V).max_size
  =>
    cached_primes(p array u64) is
    (cache cached_primes ()->
      ps := [# generated using https://bigprimes.org/
             u64
             904644503766293287,
             273661186099400849,
             334046234297393963,
             741897359597713663,
             397344200611950061,
             569354700928729277,
             122921628140331893,
             798110498943838499,
             397474344583484809,
             454177314234609187,
             160486382462582443,
             894962757252268423,
             239643940612081871,
             659159027127300797,
             263678202614407153,
             467352024101294113,
             962186220974124121,
             305257249802330333,
             629392008633749299,
             913535742779912377,
             253544983966072991,
             704658375926768441,
             954522022665259159,
             143760886812584159,
             398952305741082427,
             482296154841239663,
             241093767448102817,
             322274479876339043,
             983886456891355613,
             234844915899376649,
             859627742854685113]
      check
        debug: ps.min.or_panic > (hash_map HK V).max_size
      cached_primes ps
    ).p


  mi : mutate is

  # the contents
  #
  contents := mi ! ()->
    mcontents := mi.array (option (tuple HK V))
                   .new allocated_size.as_i64 nil
    for
      k in ks
      v in vs
    do
      h := hash k
      store (at h)

      # store k,v for index at,
      store (at u64) unit =>

        match mcontents[at]
          nil     =>     # slot is free, so use it:
            mcontents[at] := (k, v)

          t tuple =>     # we have a conflict
            ek, _ := t
            if ek = k    # no conflict, but remapping of k
              mcontents[at] := (k, v)
            else         # conflict
              store (collision at h)

/* NYI: With better pattern matching, this could be:
        match mcontents[at]
          nil,
          (k, _) =>  mcontent[at] := (k, v)  # no conflict
          (_, _) =>  store collision at      # conflict
*/

    else
      mcontents.as_array


  # get the value k is mapped to
  #
  public redef index [] (k HK) option V =>
    h := hash k

    retrieve (at u64) option V =>
      match contents[at]
        nil     => nil
        t tuple =>
          ek, v := t
          if ek = k
            v
          else
            retrieve (collision at h)

    retrieve (at h)


  # get a list of all key/value pairs in this map
  #
  public redef items Sequence (tuple HK V) =>
    contents
      .filter o->o??
      .map (o -> o.or_else (panic "filter failed"))


  # NYI: implement this when #4642 is done
  # create a mutable map from this
  #
  # public redef as_mutable_map container.Mutable_Map PK V =>


  # empty -- convenience routine to create an empty instance of hash_map
  #
  public fixed redef type.empty container.hash_map HK V =>
    container.hash_map HK V [] []