flat assembler
Message board for the users of flat assembler.

Index > Macroinstructions > Linked list macros (ready to use)

Thread Post new topic Reply to topic

Joined: 15 Dec 2005
Posts: 151
I made some macros for linked list handling (doubly linked). Because of the way they are code, a pointer indirection is avoided when the name of the list is used instead of passing the address of the list in a register. You may still pass the address of the list in a register, though.

The code does not handle memory allocation. This allows some cool things, like:
- Same structure can be part of two (or more) lists (provided the structure has two list headers, and you pass the address of the correct one when adding the element to the lists.)
- Element can be removed from one list and added to another without any memory allocation or deallocation.
- Independent of how you manage your memory.
- Variable-sized elements if needed.

Each element is a memory area which starts with two dword pointers, which are filled and read by the linked list functions (do not touch them), followed by the data.

Basic use:

; Make a static element for the example (normally would be dynamically allocated). Place somewhere it can't be executed.
dd 0 ; reserved header
dd 0 ; reserved header
dd 0 ; your data
dd 0 ; more of your data (optional)

; Define a list (this places some bytes in the file, so place this statement somewhere where it can't be executed!
list_define mylist

; Add an element to the list. Give the address of the element's header (next/previous pointers).
list_add mylist, myelement

; Get a pointer to the current element into eax
list_get_current mylist

There are more macros. Read the code's comments to see what each macro does.

Warning: No warranties! Please report any bugs.

ri equ rd       ; reserve integer/pointer
di equ dd       ; define integer/pointer
integer equ dword
sizeof_i = 4

; Linked list macros
; When the list moves off the start/end it goes to an empty element. In this
; case, next goes to the first element. list_previous is invalid.

; The macros may modify eax
; Other registers are preserved

; The list_get_* macros leaves the result in eax.
; list_next and list_previous leaves the address of the new element in eax.
; If you go off the list, this may be 0!

macro movm op1, op2 {
    if [0] eqtype op1 & [0] eqtype op2
        push integer op2
        pop  integer op1
        mov integer op1, op2
    end if

struc list_element_t {
    prev di ?
    next di ?
    ; element contents
list_element_t_prev = sizeof_i*0
list_element_t_next = sizeof_i*1

; Define a list
macro list_define name {
    list_#name ri 1
    listcur_#name ri 1

; Get the size in bytes of the list header
list_header_size = sizeof_i*2

; Generic macro to use the correct reference to a list in an instruction
; For use from the other macros
; To avoid sparkling all the other macros with ifs.
macro list_do offset, instruction_before, list, instruction_after {
    if list eqtype name                                     ; Name of list
        instruction_before [list_#list+offset] instruction_after
    else if list eqtype edx                                 ; Address of list as reg
        instruction_before [list+offset] instruction_after  
        error___ Parameter must be name of list or address of list stored in reg
    end if

; Get first element
macro list_get_first list {
    list_do 0, <mov eax,>, list

; Get current element
macro list_get_current list {
    list_do sizeof_i, <mov eax,>, list

; Set current element
; Warning: Doesn't check if the pointer is valid
macro list_set_current list, element_ptr {
    list_do sizeof_i, movm, list, <, element_ptr>

; Add an element to the list
; The new element becomes the current element
; Make sure the pointer points to a superset of list_element_t
macro list_add list, element_ptr {
    local addfirst, addcommon, epilogue
    push edx                
    mov  edx, element_ptr   ; edx = new element
    list_get_current list   ; eax = old element
    cmp  eax, 0
    jz   addfirst
    ; Normal add
        movm [edx + list_element_t_next], [eax + list_element_t_next]   ; Set *next of new to next of current
        mov  [edx + list_element_t_prev], eax                           ; Set *prev of new to current
        mov  [eax + list_element_t_next], edx                           ; Set *next of current to new
        mov  eax, [eax + list_element_t_prev]                           ; current+1 into eax for addcommon
        jmp  addcommon
    ; Add as first element
        list_get_first list                         ; Get old first element to eax
        list_do 0, mov, list, <, edx>               ; Set new first element
        mov  [edx + list_element_t_next], eax       ; Set *next of new to old first element
        mov  integer [edx + list_element_t_prev], 0 ; Set *prev of new to 0
    ; Common to in-list add and start-of-list add
        ; Set *prev of element in front of inserted element
        cmp  eax, 0     ; But only if the element in front exists
        jz   epilogue
        mov  [eax + list_element_t_prev], edx
    ; Set the new element as the current element
    list_set_current list, edx
    pop  edx

; Remove the current element from the list
; After removal, the previous element becomes the current element
; When deleting the first element, the current element becomes the element
; before the first element (0)
macro list_remove list {
    local rem_first, rem_other, rem_all, rem_last
    push edx ; prev
    push ecx ; next
    list_get_current list
    mov  edx, [eax+list_element_t_prev]
    mov  ecx, [eax+list_element_t_next]
    ; deleting the first element?
    cmp  edx, 0
    jnz  rem_other
        list_do 0, mov, list, <, ecx>       ; Set list start to next element
        jmp  rem_all
        movm [edx+list_element_t_next], ecx     ; prev.next = del.next
    ; deleting the last element?
    cmp  ecx, 0
    jz   rem_last   
        movm [ecx+list_element_t_prev], edx     ; next.prev = del.prev
    list_set_current list, edx
    pop  ecx
    pop  edx

; Go to next element and return the new current element
macro list_next list {
    local off_list, end
    list_get_current list
    cmp  eax, 0
    je   off_list
        mov  eax, [eax + list_element_t_next]
        jmp  end
    list_get_first list
    list_set_current list, eax

; Go to previous element and return new current element
macro list_previous list {
    local off_list, end
    list_get_current list
    cmp  eax, 0
    je   off_list
        mov  eax, [eax + list_element_t_prev]
        jmp  end
        ; invalid
    list_set_current list, eax

; Reset current position to before the first element
macro list_reset list {
    list_set_current list, 0

Roses are red
Violets are blue
Some poems rhyme
And some don't.
Post 19 Aug 2009, 18:41
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum

Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.