Container Data Structure

[aadityap0901]

Behold...
A new data structure for qb64 - The Container
It has many advantages:
* very fast add and delete
* very fast access

Keep in mind that this is not an indexed list, which means:
It shouldn't be used to for search, though it can be used to maintain counts...
It is actually used in Entity Component Systems, and not in many other simple things.

But this can be used in AI projects, to maintain a huge amount of entities.
It is actually configured for 4 byte Unsigned Long values, but it can be configured for fixed length strings.

Code: (Select All)

$Console:Only

Const Total = 16777216 ' 12 seconds on my arm64 laptop

ST! = Timer(0.01)

C$ = ContainerNewCapacity$(16777216)

Print "Container built in"; Timer(0.01) - ST!; "seconds"

Print "Length of C$: "; PrintSize(Len(C$))

For I = 1 To Total

    B~& = _RGBA32(Int(Rnd * 256), Int(Rnd * 256), Int(Rnd * 256), Int(Rnd * 256))

    ContainerAdd C$, B~&

Next I

Print Timer(0.01) - ST!

Sleep

System

Function ContainerNew$ () Static

    Static I As _Unsigned Long

    Static __S$

    __S$ = String$(64, 0): For I = 1 To 64 Step 4: Mid$(__S$, I, 4) = MKL$(_ShR(I, 2)): Next I

    ContainerNew$ = Chr$(16) + MKL$(16) + MKL$(0) + __S$ + __S$ + String$(64, 0)

    ' Signature + Capacity + Length + Index + Index Inverse + Data

End Function

Function ContainerNewCapacity$ (Capacity As _Unsigned Long) Static

    Static As _Unsigned Long I, J

    Static __S$

    __S$ = String$(_ShL(Capacity, 2), 0)

    For I = 1 To _ShL(Capacity, 2) Step 4

        J = _ShR(I, 2)

        Asc(__S$, I) = _Blue32(J)

        Asc(__S$, I + 1) = _Green32(J)

        Asc(__S$, I + 2) = _Red32(J)

        Asc(__S$, I + 3) = _Alpha32(J)

    Next I

    ContainerNewCapacity$ = Chr$(16) + MKL$(Capacity) + MKL$(0) + __S$ + __S$ + String$(_ShL(Capacity, 2), 0)

End Function

Sub ContainerAdd (Container As String, Element As _Unsigned Long) Static

    Static Length~&, Capacity~&

    If Len(Container) < 9 _OrElse Asc(Container) <> 16 Then Container = ContainerNew$

    Capacity~& = _RGBA32(Asc(Container, 4), Asc(Container, 3), Asc(Container, 2), Asc(Container, 5))

    Length~& = _RGBA32(Asc(Container, 8), Asc(Container, 7), Asc(Container, 6), Asc(Container, 9))

    If Capacity~& <= Length~& Then ContainerResizeCapacity Container, _IIf(Capacity~& < 1048576, _ShL(Capacity~&, 1), Capacity~& + 1048576)

    Capacity~& = _RGBA32(Asc(Container, 4), Asc(Container, 3), Asc(Container, 2), Asc(Container, 5))

    Mid$(Container, 6, 4) = MKL$(Length~& + 1)

    Asc(Container, 10 + _ShL(Capacity~&, 3) + _ShL(Length~&, 2)) = _Blue32(Element)

    Asc(Container, 11 + _ShL(Capacity~&, 3) + _ShL(Length~&, 2)) = _Green32(Element)

    Asc(Container, 12 + _ShL(Capacity~&, 3) + _ShL(Length~&, 2)) = _Red32(Element)

    Asc(Container, 9 + _ShL(Capacity~&, 3) + _ShL(Length~&, 2)) = _Alpha32(Element)

End Sub

Function ContainerLength~& (Container As String) Static

    ContainerLength~& = _RGBA32(Asc(Container, 8), Asc(Container, 7), Asc(Container, 6), Asc(Container, 9))

End Function

Function ContainerCapacity~& (Container As String) Static

    ContainerCapacity~& = _RGBA32(Asc(Container, 4), Asc(Container, 3), Asc(Container, 2), Asc(Container, 5))

End Function

Sub ContainerResizeCapacity (Container As String, NewSize As _Unsigned Long) Static

    Static Length~&, Capacity~&

    Capacity~& = _RGBA32(Asc(Container, 4), Asc(Container, 3), Asc(Container, 2), Asc(Container, 5))

    Length~& = _RGBA32(Asc(Container, 8), Asc(Container, 7), Asc(Container, 6), Asc(Container, 9))

    __T~& = _ShL(Capacity~&, 2)

    __Index$ = Mid$(Container, 10, __T~&)

    __IndexInverse$ = Mid$(Container, 10 + __T~&, __T~&)

    __Data$ = Mid$(Container, 10 + _ShL(__T~&, 1), _ShL(__T~&, 2))

    NewSize = _Max(Length~&, NewSize)

    __T~& = NewSize - Capacity~&

    If NewSize > Capacity~& Then

        __Index$ = __Index$ + String$(_ShL(__T~&, 2), 0)

        __IndexInverse$ = __IndexInverse$ + String$(_ShL(__T~&, 2), 0)

        __Data$ = __Data$ + String$(_ShL(__T~&, 2), 0)

    Else

        __Index$ = Left$(__Index$, _ShL(NewSize, 2))

        __IndexInverse$ = Left$(__IndexInverse$, _ShL(NewSize, 2))

        __Data$ = Left$(__Data$, _ShL(Length~&, 2))

    End If

    For I = 1 + _ShL(Capacity~&, 2) To _ShL(NewSize, 2) Step 4

        Mid$(__Index$, I, 4) = MKL$(_ShR(I, 2))

        Mid$(__IndexInverse$, I, 4) = MKL$(_ShR(I, 2))

    Next I

    Container = Chr$(16) + MKL$(NewSize) + MKL$(Length~&) + __Index$ + __IndexInverse$ + __Data$

End Sub

Function ContainerGet~& (Container As String, Index As _Unsigned Long) Static

    Static Length~&, Capacity~&, __Index~&

    Capacity~& = _RGBA32(Asc(Container, 4), Asc(Container, 3), Asc(Container, 2), Asc(Container, 5))

    Length~& = _RGBA32(Asc(Container, 8), Asc(Container, 7), Asc(Container, 6), Asc(Container, 9))

    __T~& = _ShL(Index, 2)

    __Index~& = _RGBA32(Asc(Container, 12 + __T~&), Asc(Container, 11 + __T~&), Asc(Container, 10 + __T~&), Asc(Container, 13 + __T~&))

    __Index~& = 10 + _ShL(__Index~&, 2) + _ShL(Capacity~&, 3)

    ContainerGet~& = _RGBA32(Asc(Container, 2 + __Index~&), Asc(Container, 1 + __Index~&), Asc(Container, __Index~&), Asc(Container, 3 + __Index~&))

End Function

Function PrintSize$ (__T As _Unsigned Long)

    If __T = 0 Then

        PrintSize$ = "0 B"

        Exit Function

    End If

    Select Case Int(Log(__T) / Log(2) / 10)

        Case 0: PrintSize$ = _ToStr$(__T) + " B"

        Case 1: PrintSize$ = _ToStr$(Round(__T / _ShL(1, 10))) + " KB"

        Case 2: PrintSize$ = _ToStr$(Round(__T / _ShL(1, 20))) + " MB"

        Case 3: PrintSize$ = _ToStr$(Round(__T / _ShL(1, 30))) + " GB"

    End Select

End Function

Function Round! (__N As Double)

    Round! = Int(100 * __N) / 100

End Function

This is currently incomplete, but has the most basic functions: add, resize, get
I will add a function to delete later.
I would like to see if anyone else has a data structure like this.
BTW, this is actually made because I saw this:  The magic container - YouTube