1

So I've tried one method that locks each node as it looks at it, but this requires ALOT of locking and unlocking... which of course requires quite a bit of overhead. I was wondering if anyone knew of a more efficient algorithm. Here is my first attempt:

typedef struct _treenode{ struct _treenode *leftNode; struct _treenode *rightNode; int32_t data; pthread_mutex_t mutex; }TreeNode; pthread_mutex_t _initMutex = PTHREAD_MUTEX_INITIALIZER; int32_t insertNode(TreeNode **_trunk, int32_t data){ TreeNode **current; pthread_mutex_t *parentMutex = NULL, *currentMutex = &_initMutex; if(_trunk != NULL){ current = _trunk; while(*current != NULL){ pthread_mutex_lock(&(*current)->mutex); currentMutex = &(*current)->mutex; if((*current)->data < data){ if(parentMutex != NULL) pthread_mutex_unlock(parentMutex); pthreadMutex = currentMutex; current = &(*current)->rightNode; }else if((*current)->data > data){ if(parentMutex != NULL) pthread_mutex_unlock(parentMutex); parentMutex = currentMutex; current = &(*current)->leftNode; }else{ pthread_mutex_unlock(currentMutex); if(parentMutex != NULL) pthread_mutex_unlock(parentMutex); return 0; } } *current = malloc(sizeof(TreeNode)); pthread_mutex_init(&(*current)->mutex, NULL); pthread_mutex_lock(&(*current)->mutex); (*current)->leftNode = NULL; (*current)->rightNode = NULL; (*current)->data = data; pthread_mutex_unlock(&(*current)->mutex); pthread_mutex_unlock(currentMutex); }else{ return 1; } return 0; } int main(){ int i; TreeNode *trunk = NULL; for(i=0; i<1000000; i++){ insertNode(&trunk, rand() % 50000); } }
Improve this question
2
  • maybe having a rwlock for the tree itself, not the nodes. so if you just need to read, you can have multiple threads doing so "at the same time". Commented Jun 28, 2011 at 12:49
  • @hexa - Yea I've tried this, and it does seem like a strong option. Commented Jun 28, 2011 at 12:52

4 Answers 4

Reset to default
1

You don't need to lock every node you visit. You can do something like this. Lock a node when you're about to do an insertion. Do your insertion and unlock. If another thread happens to need to insert at the same point it and the node is locked it should wait before traversing down any further. Once the node is unlocked it can then continue traversing the updated part of the tree.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Would I not need to lock while looking at a node? What if a thread is inserting while another looks? Would this not cause issues?
It's okay to look as long as you don't go deeper than where another thread is inserting. This works out because insertions always happen at the leaves.
1

Another straightforward way is to have 1 lock for the complete tree.

You have a more serialized access to the tree, but you only have one mutex and you lock only once. If the serialization is an issue, you use a read/write lock. so at least reading can be done in parallel.

Improve this answer

Comments

1

Use a read-write lock. Locking on individual nodes will become exceptionally difficult if you later decide to switch your tree implementation. Here's a little demo code using pthreads:

typedef struct { pthread_rwlock_t rwlock; TreeNode *root_node; } Tree; void Tree_init(Tree *tree) { pthread_rwlock_init(&tree->rwlock, NULL); tree->root_node = NULL; } int32_t Tree_insert(Tree *tree, int32_t data) { pthread_rwlock_wrlock(&tree->rwlock); int32_t ret = _insertNode(&tree->root_node, data); pthread_rwlock_unlock(&tree->rwlock); return ret; } int32_t Tree_locate(Tree *tree) { pthread_rwlock_rdlock(&tree->rwlock); int32_t ret = _locateNode(&tree->root_node); pthread_rwlock_unlock(&tree->rwlock); return ret; } void Tree_destroy(Tree *tree) { pthread_rwlock_destroy(&tree->rwlock); // yada yada }
Improve this answer

1 Comment

@Andrew: Apologies, I'm so used to doing this with Python contexts that cleaning up doesn't even come to mind anymore.
1

Lock the whole tree. There's no other way that will not get you into trouble sooner or later. Of course, if there's a lot of concurrent reads and writes, you will get a lot of blocking and slow everything down horribly.

Java introduced a concurrent skip list in version 1.6. Skip lists work like trees, but are (supposedly) a bit slower. However, they are based on singly linked lists, and therefore can theoretically be modified without locking using compare-and-swap. This makes for superb multi-threaded performance.

I googled "skip list" C++ compare-and-swap and came up with some interesting info but no C++ code. However, Java is open source, so you can get the algorithm if you are desperate enough. The Java class is: java.util.concurrent.ConcurrentSkipListMap.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.