c ++ stl file d'attente prioritaire exception insert bad_alloc

Question

Je travaille sur un processeur de requête qui se lit dans les longues listes d'identité de documents de la mémoire et cherche correspondant à ids. Quand il en trouve un, il crée une struct DOC contenant le docid (un int) et le rang du document (un double) et le pousse à une file d'attente prioritaire. Mon problème est que lorsque le mot (s) recherché a une longue liste, lorsque je tente de pousser le DOC à la file d'attente, je reçois l'exception suivante: exception non gérée à 0x7c812afb dans QueryProcessor.exe: Microsoft C ++ exception: std :: bad_alloc à l'emplacement de mémoire 0x0012ee88 ..

Quand le mot a une courte liste, il fonctionne très bien. J'ai essayé de pousser DOC de la file d'attente sur plusieurs endroits dans mon code, et ils travaillent tous jusqu'à une certaine ligne; après cela, je reçois l'erreur ci-dessus. Je suis tout à fait à une perte de ce qui est erroné, car la plus longue liste lue est inférieure à 1 Mo et je libérer toute la mémoire que j'allouer. Pourquoi faut-il tout à coup une exception bad_alloc lorsque je tente de pousser un DOC sur une file d'attente qui a une capacité de le tenir (j'ai utilisé un vecteur avec assez d'espace réservé que la structure de données sous-jacente pour la file d'attente prioritaire)?

Je sais que les questions de ce genre sont presque impossible de répondre sans voir tout le code, mais il est trop long pour poster ici. Je mets autant que je peux et espère avec impatience que quelqu'un peut me donner une réponse, parce que je suis à la fin de mon esprit.

La fonction NextGEQ lit une liste de blocs compressés de bloc de docids par bloc. Autrement dit, si on voit que le lastdocid dans le bloc (dans une liste séparée) est plus grande que le docid transmis, il décompresse le bloc et les recherches jusqu'à ce qu'il trouve la bonne. Chaque liste commence par des métadonnées sur la liste avec les longueurs de chaque bloc comprimé et le dernier docid dans le bloc. Le secteur data.iquery au début des métadonnées; Le secteur data.metapointer à chaque fois dans les métadonnées la fonction est actuellement; et data.blockpointer points au début du bloc de docids non compressés, si elle existe. Si elle voit qu'il était déjà décompressé, il recherche juste. Ci-dessous, quand je l'appelle la fonction pour la première fois, il décompresse un bloc et trouve le docid; la poussée sur la file d'attente après qui fonctionne. La deuxième fois, il n'a même pas besoin de décomprimer; qui est, aucune nouvelle mémoire est allouée, mais après cette date, en poussant à la file d'attente donne une erreur de bad_alloc.

Edit: Je nettoyais mon code un peu plus pour qu'il devrait compiler. J'ai également ajouté dans le OpenList () et NextGEQ, bien que cette dernière est longue, parce que je pense que le problème est causé par une corruption du tas quelque part en elle. Merci beaucoup!

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;

                }

           } 

}
}

Merci beaucoup, bsg.

Answer 1

En supposant que vous avez la corruption du tas et ne sont pas en fait épuiser la mémoire, la façon dont un tas plus courant peut être corrompu est en supprimant (ou libérant) le même pointeur deux fois. Vous pouvez facilement savoir si cela est la question simplement de commenter tous vos appels à supprimer (ou libre). Cela entraînera votre programme de fuir comme un tamis, mais si elle ne tombe pas en panne que vous avez fait probablement identifié le problème.

L'autre cause de cause commune d'un tas de corruption est la suppression (ou libérer) un pointeur qui n'a pas été jamais alloué sur le tas. Différencier entre les deux causes de la corruption est pas toujours facile, mais votre première priorité devrait être de savoir si la corruption est en fait le problème.

Notez que cette approche ne sera pas trop bien si les choses que vous supprimez ont Destructeurs qui sinon la sémantique rupture appelle de votre programme.

Answer 2

QUERYMANAGER::OpenList renvoie un ListNode par valeur. Dans startlist = &OpenList(value); vous allez ensuite prendre l'adresse de l'objet temporaire qui est retourné. Lorsque la va temporaire loin, vous pourrez peut-être accéder aux données pendant un certain temps et il Écrasé. Pouvez-vous déclarer une debliste de ListNode non-pointeur sur la pile et l'affecter la valeur de retour directement? Retirez ensuite le * devant d'autres utilisations et voir si cela résout le problème.

Answer 3

Une autre chose que vous pouvez essayer de remplacer tous les pointeurs est avec des pointeurs intelligents, en particulier quelque chose comme boost::shared_ptr<>, selon la façon dont le code est vraiment bien ce et combien vous êtes à l'aise automatisant la tâche. pointeurs intelligents ne sont pas la réponse à tout, mais ils sont au moins plus sûr que les pointeurs premières.

Answer 4

Merci pour votre aide. Vous aviez raison, Neil - Je dois avoir réussi à mon tas corrompu. Je ne suis toujours pas sûr de ce qui a été à l'origine, mais quand je l'ai changé le malloc (numdocids * 5) à malloc (256) magiquement arrêté de s'écraser. Je suppose que je devrais avoir vérifié si oui ou non mes mallocs étaient en fait réussir! Merci encore! Bsg