In the following code, I tried handling various linked list operations using multiple threads. Multiple linked lists can be supported and all functions are generic except I kept a few printf statements to debug the code.
typedef void (*gen_fun_t)(void *);
ll_t thread[2];
int ret;
#define RWLOCK(lt, lk) (ret=(lt) == l_read)? pthread_rwlock_rdlock(&(lk)): pthread_rwlock_wrlock(&(lk))
#define RWUNLOCK(lk) pthread_rwlock_unlock(&(lk));
typedef enum locktype locktype_t;
enum locktype
{
l_read,
l_write
};
struct node
{
void *val;
struct node *next;
pthread_rwlock_t m;
};
struct ll
{
int len;
struct node *head;
pthread_rwlock_t m;
gen_fun_t val_teardown;
gen_fun_t val_printer;
};
typedef struct ll* ll_t;
typedef struct node * ll_node;
ll_t create( gen_fun_t val_teardown)
{
ll_t list=(ll_t)malloc(sizeof(struct ll));
list->head=NULL;
list->len=0;
list->val_teardown = val_teardown;
pthread_rwlock_init(&list->m, NULL);
return list;
}
ll_node new_node(void *val)
{
ll_node node= (ll_node)malloc(sizeof(struct node));
node->val=val;
node->next=NULL;
pthread_rwlock_init(&node->m, NULL);
return node;
}
int remove_mid(ll_t list, int n)
{
printf("Before deletion \n");
print(list);
ll_node temp;
if(n==0)
{
temp=list->head;
list->head=temp->next;
printf("%d \n", *(int *)(list->head)->val);
}
else
{
ll_node it;
it=list->head;
for(;n>1;n--)
it=it->next;
printf("%d \n", *(int *)(it->next)->val);
temp=it->next;
it->next=it->next==NULL? NULL: temp->next;
printf("%d \n", *(int *)(it->next)->val);
}
(list->len)--;
list->val_teardown(temp->val);
free(temp);
return list->len;
}
int insert_mid(ll_t list, void *val, int n)
{
ll_node node= new_node(val);
if(n==0)
{
node->next=list->head;
list->head=node;
}
else
{
ll_node it;
it=list->head;
for(;n>1;n--)
it=it->next;
node->next=it->next;
it->next=node;
printf("After insertion \n");
print(list);
printf("\n");
}
(list->len)++;
return list->len;
}
void *thread_operation(void * arg)
{
long id= (long) arg;
if(id==0)
{
RWLOCK(l_write, list[0]->m);
//RWLOCK(l_read, list[0]->m);
printf("The status of lock operation is %d \n", ret);
printf("\nThread: %ld \n", id);
int v=rand()%100;
int pos=rand()%list[0]->len;
printf("The position inserted is %d \n",pos+1);
pos=insert_mid(list[0], &v, pos);
//RWUNLOCK(list[0]->m);
RWUNLOCK(list[0]->m);
}
else
{
RWLOCK(l_write, list[0]->m);
//RWLOCK(l_read, list[0]->m);
printf("The status of lock operation is %d \n", ret);
printf("\nThread: %ld \n", id);
int pos=rand()%list[0]->len;
printf("The position to be deleted is %d \n", pos+1);
pos=remove_mid(list[0], pos);
print(list[0]);
//RWUNLOCK(list[0]->m);
RWUNLOCK(list[0]->m);
}
}
int main()
{
int thread_count=2;
long thread;
srand(time(0));
list[0]= create(int_tear);
list[0]->val_printer = int_printer;
list[1]=create(float_tear);
list[1]->val_printer= float_printer;
pthread_t *thread_handles;
int l, a=2, b=8, c=15;
l=insert_first(list[0], &a);
l=insert_end(list[0], &b);
l=insert_mid(list[0], &c, rand()%l);
double start, finish, elapsed;
start=clock();
thread_handles= (pthread_t *) malloc(thread_count*sizeof(pthread_t));
for(thread=0;thread<thread_count;thread++)
pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);
for(thread=0;thread<thread_count;thread++)
pthread_join(thread_handles[thread], NULL);
finish=clock();
elapsed =(finish-start)/CLOCKS_PER_SEC;
return 0;
}
It gives output as
Thread: 0
The position to be inserted is 3
After insertion
ll: 2 15 79 8
Thread: 1
The position to be deleted is 1
Before deletion
ll: 2 15 -2087655584 8
ll: 15 -2087655584 8
Clearly, 79 was inserted in position 2 by the insert_mid function but why does it change to -2087655584? What is the solution?
If any information is required, please inform.
Short summary: You store the address of a local variable in a list node and this variable goes out of scope, so the address becomes invalid.
Your function new_node(void *val) gets an address as an argument and stores this address in the node structure as node->val.
In your main function you first create 3 nodes with the addresses of local variables.
int l, a=2, b=8, c=15;
l=insert_first(list[0], &a);
l=insert_end(list[0], &b);
l=insert_mid(list[0], &c, rand()%l);
These variables are valid until the end of main, so there is no problem here.
In this loop
for(thread=0;thread<thread_count;thread++)
pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);
you create threads running thread_operation and pass the loop counter, casted to a void* as an argument.
In thread_operation when called with argument value 0 you add a node using the address of a local variable v
void *thread_operation(void * arg)
{
long id= (long) arg;
if(id==0)
{
/* ... */
int v=rand()%100;
int pos=rand()%list[0]->len;
/* ... */
pos=insert_mid(list[0], &v, pos); /* &v is the address of a local variable */
/* ... */
}
else
{
/* ... */
}
}
/* ... */
int insert_mid(ll_t list, void *val, int n)
{
ll_node node= new_node(val); /* The address is passed to the new node. */
/* ... */
}
When thread_operation leaves the body of
if(id==0)
{
/* ... */
}
the variable goes out of scope and becomes invalid. (If you compile your program without optimization it probably keeps its value until the function returns, but this is not guaranteed.)
When thread_operation returns, the stack area where this variable was located is disposed and will be used for other function calls later.
When you print the contents of the list, the node inserted by the thread with ID 0 points to some address on the stack that once held the variable v and might be in use or might have been used for something else afterwards. That's why the value gets changed. This is undefined behavior.
To fix this problem you can either change your node structure to store the value of the variable as an int instead of the address of the variable as a void * or you have to allocate memory and create a copy of the data like this
ll_node new_node(void *val, size_t size)
{
ll_node node= (ll_node)malloc(sizeof(struct node));
/* TODO check that malloc did not return NULL */
node->val = malloc(size);
/* TODO check that malloc did not return NULL */
memcpy(node->val, val, size);
node->next=NULL;
pthread_rwlock_init(&node->m, NULL);
return node;
}
Additional possible problem:
You create a lock object in every list node. If you want to use this to to protect access to the data in the node, the corresponding thread must get (at least) a read lock for the list to prevent other threads from deleting the node.