A lockfree example

[heatblazer]

Hello, I am experimenting with a lock free simple list for inserting data:

#include<stdio.h>#include<stdlib.h>#include<pthread.h>
typedefstruct_n{intdata;struct_n*next;}node;
#defineCAS(ptr,oldp,newp)\__sync_bool_compare_and_swap(ptr,oldp,newp)
staticnode*p_head=0;


static
void atomic_push(intd)
{
node*pnode=(node*)malloc(sizeof(node));
pnode->data=d;
do{
pnode->next=p_head;
}while(!CAS(&p_head,pnode->next,pnode));}

void *doWork(void*d){atomic_push(*((int*)d));}

int main(int argc,char*argv[]){
pthread_ttlist[100];inti=0;for(i=0;i<100;i++){int*ip=malloc(sizeof(int));*ip=i;pthread_create(&tlist[i],NULL,doWork,ip);}
node*pIt=p_head;while(pIt){printf("%d\n",pIt->data);pIt=pIt->next;}
return0;}

I am wondering just if I have to add something better or do I have a pitfall here?

[algorism]

It seems to work. The main thing you're missing is that you're not joining your threads in the main thread.

#define _BSD_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>

#define SIZE 100
#define MINTIME 1000
#define RNDTIME 1000
#define CAS(ptr, oldp, newp) __sync_bool_compare_and_swap((ptr),(oldp),(newp))

typedef struct _n { 
    int data;
    struct _n *next;
} node;

node *p_head = NULL;

void atomic_push(int d) {
    node *pnode = malloc(sizeof(*pnode));
    pnode->data = d;
    do {
        pnode->next = p_head;
    } while (!CAS(&p_head, pnode->next, pnode));
}

void *doWork(void *d) {
    usleep(rand() % RNDTIME + MINTIME);
    atomic_push(*(int*)d);
    return NULL;
}

int main() {
    srand(time(NULL));

    pthread_t tlist[SIZE];
    int n[SIZE];
    int i = 0;

    for (i = 0; i < SIZE; i++) {
        n[i] = i;
        pthread_create(&tlist[i], NULL, doWork, &n[i]);
    }

    // Need to join with the threads or the main thread will
    // continue before the others have finished.
    for (i = 0; i < SIZE; i++)
        pthread_join(tlist[i], NULL);

    // Reuse n to check that all numbers are in the list once
    memset(n, 0, SIZE * sizeof*n);

    node *pIt = p_head;
    while (pIt) { 
        printf("%d ", pIt->data);
        n[pIt->data]++;
        pIt = pIt->next;
    }
    putchar('\n');

    for (i = 0; i < SIZE; i++)
        if (n[i] != 1)
            printf("%d in list %d times\n", i, n[i]);

    return 0;
}

BTW. remember to paste as plain text to avoid the unreadable code in your post.

[Codeplug]

That get's the job done, but the benefit is somewhat lost by calling malloc

Next is a memory pool, managed by a lockfree data-structure, so that other lock-free data-structures can pull memory from the pool quickly.

gg