Wie lösche ich einen gelöschten Knoten in der Mitte einer Liste ohne Valgrind-Fehler?

Question

Dies ist ein kleiner Test zur Demonstration und Überprüfung der Ausgabe von Valgrinds memcheck. Kann mir jemand helfen, herauszufinden, wie man einen Knoten aus der Mitte der Liste entfernt UND freigibt? Wenn ich die freie (cur) und freie (cur-> lock) aus dem Abschnitt remove node auskommentiere, sagt memcheck, dass ich einen Speicherleck habe, aber wenn ich sie dort halte, führe ich einen ungültigen Lesevorgang an der Spitze von die Schleife. Gibt es einen Ausweg aus diesem Rätsel?

TEST(UtilityGeneralUnittest, valgrindTests) 
{ 
    //declare a node type 
    typedef struct node{ 
     int size; 
     int value; 
     struct node *next; 
     pthread_mutex_t *lock; 
    }node_t; 

    //make the head 
    node_t *head; 
    head = (node_t*)malloc(1 * sizeof(node_t)); 
    head->size = 0; 
    head->next = NULL; 
    head->lock = (pthread_mutex_t*)malloc(1 * sizeof(pthread_mutex_t)); 
    pthread_mutex_init(head->lock, NULL); 

    //create array for storing values 
    int array[10]; 


    //build a list with random numbers 
    for (int i = 0; i < 10; i++) 
    { 
     node_t *newNode; 
     newNode = (node_t*)malloc(1 * sizeof(node_t)); 
     newNode->value = rand() % 100 + 1; 
     newNode->next = NULL; 
     newNode->lock = (pthread_mutex_t*) malloc(1 * sizeof(pthread_mutex_t)); 
     pthread_mutex_init(newNode->lock, NULL); 
     array[i] = newNode->value; 
     if (head->next == NULL) 
     { 
      head->next = newNode; 
      head->size++; 
     } 
     else 
     { 
      node_t *tmp = head->next; 
      head->next = newNode; 
      newNode->next = tmp; 
      head->size++; 
     } 
    } 
    // assert the list added nodes 
    ASSERT_EQ(10, head->size); 

    //sanity check; print the list 
    node_t *printer = head; 
    while(printer->next != NULL) 
    { 
     printer = printer->next; 
     std::cout << "value: "; 
     std::cout << printer->value << ", "; 
    } 
    std::cout << "\n"; 
    // the meat and potatoes: deleting with locks. 
    int removeMe = array[rand() % 10]; 
    bool verifyDel = true; 
    int checkVal = removeMe; 
    node_t *prev; 
    node_t *cur; 

    prev = head; 
    pthread_mutex_lock(prev->lock); 
    while((cur = prev->next) != NULL) //******** this is the problem 
    { 
     pthread_mutex_lock(cur->lock); 
     if(cur->value == removeMe) 
     { 
      prev->next = cur->next; 
      pthread_mutex_unlock(cur->lock); 
      pthread_mutex_unlock(prev->lock); 
      cur->next = NULL; 
      head->size--; 
      free(cur->lock); ///******** this is the problem 
      free(cur); ///****** this is the problem 
     } 
     pthread_mutex_unlock(prev->lock); 
     prev = cur; 
    } 
    //pthread_mutex_unlock(prev->lock); 


    //verify node has been removed 
    printer = head; 
    while(printer->next != NULL) 
    { 
     printer = printer->next; 
     if(printer->value == checkVal) 
     { 
      verifyDel = false; 
     } 
     std::cout << "value: "; 
     std::cout << printer->value << ", "; 
    } 
    std::cout << "\n"; 
    ASSERT_TRUE(verifyDel); 

    //clean up: delete the list 
    while((printer = head) != NULL) 
    { 
     head = head->next; 
     free(printer->lock); 
     free(printer); 
     std::cout << "free!!!" << std::endl; 
    } 


} 

Answer 1

in der Schleife der Suche (vereinfacht):

while ((cur = prev->next) != NULL) //* problem 
{ 
    if (cur->value == removeMe) 
    { 
     prev->next = cur->next; 
     cur->next = NULL; 
     free(cur);    //* problem 
    } 
    prev = cur; 
} 

Das Problem ist mit der Zuordnung prev = cur, aber nur, wenn der if Block ausgewertet wird. Das hat cur freigegeben, so dass beim nächsten Mal in der Schleife cur=prev->next gelöschten Speicher verweist.

Sie beheben können, dass else durch Einfügen nur zuweisen prev wenn cur nicht entfernt wurde:

while ((cur = prev->next)) { 
    if (cur->value == removeMe) { 
     prev->next = cur->next; 
     cur->next = NULL; 
     free(cur); 
    } else { 
     prev = cur; 
    } 
}