Thread: Thread Safe Linked List

  1. #1
    Registered User
    Join Date
    Jan 2016
    Posts
    45

    Thread Safe Linked List

    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:

    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.

  2. #2
    Registered User
    Join Date
    Jan 2016
    Posts
    45
    Nvm i think i figured it out.
    While doing the return the value can change.

  3. #3
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    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!

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,815
    Well both answers are wrong so far.
    Put your mutex in the code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by Salem View Post
    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"
    Last edited by Hodor; 02-10-2018 at 03:15 AM.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,815
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by Salem View Post
    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

  8. #8
    Registered User
    Join Date
    Jan 2016
    Posts
    45
    Quote Originally Posted by Salem View Post
    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.

    Code:
    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

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,079
    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.
    Last edited by stahta01; 02-10-2018 at 11:50 AM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,815
    > 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
    Code:
    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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. High performance thread safe list implementation?
    By eisteetuete in forum C Programming
    Replies: 2
    Last Post: 08-23-2017, 04:29 PM
  2. Is this thread safe?
    By theoobe in forum C# Programming
    Replies: 2
    Last Post: 09-22-2012, 02:27 AM
  3. Thread safe double linked list
    By ShwangShwing in forum C Programming
    Replies: 7
    Last Post: 06-02-2009, 10:55 AM
  4. thread safe in my code to manipulate List?
    By George2 in forum C# Programming
    Replies: 8
    Last Post: 05-01-2008, 06:57 AM
  5. Is this safe - linked list with multiple types
    By pronecracker in forum C Programming
    Replies: 18
    Last Post: 05-30-2007, 01:08 PM

Tags for this Thread