Home | Projects | Notes > Multi-Threading (POSIX Threads) > Thread Synchronization - Thread-Safe Highly Concurrent CRUD Operations - Demonstration

Thread Synchronization - Thread-Safe Highly Concurrent CRUD Operations - Demonstration

This section demonstrates a 100% thread-safe, accurate, highly-concurrent, and deadlock free application whose state is guaranteed to be consistent at any given point in time.

Demo Project Setup

Create a folder containing the following header & source files:
- crud_algorithm.c - CRUD algorithm (main)
- linked_list.h, linked_list.c - Linked list data structure
- ref_count.h, ref_count.c - Reference count data structure
- student_list.h, student_list.c - Student list data structure

Build using:


xxxxxxxxxx
1
1
gcc *.c -lpthread

Run using:
```
xxxxxxxxxx
1
1
./a.out
```
To analyze the outputs using the log file:
```
xxxxxxxxxx
1
1
./a.out > log
```
Open log.
Find deferred deletion (/deferred) - Let's say we found DELETE TH :: Roll No 9 deletion deferred.
Extract info we are interested in (grep "Roll No 9" log > rollno9.txt)

$\to$ Inspect the change in loop_count variable.
1. gdb a.out $\to$ run .
2. Ctrl+c to stop the program.
3. Print the loop count using print loop_count or p loop_count and save it.
4. Continue running the program by using continue or c.
5. Ctrl+c to stop the program again.
6. Check the value of loop_count and compare it with the previously saved value.
  If each element of loop_count has increased, then we can conclude that there's no deadlock.
7. Repeat 4~6 and monitor if there's any element that has not changed at all. If there an element that's not changing forever, we can conclude that the corresponding thread is situated in a deadlock.

Demo Project and Deadlocks

Is our demo project deadlock-free?
- Yes, provided that a thread holds lock on only one student object at any given point in time.
- No, deadlock may occur if a thread works with 2 or more student objects at any given point in time.
  In this case, Deadlock Detection Algorithms must be deployed as a part of your project to guarantee deadlock-free execution.
Since we have designed the program in such a way that no thread holds 2 or more student objects at the same time, deadlock will NOT occur.
CRUD operations usually involve a thread performing operations only on 1 object at a time. If a thread need to update more than 1 objects, it should update them one by one. (Do not hold write lock on more than 1 object at a time.)
These CRUD algorithms are being used in industry gracefully without assistance of any Deadlock Detection Algorithms.

Demo Source Code

Implementation of CRUD Algorithm


xxxxxxxxxx
264
1
/*
2
 * File Name    : crud_algorithm.c
3
 * Description  : Implementation of CRUD algorithm
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#include <stdio.h>
9
#include <stdlib.h>
10
#include <assert.h>
11
#include "student_list.h"
12

13
#if 0
14

15
 Signs that this program is erroneous :
16
 1. Any threads goes in Deadlock ( you will cease to see output from 1 or more threads )
17
 2. Marks of student update by more than INCR
18
 3. Any crash
19
 4. New Read/Write Operation is performed on a student whose deletion is deferred
20
 5. Student after "delete deferred" , not actually deleted
21
 6. Memory Leak ( of student objects )
22
 7. Ref Count value of student object goes too high ( more than 4 )
23

24
#endif
25

26
#define MAX_ROLL_NO 10
27
#define INCR 5
28

29
enum {
30
    READER_TH,
31
    UPDATE_TH,
32
    CREATE_TH,
33
    DELETE_TH,
34
    THREAD_TYPE_MAX
35
} th_type_t;
36

37
static pthread_t threads[THREAD_TYPE_MAX];
38
static uint32_t loop_count[THREAD_TYPE_MAX];
39

40
static stud_lst_t stud_lst; /* Container Object */
41

42
static void* reader_fn (void *arg)
43
{
44
    student_t *stud;
45
    uint32_t roll_no;
46

47
    while(1)
48
    {
49
        loop_count[READER_TH]++;
50

51
        roll_no = rand() % MAX_ROLL_NO; /* now, reader thread knows which student it needs
52
                                           to perform a read operation on */
53
        pthread_rwlock_rdlock(&stud_lst.rw_lock);
54

55
        stud = student_lst_lookup(&stud_lst, roll_no);
56

57
        if (!stud)
58
        {
59
            printf("READ TH  ::  Roll No %u Do not Exist\n", roll_no);
60
            pthread_rwlock_unlock(&stud_lst.rw_lock);
61
            continue;
62
        }
63

64
        /* current thread got an access to object */
65
        thread_using_object(&stud->ref_count);
66

67
        /* prepare to perform READ operation on student object */
68
        pthread_rwlock_rdlock(&stud->rw_lock);
69

70
        /* current thread has done all pre-requisites to perform read operation on 
71
           the student object, unlock the container level lock */
72
        pthread_rwlock_unlock(&stud_lst.rw_lock);
73

74
        /* now perform the READ operation */
75
        printf("READ TH  ::  Roll No %u is READ, total marks = %u\n", 
76
                roll_no, stud->total_marks);
77

78
        /* unlock the Student object */
79
        pthread_rwlock_unlock(&stud->rw_lock);
80

81
        /* done using the object */
82
        if (thread_using_object_done (&stud->ref_count))
83
        {
84
            printf("READ TH  ::  Roll No %u READ Done\n",  roll_no);
85
            student_destroy (stud);
86
            printf("READ TH :: Roll No %u destroyed\n", roll_no);
87
            continue;
88
        }
89
        else 
90
        {
91
            /* Never attempt to access stud object here or after this line in program*/
92
            printf ("READ TH  ::  Roll No %u READ Done\n", roll_no);
93
        }
94
    }
95

96
    return NULL;
97
}
98

99
static void* update_fn (void *arg)
100
{
101
    student_t *stud;
102
    uint32_t roll_no;
103

104
    while(1)
105
    {
106
        loop_count[UPDATE_TH]++;
107
        
108
        roll_no = rand() % MAX_ROLL_NO; /* now, writer thread knows which student it needs
109
                                           to perform a read operation on */
110
        pthread_rwlock_rdlock (&stud_lst.rw_lock);
111

112
        stud = student_lst_lookup (&stud_lst, roll_no);
113

114
        if (!stud)
115
        {
116
            printf ("UPDATE TH  ::  Roll No %u Do not Exist\n", roll_no);
117
            pthread_rwlock_unlock (&stud_lst.rw_lock);
118
            continue;
119
        }
120

121
        /* current thread got an access to object */
122
        thread_using_object(&stud->ref_count);
123

124
        /* prepare to perform WRITE Operation on student object */
125
        pthread_rwlock_wrlock(&stud->rw_lock);
126

127
        /* current thread has done all pre-requisites to perform write operation on 
128
           the student object, unlock the container level lock */
129
        pthread_rwlock_unlock(&stud_lst.rw_lock);
130

131
        /* now perform UPDATE operation */
132
        uint32_t old_marks = stud->total_marks;
133
        stud->total_marks = stud->total_marks + INCR;
134
        stud->total_marks = stud->total_marks % 100;
135

136
        printf ("UPDATE TH  ::  Roll No %u , Increment %d, Marks Update %u --> %u\n",
137
            stud->roll_no, INCR, old_marks, stud->total_marks);
138

139
        /* unlock the Student Object */
140
        pthread_rwlock_unlock(&stud->rw_lock);
141

142
        /* done using the object */
143
        if (thread_using_object_done (&stud->ref_count))
144
        {
145
            printf ("UPDATE TH  ::  Roll No %u UPDATE Done\n",  roll_no);
146
            student_destroy (stud);
147
            printf ("UPDATE TH :: Roll No %u destroyed\n", roll_no);
148
            continue;
149
        }
150
        else
151
        {
152
            /* never attempt to access stud object here or after this line in program*/
153
            printf ("UPDATE TH  ::  Roll No %u UPDATE Done\n",  roll_no);
154
        }
155
    }
156

157
    return NULL;
158
}
159

160
static void* create_fn (void *arg)
161
{
162
    uint32_t roll_no;
163
    student_t *new_stud;
164

165
    while (1)
166
    {
167
        loop_count[CREATE_TH]++;
168

169
        roll_no = rand() % MAX_ROLL_NO;
170

171
        pthread_rwlock_wrlock (&stud_lst.rw_lock);
172

173
        new_stud = student_lst_lookup(&stud_lst, roll_no);
174

175
        if (new_stud)
176
        {
177
            printf ("CREATE TH :: Roll No %u CREATION Failed, Already Exist\n", roll_no);
178
            pthread_rwlock_unlock (&stud_lst.rw_lock);
179
            continue;
180
        }
181

182
        new_stud = student_malloc(roll_no);
183
        assert(student_lst_insert(&stud_lst, new_stud));
184
        ref_count_inc(&new_stud->ref_count);
185
        printf ("CREATE TH :: Roll No %u CREATION Success\n", new_stud->roll_no);
186

187
        pthread_rwlock_unlock (&stud_lst.rw_lock);
188
    }
189

190
    return NULL;
191
}
192

193
static void* delete_fn (void *arg)
194
{
195
    uint32_t roll_no;
196
    student_t *stud;
197

198
    while (1)
199
    {
200
        loop_count[DELETE_TH]++;
201

202
        roll_no = rand() % MAX_ROLL_NO;
203

204
        pthread_rwlock_wrlock (&stud_lst.rw_lock);
205

206
        stud = student_lst_remove (&stud_lst, roll_no);
207

208
        if (!stud)
209
        {
210
            printf("DELETE TH :: Roll No %u DELETION Failed, Do not Exist\n", roll_no);
211
            pthread_rwlock_unlock(&stud_lst.rw_lock);
212
            continue;
213
        }
214

215
        /* switching the order of the following two statements will results in crash */
216
        thread_using_object(&stud->ref_count);
217
        assert(!ref_count_dec(&stud->ref_count));
218

219
        pthread_rwlock_unlock(&stud_lst.rw_lock);
220

221
        printf("DELETE TH :: Roll No %u Removal Success\n", roll_no);
222

223
        /* done using the object */
224
        if (thread_using_object_done (&stud->ref_count))
225
        {
226
            student_destroy (stud);
227
            printf ("DELETE TH :: Roll No %u destroyed\n", roll_no);
228
        }
229
        else
230
        {
231
            /* delete thread cannot delete the object since it is currently being used by 
232
               another thread (in this case, the thread currently using the object will
233
               delete it when done with the currently on-going operation) */
234
            printf ("DELETE TH :: Roll No %u deletion deferred\n", roll_no);
235
        }
236

237
    }
238

239
    return NULL;
240
}
241

242
int main (int argc, char *argv[])
243
{
244
    stud_lst.lst = init_singly_ll();
245
    pthread_rwlock_init(&stud_lst.rw_lock, NULL);
246

247
    loop_count[READER_TH] = 0;
248
    loop_count[UPDATE_TH] = 0;
249
    loop_count[CREATE_TH] = 0;
250
    loop_count[DELETE_TH] = 0;
251

252
    pthread_attr_t attr;
253
    pthread_attr_init(&attr);
254
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
255

256
    pthread_create (&threads[READER_TH], &attr, reader_fn, NULL);
257
    pthread_create (&threads[UPDATE_TH], &attr, update_fn, NULL);
258
    pthread_create (&threads[CREATE_TH], &attr, create_fn, NULL);
259
    pthread_create (&threads[DELETE_TH], &attr, delete_fn, NULL);
260

261
    pthread_exit(0); /* so that the termination of the main thread does not force the
262
        termination of the spawned threads */
263
    return 0;
264
}

If in the program, you could find any sequence of instructions that will lead to an inconsistent state (e.g., update thread still accessing the element which has already been destroyed by delete thread) of the system, then your CRUD algorithm is INACCURATE! By coming up with different possible scenarios (sequence of execution) and keeping track of the reference count, you will be able to identify possible inconsistencies.

Sequence diagrams help analyzing the flow of the threads.

See Thread Synchronization - Thread-Safe Highly Concurrent CRUD Operations for the sequence diagrams.

Interface for Reference Count Data Structure


xxxxxxxxxx
28
1
/*
2
 * File Name    : ref_count.h
3
 * Description  : Interface for reference count data structure
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#ifndef REF_COUNT_H
9
#define REF_COUNT_H
10

11
#include <pthread.h>
12
#include <stdint.h>
13
#include <stdbool.h>
14

15
typedef struct ref_count_
16
{
17
    uint32_t ref_count;             /* can't go negative */
18
    pthread_spinlock_t spinlock;    /* to support provide mutual exclusion */
19
} ref_count_t;
20

21
void ref_count_init(ref_count_t *ref_count);
22
void ref_count_inc(ref_count_t *ref_count);
23
bool ref_count_dec(ref_count_t *ref_count); /* returns true if ref_count after dec is zero*/
24
void ref_count_destroy(ref_count_t *ref_count);
25
void thread_using_object(ref_count_t *ref_count);
26
bool thread_using_object_done(ref_count_t *ref_count);
27

28
#endif /* REF_COUNT_H */

Implementation of Reference Count Data Structure


xxxxxxxxxx
51
1
/*
2
 * File Name    : ref_count.c
3
 * Description  : Implementation of reference count data structure
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#include <assert.h>
9
#include "ref_count.h"
10

11
void ref_count_init(ref_count_t *ref_count)
12
{
13
    /* initialize members */
14
    ref_count->ref_count = 0;
15
    pthread_spin_init(&ref_count->spinlock, PTHREAD_PROCESS_PRIVATE);
16
}
17

18
void ref_count_inc(ref_count_t *ref_count)
19
{
20
    pthread_spin_lock(&ref_count->spinlock);
21
    ref_count->ref_count++;
22
    pthread_spin_unlock(&ref_count->spinlock);
23
}
24

25
/* returns true if ref_count after decrement is zero*/
26
bool ref_count_dec(ref_count_t *ref_count)
27
{
28
    bool rc;
29
    pthread_spin_lock(&ref_count->spinlock);
30
    assert(ref_count->ref_count); /* ensure that ref_count never goes below zero */
31
    ref_count->ref_count--;
32
    rc = (ref_count->ref_count == 0) ? true : false; 
33
    pthread_spin_unlock(&ref_count->spinlock);
34
    return rc;
35
}
36

37
void ref_count_destroy(ref_count_t *ref_count)
38
{
39
    assert(ref_count->ref_count == 0);
40
    pthread_spin_destroy(&ref_count->spinlock);
41
}
42

43
void thread_using_object(ref_count_t *ref_count)
44
{
45
    ref_count_inc(ref_count);
46
}
47

48
bool thread_using_object_done(ref_count_t *ref_count)
49
{
50
    return ref_count_dec(ref_count);
51
}

Basically, the value of ref_count refers to the number of entities in the system that are referencing (or using) that reference count object.

Interface for Student List


xxxxxxxxxx
36
1
/*
2
 * File Name    : student_list.h
3
 * Description  : Interface for student list
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#ifndef STUDENT_LIST_H
9
#define STUDENT_LIST_H
10

11
#include <stdint.h>
12
#include <pthread.h>
13
#include "ref_count.h"
14
#include "linked_list.h"
15

16
typedef struct student_ 
17
{
18
    uint32_t roll_no;
19
    uint32_t total_marks;
20
    ref_count_t ref_count;
21
    pthread_rwlock_t rw_lock;
22
} student_t;
23

24
typedef struct stud_lst_
25
{
26
    ll_t *lst;
27
    pthread_rwlock_t rw_lock;
28
} stud_lst_t;
29

30
student_t* student_malloc(uint32_t roll_no);
31
void student_destroy(student_t *stud);
32
student_t* student_lst_lookup(stud_lst_t *stud_lst, uint32_t roll_no);
33
bool student_lst_insert(stud_lst_t *stud_lst, student_t *stud);
34
student_t* student_lst_remove(stud_lst_t *stud_lst, uint32_t roll_no);
35

36
#endif /* STUDENT_LIST_H */

Implementation of Student List


xxxxxxxxxx
75
1
/*
2
 * File Name    : student_list.c
3
 * Description  : Implementation of student list
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#include <stdlib.h>
9
#include <assert.h>
10
#include "student_list.h"
11

12
static uint32_t student_object_count = 0;
13

14
student_t* student_malloc(uint32_t roll_no)
15
{
16
    student_t *new_stud = (student_t *)calloc(1, sizeof(student_t));
17
    new_stud->roll_no = roll_no;
18
    new_stud->total_marks = 0;
19
    ref_count_init(&new_stud->ref_count);
20
    pthread_rwlock_init(&new_stud->rw_lock, NULL);
21
    student_object_count++;
22
    return new_stud;
23
}
24

25
void student_destroy(student_t *stud)
26
{
27
    assert(stud->ref_count.ref_count == 0);
28
    /* free stud resources */
29
    ref_count_destroy(&stud->ref_count);
30
    pthread_rwlock_destroy(&stud->rw_lock);
31
    free(stud);
32
    student_object_count--;
33
}
34

35
student_t* student_lst_lookup(stud_lst_t *stud_lst, uint32_t roll_no)
36
{
37
    student_t *stud;
38
    singly_ll_node_t *node1, *node2;
39

40
    ITERATE_LIST_BEGIN2(stud_lst->lst, node1, node2)
41
    {
42
        stud = (student_t *)(node1->data);
43
        if (stud->roll_no == roll_no) return stud;
44

45
    } ITERATE_LIST_END2(stud_lst->lst, node1, node2) ;
46

47
    return NULL;
48
}
49

50
bool student_lst_insert(stud_lst_t *stud_lst, student_t *stud)
51
{
52
    student_t *stud2 = student_lst_lookup(stud_lst, stud->roll_no);
53
    if (stud2) 
54
    {
55
        return false;
56
    }
57

58
    singly_ll_add_node_by_val(stud_lst->lst, stud);
59
    return true;
60
}
61

62
/* detaches an element from the list (it is the responsibility of the caller to free
63
   this element) */
64
student_t* student_lst_remove(stud_lst_t *stud_lst, uint32_t roll_no)
65
{
66
    student_t *stud = student_lst_lookup(stud_lst, roll_no);
67

68
    if (!stud)
69
    {
70
        return NULL;
71
    }
72

73
    singly_ll_delete_node_by_data_ptr (stud_lst->lst, stud);
74
    return stud;
75
}

Interface for Linked List


xxxxxxxxxx
106
1
/*
2
 * File Name    : linked_list.h
3
 * Description  : Interface for linked list
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#ifndef LINKED_LIST_H
9
#define LINKED_LIST_H
10

11
#define GET_HEAD_SINGLY_LL(ll) (ll->head)
12
#define INC_NODE_COUNT_SINGLY_LL(ll) (ll->node_count++)
13
#define DEC_NODE_COUNT_SINGLY_LL(ll) (ll->node_count--)
14
#define GET_NODE_COUNT_SINGLY_LL(ll) (ll->node_count)
15
#define GET_NEXT_NODE_SINGLY_LL(node) (node->next)
16

17
typedef enum {
18
    LL_FALSE,
19
    LL_TRUE
20
} bool_t;
21

22
typedef struct LL_Node
23
{
24
    void *data;
25
    struct LL_Node *next;
26
} singly_ll_node_t;
27

28
typedef struct LL
29
{
30
    unsigned int node_count;
31
    singly_ll_node_t *head;
32
    int (*comparison_fn)(void*, void *);
33
    int (*order_comparison_fn)(void *, void *);
34
} ll_t;
35

36
ll_t* init_singly_ll();
37
singly_ll_node_t* singly_ll_init_node(void* data);
38
int singly_ll_add_node(ll_t *ll, singly_ll_node_t *node);
39
int singly_ll_add_node_by_val(ll_t *ll, void* data);
40
int singly_ll_remove_node(ll_t *ll, singly_ll_node_t *node);
41
unsigned int singly_ll_remove_node_by_value(ll_t *ll, void* data, int size);
42
bool_t is_singly_ll_empty(ll_t *ll);
43
void print_singly_LL(ll_t *ll);
44
void reverse_singly_ll(ll_t *ll);
45
void delete_singly_ll(ll_t *ll);
46
int singly_ll_delete_node(ll_t *ll, singly_ll_node_t *node);
47
unsigned int singly_ll_delete_node_by_value(ll_t *ll, void *data, int size);
48
singly_ll_node_t *singly_ll_get_node_by_data_ptr(ll_t *ll, void *data);
49
void singly_ll_delete_node_by_data_ptr(ll_t *ll, void *data);
50
unsigned int singly_ll_remove_node_by_dataptr(ll_t *ll, void *data);
51
void singly_ll_set_comparison_fn(ll_t *ll, int (*comparison_fn)(void *, void *));
52
void singly_ll_set_order_comparison_fn(ll_t *ll, int (*order_comparison_fn)(void *, void *));
53
void * singly_ll_search_by_key(ll_t *ll, void *key);
54
void copy_singly_ll(ll_t *src, ll_t *dst);
55
ll_t * union_singly_ll(ll_t *list1, ll_t *list2);
56
void singly_ll_delete_data_by_key(ll_t *list, void *key);
57
void singly_ll_add_ordered_data(ll_t *ll, void *data);
58

59
#define ITERATE_LIST_BEGIN(list_ptr, node_ptr)                              \
60
    {                                                                       \
61
    singly_ll_node_t *_node_ptr = NULL;                                     \
62
    node_ptr = GET_HEAD_SINGLY_LL(list_ptr);                                \
63
    for(; node_ptr!= NULL; node_ptr = _node_ptr){                           \
64
        _node_ptr = node_ptr->next; 
65

66
#define ITERATE_LIST_END  }} 
67

68
/* delete safe loop*/
69
#define ITERATE_LIST_BEGIN2(list_ptr, node_ptr, prev)                       \
70
    {                                                                       \
71
    singly_ll_node_t *_node_ptr = NULL; prev = NULL;                        \
72
    node_ptr = GET_HEAD_SINGLY_LL(list_ptr);                                \
73
    for(; node_ptr!= NULL; node_ptr = _node_ptr){                           \
74
        _node_ptr = node_ptr->next; 
75
         
76
#define ITERATE_LIST_CONTINUE2(list_ptr, node_ptr, prev)    \
77
         {if(node_ptr) prev = node_ptr;                     \
78
         continue;}
79
            
80
#define ITERATE_LIST_BREAK2(list_ptr, node_ptr, prev)       \
81
         break
82

83
#define ITERATIVE_LIST_NODE_DELETE2(list_ptr, node_ptr, prev)   \
84
        {if(node_ptr && prev == NULL){                          \
85
            list_ptr->head = node_ptr->next;                    \
86
        }                                                       \
87
        else if(node_ptr && prev){                              \
88
            prev->next = node_ptr->next;                        \
89
        }                                                       \
90
        XFREE(node_ptr);                                        \
91
        list_ptr->node_count--;                                 \
92
        node_ptr = NULL;}
93
            
94
#define ITERATE_LIST_END2(list_ptr, node_ptr, prev)   \
95
             if(node_ptr) prev = node_ptr; }} 
96

97
#define LL_LESS_THAN(listptr, data1ptr, data2ptr)      \
98
    (listptr->order_comparison_fn(data1ptr, data2ptr) == -1)
99

100
#define LL_GREATER_THAN(listptr, data1ptr, data2ptr)   \
101
    (listptr->order_comparison_fn(data1ptr, data2ptr) == 1)
102

103
#define LL_EQUAL(listptr, data1ptr, data2ptr)          \
104
    (listptr->order_comparison_fn(data1ptr, data2ptr) == 0)
105

106
#endif /* LINKED_LIST_H */

Implementation of Linked List


xxxxxxxxxx
426
1
/*
2
 * File Name    : linked_list.c
3
 * Description  : Implementation of linked list
4
 * Author       : Modified by by Kyungjae Lee (Original: Abhishek Sagar)
5
 * Date Created : 01/15/2023
6
 */
7

8
#include <stdio.h>
9
#include <stdlib.h>
10
#include <memory.h>
11
#include "linked_list.h"
12
#include <assert.h>
13

14
ll_t* init_singly_ll()
15
{
16
    return calloc(1, sizeof(ll_t));
17
}
18

19
singly_ll_node_t* singly_ll_init_node(void* data)
20
{
21
    singly_ll_node_t* node = calloc(1,  sizeof(singly_ll_node_t));
22
    node->data = data;
23
    return node;
24
}
25

26
void copy_singly_ll(ll_t *src, ll_t *dst)
27
{    
28
    singly_ll_node_t* node = NULL;
29

30
    if (!src || !dst)
31
        return;
32

33
    delete_singly_ll(dst);
34
    ITERATE_LIST_BEGIN(src, node)
35
    {
36
        if(!node->data) 
37
            continue;
38
        singly_ll_add_node_by_val(dst, node->data);
39
    } ITERATE_LIST_END;
40
    singly_ll_set_comparison_fn(dst, src->comparison_fn);
41
}
42

43

44
ll_t* union_singly_ll(ll_t *list1, ll_t *list2)
45
{    
46
    singly_ll_node_t* node = NULL;
47

48
    if (!list1)
49
        return list2;
50
    if (!list2)
51
        return list1;
52

53
    ll_t *res = init_singly_ll();
54
    singly_ll_set_comparison_fn(res, list1->comparison_fn ? list1->comparison_fn : list2->comparison_fn);
55

56
    ITERATE_LIST_BEGIN(list1, node)
57
    {
58
        singly_ll_add_node_by_val(res, node->data);
59
    } ITERATE_LIST_END;
60
    
61
    ITERATE_LIST_BEGIN(list2, node)
62
    {
63
        singly_ll_add_node_by_val(res, node->data);
64
    } ITERATE_LIST_END;
65
    return res;
66
}
67

68
int singly_ll_add_node(ll_t* ll, singly_ll_node_t *node)
69
{
70
    if (!ll) return -1;
71
    if (!node) return -1;
72
    if (!GET_HEAD_SINGLY_LL(ll))
73
    {
74
        GET_HEAD_SINGLY_LL(ll) = node;
75
        INC_NODE_COUNT_SINGLY_LL(ll);
76
        return 0;
77
    }
78

79
    node->next = GET_HEAD_SINGLY_LL(ll);
80
    GET_HEAD_SINGLY_LL(ll) = node;
81
    INC_NODE_COUNT_SINGLY_LL(ll);
82
    return 0;
83
}
84

85
/* Duplicates will not be added*/
86
int singly_ll_add_node_by_val(ll_t *ll, void *data)
87
{
88
    if (singly_ll_get_node_by_data_ptr(ll, data))
89
        return -1;
90
    singly_ll_node_t* node = singly_ll_init_node(data);
91
    return singly_ll_add_node(ll, node);
92
}
93

94
int singly_ll_delete_node(ll_t *ll, singly_ll_node_t *node)
95
{
96
    if (!ll) return -1;
97
    if (!GET_HEAD_SINGLY_LL(ll) || !node) return 0;
98
    singly_ll_node_t *trav = NULL;
99
    /*if node is not the last node*/
100
    if (node->next)
101
    {
102
        singly_ll_node_t *temp = NULL;
103
        node->data = node->next->data;
104
        temp = node->next;
105
        node->next = node->next->next;
106
        free(temp);
107
        DEC_NODE_COUNT_SINGLY_LL(ll);
108
        return 0;
109
    }
110

111
    /* if node is the only node in LL*/
112
    if (ll->node_count == 1 && GET_HEAD_SINGLY_LL(ll) == node)
113
    {
114
        free(node);
115
        GET_HEAD_SINGLY_LL(ll) = NULL;
116
        DEC_NODE_COUNT_SINGLY_LL(ll);
117
        return 0;
118
    }
119

120
    /*if node is the last node of the LL*/
121
    trav = GET_HEAD_SINGLY_LL(ll);
122
    while (trav->next != node)
123
    {
124
        trav = trav->next;
125
        continue;
126
    }
127
    
128
    trav->next = NULL;
129
    free(node);
130
    DEC_NODE_COUNT_SINGLY_LL(ll);
131
    return 0;
132
}
133

134
int singly_ll_remove_node(ll_t *ll, singly_ll_node_t *node)
135
{
136
    if (!ll || !GET_HEAD_SINGLY_LL(ll)) return 0;
137
    if (!node)
138
    {
139
        printf("%s(%d) : Error : node is NULL\n", __FUNCTION__, __LINE__);
140
        return -1;      
141
    }
142
    int i = 0;
143
    singly_ll_node_t *head = GET_HEAD_SINGLY_LL(ll), *prev = NULL;
144
    
145
    if (head == node)
146
    {
147
        GET_HEAD_SINGLY_LL(ll) = GET_NEXT_NODE_SINGLY_LL(head);
148
        DEC_NODE_COUNT_SINGLY_LL(ll);
149
        node->next = NULL;
150
        return 0;
151
    }
152

153
    prev = head;
154
    head = GET_NEXT_NODE_SINGLY_LL(head);
155
    for (i =1; i < GET_NODE_COUNT_SINGLY_LL(ll); i++)
156
    {
157
        if (head != node)
158
        {
159
            prev = head;
160
            head = GET_NEXT_NODE_SINGLY_LL(head);
161
            continue;
162
        }
163
        
164
        GET_NEXT_NODE_SINGLY_LL(prev) = GET_NEXT_NODE_SINGLY_LL(head);
165
        GET_NEXT_NODE_SINGLY_LL(head) = NULL;
166
        DEC_NODE_COUNT_SINGLY_LL(ll);
167
        return 0;   
168
    }   
169
    printf("%s(%d) : Error : node not found\n", __FUNCTION__, __LINE__);
170
    return -1;
171
}
172

173
unsigned int singly_ll_delete_node_by_value(ll_t *ll, void *data, int size)
174
{
175
    if (!ll || !GET_HEAD_SINGLY_LL(ll)) return 0;
176
    unsigned int curren_node_count = GET_NODE_COUNT_SINGLY_LL(ll);
177
    singly_ll_node_t* trav = GET_HEAD_SINGLY_LL(ll);
178
    while (trav != NULL)
179
    {
180
        if (memcmp(trav->data, data, size) == 0)
181
        {
182
            singly_ll_delete_node(ll, trav);
183
            return curren_node_count - GET_NODE_COUNT_SINGLY_LL(ll);
184
        }
185
        trav = trav->next;
186
    }
187
    return curren_node_count - GET_NODE_COUNT_SINGLY_LL(ll);
188
}
189

190
unsigned int singly_ll_remove_node_by_value(ll_t *ll, void *data, int size)
191
{
192
    if (!ll || !GET_HEAD_SINGLY_LL(ll)) return 0;
193
    unsigned int curren_node_count = GET_NODE_COUNT_SINGLY_LL(ll);
194
    singly_ll_node_t* trav = GET_HEAD_SINGLY_LL(ll);
195
    while (trav != NULL)
196
    {
197
        if (memcmp(trav->data, data, size) == 0)
198
        {
199
            singly_ll_remove_node(ll, trav);
200
            return curren_node_count - GET_NODE_COUNT_SINGLY_LL(ll);
201
        }
202
        trav = trav->next;
203
    }
204
    return curren_node_count - GET_NODE_COUNT_SINGLY_LL(ll);
205
}
206

207
unsigned int singly_ll_remove_node_by_dataptr(ll_t *ll, void *data)
208
{
209
    if (!ll || !GET_HEAD_SINGLY_LL(ll)) return 0;
210
    unsigned int curren_node_count = GET_NODE_COUNT_SINGLY_LL(ll);
211
    singly_ll_node_t* trav = GET_HEAD_SINGLY_LL(ll);
212
    while (trav != NULL)
213
    {
214
        if (trav->data == data)
215
        {
216
            singly_ll_remove_node(ll, trav);
217
            return curren_node_count - GET_NODE_COUNT_SINGLY_LL(ll);
218
        }
219
        trav = trav->next;
220
    }
221
    return curren_node_count - GET_NODE_COUNT_SINGLY_LL(ll);
222
}
223

224
singly_ll_node_t* singly_ll_get_node_by_data_ptr(ll_t *ll, void *data)
225
{
226
    if (!ll || !GET_HEAD_SINGLY_LL(ll)) return NULL;
227
    int i = 0;
228
    singly_ll_node_t *head = GET_HEAD_SINGLY_LL(ll);
229

230
    for ( ; i < GET_NODE_COUNT_SINGLY_LL(ll); i++)
231
    {
232
        if (head->data == data)
233
            return head;
234
        head = GET_NEXT_NODE_SINGLY_LL(head);           
235
    }
236
    return NULL;
237
}
238

239
void print_singly_LL(ll_t *ll)
240
{
241
    if (!ll)
242
    {
243
        printf("Invalid Linked List\n"); 
244
        return;
245
    }
246
    if (is_singly_ll_empty(ll))
247
    {
248
        printf("Empty Linked List\n");
249
        return;
250
    }
251
    
252
    singly_ll_node_t* trav = GET_HEAD_SINGLY_LL(ll);
253
    unsigned int i = 0;
254
    printf("node count = %d\n", GET_NODE_COUNT_SINGLY_LL(ll));
255
    while (trav)
256
    {
257
        printf("%d. Data = %p, node = %p\n", i, trav->data, trav);
258
        i++;
259
        trav = trav->next;
260
    }
261
}
262

263
bool_t is_singly_ll_empty(ll_t *ll)
264
{
265
    if (!ll) assert(0);
266
    if (ll->node_count == 0)
267
        return LL_TRUE;
268
    return LL_FALSE;
269
}
270

271
void reverse_singly_ll(ll_t *ll)
272
{
273
   if (!ll) assert(0) ;
274
   if (is_singly_ll_empty(ll)) return;
275
   if (GET_NODE_COUNT_SINGLY_LL(ll) == 1) return;
276
   singly_ll_node_t *p1 = GET_HEAD_SINGLY_LL(ll), *p2 = ll->head->next, *p3 = NULL;
277
   p1->next = NULL;
278
   do {
279
        p3 = p2->next;
280
        p2->next = p1;
281
        p1 = p2;
282
        p2 = p3;
283
   } while(p3);
284
   ll->head = p1;
285
   return;
286
}
287

288
void delete_singly_ll(ll_t *ll)
289
{
290
    if (!ll) return;
291

292
    if(is_singly_ll_empty(ll))
293
    {
294
        return;
295
    }
296

297
    singly_ll_node_t *head = GET_HEAD_SINGLY_LL(ll), *next = GET_NEXT_NODE_SINGLY_LL(head);
298

299
    do {
300
        free(head);
301
        head = next;
302
        if(next)
303
            next = GET_NEXT_NODE_SINGLY_LL(next);
304
    } while(head);
305

306
    ll->node_count = 0;
307
    ll->head = NULL;
308
}
309

310
void singly_ll_set_comparison_fn(ll_t *ll, int (*comparison_fn)(void *, void *))
311
{
312
    if (!ll) assert(0);
313
    ll->comparison_fn = comparison_fn;
314
}
315

316
void singly_ll_set_order_comparison_fn(ll_t *ll, int (*order_comparison_fn)(void *, void *))
317
{
318
    if (!ll) assert(0);
319
    ll->order_comparison_fn = order_comparison_fn;
320
}
321

322
void* singly_ll_search_by_key(ll_t *ll, void *key)
323
{
324
    assert(ll);
325
    if (!key)
326
        return NULL;
327

328
    singly_ll_node_t *list_node = NULL;
329
    ITERATE_LIST_BEGIN(ll, list_node)
330
    {
331
        if (ll->comparison_fn(list_node->data, key))
332
            return list_node->data;
333
    } ITERATE_LIST_END;
334
    return NULL;
335
}
336

337
void singly_ll_delete_node_by_data_ptr(ll_t *ll, void *data)
338
{
339
    if (!data)
340
        return;
341

342
    singly_ll_node_t *list_node = singly_ll_get_node_by_data_ptr(ll, data);
343

344
    if (!list_node) 
345
        return;
346
    
347
    singly_ll_remove_node(ll, list_node);
348
    free(list_node);
349
    list_node = NULL;
350
}
351

352
#if 0
353
void singly_ll_delete_data_by_key(ll_t *list, void *key)
354
{
355
    singly_ll_node_t *list_node = NULL;
356
    singly_ll_node_t *list_node_prev = NULL;
357
    void *data = NULL;
358

359
    ITERATE_LIST_BEGIN(list, list_node)
360
    {
361
        data = list_node->data;
362
        if(list->comparison_fn(data, key) == 0)
363
        {
364
            list_node_prev = list_node;        
365
            continue;
366
        }        
367
    } ITERATE_LIST_END;
368
}
369
#endif
370

371
void singly_ll_add_ordered_data(ll_t *ll, void *data)
372
{
373
    singly_ll_node_t *list_node_prev = NULL,*list_node_next = NULL;
374

375
    if (is_singly_ll_empty(ll))
376
    {
377
        singly_ll_add_node_by_val(ll, data);
378
        return;
379
    }
380

381
    /* Only one node*/
382
    if (GET_NODE_COUNT_SINGLY_LL(ll) == 1)
383
    {
384
        if(ll->comparison_fn(ll->head->data, data) == -1)
385
        {
386
            singly_ll_add_node_by_val(ll, data);
387
        }
388
        else
389
        {
390
            singly_ll_node_t *new_node = singly_ll_init_node(data);
391
            ll->head->next = new_node;
392
            INC_NODE_COUNT_SINGLY_LL(ll);
393
        }
394
        return;
395
    }
396
    
397
    if (ll->comparison_fn(data, ll->head->data) == -1)
398
    {
399
        singly_ll_node_t *new_node = singly_ll_init_node(data);
400
        new_node->next = GET_HEAD_SINGLY_LL(ll);
401
        ll->head = new_node;
402
        INC_NODE_COUNT_SINGLY_LL(ll);
403
        return;
404
    }
405
    
406
    ITERATE_LIST_BEGIN(ll, list_node_next)
407
    {
408
        if(ll->comparison_fn(data, list_node_next->data) != -1)
409
        {
410
            list_node_prev = list_node_next;
411
            continue;
412
        }
413

414
        singly_ll_node_t *new_node = singly_ll_init_node(data);
415
        new_node->next = list_node_next;
416
        list_node_prev->next = new_node;
417
        INC_NODE_COUNT_SINGLY_LL(ll);
418
        return;
419

420
    } ITERATE_LIST_END;
421

422
    /* Add in the end*/
423
    singly_ll_node_t *new_node = singly_ll_init_node(data);
424
    list_node_prev->next = new_node;
425
    INC_NODE_COUNT_SINGLY_LL(ll);
426
}

References

Sagar, A. (2022). Part A - Multithreading & Thread Synchronization - Pthreads [Video file]. Retrieved from https://www.udemy.com/course/multithreading_parta/