Thread Safe Linked List

[seal308]

Hello
My teacher gave me sample code of a linked list thats not thread safe and told me to use pthreads mutex to make it thread safe
Sample code:

// routine to return the data from the node with the given key.
long listSearch(listNodePtr listPtr, long key) {
	listNodePtr	currPtr;
	long		result;


	currPtr=listPtr;
	while (currPtr!=NULL) {
		if (currPtr->key==key) {       	// As you convert this code for threads,
			result=currPtr->data;	// think about why I didn't just code
			return(result);		// 'return(curr->data)' in this if statement.
		} else {
			currPtr=currPtr->next;
		}
	}
	return (-1); 	// indicates "not found"
} // end listSearch

The other given functions are insert and delete.
I want to understand his comment asking why he didn't just return curr--> data directly.
im assuming the issue is that if another thread inserts/deletes that will affect search.
But not sure how that variable result helps.

[seal308]

Nvm i think i figured it out.
While doing the return the value can change.

[Hodor]

I don't know why you wouldn't just return currPtr->data (apart from it being ugly to return in the middle of a function like that but your teacher returns in the middle of the function anyway). Assigning currPtr->data to result and then returning result is no different, in your example, to simply having return currPtr->data and your compiler probably optimises the two statements into one anyway!

[Salem]

Well both answers are wrong so far.
Put your mutex in the code.

[Hodor]

Well both answers are wrong so far.
Put your mutex in the code.

My answer is not incorrect for the case where mutexes are not involved (which is the case for the given code). Of course if you're using mutexes, which the code is not at this point, then where would you free the mutex if you've already returned: you can't which is what the teacher is alluding to, but to ask why he wrote it that way for the current code is silly. My point is only that the teacher is not thinking very straight asking a question about code that is not even written yet and/or falling into the trap of writing for a specification that did not exist when the code was written.

Edit: I guess a correct answer could be "My teach wrote it like this to make it easier for me to surround it with a mutex so that I don't have to think too much, or in case I haven't learned how to use vi/vim efficiently yet"

[Salem]

Simply saying "just return currPtr->data;" ignores the crux of the problem which centres on why the assignment is necessary when mutexes become involved.

If you put the mutexes in (as per the original question), then the necessity of the assignment becomes apparent.

[Hodor]

Simply saying "just return currPtr->data;" ignores the crux of the problem which centres on why the assignment is necessary when mutexes become involved.

If you put the mutexes in (as per the original question), then the necessity of the assignment becomes apparent.

Yes, I understand that. But the original code doesn't need the assignment (nor does it need mutexes) so why do it that way? I understand what you're saying but I think the question the teacher has asked is a bit dumb and contrived, that's all

[seal308]

Simply saying "just return currPtr->data;" ignores the crux of the problem which centres on why the assignment is necessary when mutexes become involved.

If you put the mutexes in (as per the original question), then the necessity of the assignment becomes apparent.

Ok i tried putting in mutexs for the code but I don't think i get it still.
I put a mutex called lock in the LL struct.

long listSearch(listNodePtr listPtr, long key) {
    listNodePtr    currPtr;
    long        result;

    currPtr=listPtr;
    while (currPtr!=NULL) {
        pthread_mutex_lock(&currPtr->lock);    
        if (currPtr->key==key) {           // As you convert this code for threads,
            result=currPtr->data;    // think about why I didn't just code
            return(result);        // 'return(curr->data)' in this if statement.
        } else {
            currPtr=currPtr->next;
        }
        pthread_mutex_unlock(&currPtr->lock);
    }
    return (-1);     // indicates "not found"
} // end listSearch

[stahta01]

Please tell me that you understand what an return does in C/C++ ?
If not, please review what it does.

Edit: I have not used pthread locking before, I am guessing that returning will result in lock not being removed.

Tim S.

[Salem]

> I put a mutex called lock in the LL struct.
Yes, and you succeeded in returing without unlocking.

You also lock and unlock inside the loop, which means the list is free to change in the middle of your traversal.

Compare with

long listSearch(listNodePtr listPtr, long key) {
    listNodePtr    currPtr;
    long        result = -1;  // if nothing is found
 
    currPtr=listPtr;
    pthread_mutex_lock(&currPtr->lock);    
    while (currPtr!=NULL) {
        if (currPtr->key==key) {
            result=currPtr->data;  // this is why you assign.
            break;
        } else {
            currPtr=currPtr->next;
        }
    }
    pthread_mutex_unlock(&currPtr->lock);
    return result;
} // end listSearch

[rcgldr]

None of the answers posted so far are thread safe. The passed parameter needs to be a pointer to pointer to node, a pointer equal to the (fixed) address of the actual list pointer, along with a mutex associated with the list. The mutex is locked first, then the list is scanned or updated, then the mutex is unlocked.