linked list

[ghjjkl]

i'm trying to implement linked list in asm. Here's my removing node code:

Code Select Expand



;mem_free - to deallocate memory
;pNode - node to be removed
node struc

previous dw 0
next dw 0
_data_ dw 0

node ends


(...)

r_node proc near c pNode:word

.if pNode==0

jmp exit

.endif

push ds

push pNode
pop ds

.if ds:[node.next] == 0
.if ds:[node.previous] == 0
invoke mem_free,pNode
.else

push ds:[node.previous]
pop ds

mov ds:[node.next],0

invoke mem_free,pNode
.endif
.else
.if ds:[node.previous] == 0

push ds:[node.next]
pop ds

mov ds:[node.previous],0

invoke mem_free,pNode
.else

push ds:[node.next]
pop ax

push ds:[node.previous]
pop ds

mov ds:[node.next],ax

push pNode
pop ds

push ds:[node.previous]
pop ax

push ds:[node.next]
pop ds

mov ds:[node.previous],ax

invoke mem_free,pNode

.endif
.endif

pop ds


exit:

Ret
r_node endp

is there something excess? Any possible ways to get less code size?

[ghjjkl]

looks like i've got some problems with linked list  :(
here's:

Code Select Expand



node struc
prev dw 0
next dw 0
data dw 0
node ends

(...)

;this function adds new node
;tail  - pointer to linked list's tail
;_data - data we want to append
node_add proc near c tail:word, _data:word

mov bx,tail
mov ax,[bx]

.if ax==0 ;if there's no any nodes yet
invoke mem_alloc,1,bx ;memory allocation first param - count of blocks to be allocated second param would be segment address of blocks to be allocated
push ds
mov ds,ax ;ds now contains segment address
mov ax, _data_ ;store data
mov [ds:node.data],ax
pop ds
.else ;if tail != 0, there's at least one node,we consider there was no error while memory allocation
push ds
mov ds,ax
in



looks like i've got some problems with linked list  :(
here's:

[code]

node struc
prev dw 0
next dw 0
data dw 0
node ends

(...)

;this function adds new node
;tail  - pointer to linked list's tail
;_data - data we want to append
node_add proc near c tail:word, _data_:word

mov bx,tail
mov ax,[bx]

.if ax==0 ;if there's no any nodes yet
invoke mem_alloc,1,bx ;memory allocation first param - count of blocks to be allocated second param would be segment address of blocks to be allocated
push ds
mov ds,ax ;ds now contains segment address
mov ax, _data_ ;store data
mov [ds:node.data],ax
pop ds
.else ;if tail != 0, there's at least one node,we consider there was no error while memory allocation
push ds
mov ds,ax
invoke mem_alloc,1,node.next

push ds
mov ds,ax
mov ax,_data_
mov [ds:node.data],ax
;now we need to store list's tail to new list's tail previous node 
pop ax
mov  [ds:node.prev],ax
;now we need to update list's tail. We consider it's located in @data
mov ax,ds
pop ds
mov bx,tail
mov [bx],ax
.endif
ret

node_add endp

(...)

;this funtion removes node
;_node - node to be removed
;__node - offset to list's tail
;__node_seg - segment address of list's tail
;mem_free - deallocates memory, parameter - address of block to be deallocated

remove_node proc near c _node:WORD,__node:WORD,__node_seg:WORD

mov ax,_node

.if ax==0 ;if there's no any nodes
jmp exit
.endif

push ds

mov ds,_node

.if [ds:node.next]==0 ; if current node doesn't have next node

.if [ds:node.prev]==0 ; if current node doesn't have previous node

;so we have a single node, just remove it

invoke mem_free,_node
mov ax,__node_seg ;set node's tail to zero
mov ds,ax
mov [ds:__node],0

.else

;so we have have a standard sutiation when there's several nodes

push [ds:node.prev] ;go to previous node
pop ds

xor ax,ax ;we're about removing, so there's no next node anymore
mov [ds:node.next],ax


invoke mem_free,_node
;now update list's tail
push ds
mov ax,__node_seg
mov ds,ax
pop ax

mov bx,__node
mov [bx],ax

.endif

.else

.if [ds:node.prev]==0

;so node to be deleted is first node

push [ds:node.next];go to next node
pop ds

xor ax,ax ;;we're about removing, so there's no previous node anymore
mov [ds:node.prev],ax

invoke mem_free,_node

.else
;yet another situation, node to be deleted is located between two another ones

mov cx,[ds:node.next]
mov dx,[ds:node.prev]

mov ds,dx
mov [ds:node.next],cx
mov ds,cx
mov [ds:node.prev],dx

invoke mem_free,_node

.endif
.endif


exit:
pop ds

Ret
eject_node endp

(...)

;now lets imagine that we move through all nodes, starting from tail

push ds
mov cx,node_count ;located in @data
mov ax,node_tail
mov ds,ax

.while cx>0

.if (SOME_CONDITION)

(some actions)

;we're about node removing, and we need to set ds to previous node
mov ax,[ds:node.prev]
push ax
mov bx,@data
push cx
invoke remove_node,ds,offset tail,bx
pop cx
pop bx
mov ax,@data
mov ds,ax

dec node_count

mov ds,bx
jmp __label
.endif

(some actions)

;otherwise just go to next node

mov ax,[ds:node.prev]
mov ds,ax

__label:

dec cx
.endw

the problem is sometimes some node have the same node.prev and node.next and sometimes one node can point on itself  :(

[ghjjkl]

So, do you want to know what was an error? 

[dedndave]

most of us keep busy with 32-bit or 64-bit code   :P

that's why you may not see a lot of response to this type of thread

[Gunther]

Hi ghjjkl,

I think there's a book by Ray Duncan: Power Programming with Microsoft Macro Assembler. It has code for linked lists, double linked lists etc. and it's 16-bit DOS stuff. That's what you're looking for.

Gunther

[ghjjkl]

it seems that i forgot to set some struct's fields to zero. That's why some of them could contain outdated pointers to previous and next nodes, which could be removed by the time of new node allocation. So i could find unexpected and suspicious disappearance of all nodes

[dedndave]

wait til you write one for win32....
....and, you want it to be thread safe   :P

[avcaballero]

Hello, some examples of linked lists in my tuto, but with somo libs not available, sorry, but maybe can help you. There are also trees, sorting, searching, etc.

Regards

[BlueMR2]

most of us keep busy with 32-bit or 64-bit code   :P

that's why you may not see a lot of response to this type of thread

I still do more 16-bit than 32 and 64.  However, I don't have a lot of time to look into problems posted here or I'd answer more...  :-(