Hello,
I'm really new with ASM but i'm wondering if you could point me to an
implementation of a binary tree(or a linked list) in asm, it will be very useful to
study the code to clear my mind.
I know to implement this in C and Java but i'm having trouble with
assembly.

Thank you.

PS: I've seen some older posts but didn't find any implementation that i can study... so please help.
Posted on 2007-12-28 02:57:44 by miro
If you know how to do it in C, you should know how to do it in Assembly as well (if you have a little assembly experience), as there's really only very basic instructions available. If you aren't familiar with Assembly yet, you should probably take a look at MadWizard's crash course.

Also, if you have a working C solution, most compilers have a switch for outputting a .asm file listing of the generated code. If using this, be sure to either disable optimizations, or to optimize for size. Speed-optimized compiler output isn't the easiest to decipher :)
Posted on 2007-12-28 06:10:18 by f0dder
The idea is simple enough - the 'nodes' of the Tree are structs.
Each struct contains at least one pointer to another node, and this pointer will typically be set to ZERO if a given node has no 'child'.
In order to attach new nodes to existing ones, you need to manipulate those pointers.
Pretty much all Tree structures work this way, the only differences are usually in regards to how the node structs were allocated (one at a time, or in 'pages'), whether there are pointers from the child to the parent (so we can walk 'up' as well as 'down' the tree) and in the case of n-ary trees (eg quad or oct trees), how many childs can be attached to any parent node.

Each variation on this theme is more suitable to a particular application, so you really need to stop and think about what you need - for example, will the nodes need to be sorted at a later stage? Will there be huge numbers of nodes? Stuff like that.


MyNode struct
  blah1 dword ?
  blah2 dword ?
  pChild dword ? ;<--- pointer to next node in chain, list,tree,whatever
MyNode ends

Posted on 2007-12-28 19:43:33 by Homer
well finally i got it! the only thing to figure out is how to dynamically allocate memory. since i'm using .small and i think it will eventually run out of memory. any pointers? i'm working with tasm x86

Thank you
Posted on 2007-12-29 09:20:17 by miro
How to alloc memory depends on which operating system you're running under. For windows, use HeapAlloc for normal allocations, and VirtualAlloc for huge (several megabytes).
Posted on 2007-12-29 10:07:12 by f0dder

If you know how to do it in C, you should know how to do it in Assembly as well (if you have a little assembly experience), as there's really only very basic instructions available. If you aren't familiar with Assembly yet, you should probably take a look at MadWizard's crash course.

Also, if you have a working C solution, most compilers have a switch for outputting a .asm file listing of the generated code. If using this, be sure to either disable optimizations, or to optimize for size. Speed-optimized compiler output isn't the easiest to decipher :)



it seemed that Madwizard has update his website on 2008 1 1, beautiful screen!
Posted on 2008-01-03 02:57:05 by z23
There are different flavors of binary tree.

The graph methodology is basically a standard graph with each node having 2 (or 3) links to other nodes. The graph methodology is often the best choice when neither time nor space constraints are involved. It is generally costly to create new nodes, but relatively cheap to perform tree rotations.

When most people think of binary trees, they think of this graph methodology. It is very well documented and many algorithms demand the cheap tree rotations (splay trees, red-black trees, and so forth)

--

Aside from the graph methodology, there is also an address methodology where each node has an implicit address based on its topographical location.

From here there are several variations, one of which uses the address as an index into a heap and another uses the address as a key for a hash table.

The address as index variation has some severe limitations but is the fastest of them all (often used in memory managers). Traversal and new nodes are extremely cheap, but rotations are very expensive. There are also major constraints on tree depth.

The address as hash key variation has few limitations, the most prominent being again that tree rotations are very expensive. There is virtualy no limit on tree depth aside from the word size used to encode the address (depth 32 for 32-bit integers, depth 64 for 64-bit integers, and so forth)

The basics of the address concept begins with a stop bit. All addresses have one and it is the most significant '1' bit in the address. The next bit down from the stop bit encodes if we had to move left or right from the root, the bit after that again encodes a left or right choice, and so forth. Address '0' does not exist, with address '1' being the root.

Navigating around an address-based tree is fairly simple and extremely efficient.

leftchild = (address << 1)
rightchild = (address << 1) | 1
parent = (address >> 1)

When programming in assembly, it is convenient to use the carry flag to indicate if you need to go left or right, allowing you to use a single RCL instruction when navigating towards the leaves, and for going back to parent a single SHR is required. Very very efficient navigation, which is why memory managers use the address methodology (you will often also see huffman encoders and decoders using it.)

Posted on 2008-01-05 03:03:03 by Rockoon