1. bitsquid
  2. foundation
  3. Issues
Issue #5 new

hash::erase() : an array size update is missing

Adrien Cuisinier
created an issue

Hi,

There is a little mistake in hash.h in the "erase" function.

The array size is not update in all cases. If we erase an item in the hash which is not stored at the end of the array, the size is not updated.

Here is a possible correction.

    template<typename T> void erase(Hash<T> &h, const FindResult &fr)
    {
      if (fr.data_prev == END_OF_LIST)
        h._buckets[fr.hash_i] = h._data[fr.data_i].next;
      else
        h._data[fr.data_prev].next = h._data[fr.data_i].next;

      array::pop_back(h._data);

      if (fr.data_i == array::size(h._data)) return;

      h._data[fr.data_i] = h._data[array::size(h._data)];

      FindResult last = find(h, h._data[fr.data_i].key);

      if (last.data_prev != END_OF_LIST)
        h._data[last.data_prev].next = fr.data_i;
      else
        h._buckets[last.hash_i] = fr.data_i;
    }

Thank you for sharing so much and with such quality ! You are awesome :D

Comments (1)

  1. Mathieu Capdegelle

    Hi, another thing is that you should use the overloaded "find" function that takes a pointer to get the last find result, or magical things happen with multi hashes.

    ...
      FindResult last = find(h, &h._data[array::size(h._data)]);
      if (last.data_prev != END_OF_LIST)
        h._data[last.data_prev].next = fr.data_i;
      else
        h._hash[last.hash_i] = fr.data_i;
    }
    
  2. Log in to comment