C ++ stl Prioritätswarteschlange Einsatz bad_alloc Ausnahme

Question

Ich arbeite an einem Abfrage-Prozessor, der aus dem Speicher in langen Listen von Dokumenten-IDs liest und sieht für ids entsprechen. Wenn es einen findet, erstellt es eine DOC-Struktur die docid (int) und des Dokuments Rang (a double) und drückt es auf eine Prioritätswarteschlange enthält. Mein Problem ist, dass, wenn das Wort (e) nach einer langen Liste, wenn ich versuche, die DOC drücken auf die Warteschlange, ich die folgende Ausnahme erhalten: Nicht behandelte Ausnahme bei 0x7c812afb in QueryProcessor.exe: Microsoft C ++ Ausnahme: std :: bad_alloc an Speicherplatz 0x0012ee88 ..

Wenn das Wort eine kurze Liste hat, funktioniert es gut. Ich habe versucht, DOC in die Warteschlange an mehreren Stellen in meinem Code schieben, und sie alle arbeiten, bis eine bestimmte Linie; Danach habe ich den obigen Fehler erhalten. Ich bin völlig ratlos, was falsch ist, weil die längste Liste lesen ist in weniger als 1 MB und ich frei, alle Speicher, dass ich zuzuteilen. Warum soll es plötzlich eine bad_alloc Ausnahme sein, wenn ich versuche, ein DOC auf eine Warteschlange zu schieben, die eine Kapazität, es zu halten hat (ich einen Vektor mit genügend Platz verwendet als die zugrunde liegende Datenstruktur reserviert für die Prioritätswarteschlange)?

Ich weiß, dass Fragen wie diese fast unmöglich zu beantworten, ohne die gesamten Code zu sehen, aber es ist zu lang, um hier zu posten. Ich bin so viel setzen, wie ich kann und hoffe, ängstlich, dass jemand mir eine Antwort geben kann, weil ich an meinem Latein am Ende bin.

Die NextGEQ Funktion liest eine Liste der komprimierten Blöcke von DocIDs Block für Block. Das heißt, wenn es sieht, dass die lastdocid im Block (in einer separaten Liste) größer ist als die docid eingeleitet, den Block und sucht dekomprimiert, bis er die richtige findet. Jede Liste beginnt mit Metadaten über die Liste mit den Längen jedes komprimierten Brocken und dem letzten docid im Chunk. data.iquery zeigt auf den Anfang der Metadaten; data.metapointer Punkte überall in den Metadaten der Funktion zur Zeit ist; und data.blockpointer zeigt auf den Anfang des Blocks der unkomprimierten DocIDs, wenn gibt es einen. Wenn es sieht, dass es bereits dekomprimiert wurde, sucht es nur. Unten, wenn ich die Funktion zum ersten Mal aufrufen, dekomprimiert sie einen Block und findet die docid; die Push in die Warteschlange nach, die funktioniert. Das zweite Mal, dauert es nicht einmal zu dekomprimieren müssen; Das heißt, kein neuer Speicher zugewiesen, aber nach dieser Zeit in die Warteschlange auf dem Druck ergibt einen bad_alloc Fehler.

Edit: Ich säuberte meinen Code auf einige mehr, so dass es kompilieren sollte. Ich habe auch in der Openlist () und NextGEQ Funktionen hinzugefügt, obwohl letztere lang ist, weil ich denke, das Problem durch eine Heapbeschädigung irgendwo in ihm verursacht wird. Vielen Dank!

struct DOC{

    long int docid;
    long double rank;

public:
    DOC()
    {
        docid = 0;
        rank = 0.0;
    }

    DOC(int num, double ranking)
    {
        docid = num;
        rank = ranking;

    }

     bool operator>( const DOC & d ) const {
       return rank > d.rank;
    }

      bool operator<( const DOC & d ) const {
       return rank < d.rank;
    }
    };

struct listnode{

int* metapointer;
int* blockpointer;
int docposition;
int frequency;
int numberdocs;
int* iquery;
listnode* nextnode;

};

void QUERYMANAGER::SubmitQuery(char *query){

    listnode* startlist;

        vector<DOC> docvec;
        docvec.reserve(20);
        DOC doct;


    //create a priority queue to use as a min-heap to store the documents and rankings;


        priority_queue<DOC, vector<DOC>,std::greater<DOC>> q(docvec.begin(), docvec.end());

        q.push(doct);

    //do some processing here; startlist is a pointer to a listnode struct that starts the   //linked list

        //point the linked list start pointer to the node returned by the OpenList method

        startlist = &OpenList(value);
        listnode* minpointer;
        q.push(doct);


        //start by finding the first docid in the shortest list
            int i = 0;
            q.push(doct);
            num = NextGEQ(0, *startlist);
            q.push(doct);
            while(num != -1)
               {

            q.push(doct);

    //the is where the problem starts - every previous q.push(doct) works; the one after
    //NextGEQ(num +1, *startlist) gives the bad_alloc error

            num = NextGEQ(num + 1, *startlist);

         //this is where the exception is thrown
            q.push(doct);               
        }

    }



//takes a word and returns a listnode struct with a pointer to the beginning of the list
//and metadata about the list 
listnode QUERYMANAGER::OpenList(char* word)
{
    long int numdocs;

    //create a new node in the linked list and initialize its variables


    listnode n;
    n.iquery = cache -> GetiList(word, &numdocs);
    n.docposition = 0;
    n.frequency = 0;
    n.numberdocs = numdocs;

   //an int pointer to point to where in the metadata you are
    n.metapointer = n.iquery;
    n.nextnode = NULL;
  //an int pointer to point to the uncompressed block of data, if there is one
    n.blockpointer = NULL;



    return n;


}


int QUERYMANAGER::NextGEQ(int value, listnode& data)
{
     int lengthdocids;
     int lengthfreqs; 
     int lengthpos;
     int* temp;
     int lastdocid;


     lastdocid = *(data.metapointer + 2);

while(true)
{

         //if it's not the first chunk in the list, the blockpointer will be pointing to the 
        //most recently opened block and docpos to the current position in the block
    if( data.blockpointer && lastdocid >= value)
    {

            //if the last docid in the chunk is >= the docid we're looking for,
            //go through the chunk to look for a match


        //the last docid in the block is in lastdocid; keep going until you hit it
        while(*(data.blockpointer + data.docposition) <= lastdocid)
        {
            //compare each docid with the docid passed in; if it's greater than or equal to it, return a pointer to the docid
             if(*(data.blockpointer + data.docposition ) >= value)
             {

                 //return the next greater than or equal docid
                 return *(data.blockpointer + data.docposition);
             }
             else
             {
                 ++data.docposition;
             }
        }

        //read through the whole block; couldn't find matching docid; increment metapointer to the next block;
        //free the block's memory

        data.metapointer += 3;
        lastdocid = *(data.metapointer + 3);
        free(data.blockpointer);
        data.blockpointer = NULL;
    }


        //reached the end of a block; check the metadata to find where the next block begins and ends and whether 
        //the last docid in the block is smaller or larger than the value being searched for


        //first make sure that you haven't reached the end of the list
            //if the last docid in the chunk is still smaller than the value passed in, move the metadata pointer
           //to the beginning of the next chunk's metadata; read in the new metadata


            while(true)
         //  while(*(metapointers[index]) != 0 )
           {
               if(lastdocid < value && *(data.metapointer) !=0)
               {
               data.metapointer += 3;
               lastdocid = *(data.metapointer + 2);
               }


           else if(*(data.metapointer) == 0)
           {
               return -1;
             }

           else
               //we must have hit a chunk whose lastdocid is >= value; read it in
           {
                //read in the metadata
           //the length of the chunk of docid's is cumulative, so subtract the end of the last chunk 
           //from the end of this chunk to get the length

               //find the end of the metadata


                temp = data.metapointer;

            while(*temp != 0)
            {
                temp += 3;
            }
                temp += 2;
    //temp is now pointing to the beginning of the list of compressed data; use the location of metapointer
    //to calculate where to start reading and how much to read

         //if it's the first chunk in the list,the corresponding metapointer is pointing to the beginning of the query
        //so the number of bytes of docid's is just the first integer in the metadata
                if(  data.metapointer == data.iquery)
                {
                    lengthdocids = *data.metapointer;

                }

                else
                {
                    //start reading from the offset of the end of the last chunk (saved in metapointers[index] - 3)
                    //plus 1 = the beginning of this chunk

                    lengthdocids = *(data.metapointer) - (*(data.metapointer - 3));
                    temp += (*(data.metapointer - 3)) / sizeof(int); 

                   }


           //allocate memory for an array of integers - the block of docid's uncompressed
           int* docblock = (int*)malloc(lengthdocids * 5 );

           //decompress docid's into the block of memory allocated
            s9decompress((int*)temp, lengthdocids /4, (int*) docblock, true);

            //set the blockpointer to point to the beginning of the block
            //and docpositions[index] to 0
            data.blockpointer = docblock;
            data.docposition = 0;
            break;

                }

           } 

}
}

Vielen Dank, bsg.

Answer 1

Angenommen, Sie Heapbeschädigung und sind in der Tat nicht anstrengend Gedächtnis haben, die häufigste Art und Weise ein Heap beschädigt werden kann, ist durch das Löschen (oder Befreiung) den gleichen Zeiger zweimal. Sie können ganz leicht finden, wenn dies das Problem, indem Sie einfach kommentieren Sie alle Ihre Anrufe (oder frei) zu löschen. Dies bewirkt, dass das Programm wie ein Sieb lecken, aber wenn es tatsächlich nicht abstürzen Sie haben wahrscheinlich das Problem erkannt.

Die andere häufige Ursache Ursache eines korrupten Haufen löscht (oder Befreiung) ein Zeiger, der nicht immer auf dem Heap zugewiesen wurde. zwischen den beiden Ursachen der Korruption Differenzieren ist nicht immer einfach, aber Ihre erste Priorität soll, um herauszufinden, wenn Korruption eigentlich das Problem ist.

Beachten Sie diesen Ansatz wird auch nicht gut funktionieren, wenn die Dinge, die Sie haben Destruktoren zu löschen, die, wenn nicht brechen die Semantik des Programms genannt.

Answer 2

QUERYMANAGER::OpenList gibt einen listnode von Wert. In startlist = &OpenList(value); gehen Sie dann die Adresse des temporären Objekt zu nehmen, die zurückgegeben wird. Wenn die temporäre weggeht, können Sie in der Lage sein, die Daten für eine Zeit für den Zugriff auf und dann überschreibt es ist. Könnten Sie eine Nicht-Zeiger listnode Startliste auf dem Stapel deklarieren und den Rückgabewert direkt zuweisen? Dann entfernen Sie die * vor anderen Nutzungen und sehen, ob das das Problem behebt.

Answer 3

Eine andere Sache, können Sie versuchen, alle Zeiger mit Smart-Pointer ersetzt speziell etwas wie boost::shared_ptr<>, je nachdem, wie viel Code wirklich ist und wie viel Sie bequem die Aufgabe zu automatisieren. Intelligente Zeiger sind nicht die Antwort auf alles, aber sie sind zumindest sicherer als roher Zeiger.

Answer 4

Vielen Dank für Ihre Hilfe. Sie haben Recht, Neil - ich muss mein Haufen zu korrumpieren geschafft haben. Ich bin immer noch nicht sicher, was es verursacht wurde, aber als ich die malloc geändert (numdocids * 5) zu malloc (256) es Absturz auf magische Weise gestoppt. Ich glaube, ich hätte überprüft, ob meine mallocs wurden nachfolgende tatsächlich! Danke noch einmal! Bsg