Утечки памяти в связанных списках - PullRequest
1 голос
/ 14 июня 2019

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

Код:

 struct node {
    int value;
    node* next;
    pthread_mutex_t lock; // hand over hand implies a lock for every 
                          // node
 };

struct list {
   node* head;
};

  // insert function for a new value if a value already exists then do 
  nothing

  void insert_value(list* list, int value)
{
if(list == NULL) return; // if list pointer is NULL then do nothing`

node* new_node = malloc(sizeof(node)); // create new node                                  

if(new_node == NULL) return; // check if allocation fails

new_node->value = value;

pthread_mutex_init(&(new_node->lock),NULL); // initialize mutex lock  
                                            // for the new node

pthread_mutex_lock(&(new_node->lock)); // lock the new node

if(list->head == NULL) // new node is the first element in the list
{
     new_node->next = NULL;
     list->head = new_node;
     pthread_mutex_unlock(&(new_node->lock));
     return;
}

pthread_mutex_lock(&(list->head->lock)); // lock the head of the list

node* temp;

if(list->head->value == new_node->value) // do nothing if the head of 
                                         // list is equal to new node

{
   pthread_mutex_unlock(&(list->head->lock));
   pthread_mutex_unlock(&(new_node->lock));
   pthread_mutex_destroy(&(new_node->lock));
   free(new_node);
   return;
}

else if(list->head->value > new_node->value) // new node comes before 
                                             // the list head
{
   new_node->next = list->head;
   temp = list->head;
   list->head = new_node;
   pthread_mutex_unlock(&(list->head->lock));
   pthread_mutex_unlock(&(temp->lock));
   return;
}

else
{
    // Locate the node before the point of insertion //

    node* dummy;
    node* current = list->head;
    temp = current->next; 

    if(temp == NULL) // new node comes after
                     // the list head
    {
        new_node->next = current->next;
        current->next = new_node;
        pthread_mutex_unlock(&(new_node->lock));
        pthread_mutex_unlock(&(current->lock));
        return;
    }

   pthread_mutex_lock(&(temp->lock)); // lock the successor of the head

   // perform hand over hand traversal of the list
   // and check if temp reaches the end of the list (NULL)

    while (temp->value < new_node->value)
    {
      pthread_mutex_unlock(&(current->lock));
      current = temp;
      temp = temp->next;
      if(temp == NULL) break;
      pthread_mutex_lock(&(temp->lock));
    }

    if(temp == NULL) // new node will be the last element in this case 
    {
        current->next = new_node;
        new_node->next = NULL;
        pthread_mutex_unlock(&(current->lock));
        pthread_mutex_unlock(&(new_node->lock));
        return;
    }

    else if(temp->value == new_node->value) //new node already exists 
    {
       pthread_mutex_unlock(&(temp->lock));
       pthread_mutex_unlock(&(current->lock));
       pthread_mutex_unlock(&(new_node->lock));
       pthread_mutex_destroy(&(new_node->lock));
       free(new_node);
       return;
    }

    else // new node should be inserted inside the list
    {
       dummy = temp;
       new_node->next = current->next;
       current->next = new_node;
       pthread_mutex_unlock(&(dummy->lock));
       pthread_mutex_unlock(&(current->lock));
       pthread_mutex_unlock(&(new_node->lock));
       return;
    }
}
 } `
...