Thread: Funny Linked List Error

Hello,
I'm writing a program to look at very large data sets. When I wrote the program to use a 3-d linked list, the thing did not finish over 3 days. I'd like to use arrays to take advantage of indexing, but there are very few computers that have enough ordered memory...

Anyway, to my point:
I have an array of linked list pointers, with each node in the first list pointing to a second (I have some knowledge about how my data will look, but not that much).

When I run my program, I get a nice segmentation fault. I tried running it in GDB and get this odd message: "Program received signal SIGSEV ... at line 299"

Code:

while(mag->next != NULL && mag->next->r < r_rB )

what it's referring to is this part of the code, which I call before (although I'm not making more than one list node from the array before I make a list of points.

Code:

rowH v1,mag = magArr[r_rA];
            if(mag == NULL)
               {
               if( (mag = (rowHeader *) malloc(sizeof(rowHeader))) == NULL)
                  {
                  printf ("Out of Memory!\n");exit(0);
                  };
               mag->next = NULL;
               mag->point = NULL;
               mag->r = r_rB;
               v1=mag;
               }
            
            else
               {
               while(mag->next != NULL && mag->next->r < r_rB ) //faults here
                  {
                  if(mag->r == r_rB)
                     break;
                  mag = mag->next;
                  }

This program is very long, but I'm not sure why it's faulting here. I wrote very similar code using random inputs for a small sample size and everything worked fine. I guess inputing 4000^3 points is difficult, but I think something is funny with my code. Any help is appreciated.

I'm curious in general as to your preference for using linked lists.

1) On a freshly booted system, if you don't have enough ordered memory, how will you have enough un-ordered memory?

Malloc only takes memory from the heap, and you can malloc an array worth of memory as easily as a linked list.

2) If you can't get enough memory to handle all your data in one huge array, why not handle it in two smaller array "chunks"? Process chunk A, then process chunk B. I've used this in the past, with excellent results.

That idea can be used to avoid causing the system to use a HD as temporary RAM (virtual memory). That will bring your program to it's knees!

I believe you'd see a remarkable speed up, by finding a way to use array(s), instead of linked lists, while avoiding any use of a swap file on the HD, by the OS.

The code looks fine. Well, we don't have the whole code to see if there is a chance the mag->next->r is pointing somewhere invalid. If it doesn't then probably it's a memory problem as you suspect.

I totally agree with Adak. Use arrays for efficiency if you can.

I don't really know what malloc() does when there isn't enough un-ordered memory. Why would it use the HDD though. Wouldn't it just give you an un-ordered memory? Or return NULL? That would be more efficient. Of course if you totally run out of memory then HDD cannot be avoided anyhow. I don't know though how efficient malloc() works.

And a linked list will need more memory. You will need to store values and the pointers. With an array you will save memory since you just need one pointer for the whole array. So even un-orderered an array should be better.

4000^3 points

You're completely out of memory. Assuming your struct is 8 bytes long, you will need 488281.25 megabytes of memory for the whole linked list. That is probably even larger than your hard drive.

That too :P