Data Structures

Hello,
Can someone give me some pointers on how to implement a doubly linked list while still staying in the 8086 arch. (16-bit). Yes, this is for a class project. http://www.cs.uakron.edu/~margush/306/PRG4.html
Thanks.

Comments

  • : Hello,
    : Can someone give me some pointers on how to implement a doubly linked list while still staying in the 8086 arch. (16-bit). Yes, this is for a class project. http://www.cs.uakron.edu/~margush/306/PRG4.html
    : Thanks.
    :
    If you know C, write it out in C first and convert (no, I DON'T mean -S). Converting to and from C/ASM is something I've gotten fairly good at. Either way, if you can't implement it in C (assuming you DO know C) then you won't be able to in assembly. The assembly should flow right from the C source when you finish.

    Whether you follow my advice (if relevant) or not here is some more.

    *Preliminary note: I don't target 8086 and I'm not going to really bother making sure this is 8086 compatible. Nothing I'm going to write is going to be inconvertible. *

    Basically, you'll have some structure that holds a next and a prev pointer and whatever data. So, let's say it holds WORDs. You might have something like the following (using the syntax of your assembler, this is TASM/MASM syntax)...

    [code]
    NODE STRUCT
    data dw ? ;the data
    next dw ? ;next near pointer
    prev dw ? ;prev near pointer
    NODE ENDS
    [/code]

    From there you just need to think of what you have to do for a linked-list.

    eg
    Insert at head

    Here's some quick C assuming an analogous structure...

    node->next=head;
    node->prev=NULL;
    head->prev=node;
    head=node;

    and a possible assembly interpretation (TASM syntax, though it will probably work with MASM, others will likely need some fixing)

    ;si=node di=head
    mov [si].NODE.next, di
    mov [si].NODE.prev, 0
    mov [di].NODE.prev, si
    mov di, si

    You can see how this flows straight from the C.

    Compatibility notes (if you are using a different assembler)

    The most general (ie least features needed of the assembler) way to rewrite this would be to replace the STRUCT with a set of symbolic constants that evaluated to the proper offset (in this case it would look like the following in TASM... (the names aren't important)

    NODE_DATA=0
    NODE_NEXT=2
    NODE_PREV=4
    )

    Then to use it you'd simply add (this is all TASM does behind the scenes). Once again, what it might look like in TASM.
    mov [si].NODE.next,di
    is now
    mov [si+NODE_NEXT],di

    "We can't do nothing and think someone else will make it right."
    -Kyoto Now, Bad Religion

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion