Constructing a Star System with O(1) Complexity

[mathmari]

Hey!

I want to write a function for the constitution of a star system "ss".
The new star system contains an empty list of planetary system, that means that in the list of the planetary system exists only the sentinel node, and the empty tree of the free-floating planets (ffp). The new star system should be inserted into the array of star systems(StarS). The complexity of the insertion should be $O(1)$.

The structures are the following:

struct starsy {
	int         ss;       /* The star system identifier. >0 */
	plansys_t *plasy;    /* Pointer to the first element in the list of the planetary system */
	plansys_t *Sentinel; /* Pointer to the sentinel node of the list of the planetary system */
	asteroid_t   *ff;   /* The free-floating planets tree  */
};struct plansys {
	int           solid;         /* The planetary system identifier. >0 */
	asteroid_t     *asteroids;     /* Pointer to the first node in the list of the asteroids */
	asteroid_t     *asentinel;   /* Pointer to the sentinel node of the asteroids tree */
	plansys_t      *next;        /* Pointer to the next node in the list of the planetary systemt */
};struct asteroid {
	int           as;         /* The asteroid identifier. >0 */
	int           gap;    /* The absolute gap from the object of the planetary system */
	asteroid_t     *PARENT;      /* Pointer to the parent node in the asteroids tree */
	asteroid_t     *LC;          /* Pointer to the left child in the asteroids tree */
	asteroid_t     *RC;          /* Pointer to the right child in the asteroids tree */
};

starsy_t StarS[N];     /*The array of the star systems, it is an array of lists */
 
int Sfreep;      /*An index to the first free position in the array of the star systems*/

I have the following:

int Constitution(int ss) {
        int i;
        starsy_t *starsystem=NULL;
        if(Sfreep<N){
        	starsystem = &StarS[Sfreep];
        	Sfreep++;
        }
        if(Sfreep>=N){
        	return -1;
        }
        starsystem->ss = ss;
        starsystem->plasy=NULL;
   	 	starsystem->Sentinel=NULL;
		starsystem->ff->as=INT_MAX;
		starsystem->ff->gap=INT_MAX;
		starsystem->ff->PARENT=NULL;
		starsystem->ff->LC=NULL;
		starsystem->ff->RC=NULL;
		
		return 0;
}

Is it correct?? (Wondering)

What does it mean "in the list of the planetary system exists only the sentinel node"?? (Wondering) How could we do that?? (Wondering)

 

[I like Serena]

Is it correct?? (Wondering)

What does it mean "in the list of the planetary system exists only the sentinel node"?? (Wondering) How could we do that?? (Wondering)

Hi! (Wave)

When you run it, does it perchance generate a segmentation fault? (Wondering)

A sentinel node is supposed to be a dummy node that you can check for when iterating over the collection.
That means that you have to create that dummy node, and that both the plasy and the Sentinel should point to it. The fact that they point to the same node means that the list is actually empty. (Nerd)

 

[mathmari]

When you run it, does it perchance generate a segmentation fault? (Wondering)

I get a segmentation fault... (Angry)

[m]Program received signal SIGSEGV, Segmentation fault.
0x00401c8b in Constitution (ss=762) at stars2.c:68
68 starsystem->ff->as=INT_MAX;[/m]

But why?? (Wondering)

A sentinel node is supposed to be a dummy node that you can check for when iterating over the collection.
That means that you have to create that dummy node, and the both the plasy and the Sentinel should point to it. The fact that they point to the same node means that the list is actually empty. (Nerd)

So, could we create the dummy node as followed??

plansys_t *Sen=NULL;
Sen->asentinel->as=-5;
Sen->asentinel->gap=-5;
Sen->asentinel->PARENT=NULL; 
Sen->asentinel->LC=NULL; 
Sen->asentinel->RC=NULL;

(Wondering)

 

[I like Serena]

I get a segmentation fault... (Angry)

[m]Program received signal SIGSEGV, Segmentation fault.
0x00401c8b in Constitution (ss=762) at stars2.c:68
68 starsystem->ff->as=INT_MAX;[/m]

But why?? (Wondering)

Where does [m]starsystem->ff[/m] point to? (Wondering)
Did you make it point to anything?
Because if not... chaos and madness! (Devil)

So, could we create the dummy node as followed??

plansys_t *Sen=NULL;
Sen->asentinel->as=-5;
Sen->asentinel->gap=-5;
Sen->asentinel->PARENT=NULL; 
Sen->asentinel->LC=NULL; 
Sen->asentinel->RC=NULL;

(Wondering)

Nope. Not quite. (Shake)

When you use [m]Sen->asentinel[/m], where does [m]Sen[/m] point to?
It doesn't point to anything does it? It's a NULL pointer.
There you go: segmentation fault. (Evilgrin)

 

[mathmari]

Where does [m]starsystem->ff[/m] point to? (Wondering)
Did you make it point to anything?
Because if not... chaos and madness! (Devil)

At the initialization function I wrote the following:

int Initialization() {
	int i, j;
	for(i=0; i<N; i++){
		StarS[i].ss=INT_MAX;
		StarS[i].plasy=NULL;
		StarS[i].Sentinel=NULL;
		StarS[i].ff->as=INT_MAX;
		StarS[i].ff->gap=INT_MAX;
		StarS[i].ff->PARENT=NULL;
		StarS[i].ff->LC=NULL;
		StarS[i].ff->RC=NULL;
	}
	return 0;
}

Do I have to write [m]StarS.ff=NULL;[/m] instead of

[m]StarS.ff->as=INT_MAX;
StarS.ff->gap=INT_MAX;
StarS.ff->PARENT=NULL;
StarS.ff->LC=NULL;
StarS.ff->RC=NULL;[/m]

?? (Wondering)

The description of the Initialization function is the following:

The structure of the array StarS should be initialized, where each field of each cell of the array should be initialized with the value [m]NULL[/m] if it is a pointer and [m]INT_MAX[/m] if it is of type int.

Nope. Not quite. (Shake)

When you use [m]Sen->asentinel[/m], where does [m]Sen[/m] point to?
It doesn't point to anything does it? It's a NULL pointer.
There you go: segmentation fault. (Evilgrin)

How could I do this then?? (Wondering)

 

[I like Serena]

Do I have to write [m]StarS.ff=NULL;[/m]?? (Wondering)

That does look much better! (Nod)

How could I do this then?? (Wondering)

I believe you should create a dummy node with [m]calloc[/m].
Then you can make plasy and Sentinel point to this new dummy node. (Nerd)

 

[mathmari]

That does look much better! (Nod)

Good! (Smile)

 

[mathmari]

I believe you should create a dummy node with [m]calloc[/m].
Then you can make plasy and Sentinel point to this new dummy node. (Nerd)

So, should it be as followed??

int Constitution(int ss) {
        int i;
        starsy_t *starsystem=NULL;
        plasy_t *Sen = calloc(1, sizeof(starsy_t));
        if(Sfreep<N){
        	starsystem = &StarS[Sfreep];
        	Sfreep++;
        }
        if(Sfreep>=N){
        	return -1;
        }
        Sen->solid=-5;
        Sen->asteroids=NULL;
	Sen->asentinel=NULL; 
	Sen->next=NULL; 
        starsystem->ss = ss;
        starsystem->plasy=Sen;
   	starsystem->Sentinel=Sen;
	starsystem->ff=NULL;
	return 0;
}

(Wondering)

 

[I like Serena]

So, should it be as followed??

int Constitution(int ss) {
        int i;
        starsy_t *starsystem=NULL;
        plasy_t *Sen = calloc(1, sizeof(starsy_t));
        if(Sfreep<N){
        	starsystem = &StarS[Sfreep];
        	Sfreep++;
        }
        if(Sfreep>=N){
        	return -1;
        }
        Sen->solid=-5;
        Sen->asteroids=NULL;
	Sen->asentinel=NULL; 
	Sen->next=NULL; 
        starsystem->ss = ss;
        starsystem->plasy=Sen;
   	starsystem->Sentinel=Sen;
	starsystem->ff=NULL;
	return 0;
}

(Wondering)

Much better! (Happy)The calloc() should be done after the possible [m]return -1[/m].
Otherwise you're allocating memory without every freeing it, when there is no space in StarS. (Worried)

And instead of [m]if(Sfreep>=N)[/m] it's better to write [m]else[/m]. (Nerd)Either way, everything gets initialized properly now without segmentation faults! (Nod)

 

[mathmari]

Much better! (Happy)The calloc() should be done after the possible [m]return -1[/m].
Otherwise you're allocating memory without every freeing it, when there is no space in StarS. (Worried)

And instead of [m]if(Sfreep>=N)[/m] it's better to write [m]else[/m]. (Nerd)Either way, everything gets initialized properly now without segmentation faults! (Nod)

Ok! (Mmm)

 

[mathmari]

Then I have to write also an other function for the constitution of a new asteroid with identifier "as" at the planetary system "solid".
"gap" is the gap between the new asteroid and the object of the planetray system "solid".
The new asteroid should be added in the appropriate position, in respect of the "gap", in the tree of asteroids of the planetray system "solid".
The field gap, that corresponds to the new asteroid, contains the gap from the object of the planetary system in which in contains.

I have done the following:

void Insert(asteroid_t *p, asteroid_t *new, asteroid_t Sentinel_node) {
   if (new->gap < p->gap) {
      if (root->LC == Sentinel_node)
         p->LC = new;
         
      else
         Insert(p->LC, new);
   }
 
   if (new->gap > p->gap) {
      if (p->RC == Sentinel_node)
         p->RC = new;
      else
         Insert(p->RC, new);
   }
}

void In_Order(asteroid_t *p, asteroid_t Sentinel_node) {
	if (p == Sentinel_node) return;
	In_Order(p->LC);
	printf(" %d , %d \n", p->as, p->gap);
	In_Order(p->RC);
}int asteroid_constitution(int as, int gap, int solid) {
	int i, g=0, k=-1;
	

	asteroid_t *ast = calloc(1, sizeof(asteroid_t));
	
	ast->as=as;
	ast->gap=gap;
	ast->PARENT=NULL;
	ast->LC=NULL;
	ast->RC=NULL; 
	
	plansys_t *p=NULL;
	
	for(i=0; i<Sfreep; i++){
		p=StarS[i].plasy;
		while (p != StarS[i].Sentinel && p->solid != solid){
			p=p->next;
		}
		if(p != StarS[i].Sentinel && p->solid == solid){
			k=i;
		}
	}
	if(k == -1){
		return -1;
	}
	
	p=StarS[k].plasy; 
	plasy_sent=p->asentinel;
	
	Insert(p->asteroids, ast, plasy_sent);
	In_Order(p->asteroids, plasy_sent);

	return 0;
}

Is this correct?? (Wondering)

Is the way I used the sentinel node correct?? (Wondering)

 

[mathmari]

Also, are the functions Insert() and In_Order() correct?? (Wondering)

 

[I like Serena]

void Insert(asteroid_t *p, asteroid_t *new, asteroid_t Sentinel_node) {

Shouldn't the Sentinel_node be a pointer? (Wondering)

   if (new->gap < p->gap) {
      if (root->LC == Sentinel_node)
         p->LC = new;

A Sentinel_node is supposed to go at the end of a linked list.
But it appears you have a binary tree?
I don't think a Sentinel node has a place in a binary tree.

And btw, shouldn't the Sentinel_node be linked to the end of the list? (Wondering)

void In_Order(asteroid_t *p, asteroid_t Sentinel_node) {
	if (p == Sentinel_node) return;

This is where I expect a compilation error. (Worried)
Do you get any? (Wondering)

	In_Order(p->LC);

This should generate another compilation error, since the function has 2 parameters. (Sweating)

int asteroid_constitution(int as, int gap, int solid) {
	int i, g=0, k=-1;
	asteroid_t *ast = calloc(1, sizeof(asteroid_t));
	...
	if(k == -1){
		return -1;
	}

The calloc() should be done after the possible [m]return -1[/m], since otherwise we have a memory leak.

	p=StarS[k].plasy; 
	plasy_sent=p->asentinel;
	
	Insert(p->asteroids, ast, plasy_sent);

I'm afraid this can't work correctly. (Worried)

If the insertion should be done at the head of the list, the head, which is [m]p->asteroids[/m], should be updated. But the function Insert() won't be able to do that, since you're passing a copy of the pointer to the function. (Sweating)

The same thing is true for the Sentinel, which needs to be updated if the asteroid is inserted at the end of the list. (Sweating)

 

[mathmari]

Shouldn't the Sentinel_node be a pointer? (Wondering)

This is where I expect a compilation error. (Worried)

This should generate another compilation error, since the function has 2 parameters. (Sweating)
The calloc() should be done after the possible [m]return -1[/m], since otherwise we have a memory leak.

I'm afraid this can't work correctly. (Worried)

If the insertion should be done at the head of the list, the head, which is [m]p->asteroids[/m], should be updated. But the function Insert() won't be able to do that, since you're passing a copy of the pointer to the function. (Sweating)

The same thing is true for the Sentinel, which needs to be updated if the asteroid is inserted at the end of the list. (Sweating)

I made some changes...

asteroid_t *Insert(asteroid_t *p, asteroid_t *new, asteroid_t *Sentinel_node) {
   if (new->gap < p->gap) {
      if (root->LC == Sentinel_node)
         p->LC = new;
         
      else
         Insert(p->LC, new, Sentinel_node);
   }
 
   if (new->gap > p->gap) {
      if (p->RC == Sentinel_node)
         p->RC = new;
      else
         Insert(p->RC, new, Sentinel_node);
   }
   return p;
}
void In_Order(asteroid_t *p, asteroid_t *Sentinel_node) {
	if (p == Sentinel_node) return;
	In_Order(p->LC, Sentinel_node);
	printf(" %d , %d \n", p->as, p->gap);
	In_Order(p->RC, Sentinel_node);
}
int asteroid_constitution(int as, int gap, int solid) {
	int i, g=0, k=-1;
	
	plansys_t *p=NULL;
	asteroid_t *plasy_sent=NULL;
	
	for(i=0; i<Sfreep; i++){
		p=StarS[i].plasy;
		while (p != StarS[i].Sentinel && p->solid != solid){
			p=p->next;
		}
		if(p != StarS[i].Sentinel && p->solid == solid){
			k=i;
		}
	}
	if(k == -1){
		return -1;
	}
	
	asteroid_t *ast = calloc(1, sizeof(asteroid_t));
	
	ast->as=as;
	ast->gap=gap;
	ast->PARENT=NULL;
	ast->LC=NULL;
	ast->RC=NULL; 
	
	p=StarS[k].plasy; 
	plasy_sent=p->asentinel;
	
	p->asteroids=Insert(p->asteroids, ast, plasy_sent);
	In_Order(p->asteroids, plasy_sent);

	return 0;
}

Is it better now?? (Wondering)

I get the following segmentation fault:

[m]Program received signal SIGSEGV, Segmentation fault.
0x00402459 in Insert (p=0x0, new=0x800599b0, Sentinel_node=0x80059998)
at stars2.c:146
146 if (new->gap < p->gap) {[/m]

(Wondering)

A Sentinel_node is supposed to go at the end of a linked list.
But it appears you have a binary tree?
I don't think a Sentinel node has a place in a binary tree.

And btw, shouldn't the Sentinel_node be linked to the end of the list? (Wondering)

The structures have the following form:

View attachment 3708

where T1 is the tree of free-floating planets:

View attachment 3709

and T2 is the tree of asteroids:

View attachment 3710

 

[I like Serena]

I made some changes...

Is it better now?? (Wondering)

I think you processed 5 of my 8 comments.
Good! (Happy)

Perhaps you can also process the remaining 3? (Wondering)

I get the following segmentation fault:

[m]Program received signal SIGSEGV, Segmentation fault.
0x00402459 in Insert (p=0x0, new=0x800599b0, Sentinel_node=0x80059998)
at stars2.c:146
146 if (new->gap < p->gap) {[/m]

(Wondering)

That's because p = NULL and p gets dereferenced.
It means that the list is empty, so it's not possible to refer to the first element of the list.
This is a case that needs to be handled separately.
In particular it means that [m]plasy->asteroids[/m] will need to get a new value.
So we need to find a way to be able to do that. (Thinking)

The structures have the following form

Aha! That clarifies what's going on. (Smile)

Hmm... it's a bit odd that Sentinel->next would point back in the list, isn't it?
It would make more sense if it were NULL. (Wasntme)

 

[mathmari]

I think you processed 5 of my 8 comments.
Good! (Happy)

(Happy)

Perhaps you can also process the remaining 3? (Wondering)

Which are the remaining 3 comments?? (Blush)

That's because p = NULL and p gets dereferenced.
It means that the list is empty, so it's not possible to refer to the first element of the list.
This is a case that needs to be handled separately.
In particular it means that [m]plasy->asteroids[/m] will need to get a new value.
So we need to find a way to be able to do that. (Thinking)

So, should we add the following if statement?? (Wondering)

asteroid_t *Insert(asteroid_t *p, asteroid_t *new, asteroid_t *Sentinel_node) {
   [COLOR="#FF0000"]if (p == NULL) p=new;[/COLOR]
   if (new->gap < p->gap) {
      if (root->LC == Sentinel_node)
         p->LC = new;
         
      else
         Insert(p->LC, new, Sentinel_node);
   }
 
   if (new->gap > p->gap) {
      if (p->RC == Sentinel_node)
         p->RC = new;
      else
         Insert(p->RC, new, Sentinel_node);
   }
   return p;
}

Aha! That clarifies what's going on. (Smile)

(Smile)

Hmm... it's a bit odd that Sentinel->next would point back in the list, isn't it?
It would make more sense if it were NULL. (Wasntme)

Yes... (Dull)

 

[I like Serena]

Which are the remaining 3 comments?? (Blush)

1. And btw, shouldn't the Sentinel_node be linked to the end of the list? (Wondering)
2. I'm afraid this can't work correctly. (Worried)
   If the insertion should be done at the head of the list, the head, which is [m]p->asteroids[/m], should be updated. But the function Insert() won't be able to do that, since you're passing a copy of the pointer to the function. (Sweating)
3. The same thing is true for the Sentinel, which needs to be updated if the asteroid is inserted at the end of the list. (Sweating)

(Nerd)

So, should we add the following if statement?? (Wondering)

asteroid_t *Insert(asteroid_t *p, asteroid_t *new, asteroid_t *Sentinel_node) {
   [COLOR="#FF0000"]if (p == NULL) p=new;[/COLOR]

That would fix the segmentation fault, but not the underlying root cause. (Worried)

The problem is that we want to insert at the beginning of the list, but we can't properly do that because we only have a NULL pointer instead of the actual head of the list. (Sweating)

 

[mathmari]

1.And btw, shouldn't the Sentinel_node be linked to the end of the list?
I'm afraid this can't work correctly.

At which point have I done this wrong?? (Wondering)

2. If the insertion should be done at the head of the list, the head, which is [m]p->asteroids[/m], should be updated. But the function Insert() won't be able to do that, since you're passing a copy of the pointer to the function.

So, do I have to update the pointer in the [m]main[/m] ??

3. The same thing is true for the Sentinel, which needs to be updated if the asteroid is inserted at the end of the list.

This should also be done in the main?? (Wondering)

That would fix the segmentation fault, but not the underlying root cause. (Worried)

The problem is that we want to insert at the beginning of the list, but we can't properly do that because we only have a NULL pointer instead of the actual head of the list. (Sweating)

Shouldn't instead of [m]NULL[/m] be the sentinel?? (Wondering)

 

[I like Serena]

At which point have I done this wrong?? (Wondering)

So, do I have to update the pointer in the [m]main[/m] ??

This should also be done in the main?? (Wondering)

Shouldn't instead of [m]NULL[/m] be the sentinel?? (Wondering)

I would pass [m]plasy[/m] to the Insert() function instead of [m]plasy->asteroids[/m] and [m]plasy->Sentinel[/m]. That allows the Insert() function to change the asteroids and Sentinel fields as it should. (Thinking)So no, it shouldn't be done in main(), it should be done inside the Insert() function. What you need is that the Insert() function has the access needed to do its job. (Nerd)

 

[mathmari]

I would pass [m]plasy[/m] to the Insert() function instead of [m]plasy->asteroids[/m] and [m]plasy->Sentinel[/m]. That allows the Insert() function to change the asteroids and Sentinel fields as it should. (Thinking)So no, it shouldn't be done in main(), it should be done inside the Insert() function. What you need is that the Insert() function has the access needed to do its job. (Nerd)

So, should it be as followed??

asteroid_t *Insert(plansys_t *p, asteroid_t *new) {
   if (p->asteroids == p->asentinel) p->asteroids=new;
   if (new->gap < p->asteroids->gap) {
      if (p->asteroids->LC == p->asentinel)
         p->asteroids->LC = new;
         
      else
         Insert(p->asteroids->LC, new);
   }
 
   if (new->gap > p->asteroids->gap) {
      if (p->asteroids->RC == p->asentinel)
         p->asteroids->RC = new;
      else
         Insert(p->asteroids->RC, new);
   }
   return p->asteroids;
}

void In_Order(plansys_t *p) {
	if (p->asteroids == p->asentinel) return;
	In_Order(p->asteroids->LC);
	printf(" %d , %d \n", p->asteroids->as, p->asteroids->gap);
	In_Order(p->asteroids->RC);
}
int asteroid_constitution(int as, int gap, int solid) {
	int i, g=0, k=-1;
	
	plansys_t *p=NULL;
	asteroid_t *plasy_sent=NULL;
	
	for(i=0; i<Sfreep; i++){
		p=StarS[i].plasy;
		while (p != StarS[i].Sentinel && p->solid != solid){
			p=p->next;
		}
		if(p != StarS[i].Sentinel && p->solid == solid){
			k=i;
		}
	}
	if(k == -1){
		return -1;
	}
	
	asteroid_t *ast = calloc(1, sizeof(asteroid_t));
	
	ast->as=as;
	ast->gap=gap;
	ast->PARENT=NULL;
	ast->LC=NULL;
	ast->RC=NULL; 
	
	p=StarS[k].plasy; 
	plasy_sent=p->asentinel;
	
	p->asteroids=Insert(p, ast, plasy_sent);
	In_Order(p->asteroids, plasy_sent);

	return 0;
}

(Wondering)

 

[mathmari]

asteroid_t *Insert(plansys_t *p, asteroid_t *new) {
   if (p->asteroids == p->asentinel) p->asteroids=new;
   if (new->gap < p->asteroids->gap) {
      if (p->asteroids->LC == p->asentinel)
         p->asteroids->LC = new;
         
      else
        [COLOR="#FF0000"] Insert(p->asteroids->LC, new);[/COLOR]
   }
 
   if (new->gap > p->asteroids->gap) {
      if (p->asteroids->RC == p->asentinel)
         p->asteroids->RC = new;
      else
        [COLOR="#FF0000"] Insert(p->asteroids->RC, new);[/COLOR]
   }
   return p->asteroids;
}

void In_Order(plansys_t *p) {
	if (p->asteroids == p->asentinel) return;
	[COLOR="#FF0000"]In_Order(p->asteroids->LC);[/COLOR]
	printf(" %d , %d \n", p->asteroids->as, p->asteroids->gap);
	[COLOR="#FF0000"]In_Order(p->asteroids->RC);[/COLOR]
}
int asteroid_constitution(int as, int gap, int solid) {
	int i, g=0, k=-1;
	
	plansys_t *p=NULL;
	asteroid_t *plasy_sent=NULL;
	
	for(i=0; i<Sfreep; i++){
		p=StarS[i].plasy;
		while (p != StarS[i].Sentinel && p->solid != solid){
			p=p->next;
		}
		if(p != StarS[i].Sentinel && p->solid == solid){
			k=i;
		}
	}
	if(k == -1){
		return -1;
	}
	
	asteroid_t *ast = calloc(1, sizeof(asteroid_t));
	
	ast->as=as;
	ast->gap=gap;
	ast->PARENT=NULL;
	ast->LC=NULL;
	ast->RC=NULL; 
	
	p=StarS[k].plasy; 
	plasy_sent=p->asentinel;
	
	p->asteroids=Insert(p, ast);
	In_Order(p);

	return 0;
}

When I call the function, at the red lines, the first argument is wrong, since it is an other type as we have defined the first argument.

What should it be then?? (Wondering)