Back to General and Gameplay Programming

Thread-safe iteration/traversal

Nicolai · 2011-08-04T07:04:29

This is for C++, but the question also applies to programming in general. I am just beginning to learn concurrent programming for real, and some serious issues are starting to pop up. Normally - single-threaded, that is - when you have a class which manages objects of some sort in a structure, be that an STL container of just some custom tree with a parent pointer and children pointers for each node, and you want other classes to be able to iterate/list its contents, you have several options/patterns, but I cannot seem to make iteration thread-safe from outside the managing class. Internally, from inside the managing class, you can lock its internal mutex(es) and iterate, thereby ensuring thread-safety while iterating. This is how I am doing it now. Any comments on this? For instance, Ogre3D has STL iterator wrappers which are given the start and end iterator (normally begin() and end()) of the container and just checks the validity before advancement. But with multiple threads possibly altering the managing class, you cannot ensure thread-safety while iterating outside the class, since STL iterators are not thread-safe by themselves. How it this solved? I am also pretty sure that it is not only the iterator pattern which suffers from thread-insafety when used "normally". To mention some cases where I need to come up with thread-safe solutions, first I have a class managing the classic STL container with much data that needs to be listed/iterated, and then I have a custom tree structure which needs to be traversed, both listed below. I have a memory tracker which can return a list of memory leaks. Right now I just lock the internal mutex via a scoped lock and return a copy of the container containing the memory leaks (actually, it contains all tracked allocations, which is then considered memory leaks if they were not present at first). This is fine, because I only do it once, just before exiting the program. Doing it frequently at run-time, however, I would prefer not to copy the contents every time, as it may contain quite a lot of data. This can be solved by the returning iterators, such as the ones used within Ogre3D, for single-threaded programs - what about multi-threaded programs? I also have a virtual file system containing a node for each directory. Each node consists of a parent pointer (weak pointer), a container with subdirectories (shared pointers), a container with links (weak pointers to other nodes) and, finally, a container with files (shared pointers). Each file then consists of multiple file data (shared pointers), first prioritized by custom priority and secondly by last modified timestamps in order to control/merge overlapping file systems (for instance, the real game directory may contain directories/files which also exist in the archives - both are then merged into a single virtual file system). How would I go about thread-safely traversing this tree? Thanks in advance.

General and Gameplay Programming Programming

Started by nife87 July 31, 2011 06:11 PM

9 comments, last by JarkkoL 12 years, 8 months ago

JarkkoL

153

August 04, 2011 07:04 AM

[font="arial, verdana, tahoma, sans-serif"]Immutable objects in C++ are a pain to work with. For one, if it doesn't have an assignment operator, you can't use it in STL containers.[/font]

That sounds like a strange limitation of STL containers. I would have imagined only copy-constructor & destructor are required.

Cheers, Jarkko

[size="1"][size="1"]Spin-X Platform (sources) / Community / Blog / Twitter / Facebook

Thread-safe iteration/traversal

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Thread-safe iteration/traversal

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines