Precomputation of dictionnary hashes and usage of other hashing algorithm than FNV1A

[F3llFr0mTh3Sky]

In bug #149 I suggested that M*Lib should support precomputed hash for reusability purposes, which as I said, would allow faster access to dict entries when the hash could be saved somewhere in the heap instead of being recomputed.
You, P-p-H-d, have implemented this feature that I requested by adding the _prehashed_get function, and I'm very grateful for that. However, I think M*Lib should also have a _prehashed_set_at function so that a generated FNV1A hash would be truly reusable:
without it, for the hash to be reusable, it need to be computed twice, so one time by the _set_at function, and another time out of it.

So for the reasons I just explained, since M*Lib now has the _prehashed_get function, it should also have the _prehashed_set_at function.

I also suggested that since the hash can be stored somewhere and reused from this somewhere, it might be even faster for retrieving entries in a dict that M*Lib could also support collision-less perfect hash algorithms (either static or dynamic ones) instead of comparing both hash and keys. I'd like to get your opinon about it.
Would it be worth it or not?
Also, for instance, if perfect hash would be too complex to implement, could other hashing algorithms than FNV1A be used?
e.g. Cuckoo, Robin Hood, wathever? Would any of them be faster than FNV1A?

[P-p-H-d]

There is this example which may be interesting: https://github.com/P-p-H-d/mlib/blob/master/example/ex-mph.c
To check what can be done with existing infrastructure.

I doubt Cuckoo, Robin Hood hash will be faster than FNV1A. They may provide fewer collision however.

[F3llFr0mTh3Sky]

Well, for now, for me, it's not so much of a big deal to use another hashing algorithm other than FNV1A.
What matters more is that instead of a hash being calculated twice, so the first time before calling _set_at so it can be stored somewhere and then reused, and then by calling _set_at, so something like the following functions should be added to M*Lib dicts so that the hash is calculated only once before calling _prehashed_set_at (and so it is now fully reusable) :

  M_IF(isSet)(                                                                \
    M_P(void, name, _prehashed_push, dict_t map, key_type const key) ,        \
    M_P(void, name, _prehashed_set_at, dict_t map, key_type const key, size_t hash, value_type const value)) \
  {                                                                           \
    M_D1CT_CONTRACT(map);                                                     \
    const m_index_t mask = map->mask;                                         \
    m_index_t p = hash & mask;                                                \
                                                                              \
    /* Test if bucket is not empty ? (50 % likely) */                         \
    if (map->index[p].index != 0) {                                           \
      /* Find the insertion point as the bucket[] is not empty */             \
      m_index_t delPos = (m_index_t) -1;                                      \
      m_index_t s = 1U;                                                       \
      do {                                                                    \
        if (M_UNLIKELY(hash == (map->index[p].hash))) {                       \
          m_index_t d = map->index[p].index;                                  \
          M_ASSERT(d <= map->freelist_count);                                 \
          if (d >= 2 && M_CALL_EQUAL(key_oplist, map->data[d].pair.key, key)) { \
            M_CALL_SET(value_oplist, map->data[d].pair.value, value);         \
            return;                                                           \
          }                                                                   \
        }                                                                     \
        if (map->index[p].index == 1 && delPos == (m_index_t) -1) delPos = p; \
        p = (p + M_D1CT_OA_PROBING(s)) & mask;                                \
      } while (map->index[p].index != 0);                                     \
      if (delPos != (m_index_t) -1) {                                         \
        p = delPos;                                                           \
        map->count_delete --;                                                 \
      }                                                                       \
    }                                                                         \
                                                                              \
    m_index_t d = M_C3(m_d1ct_,name,_get_free_bucket)(map);                   \
    M_CALL_INIT_SET(key_oplist, map->data[d].pair.key, key);                  \
    M_CALL_INIT_SET(value_oplist, map->data[d].pair.value, value);            \
    map->index[p].index = d;                                                  \
    map->index[p].hash  = hash;                                               \
    map->count++;                                                             \
    map->count_delete ++;                                                     \
                                                                              \
    if (M_UNLIKELY (map->count_delete >= map->upper_limit)) {                 \
      m_index_t newSize = map->mask+1;                                        \
      if (map->count > newSize/2) {                                           \
        newSize += newSize;                                                   \
        if (M_UNLIKELY_NOMEM (newSize <= map->mask+1)) {                      \
          M_MEMORY_FULL(char, (size_t)-1);                                    \
        }                                                                     \
      }                                                                       \
      M_F(name,_i_resize_up)M_R(map, newSize, true);                          \
    }                                                                         \
    M_D1CT_CONTRACT(map);                                                     \
  }                                                                           \

[P-p-H-d]

it need to be computed twice, so one time by the _set_at function, and another time out of it.

Today compilers are fully able to factorize this and computes the hash only once despite being called twice.
See https://en.wikipedia.org/wiki/Pure_function

support collision-less perfect hash algorithms (either static or dynamic ones) instead of comparing both hash and keys. I'd like to get your opinon about it.

Well, if you implement collision-less perfect hash algorithms, you'll use basic arrays for this, not hashmap. (See provided example), so modifying the dict data structure is useless for perfect hash.