HashSet - Bugfixing

Wie das immer so ist: man programmiert was, was mal mehr als drei Zeilen hat und schon geht's schief. In dem HashSet von letzter Woche finden sich zwei hässliche kleine Bugs, die ein korrektes Löschen und Wiedereinfügen von Elementen unmöglich machen.

Video

Quellcode

[...]
  void insert(T const &element)
  {
    auto position = internalFind(element, true);
    if (position == end()) {
      rehash();
      position = internalFind(element, true);
    }
    position.holder().elem.reset(new T(element));
    position.holder().deleted = false;
  }
[...]
private:
  
  iterator internalFind(T const &key, bool withEmpty)
  {
    auto hashCode = mHash(key);
    auto position = begin() + (hashCode % mElements.size());
    auto candidate = position;
    auto firstFree = end();
    while (true) {
      if (candidate.holder().empty()) {
	if (withEmpty) {
	  if (firstFree == end()) {
	    firstFree = candidate;
	  }
	  if (!candidate.holder().deleted) {
	    return firstFree;
	  }
	}
	else {
	  if (!candidate.holder().deleted) {
	    return end();  // Element ist nicht vorhanden
	  }
	}
      }
      else {
	if (mEqual(*candidate, key)) {
	  return candidate;
	}
      }
      if (withEmpty) {
	candidate.nextSlot();
      }
      else {
	++candidate;
      }
      if (candidate == position) {
	// eine Runde rum -> nicht gefunden
	return firstFree; // end(), wenn keine freie Position zwischendurch gefunden wurde
      }
    }
  }
[...]

Erkärung

Die erste Korrektur findet sich in Zeile 10 des Quellcodeschnipsels oben: die im HashSet abgelegten ElemHolder-Objekte werden beim Löschen eines Objektes ja als deleted markiert, damit die Optimierung mit dem verfrühten Abbruch der Sondierung auch mit gelöschten Objekten noch funktioniert. Dummerweise wird im Originalcode vom letzten Mal das deleted-Flag nicht zurückgesetzt, so dass zwar die Daten im Set gespeichert sind, aber niemals wiedergefunden werden, da der Iterator solche als deleted markierte Elemente überspringt.

Hat man diesen Fehler behoben, so tritt ein anderer zu Tage. Durch eine ungünstige Kombination aus Hash-Kollosionen, Lösch- und Einfügeoperationen kann es dazu kommen, dass Elemente doppelt eingefügt werden können. Das kann immer dann passieren, wenn zwei Elemente A & B kollidieren. Wird A vor B eingefügt (B liegt also in der Sondierungskette hinter A), dann wieder gelöscht und schließlich wird nochmal versucht, B einzufügen, dann landet B auf der als gelöscht markierten Stelle, an der A früher stand. Die Tatsache, dass in der Sondierungskette weiter hinten bereits ein B steht, wird nicht beachtet. So hat man dann B doppelt im Set.

Die Korrektur dieses Fehlers ist in der Grundidee simpel: wir gehen die Sondierungskette von B bis zum Abbruchkriterium durch (entweder erfolgt der Abbruch durch ein echt leeres Element oder weil wir einmal um das HashSet rum sind) und merken uns dabei die erste freie Stelle (über die Variable firstFree). Kann B innerhalb der Kette nicht gefunden werden, so liefern wir diese freie Stelle zurück.