I was wondering, how would you classify/differentiate a linked list. I need help on this one. The attached program is an attempt to recreate that aspect of the HLL. Please check if my program meets that criteria of a linked list.

If not? Tell me what's the criteria...(I have already done linked lists in HLL but never in ASM.)

I searched all search engines, newgroups and found none that pinpoints of creating linked lists in assembly.

In addition, Thomas, who was looking for something that he can mimic the forward and back button of browsers. I think this might be the answer.

I'm nearly finished with my doubly linked list. Im still unsure if i did the right thing(met the criteria).

Thanks!!!

By the way this is my 100th posts !!! yay !!! :grin:
Posted on 2002-01-24 16:05:49 by stryker
I think what thomas needed was to make IE go forward/backward
(as if you pressed the buttons), not create forward/back functionality
in his app. But I might be wrong.
Posted on 2002-01-24 16:27:43 by f0dder
I understood like you, f0dder... btw... umberg, it is a very nice example... I was considering implementing something like that in one of my programs so I will definitely have a look at it. ;)

Thanks !
Posted on 2002-01-24 16:44:14 by JCP
Actually, I think this is a dynamic structure array. Linked list is suppose to point the next/previous structure...I'll release a fix soon, in a few days.

Fodder/Readiosys you are right, I didn't actually read the whole post by Thomas. My apologies :grin:

I'm in the middle of a class...logging off
:)
Posted on 2002-01-24 22:13:23 by stryker
Offtopic: umberg, where in O.C. you live? I live in Tustin Ranch...




Thanks,
_Shawn
Posted on 2002-01-25 03:03:06 by _Shawn
Its old, very old, I wrote it back when I was even worse at assembly than I am now!

Mirno
Posted on 2002-01-25 05:07:28 by Mirno
Me, I live in Laguna Hills...

Mirno, this is so cool.... I've been looking for months but never found one...I searched newsgroups, searched all search engines with all the possible search terms and found none...Anyway I'll check the source code and see what I can improve...Maybe I can make it into doubly circular linked list...

As for me saying that it's a dynamic structure array, im pretty sure it is. Because the next/prev pointers are not actually pointers to memory addresses but an index of the dynamic structure...

Oops gotta do some homework...I'll post some code in a few days... :grin:

Thanks for the help!
Posted on 2002-01-25 12:04:50 by stryker
The attachment here is now a full fledge working example of a doubly linked list. No more dynamic array of structures.

Next: Singly Circular and Doubly Circular Linked Lists.

Tell me if you have questions!!!

Have Fun!!! :grin:
Posted on 2002-01-25 20:44:43 by stryker
Ok! I screwed up on this one...but it's just a minor glitch... When you don't enter anything and then you close the application, it's going to give you an error...Why, because it's going to deallocate memory without having to create that part of memory first. Meaning, it's deallocating a NULL value.

Here's the code to make that up for:



@@MSGClose:

mov edx, RootNode

@@:
cmp edx, NULL
je @f
push (URLList ptr [edx]).ptNext
invoke HeapFree, ptProcessHeap, NULL, edx
pop edx
jmp @b

@@:

invoke EndDialog, hWnd,NULL
jmp @@DlgProcRetTrue


If you want to see, how many nodes it has deallocated...



@@MSGClose:

mov edx, RootNode
xor ecx, ecx

@@:
cmp edx, NULL
je @f
push (URLList ptr [edx]).ptNext
inc ecx
push ecx
invoke HeapFree, ptProcessHeap, NULL, edx
pop ecx
pop edx
jmp @b

@@:

invoke SetDlgItemInt, hWnd, IDE_INPUTSTATUS, ecx, FALSE
invoke MessageBox, 0, 0, 0, 0

invoke EndDialog, hWnd,NULL
jmp @@DlgProcRetTrue


The output will be on the first input status box. The messagebox there prevents the window from closing, so that you can see the number of nodes deallocated...

Again, my apologies for the bug :grin:
Posted on 2002-01-25 21:31:32 by stryker
Ok it took me a long time to update this one(very busy with school :grin: ). This is a doubly circular linked list. Not much of a difference from the doubly linked list but in here there is no end to the list, it just keeps running in circles.
If you already know how doubly linked list works there is not much of a problem if you want a singly or singly circular linked list.

Happy Coding :grin:

Next: Deleting and Inserting from a list.
Posted on 2002-02-05 23:56:59 by stryker
nice example! And here a bunch of questions:

I took a short look at your code, so if I looked right, you alloc a new entry with HeapAlloc. Why dont you free it with HeapFree on Clear?

And is this way proper for a large and often changing list? I'm using large memory lists (not linked) with about 10-10000 entries, one entry about 10 DWORDs. The list has many changes during "lifetime". I afraid a linked and allocated list will lead to memory fragmentation.

(and by the way : what do the double @ signs in front of your labels? Is it some kind of MASM functionality?)
Posted on 2002-02-06 03:52:06 by beaster

(and by the way : what do the double @ signs in front of your labels? Is it some kind of MASM functionality?)
The double @ signs allow you to jump without creating an explicit label name:
@@:mov al,[esi]

inc esi
dec al
jne @B ; this means jump [b]B[/b]ack to previous @@
js @F ; this means jump [b]F[/b]orward to next @@
mov [edi],al
inc edi
jmp @B
@@:ret
Posted on 2002-02-06 10:00:33 by bitRAKE
I took a short look at your code, so if I looked right, you alloc a new entry with HeapAlloc. Why dont you free it with HeapFree on Clear?

You don't need to free it everytime because if you do you'll lose the data. The concept of linked list is that it has to "linked" those data even if the memory is allocated elsewhere.

E.G. (Doubly Linked List)

First Allocation: (RootNode)
-> Allocate Memory. Memory Allocated at E
-> E.ptNext = NULL ,,, E.ptPrev = NULL

Second Allocation:
-> Allocate Memory. Memory Allocated at X
-> X.ptNext = NULL ,,, X.ptPrev = E
-> E.ptNext = X

Third Allocation:
-> Allocate Memory. Memory Allocated at A
-> A.ptNext = NULL ,,, A.ptPrev = X
-> X.ptNext = A

Fourth Allocation:
-> Allocate Memory. Memory Allocated at M
-> M.ptNext = NULL ,,, M.ptPrev = A
-> A.ptNext = M

If I free the memory of the previous one, then there is no link created and the data is lost. The only time you'll ever going to free it is when you don't need it anymore(close the application). You can see the HeapFree code at the @@MSGClose label.

And is this way proper for a large and often changing list? I'm using large memory lists (not linked) with about 10-10000 entries, one entry about 10 DWORDs. The list has many changes during "lifetime". I afraid a linked and allocated list will lead to memory fragmentation.


I'm not sure, I haven't tested this one on a very large list :grin: I read the platform sdk and it says:

Memory allocated by HeapAlloc is not movable. Since the memory is not movable, it is possible for the heap to become fragmented.

I'm a little bit worried but maybe you can change it to GlobalAlloc since platform sdk didn't said anything about fragmentation of this API.

As for the fact that it allocates just anywhere in memory, that's how linked list works...If you have a very large linked list, it'll look like a spaghetti in memory(that one points to that one...check the sample pseudo code above - if we have a memory from a - z, just looks how it goes backwards and forwards...)

I hope I answered your question.

As for the @@LabelName, I was coding in TASM before, @@LabelName is local labels in TASM, maybe I was thinking I'm still coding in TASM he! he! he! :grin: You can see the @@, @f, @b at the @@MSGClose label, I also did it for a bit of clarity.
Posted on 2002-02-06 10:29:29 by stryker
Our Object Model has a defined linked list class and a link class. They are used in the 3pic example on my web-page (if you want to check them out).

We have a double linked list class as well, but its not publically released. (We are using it in the "object creator" that were building... if your interested, i could clean up the class and release it too )

NaN
Posted on 2002-02-06 11:38:06 by NaN
under win32, LocalAlloc and GlobalAlloc both use HeapAlloc internally.
They do some checks and parameter conversion, and then hop off
to HeapAlloc. So no difference there.

To avoid memory fragmentation, you can allocate "pools" of nodes,
but this requires a good deal of extra management code if you still
want the flexibility of linked lists.

Other allocation strategies involve dynamic arrays aka delta arrays,
where you use HeapAlloc/HeapRealloc, and resize the array in chunks
instead of single entries. Because of the realloc, this can leave
*large* holes in the heap...

It all comes down to your specific needs. I haven't found a method
yet that works well everywhere. Linked lists are nice beacuse they
are simple to implement and work with, but they have disadvantages
of nonlinear access, fragmentation, etc.
Posted on 2002-02-06 11:39:25 by f0dder
Nice, NaN :alright: sounds like fun in the OOP scene

I didn't knew that LocalAlloc and GlobalAlloc uses HeapAlloc internally, thanks for the info.
Posted on 2002-02-06 11:55:07 by stryker
f0dder,

One of our 'work in progress' areas on the OOP model is better management of the heap. We are thinking of making "pools" of heap area and managing them for instance creation. But this *is* alooooot of work. And almost certainly not solely within the bounds of macro code :)

If you have any ideas from your experiences how one might speed up the object creation/destruction process in the heap, i would definetly like to hear what you got to say.

Real problem is objects are "random" in instance sizes from class to class. As well there is no fixed assumptions of how many instances an application may generate....

Oh well, i have a strong feeling this will be a long to solve...

NaN
Posted on 2002-02-06 12:02:20 by NaN
HeapAlloc / HeapFree not good enough for the object creation/destruction?
Do you need to keep lists of the objects? Do you need to automatically
call destructors? If you don't have any "special" needs, HeapAlloc/Free
shoudl be just fine. You might want to consider creating a new heap
instead of using the default process heap though. Haven't yet
looked at how multiple heaps are positioned in the address space,
but I think it should work fairly well.
Posted on 2002-02-06 12:09:41 by f0dder
Oh it does... Im quite happy with its dynamic response... but i have seen it "chug" a bit with massive linked lists being built. I attributed this to individually allocating each link via API (as Betov point out to me a while ago :) )

The thought that if i were to somehow manage one *big* allocation, this would speed things up.... but im sure its far from the best solution...

NaN
Posted on 2002-02-06 12:14:35 by NaN
Question is, is this because Heap* are slow, or because your linked
list routines are slow? Try allocating one *large* chunk of memory
(enough to hold all the alloc requests you'll need). Use VirtualAlloc
for this. Then write a simple "dummy" allocation routine that just
returns an offset within this chunk, and increases "next available"
block. Don't bother writing a free. Time this against Heap* functions.
Would be interesting to see the results... I don't much like the thought
of managing your own heap inside the process heap, but if the
Heap* functions *are* slow... oh well, have to do testing I guess ;)
Posted on 2002-02-06 12:31:27 by f0dder