c ++ stl priorità eccezione coda inserto bad_alloc

Question

Sto lavorando su un processore di query che legge in lunghe liste di id del documento dalla memoria e cerca di corrispondenza di id. Quando ne trova uno, si crea una struct DOC contenente il docid (un int) e il rango del documento (una doppia) e lo spinge in una coda di priorità. Il mio problema è che quando la parola (s) cercato conta un lungo elenco, quando provo a spingere il DOC a coda, ottengo la seguente eccezione: Eccezione non gestita a 0x7c812afb in QueryProcessor.exe: eccezione Microsoft C ++: std :: bad_alloc in posizione di memoria 0x0012ee88 ..

Quando la parola ha un breve elenco, funziona benissimo. Ho provato a spingere DOC nella coda in diversi luoghi nel mio codice, e che tutti i lavori fino a una certa linea; Dopo di che, ho l'errore di cui sopra. Sono completamente ad una perdita quanto a ciò che è sbagliato, perché la più lunga lista letta è inferiore a 1 MB e liberare tutta la memoria che ho allocare. Perché dovrebbe esserci improvvisamente essere un'eccezione bad_alloc quando cerco di spingere un DOC su una coda che ha una capacità di tenerlo (io ho usato un vettore con abbastanza spazio riservato come struttura dati sottostante per la coda di priorità)?

so che domande di questo tipo sono quasi impossibili da risolvere senza vedere tutto il codice, ma è troppo lungo per postare qui. Sto mettendo quanto più posso e sto con ansia sperando che qualcuno mi può dare una risposta, perché io sono alla fine più cosa fare.

La funzione NextGEQ legge un elenco di blocchi compressi di blocco docids di blocco. Cioè, se si vede che il lastdocid nel blocco (in un elenco a parte) è più grande della docid passata, si decomprime il blocco e le ricerche fino a trovare quella giusta. Ogni lista inizia con i metadati relativi alla lista con le lunghezze di ogni blocco compressa e l'ultimo docid nel pezzo. punti data.iquery per l'inizio dei metadati; punti data.metapointer alla tua nei metadati della funzione attualmente è; e data.blockpointer punta all'inizio del blocco di docids non compressi, se presente. Se si vede che era già decompresso, esso cerca solo. Qui di seguito, quando chiamo la funzione per la prima volta, si decomprime un blocco e trova il docid; la spinta sulla coda dopo che le opere. La seconda volta, non ha nemmeno bisogno di decomprimere; vale a dire, nessuna nuova memoria viene allocata, ma dopo che il tempo, spingendo alla coda dà un errore di bad_alloc.

Edit: ho ripulito il mio codice di un po 'di più in modo che esso dovrebbe compilare. Ho anche aggiunto nel OpenList () e le funzioni NextGEQ, anche se quest'ultimo è lungo, perché penso che il problema è causato da un qualche mucchio di corruzione in esso. Grazie mille!

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;

                }

           } 

}
}

La ringrazio molto, BSG.

Answer 1

Supponendo di avere danneggiamento di heap e non sono di fatto esaurire la memoria, il modo più comune di un heap può avere danneggiato è cancellando (o liberare) lo stesso puntatore due volte. Si può facilmente scoprire se questo è il problema, semplicemente commentando tutte le chiamate per cancellare (o libero). Questo farà sì che il vostro programma a fuoriuscire come un setaccio, ma se non va in crash in realtà probabilmente avete individuato il problema.

L'altra causa comune causa di un mucchio corrotto è l'eliminazione (o liberare) un puntatore che non è stato mai allocato sul mucchio. Differenziazione tra le due cause della corruzione non è sempre facile, ma la vostra prima priorità dovrebbe essere quella di scoprire se la corruzione è in realtà il problema.

Nota questo approccio non funziona troppo bene se le cose che si desidera eliminare hanno distruttori che, se non chiamati pausa la semantica del programma.

Answer 2

QUERYMANAGER::OpenList restituisce un listnode per valore. In startlist = &OpenList(value); poi procedere a prendere l'indirizzo del oggetto temporaneo che viene restituito. Quando la temporanea va via, si può essere in grado di accedere ai dati per un certo tempo e poi è sovrascritto. Potresti dichiarare una listnode lista di partenza non puntatore sullo stack e assegnare il valore di ritorno direttamente? Quindi rimuovere il * di fronte a altri usi e vedere se questo risolve il problema.

Answer 3

Un'altra cosa che si può provare sta sostituendo tutti i puntatori con puntatori intelligenti, in particolare qualcosa come boost::shared_ptr<>, a seconda della quantità di codice Questo in realtà è e quanto sei a tuo agio l'automatizzazione del processo. puntatori intelligenti non sono la risposta a tutto, ma sono almeno più sicuro di puntatori prime.

Answer 4

Grazie per tutto il vostro aiuto. Avevi ragione, Neil - devo aver riuscito a corrompere il mio mucchio. Non sono ancora sicuro di quello che stava causando, ma quando ho cambiato il malloc (numdocids * 5) malloc (256) magicamente fermato schiantarsi. Suppongo che avrei dovuto controllare se i miei mallocs sono stati effettivamente riuscendo! Grazie ancora! BSG