c ++ stl prioridad excepción cola inserto bad_alloc

Question

Estoy trabajando en un procesador de consultas que se lee en largas listas de Identificación del documento de la memoria y busca a juego Identificación del. Cuando encuentra uno, se crea una estructura que contiene el DOC iddoc (un int) y el rango del documento (una doble) y lo empuja en una cola de prioridad. Mi problema es que cuando la palabra (s) buscado tiene una larga lista, cuando trato de empujar el DOC a la cola, me sale el siguiente excepción: excepción no controlada en 0x7c812afb en QueryProcessor.exe: Microsoft C ++ excepción: std :: bad_alloc en la posición de memoria 0x0012ee88 ..

Cuando la palabra tiene una lista corta, funciona bien. Intenté empujar DOC en la cola en varios lugares en mi código, y todos trabajan hasta una cierta línea; después de eso, me sale el error anterior. Estoy completamente en una pérdida en cuanto a lo que es incorrecto porque la lista más larga leer en menos de 1 MB y liberar toda la memoria que asigno. ¿Por qué debería estar allí pronto una excepción bad_alloc cuando trato de empujar un DOC en una cola que tiene una capacidad para sostenerlo (he usado un vector con suficiente espacio reservado como la estructura de datos subyacente para la cola de prioridad)?

Yo sé que este tipo de preguntas son casi imposible de responder sin ver todo el código, pero es demasiado tiempo para publicar aquí. Estoy poniendo todo lo que puedo y estoy ansioso esperando que alguien me puede dar una respuesta, porque estoy en el extremo de mis ingenios.

La función NextGEQ lee una lista de bloques comprimidos de bloque docIDs por bloque. Es decir, si se ve que el lastdocid en el bloque (en una lista separada) es mayor que la aprobada en iddoc, se descomprime el bloque y búsquedas hasta encontrar la correcta. Cada lista comienza con los metadatos de la lista con las longitudes de cada bloque comprimido y el último iddoc en el trozo. data.iquery puntos al comienzo de los metadatos; data.metapointer puntos a cualquier lugar en los metadatos de la función actualmente es; y data.blockpointer puntos al principio del bloque de docIDs sin comprimir, si es que existe. Si se ve que ya se descomprimió, sólo se busca. A continuación, cuando llamo a la función de la primera vez, se descomprime un bloque y encuentra el iddoc; el empuje en la cola después de que las obras. La segunda vez, no necesita ni siquiera para descomprimir; es decir, ninguna nueva memoria se asigna, pero después de ese tiempo, empujando a la cola da un error de bad_alloc.

Editar: Limpié mi código un poco más para que se debería compilar. También he añadido en el OpenList () y funciones NextGEQ, aunque este último es mucho tiempo, porque creo que el problema es causado por un algún lugar daños en el montón en ella. ¡Muchas gracias!

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;

                }

           } 

}
}

Muchas gracias, BSG.

Answer 1

Asumiendo que tiene daños en el montón y no son, de hecho, de agotar la memoria, la forma más común de un montón pueden corromperse es mediante la supresión (o liberar) el mismo puntero dos veces. Puede encontrar muy fácilmente si este es el problema simplemente comentando todas sus llamadas a eliminar (o libre). Esto hará que su programa a la fuga como un colador, pero si en realidad no bloquee es probable que haya identificado el problema.

La otra causa común causa de un montón corrupta está eliminando (o liberar) un puntero que no fue nunca asigna en el montón. La diferenciación entre las dos causas de la corrupción no siempre es fácil, pero su primera prioridad debe ser para averiguar si la corrupción es en realidad el problema.

Tenga en cuenta este enfoque no funciona demasiado bien, si las cosas que se van a suprimir tienen destructores que si no se llama ruptura de la semántica de su programa.

Answer 2

QUERYMANAGER::OpenList devuelve un NodoLista por valor. En startlist = &OpenList(value);, a continuación, proceder a tomar la dirección del objeto temporal que se devuelve. Cuando va la distancia temporal, es posible que pueda acceder a los datos por un tiempo y entonces es sobrescrito. Podría usted acaba de declarar una startlist NodoLista no puntero de la pila y asignarle el valor de retorno directamente? A continuación, retire el * frente a otros usos y ver si se soluciona el problema.

Answer 3

Otra cosa que puedes intentar está reemplazando todos los punteros con punteros inteligentes, específicamente algo así como boost::shared_ptr<>, dependiendo de la cantidad de código que esto realmente es y lo mucho que se sienta cómodo automatizar la tarea. punteros inteligentes no son la respuesta para todo, pero son al menos seguros que los punteros primas.

Answer 4

Gracias por toda su ayuda. Tenías razón, Neil - Me debe haber logrado corromper mi montón. Todavía no estoy seguro de lo que estaba causando, pero cuando he cambiado el malloc (numdocids * 5) a malloc (256) que mágicamente se detuvo estrellarse. Supongo que debería haber comprobado si o no mis mallocs en realidad estaban teniendo éxito! ¡Gracias de nuevo! BSG