www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Issue with free() for linked list implementation

reply "Kitt" <NekoAssassin gmail.com> writes:
Hello. I’m trying to write my own version of a list that doesn’t 
rely on the garbage collector. I’m working on a very bare bones 
implementation using malloc and free, but I’m running into an 
exception when I attempt to call free. Here is a very minimal 
code sample to illustrate the issue:

// Some constant values we can use
static const int two = 2, ten = 10;

// Get memory for two new nodes
Node* head = cast(Node*)malloc(two.sizeof);
Node* node1 = cast(Node*)malloc(ten.sizeof);

// Initialize the nodes
node1.value = ten;
node1.next = null;
head.value = two;	
head.next = node1;

// Attempt to free the head node
Node* temp = head.next;
head.next = null;
free(head); // Exception right here
head = temp;

Note, if I comment out the line ‘head.next = node1’, this code 
works. Does anyone know what I’m doing wrong with my manual 
memory management?
Apr 03 2015
parent reply "Namespace" <rswhite4 gmail.com> writes:
On Friday, 3 April 2015 at 22:02:13 UTC, Kitt wrote:
 Hello. I’m trying to write my own version of a list that 
 doesn’t rely on the garbage collector. I’m working on a very 
 bare bones implementation using malloc and free, but I’m 
 running into an exception when I attempt to call free. Here is 
 a very minimal code sample to illustrate the issue:

 // Some constant values we can use
 static const int two = 2, ten = 10;

 // Get memory for two new nodes
 Node* head = cast(Node*)malloc(two.sizeof);
 Node* node1 = cast(Node*)malloc(ten.sizeof);

 // Initialize the nodes
 node1.value = ten;
 node1.next = null;
 head.value = two;	
 head.next = node1;

 // Attempt to free the head node
 Node* temp = head.next;
 head.next = null;
 free(head); // Exception right here
 head = temp;

 Note, if I comment out the line ‘head.next = node1’, this code 
 works. Does anyone know what I’m doing wrong with my manual 
 memory management?
Why did you allocate only 2 / 10 bytes and not Node.sizeof bytes? Since your Node struct has at least one pointer (nexT) and a value (I assume of type int) you must allocate at least 8 bytes for one Node. I'm sure that is at least one of your problems.
Apr 03 2015
parent reply "Kitt" <NekoAssassin gmail.com> writes:
On Friday, 3 April 2015 at 22:06:06 UTC, Namespace wrote:
 On Friday, 3 April 2015 at 22:02:13 UTC, Kitt wrote:
 Hello. I’m trying to write my own version of a list that 
 doesn’t rely on the garbage collector. I’m working on a very 
 bare bones implementation using malloc and free, but I’m 
 running into an exception when I attempt to call free. Here is 
 a very minimal code sample to illustrate the issue:

 // Some constant values we can use
 static const int two = 2, ten = 10;

 // Get memory for two new nodes
 Node* head = cast(Node*)malloc(two.sizeof);
 Node* node1 = cast(Node*)malloc(ten.sizeof);

 // Initialize the nodes
 node1.value = ten;
 node1.next = null;
 head.value = two;	
 head.next = node1;

 // Attempt to free the head node
 Node* temp = head.next;
 head.next = null;
 free(head); // Exception right here
 head = temp;

 Note, if I comment out the line ‘head.next = node1’, this code 
 works. Does anyone know what I’m doing wrong with my manual 
 memory management?
Why did you allocate only 2 / 10 bytes and not Node.sizeof bytes? Since your Node struct has at least one pointer (nexT) and a value (I assume of type int) you must allocate at least 8 bytes for one Node. I'm sure that is at least one of your problems.
Wow, I can't even begin to explain how red my cheeks are right now. You're completely right; I have no idea what my head was thinking. Sure enough, call malloc with the correct type, and the error goes away =P Thanks for the help =) I guess I've been in C# land at work for way too long now, my low level C skills are evaporating!
Apr 03 2015
next sibling parent "Namespace" <rswhite4 gmail.com> writes:
 Wow, I can't even begin to explain how red my cheeks are right 
 now. You're completely right; I have no idea what my head was 
 thinking. Sure enough, call malloc with the correct type, and 
 the error goes away =P

 Thanks for the help =) I guess I've been in C# land at work for 
 way too long now, my low level C skills are evaporating!
Sometimes you wonder how simple such a problem can be. :D My pleasure.
Apr 03 2015
prev sibling next sibling parent reply "Gary Willoughby" <dev nomad.so> writes:
On Friday, 3 April 2015 at 22:08:52 UTC, Kitt wrote:
 Thanks for the help =) I guess I've been in C# land at work for 
 way too long now, my low level C skills are evaporating!
I've written a straight forward linked list implementation here: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d Even though I'm using the GC to manage memory, maybe it will help you.
Apr 03 2015
parent reply "Namespace" <rswhite4 gmail.com> writes:
On Friday, 3 April 2015 at 22:38:00 UTC, Gary Willoughby wrote:
 On Friday, 3 April 2015 at 22:08:52 UTC, Kitt wrote:
 Thanks for the help =) I guess I've been in C# land at work 
 for way too long now, my low level C skills are evaporating!
I've written a straight forward linked list implementation here: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d Even though I'm using the GC to manage memory, maybe it will help you.
Good idea to link to some existing code. Here is mine: https://github.com/Dgame/m3/blob/master/source/m3/List.d
Apr 03 2015
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Namespace:

 I've written a straight forward linked list implementation 
 here:

 https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d

 Even though I'm using the GC to manage memory, maybe it will 
 help you.
Good idea to link to some existing code. Here is mine: https://github.com/Dgame/m3/blob/master/source/m3/List.d
In 99%+ of cases it's a bad idea to use a linked list. Bye, bearophile
Apr 04 2015
parent "Namespace" <rswhite4 gmail.com> writes:
On Saturday, 4 April 2015 at 09:05:03 UTC, bearophile wrote:
 Namespace:

 I've written a straight forward linked list implementation 
 here:

 https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d

 Even though I'm using the GC to manage memory, maybe it will 
 help you.
Good idea to link to some existing code. Here is mine: https://github.com/Dgame/m3/blob/master/source/m3/List.d
In 99%+ of cases it's a bad idea to use a linked list. Bye, bearophile
The thread creator wanted to use it.
Apr 04 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/3/15 6:08 PM, Kitt wrote:
 On Friday, 3 April 2015 at 22:06:06 UTC, Namespace wrote:
 On Friday, 3 April 2015 at 22:02:13 UTC, Kitt wrote:
 Hello. I’m trying to write my own version of a list that doesn’t rely
 on the garbage collector. I’m working on a very bare bones
 implementation using malloc and free, but I’m running into an
 exception when I attempt to call free. Here is a very minimal code
 sample to illustrate the issue:

 // Some constant values we can use
 static const int two = 2, ten = 10;

 // Get memory for two new nodes
 Node* head = cast(Node*)malloc(two.sizeof);
 Node* node1 = cast(Node*)malloc(ten.sizeof);

 // Initialize the nodes
 node1.value = ten;
 node1.next = null;
 head.value = two;
 head.next = node1;

 // Attempt to free the head node
 Node* temp = head.next;
 head.next = null;
 free(head); // Exception right here
 head = temp;

 Note, if I comment out the line ‘head.next = node1’, this code works.
 Does anyone know what I’m doing wrong with my manual memory management?
Why did you allocate only 2 / 10 bytes and not Node.sizeof bytes? Since your Node struct has at least one pointer (nexT) and a value (I assume of type int) you must allocate at least 8 bytes for one Node. I'm sure that is at least one of your problems.
Wow, I can't even begin to explain how red my cheeks are right now. You're completely right; I have no idea what my head was thinking. Sure enough, call malloc with the correct type, and the error goes away =P Thanks for the help =) I guess I've been in C# land at work for way too long now, my low level C skills are evaporating!
I'm not here to redden your cheeks any further, but I did want to make sure you understood what actually was happening above: 1. you have established 2 integers named 'two' and 'ten'. These are simply integers. 2. When you malloc, you use 'two.sizeof' and 'ten.sizeof'. Integers are 4 bytes, so you were allocating 4 bytes for each of these (not 2 or 10 bytes as is alluded to above). 3. Then you are casting the resulting pointer as pointing at a "Node *". I'm assuming, having implemented linked lists many times and seeing your usage of Node, that it has at least a pointer and a value. Best case, this needs at least 8 bytes of space (32-bit CPU), and worst case 16 bytes (64-bit CPU). 4. When you access the "Node *" flavored pointer to your 4-byte block, you were corrupting memory in any case. Why does the free fail? Probably due to corrupted memory, be careful when using casts and C malloc. -Steve
Apr 06 2015
parent "Namespace" <rswhite4 gmail.com> writes:
 2. When you malloc, you use 'two.sizeof' and 'ten.sizeof'. 
 Integers are 4 bytes, so you were allocating 4 bytes for each 
 of these (not 2 or 10 bytes as is alluded to above).
Yeah, my mistake. I saw the mistake but could not describe it correctly. :)
Apr 06 2015