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?

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.

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!

> 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.

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.

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

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

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.

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

> 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. :)