C ++ STL Priority Queue Insert Bad_Alloc Exception

Question

Estou trabalhando em um processador de consultas que lê em longas listas de IDs de documentos da memória e procuram IDs correspondentes. Quando encontra um, cria uma estrutura de documentos contendo o docid (um int) e a classificação do documento (um duplo) e o empurra para uma fila de prioridade. Meu problema é que, quando as palavras procuradas têm uma longa lista, quando tento empurrar o documento para a fila, recebo a seguinte exceção: exceção não enfrentada em 0x7c812afb no queryprocessor.exe: Microsoft C ++ Exceção: std: : bad_alloc no local da memória 0x0012ee88 ..

Quando a palavra tem uma lista curta, funciona bem. Tentei empurrar os documentos para a fila em vários lugares do meu código, e todos eles funcionam até uma determinada linha; Depois disso, recebo o erro acima. Estou completamente sem problemas sobre o que está errado, porque a lista mais longa lida é inferior a 1 MB e eu libero toda a memória que aloco. Por que de repente deve haver uma exceção Bad_All quando eu tento empurrar um documento para uma fila com capacidade para segurá -la (usei um vetor com espaço suficiente reservado como estrutura de dados subjacente para a fila de prioridade)?

Sei que perguntas como essa são quase impossíveis de responder sem ver todo o código, mas é muito longo para postar aqui. Estou colocando o máximo que posso e espero ansiosamente que alguém possa me dar uma resposta, porque estou no final do meu juízo.

A função NextGeq lê uma lista de blocos compactados de documentos de bloco por bloco. Ou seja, se vê que o LastDocid no bloco (em uma lista separada) é maior do que o docid, descompacta o bloco e pesquisa até encontrar o certo. Cada lista começa com os metadados sobre a lista com os comprimentos de cada pedaço compactado e o último documento no pedaço. Data.iquiery aponta para o início dos metadados; Data.MetaPointer aponta para onde quer que seja nos metadados a função atualmente; e Data.BlockPointer aponta para o início do bloco de docides não compactados, se houver um. Se vê que já foi descomprimido, apenas pesquisa. Abaixo, quando eu chamo a função pela primeira vez, ela descomprima um bloco e encontra o docid; O empurrão na fila depois disso funciona. Na segunda vez, ele nem precisa descomprimir; Ou seja, nenhuma nova memória é alocada, mas depois desse tempo, pressionando a fila fornece um erro BAD_Alloc.

EDIT: Limpei meu código um pouco mais para que ele fosse compilar. Eu também adicionei as funções OpenList () e NextGeq, embora o último seja longo, porque acho que o problema é causado por uma corrupção de heap em algum lugar. Muito obrigado!

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;

                }

           } 

}
}

Muito obrigado, BSG.

Answer 1

Supondo que você tenha corrupção de heap e não seja de fato a memória exaustiva, a maneira mais comum uma pilha pode ser corrompida é excluir (ou liberar) o mesmo ponteiro duas vezes. Você pode descobrir facilmente se esse é o problema simplesmente comentando todas as suas chamadas para excluir (ou gratuitas). Isso fará com que seu programa vaze como uma peneira, mas se ele não falhar, você provavelmente identificou o problema.

A outra causa comum de uma pilha corrupta está excluindo (ou liberando) um ponteiro que nunca foi alocado na pilha. A diferenciação entre as duas causas de corrupção nem sempre é fácil, mas sua primeira prioridade deve ser descobrir se a corrupção é realmente o problema.

Observe que essa abordagem não funcionará muito bem se as coisas que você está excluindo têm destruidores que, se não forem chamados, quebre a semântica do seu programa.

Answer 2

QUERYMANAGER::OpenList Retorna um ListNode By Value. Dentro startlist = &OpenList(value); Em seguida, você segue o endereço do objeto temporário que foi retornado. Quando o temporário desaparecer, você poderá acessar os dados por um tempo e, em seguida, é substituído. Você poderia apenas declarar uma lista de inicialização da ListNode Non Pointer na pilha e atribuí-la diretamente ao valor de retorno? Em seguida, remova o * na frente de outros usos e veja se isso corrige o problema.

Answer 3

Outra coisa que você pode tentar é substituir todos os ponteiros por ponteiros inteligentes, especificamente algo como boost::shared_ptr<>, dependendo de quanto código isso realmente é e quanto você está confortável automatizando a tarefa. Ponteiros inteligentes não são a resposta para tudo, mas eles são pelo menos mais seguros do que os indicadores crus.

Answer 4

Obrigado por toda sua ajuda. Você estava certo, Neil - eu devo ter conseguido corromper minha pilha. Ainda não tenho certeza do que estava causando isso, mas quando mudei o malloc (numdocids * 5) para Malloc (256), ele parou de bater magicamente. Suponho que deveria ter verificado se meus MaiCs estavam realmente tendo sucesso! Obrigado novamente! BSG