Nestharus
o-o
- Reaction score
- 84
http://www.thehelper.net/forums/showthread.php?t=137848
The collections framework deals with common collections and ways of allocating memory.
As of 8.0-
Malloc
Stacks
Dequeues
9.0 Will introduce a variety of trees and the queue data structure
It will also introduce some circular data structures.
The purpose of this guide is to give an understanding of how the collections framework can be used rather than packaged systems. For a deeper understanding of the API in the collections framework, please look into the collections framework header.
Malloc
------------------------------------------------------------
Malloc is the primary means of data allocation. This retrieves an instance for you to attach data to, like an index for an array. This method is used by structs.
Malloc uses an integer array and 2 integers for its allocation-
memory refers to memory's current index, free refers to how much free memory there is, and freed stores the memory. Memory typically starts at 1 as 0 is used for null or default values.
Allocation
Deallocation
Rather than writing this out constantly, structs are typically used (allocate and deallocated).
The collections framework uses macros to set up memory spaces, allocate, and free memory.
The namespace is similar to the concept of a vjass scope-
It allows multiple memory spaces within a given struct. The default memory spaces used by the framework's modules is "", so don't use that.
sets up the variables
Attempts to get freed memory
Otherwise gets new
Remember the if statement in the allocation? The if statement still exists and is automatically started with GET_FREED. It is not continued at all with GET_NEW, so our usage looks like this-
So these macros do the exact same thing as an efficient allocation method, but they save you code. The macro names are DYNAMIC_MEMORY as of 8.0, but they will change to MALLOC to be more standardized.
If you don't need the crazy power of these macros, there are also 2 different implementations of modules-
Stack
------------------------------------------------------------
Stacks are normally written as so-
And node operations are generally singular
The stacks in collections work differently and only have range operations as range and singular in it have exact same overhead.
variables
temporary copy to global range vars
move range
remove range
As you can see, memory allocation is not actually defined as that is completely up to you. Normally, malloc style is used, but sometimes a queue style memory allocation (like a buffer), list style (sub memory pools), or indexed style (unordered memory where only iteration through all elements matters).
What this means is that the stack only defines the stack and nothing else. Many collections come package with memory allocation, typically malloc as that can apply to anything.
When dealing with a stack, you are only ever supposed to be manipulating the first element, but with this implementation, it allows you to manipulate a range of elements if you really want to. Because a stack only points to the next element, you can only ever manipulate the element in front of the current element, so for example, move will move curNode.next through lastNode to in between targetNode and targetLastNode or
head->1->2->3->4->5
head->6->7->8->9->10
So, you are current on the first stack at 2. You want to move 2, but you can't. Why? You can't change where 1 points to.
To remove 2, you'd have to do this-
1 -> 3
And since you aren't currently pointing to 1, you can't. You can only move 3 through 5. You decide to move 3 and 4 to in between 6 and 7 on next list.
head->1->2->3->4->5
head->6->3->4->7->8->9
Uh oh, 3 and 4 are still in the first stack!! So how do you get them out of there so they aren't in two spots at once? With Remove. Each operation only does what it says it does, move only moves (like a copy) and remove only removes. They don't allocate, deallocate, or do anything extra.
So removing 3 and 4 from first stack results in this
head->1->2->5
head->6->3->4->7->8->9
Operation complete.
While this may seem harder than a typical move method in a packaged collection, it actually gives you more flexibility. Another operation would be swap, which is where you want move to act like it does. In fact, with swap, you never even have to remove values as the move operation replaces the pointers of where it goes in between.
Example-
4, 5, 6
7, 8, 9, 10, 11, 12
If you wanted to move 5 to in between 9 and 12, you'd get this
4, 5, 6
7, 8, 9, 5, 12
9 now points to 5 and 5 points to 12
Now what do you do with 10 and 11? You could either deallocate them and remove 5 from first stack or move them in between 4 and 6 (5's old position)
4, 10, 11, 6
7, 8, 9, 5, 12
Successful swap! : D
To keep the positions of the first swap intact, temporary variables have to be set. The actual operation (direct code from StackSwap module) looks like this:
And that is all there really is to a stack.
Dequeue
------------------------------------------------------------
A dequeue is much easier to work with than a stack, but it uses double pointers, previous and next. It also has a head and tail rather than just a head. This means that it is quite literally double the memory for initial creation and double the operations. While it may be double, the operations are still very low, especially compared to standard dequeue modules that you may find in other collection implementations in the wc3 community. A movement of 100 nodes is 306 operations in standard implementation whereas collections framework is only 4.
So really, you should be getting the macro patterns at this point
The move and remove apply to current node through last node rather than the current node's next because a dequeue has access to it's current's previous node.
0<-head<->1<->2<->3<->tail->0
However, because there is a head and a tail, it requires two nodes to form it up. Stack only needed one node, so no special operation was needed, you could really do w/e you wanted. With this, head and tail have their own operation.
Which just does this-
0<-head<->tail->0
--------------------------------------------------------------------
So, where can you use MALLOC, STACK, and DEQUEUE?
Virtually anywhere! Dequeues for projectile systems with Malloc for memory allocation, stacks for things like simplistic spawns or targets for a spell.
How do operations compare with stacks, dequeues, and queues?
stack- 2
queue- 3
dequeue- 4
extra memory?
stack- 1
queue- 2
dequeue- 2
So hopefully by this point, you can see that operation wise, this saves a massive amount on ranges and saves some extra operations on singles. Also, it has much more flexibility, and based on what you need you can go for a super simple API (all in one module), default API (one namespace/implementation), or macro API (w/e you want). I hope you can also see that writing this all out from scratch isn't fun and that the macros/modules are huge time saves. Yes, a struct may be a time saver on malloc memory allocation (given you don't want to be able to inject into on freed/on new and you want extra stuff, which is why you should at least use the malloc all in one module), and an all in one standard package in wc3 community might be super simple (but look at operations and look at how simple this is... this is actually simpler or as simple as all of them... it only has 2 operations!!), but I believe that this framework is the way to go in all scenarios no matter what your needs are. It beats out the competition hands down.
If there is anything else you think should be added to this guide on covering the current Collections Framework, let me know.
9.0 plans (this guide will be updated)-
queue
a billion trees (a billion)
circular stacks, queues, and dequeues
Why not indexed memory? Indexed memory is so simple that'd it'd actually be harder using macros than writing it from scratch ><.
The collections framework deals with common collections and ways of allocating memory.
As of 8.0-
Malloc
Stacks
Dequeues
9.0 Will introduce a variety of trees and the queue data structure
It will also introduce some circular data structures.
The purpose of this guide is to give an understanding of how the collections framework can be used rather than packaged systems. For a deeper understanding of the API in the collections framework, please look into the collections framework header.
Malloc
------------------------------------------------------------
Malloc is the primary means of data allocation. This retrieves an instance for you to attach data to, like an index for an array. This method is used by structs.
Malloc uses an integer array and 2 integers for its allocation-
memory refers to memory's current index, free refers to how much free memory there is, and freed stores the memory. Memory typically starts at 1 as 0 is used for null or default values.
Allocation
JASS:
local thistype this
if free > 0 then
set free = free - 1
set this = freed[free]
//do get freed code
else
set this = memory
set memory = memory + 1
//do get new code
endif
//do always codeDeallocation
JASS:
set freed[free] = this
set free = free + 1Rather than writing this out constantly, structs are typically used (allocate and deallocated).
The collections framework uses macros to set up memory spaces, allocate, and free memory.
JASS:
//! textmacro DYNAMIC_MEMORY takes NAMESPACE
//! textmacro DYNAMIC_MEMORY_GET_FREED takes NAMESPACE, TO_MEMORY
//! textmacro DYNAMIC_MEMORY_GET_NEW takes NAMESPACE, TO_MEMORY
//! textmacro DYNAMIC_MEMORY_FREE takes NAMESPACE, FROM_MEMORYThe namespace is similar to the concept of a vjass scope-
JASS:
scope Hi
endscopeIt allows multiple memory spaces within a given struct. The default memory spaces used by the framework's modules is "", so don't use that.
JASS:
//! textmacro DYNAMIC_MEMORY takes NAMESPACEsets up the variables
JASS:
//! textmacro DYNAMIC_MEMORY_GET_FREED takes NAMESPACE, TO_MEMORYAttempts to get freed memory
JASS:
//! textmacro DYNAMIC_MEMORY_GET_NEW takes NAMESPACE, TO_MEMORYOtherwise gets new
Remember the if statement in the allocation? The if statement still exists and is automatically started with GET_FREED. It is not continued at all with GET_NEW, so our usage looks like this-
JASS:
struct MyStruct extends array
//! runtextmacro DYNAMIC_MEMORY("test") //test is the namespace
public static method allocate takes nothing returns thistype
local thistype this
//! runtextmacro DYNAMIC_MEMORY_GET_FREED("test", "this")
//do get freed code
else
//! runtextmacro DYNAMIC_MEMORY_GET_NEW("test", "this")
//do get new code
endif
//do always code
endmethod
/*
//! textmacro DYNAMIC_MEMORY_FREE takes NAMESPACE, FROM_MEMORY
will pass var value into freed space
*/
public method deallocate takes nothing returns nothing
//! runtextmacro DYNAMIC_MEMORY_FREE("test", "this")
//do freed code
endmethod
endstructSo these macros do the exact same thing as an efficient allocation method, but they save you code. The macro names are DYNAMIC_MEMORY as of 8.0, but they will change to MALLOC to be more standardized.
If you don't need the crazy power of these macros, there are also 2 different implementations of modules-
JASS:
module DynamicMemoryStruct //first implementation, all in one
//second, like macros but thistype this is auto defined and namespace is ""
module DynamicMemory
module DynamicMemoryGet
module DynamicMemoryGetFreed
module DynamicMemoryGetNewStack
------------------------------------------------------------
Stacks are normally written as so-
JASS:
And node operations are generally singular
The stacks in collections work differently and only have range operations as range and singular in it have exact same overhead.
JASS:
//! textmacro STACK takes NAMESPACEvariables
JASS:
//! textmacro STACK_TEMP takes NAMESPACE, NODE_FIRST, NODE_LASTtemporary copy to global range vars
JASS:
//! textmacro STACK_MOVE takes NAMESPACE, NODE_FIRST, NODE_LAST, TO_NODE_FIRST, TO_NODE_LASTmove range
JASS:
//! textmacro STACK_REMOVE takes NAMESPACE, NODE_FIRST, NODE_LASTremove range
As you can see, memory allocation is not actually defined as that is completely up to you. Normally, malloc style is used, but sometimes a queue style memory allocation (like a buffer), list style (sub memory pools), or indexed style (unordered memory where only iteration through all elements matters).
What this means is that the stack only defines the stack and nothing else. Many collections come package with memory allocation, typically malloc as that can apply to anything.
When dealing with a stack, you are only ever supposed to be manipulating the first element, but with this implementation, it allows you to manipulate a range of elements if you really want to. Because a stack only points to the next element, you can only ever manipulate the element in front of the current element, so for example, move will move curNode.next through lastNode to in between targetNode and targetLastNode or
head->1->2->3->4->5
head->6->7->8->9->10
So, you are current on the first stack at 2. You want to move 2, but you can't. Why? You can't change where 1 points to.
To remove 2, you'd have to do this-
1 -> 3
And since you aren't currently pointing to 1, you can't. You can only move 3 through 5. You decide to move 3 and 4 to in between 6 and 7 on next list.
head->1->2->3->4->5
head->6->3->4->7->8->9
Uh oh, 3 and 4 are still in the first stack!! So how do you get them out of there so they aren't in two spots at once? With Remove. Each operation only does what it says it does, move only moves (like a copy) and remove only removes. They don't allocate, deallocate, or do anything extra.
So removing 3 and 4 from first stack results in this
head->1->2->5
head->6->3->4->7->8->9
Operation complete.
While this may seem harder than a typical move method in a packaged collection, it actually gives you more flexibility. Another operation would be swap, which is where you want move to act like it does. In fact, with swap, you never even have to remove values as the move operation replaces the pointers of where it goes in between.
Example-
4, 5, 6
7, 8, 9, 10, 11, 12
If you wanted to move 5 to in between 9 and 12, you'd get this
4, 5, 6
7, 8, 9, 5, 12
9 now points to 5 and 5 points to 12
Now what do you do with 10 and 11? You could either deallocate them and remove 5 from first stack or move them in between 4 and 6 (5's old position)
4, 10, 11, 6
7, 8, 9, 5, 12
Successful swap! : D
To keep the positions of the first swap intact, temporary variables have to be set. The actual operation (direct code from StackSwap module) looks like this:
JASS:
module StackSwap
//! runtextmacro STACK_TEMP("", "nodeFirst1", "nodeLast2")
//! runtextmacro STACK_MOVE("", "nodeFirst2.Next", "nodeLast2", "nodeFirst1", "nodeLast1.Next")
//! runtextmacro STACK_MOVE("", "thistype.tempPrevious", "nodeLast1", "nodeFirst2", "thistype.tempNext")
endmoduleAnd that is all there really is to a stack.
Dequeue
------------------------------------------------------------
A dequeue is much easier to work with than a stack, but it uses double pointers, previous and next. It also has a head and tail rather than just a head. This means that it is quite literally double the memory for initial creation and double the operations. While it may be double, the operations are still very low, especially compared to standard dequeue modules that you may find in other collection implementations in the wc3 community. A movement of 100 nodes is 306 operations in standard implementation whereas collections framework is only 4.
So really, you should be getting the macro patterns at this point
JASS:
//! textmacro DEQUEUE takes NAMESPACE
//! textmacro DEQUEUE_TEMP takes NAMESPACE, NODE_FIRST, NODE_LAST
//! textmacro DEQUEUE_MOVE takes NAMESPACE, NODE_FIRST, NODE_LAST, TO_NODE_FIRST, TO_NODE_LAST
//! textmacro DEQUEUE_REMOVE takes NAMESPACE, NODE_FIRST, NODE_LASTThe move and remove apply to current node through last node rather than the current node's next because a dequeue has access to it's current's previous node.
0<-head<->1<->2<->3<->tail->0
However, because there is a head and a tail, it requires two nodes to form it up. Stack only needed one node, so no special operation was needed, you could really do w/e you wanted. With this, head and tail have their own operation.
JASS:
//! textmacro DEQUEUE_FORM takes NAMESPACE, HEAD, TAILWhich just does this-
0<-head<->tail->0
--------------------------------------------------------------------
So, where can you use MALLOC, STACK, and DEQUEUE?
Virtually anywhere! Dequeues for projectile systems with Malloc for memory allocation, stacks for things like simplistic spawns or targets for a spell.
How do operations compare with stacks, dequeues, and queues?
stack- 2
queue- 3
dequeue- 4
extra memory?
stack- 1
queue- 2
dequeue- 2
So hopefully by this point, you can see that operation wise, this saves a massive amount on ranges and saves some extra operations on singles. Also, it has much more flexibility, and based on what you need you can go for a super simple API (all in one module), default API (one namespace/implementation), or macro API (w/e you want). I hope you can also see that writing this all out from scratch isn't fun and that the macros/modules are huge time saves. Yes, a struct may be a time saver on malloc memory allocation (given you don't want to be able to inject into on freed/on new and you want extra stuff, which is why you should at least use the malloc all in one module), and an all in one standard package in wc3 community might be super simple (but look at operations and look at how simple this is... this is actually simpler or as simple as all of them... it only has 2 operations!!), but I believe that this framework is the way to go in all scenarios no matter what your needs are. It beats out the competition hands down.
If there is anything else you think should be added to this guide on covering the current Collections Framework, let me know.
9.0 plans (this guide will be updated)-
queue
a billion trees (a billion)
circular stacks, queues, and dequeues
Why not indexed memory? Indexed memory is so simple that'd it'd actually be harder using macros than writing it from scratch ><.
