Array Allocation Management Examples

[kevin]

Array Allocation Management Examples

   This example demonstrates a stack approach managing active & free objects within a array, without iterating through the object array looking for free spaces.   It's works via storing all the available slots in the free stack and the allocated slots on the allocated stack.  In this example I've used two arrays for clarity.   Cell zero is used as the current stack size of either.

   When a new objects is requested,  we pop the last item from the free stack then add it to the allocated stack.   To retrieve is a little trickier logically, but effectively all were doing is copying the last used item from the allocated stack over the cell being released.    This freed index is then placed back on the free stack.   This keeps the allocated stack sequential without having to copy the cells above the delete point down.  

    To process the 'active' objects we iterate through the allocated stack, starting at index 1 and ending size value held in cell zero of the allocation stack.  . In this example the values stored in the stacks are indexes to whatever array you have to associate it with.   This could be made into a generic manager if you wanted,  but that's for you do to :)

   Although,  there is of course a simpler approach to doing this,  which i'll demo in a minute.




Download Attached
 

[kevin]

Array Allocation Management - Sequential Allocation Via Last Cell Swapping

   This example is variation of the above method.   The object in there version is to keep our array of activate objects packed together within one array.   So Active objects are stored from cell 1 to the number of objects.  The containing array is never searched,  or resized.  You can easily add some code tro handle expanding the array if need be, but it's not included in this example.  

    When a new ball object is requested,  we simply bump the BallCount variable (This is just a variable that holds the current number of used objects in our array) and return this as the new free index.  To free a cell,  we simply the swap the last cell with the cell we wish to remove.  Then decrease the ball counter variable.  The trick here is the swap.   In order to swap the elements in the typed array we're simply peeking the address of the cell to the remove and the last cell and swapping the handles they contain.  Hey presto...

    To iterate through the list of active objects (balls in this examples case), we just run a for loop from the index 1 to BallCount.   Obviously since we're possibly exchanging the order of cells while processing the list, it's assumed we're going to managing objects from start to finish.  If a current object is deleted, then we need to step back and repeat this loop (at this for counter position) other wise the last object(s) in the list won't get refreshed if there's a prior deletion.  Think about it :)



Download Attached

[kevin]

Array Allocation Management Examples (combined Example)

   This example is a variation of the first stack method.  In the first example we're using two arrays to manage free and allocated 'indexes' - However we can pack this into a single array.    

   As per the first example,  we initialize our allocation array with the sequence of FREE indexes.  Cell zero is used to keep track of the number of allocated Items.  Initially, this cell is zero.  (Since there's no allocated Items in the list, only free items)

   To get a free Index , we query number of allocated items (get cell zero) and then return this INDEX at this position in the allocation array.  In this example, it screens the number of items against the size of the allocation array.    If the allocation count is maxed it,  it doesn't bother returning anything.   You could of course Expanded the array in these situations,  but that's an exercise for the user .. :)

   To delete items,  we simply swap the cell to be deleted with the last allocated cell,  then decrease the allocation count.   If you think about it,  the allocation count is conceptually a divider between the two halves of the array.   On the left side (from index 1 to allocation count) we have allocated cells,  on the right side (from the number allocated cells to the end of the array)  we have the free cells.   So we're really just moving the marker point.

    To process the 'active' objects we iterate through the allocated stack array, starting at index 1 and ending size value held in cell zero of the allocation stack.  .

PlayBASIC Code: [Select]

; PROJECT : Array_Allocation_Manager_Combined
; AUTHOR  : Kevin Picone
; CREATED : 7/4/2008
; EDITED  : 7/4/2008
; ---------------------------------------------------------------------

   Type TObject
      X,y
      Size
      Colour
   EndType


   // Array to store both free and Allocated object indexes in
   Dim AllocatedStack(1)

   // Typed array container to hold the actual objects
   Dim Balls(1) as Tobject

   // In the Allocated/Free Index arrays
   InitAllocator(1000)
   
;*=-----------------------------------------------------------------------------=*   
;                              >> Main Loop <<
;*=-----------------------------------------------------------------------------=*   
   
   Do
      // Clear the Screen
         Cls rgb(0,0,0)


         // ====================================
         // Randomly add a new objects to the scene
         // ====================================

         if timer()>AddNextObject
            AddNextObject=timer()+rndRange(1,20)

            // Get Free Object time
            index=NewBall()
            
            if Index
               // Init the object at this position
               balls(index).x#   =-20
               balls(index).y#   =Rnd(600)
               balls(index).size   =RndRange(10,20)
               balls(index).Colour   =rndrgb()
            endif
         endif


         // ====================================
         // Process Allocated Object Stack
         // ====================================

         lockbuffer
         AllocatedCount=AllocatedStack(0)
         for lp=1 to AllocatedCount
         
            Index=AllocatedStack(lp)
            
            // Just make sure we're got an legal index (assume to be positive integer)
            If Index

                  // Move ball right and draw it 
                  Xpos=balls(index).x+1
                  Circlec xpos,balls(index).y,balls(index).Size,true,balls(index).Colour
                  balls(index).x=Xpos

                  // Check if ball is still on the screen
                  if xpos> 820

                     //If not, reclaim it....
                     
                     // Null this pointer in the typed array
                        Balls(index)=null

                     // reclaim this index from the allocated list
                        AllocatedCount=ReclaimBall(lp)
                        
                     // Step back to the current index, to avoid missing the last
                     // object, since they were swapped  during reclaim (delete) process.
                        dec lp
                  endif

            Endif         
         Next
         UNlockbuffer

         Size=GetArrayElements(AllocatedStack(),1)
         print "Used Count:"+str$(AllocatedStack(0))
         print "Free Count:"+str$(Size-AllocatedStack(0))

      Sync
   loop



;*=-----------------------------------------------------------------------------=*   
;                           >> Init the Allocation Arrays <<
;*=-----------------------------------------------------------------------------=*   

Function InitAllocator(Size)

      Dim AllocatedStack(Size)
      Dim Balls(size) as tobject

      ; predefine list of free cells from index 1 to array size   
      For lp=1 to Size
         AllocatedStack(lp)=lp   
      Next
      ; set the number of allocated objects to zero
      AllocatedStack(0)=0
      
EndFunction


;*=-----------------------------------------------------------------------------=*   
;                              >> Allocate New Ball <<
;*=-----------------------------------------------------------------------------=*   


Function NewBall()
      //Stack Sizes are store in Index 0 of the array
      UsedCount   =AllocatedStack(0)+1
      if UsedCount<=GetArrayElements(allocatedStack(),1)
         index=AllocatedStack(USedCount)
         AllocatedStack(0)=UsedCount
      endif
EndFunction index


;*=-----------------------------------------------------------------------------=*   
;                              >> Reclaim Ball <<
;*=-----------------------------------------------------------------------------=*   

Function ReclaimBall(AllocatedIndex)

      // Get the size of the Allocated Stack
      UsedSize=AllocatedStack(0)

      // Swap reclaimed object with the Last object in the allocated list
      Index=AllocatedStack(AllocatedIndex)
      AllocatedStack(AllocatedIndex)=AllocatedStack(UsedSize)
      AllocatedStack(UsedSize)=Index

      // Lower the allocated stack size
      dec UsedSize


Login required to view complete source code

Download Attached PlayBASIC Project