Memory Leak bei STD::Map

Hymir90

Hy @ all,
ich habe ein sehr seltsames Problem. Da meines Erachtens nach es leider in der STL keine HashMap gibt, hab ich mich mal daran versucht eine ganz simple Hashmap zu schreiben.
Soweit bin ich bis jetzt:

stringutils.hh

#ifndef stringutils_hpp
    #define stringutils_hpp

    #include <string.h>
    #include <string>
    #include <iostream>
    #include <sstream>

    namespace stringutils{
      using namespace std;
      /**
         hashSDBM
         wandelt char* in Hashwert (SDBM - Algorithmus)
         @param strToHash            zu hashender String
         @return Hashwert
      */
      unsigned long& hashSDBM(char *strToHash){
          static unsigned long hash;
          hash = 0;          
          unsigned char* str = new unsigned char[strlen(strToHash) + 1];
          strncpy( (char *) str, strToHash, strlen(strToHash) );

          int i = 0;

          while(str[i]){
            hash = str[i] + (hash <<6) + (hash <<16) - hash;
            ++i;
          }
          delete [] str;

          return (hash);
      }
    }

#endif

Die Funktion HashSDBM soll eigentlich nichts weiter tun, als einen string zu hashen. Das klappt an sich auch schon recht gut!

Jetzt gehts ans eingemacht!

hashmap.hh

#ifndef hashmap_hh
  #define hashmap_hh

  #include <map>
  #include <iostream>
  #include <cstring>
  #include "stringutils.hh"

  namespace{

    using namespace std;

    class MapElement{

	    private:
		    string *filename;
		    string *path;

	    public:
		    MapElement(string *f, string *p):filename(f), path(p){}
			~MapElement(){
			  cerr<<"Desktruktor: MapElement ["<<*filename<<","<<*path<<"] wird aufgerufen"<<endl;
			  delete filename;
			  delete path;
			}
		    string getFileName(){ return *filename; }
		    string getPath(){ return *path; }

    };

    class HashMap{

	    private:
		    map<unsigned long, MapElement*> *hm;

		    unsigned long& hash(string *key);

	    public:
			HashMap(){
			  hm = new map<unsigned long, MapElement*>(); //auf dem Heap allozieren, da sehr gross werden kann
			}
			~HashMap(){
			  cerr<<"Destruktor von HashMap wird aufgerufen"<<endl;
			  map<unsigned long, MapElement*>::iterator it;
			  for(it = hm->begin(); it != hm->end(); ++it){
				delete ((*it).second);
			  }
			  delete hm;
			}
		    unsigned long put(string *k, MapElement *v);

    };

    unsigned long& HashMap::hash(string *key){
      char * buffer = new char[(*key).length()+1];
      strncpy(buffer, (*key).c_str(), (*key).length());
      static unsigned long result;      
      result = stringutils::hashSDBM(buffer);
      delete [] buffer;
      return (result);
    }

    unsigned long HashMap::put(string *k, MapElement *v){
		unsigned long key = hash(k);

		map<unsigned long, MapElement*>::iterator it = hm->find(key);  

		if(it==hm->end()){
		hm->insert(std::pair<unsigned long, MapElement*>(key, v));

		cerr<<"INSERTED "<<key<<endl;
		return 0;
		}else{
		cerr<<"Gabs schon: "<<v->getFileName()<<endl;      
		return key;
		}      
    }
  }
#endif

soweit so gut.

Das ganze teste ich in der test.cc:

#include "map.hh"
#include "stringutils.hh"

#include <iostream>

  HashMap *hm = new HashMap();

  int main(void){

    MapElement *m1; 

    string *a = new string("hello");
    string *b = new string("world");
    m1 = new MapElement(a,b);
    hm->put(a, m1);

    string *c = new string("thats");
    string *d = new string("a test");
    m1 = new MapElement(c,d);
    hm->put(c, m1);

    string *e = new string("hello");
    string *f = new string("test");
    m1 = new MapElement(e,f);
    hm->put(e, m1);

    delete hm;

    return 0;
  }

alles kompiliert einwandfrei und fuehrt auch alles super aus (<hello, world>; <thats, a test>) wird hinzugefügt, bei <hello, test> beschwert er sich, da es den key "hello" schon gibt!

Also alles in allem sieht es relativ gut aus! Wenn ich JETZT aber das binary mit valgrind unter die Lupe nehme wird mir ein Memory Leak angezeigt!

Der komplette Auszug von valgrind folgt:

valgrind --leak-check=full --track-origins=yes ./shell 2>&1 > valgrind.txt
==8060== Memcheck, a memory error detector
==8060== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==8060== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==8060== Command: ./shell
==8060==
==8060== Conditional jump or move depends on uninitialised value(s)
==8060== at 0x4C2BFB8: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401376: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x401F87: main (in dev/map)
==8060== Uninitialised value was created by a heap allocation
==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401CCC: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x401F87: main (in dev/map)
==8060==
==8060== Conditional jump or move depends on uninitialised value(s)
==8060== at 0x4C2BFB8: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401392: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x401F87: main (in dev/map)
==8060== Uninitialised value was created by a heap allocation
==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401CCC: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x401F87: main (in dev/map)
==8060==
==8060== Conditional jump or move depends on uninitialised value(s)
==8060== at 0x40140B: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x401F87: main (in dev/map)
==8060== Uninitialised value was created by a heap allocation
==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401382: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x401F87: main (in dev/map)
==8060==
INSERTED 7416051667693574450
==8060== Conditional jump or move depends on uninitialised value(s)
==8060== at 0x40140B: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x40203F: main (in dev/map)
==8060== Uninitialised value was created by a heap allocation
==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401382: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x40203F: main (in dev/map)
==8060==
INSERTED 8269306963433084652
==8060== Conditional jump or move depends on uninitialised value(s)
==8060== at 0x40140B: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x4020F7: main (in dev/map)
==8060== Uninitialised value was created by a heap allocation
==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x401382: stringutils::hashSDBM(char*) (in dev/map)
==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
==8060== by 0x4020F7: main (in dev/map)
==8060==
Gabs schon: hello
Destruktor von HashMap wird aufgerufen
Desktruktor: MapElement [hello,world] wird aufgerufen
Desktruktor: MapElement [thats,a test] wird aufgerufen
==8060==
==8060== HEAP SUMMARY:
==8060== in use at exit: 91 bytes in 5 blocks
==8060== total heap usage: 25 allocs, 20 frees, 464 bytes allocated
==8060==
==8060== 91 (16 direct, 75 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 5
==8060== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8060== by 0x4020C3: main (in dev/map)
==8060==
==8060== LEAK SUMMARY:
==8060== definitely lost: 16 bytes in 1 blocks
==8060== indirectly lost: 75 bytes in 4 blocks
==8060== possibly lost: 0 bytes in 0 blocks
==8060== still reachable: 0 bytes in 0 blocks
==8060== suppressed: 0 bytes in 0 blocks
==8060==
==8060== For counts of detected and suppressed errors, rerun with: -v
==8060== ERROR SUMMARY: 10 errors from 6 contexts (suppressed: 2 from 2)

Also wenn ich die Meldung von valgrind richtig interpretiere, werden die longs für die Map (OHNE MEIN ZUTUN -_-) auf dem Heap allokiert und selbstredend später nicht mehr freigegeben!

Hat irgendjemand eine Idee, wo mein Fehler ist, beziehungsweiße was ich besser machen kann?! Ich verzweifle hier nämlich bald und hab das ungute Gefühl das ich einfach den Wald vor lauter Bäumen nicht sehe!!!

Ich bedanke mich bereits im Vorraus für eure Hilfe und eure Zeit!

MfG

Hymir

daddy_felix

Du hast die Regel der drei verletzt.

vielleicht sind da noch mehr Fehler, aber immer einen Schritt nach dem anderen.

Hymir90

Du hast die Regel der drei verletzt.

? was heißt das denn? =O

http://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)

Hymir90

ich sollte also noch ne copy operator und nen operator= schreiben und das sollte das problem lösen?
=O

Beim schnellen drüber schauen ist mir aufgefallen, dass Du die map mit new anlegst, mit dem Kommentar, dass sie sehr groß werden kann und Du sie daher auf dem Heap anlegen möchtest. Die map selbst verwaltet aber bereits seine Daten auf dem Heap. Selbst wenn sie groß wird, wird nicht mehr Stack verbraucht. Sonst müsste er ja dynamisch Stack verbrauchen, was ja eben nicht geht.

Außerdem wozu kopierst Du in der Hash-Funktion Deine Daten? Du kannst direkt über strToHash iterieren. Und warum wird der String als char* und nicht als const char* übergeben? Oder besser noch als const std::string&. Der Rückgabewert ist auch sehr merkwürdig. Du kannst direkt den Hash-Wert als unsigned long liefern, statt eine konstante Referenz. Dann brauchst Du auch keine statische Instanz von Deinem unsigned long, die sowieso fehlerhaft ist, da der Wert bei jedem Aufruf überschrieben wird.

Bei Zeiger auf std::string wird mir übel. Entweder klassisch mit const char* oder gleich einfach std::string, aber Zeiger auf std::string ist eigentlich immer falsch.

string *a = new string("hello");

ist einfach nur falsch. Einfacher, sicherere und schneller ist das:

string a = "hello"

Da ist kein Speicherleck und der Code ist weitaus lesbarer.

Dass Du bei diesen Zeigerwust Speicherlecks hast, wundert mich so rein gar nicht.

Wenn ich noch weiter schauen würde, würde ich sicher noch viel mehr finden. Aber wie daddy_felix auch sagt: ein Schritt nach dem anderen.

daddy_felix

Hymir90 schrieb:

ich sollte also noch ne copy operator und nen operator= schreiben und das sollte das problem lösen?
=O

es löst auf jeden Fall einige Probleme. Ob es alle sind, wirst du dann ja sehen

Hymir90 schrieb:

ich sollte also noch ne copy operator und nen operator= schreiben und das sollte das problem lösen?
=O

Ne, das glaube ich nicht. Aber hier stellen sich so viele Fragen, z.B. wieso dynamische Speicherverwaltung mit new, wieso rohe Zeiger, wieso reinterpreter-Casts, wieso dynamische Arrays mit new[], wieso ist der Value der map ein roher Zeiger, wieso kommt da nirgendwo const vor Fragen über Frange. All das zusammen führt zu deinen Bugs.

pumuckl

stringutils.hh

warum .hh als Endung? Ist eher ungewöhnlich. .h oder .hpp, seltener .hxx
warum benutzt du <string.h>? (Der C++-Header hieße <cstring>, wenn du die C-String Funktionen brauchst)
using namespace std auf namespace-Ebene in einem header - vielleicht keine gute Idee
wozu das temporäre char-array str in der Funktion? den hash kannst du genauso auf dem übergebene array berechnen.
warum char* als Parameter und nicht char const*, wenn du das übergebene char-Array nicht änderst?
warum eine statische Variable hash und als Rückgabe eine Referenz darauf???? Das schreit nach verrücktem, unerwarteten Verhalten
wozu <iostream>, <sstream> und <string> einbinden, wenn du sie nicht nutzt?
warum ist die Funktion nicht inline definiert? Damit hast du eine ODR-Verletzung, sobald du den header in mehr als einer Übersetzungseinheit einbindest.

hashmap.hh
9) Warum wirfst du überall mit Pointern um dich? Das sieht schonmal arg nach Java-Abkömmling aus, und da wundert es nicht mehr, warum du überall memleaks hast. Zumal du dann bei den Gettern von MapElement plötzlich Kopien zurück gibst, was wiederum absolut unnötig ist.
10) MapElement übernimmt offenbar den Besitz von filename und path (löscht sie zumindest im DTor). Da du aber keinen op= und keinen Copy-Ctor erstellt hast, läufst du wenn du das Ding an eine std::map übergibst schneller auf double deletes als du "huch" sagen kannst.

Da gibts noch viele weitere Punkte, aber nach der Pointerschlacht hab ich aufgegeben, weiter zu schauen. Mein Fazit: Dass du memleaks hast, ist nicht verwunderlich. Verwunderlich ist eher, dass Programm soweit durchläuft, dass valgrind dir irgendwas sagen kann, bevor dir das ganze Ding um die Ohren fliegt. Ich empfehle dringend, dich vom Referenz-Denken aus Java (oder C# oder woher auch immer du das hast) zu lösen und mit einem guten C++-Buch die Grundlagen zu erarbeiten.

Hymir90

jawohl jawohl, ich gebs ja zu! ^^ Ich komm aus der Java-Ecke und hab grad echte Probleme mit den Pointern usw. Danke erstmal für die vielen Antworten. Ich werde mir das mal in Ruhe anschauen!

MfG

SeppJ

Man sollte mal erwähnen, dass die ganze Prämisse bezüglich einer fehlenden Hashmap falsch ist:
http://en.wikipedia.org/wiki/Unordered_associative_containers_(C%2B%2B)#History

Kellerautomat

Mal abgesehen hat C++ bereits eine Hashmap. std::unordered_map.

Edit: Ach Mist, zu langsam

Hymir90 schrieb:

jawohl jawohl, ich gebs ja zu! ^^ Ich komm aus der Java-Ecke und hab grad echte Probleme mit den Pointern usw. Danke erstmal für die vielen Antworten. Ich werde mir das mal in Ruhe anschauen!

Das macht aber gar nichts. Zeiger brauchst du in C++ nur selten. Deswegen kannst du Zeiger erstmal aus deinem Kopf streichen.

pumuckl

In Boost und der C++11-Bibliothek gibts übrigens eine unordered_map, dürfte in deine Richtung gehen

Wie deine Hashfunktion aussehen könnte:

#ifndef stringutils_hpp
#define stringutils_hpp

namespace stringutils{
  /**
     hashSDBM
     wandelt char* in Hashwert (SDBM - Algorithmus)
     @param strToHash            zu hashender String
     @return Hashwert
  */
  unsigned long hashSDBM(char const* strToHash){
    unsigned long hash = 0;
    for(;*strToHash;++strToHash)
      hash = *strToHash + (hash <<6) + (hash <<16) - hash;
    return hash;
    }

#endif

Wobei ich nicht sicher bin, ob das so klug ist, char* als Parameter zu haben, wenn hash ein unsigned long ist. char ist nicht notwendigerweise unsigned, so dass folgendes z.B. Murks erzeugt:
hashSDBM("\x80") -> \x80 = (char)128 = -128 für signed char
-> hash = -128 + (0<<6) + (0<<16) - 0 = -128 -> Unterlauf
Ein Compiler sollte da auch eine Warnung bzgl. signed/unsigned mismatch liefern

TyRoXx

pumuckl schrieb:

Wobei ich nicht sicher bin, ob das so klug ist, char* als Parameter zu haben, wenn hash ein unsigned long ist. char ist nicht notwendigerweise unsigned, so dass folgendes z.B. Murks erzeugt:
hashSDBM("\x80") -> \x80 = (char)128 = -128 für signed char
-> hash = -128 + (0<<6) + (0<<16) - 0 = -128 -> Unterlauf
Ein Compiler sollte da auch eine Warnung bzgl. signed/unsigned mismatch liefern

An welcher Stelle genau soll es da eine Warnung geben und warum?
Würde static_cast<unsigned char>(*strToHash) deine hypothetische Warnung verstummen lassen?

@Hymir90: Informiere dich, was tatsächlich eine Hash Map ist und tut. Dein Ansatz verwendet den Hash als eindeutigen Schlüssel für die std::map , obwohl natürlich mehrere Elemente den gleichen Hash haben können. Außerdem hat eine Hash Map typischerweise konstante Such- und Einfügezeit, nicht logarithmische wie std::map .

out schrieb:

Hymir90 schrieb:

jawohl jawohl, ich gebs ja zu! ^^ Ich komm aus der Java-Ecke und hab grad echte Probleme mit den Pointern usw. Danke erstmal für die vielen Antworten. Ich werde mir das mal in Ruhe anschauen!

Das macht aber gar nichts. Zeiger brauchst du in C++ nur selten. Deswegen kannst du Zeiger erstmal aus deinem Kopf streichen.

Ach ja? Wie macht ihr dass wenn ihr Referenzen auf Objekte oder sogar Listen mit Referenzen auf Objekte braucht?

SeppJ

Butterbrot schrieb:

Das macht aber gar nichts. Zeiger brauchst du in C++ nur selten. Deswegen kannst du Zeiger erstmal aus deinem Kopf streichen.

Ach ja? Wie macht ihr dass wenn ihr Referenzen auf Objekte oder sogar Listen mit Referenzen auf Objekte braucht?

Mit Pointern. Aber das brauche ich nur selten.

otze

Butterbrot schrieb:

Ach ja? Wie macht ihr dass wenn ihr Referenzen auf Objekte oder sogar Listen mit Referenzen auf Objekte braucht?

Referenzen auf Objekte -> Referenzen. Letzteres kommt so gut wie nie vor ud wird meistens durch Iteratoren ersetzt.

//und und bei den wenigen Fällen die übrig bleiben Pointer. Aber dann hängt da meistens keine Speicherverwaltung mit dran.

Ich Frage nur weil ich mich gerade mit Design Patterns beschäftige und dort ständig Pointer einsetze, dann mache ich wohl was falsch. Kann man denn eine Liste mit Referenzen haben, wie mache ich das mit Null Referenzen? Vielleicht NULL-Objekte erstellen?

Kellerautomat

Ja, Java in C++ ist eine ganz schlechte Idee.