Managing data structures: lists

[NoCforMe]

A current project of mine is going to need some list management. This is something I've done before, but it's always something of a pain; I end up doing a lot of scribbling with pencil and paper before figuring it out.

The data structure is super-simple: it's just a list (a linear list, not linked) of structures:

Code Select Expand

$TL STRUCT
  dispTxtPtr DD ?
  insertTxtPtr DD ?
  tlType DD ?
$TL ENDS
This defines a "tool list" for my editor. The list is constructed by reading an initialization file and writing structure elements to a list in heap memory. So far, so good.

Thing is, I want to be able to manipulate this list: insert new elements between existing ones, or at the head or tail; move elements up or down and delete elements. This will be accomplished in code by setting source and destination pointers and doing block moves (REP MOVSx comes in real handy here).

I'll be able to do this after a lot of head-scratching and drawing boxes on paper. But I'm thinking, maybe this is a case where it would be nice to have a library that could take care of these operations. I'm sure it could be done as a general-purpose tool, where elements of any size could be moved around.

Well, something to think about. Maybe I'll start on that.

[sinsi]

I usually use 2 memory blocks, one for the 'objects' themselves, and one for a list of addresses to them.
That way, you manipulate the address list, which works no matter the object size.
By growing the address list memory you can increase the number of 'slots' for objects.

[jj2007]

it's just a list (a linear list, not linked) of structures

On lists:

In many programming languages like Python, this data structure is commonly known as an array.

Why not a simple array? What can you do with a list that you can't do with an array (and vice versa)?

[HSE]

Well, something to think about. Maybe I'll start on that.

   Don't think too much, is just an array.

You can work with pointers or just an index.

[NoCforMe]

OK, this morning at breakfast I sketched out the beginnings of my scheme.

I'll call the whole package LMlib (for "list management").

Master structure:

Code Select Expand

LMINFO    STRUC
  structSize    DD ?        ;In case a new version comes along at some point ...
  baseAddr    DD ?          ;Addr. of allocated list.
  elementSize    DD ?
  numElements    DD ?
  maxElements    DD ?       ;For checking for overflow
LMINFO    ENDS
Functions:

• LMinit():    initializes everything, allocates memory for list
• LMnew():    adds a new element at the end of the list
• LMinsert():    inserts a new element @ [index]
• LMdelete():    deletes an element
• LMmove():    moves an element to a new location
• LMdealloc():    deallocates list memory

Example usage:

Code Select Expand

    MOV    LMI.structSize, SIZEOF LMINFO
    MOV    LMI.elementSize, <element size>
    MOV    LMI.maxElements, <max. # elements>
    INVOKE    LMinit, ADDR LMI

    INVOKE    LMinsert, ADDR LMI, ADDR <new element>, index

    INVOKE    LMmove, ADDR LMI, ADDR <element to move>, index

I suppose LMnew() could just be considered a special case of LMinsert(), where index is at the end of the list.

[NoCforMe]

it's just a list (a linear list, not linked) of structures

On lists:

In many programming languages like Python, this data structure is commonly known as an array.

Why not a simple array? What can you do with a list that you can't do with an array (and vice versa)?

Terminology alert:
Let's not get bogged down here in semantics. When I say "a list", I mean a simple, non-linked list, i.e., an array. Same damn thing.

[HSE]

It's a dynamic list  You have to save and to retrieve that from a file.

[jj2007]

maybe this is a case where it would be nice to have a library that could take care of these operations

Absolutely - see Dim, Insert and Delete

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc
  Init
  Cls 3
  Dim rc() As RECT    ; whatever: DWORD, BYTE, REAL8, WNDCLASSEX, ...
  For_ ecx=0 To 9
    mov rc(ecx, left), ecx
    mov rc(ecx, top), Rand(100)
    mov rc(ecx, right), Rand(100)
    mov rc(ecx, bottom), Rand(100)
  Next
  m2m ecx, 5
  Insert rc(ecx)
  lea eax, [ecx+100]
  mov rc(ecx, left), eax    ; 105
  mov rc(ecx, top), Rand(100)
  mov rc(ecx, right), Rand(100)
  mov rc(ecx, bottom), Rand(100)
  Delete rc(7)
  PrintLine " left    top  right bottom"
  For_ ecx=0 To rc(?)-1
    Print Str$("%____i  ", rc(ecx, left)), Str$("%____i  ", rc(ecx, top))
    Print Str$("%____i  ", rc(ecx, right)), Str$("%____i\n", rc(ecx, bottom))
  Next
  MsgBox 0, "Arrays, yeah!!", "Hi", MB_OK
EndOfCode
Output:

Code Select Expand

left    top  right bottom
    0     28     25     40
    1     12     79     24
    2     71     57     93
    3     46     63     43
    4     51     77     28
  105      3     61     25
    5     18     40     37
    7     35     23     44
    8     45     94      2
    9      8     96     21

When I say "a list", I mean ... an array

Thanks for clarifying that

[NoCforMe]

maybe this is a case where it would be nice to have a library that could take care of these operations

Absolutely - see Dim, Insert and Delete

I. Don't. Use. MasmBasic.

[NoCforMe]

It's a dynamic list  You have to save and to retrieve that from a file.

????? Please explain; I don't understand.

Yes, it's a dynamic list, constructed from reading an .ini file. So what?

To me, a list is a list. (Not a linked list; that's a different critter.)

[jj2007]

I. Don't. Use. MasmBasic.

That's courageous

There are the DSA_* functions, but they have two problems:
a) they are clumsier and less powerful than Dim, Insert & Delete
b) it's an external library, so you'll have to deal with Bill Gates instead of me ;-)

[NoCforMe]

Which is why I'll be rolling my own if I go ahead with this project. My own code I can trust.

[TimoVJL]

I. Don't. Use. MasmBasic.

That's courageous

There are the DSA_* functions, but they have two problems:
a) they are clumsier and less powerful than Dim, Insert & Delete
b) it's an external library, so you'll have to deal with Bill Gates instead of me ;-)

DSA comes from Win OS, and have been there quite long, since NT born.
Dynamic Structure Arrays

[jj2007]

DSA comes from Win OS

Yes indeed, and maybe I would have used DSA_* instead of rolling my own array stuff (Dim, Insert, Delete, Erase, Swap) if I had known them 15 years ago. Strangely enough, they have never been used in this forum, except for two posts by Edgar alias Donkey in 2008 and 2011.

The point here is the artificial distinction between "built-in" and "third party". Yes, DSA_* is "built-in", and yes, MasmBasic is "third party", but so is the Masm32 library that almost all the forum members (well, those who do code...) use every day.

"Third party" is a bad word if it means "buggy and/or bloated and/or not maintained". What comes to my mind here are behemoths like QT. Or, to stay within the "built-in" category, the RichEdit control.

Would David refuse to work with the Masm32 library? Reinvent the wheel for things like print str$(eax)? Then I would congratulate him for his courage.

Posting "it would be nice to have a library" and, when shown that such a library exists already, responding in fat letters "I. Don't. Use. MasmBasic." is a bit ridiculous. I wish him luck rolling his own. It's years of hard work programming that stuff in Assembly. I'll watch his progress with great amusement.

[NoCforMe]

The point here is the artificial distinction between "built-in" and "third party". Yes, DSA_* is "built-in", and yes, MasmBasic is "third party", but so is the Masm32 library that almost all the forum members (well, those who do code...) use every day.

Would David refuse to work with the Masm32 library? Reinvent the wheel for things like print str$(eax)? Then I would congratulate him for his courage.

Welll, regarding the Masm32 library, the only function I've ever used from that is the one that extracts "command-line" arguments (GetCL()). I do roll my own for everything else. (Remember my motto: "Assembly language should be fun!")

Now obviously I'm not a production programmer; if I was I'd certainly be using more "external" libraries, perhaps even ones from MasmBasic. But I'm not, and I actually prefer my own home-grown code where it's possible. (If it comes to complex stuff like, say, dealing with JPGs, then I certainly look for existing codebases.)

For things like your example, print str$(eax), I find that wsprintf() takes care of all my needs.