Einheitliches Mapping

Mit der Einführung von Hashmaps war es nun so weit:

Die Map APIs im GATE Projekt müssen umgestellt werden.

Und dieses Unterfangen war mühsamer als erwartet. Denn inzwischen bauen einige Applikationen darauf auf, die ebenso angepasst werden mussten.

Während C++ mit std::map und seit C++11 mit std::unordered_map jedes beliebige Key-Value Mapping problemlos bewältigen kann, hat man in C genau gar nichts im Standard, was einem hilft.

Natürlich könnte man hier unzählige Fremdbibliotheken einbinden, die alle zu einander inkompatibel sind und einen fetten Rattenschwanz an Abhängigkeiten nachziehen, oder man implementiert dieses Strukturen selbst und achtet auf möglichst viel Unabhängigkeit.

gate_map_t ist seit Anfang des GATE Projektes mit dabei und stellt eine generische Rot-Schwarz-Baum Implementierung bereit, die jedes beliebige Objekt (inklusive Konstruktor- und Destruktor-Funktion) aufnehmen kann.
Im C++ Layer nutzt das gate::Map<KEY, VALUE> Template die C Schnittstelle und macht sie ähnlich wie std::map nutzbar.
Schlüssel und Werte sind dabei direkt in die Baumknoten Objekte eingebaut und die C Iteratoren geben den Zugriff darauf über generische Pointer (void*) zurück, während C++ diese auf die korrekten Typ-Referenzen umwandelt.

Und dann kam die Sequence-Map hinzu, die im Endeffekt nur ein Array von Schlüssel-Wert Paaren ist und deren Auszeichnungsmerkmal das Erhalten der Reihenfolge des Hinzufügens ist.
Hier speichert ein gate_seqmap_t Objekt die Byte Offsets von Schlüssel und Wert in einem Eintrag und im Array wird stets ein ganzer Eintragsblock allokiert, wo die beiden Felder direkt hintereinander liegen.
Iteratoren nutzen dann die Offsets um aus einem Pointer dann zwei zu machen.

In den letzten Tagen kam nach der Implementierung einer Hashfunktion für die meisten GATE Typen eine Hashmap hinzu. Sie führt ein Array von verkürzten Hash-Codes in dem wiederum ein Array von Schlüssel-Wert Paaren liegen kann.

Und genau hier fiel mir mein Fehler auf: Alle Maps speichern Key/Value Paare, aber speichern sie immer anders.
Die Lösung war naheliegend:

Wir brauchen eine gemeinsame Datenstruktur, die alle Maps intern nutzen, damit Iteratoren und Enumeratoren immer die gleiche Schnittstelle zurückliefern können.

gate_mapping_t und gate::Mapping<KEY, VALUE>

Es ist eigentlich nur eine Art Header, der aus zwei Zeigern besteht, nämlich einem void const* key; und einem void* value; und dieser ist der kleinste gemeinsame Nenner aller Formen von Map-Objekten. Die tatsächlichen Daten liegen in der Regel unmittelbar hinter den beiden Zeigern, wenn gleich dieser Header auch zulassen würde, dass die Daten außerhalb der Maps liegen können.

Hilfreich ist das vor allem für Enumeratoren, diese stellen eine einheitliche Form des Auflistens von Containern zur Verfügung und bisher hat jede Map etwas anderes zurückgegeben.
Ab sofort liefen alle Maps einen C Enumerator von gate_mapping_t zurück und der C++ Wrapper castet das wiederum auf gate::Enumerator<gate::Mapping<KEY, VALUE> >

Nun kann man also endlich einheitlich mit allen Key/Value Containern arbeiten.

Zucker für den Debugger

In C++ im Debugging-Modus (NDEBUG oder GATE_DEBUG_MODE) hat nun das Mapping Template einen kleinen Zusatz spendiert bekommen hat, der in etwa so aussieht:

 template<class KEY, class VALUE>
 class Mapping
 {
 private:
 #if defined(GATE_DEBUG_MODE)
   union
   {
     gate_mapping_t        impl;
     struct
    {
      KEY const* key_shadow;
      VALUE const* value_shadow;
    };
  };
#else
  gate_mapping_t        impl;
#endif

Durch den Einsatz von union wird im Template parallel zu den generischen void* Zeigern auch noch eine typisierte Variante sichtbar. Und im Debugger kann man auf diese Weise den Inhalt der Datentypen inspizieren.

Das Schöne dabei ist, dass sich das Speicherlayout des Objektes dabei nicht ändert und man keine Inkompatibilitäten zwischen Debug und Release Variante schafft.

Fazit

Nun, solche “Überarbeitungen” sind mühsam, wenn man zahlreiche andere Codestellen anpassen muss, wo die vorherige Schnittstelle im Einsatz war. Doch es lohnt sich, wenn man nun viel generischer zwischen unterschiedlichen Containertypen hin und her wechseln kann.

Und dass das nun auch in purem C Code möglich ist, freut mich natürlich ganz besonders. Schließlich sind es genau diese Features aus C++, die man in C immer so schmerzlich vermisst.