Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Assember code, pointers and dynamic structures
- Thread starter LVL
- Start date
lionelhill
Technical User
There are two parts to this question. (1) allocation of memory, and (2) setting up a linked list or similar.
(1)
In genuine assembler you are responsible for memory management, so you are starting with a lump of memory allocated by the operating system, and it is your job to remember which bits are in use, and which aren't, and make sure that the area is used as efficiently as possible. This is a huge subject, that you can touch on as little or as much as you like. If you have access to Pascal (I assume you might from the way you ask the question) then you could do worse than have a look at the memory allocation strategy that Pascal uses in controlling the heap. The pascal documentation explains it, and you could emulate that. If you really want the heavy stuff, then Knuth's big tome has loads. But I have never managed to plough through more than about 30 pages of Knuth at a time doing exercises before it's been time to return him to the library....
The good side is, though, if you are writing assembler to interface with a high level language (and in practice you often may be), then allocating memory is simply a matter of arranging for the assembly bit to call the high-level language memory allocation. i.e. call Pascal's getmem. Easier said than done since getmem is in the system unit whose addresses aren't available. But whatever language you are using, you should be able to write your own function that calls getmem or equivalent, and whose address is known to your assembler thing. This will cost you an extra jump though.
(1b - simple memory management)
If you must write your own memory allocation strategy, I suggest you write it as a separate routine. A typical way to do it would be to put a marker at the start of the empty block allocated by operating system indicating that x-bytes are free and this is the final marker. When asked for memory, this marker is changed to indicate that x-bytes are occupied, and the next free block starts at address Y. Address Y now holds a marker to say z bytes are free and this is the final marker. A request for memory can be dealt with quickly by choosing the first marker indicating that there is enough free to fulfill the request, or efficiently by choosing the hole that most nearly matches the size of the request. In effect, the memory is managed as a linked list of variable size data structures, each of which can be returned as an address to someone who wants to store data. Holes happen where "freemem" is called. This needs to change the corresponding marker to indicate that x bytes are now free, but this isn't the top of the heap, and the next block begins at address Y. With a bit of cleverness you can notice if the next block, at Y, is also free, in which case you can amalgamate them into a single block and cut out the marker at Y altogether. Similarly if less memory is returned than was first requested, you could do something clever like modify the first marker to indicate the smaller reserved block, and insert a new marker at its end to indicate the size of the free bit.
(2) Once you've got memory allocation, setting up a linked list is easy. You do the same as you would in pascal.
{ currently address of node is in es:di. Following code adds one node to list, assuming that first entry is the far pointer to the previous node }
push es ; save existing node's address
push di
push sizeofnextnode ; prepare to allocate memory
call getmemthing ; returns address in es:di or whatever
pop cx ; set up previous node's address in list
mov es:[di], cx
pop cx
mov es:[di+2], cx
... and you now have a new node. This builds linked lists backwards so the final node you add is the base, pointing to all the others. But seeing as that is simple, that's often how I build a linked list.
Circular lists are usually best built linear, then you find the end, and put in its nil pointer the address of the last node you added, which is the base node. Then it is circular.
Hope that helps.
(1)
In genuine assembler you are responsible for memory management, so you are starting with a lump of memory allocated by the operating system, and it is your job to remember which bits are in use, and which aren't, and make sure that the area is used as efficiently as possible. This is a huge subject, that you can touch on as little or as much as you like. If you have access to Pascal (I assume you might from the way you ask the question) then you could do worse than have a look at the memory allocation strategy that Pascal uses in controlling the heap. The pascal documentation explains it, and you could emulate that. If you really want the heavy stuff, then Knuth's big tome has loads. But I have never managed to plough through more than about 30 pages of Knuth at a time doing exercises before it's been time to return him to the library....
The good side is, though, if you are writing assembler to interface with a high level language (and in practice you often may be), then allocating memory is simply a matter of arranging for the assembly bit to call the high-level language memory allocation. i.e. call Pascal's getmem. Easier said than done since getmem is in the system unit whose addresses aren't available. But whatever language you are using, you should be able to write your own function that calls getmem or equivalent, and whose address is known to your assembler thing. This will cost you an extra jump though.
(1b - simple memory management)
If you must write your own memory allocation strategy, I suggest you write it as a separate routine. A typical way to do it would be to put a marker at the start of the empty block allocated by operating system indicating that x-bytes are free and this is the final marker. When asked for memory, this marker is changed to indicate that x-bytes are occupied, and the next free block starts at address Y. Address Y now holds a marker to say z bytes are free and this is the final marker. A request for memory can be dealt with quickly by choosing the first marker indicating that there is enough free to fulfill the request, or efficiently by choosing the hole that most nearly matches the size of the request. In effect, the memory is managed as a linked list of variable size data structures, each of which can be returned as an address to someone who wants to store data. Holes happen where "freemem" is called. This needs to change the corresponding marker to indicate that x bytes are now free, but this isn't the top of the heap, and the next block begins at address Y. With a bit of cleverness you can notice if the next block, at Y, is also free, in which case you can amalgamate them into a single block and cut out the marker at Y altogether. Similarly if less memory is returned than was first requested, you could do something clever like modify the first marker to indicate the smaller reserved block, and insert a new marker at its end to indicate the size of the free bit.
(2) Once you've got memory allocation, setting up a linked list is easy. You do the same as you would in pascal.
{ currently address of node is in es:di. Following code adds one node to list, assuming that first entry is the far pointer to the previous node }
push es ; save existing node's address
push di
push sizeofnextnode ; prepare to allocate memory
call getmemthing ; returns address in es:di or whatever
pop cx ; set up previous node's address in list
mov es:[di], cx
pop cx
mov es:[di+2], cx
... and you now have a new node. This builds linked lists backwards so the final node you add is the base, pointing to all the others. But seeing as that is simple, that's often how I build a linked list.
Circular lists are usually best built linear, then you find the end, and put in its nil pointer the address of the last node you added, which is the base node. Then it is circular.
Hope that helps.
- Status