Here's a little somethin I've been using a lot lately.
With the exception of untested BackPointer stuff, it's solid as a rock? :P
If anyone improves / extends this code, please post your version update here for all to use :)


;=====================================================================
;April 14 2005
;EvilHomer proudly presents:
;LinkedList Class for ATC version 3.1
;A general-purpose (naive) heap-object array manager.
;Now supports BackPointers, Insertion and Deletion.
;
;=====================================================================
;
;Two methods are supplied for adding Objects to an instance of LinkedList.
;1) Append
; This method appends an object you allocated with malloc to the end of a LinkedList.
; Use this if you prefer to allocate your own memory, but DO use malloc to do it.
;2) AddNewObject
; This method will malloc a new object of given size and append it for you.
; It will return a pointer to the object, which you can then use to set data in the new object.
;
;Note about destruction / cleanup :
;When you delete the LinkedList instance, it will automatically free any objects it contains.
;This can be handy, but DO note the following:
;It will not clean up or release any data stored within those objects, as it is naive as to exactly
;which kind, or size, of objects it is actually storing.
;There is currently NO support for deletion / insertion of objects.
;=====================================================================
;This structure describes the Nodes stored in the LinkedList
;Each Node contains a ptr to the next Node , and also
;contains a ptr to some object Owned by the Node.
;
;Here is an ascii representation of the Tree topology.
;As you can see, it couldn't be more simple.
;
;Root
;  |
;Node0 --> Object0
;  |
;Node1 --> Object1
;  |
;NodeN --> ObjectN
;  |
;(NULL)
;
;=====================================================================
LinkedNode struct
pLinkFwd      dd ?          ;ptr to the next Node
pLinkBack    dd ?        ;ptr to the previous Node
pObjectData dd ?          ;This Node's ObjectPtr
LinkedNode ends
;=====================================================================

class LinkedList, ,C++ compatible
;Allocate a new Object and Append it to the LinkedList (returns ptr)
void GetFirst                                  ;Fetches the 'first' object in list and presets internal iteration ptr
void GetNext                                  ;Fetches the 'next' object in list and updates internal iteration ptr
void GetPrev                                  ;Fetches the 'previous' object in list, updates internal  iteration ptr
void GetNth:dwIndex                      ;Fetches the 'Nth' object in list
void Append:SomeObjectPointer  ;Append an existing object to the LinkedList
void AddNewObject:dwObjectSize ;Allocates new Object of given Size, Appends, returns pObject

void GetNodeByDataObject:pObject ;Finds container LinkedNode for given Object
void InsertAfter:pObjectParent, pObjectNew ;Insert an Object after a given Object in the List
void DeleteObject:pObjectToDelete  ;Deletes an arbitrary object from the List

long pFirstNode          ;A quick, handy link to the First Node in the chain
long pLastNode          ;A quick, handy link to the Last Node in the chain
long pCurrentNode    ;An iteration pointer for walking the Nodes (see GetFirst/GetNext)
long NumNodes
endclass

;=====================================================================

LinkedList_LinkedList proc
ret
LinkedList_LinkedList endp

LinkedList_Append proc pObjectData
local pnode
inc .LinkedList.NumNodes                  ;We can increment our counter now, its ok
mov pnode, malloc(sizeof LinkedNode)      ;Allocate a new LinkedNode struct
m2m .LinkedNode.pObjectData, pObjectData ;Store ptr to payload Object in Node
.if .LinkedList.pFirstNode==0              ;If there's no First Node in the List
    mov .LinkedList.pFirstNode, eax        ;then this will be the First Node
.else                                                            ;else if there's already a First Node
    mov ebx, .LinkedList.pLastNode        ;fetch the Last Node
    mov .LinkedNode.pLinkFwd,eax        ;point fwd from old lastnode to new node
    mov .LinkedNode.pLinkBack, ebx    ;point back from new node to old lastnode
.endif
mov .LinkedList.pLastNode,eax            ;We just made a new Last Node
ret
LinkedList_Append endp

LinkedList_$LinkedList proc
local me
mov me,ecx
mov ecx,.LinkedList.pFirstNode
.while ecx!=0
    .if .LinkedNode.pObjectData!=0                        ;If this node has Object data
        free  .LinkedNode.pObjectData              ;Free the Object data (we hope)
    .endif
    push .LinkedNode.pLinkFwd                      ;preserve address of next node
    free ecx                                                          ;destroy this node
    pop ecx                                                              ;restore address of next node
.endw
ret
LinkedList_$LinkedList endp

LinkedList_GetFirst proc 
    mov eax, .LinkedList.pFirstNode          ;<-- Starting with the FIRST node   
    .if eax!=0  ;<-- check for NULL first node (no content in LL)
        mov .LinkedList.pCurrentNode, eax      ;<-- Set up the current node
        mov eax,.LinkedNode.pObjectData              ;<-- Return the node's Object ptr
    .endif
    ret
LinkedList_GetFirst endp

LinkedList_GetNth proc dwIndex
    mov eax, .LinkedList.pFirstNode          ;<-- Starting with the FIRST node 
    .while dwIndex!=0 && eax!=0
        mov eax,.LinkedNode.pLinkFwd
        dec dwIndex
    .endw
    .if eax!=0
        mov eax,.LinkedNode.pObjectData   
    .endif
    ret
LinkedList_GetNth endp

LinkedList_GetNext proc
    mov eax, .LinkedList.pCurrentNode      ;<-- Starting with the current node
    .if eax!=0
        mov eax, .LinkedNode.pLinkFwd          ;<-- Increment the current node
        mov .LinkedList.pCurrentNode,eax        ;<-- Set up the incremented current node
        .if eax!=0
            mov eax,.LinkedNode.pObjectData              ;<-- Return the node's Object ptr
        .endif
    .endif
    ret
LinkedList_GetNext endp

LinkedList_GetPrev proc
    mov eax, .LinkedList.pCurrentNode      ;<-- Starting with the current node
    .if eax!=0
        mov eax, .LinkedNode.pLinkBack          ;<-- Decrement the current node
        mov .LinkedList.pCurrentNode,eax        ;<-- Set up the incremented current node
        .if eax!=0
            mov eax,.LinkedNode.pObjectData              ;<-- Return the node's Object ptr
        .endif
    .endif
    ret
LinkedList_GetPrev endp

LinkedList_AddNewObject proc dwObjectSize
    push malloc (dwObjectSize)
    icall ecx, LinkedList, Append, eax
    .if eax==0
        pop eax
        Message "LinkedList_AddNewObject : malloc failed !!!"
    .endif
    pop eax
    ret
LinkedList_AddNewObject endp

LinkedList_GetNodeByDataObject proc pObject
.if pObject==0
    return NULL
.endif
.if .LinkedList.pFirstNode==0
    return NULL
.endif
mov eax, .LinkedList.pFirstNode
mov ebx,pObject
.while eax!=0
    .if .LinkedNode.pObjectData==ebx
        ret
    .endif
    mov eax,.LinkedNode.pLinkFwd
.endw
ret
LinkedList_GetNodeByDataObject endp

LinkedList_InsertAfter proc pObjectParent, pObjectNew
local pnode
.if pObjectParent==0
    ret
.endif
inc .LinkedList.NumNodes                  ;We can increment our counter now, its ok
mov pnode, malloc(sizeof LinkedNode)      ;Allocate a new LinkedNode struct
m2m .LinkedNode.pObjectData, pObjectNew;Store ptr to payload Object in Node

; Try to find the LinkedNode which owns the object we wish to insert behind.
; If this returns NULL, then pObjectParent isn't stored in the List
; Otherwise it returns a ptr to the LinkedNode containing pObjectParent
; which we want to manipulate.

icall ecx, LinkedList, GetNodeByDataObject, pObjectParent
.if eax!=0                                              ;eax=Parent
    mov ebx,pnode                                ;ebx=This
    push  .LinkedNode.pLinkFwd  ;pushed old Child
    m2m .LinkedNode.pLinkFwd,pnode ;link Parent forward to This
    mov .LinkedNode.pLinkBack,eax    ;link This back to Parent
    pop eax
    .if eax!=0                                                    ;If there was an old Child
        mov .LinkedNode.pLinkBack,ebx  ;link old Child back to This
    .endif
    .if eax== .LinkedList.pLastNode            ;If the old Child was the Last Node
        m2m  .LinkedList.pLastNode, pnode      ;make This the new Last Node
    .endif
    inc .LinkedList.NumNodes
.endif
ret
LinkedList_InsertAfter endp

LinkedList_DeleteObject proc pObject
.if pObject==0
    ret
.endif

; Fetch the LinkedNode containing pObject
icall ecx, LinkedList, GetNodeByDataObject, pObject
.if eax==0
    ret
.endif

dec .LinkedList.NumNodes

; If we are deleting First Node, make the Next node be First node
.if eax==.LinkedList.pFirstNode
    m2m .LinkedList.pFirstNode, .LinkedNode.pLinkFwd
.endif

; If we are deleting Current Node, make the Next node be Current node
.if eax==.LinkedList.pCurrentNode
    m2m .LinkedList.pCurrentNode, .LinkedNode.pLinkFwd
.endif

; If we are deleting Last Node, the Last node is NULL
.if eax==.LinkedList.pLastNode
    mov .LinkedList.pLastNode,0
.endif

; If This node had a Parent, patch the Parent's link
.if .LinkedNode.pLinkBack!=0
    mov ebx,  .LinkedNode.pLinkBack
    m2m .LinkedNode.pLinkFwd,  .LinkedNode.pLinkFwd
.endif

; If This node had a Child, patch the Child's link
.if .LinkedNode.pLinkFwd!=0
    mov ebx, .LinkedNode.pLinkFwd
    m2m .LinkedNode.pLinkBack,  .LinkedNode.pLinkBack
.endif

; Free pObject and its Node container
push eax
free pObject
pop eax
free eax

ret
LinkedList_DeleteObject  endp



Posted on 2005-04-12 23:50:38 by Homer
Nice work. I suggest adding forward and backward iterators. Take a look at the OA32 Collection object.
It is one of the most important objects!

Object Collection, CollectionID, Streamable
? StaticMethod? ? ? Delete,? ? ? ? ?Pointer? ? ? ? ? ? ? ?;-> Item
? StaticMethod? ? ? DeleteAt,? ? ? ?dword? ? ? ? ? ? ? ? ?;Index in range [0..Count-1]
? StaticMethod? ? ? DeleteAll
? DynamicMethod? ? ?DestroyItem,? ? Pointer? ? ? ? ? ? ? ?;Override for data structures
? StaticMethod? ? ? Dispose,? ? ? ? Pointer? ? ? ? ? ? ? ?;-> Item
? StaticMethod? ? ? DisposeAt,? ? ? dword? ? ? ? ? ? ? ? ?;Index in range [0..Count-1]
? StaticMethod? ? ? DisposeAll
? RedefineMethod? ? Done
? StaticMethod? ? ? FirstThat,? ? ? Pointer, Pointer? ? ? ;-> Proc, -> Parameter
? StaticMethod? ? ? ForEach,? ? ? ? Pointer, Pointer? ? ? ;-> Proc, ->Parameter
? StaticMethod? ? ? ForEachRev,? ? ?Pointer, Pointer? ? ? ;ForEach in reverse order
? DynamicMethod? ? ?GetItem,? ? ? ? Pointer? ? ? ? ? ? ? ?;-> Stream
? StaticMethod? ? ? IndexOf,? ? ? ? Pointer? ? ? ? ? ? ? ?;-> Item
? RedefineMethod? ? Init,? ? ? ? ? ?Pointer, dword, dword, dword ;-> Owner, Cnt, Inc, Lim
? StaticMethod? ? ? Insert,? ? ? ? ?Pointer? ? ? ? ? ? ? ?;-> Item
? StaticMethod? ? ? InsertAt,? ? ? ?dword, Pointer? ? ? ? ;Index, -> Item
? StaticMethod? ? ? ItemAt,? ? ? ? ?dword? ? ? ? ? ? ? ? ?;Index in range [0..Count-1]
? StaticMethod? ? ? LastThat,? ? ? ?Pointer, Pointer? ? ? ;-> Proc, -> Parameter
? RedefineMethod? ? Load,? ? ? ? ? ?Pointer, Pointer? ? ? ;-> Stream, -> Owner
? StaticMethod? ? ? PutAt,? ? ? ? ? dword, Pointer? ? ? ? ;Index, -> Item
? DynamicMethod? ? ?PutItem,? ? ? ? Pointer, Pointer? ? ? ;-> Stream, -> Item
? PrivateMethod? ? ?SetLimit,? ? ? ?dword? ? ? ? ? ? ? ? ?;Sets new limit (internal method)
? StaticMethod? ? ? Shrink
? RedefineMethod? ? Store,? ? ? ? ? Pointer? ? ? ? ? ? ? ?;-> Stream

? DefineVariable? ? pItems,? ? ? ? ?Pointer,? ? NULL
? DefineVariable? ? dCount,? ? ? ? ?dword,? ? ? 0
? DefineVariable? ? dLimit,? ? ? ? ?dword,? ? ? 0
? DefineVariable? ? dDelta,? ? ? ? ?dword,? ? ? 0
? DefineVariable? ? dMaxSize,? ? ? ?dword,? ? ? 0
ObjectEnd


Regards,

Biterider
Posted on 2005-04-13 00:43:54 by Biterider
I respect that, I really do.
I reposted the code with such support methods.
The code hasn't been tested, but looked ok at a glance.
All existing methods were modified to support backpointers.
New methods were added which exploit backpointers.
I'd call my GetNodeByDataObject a private method and let the users deal just with their own objects and not need to know about LinkedNodes.
I've not needed to insert/delete arbitrarily for a while now, but anyways.. yes very, VERY useful to have an object list / array manager of some kind, and I've been playing with plenty lately :)

What's with the Limiting of the element count? Are you storing a flat array of pointers rather than linked nodes and thus are limited by hard page size?

Posted on 2005-04-13 11:46:11 by Homer
Hi EvilHomer2k

The use of iterators makes the live easier and depending on the specific problem to solve, a linked list can be faster than a Collection or not.

The Collection approach uses the Borland strategy. Basically it is an expandable array of pointers that points to objects or memory structures. The Collection object handles it items as objects, that means that they are destroyed (the destructor is invoked and the object is freed from memory) when disposed. On the other side, the DataCollection handles it items as memory chunks. When they are disposed, they are simply removed from memory.

The Collection object are initialized with some parameters that are specific for the pointer array; the initial size, the grow factor and the max size. Usually, the last parameter is set to a very big number (COLLECTIONMAXSIZE) that can never be reached, but you can set it to a specific number to keep things under control. If this limit is reached an error condition is triggered and passed to the owner of the collection to handle it.

As said before, for some tasks, a linked list can be easier and faster than a collection but for a width use of it, iterators will be a nice thing. Considder to pass an auxiliary parameter to the iteration procedure!  8)

Regards,

Biterider
Posted on 2005-04-14 01:56:18 by Biterider
In my object base (\masm32\ultrano\bank\base.inc , provided with Ilix) , there are the ObjVector, HookVector and VarVector already, with iterations done easily:


foreach FocusedWorkspace, invoke ShowWindow,EDX,SW_HIDE
(this one actually hides all windows, listed in the FocusedWorkspace vector)

(some advanced)
; delete all windows from pSrc, insert them in pDest
foreach pSrcWorkspace,multi icall pSrcWorkspace,ObjVector,delete,EDX | icall pDest,ObjVector,insert,EDX

.ForEach pWorkspaces
mov pCurWorkspace,EDX
.if FindInObjVector(pCurWorkspace,hWnd)
m2m pWorkspace,pCurWorkspace
.endif
.EndForEach pWorkspaces

; show absolutely all windows
foreach pWorkspaces, multi mov CurWorkspace,edx | foreach CurWorkspace,invoke ShowWindow,edx, SW_SHOW


Reminds me a bit of Perl's regular expressions, but at least it's readable once you know how to use these objects and macros.
The only "bad" thing about these is that they're thread-safe, which if you code a single-threaded app, is a few useless instructions in extra. But for multithreading it's perfect :)
If you're interested, I can send you the macros and objects (their latest version, two days ago)
Posted on 2005-04-14 14:02:28 by Ultrano
Certainly interested in the macros.
Didn't that stuff use arrays of static pointers, Ultrano?
I like linkedlists because we don't need to decide on a page size, a number of pages, etc.

Ultrano's SmallAlloc codebase used a system of linked page structs, converging both the speed of linear lookups with the flexibility of linkedlists.
It's limitation was that it has to allocate at least one page for each objecttype (in terms of struct size) - so it is potentially quite wasteful.

Linear arrays don't cope well with arbitrary insertions and deletions, and searching for "holes" in arrays is messy.

My LinkedList class provides the ability to create chains of objects which may not necessarily be the same object type - elements are naive pointers.
It's not a total solution to memory management by a long shot, but a useful "utility" class apon which more complex classes can be built.
At least that's how I use it..



Posted on 2005-04-17 06:22:40 by Homer
http://www.ultrano.com/ilix/UltraVector.zip

base.lib contains all my global oop objects and helper functions
ultrabase.lib is just for compatibility when linking the above lib with a project that doesn't know what ATC is (asm or C/C++)
vectors.asm is just the source of the vectors - to see how they work. This code is already compiled and included in base.lib
base.inc - the only file I ever need to include when starting a new project
class.inc - the current ATC

Vectors here take 1kB "pages".
Assume we have 5 elements in a vector (element #0...4).
When we delete #2,  then #3 and #4 are shifted left to the beginning of the array.

There is no universal approach to managing dynamic arrays of objects, when we take speed and extra-memory usage into account. Thus, the programmer needs to choose which existing approach to use, or create a specific one for his current needs. Here I just give another option - already existing and well-tested - to eventually save you time.
When managing objects in my multithreaded apps, my first choice is ObjVector. HookVector I already introduced some time ago - but just lately I've started using it a lot - and it's literally saving me hundreds of lines of boring code, while maintaining app safety (because of the multithreading).

SmallAlloc is definitely not wasteful when you use it the way it was meant to be used . Allocating strings and the like with it is a no-no, as I accented on in the readme.txt for it.

But anyway, it's up to the programmer to choose what functions to use.
Posted on 2005-04-17 11:43:39 by Ultrano
Regarding threadsafe arrays:

I've added a locking mechanism to LinkedList (it uses CriticalSection), but I've implemented it using a compiletime switch so you can build with or without the locking mechanism.
This may or may not suit you depending on the implementation.

Bah, who am I kidding? I'll be the only one to ever use this stuff :|
Posted on 2005-05-05 13:06:03 by Homer

Bah, who am I kidding? I'll be the only one to ever use this stuff :|

Welcome to the club :| (though I've said this a million times already). Today I remembered all my projects ended up like that - with me being the only user. Only ATC is an exception - with whole two users lol. Thus I'm no longer eager to make that 3D engine for PC - I'm much better off using my code alone and selling it, instead of trying to help others sell products that use my code. Then showing what can be done with asm can inspire coders here.. it's my only hope of helping/sharing now :/ . I think I managed to move some people with the "Dreamer" software. Perhaps if they see Dreamer2 that uses all code that I've published here, I'll manage to contribute more... leading to the creation of more fast and great asm-coded apps.
Posted on 2005-05-05 13:50:25 by Ultrano
Also, I'm not sure - but since September 2004 till now there has been a major drop in the productivity of many many people, teams and companies. Maybe it's just that my expectations went high.
Gotten used to the all good and new content that came up often, when Sept. or Oct. came , it was as unpleasant for me as if I no longer had internet.
Posted on 2005-05-05 14:10:06 by Ultrano
Ah, on the thread-safe matter: Why don't you use the following macros of mine for locking. I've been using them for a lot of time now - they are both faster, safer and smaller (require only 2 bytes, not a whole criticalsection)

iTryLockObject macro
local _again,_bad,_good
_again:
xor eax,eax
cmp .isdead,0
jne _bad
mov al,1
xchg .locked,al
or al,al
jz _good
pushad
invoke SwitchToThread ; may change it with 'Sleep,0'
popad
jmp _again
  _good:mov eax,1
  _bad:
endm


iTryLockObjectFast macro ; 0 = object is DEAD 
local _bad ; 1 = WE locked the object , it's OK now to work with it    <=== use ".if eax==1"
xor eax,eax ; 2 = the object is already locked by another proc
cmp .isdead,0
jne _bad
mov al,1
xchg .locked,al
inc al
  _bad:
endm

iUnlockObject macro
push eax
xor al,al
xchg .locked,al
pop eax
endm

iKillObject macro
push eax
mov al,1
xchg .isdead,al
pop eax
endm





iTryLockObject2 macro LockedElement:REQ
local _again,_bad,_good
_again:
xor eax,eax
cmp .isdead,0
jne _bad
mov al,1
xchg .LockedElement,al
or al,al
jz _good
pushad
invoke SwitchToThread ; may change it with 'Sleep,0'
popad
jmp _again
  _good:mov eax,1
  _bad:
endm

iUnlockObject2 macro LockedElement:REQ
push eax
xor al,al
xchg .LockedElement,al
pop eax
endm



The code to use them is like:

myobj struct
  isdead db ?
  islocked db ?
;.... now put the struct members you want to lock here
myobj ends


assume ecx:ptr myobj
mov ecx,pSomeObject1
iTryLockObject
.if eax ; if this object is alive
    ; do stuff with it
    ;....

    ; finally, unlock it
    mov ecx,pSomeObject1
    iUnlockObject
.endif

assume ecx:nothing




Posted on 2005-05-05 14:20:45 by Ultrano
Simple is an understatement.
That's cross-thread safe, but not cross-process safe.
Still, I like it :)

Actually, I'm just depressed that my favorite machine has self-destructed.
I'm sitting here on a 333 looking at motherboard prices.
A dual would be nice :)
Posted on 2005-05-06 09:22:34 by Homer