Programmer's notes: December 2023

There is a beautiful morning. It's snowing. And I decided to write one more article. Today it will be just simple article where I would like to present my version how singly linked list can be reversed in C.

At first we need to define our list:

typedef struct list_s {
	int data;
	struct list_s* next;
} list_t, *list_p, **list_pp;

In this code the variable data is some data. In our case its type is INTEGER (int). The variable next is a pointer to next element.

So, now we need to write a function that will print our list:

void print_list(list_p l) {
	while(l) {
		UNUSED(printf("%d ", l->data));
		l = l->next;
	}
	UNUSED(puts(""));
}

Because some functions return result which we don't want to use and if we don't want to see any warnings in some compilers I think we need to suppress potential warnings. Because of that I created macro called UNUSED. It's just explicit cast to void type.

1	#define UNUSED(x) (void) x

Now we need to write functions which will reverse our list. I will write two functions.
The first function gets pointer to list, reverses this list and after that returns new pointer, but argument of this function is still without changes.

list_p reverse_list(list_p l) {
	list_p new_head = NULL;
	
	while(l) {
		list_p next = l->next;
		l->next = new_head;
		new_head = l;
		l = next;
	};

	return new_head;
}

The second function gets pointer to pointer to list, reverses this list and after that returns new pointer but as argument (not through return). In other words this function will change input argument.

void reverse_list_self(list_pp l) {
	list_p new_head = NULL;
	list_p lst = *l;

	while(lst) {
		list_p next_lst = lst->next;
		lst->next = new_head;
		new_head = lst;
		lst = next_lst;
	}

	*l = new_head;
}

Currently we have function for printing, two functions for reversing and struct which describes our list. And now we have to write main function. This function also has to create our list. I would like to tell that it's just example so I will not read return code of some functions and I will not handle any memory errors and read errno.
By the way I could be not use UNUSED macro because I use gcc compiler and it does not argue if I don't read return code of printf or pust functions.

int main() {
	list_p list = NULL;

	/* Fill */
	for(unsigned int i = 10; i > 0; --i) {
		list_p el = malloc(sizeof(*list));
		el->data = i;
		el->next = list;
		list = el;
	}

	print_list(list);

	list = reverse_list(list);

	print_list(list);

	reverse_list_self(&list);
	
	print_list(list);
	
	return EXIT_SUCCESS;
}

So currently we are able to assemble all code parts in one program.

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

#define UNUSED(x) (void) x

typedef struct list_s {
	int data;
	struct list_s* next;
} list_t, *list_p, **list_pp;

static void print_list(list_p l);
static list_p reverse_list(list_p l);
static void reverse_list_self(list_pp l);

int main() {
	list_p list = NULL;

	/* Fill */
	for(unsigned int i = 10; i > 0; --i) {
		list_p el = malloc(sizeof(*list));
		el->data = i;
		el->next = list;
		list = el;
	}

	print_list(list);

	list = reverse_list(list);

	print_list(list);

	reverse_list_self(&list);
	
	print_list(list);
	
	return EXIT_SUCCESS;
}

void print_list(list_p l) {
	while(l) {
		UNUSED(printf("%d ", l->data));
		l = l->next;
	}
	UNUSED(puts(""));
}

list_p reverse_list(list_p l) {
	list_p new_head = NULL;
	
	while(l) {
		list_p next = l->next;
		l->next = new_head;
		new_head = l;
		l = next;
	};

	return new_head;
}

void reverse_list_self(list_pp l) {
	list_p new_head = NULL;
	list_p lst = *l;

	while(lst) {
		list_p next_lst = lst->next;
		lst->next = new_head;
		new_head = lst;
		lst = next_lst;
	}

	*l = new_head;
}

/*
 * The end of the file
 */

Let's compile our code:

$ ls -lah
total 4.0K
drwxr-xr-x 2 bodro bodro   20 Dec 29 13:47 .
drwxr-xr-x 5 bodro bodro   92 Oct  1  2021 ..
-rw-r--r-- 1 bodro bodro 1.1K Oct  1  2021 main.c
$ gcc -Wall -Wextra -Wpedantic -o main main.c 
$ ls -lah
total 20K
drwxr-xr-x 2 bodro bodro   32 Dec 29 13:48 .
drwxr-xr-x 5 bodro bodro   92 Oct  1  2021 ..
-rwxr-xr-x 1 bodro bodro  16K Dec 29 13:48 main
-rw-r--r-- 1 bodro bodro 1.1K Oct  1  2021 main.c
$ file main
main: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV),
dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2,
BuildID[sha1]=087a2c8d0fd1b8fee07a6b84806ae9698ae84424, for GNU/Linux 3.2.0, not stripped
$ strip --strip-all main
$ file main
main: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV),
dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2,
BuildID[sha1]=087a2c8d0fd1b8fee07a6b84806ae9698ae84424, for GNU/Linux 3.2.0, stripped
$ ls -lah
total 20K
drwxr-xr-x 2 bodro bodro   32 Dec 29 13:49 .
drwxr-xr-x 5 bodro bodro   92 Oct  1  2021 ..
-rwxr-xr-x 1 bodro bodro  15K Dec 29 13:49 main
-rw-r--r-- 1 bodro bodro 1.1K Oct  1  2021 main.c
$

As we can see it was compiled correctly.

Shall we check?

$ ./main 
1 2 3 4 5 6 7 8 9 10 
10 9 8 7 6 5 4 3 2 1 
1 2 3 4 5 6 7 8 9 10
$

OK. I hope you understand that our code works. :)

So today we wrote simple code that reverses singly linked list in C without temporary lists or arrays. It's just simple task however you can meet it when you try to pass any interview.

Have a nice day my friends! And Happy coming New Year! :)

Best regards,

Vasiliy V. Bodrov aka Bodro,

the 29-th of December, 2023.

Hi, my friends and just everyone! :)

You shouldn't think that I forgot about my blog. After more then 6 years I decided to continue writing articles. And I'm glad to present my new article about strange behavior of C++ compilers. However, the reason maybe more interesting. E.g. in C++ standards.

So today I would like to talk about implicit type conversions and particular about implicit narrowing conversion of types.

Me and my friends were sure that if we can lose data the compiler has to show error or at least show warning.
Actually, look at this:

#include <cstdint>

void f(uint16_t) {}

int main() {
    uint32_t x = 0xFFFFFFFF;
    f(x);
}

I think you are sure that gcc or clang compilers have to show warning or error? :) But no!

$ rm -f a.out; g++ main1.cpp && ./a.out
$ rm -f a.out; clang++ main1.cpp && ./a.out
$

As we can see there are no any warnings or errors. Hmmm. Ok! Maybe we can use special warnings level? No problem!

$ rm -f a.out; g++ -Wall -Wextra -Wpedantic main1.cpp && ./a.out
$ rm -f a.out; clang++ -Wall -Wextra -Wpedantic main1.cpp && ./a.out
$

So, we don't see any warnings or errors. And any warnings flags couldn't help. In that case we can write the program which can demonstrate big problems with that behavior.

#include <iostream>
#include <cstdint>

void Bob(uint16_t x) {
    std::cout << "I'm Bob. My salary is $"
              << x
              << std::endl;
}

struct Snob {
    Snob(uint16_t x) {
        std::cout << "I'm Snob and my salary is $"
                  << x
                  << std::endl;
    }
};

int main() {
    uint32_t x = 0xFFFF0001; // 4294901761

    std::cout << "I'm the boss and I would like to give money to Bob and Snob. "
              << "Guys! Take your salary! "
              << "It is $"
              << x
              << std::endl;
    
    Bob(x);

    Snob snob(x);
}

The result (gcc):

$ rm -f a.out; g++ -std=c++17 -Wall -Wextra -Wpedantic main2.cpp && ./a.out
I'm the boss and I would like to give money to Bob and Snob. Guys! Take your salary!
It is $4294901761
I'm Bob. My salary is $1
I'm Snob and my salary is $1
$

The result (clang):

$ rm -f a.out; clang++ -std=c++17 -Wall -Wextra -Wpedantic main2.cpp && ./a.out
I'm the boss and I would like to give money to Bob and Snob. Guys! Take your salary!
It is $4294901761
I'm Bob. My salary is $1
I'm Snob and my salary is $1
$

OK? Do you understand what problems can be? Currently, I have no idea about reasons. I have not found the explanation of this behavior yet. So if you know I would be happy if you could explain to me.

Have a nice time! :)

Best regards,

Vasiliy V. Bodrov aka Bodro,

the 28-th of December, 2023.

Programmer's notes

Friday, December 29, 2023

How to reverse singly linked list in C (trivial way)

Thursday, December 28, 2023

Narrowing type conversions in C/C++

How to reverse singly linked list in C (trivial way)