What happens to structs internally?

[Flux]

Hello everyone. I want to learn how structs internally operates.

After creating structs and looking at the actual script generated by JassHelper, this is the function it generates (struct name is myStruct)

//Generated allocator of myStruct
function s__myStruct__allocate takes nothing returns integer
    local integer this=si__myStruct_F
    if (this!=0) then
        set si__myStruct_F=si__myStruct_V[this]

    else
        set si__myStruct_I=si__myStruct_I+1
        set this=si__myStruct_I
    endif
    if (this>8190) then
        return 0
    endif
    set si__myStruct_V[this]=-1
    return this
endfunction

//Generated destructor of myStruct
function s__myStruct_deallocate takes integer this returns nothing
    if this==null then
        return
    elseif (si__myStruct_V[this]!=-1) then
        return
    endif
    
    set si__myStruct_V[this]=si__myStruct_F
    set si__myStruct_F=this
endfunction

Correct me if I'm wrong, but from what I see, the this integer is the instance/index of the struct data. However, I can't figure out what is the si__myStruct_V[this] and si__myStruct_F for? Does the allocation and deallocation operate like this?

8     4     2     9     7           this = 5
8    ---    2     9     7           this = 5
8     7     2     9                  this = 4

 

[Nestharus]

F = top of stack
V = stack

Just use the Alloc lib in spells section. It's better.

 

[PurgeandFire]

I'll break it down a bit.

Struct allocation behaves like a stack. (you can visualize it as one of those toys where you stack rings on a pipe):

Image

Before I go into the details, let me define what an instance is. Creating a new instance is equivalent to calling .allocate() or .create() for your struct. It is just creating a new index for you to use (struct members are internally stored as arrays, so .create() and .allocate() just returns an available index for you to use).

Next, let me go into the allocation process. First, it'll check if there are any available instances that can be reused. If there aren't any, it'll extend the cap by 1 and give you that new instance. It'll mark the instance as used, and then return that instance.

Let's break down the variables:

Instance Count	This is represented as si__myStruct_I, and it counts the total number of instances that were allocated.​
Free Index	This is represented as si_myStruct_F, and it points to the most recently freed instance.​
Stored Instances	This is represented as si_myStruct_V, and it keeps track of existing instances. Instances in use return -1. Otherwise, it points to an available index.​

Let's go back to our toy example to really visualize what is going on. We'll be creating a series of instances and observing what happens with all the variables that we are using.

• We'll be starting off with an empty struct. We haven't created anything yet.
  

  struct A
  endstruct

  Initial Configuration (Empty)

  
• Let's create 1 instance:
  

  set instances[1] = A.create()

  Observe what the code is reduced to:
  
  Code Analysis

  The allocation function looks pretty messy. But given the initial picture above, what do you think this function will simplify to?
  

  function s__myStruct__allocate takes nothing returns integer
      local integer this=si__myStruct_F // == 0
      if (this!=0) then
          set si__myStruct_F=si__myStruct_V[this]
  
      else
          set si__myStruct_I=si__myStruct_I+1 // I = 1
          set this=si__myStruct_I // this = 1
      endif
      if (this>8190) then
          return 0
      endif
      set si__myStruct_V[this]=-1 // V[1] = -1
      return this // return 1
  endfunction

  As shown by the comments, this is what it ultimately ends up doing on our first creation.
  

  function allocate takes nothing returns integer
      local integer this = 0
      set I = I + 1
      set this = I
      set V[this] = -1
      return this
  endfunction

  The struct didn't have any instances, so naturally there aren't any "free" instances yet. Instances are only considered "free" if they have been allocated and deallocated. As such, we raise our instance count (I = I + 1) and return that number (1).
  
  
  
  Image

  We created a new instance "1" for the user to use. It is simply placed on the side and given to the user. I've labeled it as "1" below.
  

  

  
  In "V", I have labeled the item as light blue. From now on, that will signify that the item is marked as used. In the code, it is equivalent to setting it to -1.
• Let's create two more instances.
  

  set instances[2] = A.create()
  set instances[3] = A.create()

  Image

  Similar to before--we don't have any "freed" instances yet. F still points to 0. As such, "I" will go up and we will simply give those instances to the user:
  

  

  
  Keep in mind that V isn't actually equal to an array of [1, 2, 3]. That just represents the indices and which are marked. It actually looks like:
  V[1] = -1
  V[2] = -1
  V[3] = -1
  This shows that all three of those instances are in use.
  
• Now let's try deallocating the instance "1".
  

  call instances[1].destroy()

  Code Analysis

  When we deallocate an instance, there are some preliminary checks to make sure we don't run into issues:
  (1) Is the instance null? If so, we should do nothing.
  (2) Is the instance not in use? If so, that means it was already deallocated, so the user probably did something wrong. Wc3 will print these as a "double-free" error if you have "Jasshelper -> Debug Mode" enabled.
  
  If those checks are passed, then it will set V[this] to point to F. In a way, you are kind of "storing" this value for later. Don't worry about it now, it'll be clear in the next example.
  
  In the next line, we set F (the last freed instance) to point to our deallocated instance, so that it can be reused.
  

  function s__myStruct_deallocate takes integer this returns nothing
      if this==null then
          return
      elseif (si__myStruct_V[this]!=-1) then
          return
      endif
      
      set si__myStruct_V[this]=si__myStruct_F
      set si__myStruct_F=this
  endfunction

  This would end up looking like this (for instance 1):
  

  set V[1] = F
  set F = 1

  
  
  Image

  This picture will be a lot to grasp, so bear with me.
  

  

  
  Ever since I made this image, you were probably wondering what that weird pole was on the left side. That will represent our "free" instances. When we allocate a new instance, we'll first check if there are any instances available from that pole. Otherwise we'll increase the instance count by 1 and make a brand new one. In our case, we moved 1 onto that pole since it is destroyed--it is now available for use on the next allocation.
  
  As such, F now points to 1 (the top of the pole "stack"). V changed too--1 is no longer in use, so it isn't marked as blue. Instead, the old value of F took its place, which is why a put a 0 there.
  
• If you are confused, don't worry. Let's keep moving by deallocating instance #2.
  

  call instances[2].destroy()

  Image

  Same process as before.
  

  

  
  Since we freed instance #2, we put it on top of the stack. And since F is supposed to point to the most recently freed instance, we set it to point to 2. But what will happen to instance 1? We want to keep track of it somewhere, so we set V[2] = 1, just like how we set V[1] = 0 in the previous example.
  
  What does this mean? Well, if we were to call .allocate() right now, it would grab 2 from the top. What else do you think would have to be done? We would have to mark "2" as "used" (mark it as blue in V), and we would have to set F to 1. We'll explore this in the next example.
• Let's allocate a new instance to finish off.
  

  set instances[2] = A.create()

  Image

  

  
  Notice anything familiar? This is exactly where we were 2 steps ago! When we allocated, it checked if there were any free instances on the stack. It grabbed 2 from the top, reassigned the "top" pointer to be 1, and set 2 as used. Hopefully this is expected behavior by now.
• Just to make things absolutely clear, I'll deallocate 3 as well.
  

  call instances[3].destroy()

  Image

  

  
  As you can see, we put 3 on top of the stack instead. V[3] was changed to point to 1 (the freed index below it), F was changed to 3 since that is the new top, and we're done!

Go through these examples and let me know if it is still confusing. I know it is a big wall of text, but hopefully the images will help you visualize the process in your head. Good luck.

 

[Nestharus]

Purge, make a tutorial on collections man .

Lists, stacks, queues, trees, BSTs, quad/octal trees, avl trees, red black trees, kd-trees, interval trees, range trees, min-max trees, decision trees, heaps, etc .

 

[BPower]

This is very nice structured and easy to understand. Good job.

 

[Flux]

Thanks Purge, those images and analogy really helped instead of using BJDebugMsg on Warcraft. I understand it very clearly now. Thanks for taking the time to write this.

 

[PurgeandFire]

Thanks guys. I'm glad it helped.

@Nestharus: I'd be pretty much teaching a data structures course. xD But I think it is always fascinating trying to explain data structures, so maybe I'd tackle some of them in the future.

 

[Nestharus]

@Purge

Do it : p

 

[Zwiebelchen]

@Purge:
Great job at explaining this... I'd say go and submit this as a tutorial, but it isn't really a tutorial, so umm...
maybe it's time for a "nice and useful things to know" sub-forum...

It could also list all the weird bugs and abuses we found over the years...

 

[Nestharus]

That's kinda what The Lab is.

 

[Zwiebelchen]

That's kinda what The Lab is.

Isn't the lab more for "check out this cool WIP"?

 

[Nestharus]

Eh, I guess you're right. I mean, you can also talk about weird hacks and stuff in The Lab too, like ConvertAttackType(7). I don't know if talking about structs would constitute as that though.

 

[Zwiebelchen]

Maybe we should rename the lab into "Script-Offtopic".