I’ve had a hard time finding information about this, so I came to the one place I might be able to get an answer quickly.
Exactly how does one build and access a mutiple-threaded linked list? I understand it had mutiple heads, but other then that, I’m not sure how to make one.
struct node
{
int data;
node *next;
}
class list
{
Public:
list();
~list();
private:
node * head1;
node * head2;
}
list::list()
{
head1=NULL;
head2=NULL;
}
I’m not quite sure where to go from here. Could anyone give me a brief explnation or point me to a site which would have one?
The basic point is that access to the entire linked list is protected by a single mutex, so it’s safe for use by multiple threads at once. Other than that it’s a regular linked list.
On the other hand, if it’s not multi-thread safe linked lists (for use with multiple independantly running threads), then the question becomes ‘what are you using the multiple lists to accomplish’?
You can create an arbitrarily complex tree or set of lists or whatever you like, if you have a purpose in doing so.
You could maintain multiple lists in a single container to be able to keep them sorted by different criteria or something.
Treat it like a normal linked list, just with a separate insert and retrieve function for each of the different keys. So let’s assume your list is sorted by name, age, and sex.
OK, when you say “multithreaded”, you mean something entirely different from what we mean by it. Multithreading is the double-edged sword to end all double-edged swords; don’t mess with it unless you’ve got a good reason.
For what you’re doing, it might work just as well to have a single templated list class and create multiple instances as needed. You probably won’t need to store an arbitrary collection of those (which is an interesting proposition), so you can just put them in a struct. Is that reasonable?
Yes, everyone hear seems to have a different idea of what the term ‘multithreaded’ means.
Myself, I’m reminded of a problem question in an old C++/data structures primer asking for the implementation of a data structure called a “thread.” It was defined as a structure that could be traversed as a singly-linked list in sorted order by two different key fields - but with only one set of data nodes. (There would be other data fields besides the key field, so if you stepped to a particular node according to the first key and changed it, the same changes had to hold when you stepped to the same node by the second key. You didn’t have to worry about changing the key values themselves in this example, since that would mean moving a node to a different place in the sorted order.)
This isn’t quite what the OP asked for, though that just might be because HPL didn’t quite understand what he read. It’s pretty much what finangle was talking about, I now realize, except that he didn’t seem to cover the most important design point. Each node must have more than one next pointer – one for each thread index you want to support. (nextName and nextAge, for instance.)
I’m sorry I haven’t been able to be more clear about this. I’m doing this for a class and we really haven’t talked about how it works…we are just expected to know it.
The class/structure I posted was as well as I understand the concept, which is not very well.
However, I appreciate the help I’ve been given so far. Thank you all.
I think that this is the idea you’re getting at…say that you have a set of data that you want to store in two different orders, incrementing and decrementing, in the hopes of halving your access time (as this seems to be the only practical purpose that doing this can serve). To do that, based on the code you started with (btw, the code tag is your friend):
struct node
{
int key;
void *data;
node *next1;
node * next2;
}
class list
{
Public:
list();
~list();
void insert (key, data);
void *find (key);
private:
node * head1; //incrementing
node * head2; //decrimenting
int max_key; //silly bookkeeping thing used for bad estimation in attempt
// to optimize find()
}
list::list()
{
head1=NULL;
head2=NULL;
}
list::insert(key, data)
{
node *new_node = new(node);
new_node->key = key;
new_node->data = data;
if (key > max_key) max_key = key;
for( node *np = head1, *np_trail = 0; np != null; np=np->next1, np_trail = np)
{
if (key > np->key)
{
if (np_trail != null)
{
new_node->next1 = np;
np_trail->next1 = new_node;
} else {
new_node->next1 = head1;
head1 = new_node;
}
}
}
for( node *np = head2, *np_trail = 0; np != null; np=np->next1, np_trail = np)
{
if (key < np->key)
{
if (np_trail != null)
{
new_node->next2 = np;
np_trail->next2 = new_node;
} else {
new_node->next2 = head2;
head2 = new_node;
}
}
}
}
void * list::find(int key)
{
if (key < (max_key / 2))
{
/* walk the incrementing list until you find the right node */
} else {
/* walk the decrementing list until you find the right node */
}
}
If done theortically perfectly, this doubles your insert time while halving your find time, and would be best suited for large structures with infrequent additions.
