Container list

[VonGodric]

Hya,

I whipped this together becouse I need it for one of my project. It is a container like list ( a bit like std::vector ) that can store almost any type of data.

Code: Select all

option explicit
option escape

#include "crt.bi"

'
' This type definition is only thing that needs changing. Set it to any type of your 
' choosing. For example : integer | string | user defined data type
'
type _dTYPE as integer

    type TypeData    :_
        m_Data      as _dTYPE
    end type
    
    type TypeInfo
        m_MemSize   as integer
        m_Count     as integer
        m_DefSize   as integer
        m_Index     as TypeData ptr ptr
    end type
    
    #define NULLLIST    cptr( TypeInfo ptr, 0 )
    #define NULLDATA    cptr( TypeData ptr, 0 )
    #define CONT_CREATE( id, defSize ) :_
        dim id as TypeInfo : _
        id . m_Count = -1 : _
        id . m_DefSize = defSize
    
    sub Cont_Push ( byval list as TypeInfo ptr, node as _dTYPE )
    
        dim newNode     as TypeData ptr
        dim tempIdx     as TypeData ptr ptr
        dim tempSize    as integer
        
        if ( list = NULLLIST ) then exit sub
        if ( list->m_MemSize = 0 ) then
            list->m_MemSize = list->m_DefSize * len( TypeData ptr ) 
            list->m_Index = callocate( list->m_MemSize )
        elseif ( list->m_MemSize <= ( list->m_Count * len( TypeData ptr ) ) ) then
            tempSize = list->m_MemSize + list->m_DefSize * len( TypeData ptr ) 
            tempIdx = callocate( tempSize )
            memcpy ( tempIdx, list->m_Index, list->m_MemSize )
            deallocate list->m_Index
            list->m_MemSize = tempSize
            list->m_Index = tempIdx
            
        end if
        
        if ( list->m_Index[ list->m_Count ] = NULLDATA ) then
            newNode = allocate( len( TypeData ) )
            list->m_Index[ list->m_Count ] = newNode
        else
            newNode = list->m_Index[ list->m_Count ]
        end if
        newNode->m_Data = node
        list->m_Count += 1
    end sub
    
    function Cont_Pop ( byval list as TypeInfo ptr ) as _dTYPE
        if ( list = NULLLIST ) then exit sub
        if ( list->m_Count < 0 ) then exit sub
        list->m_Count -= 1
        dim node as TypeData ptr = list->m_Index[ list->m_Count ]
        function = node->m_Data        
    end function
    
    sub Cont_Strip ( byval list as TypeInfo ptr )
        if ( list = NULLLIST ) then exit sub
        dim total = list->m_MemSize / len( TypeData ptr )
        
        while ( total > list->m_Count )
            if ( list->m_Index[ total ] ) then
                deallocate list->m_Index[ total ]
                list->m_Index[ total ] = NULLDATA
            end if
            total -= 1
        wend
    end sub
    
    sub Cont_Remove ( byval list as TypeInfo ptr, byval el as uinteger )
        if ( list = NULLLIST ) then exit sub
        if ( list->m_Count < 0 ) then exit sub
        if ( el >= list->m_Count ) then exit sub
        dim s as uinteger
        for s = el to list->m_Count - 1
            list->m_Index[ s ] = list->m_Index[ s + 1 ]
        next
        list->m_Count -= 1
    end sub
    
    sub Cont_Insert( byval list as TypeInfo ptr, byval slot as uinteger, node as _dTYPE )
    
        dim newNode     as TypeData ptr
        dim tempIdx     as TypeData ptr ptr
        dim tempSize    as integer
        dim s as uinteger
        if ( list = NULLLIST ) then exit sub
        
        if ( list->m_Count < 1 ) then 
            Cont_Push( list, node )
            exit sub
        end if
        
        if ( slot >= list->m_Count ) then 
            Cont_Push( list, node )
            exit sub
        end if
        
        if ( list->m_MemSize = 0 ) then
            list->m_MemSize = 100 * len( TypeData ptr ) 
            list->m_Index = callocate( list->m_MemSize )
        elseif ( list->m_MemSize <= ( list->m_Count * len( TypeData ptr ) ) ) then
            tempSize = list->m_MemSize + 100 * len( TypeData ptr ) 
            tempIdx = callocate( tempSize )
            memcpy ( tempIdx, list->m_Index, list->m_MemSize )
            deallocate list->m_Index
            list->m_MemSize = tempSize
            list->m_Index = tempIdx
        end if
        
        newNode = list->m_Index[ list->m_Count ]
        
        for s = list->m_Count to slot + 1 step -1
            list->m_Index[ s ] = list->m_Index[ s - 1 ]
        next
        
        if ( newNode = NULLDATA ) then
            newNode = allocate( len( TypeData ) )
        end if
        list->m_Index[ slot ] = newNode
        newNode->m_Data = node
        list->m_Count += 1
        
    end sub
        
    
    function Cont_GetNode ( byval list as TypeInfo ptr, byval el as uinteger ) as _dTYPE
        if ( list = NULLLIST ) then exit sub
        if ( list->m_Count < 0 ) then exit sub
        if ( el >= list->m_Count ) then exit sub
        function =  list->m_Index[ el ]->m_Data
    end function

    
    function Cont_GetListPtr ( byval list as TypeInfo ptr ) as _dTYPE ptr
        if ( list = NULLLIST ) then exit sub
        return cptr( _dTYPE ptr, list->m_Index )
    end function
    
    function Cont_GetElCount ( byval list as TypeInfo ptr ) as uinteger
        if ( list = NULLLIST ) then exit sub
        return list->m_Count
    end function
    
    
    sub Cont_Swap ( byval list as TypeInfo ptr, byval el1 as uinteger, byval el2 as uinteger)
        if ( list = NULLLIST ) then exit sub
        if ( ( el1 < list->m_Count ) and ( el2 < list->m_Count ) and ( el1 <> el2 ) ) then
            swap list->m_Index[ el1 ], list->m_Index[ el2 ]
        end if
    end sub

Now using it:

Code: Select all

'Create container and set default size to 100 elements
CONT_CREATE( MyCont, 100 )
'Create a pointer, so we could access nodes via list ( fast )
dim c as _dTYPE ptr ptr
dim i

' Push some integers
Cont_Push ( @MyCont, 10 )   ' 0
Cont_Push ( @MyCont, 22 )   ' 1
Cont_Push ( @MyCont, 33 )   ' 2
Cont_Push ( @MyCont, 44 )   ' 3
Cont_Push ( @MyCont, 55 )   ' 4
Cont_Push ( @MyCont, 66 )   ' 5 
Cont_Push ( @MyCont, 77 )   ' 6
Cont_Push ( @MyCont, 88 )   ' 7
Cont_Push ( @MyCont, 99 )   ' 8
Cont_Push ( @MyCont, 111 )   ' 9

'Print out using indexed list
c = Cont_GetListPtr( @MyCont )
i = 0
while i < Cont_GetElCount( @MyCont )
    print i & " : " & *c[ i ]
    i += 1
wend


print "Test 2 : Insert : Press any key"
sleep
' Try inserting
Cont_Insert( @MyCont, 10, 333 )
Cont_Insert( @MyCont, 5, 444 )
'Print out. DO NOT forget to get a new pointer -internally might change!!!
c = Cont_GetListPtr( @MyCont )
i = 0
while i < Cont_GetElCount( @MyCont )
    print i & " : " & *c[ i ]
    i += 1
wend


print "Test 3 : Remove : Press any key"
sleep
'Try removing
Cont_Remove( @MyCont, 3 )
Cont_Remove( @MyCont, 5 )
Cont_Remove( @MyCont, 7 )
'Print out. DO NOT forget to get a new pointer -internally might change!!!
c = Cont_GetListPtr( @MyCont )
i = 0
while i < Cont_GetElCount( @MyCont )
    print i & " : " & *c[ i ]
    i += 1
wend

print "Test 4 : Pop : Press any key"
sleep
i = 0
while( Cont_GetElCount( @MyCont ) )
    print i & " : " & Cont_Pop( @MyCont )
    i += 1
wend

'And now to free unused memory
Cont_Strip( @MyCont )
sleep

Few more words:
Internally it allocates more memory then explicitly needed, and when removing nodes or poping them out, they are not deleted nor is memory freed. If you add something again into the list -previously allocated space will be reused. Also when calling CONT_CREATE you also specify initial amount of nodes. If you get more -no worries, it will just allocate more space. This way actually very few allocate/deallocates are done.

If you want to clear the list ( free memory ) then call Cont_Strip function. It will not effect nodes in the list in any way -only frees unused memory by the list.

Code: Select all

sub Cont_Push ( byval list as TypeInfo ptr, node as _dTYPE ) - pushes node to the list ( to the end of it).

function Cont_Pop ( byval list as TypeInfo ptr ) as _dTYPE - pop's the node from the end of the list

sub Cont_Strip ( byval list as TypeInfo ptr ) - strips the lcontainer of unused memory

sub Cont_Remove ( byval list as TypeInfo ptr, byval el as uinteger ) - remove the node specified by index.

sub Cont_Insert( byval list as TypeInfo ptr, byval slot as uinteger, node as _dTYPE ) - insert the node into the list -any point by an index

function Cont_GetNode ( byval list as TypeInfo ptr, byval el as uinteger ) as _dTYPE - returns a node specified by index, but does not remove it from the list. ( it is faster use indexed list showed in example, if many nodes are checked! )

function Cont_GetListPtr ( byval list as TypeInfo ptr ) as _dTYPE ptr - returns a pointer to be used with indexed list. However this function should be recalled as much as possible -becouse pointer returned may be changed during pushing, inserting.

function Cont_GetElCount ( byval list as TypeInfo ptr ) as uinteger - returns amount of nodes in the Container

sub Cont_Swap ( byval list as TypeInfo ptr, byval el1 as uinteger, byval el2 as uinteger) - swaps 2 nodes in the container.

Hope this is usefule.

[MystikShadows]

Von, what perfect timing :-). Here I was just now saying to myself, "man this would be so much easier if I had a pointer list or a container list". like less than 2 minutes ago...then I come here to check things up and here you are, with my solution...lol...Thanks for sharing :-)...I'll adapt it though cause I need a few more functionalities and such...Then again maybe I shouldn't look at it and just create one for myself (as a learning experience) then when I mess it up good, I'll cut and paste yours..ROFLMAO

[Imortis]

This Is Perfect! I have been researching neural networks, and this can be adapted very easly to Neural Network applications!

[Ryan]

I've unsuccessfully tried to use linked lists in a part program (something off with the way I was keeping track of what memory to deallocate), but this seems like it might do what I'm looking at doing. It won't compile as is, though. Gave me an error on line 29 that defSize was not declared. And I was wondering if this would be useable for an issue like this:

Basically, I was trying to keep track of all the users connected to my server with a linked list of my user data type. When one logged off it would deallocate that memory. When someone came on, it would allocate memory and tack 'em onto the list. I dunno, but it seems like I could use this code with my user type to do a similar thing. (Minus what you said about the memory not actually being deallocated.) I just don't quite understand the code that makes it work yet. ^_^

Also, I noticed the output for your example program was off. For the first list it prints onto the screen, it's actually misprinting the values. So when i is 0, it's printing the value as if i was 1. (Didn't know a better way to describe that..) If I set i to -1, it works fine and dandy.

[VonGodric]

It can be used to story any kind of data. Don't mind much about not deallocating the memory -you can force this by calling Cont_Strip every time you remover / pop from the container something.

However this output isn't best example but works here fine. With it's pop/push it works more like a stack.

1st part of code and 2nd part of code must both be used in the same src.