Deadlock prevention in C

Here is a classical deadlock that wouldn't exist in Java (I think). How can I get around it?

Code:

struct Vertex {
	char label; // label
	color clr; // color
	List* adj; // adjacency list
	struct Vertex* pred; // predecessor
	bool critical; // flag if critical vertex
	int dTime; // discovery time
	int dist;
	int ind;
}; typedef struct Vertex Vertex;

struct List{
	Vertex* v;
	struct List* next;
}; typedef struct List List;
List* q;

You might want to elaborate. I am sure that the wizards in this area would instantly know what you are talking about, but rest of us need to figure out the words of the incantation before we can understand the deep magic.

Yeah I don't see a way out of that either, but I don't think it matters much -- you can just use a void pointer:

Code:

struct Vertex {
	char label; // label
	color clr; // color
        void *adj; // adjacency list
[...]
List *q;
Vertex V;
V.adj=q;

This doesn't require typecasting or anything, so the difference is only noticeable in the definition. Kind of cosmetic.

[edit] I guess a more proper way would be to use a forward declaration as described by ಠ_ಠ below.

[The] rest of us need to figure out the words of the incantation before we can understand the deep magic.

Poetry


Deadlock usually refers to threaded programming, where two threads lock against the same resource in such a way that neither will ever release.

This is a data structure, which offers a containment puzzle - and I 'divine' that's really the point of your inquiry.

If this is about the compiler not yet being aware of List, is it such a problem to provide a forward declaration?


As to containment, in this case there's a list of type vertex, where each vertex may have a list.

The problem relates to 'what owns the Vertex' - since it's likely that the Vertex pointer owned as an "adjacency list" refers to Vertex instances already 'owned' by a list elsewhere (that is, pointers to one Vertex may appear in multiple lists).

In Java and C# (and a host of similar languages sans pointers), this isn't a problem because every instance is contained by a reference counted containment system kept "under the hood" by the language itself.

I have to remind myself this is a subject about C, where it's not possible to automatically manage this kind of containment. Indeed, it's a classic problem in C development. Still, there are libraries that manage reference counted pointers in C, and that would solve the problem - or, a list would have to be 'tagged' in such a way that it's configured NOT to contain (that is, not delete) it's references - or containment would have to recognize the difference between a "primary list" and an "adjacency list" with respect to deletion.

In C++ one would select a reference counted smart pointer from any number of sources (boost, tr1, etc) which provide services quite similar to Java and C# with respect to the containment management (obviously, not garbage collection, though there are libraries for that, too).

Originally Posted by simpatico_qa

Here is a classical deadlock that wouldn't exist in Java (I think). How can I get around it?

Code:

struct Vertex {
	char label; // label
	color clr; // color
	List* adj; // adjacency list
	struct Vertex* pred; // predecessor
	bool critical; // flag if critical vertex
	int dTime; // discovery time
	int dist;
	int ind;
}; typedef struct Vertex Vertex;

struct List{
	Vertex* v;
	struct List* next;
}; typedef struct List List;
List* q;

put this above your structures

Code:

struct List;
typedef struct List List;
struct Vertex;
typedef struct Vertex Vertex;

Originally Posted by laserlight

You might want to elaborate. I am sure that the wizards in this area would instantly know what you are talking about, but rest of us need to figure out the words of the incantation before we can understand the deep magic.

he put the problem in bold

Originally Posted by ಠ_ಠ

he put the problem in bold

Oh, now I understand. I was trying to figure out if the critical member variable had anything to do with a critical section.

Originally Posted by ಠ_ಠ

put this above your structures

It would only be necessary to write:

Code:

typedef struct List List;
typedef struct Vertex Vertex;

Originally Posted by JVene

As to containment, in this case there's a list of type vertex, where each vertex may have a list.

The problem relates to 'what owns the Vertex' - since it's likely that the Vertex pointer owned as an "adjacency list" refers to Vertex instances already 'owned' by a list elsewhere (that is, pointers to one Vertex may appear in multiple lists).

I don't see any "problem" at all (maybe you could explain?) -- this concept of ownership seems out-of-place, and the only sensible issue I can conceive of in relation to this is about the scope of individual instances. Which should be easy to keep track of, right?

My C thinking is rusty, I admit - I have to go back over a decade.

To a C++ 'thinker' the issue of having a pointer refer to an instance which is contained by something else brings up the question, is the pointer a container or not? That is, will delete have to be called on that pointer.

In the adjacency list, the vertices included there are not 'owned' by that list - they are for reference only and don't act as containers, but this isn't obvious (and I must assume that's the intent with this snippet). It is by context that one realizes the difference.

In C++, where one might have containment management in List, the issue would require consideration - when does the list delete a vertex and when does it not?

In C, functions that manage containment would 'know' which is why by context, whether the list to be deleted was a member of a vertex or some other container.

But then, too, my point was relative to laserlight's post - we weren't entirely sure what "deadlock" really meant - a term usually used to refer to threaded programming, where the issues of containment are more pertinent.

This was an issue of declaration order - how the compiler would know what a list was. My point is a tributary based on the ambiguity of 'deadlock'

Originally Posted by JVene

My C thinking is rusty, I admit - I have to go back over a decade.

To a C++ 'thinker' the issue of having a pointer refer to an instance which is contained by something else brings up the question, is the pointer a container or not? That is, will delete have to be called on that pointer.

It sounded like you meant something like that; I don't know C++ but I know OO from elsewhere. Since there is no reference counting, etc, in C (unless you impliment it), this is kind of non-sensical in context.

If you delete/destroy/nullify a struct holding an allocated pointer, even if that pointer is not "referenced" anywhere else nor "owned" by anything else, you still have to free the pointer*. And a pointer will not be allocated anything other than a pointer automatically. So the question "will delete have to be called?" is easy to answer...the answer is always YES.

*hopefully first, or you will have no handle on it. Which would be a leak. Which means "garbage collection" must be done by the programmer.

If I may ask a related pointers question:

Code:

void eQ(List* l, Vertex* v){
	List* new = malloc(sizeof(List*)); new->v = v;
	if (l == NULL) l = new;
	else{
		List* temp = l;
		while (temp->next != NULL) temp = temp->next;
		temp->next = new;
	}
}
void connect(Vertex* v, Vertex* u){
	int i = vIndex(v); int j = vIndex(u);
	AC[i][j] = 1; AC[j][i] = 1;
	eQ(v->adj, u); eQ(u->adj, v);
}

Now unfortunately exiting eq(..) v->adj and u->adj remain unchanged pointing to null. I know of the solution: v->adj = eQ(v->adj, u) but I'd like to get the 'pointers' solution to work as well. Could someone suggest the code modifications to make to achieve that?

Originally Posted by simpatico_qa

Could someone suggest the code modifications to make to achieve that?

This is where C starts to seem obscure. You need to pass a pointer to a pointer and then dereference it in the function, eg:

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct this {
	char *ptr;
};

void test2 (char **ptr) {
	*ptr=malloc(12);
	strcpy(*ptr,"hello world");
}

void test1 (struct this *ptr) {
	test2(&ptr->ptr);
}

int main () {
	struct this that;
	test1(&that);
	printf("%s\n",that.ptr);
	return 0;
}

So going back to your example, the prototype for eQ would be:

Code:

	
void eQ(List** l, Vertex* v);

and in "connect"

Code:

eQ(&v->adj, u); eQ(&u->adj, v);

Get it?

Originally Posted by JVene

Quite certainly not.

If two pointers identify the same instance, which is likely the case in an adjacency list which may not be a hierarchical storage, but a reference of adjacent items which are contained by a different list, then deletion of what the pointer is pointing to in all cases would lead to double deletions, and crashes - the point I was making.

Sorry, I misunderstood you rather badly.

fair enough, what about this then:

Code:

void dQ(List** l){ if (*l != NULL) *l = *l->next;

adding brackets around *l should do the trick? What's the logic? This stuff I seem only to learn from other experienced developers and from trial and error.