6
\$\begingroup\$

Helo everyone, I need to review on function swapNode in doubly linked list. It works but I want to make it clearer and better. Are there any errors like memory leak in my code?

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

struct node;
struct list;

typedef struct node node;
typedef struct list list;

struct node
{
    int point;
    char name[30];
    node *next;
    node *prev;
};

struct list
{
    node *head;
    node *tail;
    int count;
};

node *createNewNode(int point, char name[30], node *prev, node *next);
list *createList();
void insertHead(list *listNode, int point, char name[30]);
bool compareName(char a[30], char b[30]);
void swapNode(list *listNode, char nameA[30], char nameB[30]);


int main()
{
    list *listNode = createList();

    insertHead(listNode, 10, "abc def");
    insertHead(listNode, 9, "qwe rty");
    insertHead(listNode, 8, "ui op");
    insertHead(listNode, 30, "fgh jkl");
    insertHead(listNode, 1234, "akaka");

    swapNode(listNode, "fgh jkl", "akaka");

    node *temp = listNode->head;
    while (temp != NULL)
    {
        printf("%-20s%d\n", temp->name, temp->point);
        temp = temp->next;
    }

    return 0;
}

node *createNewNode(int point, char name[30], node *prev, node *next)
{
    node *newNode = (node *)malloc(sizeof(node));
    newNode->point = point;
    strcpy(newNode->name, name);
    newNode->next = next;
    newNode->prev = prev;
    return newNode;
}

list *createList()
{
    list *listNode = (list *)malloc(sizeof(list));
    listNode->count = 0;
    listNode->head = NULL;
    listNode->tail = NULL;
    return listNode;
}

void insertHead(list *listNode, int point, char name[30])
{
    node *newNode = allocateNewNode(point, name, NULL, listNode->head);
    if (listNode->head)
        listNode->head->prev = newNode;
    listNode->head = newNode;
    if (listNode->tail == NULL)
        listNode->tail = newNode;
    ++listNode->count;
}

bool compareName(char a[30], char b[30])
{
    for (int i = 0; i < 31; i++)
    {
        if (a[i] != b[i])
            return false;
        if (a[i] == '\0')
            break;
    }

    return true;
}

void swapNode(list *listNode, char nameA[30], char nameB[30])
{
    node *A = NULL, *B = NULL;
    node *temp = listNode->head;

    for (int i = 0; i < listNode->count; i++)
    {
        if (compareName(temp->name, nameA))
            A = temp;
        else if (compareName(temp->name, nameB))
            B = temp;
        temp = temp->next;
        if (A && B)
            break;
    }
    if (!A || !B)
        return false;
    else if (A == B)
        return false;

    node p=*A;
    *A=*B;
    *B=p;

    B->next = A->next;
    B->prev = A->prev;

    A->next = p.next;
    A->prev = p.prev;
}
\$\endgroup\$
5
\$\begingroup\$

Don't Return Values from void Functions

    if (!A || !B)
        return false;
    else if (A == B)
        return false;

The function void swapNode(List *listNode, char nameA[30], char nameB[30]) is declared void, which means it doesn't return a value, yet it attempts to return false in two places. Some compilers actually report this as an error. Rather than return false; it should just be return;.

The two if statements above could be rewritten as one if statement

    if ((!A || !B) || (A == B))
    {
        return;
    }

Missing Error Checking

The C programming memory allocation functions malloc(size_t size), calloc(size_t count, size_t size) and realloc( void *ptr, size_t new_size) may fail. If they do fail then they return NULL. Any time one of these functions are called, the result should be tested to see if it is NULL. Referencing fields through a NULL pointer yields unknown behavior and is generally a bug.

Node *safeMalloc(size_t size)
{
    Node* newNode = malloc(size);
    if (newNode == NULL)
    {
        fprintf(stderr, "Memory allocation failed in safeMalloc\n");
        exit(EXIT_FAILURE);
    }

    return  newNode;
}

Node *createNewNode(int point, char name[30], Node *prev, Node *next)
{
    Node *newNode = safeMalloc(sizeof(*newNode));
    newNode->point = point;
    strcpy(newNode->name, name);
    newNode->next = next;
    newNode->prev = prev;

    return newNode;
}

Declarations of Node Structs

It might have been easier to write the struct declarations as

typedef struct node
{
    int point;
    char name[30];
    struct node *next;
    struct node *prev;
} Node;

typedef struct list
{
    Node *head;
    Node *tail;
    int count;
} List;

Complexity

The function void swapNode(List *listNode, char nameA[30], char nameB[30]) can be simplified by breaking it into 2 functions, one that does the comparisons and then calls a swaping function as necessary:

void doSwap(Node *A, Node*B)
{
    Node p=*A;
    *A=*B;
    *B=p;

    B->next = A->next;
    B->prev = A->prev;

    A->next = p.next;
    A->prev = p.prev;
}

void swapNode(List *listNode, char nameA[30], char nameB[30])
{
    Node *A = NULL, *B = NULL;
    Node *temp = listNode->head;

    for (int i = 0; i < listNode->count; i++)
    {
        if (compareName(temp->name, nameA))
        {
            A = temp;
        }
        else if (compareName(temp->name, nameB))
        {
            B = temp;
        }
        temp = temp->next;
        if (A && B)
        {
            break;
        }
    }

    if ((A && B) && (A != B))
    {
        doSwap(A,B);
    }
}

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

A Good Habit for Programming in C and C++

For readability and maintainability a good good habit (best practice) to get into is to always put the actions in if statements and loops into braces ({ and }) as shown in the previous example. One of the major causes of bugs is to add a single line to the contents of an iff statement and to forget to add the necessary the necessary braces. This type of problem is very hard to track down when it doesn't result in a compiler error.

Leaks

Are there any errors like memory leak in my code?

If the code was part of a larger project there would be memory leaks, the function free(void *ToBeFreed) is never called. It might be better if some linked list operations such as deleteNode() were added to the code.

\$\endgroup\$
  • \$\begingroup\$ I think function safeMalloc is not necessary because as far as I concern, when we allocate a pointer by malloc calloc or realloc compiler will set some adjacent bytes in RAM so it can not be NULL pointer. Am I right? @pacmaninbw \$\endgroup\$ – Becker Jan 22 at 15:40
  • \$\begingroup\$ No, you are absolutely wrong. Given current RAM sizes it is rare for malloc to fail, but if it does fail the return value is NULL. \$\endgroup\$ – pacmaninbw Jan 22 at 15:58
  • \$\begingroup\$ so how do we know a pointer is failed to allocate memory, it is random or have a condition? \$\endgroup\$ – Becker Jan 22 at 16:04
  • \$\begingroup\$ @Becker in more modern languages such as C++, C# and Java memory allocation errors throw exceptions, the C programming languages is more of a high level assembler than most high level languages and memory allocation is just memory allocation and nothing else \$\endgroup\$ – pacmaninbw Jan 22 at 16:04
  • \$\begingroup\$ @pacmaninbw Rust is plenty modern, and it doesn't have exceptions. Also, C isn't anywhere near high level assembly, otherwise it wouldn't be possible to optimize it so much. Sure, JVM and .Net languages do far more to keep you from the metal, with all the advantages and disadvantages that implies. \$\endgroup\$ – Deduplicator Jan 22 at 18:15
3
\$\begingroup\$

I get quite a lot of warnings when compiling with a reasonably picky compiler¹. Many are due to assigning string literals (const char*) to char* variables, which risks attempting invalid writes. For example:

236002.c: In function ‘main’:
236002.c:172:30: warning: passing argument 3 of ‘insertHead’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  172 |     insertHead(listNode, 10, "abc def");
      |                              ^~~~~~~~~
236002.c:163:49: note: expected ‘char *’ but argument is of type ‘const char *’
  163 | void insertHead(list *listNode, int point, char name[30]);
      |                                            ~~~~~^~~~~~~~

main() and createList() are declared as accepting unspecified arguments; it's good practice to declare them taking no arguments:

list *createList(void);
int main(void);

We call allocateNewNode() which doesn't exist - perhaps that should be createNewNode()?

There are return statements with a value, in a function declared to return void. That needs to be fixed.

Once the code compiles, we can run it under Valgrind and see what it says:

==2746238== HEAP SUMMARY:
==2746238==     in use at exit: 304 bytes in 6 blocks
==2746238==   total heap usage: 7 allocs, 1 frees, 1,328 bytes allocated
==2746238== 
==2746238== 304 (24 direct, 280 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==2746238==    at 0x483677F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2746238==    by 0x1092B7: createList (236002.c:68)
==2746238==    by 0x109161: main (236002.c:36)
==2746238== 
==2746238== LEAK SUMMARY:
==2746238==    definitely lost: 24 bytes in 1 blocks
==2746238==    indirectly lost: 280 bytes in 5 blocks
==2746238==      possibly lost: 0 bytes in 0 blocks
==2746238==    still reachable: 0 bytes in 0 blocks
==2746238==         suppressed: 0 bytes in 0 blocks

That's disappointing: we have failed to clean up the memory we allocated - some malloc() or similar is not matched with a corresponding free().

Looking in detail at the code, I see a function compareName() that seems to be mostly a reimplementation of strncmp() - do familiarise yourself with the Standard C Library, and use it to avoid reimplementing functions that have been written for you (generally more robustly and efficiently).

The creation functions allocate memory, but always assume that malloc() was successful. That's a latent bug - it can return a null pointer if it fails. A minimal check could just bail out in that case:

node *newNode = malloc(sizeof *newNode);
if (!newNode) {
    fputs("Memory allocation failure.\n", stderr);
    exit(EXIT_FAILURE);
}

Note: malloc() returns a void*, which needs no cast to be assigned to any pointer variable. And we take the sizeof the pointed-to object, which is easier to check than having to look up its type.

More library-orientated code will just return NULL early, to pass the error on to the caller to handle.

The list structure is unusual - we don't normally use a count, but just let a sentinel pointer in next (either a null pointer, or a pointer back to a dummy head) indicate the end of the list. The code seems to use a mix of both, sometimes counting (e.g. in swapNode()) and sometimes chasing pointers (e.g. in main()).


¹ gcc -std=c17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wstrict-prototypes -Wconversion

\$\endgroup\$
  • \$\begingroup\$ could you please give me an e.g. about Many are due to assigning string literals (const char*) to char* variables, which risks attempting invalid writes. \$\endgroup\$ – Becker Jan 23 at 3:51
  • \$\begingroup\$ I've edited to include the first of those warnings. HTH. \$\endgroup\$ – Toby Speight Jan 23 at 8:50
  • \$\begingroup\$ my compiler does not show that warning. I have search for "picky compiler" but there is no tutorial to set up picky compiler. Could you show me how to set up it please? \$\endgroup\$ – Becker Jan 23 at 10:30
  • \$\begingroup\$ Did you read the footnote showing my GCC options? Most reputable compilers have a similar set of warnings that you'd want to enable (just try searching for your compiler name with "all warnings" or similar). \$\endgroup\$ – Toby Speight Jan 23 at 10:45
  • \$\begingroup\$ ok, I have just turn on some GCC options but when I compile code there is no warning. How to fix it? \$\endgroup\$ – Becker Jan 23 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.