Contiguous Array version of Linked List

Backstory:
We were given a functional Linked List code and interface, and were told to change it to incorporate an array instead of next/prev pointers.
I decided to implement it as an in-order array that shifts whenever things are added.

The Problem:
I am getting segmentation faults whenever I try to add something to the array. The program doesn't seem to like me adding to the element_count variable in the List struct. If I comment the element_count++; it works, but then the underlaying code doesn't print anything out because it still thinks there are 0 elements.

Code:

The List struct

Code:

typedef struct List_t
{
	int     element_count;		/* number of elements in list */
	int     position;		/* current (numeric) position in list */
	Element *elementArray[MAX_SIZE];
} List;

The List creation

Code:

List *listCreate(void)
{

	List *new = NULL;		/* new list */

	if (!(new = calloc(1,sizeof(List))))
	    return(NULL);

	new->element_count = 0;
	new->position = 0;

	return(new);
}

The Element creation

Code:

Element *elementCreate(void *data)
{
	Element *new;		/* new element */

	if (!(new = calloc(1,sizeof(Element))))
		return(NULL);

	new->data = data;

	return(new);

} /* elementCreate */

The list is then passed back into the abstracted code and passed back into each function.
I didn't change anything in the interface or abstracted code, so it shouldn't be a problem there.

The Problematic Function

Code:

List *listAddAfter(List *this, void *data)
{
	int i;			/* loop index */
	Element *new;		/* new element */

	if (this->element_count >= MAX_SIZE)	/*Array boundary check*/
		return (NULL);
	if (!(new = elementCreate(data))) 	/*new element*/
		return (NULL);

	if (this->element_count == 0)
	{
		this->elementArray[0] = new;
		this->position = 1;
	}
	else if (this->element_count > 0)	/* Traverse array */
	{
		for (i = this->element_count ; i > this->position ; i--)
		{
			this->elementArray[i] = this->elementArray[i-1];
		}
		this->elementArray[this->position+1] = new;
	}

	this->element_count++; /* This is where it breaks */
	return(this);

} /* listAddAfter */

There is a function called listAddBefore which fails too, but it is essentially the same thing. The position just ends up in a different place.

Any help would be appreciated. I can give more code if requested.

Welcome to CBoard.

Code:

this->position = 1;

I think you should assign that to 0 . . . or rather, leave it alone since listCreate() sets it to zero.

Code:

		for (i = this->element_count ; i > this->position ; i--)
		{
			this->elementArray[i] = this->elementArray[i-1];
		}
		this->elementArray[this->position+1] = new;

Otherwise, you assign to [0] and then [2], over and over again. So incrementing this->position would be a good idea too. Perhaps

Code:

		this->elementArray[++ this->position] = new;

Oh and BTW, I wouldn't call a variable this or new if I were you. Those are both C++ keywords, so your code would not compile as C++.

Thanks for the welcome

I left the variable names the same as the code our professor gave us. Personally I don't really like them as my first language was Java (and I am also doing a Rogue-like project in Java that involves a lot of this.variable stuff), but it's not that big of a deal.

The position isn't the same as the position in the array.
If elementArray[0] were filled, its position would be 1, and the element_count would be 1.
It's just a pointer to where you are currently located in the "list"
For example:

[Something1] [Something2] *[Something3]* [Something4]
this->position would be equal to 3.

If it were left at 0 it still works, but to me it makes no sense, because something WAS added to the array/list, and position should be updated. That statement is only reached if there is nothing in the array when AddAfter is called. Regardless, it's not the source of the problem.


What makes me angry is listAddBefore was working once. It would add the element, the interface would print it out, and the position would be properly displayed. Then I did some changes to try and make it work all the time, and it broke.

As far as I can tell, listAddAfter makes perfect sense. If I follow it on paper, it works. Something is breaking in the abstracted code when element_count is incremented.

My code for these functions is identical to my friend's, but his works and mine does not. We tried to fix it for about 45 minutes but couldn't find anything wrong.

Well. Here's what I think is happening.

I'll assume that the list is empty to begin with. The first call to listAddAfter() creates a structure like this:

Code:

element_count = 1
position = 1
elementArray = {number1, random, random, ...}

where number1 is a pointer to the first element added.

Now, the next call is a little more interesting. This code executes:

Code:

		for (i = this->element_count ; i > this->position ; i--)
		{
			this->elementArray[i] = this->elementArray[i-1];
		}
		this->elementArray[this->position+1] = new;

Since element_count is 1, and so is this->position, the loop doesn't execute. But as this->position is 1, elementArray[2] is set. Okay, now the structure looks like this:

Code:

element_count = 2
position = 1
elementArray = {number1, random, number2, random, ...}

And, of course, the rest of your code, since element_count is 2, assumes that elementArray[1] exists. Which it doesn't. It's probably random, or at least NULL or something. And so your code segfaults.

The best way to fix it would be to drop the +1 here:

Code:

this->elementArray[this->position+1] = new;

Try it. It's possible that the change is minor enough that your friend's code has it and yours doesn't and you didn't notice.

Or, of course, now that I think about it, it might be even better to just set position to zero initially instead of 1.

P.S. I don't like those variable names . . . besides the fact that they are keywords in other languages, they're different styles . . . element_count uses "underscore notation", while elementArray uses Camel notation. Of course you can't do anything about it, though.

Yeah elementArray was added by me. Not a huge fan of underscores outside of #define

I took out the this->position = 1, I see where it would cause issues. I suppose it makes no difference, but this is what the original code looked like:

Code:

List *listAddAfter(List *this, void *data)
{
	Element *new;		/* new element */

	if (!(new = elementCreate(data)))
		return(NULL);

	/*
	 * link into list
	 */
	if (!this->elements)
	{
		this->elements = new;
		this->current = this->elements;
		elementSetLeft(this->current,new);
		elementSetRight(this->current,new);
		this->position++;
	}
	else
	{
		elementSetLeft(elementGetRight(this->current),new);
		elementSetRight(new,elementGetRight(this->current));
		elementSetLeft(new,this->current);
		elementSetRight(this->current,new);
	}
	this->element_count++;

	return(this);

} /* listAddAfter */

And here is what the input/interface looks like when I am using the function.

Code:

List (<ctrl-C> to quit):
1  - listClear()
2  - listHead()
3  - listTail()
4  - listPrev()
5  - listNext()
6  - listMoveToNth()
7  - listAddAfter()
8  - listAddBefore()
9  - listGetCurrent()
10 - listSetCurrent()
11 - listDelCurrent()
12 - listIsEmpty()
13 - listLength()
14 - listPosition()

CHOICE: 7

KEY(int)       : 7
STRING(char *) : 7

============

NEW (CURRENT) STATE:
Segmentation fault

with the original code it would appear as:

Code:

CHOICE: 7

KEY(int)       : 7
STRING(char *) : 7

============

NEW (CURRENT) STATE:
*>[7|7]<*

Hit <enter>...

Can you use a debugger to find out exactly what the data structure looked like when it segfaulted, and of course exactly where it segfaulted? That would greatly help aid your debugging.

Are you using GDB? If so, I can walk you through the commands you'd need to use if you like. Or if you want to post the source code I can compile it on my computer and have a look at it. You probably can't send me the executable because I'm running a 64-bit Debian GNU/Linux system.

I've never even heard of that I'm running on Ubuntu and compiling with gcc.
I can tar.gz the folder if that works for you.

I've pretty much given up on debugging this myself. I've moved on to the other parts of the project (encapsulating the List ADT into a Stack and Queue ADT... yay )

No? Debian is a reasonably common distribution of Linux. In fact I think it's second most common, right after Fedora Code (right, never heard of it either, eh?). In fact, I'm pretty sure that Ubuntu is originally based on Debian.

Anyway, it's irrelevant. Sure, you could send me the folder if you like. But if it's a large project I probably wouldn't be of much help. (Create the archive, rename it to a .TXT, and attach it to a post. That's the easiest way, if it isn't too large.)

Here's what I think you should do. Either use the debugger to walk through the code to see exactly what's happening, or do it automatically with frequent calls to something like the following:

Code:

void dumpList(List *list) {
    int x;

    printf("\n---- dump of List (%p)\n", list);
    printf("element_count = %d\nposition = %d\n",
        list->element_count, list->position);

    for(x = 0; x < list->element_count + 5; x ++) {
        printf("elementArray[%d] = %p\n", x, list->elementArray[x]);
    }
}

Fedora Core I use in some computer labs, but not Debian. We were given a choice of either Fedore or Ubuntu during the "Linux install-fest" and I was told Ubuntu would be better.

It's decently big, but the only file that I'm really concerned with is List.c
The rest is just there so that you'd be able to make it and run it (./ListMenu will run it after make, forget if it says that when compiling)

There's a lot of junk in there, but again, List.c and List.h are the only things I altered in any major way. I believe List.c is about 600 lines of code, but it's heavily commented.

I'll try more manual debugging myself. It's frustrating because I can't really directly print out what is in the array because it's a structure inside a structure and the -> trail would be huge.

EDIT:
Using dumpList, element_count is being incremented, there is a structure being placed into elementArray[0], position says as 0... but it still segfaults after list is returned to ListMenu (main).
I have a feeling it's an error with ListMenu printing out the results, but it's worked once or twice in the past.

Maybe it doesn't understand how there can be something in the list, but position is still 0?
The interface is supposed to display asterisks around the current element, but technically the "0" position doesn't exist outside of the Array. It would be 1.

Well, the cause of the actual segmentation fault is simple to find.

Code:

(gdb) run
Starting program: ...



List (<ctrl-C> to quit):
1  - listClear()
2  - listHead()
3  - listTail()
4  - listPrev()
5  - listNext()
6  - listMoveToNth()
7  - listAddAfter()
8  - listAddBefore()
9  - listGetCurrent()
10 - listSetCurrent()
11 - listDelCurrent()
12 - listIsEmpty()
13 - listLength()
14 - listPosition()

CHOICE: 7

KEY(int)       : 7
STRING(char *) : 7

============

NEW (CURRENT) STATE:

Program received signal SIGSEGV, Segmentation fault.
0x00000000004008ae in elementGetData (this=0x0) at Element.c:95
95              return(this->data);
(gdb) p *this
Cannot access memory at address 0x0
(gdb) l
90       *              void
91       * ---------------------------------------------------------
92       */
93      void *elementGetData(Element *this)
94      {
95              return(this->data);
96
97      } /* elementGetData */
98
99
(gdb)

elementGetData() does not check for a NULL pointer.

But why is that point NULL in the first place? Well, that's going to be interesting . . .

I've annotated this a very little.

Code:

(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y

Starting program: ... 



List (<ctrl-C> to quit):
1  - listClear()
2  - listHead()
3  - listTail()
4  - listPrev()
5  - listNext()
6  - listMoveToNth()
7  - listAddAfter()
8  - listAddBefore()
9  - listGetCurrent()
10 - listSetCurrent()
11 - listDelCurrent()
12 - listIsEmpty()
13 - listLength()
14 - listPosition()

CHOICE: 7

KEY(int)       : 7
STRING(char *) : 7

Breakpoint 1, listAddAfter (this=0x603010, data=0x604f60) at List.c:324
324             if (this->element_count >= MAX_SIZE)    /*Array boundary check*/
(gdb) l
319     List *listAddAfter(List *this, void *data)
320     {
321             int i;                  /* loop index */
322             Element *new;           /* new element */
323
324             if (this->element_count >= MAX_SIZE)    /*Array boundary check*/
325                     return (NULL);
326             if (!(new = elementCreate(data)))       /*new element*/
327                     return (NULL);
328
(gdb) n
326             if (!(new = elementCreate(data)))       /*new element*/
(gdb) 
329             if (this->element_count == 0)
(gdb) p *this
$2 = {element_count = 0, position = 0, elementArray = {
    0x0 <repeats 999 times>}}
(gdb) n
331                     this->elementArray[0] = new;
(gdb) 
342             this->element_count++;
(gdb) p *this
$3 = {element_count = 0, position = 0, elementArray = {0x604f80, 
    0x0 <repeats 998 times>}}
(gdb) n
343             return(this);
(gdb) 
345     } /* listAddAfter */
(gdb) 
main () at ListMenu.c:153
153                     printf("\n============\n\n");
(gdb) 

============

154                     printf("NEW (CURRENT) STATE:\n");
(gdb) 
NEW (CURRENT) STATE:
156                     savepos = listPosition(tst);
(gdb) p tst
$4 = (List *) 0x603010
(gdb) s
listPosition (this=0x603010) at List.c:578
578             return(this->position);
(gdb) p this
$5 = (List *) 0x603010
(gdb) p *this
$6 = {element_count = 1, position = 0, elementArray = {0x604f80, 
    0x0 <repeats 998 times>}}
(gdb) n
580     } /* listPosition */
(gdb) 
main () at ListMenu.c:158
158                     listHead(tst);
(gdb) p tst
$7 = (List *) 0x603010
(gdb) n
159                     if (listIsEmpty(tst))
(gdb) 
165                                     el = listGetCurrent(tst);
(gdb) p tst
$8 = (List *) 0x603010
(gdb) n

Program received signal SIGSEGV, Segmentation fault.
0x00000000004008ae in elementGetData (this=0x0) at Element.c:95
95              return(this->data);

Okay, so it's in the call to listGetCurrent that it segfaults. I add a breakpoint there.

Code:

(gdb) break listGetCurrent
Breakpoint 2 at 0x401379: file List.c, line 420.
(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y

Starting program: ...



List (<ctrl-C> to quit):
1  - listClear()
2  - listHead()
3  - listTail()
4  - listPrev()
5  - listNext()
6  - listMoveToNth()
7  - listAddAfter()
8  - listAddBefore()
9  - listGetCurrent()
10 - listSetCurrent()
11 - listDelCurrent()
12 - listIsEmpty()
13 - listLength()
14 - listPosition()

CHOICE: 7

KEY(int)       : 7
STRING(char *) : 7

Breakpoint 1, listAddAfter (this=0x603010, data=0x604f60) at List.c:324
324             if (this->element_count >= MAX_SIZE)    /*Array boundary check*/
(gdb) c
Continuing.

============

NEW (CURRENT) STATE:

Breakpoint 2, listGetCurrent (this=0x603010) at List.c:420
420             if (this->element_count == 0)
(gdb) l
415      *              NULL : list is empty
416      * ---------------------------------------------------------
417      */
418     void *listGetCurrent(List *this)
419     {
420             if (this->element_count == 0)
421                     return(NULL);
422
423             return(elementGetData(this->elementArray[this->position]));
424
(gdb) s
423             return(elementGetData(this->elementArray[this->position]));
(gdb) s
elementGetData (this=0x0) at Element.c:95
95              return(this->data);
(gdb) p this
$9 = (Element *) 0x0
(gdb) p *this
$10 = {element_count = 1, position = 1, elementArray = {0x604f80, 
    0x0 <repeats 998 times>}}
(gdb)

In other words, you're trying to access elementArray[position], which is elementArray[1]; even though elementArray[0] is the only valid element.

So something is probably changing position where is shouldn't be.

Code:

$ grep -n position *.c
List.c:40:      new->position = 0;
List.c:122:     this->position = 0;
List.c:133: *           - Adjust position to the beginning of provided list
List.c:141: *           position references the first element in
List.c:152:             this->position = 1;
List.c:165: *           - Adjust position to the end of provided list
List.c:173: *           position references the last element in
List.c:184:             this->position = this->element_count;
List.c:200: *           list is non-empty; list is not positioned at the
List.c:219:     if ((this->position == 1) || (this->element_count < 2))
List.c:222:     this->position--;
List.c:236: *           list is non-empty; list is not positioned at the
List.c:240: *           position now references the element
List.c:255:     if ((this->position == this->element_count) || (this->element_count < 2))
List.c:258:     this->position++;
List.c:275: *           position now references the "Nth" element
List.c:291:     this->position = n;
List.c:335:             for (i = this->element_count ; i > this->position ; i--)
List.c:339:             this->elementArray[this->position+1] = new;
List.c:386:             for (i = this->element_count ; i > this->position-1 ; i--)
List.c:390:             this->elementArray[this->position] = new;
List.c:391:             this->position++;
List.c:423:     return(elementGetData(this->elementArray[this->position]));
List.c:452:     dval = elementGetData(this->elementArray[this->position]);
List.c:453:     elementSetData(this->elementArray[this->position], data);
List.c:492:     el = this->elementArray[this->position];
List.c:497:     for (i = this->position ; i < this->element_count ; i++)
List.c:563: *           - Obtain numeric value of current position in
List.c:570: *           returns value of position
List.c:578:     return(this->position);
$

I've highlighted the only code that could make the value of position 1. Lines 152, 258, 291, and 391.

Line 152 is here:

Code:

List *listHead(List *this)
{
	if (this->element_count > 0)
	{
		this->position = 1;
		return(this);
	}
	else
		return(NULL);

} /* listHead */

I ran this through GDB:

Code:

(gdb) run
Starting program: ...



List (<ctrl-C> to quit):
1  - listClear()
2  - listHead()
3  - listTail()
4  - listPrev()
5  - listNext()
6  - listMoveToNth()
7  - listAddAfter()
8  - listAddBefore()
9  - listGetCurrent()
10 - listSetCurrent()
11 - listDelCurrent()
12 - listIsEmpty()
13 - listLength()
14 - listPosition()

CHOICE: 7

KEY(int)       : 7
STRING(char *) : 7

============

NEW (CURRENT) STATE:

Breakpoint 1, listHead (this=0x603010) at List.c:150
150             if (this->element_count > 0)
(gdb) p *this
$1 = {element_count = 1, position = 0, elementArray = {0x604f80, 
    0x0 <repeats 998 times>}}
(gdb)

It seems that that is the problem. I'd change that line in listHead to this->position = 0; if I were you. When I do that, the "7-7-7" input works just fine.

So there you have it. An extended debugging session. Enjoy.

BTW not that anyone cares... it's called Fedora now, the 'core' has been dropped since it's been merged together, the repos and everything.

Now I guess I have to add something helpful to this thread... carry on

You can tell I'm a Debian user myself.

A debugger like GDB is really a very useful programming tool. Even if you only know basic commands, like

• list [lines] (l): display sources code
• next (n): step over the next line
• step (s): step into the next line (go into functions)
• backtrace (bt): show which functions called which functions etc to get to the current place
• print [expression] (p): print the value of an expression or a variable -- you can do math here
• break (b): set a breakpoint
• continue (c): continue on executing without prompting before executing each line
• run [program-arguments] (r): restart the program
• quit (q): quit

where the format is command [optional arguments] (abbreviation that I use). Anything else, and you can use GDB's built-in help. It's really very extensive. Type "help" to get to it.

Wow. That looks very convoluted.
No idea listHead was being called from listAddAfter, so I didn't pay it any attention.

That solves that problem, thank you. Now the problem seems to be when adding a second element to the list, but I'm sure it's something inconsistent with the for loops.

The asterisks around the 7-7-7 entry means it's correctly point there, but when I use the listMoveToNth function and set it to 1 nothing is highlighted, but it does not seg fault.
n = 0 is not a valid entry for listMoveToNth.

Is there a legitimate way to set position to 1 when that first element is added?

Wow. That looks very convoluted.

Yeah, I typed a lot of extra stuff I didn't need to. But debugging tends to be like that. If I just showed you the optimal solution you might think I was extremely insightful or something, which wouldn't help you at all.

The asterisks around the 7-7-7 entry means it's correctly point there, but when I use the listMoveToNth function and set it to 1 nothing is highlighted, but it does not seg fault.
n = 0 is not a valid entry for listMoveToNth.

Well, look at it with a debugger and see what's happening! If you've never used one before, there's no time like the present . . . find a GDB tutorial, for example http://www.cprogramming.com/gdbtutorial.html, and start reading.

Is there a legitimate way to set position to 1 when that first element is added?

Not really. If you're assuming that elementArray[position] is a valid element, then you'll have to use 0 instead of 1. Really, I think that's what you should be doing anyway. It won't take too long, in all likelyhood. The grep only shows [*runs wc*] 30 usages of position, and some of those are comments.

Of course, you could assume that elementArray[position-1] is valid if you wanted to, but I think that would overly complicate things.

Yeah I see the problem, now that I take a look at the other functions.
I'll just go over it quickly and match up position with the array positions.

Curious, there's no more seg faults, but the position on the display isn't correct.

Code:

	else if (this->element_count > 0)	/* Traverse array */
	{
		for (i = this->element_count ; i > this->position ; i--)
		{
			this->elementArray[i] = this->elementArray[i-1];
		}
		this->elementArray[this->position+1] = new;
	}

Assuming there is already something in the array. It should cycle through the for loop, copy the element into the adjacent spot, then write over the spot directly infront of position..
list->position is jumping around wildly when I add 7-7-7 over and over.

When I follow it on paper is makes sense. Assume the capital letter is the current position, letters are elements.
Add 'r' After:
vBjk
vBjkk
vBjjk
vBrjk

Oh well, at least it's something I can deal with easily, unlike a seg fault.

Thank you for all your help dwks.