Deleting Linked List Elements

I’m curious what I have done wrong, since my void *DeleteDoneNodes(node * n) doesn’t do anything, no error but no output neighter, so could anyone help me finding the root of my problem thank you.

Scenario: cmd line ./s m n m number of nodes in list, n number of workingThreads should delete each nodes with node->value == 1, but it doesn’t do anything…

code:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <math.h>
#include <semaphore.h>

#define finishedNodes 5
#define workersLimitNr 3

int workingThreads = 0;
sem_t sem;

struct dataBlock{
    struct node *root;
    int listSize;
    int forIndex;
};

struct node { // std linked list node
    int value;
    int worker;
    struct node *next;
};

int slots = 0; // only 3 threads are allowed to access the list
int availableCheck(){   // check if thread can acces the list
    if(slots < 3) 
        return 0;
    else 
        return -1;
}



pthread_mutex_t mutp = PTHREAD_MUTEX_INITIALIZER;   // mutex
pthread_cond_t  condvar = PTHREAD_COND_INITIALIZER;   //condvar

void *deleteDoneNodes(struct node *n){ // T H I S  I S  T H E  F U N C
        struct node *root = n;
        struct node *it;
        it = root;
        do{
            if(it->value == 1){
                struct node *tmp;
                printf("DELETING: %d > %dn", it->value, it->worker );
                root = root->next;
                tmp = it;
                it = it->next;
                free(tmp);
            }
            else
                it = it->next;
    }while(it !=  NULL);

    return NULL; 
}

void * worker( void *data ){
    struct dataBlock *inData = (struct dataBlock *) data;
    struct node *root = inData->root;
    int forIndex = inData ->forIndex;
    free(data);
    printf( "*    Thread id: %lu    forID:  %d  workerNode: n",pthread_self(),forIndex); 

    pthread_mutex_lock( &mutp );
    if(availableCheck() < 0){
        printf( " ^^^ List not available yet... n" ); 
        pthread_cond_wait( &condvar, &mutp ); 
    } 
    struct node *it = root;

    printf( " _forID_ %dn |", forIndex );  
    do{
        if(forIndex == it->worker){
            printf("valid for sqrt  forIndex %d == it->worker %dn",forIndex, it->worker );
            if(it->value > 2){
                while(it->value != 1)
                it->value = sqrt(it->value);
                // it->value = it->value - 1;
            }
        }
        it = it->next;
    }while(it !=  NULL);

    pthread_cond_signal( &condvar ); // 
    pthread_mutex_unlock( &mutp ); 
    return NULL;
}

int main( int argc, char *argv[] ){
    if ( argc != 3 ){
        printf( "Programm must be called with n NR of elements and NR of workers! n " );
        exit( 1 );
    }

    int i;
    struct node *root;
    struct node *iterator;  

//prepare list for task
    int listSize = atoi(argv[1]);
    int nrWorkers = atoi(argv[2]);
    root = malloc(sizeof( struct node) );

    root->value = rand() % 100;
    root->worker = 0;
    iterator = root;

    for( i=1; i<listSize; i++ ){
        iterator->next = malloc(sizeof(struct node));
        iterator = iterator->next;
        iterator->value = rand() % 100;
        iterator->worker = i % nrWorkers;
        printf("node #%d worker: %d  value: %dn", i, iterator->worker,iterator->value);
    }
    iterator->next = NULL;
    printf("? List got populatedn");
// init semaphore > keeps max 3 threads working over the list

    if( sem_init(&sem,0,3) < 0){
      perror("semaphore initilization");
      exit(0);
    }

// Create all threads to parse the link list
    int ret;    
    pthread_mutex_init(&mutp,NULL);

    pthread_t w_thread;
    pthread_t* w_threads = malloc(nrWorkers * sizeof(w_thread));

    for( i=0; i < nrWorkers; i++ ){         
        struct dataBlock *data = malloc(sizeof(struct dataBlock));
        data->root = root;
        data->listSize = listSize;
        data->forIndex = i;
        ret = pthread_create ( &w_threads[i], NULL, worker, (void *) data );
        if( ret ) {
            perror("Thread creation fail");
            exit(2);    
        }   
    } 

    deleteDoneNodes( root );
    // printf( ">>>> %dn", root->value );
    for ( i = 0; i < nrWorkers; i++ ){
        pthread_join(w_threads[i],NULL);
    }
    // for ( i = 0; i < nrWorkers; i++){
    //  free(w_threads);
    // }

    iterator = root;
    for ( i = 0; i < listSize; i++){
        printf("val: %d  worker: %d _  ", iterator->value, iterator->worker);
        iterator = iterator->next;
    }

    free(root);
    free(iterator);
    return 0;
}

PS: It compiles / works error /warningless – tested with valgrind also.

Answer

Here’s an alternative version

void *deleteDoneNodes(struct node *n){
    struct node *root = n;
    struct node *it = root;
    struct node *prev = NULL;
    do{
        if(it->value == 1){
            struct node *next = it->next;
            if (prev != NULL) {
                prev->next = next;
            }
            if (it == root) {
                root = next;
            }
            free(it);
            it = next;
        }
        else {
            prev = it;
            it = it->next;
        }
    }while(it !=  NULL);

    return root;
}

The main changes are:

• Handling removal of an item from the middle of the list. The previous item needs to change its next pointer. Without this, it’ll keep pointing to freed memory.
• Logic for updating root. This only needs to happen if we free root
• Communicating possible change in root. If we remove the root (aka head) item from the list, this needs to be communicated to the caller. I’ve done this by returning the (possibly updated) value of root instead of NULL