• Create Account

### #ActualKhatharr

Posted 31 December 2012 - 09:51 PM

'ptr' does not point to itself. Even if it did this would not be correct, since the arg is a copy with the same value rather than the same pointer. You need to search out the pointer value manually.

virtual void dealloc(char* ptr, size_t = 0) {MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

You must have edited this out, but I looked into it and finally made sense of it. After looking it over, I realized that this line of code was going back 8 bytes from 'ptr' but my real intention was to basically subtract 8 [ sizeof (MemChunk* )* 2 ] from the actual address of the pointer. I _think_ I accomplished that, like this.
MemChunk *pCurChunk = (MemChunk*) reinterpret_cast<char*>(reinterpret_cast<ptrdiff_t>(ptr)- static_cast<ptrdiff_t>(sizeof(MemChunk*) * 2));
Whether this fixed my problem is still yet to be tested extensively, but it passed the quick test I put together for it.

I also took your advice and added a data member to the MemChunk struct which does allow me to use an array index, making things a lot more readable.

Lastly, I realized that the addresses from mFirst to mLast were descending, which was the opposite of what I wanted it to do (which accounts for the weird subtraction in the getPtr() function). To fix that, I made the loop that links the nodes together run backwards (from mMaxSize to 0). That allowed me to directly access the memory in the getPtr function the way I intended.

Ah yeah, I edited that post like 20 times as I was wrestling with the forum and also trying to understand what the code as up to. I was confused as to what direction the list was going, but there's a lot of other stuff in there that seemed weird to me as well. I recognize that this is experimentation code. If I may point a few things out about the general design:

If you can access the allocated members by array index there's no need for MemChunk. You're just implementing a very complicated array, or perhaps reinventing std::vector at length. If all elements are equivalent in type then an indexed allocation is all you need, right?

In the case that you're wanting to be able to allocate multiple objects with one call then there's a simpler approach that may appeal to you:

Make yourself a struct like MemChunk. It needs next/prev pointers and should contain a 'size' indicator of some sort (element count or byte length or both). It may also contain metadata, such as the name of the allocation or whatever.

In your allocator class create a pointers to this type, 'root', 'head' and 'tail' or whatever. Point them all to the base of the allocation and zerofill the first sizeof(YourStruct) bytes of the allocation.

'root' shall never move. You need it to free the master allocation.

When you want to allocate, set the 'byteSize' member of 'tail' to the number of bytes you want, set your other metadata, then calculate a new pointer position: (sizeof(YourStruct) + byteSize). Set the 'next' member of 'tail' to that value, record the position of 'tail' then set 'tail' to tail->next. Finally, set tail->prev to the old 'tail' value and tail->next to NULL, indicating the end of the list.

Essentially 'tail' refers to the next allocatable space. For any linked node, if node->next is NULL then that's the end of the list and no valid data follows it. If root->next is NULL then no allocations are present.

To delete/free an allocation via its pointer simply subtract sizeof(YourStruct) from that pointer and unlink the node at that location. Check to see if the node is == head, and if so then unlink simply by saying head = head->next. Otherwise do a bidirectional unlink as normal.

You can enumerate determine the available space as follows:

endPtr = (address of root) + (size of master allocation)
available bytes = endPtr - (address of tail)

Just ensure that you use a byte-length type when you do the math there, or better yet, convert the pointers to an size_t and do the math on those. (size_t is unsigned 64-bit integer on an x64 system)

If you delete allocations that are not at the end then the memory will become fragmented. Rather than trying to cram things into the cracks just throw a bool indicating that a deallocation has caused fragmentation. If you run out of space and the fragmented flag is true you can traverse the nodes and compact the memory using &lt;string.h&gt; memmove() (I'll probably catch hell for saying that since it's a C function.). At that point check the available space as mentioned above and if it's still not enough then you can reallocate the master and copy in the data. Alternatively you can have const functions that return the available space and fragmentation status and expose the realloc and defrag functions. (if realloc is called when fragmentation is true just defrag into the new allocation)

Hope that helps.

Semi-edit - I clicked post and my phone took a crap, so I C&P my post body and reloaded, then Codarki had posted. Sorry if I'm reiterating. I consider myself ninja'd.

(OMG I'm about to go super saiyan and punch this parser in the dong.)

### #4Khatharr

Posted 31 December 2012 - 09:48 PM

<blockquote class="ipsBlockquote" data-author="SFCBias" data-cid="5016234" data-time="1357004911">
<blockquote class="ipsBlockquote" data-author="Khatharr" data-cid="5016077" data-time="1356967837">
<p>'ptr' does not point to itself. Even if it did this would not be correct, since the arg is a copy with the same value rather than the same pointer. You need to search out the pointer value manually.</p>
<pre class="_prettyXprint _lang-auto _linenums:1">
virtual void dealloc(char* ptr, size_t = 0) {MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));</pre>
</blockquote>
You must have edited this out, but I looked into it and finally made sense of it. After looking it over, I realized that this line of code was going back 8 bytes <strong>from 'ptr'</strong> but my real intention was to basically subtract 8 [ sizeof (MemChunk* )* 2 ] from the actual address of the pointer. I _think_ I accomplished that, like this.
<pre class="_prettyXprint _lang-auto _linenums:1">
MemChunk *pCurChunk = (MemChunk*) reinterpret_cast&lt;char*&gt;(reinterpret_cast&lt;ptrdiff_t&gt;(ptr)- static_cast&lt;ptrdiff_t&gt;(sizeof(MemChunk*) * 2));</pre>
Whether this fixed my problem is still yet to be tested extensively, but it passed the quick test I put together for it.<br />
<br />
I also took your advice and added a data member to the MemChunk struct which does allow me to use an array index, making things a lot more readable.<br />
<br />
Lastly, I realized that the addresses from mFirst to mLast were descending, which was the opposite of what I wanted it to do (which accounts for the weird subtraction in the getPtr() function). To fix that, I made the loop that links the nodes together run backwards (from mMaxSize to 0). That allowed me to directly access the memory in the getPtr function the way I intended.</blockquote>
<p>Ah yeah, I edited that post like 20 times as I was wrestling with the forum and also trying to understand what the code as up to. I was confused as to what direction the list was going, but there's a lot of other stuff in there that seemed weird to me as well. I recognize that this is experimentation code. If I may point a few things out about the general design:<br />
<br />
If you can access the allocated members by array index there's no need for MemChunk. You're just implementing a very complicated array, or perhaps reinventing std::vector at length. If all elements are equivalent in type then an indexed allocation is all you need, right?<br />
<br />
In the case that you're wanting to be able to allocate multiple objects with one call then there's a simpler approach that may appeal to you:<br />
<br />
Make yourself a struct like MemChunk. It needs next/prev pointers and should contain a 'size' indicator of some sort (element count or byte length or both). It may also contain metadata, such as the name of the allocation or whatever.<br />
<br />
In your allocator class create a pointers to this type, 'root', 'head' and 'tail' or whatever. Point them all to the base of the allocation and zerofill the first sizeof(YourStruct) bytes of the allocation.<br />
<br />
'root' shall never move. You need it to free the master allocation.<br />
<br />
When you want to allocate, set the 'byteSize' member of 'tail' to the number of bytes you want, set your other metadata, then calculate a new pointer position: (sizeof(YourStruct) + byteSize). Set the 'next' member of 'tail' to that value, record the position of 'tail' then set 'tail' to tail-&gt;next. Finally, set tail-&gt;prev to the old 'tail' value and tail-&gt;next to NULL, indicating the end of the list.<br />
<br />
Essentially 'tail' refers to the next allocatable space. For any linked node, if node-&gt;next is NULL then that's the end of the list and no valid data follows it. If root-&gt;next is NULL then no allocations are present.<br />
<br />
To delete/free an allocation via its pointer simply subtract sizeof(YourStruct) from that pointer and unlink the node at that location. Check to see if the node is == head, and if so then unlink simply by saying head = head-&gt;next. Otherwise do a bidirectional unlink as normal.<br />
<br />
You can enumerate determine the available space as follows:<br />
<br />
endPtr = (address of root) + (size of master allocation)<br />
available bytes = endPtr - (address of tail)<br />
<br />
Just ensure that you use a byte-length type when you do the math there, or better yet, convert the pointers to an size_t and do the math on those. (size_t is unsigned 64-bit integer on an x64 system)<br />
<br />
If you delete allocations that are not at the end then the memory will become fragmented. Rather than trying to cram things into the cracks just throw a bool indicating that a deallocation has caused fragmentation. If you run out of space and the fragmented flag is true you can traverse the nodes and compact the memory using &lt;string.h&gt; memmove() (I'll probably catch hell for saying that since it's a C function.). At that point check the available space as mentioned above and if it's still not enough then you can reallocate the master and copy in the data. Alternatively you can have const functions that return the available space and fragmentation status and expose the realloc and defrag functions. (if realloc is called when fragmentation is true just defrag into the new allocation)<br />
<br />
Hope that helps. <img class="bbc_emoticon" src="http://public.gamedev.net//public/style_emoticons/default/smile.png" title=":)" /><br />
<br />
Semi-edit - I clicked post and my phone took a crap, so I C&amp;P my post body and reloaded, then Codarki had posted. Sorry if I'm reiterating. I consider myself ninja'd.</p>

### #3Khatharr

Posted 31 December 2012 - 09:44 PM

'ptr' does not point to itself. Even if it did this would not be correct, since the arg is a copy with the same value rather than the same pointer. You need to search out the pointer value manually.

virtual void dealloc(char* ptr, size_t = 0) {MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));
You must have edited this out, but I looked into it and finally made sense of it. After looking it over, I realized that this line of code was going back 8 bytes from 'ptr' but my real intention was to basically subtract 8 [ sizeof (MemChunk* )* 2 ] from the actual address of the pointer. I _think_ I accomplished that, like this.
MemChunk *pCurChunk = (MemChunk*) reinterpret_cast<char*>(reinterpret_cast<ptrdiff_t>(ptr)- static_cast<ptrdiff_t>(sizeof(MemChunk*) * 2));
Whether this fixed my problem is still yet to be tested extensively, but it passed the quick test I put together for it.

I also took your advice and added a data member to the MemChunk struct which does allow me to use an array index, making things a lot more readable.

Lastly, I realized that the addresses from mFirst to mLast were descending, which was the opposite of what I wanted it to do (which accounts for the weird subtraction in the getPtr() function). To fix that, I made the loop that links the nodes together run backwards (from mMaxSize to 0). That allowed me to directly access the memory in the getPtr function the way I intended.
Ah yeah, I edited that post like 20 times as I was wrestling with the forum and also trying to understand what the code as up to. I was confused as to what direction the list was going, but there's a lot of other stuff in there that seemed weird to me as well. I recognize that this is experimentation code. If I may point a few things out about the general design:

If you can access the allocated members by array index there's no need for MemChunk. You're just implementing a very complicated array, or perhaps reinventing std::vector at length. If all elements are equivalent in type then an indexed allocation is all you need, right?

In the case that you're wanting to be able to allocate multiple objects with one call then there's a simpler approach that may appeal to you:

Make yourself a struct like MemChunk. It needs next/prev pointers and should contain a 'size' indicator of some sort (element count or byte length or both). It may also contain metadata, such as the name of the allocation or whatever.

In your allocator class create a pointers to this type, 'root', 'head' and 'tail' or whatever. Point them all to the base of the allocation and zerofill the first sizeof(YourStruct) bytes of the allocation.

'root' shall never move. You need it to free the master allocation.

When you want to allocate, set the 'byteSize' member of 'tail' to the number of bytes you want, set your other metadata, then calculate a new pointer position: (sizeof(YourStruct) + byteSize). Set the 'next' member of 'tail' to that value, record the position of 'tail' then set 'tail' to tail->next. Finally, set tail->prev to the old 'tail' value and tail->next to NULL, indicating the end of the list.

Essentially 'tail' refers to the next allocatable space. For any linked node, if node->next is NULL then that's the end of the list and no valid data follows it. If root->next is NULL then no allocations are present.

To delete/free an allocation via its pointer simply subtract sizeof(YourStruct) from that pointer and unlink the node at that location. Check to see if the node is == head, and if so then unlink simply by saying head = head->next. Otherwise do a bidirectional unlink as normal.

You can enumerate determine the available space as follows:

endPtr = (address of root) + (size of master allocation)
available bytes = endPtr - (address of tail)

Just ensure that you use a byte-length type when you do the math there, or better yet, convert the pointers to an size_t and do the math on those. (size_t is unsigned 64-bit integer on an x64 system)

If you delete allocations that are not at the end then the memory will become fragmented. Rather than trying to cram things into the cracks just throw a bool indicating that a deallocation has caused fragmentation. If you run out of space and the fragmented flag is true you can traverse the nodes and compact the memory using <string.h> memmove() (I'll probably catch hell for saying that since it's a C function.). At that point check the available space as mentioned above and if it's still not enough then you can reallocate the master and copy in the data.

Hope that helps.

Semi-edit - I clicked post and my phone took a crap, so I C&P my post body and reloaded, then Codarki had posted. Sorry if I'm reiterating. I consider myself ninja'd.

### #2Khatharr

Posted 31 December 2012 - 09:37 PM

'ptr' does not point to itself. Even if it did this would not be correct, since the arg is a copy with the same value rather than the same pointer. You need to search out the pointer value manually.

virtual void dealloc(char* ptr, size_t = 0) {MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

You must have edited this out, but I looked into it and finally made sense of it. After looking it over, I realized that this line of code was going back 8 bytes from 'ptr' but my real intention was to basically subtract 8 [ sizeof (MemChunk* )* 2 ] from the actual address of the pointer. I _think_ I accomplished that, like this.
MemChunk *pCurChunk = (MemChunk*) reinterpret_cast<char*>(reinterpret_cast<ptrdiff_t>(ptr)- static_cast<ptrdiff_t>(sizeof(MemChunk*) * 2));
Whether this fixed my problem is still yet to be tested extensively, but it passed the quick test I put together for it.

I also took your advice and added a data member to the MemChunk struct which does allow me to use an array index, making things a lot more readable.

Lastly, I realized that the addresses from mFirst to mLast were descending, which was the opposite of what I wanted it to do (which accounts for the weird subtraction in the getPtr() function). To fix that, I made the loop that links the nodes together run backwards (from mMaxSize to 0). That allowed me to directly access the memory in the getPtr function the way I intended.

Ah yeah, I edited that post like 20 times as I was wrestling with the forum and also trying to understand what the code as up to. I was confused as to what direction the list was going, but there's a lot of other stuff in there that seemed weird to me as well. I recognize that this is experimentation code. If I may point a few things out about the general design:

If you can access the allocated members by array index there's no need for MemChunk. You're just implementing a very complicated array, or perhaps reinventing std::vector at length. If all elements are equivalent in type then an indexed allocation is all you need, right?

In the case that you're wanting to be able to allocate multiple objects with one call then there's a simpler approach that may appeal to you:

Make yourself a struct like MemChunk. It needs next/prev pointers and should contain a 'size' indicator of some sort (element count or byte length or both). It may also contain metadata, such as the name of the allocation or whatever.

In your allocator class create a pointers to this type, 'root', 'head' and 'tail' or whatever. Point them all to the base of the allocation and zerofill the first sizeof(YourStruct) bytes of the allocation.

'root' shall never move. You need it to free the master allocation.

When you want to allocate, set the 'byteSize' member of 'tail' to the number of bytes you want, set your other metadata, then calculate a new pointer position: (sizeof(YourStruct) + byteSize). Set the 'next' member of 'tail' to that value, record the position of 'tail' then set 'tail' to tail->next. Finally, set tail->prev to the old 'tail' value and tail->next to NULL, indicating the end of the list.

Essentially 'tail' refers to the next allocatable space. For any linked node, if node->next is NULL then that's the end of the list and no valid data follows it. If root->next is NULL then no allocations are present.

To delete/free an allocation via its pointer simply subtract sizeof(YourStruct) from that pointer and unlink the node at that location. Check to see if the node is == head, and if so then unlink simply by saying head = head->next. Otherwise do a bidirectional unlink as normal.

You can enumerate determine the available space as follows:

endPtr = (address of root) + (size of master allocation)
available bytes = endPtr - (address of tail)

Just ensure that you use a byte-length type when you do the math there.

If you delete allocations that are not at the end then the memory will become fragmented. Rather than trying to cram things into the cracks just throw a bool indicating that a deallocation has caused fragmentation. If you run out of space and the fragmented flag is true you can traverse the nodes and compact the memory using <string.h> memmove() (I'll probably catch hell for saying that since it's a C function.). At that point check the available space as mentioned above and if it's still not enough then you can reallocate the master and copy in the data.

Hope that helps.

Semi-edit - I clicked post and my phone took a crap, so I C&P my post body and reloaded, then Codarki had posted. Sorry if I'm reiterating. I consider myself ninja'd.

### #1Khatharr

Posted 31 December 2012 - 09:32 PM

'ptr' does not point to itself. Even if it did this would not be correct, since the arg is a copy with the same value rather than the same pointer. You need to search out the pointer value manually.

virtual void dealloc(char* ptr, size_t = 0) {
MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

You must have edited this out, but I looked into it and finally made sense of it. After looking it over, I realized that this line of code was going back 8 bytes from 'ptr' but my real intention was to basically subtract 8 [ sizeof (MemChunk* )* 2 ] from the actual address of the pointer. I _think_ I accomplished that, like this.

MemChunk *pCurChunk = (MemChunk*) reinterpret_cast<char*>(reinterpret_cast<ptrdiff_t>(ptr)
- static_cast<ptrdiff_t>(sizeof(MemChunk*) * 2));

Whether this fixed my problem is still yet to be tested extensively, but it passed the quick test I put together for it.

I also took your advice and added a data member to the MemChunk struct which does allow me to use an array index, making things a lot more readable.

Lastly, I realized that the addresses from mFirst to mLast were descending, which was the opposite of what I wanted it to do (which accounts for the weird subtraction in the getPtr() function). To fix that, I made the loop that links the nodes together run backwards (from mMaxSize to 0). That allowed me to directly access the memory in the getPtr function the way I intended.

Ah yeah, I edited that post like 20 times as I was wrestling with the forum and also trying to understand what the code as up to. I was confused as to what direction the list was going, but there's a lot of other stuff in there that seemed weird to me as well. I recognize that this is experimentation code. If I may point a few things out about the general design:

If you can access the allocated members by array index there's no need for MemChunk. You're just implementing a very complicated array, or perhaps reinventing std::vector at length. If all elements are equivalent in type then an indexed allocation is all you need, right?

In the case that you're wanting to be able to allocate multiple objects with one call then there's a simpler approach that may appeal to you:

Make yourself a struct like MemChunk. It needs next/prev pointers and should contain a 'size' indicator of some sort (element count or byte length or both). It may also contain metadata, such as the name of the allocation or whatever.

In your allocator class create a pair of pointers to this type, 'root' and 'tail' or whatever. Point them both to the base of the allocation and zerofill the first sizeof(YourStruct) bytes of the allocation.

When you want to allocate, set the 'byteSize' member of 'tail' to the number of bytes you want, set your other metadata, then calculate a new pointer position: (sizeof(YourStruct) + byteSize). Set the 'next' member of 'tail' to that value, record the position of 'tail' then set 'tail' to tail->next. Finally, set tail->prev to the old 'tail' value and tail->next to NULL, indicating the end of the list.

Essentially 'tail' refers to the next allocatable space. For any linked node, if node->next is NULL then that's the end of the list and no valid data follows it. If root->next is NULL then no allocations are present.

To delete/free an allocation via its pointer simply subtract sizeof(YourStruct) from that pointer and unlink the node at that location.

You can enumerate determine the available space as follows:

endPtr = (address of root) + (size of master allocation)

available bytes = endPtr - (address of tail)

Just ensure that you use a byte-length type when you do the math there.

If you delete allocations that are not at the end then the memory will become fragmented. Rather than trying to cram things into the cracks just throw a bool indicating that a deallocation has caused fragmentation. If you run out of space and the fragmented flag is true you can traverse the nodes and compact the memory using <string.h> memmove() (I'll probably catch hell for saying that since it's a C function.). At that point check the available space as mentioned above and if it's still not enough then you can reallocate the master and copy in the data.

Hope that helps.

Semi-edit - I clicked post and my phone took a crap, so I C&P my post body and reloaded, then Codarki had posted. Sorry if I'm reiterating. I consider myself ninja'd.

PARTNERS