[Das Kartoffel]

Hello Guys,

After doing quite some C++, I decided to do some work on C and began working on Linked Lists. I ended up with a code I have made for training and am seeking your reviews and advices regarding what I did wrong or what I forgot.

Here is the code:



Note that I haven't been using free() at all, as according go Windows ressources monitor, no RAM was being released when freeing structs in either of the pop_* functions, that when I was using free(). Maybe was I doing it wrong ?

Thanks.

[Goodies]

Oh no you should be calling free once for every malloc.

---

It seems that your node_t** functions are taking in a double pointer unnecessarily. It can, and should, be done with a single pointer if, for nothing else, to be inform with the rest of your code.

[Kantos]

Oh no you should be calling free once for every malloc.

---

It seems that your node_t** functions are taking in a double pointer unnecessarily. It can, and should, be done with a single pointer if, for nothing else, to be inform with the rest of your code.

The double pointer used in functions that modify the head of the list. Using a single pointer, you would need to return the modified list (whose head pointer is a copy of the one you passed in) and assign it back to the head.

So it depends on whether you want this:

push_back(list, val);
push_front(&list, val);

or this

push_back(list, val);
list = push_front(list, val);

If you really want each function to be consistent and take a single pointer, then you could do so by creating a List struct that contains a pointer to head. Each function would then take a pointer to a List as an argument and it can modify head if it needs to. It also makes it cleaner when adding niceties like a tail pointer and a length variable.

[Goodies]

The double pointer used in functions that modify the head of the list. Using a single pointer, you would need to return the modified list (whose head pointer is a copy of the one you passed in) and assign it back to the head.

So it depends on whether you want this:

push_back(list, val);
push_front(&list, val);

or this iii

push_back(list, val);
list = push_front(list, val);

If you really want each function to be consistent and take a single pointer, then you could do so by creating a List struct that contains a pointer to head. Each function would then take a pointer to a List as an argument and it can modify head if it needs to. It also makes it cleaner when adding niceties like a tail pointer and a length variable.

Not going to lie. I didn't even check the code, but that should have been obvious to me. I'd prefer creating a new type that has its own head/tail and just pass that in. At least that way it is all the same.

---

Edit: oh that's pretty much what you said.

[Kantos]

Not going to lie. I didn't even check the code, but that should have been obvious to me. I'd prefer creating a new type that has its own head/tail and just pass that in. At least that way it is all the same.

---

Edit: oh that's pretty much what you said.

Yeah. With C++'s pass by reference this isn't an issue either. But from a C and code readability standpoint pass by reference annoys me since you can't tell whether a function can modify its arguments without looking at the declarations.

[Goodies]

Yeah. With C++'s pass by reference this isn't an issue either. But from a C and code readability standpoint pass by reference annoys me since you can't tell whether a function can modify its arguments without looking at the declarations.

Winapi has a nice nomenclature that solves the issue. I've sometimes used it in my own code. It's called SAL:
https://msdn.microsoft.com/en-us/library....110).aspx

Basically, just have some empty PP definitions like:

PHP Code


<?php 
#define _IN_
#define _IN_OUT_
#define _OUT_ 


That way:

PHP Code


<?php 
void foo(int *ptr1, int *ptr2); 


become:

PHP Code


<?php 
void foo(_IN_ int *ptr1, _OUT_ int *ptr2); 


From that, you can tell that ptr2 will be altered. ptr1 may be able to be passed as const, but the one thing we know for sure is that it's an input.

---

Just started writing up my own simple implementation.

Doubly-linked "managed" list in the sense that the size and front/back are tracked.

Give me an hour or so.

---

Ran into some issues because I totally forgot that C doesn't have overloaded functions.

This is just a preliminary one for push/pop and stuff like that.

MyList.h

PHP Code


<?php 
#define MYLIST_H
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ALLOC_ERR    -1    // Hopefully never returned...
#define SUCCESS        0    // Hopefully almost always returned...
#define NOT_EMPTY    1    // returned when checking if the list is empty
#define EMPTY        2    // returned when popping
#define INDEX_ERR    3    // returned when getting/setting/removing

/*
    This macro's purpose is to check the createFirstNode() return value.
    If there was an allocation error, return the same error.
    If it successfully allocated a new node, return success.
    If the list is not empty, then continue execution after the check.
*/
#define CHECKFIRSTNODE(status) \
    switch (status) { \
    case ALLOC_ERR: \
    case SUCCESS: \
        return status; \
    }
#define RETIFNULL(var) if(var == NULL) return;
#define RETVALIFNULL(var, val) if(var == NULL) return val;

typedef int node_val, *pnode_val, **ppnode_val;
typedef struct node_s node_t, *pnode_t;

/*
    Each node has a pointer to the next and previous node. If there is only one node, both are NULL.
    The "head" should always point to a node with a "prev" of NULL.
    The "tail" should always point to a node with a "next" of NULL.
*/
typedef struct node_s {
    pnode_t prev;
    pnode_t next;
    node_val val;
} node_t, *pnode_t;

/*
    Each list instance has a pointer to the head of the list and the tail of the list as well as the number of items in the list.
    The head and tail should either both be NULL, or neither be NULL.
    If there is one element, then they point to the same item. (i.e. do not free by head/tail)
*/
typedef struct list_s {
    size_t size;
    pnode_t head;
    pnode_t tail;
} list_t, *plist_t;

plist_t createList(void);                /*    Creates an empty list instance (head and tail are NULL) and returns it. */
void deleteList(plist_t);                /*    Iterates through all items in the list and deallocates all nodes.
                                            If node_val contains data that must be freed, it should be done prior to deleting the list.    */

/*
    These functions pertain to altering the list. They each receive a list_t pointer as a parameter.
    A node_val value is either received (when pushing) or returned (when popping).
*/

// This will be called if the head/tail is NULL.
int createFirstNode(plist_t list, node_val val);
//int createFirstNode(plist_t list, pnode_val pval);

// Pushing will return 0 upon success and non-zero upon failure.
int pushBack(plist_t, node_val);
int pushFront(plist_t, node_val);

// Poping will retrieve the value from the list and de-allocate the node assosciated with it, settings the head's prev or tail's next to NULL;
int popBack(plist_t, pnode_val);
int popFront(plist_t, pnode_val); 


MyList.c

PHP Code


<?php 
#include "MyList.h"

plist_t createList() {
    plist_t t = (plist_t)malloc(sizeof(list_t));
    RETVALIFNULL(t, NULL);
    t->size = 0;
    t->head = NULL;
    t->tail = NULL;
    return t;
}

void deleteList(plist_t list) {
    if (list) {
        if (list->head != NULL && list->tail != NULL) // if one is NULL, they both should be, but just in case
            for (pnode_t cur = list->head, next = NULL; cur != NULL; cur = next) {
                next = cur->next;
                free(cur);
            }
        return free(list);
    }
}

int createFirstNode(plist_t list, node_val val) {
    if (list->head == NULL && list->tail == NULL) {
        list->head = (pnode_t)malloc(sizeof(node_t));
        RETVALIFNULL(list->head, ALLOC_ERR);
        list->head->val = val;
        list->head->next = list->head->prev = NULL;
        list->tail = list->head;
        return list->size = 1, SUCCESS;
    }
    return NOT_EMPTY;
}

int pushBack(plist_t list, node_val val) {
    CHECKFIRSTNODE(createFirstNode(list, val));
    list->tail->next = (pnode_t)malloc(sizeof(node_t));
    RETVALIFNULL(list->tail->next, ALLOC_ERR);
    pnode_t tmpTail = list->tail;
    list->tail = list->tail->next;
    list->tail->val = val;
    list->tail->prev = tmpTail;
    list->tail->next = NULL;

    return list->size++, SUCCESS;
}

int pushFront(plist_t list, node_val val) {
    CHECKFIRSTNODE(createFirstNode(list, val));

    list->head->prev = (pnode_t)malloc(sizeof(node_t));
    RETVALIFNULL(list->head->prev, ALLOC_ERR);

    pnode_t tmpHead = list->head;
    list->head = list->head->prev;
    list->head->val = val;
    list->head->next = tmpHead;
    list->head->prev = NULL;

    return list->size++, SUCCESS;
}

int popBack(plist_t list, pnode_val pval) {
    if (list->size == 0)
        return pval = NULL, EMPTY;
    
    pnode_t tmpNode = list->tail;
    list->tail = list->tail->prev;

    if (list->tail == NULL) 
        list->head = NULL;
    else
        list->tail->next = NULL;

    *pval = tmpNode->val;
    free(tmpNode);
    return list->size--, SUCCESS;
}

int popFront(plist_t list, pnode_val pval) {
    if (list->size == 0)
        return pval = NULL, EMPTY;

    pnode_t tmpNode = list->head;
    list->head = list->head->next;

    if (list->head == NULL)
        list->tail = NULL;
    else
        list->head->prev = NULL;

    *pval = tmpNode->val;
    free(tmpNode);
    return list->size--, SUCCESS;
} 


Main.c:

PHP Code


<?php 
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#include "MyList.h"

void foo() {
    plist_t list = createList();
    pushBack(list, 10);
    pushBack(list, 20);
    pushFront(list, 55);

    int i = 0;
    while(!popBack(list, &i))
        printf("Number: %i\n", i);

    deleteList(list);
}

int main(int argc, char **argv) {
    foo();
    _CrtDumpMemoryLeaks();
    fgetc(stdin);
    return 0;
} 


[Das Kartoffel]

Thank you guys for your advices.
Effectively, I'm passing double pointer as I alter the original head being passed as it looks better to me 😉.

Also, how would I use free() ? As Windows Monitor wasn't changing the RAM being used on popping while it was increasing it when doing malloc. Is it the Windows Monitor which is just bad or did I do something wrong ? Here is what I was using with pop_back().

PHP Code


<?php 
void pop_back(node_t *head)
{
    node_t *current = head;
    while (current->next->next != NULL)
        current = current->next;
   
    free(current->next);
    current->next = NULL;
} 


[Goodies]

Thank you guys for your advices.
Effectively, I'm passing double pointer as I alter the original head being passed as it looks better to me 😉.

Also, how would I use free() ? As Windows Monitor wasn't changing the RAM being used on popping while it was increasing it when doing malloc. Is it the Windows Monitor which is just bad or did I do something wrong ? Here is what I was using with pop_back().

PHP Code


<?php 
void pop_back(node_t *head)
{
    node_t *current = head;
    while (current->next->next != NULL)
        current = current->next;
   
    free(current->next);
    current->next = NULL;
} 


You use free literally every time you use malloc. It should be a 1:1 with very few exceptions, if any.

That code will work assuming there is at least two elements. If you try to do that while only having one element (i.e. head->next is NULL) then you will get a null dereference error.

[Ashlanfox]

What you should do:

• Create a function which instantiate a node, it would make your code cleaner and easier for debugging purposes.
  


• Use accessors for your structure.
  


• Consider using ODT as a model for such structures, more information here: https://en.wikipedia.org/wiki/Opaque_data_type