Dynamic LinkedList / Array of LinkedList

Trond · Post by **Trond** » Wed Nov 01, 2006 11:37 am

Edit: If you use Windows 9.x you must manually free all the lists before you end the program. Also the free list procedure isn't very tested so I hope it works...

This code allows you to create native PB linked lists on-the-fly. You can put them into arrays, sort them and juggle them around as you see fit.

Each function that deals with the dynamic lists requires the type of the list as a postfix to the function name, so to bind a list name to a dynamic list of strings, the function used is BindListS(ListName(), List). To create a new list of strings, use List.q = DynamicNewListS().

To create functions for a type use UseListType(Type). All this becomes clear as you see the example.

The code that you need to include or put on top of your file:

Code: Select all

Macro GlobalNewDynamicListPointer(Name, Type)
  If 0
    Global NewList Name.Type()
  EndIf
EndMacro

Macro NewDynamicListPointer(Name, Type)
  If 0
    NewList Name.Type()
  EndIf
EndMacro

Macro BindListTemplate(Type)
  Procedure BindList#Type(List.Type(), ID.q)
    !mov eax, [p.v_ID]
    !mov edx, [p.v_ID+4]
    !mov ecx, [p.v_ID-4]
    !mov [ecx], eax
    !add ecx, 4
    !mov [ecx], edx
  EndProcedure
EndMacro

Macro DynamicNewListTemplate(Type)
  Procedure.q DynamicNewList#Type()
    Protected NewList Local.Type()
    !mov eax, [esp]
    !mov edx, [esp+4]
    !add esp, 8
    !ret
  EndProcedure
EndMacro

Macro FreeListTemplate(Type)
  Procedure FreeList#Type(ID.q)
    If 0
      NewList Dummy.Type()
    EndIf
    BindList#Type(Dummy(), ID.q)
  EndProcedure
EndMacro

Macro UseListType(Type)
  BindListTemplate(Type)
  DynamicNewListTemplate(Type)
  FreeListTemplate(Type)
EndMacro

Example of an array of linked lists of strings. It assumes that the code above is included.

Code: Select all

UseListType(S) ; Generate functions with postfix S for string type
; UseListType(L) ; Generate functions with postfix L for long type

#ArrayLen = 10
; Allocate array
Dim ListArray.q(#ArrayLen) ; Notice that ListArray is of type .q. It can
; store lists of any type.

; Create a dummy list ("list name") to represent the dynamic lists
; Global means that NAME is global. The dynamic LISTS you create are
; always global. Later you use a dynamically created list by binding the
; name to a list. So you don't have to create 1000 names to work with
; 1000 dynamic lists.
GlobalNewDynamicListPointer(Dummy, s) ; Notice that names are typed.

; Fill array with LinkedLists
For I = 0 To #ArrayLen
  ListArray(I) = DynamicNewListS()
Next

; Fill those LinkedLists with some gibberish
For I = 0 To #ArrayLen
  BindListS(Dummy(), ListArray(I))
  For J = 0 To I
    AddElement(Dummy())
    Dummy() = Str(J) + "_"
  Next
Next

BindListS(Dummy(), ListArray(9))
SortList(Dummy(), 1)

; Print each LinkedList. Notice that ForEach can be used
; for the individual lists, but obviously not for the
; array
For I = 0 To #ArrayLen
  Debug "------------ " + Str(I) + " ------------"
  BindListS(Dummy(), ListArray(I))
  ForEach Dummy()
    Debug Dummy()
  Next
Next

kinglestat · Post by **kinglestat** » Fri Nov 03, 2006 6:42 pm

well well
this looks like pure genius
though took me several ideas to understand

question

can I use custom defined types (I mean structures) rather than strings or longs ?

regards

Terence

Trond · Post by **Trond** » Fri Nov 03, 2006 7:12 pm

kinglestat wrote: can I use custom defined types (I mean structures) rather than strings or longs ?

Yes, you can use any types, even structures. Just define the structure before UseListType(StructureName).

I made an example for you (and to properly test it) but the IDE crashed so you'll have to make one yourself. But it works.

Also I found a small problem: The debugger doesn't always catch it if you try to access a freed list. The FreeList*() functions works though.

kinglestat · Post by **kinglestat** » Sat Nov 04, 2006 9:47 pm

thank you!
I'll try it out

Terence

kinglestat · Post by **kinglestat** » Tue Nov 21, 2006 4:52 pm

I've been trying out these in a project but I noticed that I get crashes in strange places

eg

doing these in a procedure

gListArray ( #LLValidation ) = DynamicNewListstLocal ()
gListArray ( #LLTrigger ) = DynamicNewListstLocal ()

will cause program to give error on exit (when run from inside PB)
putting them in the root fixed that problem

but now I am getting other crashes in strange places mostly with DeleteElement() but at times in the eventhandler in
EventID = WaitWindowEvent()

using normal linked lists seem to work fine and without crashes - but obviously I prefer your approach with the ability to attach the list on the fly

I'll try to wrap up a demo to demonstrate the problem but meanwhile maybe you have any ideas ?

cheers

KingLestat

Trond · Post by **Trond** » Tue Nov 21, 2006 4:57 pm

I can't reproduce it, can you post some code that shows the problem?

kinglestat · Post by **kinglestat** » Tue Nov 21, 2006 7:18 pm

I have to admit that I havent managed to replicate the issues on a demo program. I will try to narrow the issue in my own program first and port out that on demo.

cheers

Trond · Post by **Trond** » Tue Nov 21, 2006 9:36 pm

Some tips: If you allocate local lists you must free them sooner or later, and if you create a local list name and bind it to a list, that list will get freed at the end of the procedure.

Dare · Post by **Dare** » Tue Nov 21, 2006 10:38 pm

Missed this - I obviously don't spend enough time on the boards these days!

Thanks Trond.

Konne · Post by **Konne** » Mon Nov 27, 2006 7:22 pm

Dim ListArray.q(#ArrayLen) ; Notice that ListArray is of type .q. It can
; store lists of any type.

Why q? Doesn't the array same a Pointer?

And what are all the If 0 things for?

Konne · Post by **Konne** » Mon Nov 27, 2006 7:39 pm

What am I doing wrong? It crashes if I try to read the Values again.

Code: Select all

Macro GlobalNewDynamicListPointer(Name, Type)
  If 0
    Global NewList Name.Type()
  EndIf
EndMacro

Macro NewDynamicListPointer(Name, Type)
  If 0
    NewList Name.Type()
  EndIf
EndMacro

Macro BindListTemplate(Type)
  Procedure BindList#Type(List.Type(), ID.q)
    !mov eax, [p.v_ID]
    !mov edx, [p.v_ID+4]
    !mov ecx, [p.v_ID-4]
    !mov [ecx], eax
    !add ecx, 4
    !mov [ecx], edx
  EndProcedure
EndMacro

Macro DynamicNewListTemplate(Type)
  Procedure.q DynamicNewList#Type()
    Protected NewList Local.Type()
    !mov eax, [esp]
    !mov edx, [esp+4]
    !add esp, 8
    !ret
  EndProcedure
EndMacro

Macro FreeListTemplate(Type)
  Procedure FreeList#Type(ID.q)
    If 0
      NewList Dummy.Type()
    EndIf
    BindList#Type(Dummy(), ID.q)
  EndProcedure
EndMacro

Macro UseListType(Type)
  BindListTemplate(Type)
  DynamicNewListTemplate(Type)
  FreeListTemplate(Type)
EndMacro


Structure Column
  Column.s
  Type.l
  InitVal.q
EndStructure

Structure Row
  Row.s
EndStructure

Structure List
  Columns.q
  Rows.q
EndStructure

NewList Lists.List()

UseListType(Column)
UseListType(Row)

GlobalNewDynamicListPointer(Columns, Column)
GlobalNewDynamicListPointer(Rows, Row)

For t = 1 To 10
  AddElement(Lists())
  Lists()\Columns=DynamicNewListColumn()
  Lists()\Rows=DynamicNewListRow()
Next

ForEach Lists()
  BindListColumn(Columns(), Lists())
  
  Debug "---"
  List+1
  
  For x = 1 To 5
    AddElement(Columns())
    Columns()\Column="List-"+Str(List)+" Column-"+Str(x)
    Debug Columns()\Column
  Next

Next

Debug "---"
Debug "Try to get the Values"

ForEach lists()
  BindListColumn(Columns(), Lists())
  
  Debug "---"
  
  ForEach Columns()
    Debug Columns()\Column 
  Next
Next

Trond · Post by **Trond** » Mon Nov 27, 2006 8:06 pm

Konne wrote:Why q? Doesn't the array same a Pointer?

A quad is required to store a PB linked list. Why I've got no idea. Ask Fred.

Konne wrote:And what are all the If 0 things for?

If a list is declared inside if 0 it is not actually allocated, but it's still declared, and is freed at the end of the procedure.

I will look at your code.

Trond · Post by **Trond** » Mon Nov 27, 2006 8:12 pm

kinglestat, have you tried to run your faulty program without the debugger? It could complain at certain places where it shouldn't because I'm doing some tricks. Also check if you did the same error as konne.

Konne, you're binding the list name to the an element in the PB linked list instead of the \Columns structure field.

Code: Select all

Structure List
  Columns.q
EndStructure

NewList Lists.List()
AddElement(Lists())
Lists()\Columns = DynamicNewListL()

BindListColumn(Columns(), Lists()) ; Wrong
BindListColumn(Columns(), Lists()\Columns) ; Good

By the way, I'm using this myself without any problems so far.

Konne · Post by **Konne** » Mon Nov 27, 2006 8:26 pm

Ah OK thx

If 0

wouldn't a goto be faster?

kinglestat · Post by **kinglestat** » Tue Nov 28, 2006 2:52 pm

yes I tried without debugger
but in fact the problem was a MID function written in assembly though no idea why it bombs out with the linklists. The MID function was posted somewhere around on the board

sorry for my late reply
cheers

KingLestat