C++ stl priority queue insert bad_alloc exception

Question

Я работаю над процессором запросов, который читает в длинных списках идентификатора документа из памяти и ищет соответствующие идентификаторы. Когда он находит один, он создает структуру DOC, содержащую docid (int) и ранг документа (двойной), и помещает его в очередь приоритетов. Моя проблема заключается в том, что когда поиск слова (ов) имеет длинный список, когда я пытаюсь нажать DOC на очередь, я получаю следующее исключение: Необработанное исключение в 0x7c812afb в QueryProcessor.exe: исключение Microsoft C++: std :: bad_alloc в ячейке памяти 0x0012ee88 ..

Когда слово имеет короткий список, оно отлично работает. Я попытался нажать DOC на очередь в нескольких местах в моем коде, и все они работают до определенной строки; после этого я получаю вышеуказанную ошибку. Я совершенно не понимаю, что не так, потому что самый длинный список читается меньше 1 МБ, и я освобождаю всю память, которую я выделяю. Почему вдруг возникает ошибка bad_alloc, когда я пытаюсь нажать DOC на очередь, в которой есть возможность ее удерживать (я использовал вектор с достаточным пространством, зарезервированным в качестве базовой структуры данных для очереди приоритетов)?

Я знаю, что вопросы, подобные этому, почти невозможно ответить, не видя всего кода, но это слишком долго, чтобы публиковать здесь. Я делаю все, что в моих силах, и с тревогой надеюсь, что кто-то может дать мне ответ, потому что я нахожусь в своем уме.

Функция NextGEQ считывает список сжатых блоков docids по блоку. То есть, если он видит, что lastdocid в блоке (в отдельном списке) больше, чем переданный docid, он распаковывает блок и выполняет поиск, пока не найдет правильный. Каждый список начинается с метаданных о списке с длиной каждого сжатого фрагмента и последнего docid в куске. data.iquery указывает на начало метаданных; data.metapointer указывает на везде, где в метаданных есть функция; и data.blockpointer указывает на начало блока несжатых докид, если он есть. Если он видит, что он уже распакован, он просто ищет. Ниже, когда я вызываю функцию в первый раз, она распаковывает блок и находит docid; после этого нажимается на очередь. Во второй раз это даже не нужно распаковывать; то есть никакой новой памяти не выделяется, но после этого времени нажатие на очередь дает ошибку bad_alloc.

Редактировать: Я очистил свой код еще и так, чтобы он компилировался. Я также добавил в OpenList() и функции NextGEQ, хотя последний длинный, потому что я думаю, что проблема вызвана кучей коррупции где-то в нем. Большое спасибо!

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; 

       } 

      } 

} 
} 

Большое спасибо, bsg.

Answer 1

Предполагая, что у вас есть повреждение кучи и на самом деле не изнуряющая память, самый распространенный способ получить повреждение кучи - это удалить (или освободить) тот же указатель дважды. Вы можете легко узнать, не является ли это проблемой, просто комментируя все ваши звонки, чтобы удалить (или бесплатно). Это приведет к утечке вашей программы, как к сите, но если это действительно не сбой, вы, вероятно, определили проблему.

Другая причина, связанная с поврежденной кучей, заключается в удалении (или освобождении) указателя, который никогда не выделялся в куче. Дифференциация между двумя причинами коррупции не всегда легко, но ваш первый приоритет должен состоять в том, чтобы выяснить, действительно ли коррупция является проблемой.

Обратите внимание, что этот подход не будет работать слишком хорошо, если объекты, которые вы удаляете, имеют деструкторы, которые, если не вызывать, нарушают семантику вашей программы.

Answer 2

QUERYMANAGER::OpenList возвращает значение listnode по значению. Затем в startlist = &OpenList(value); вы берете адрес возвращаемого временного объекта.Когда временное уходит, вы можете получить доступ к данным некоторое время, а затем перезаписать. Не могли бы вы просто объявить начальный список списка не указателей в стеке и сразу присвоить ему возвращаемое значение? Затем удалите * перед другими видами использования и проверьте, устраняет ли это проблему.

Answer 3

Еще одна вещь, которую вы можете попробовать - это заменить все указатели на интеллектуальные указатели, в частности что-то вроде boost::shared_ptr<>, в зависимости от того, сколько кода это действительно так, и насколько вам удобно автоматизировать задачу. Умные указатели не являются ответом на все, но они по меньшей мере безопаснее, чем исходные указатели.

Answer 4

Спасибо за вашу помощь. Ты был прав, Нил, мне, должно быть, удалось развратить мою кучу. Я все еще не уверен, что это вызвало, но когда я сменил malloc (numdocids * 5) на malloc (256), он волшебным образом остановился. Полагаю, я должен был проверить, действительно ли мои малловоды преуспели! Еще раз спасибо! Bsg