Как удалить удаленный узел в середине списка без ошибок valgrind?

Question

Это небольшой тест, помогающий продемонстрировать и проанализировать выпуск memcheck valgrind. Может кто-нибудь помочь мне выяснить, как удалить И освободить узел из середины списка? Если я прокомментирую бесплатный (cur) и свободный (cur-> lock) из секции удаления узла, то memcheck сообщает мне, что у меня есть утечка памяти, но если я их сохраню, то я делаю недопустимое чтение в верхней части петля. Есть ли выход из этой головоломки?

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

Глядя на вашу петле (упрощенной):

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

проблема с назначением prev = cur, но только тогда, когда if блока оцениваются. Это освободило cur, поэтому в следующий раз вокруг цикла, cur=prev->next ссылается на удаленное хранилище.

Вы можете исправить, вставив else назначать prev только тогда, когда cur не был удален:

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