![]() |
![]() |
![]() |
![]() |
18 The Lists Module (lists.hhf)
The HLA Standard Library provides a generic list abstract data type via the lists module. The lists module provides two classes: a generic list class and a generic, abstract, node class. These classes have the following definitions:
node: class var Prev: pointer to node; Next: pointer to node; procedure create; @returns( "esi" ); external; method destroy; abstract; endclass; list: class var Head: pointer to node; Tail: pointer to node; Cnt: uns32; #if( @CurOffset mod 4 <> 0 ) Padding: byte[ 4 - (@CurOffset mod 4) ]; #endif procedure create; @returns( "esi" ); method destroy; method numNodes; @returns( "eax" ); method append_index( var n:node; posn: dword ); @returns( "esi" ); method append_node( var n:node; var after: node ); @returns( "esi" ); method append_last( var n:node ); @returns( "esi" ); method insert_index( var n:node; posn:dword ); @returns( "esi" ); method insert_node( var n:node; var before:node ); @returns( "esi" ); method insert_first( var n:node ); @returns( "esi" ); method delete_index( posn:dword ); method delete_node( var n:node ); method delete_first; method delete_last; method index( posn:dword ); iterator itemInList; endclass;Program 3 LIST Class Definitions
The node class is an abstract base class from which you must derive a node type for the nodes in your list. You would normally override the node.create procedure and write a procedure that specifically allocates storage for an object of type node and initializes any important data fields. If you like, your overloaded create procedure can call node.create to initialize the link fields of the node you create, although this is not strictly necessary.
The node.destroy method is an abstract method that you must override. The list.destory method calls node.destroy (or, at least, your overloaded version of it) in order to free the storage associated with a given node. A typical concrete implementation of this function looks like the following:
method MyNode.destroy; @nodisplay; @noframe; begin destroy; // On entry, ESI points at the current node object. // Free the storage associated with this node. if( isInHeap( esi )) then free( esi ); endif; end destroy;For a typical example of an overloaded node class, see the listDemo.hla example in the HLA examples subdirectory.
The list class is an abstract data type used to maintain lists of nodes. Internally, the list class represents lists of nodes using a doubly-linked list, although your applications should not be aware of the internal implementation. Likewise, for efficiency reasons the list class maintains a pointer to the head of the list, a pointer to the tail of the list, and a count of the number of nodes currently in the list. Your applications should ignore these fields (note that you can obtain the number of nodes in the list by calling the numNodes method).
The following subsections describe each of the methods available in the lists class
18.1 List Maintenance
procedure list.create; @returns( "esi" );If you call this class procedure via "list.create( )" it will allocate storage for a new list object, initialize the fields of that object (to the empty list), and return a pointer to that list object. If you call this class procedure via "someListVarName.create( )" then this procedure will initialize the (presumably) allocated list object (again, to the empty list).
method list.destroy;This method frees the storage associated with each node in the list (if the individual nodes were allocated on the heap), it then frees the storage associated with the list object itself, assuming the list was allocated on the heap. Note that successful execution of this method requires that you create a derived class from the abstract base class node and that you've overridden the node.destroy method. The list.destroy method deallocates the nodes in the list by calling the node.destroy method for each node in the list.
18.2 Adding Nodes to a List
method list.append_index( var n:node; posn: dword ); @returns( "esi" );This method appends node n to the list after node posn in the list. If posn is greater than or equal to the number of nodes in the list, then this method appends node n to the end of the list. Normally, you would not call this method directly. Instead, you would use the
listVar.append(n,posn)macro to call this method. This function returns a pointer to node n in ESI. As with most method invocations, this call wipes out the value in EDI.
method list.append_node( var n:node; var after: node ); @returns( "esi" );This method inserts node n in the object list immediately after node after in that list. This method assumes that after is a node in the object's list; it does not validate this fact. Therefore, you must ensure that after is a member of the object's list. Normally, you would not call this function directly; instead, you would invoke the listVar.append( n, after ) macro to do the work. This function returns a pointer to node n in ESI. As with most method invocations, this call wipes out the value in EDI.
method list.append_last( var n:node ); @returns( "esi" );This method appends node n to the end of the object list. Normally you would not call this method directly, instead you would just invoke the listVar.append(n) macro. This function returns a pointer to node n in ESI. As with most method invocations, this call wipes out the value in EDI.
method list.insert_index( var n:node; posn:dword ); @returns( "esi" );This method inserts node n before the posnth node in the list. If posn is greater than or equal to the number of nodes in the list, this method simply appends the node to the end of the list (remember, nodes are numbered from 0..Cnt-1; so if posn=Cnt then that would imply inserting the node at the end of the list). Normally you would not call this method directly; instead, you'll invoke the listVar.insert( n, posn) macro to do the job. This function returns a pointer to node n in ESI. As with most method invocations, this call wipes out the value in EDI.
method list.insert_node( var n:node; var before:node ); @returns( "esi" );This method inserts node n before node before in the object's list. This method assumes that before is an actual member of the list, it does not verify this prior to insertion. You would not normally call this routine directly. Instead, invoke the listVar.insert( n, before ) macro to do th actual work. This function returns a pointer to node n in ESI. As with most method invocations, this call wipes out the value in EDI.
method list.insert_first( var n:node ); @returns( "esi" );This function inserts node n at the beginning of the object's list. You would not normally call this method directly; you should normally invoke the listVar.insert( n ) macro and let it do all the work. This function returns a pointer to node n in ESI. As with most method invocations, this call wipes out the value in EDI.
18.3 Removing Nodes from a List
method list.delete_index( posn:dword ); @returns( "esi" );This method removes the posnth node from the list and returns a pointer to this node in ESI. Normally you would invoke the listVar.delete( posn ) macro rather than calling this method directly.
method list.delete_node( var n:node ); @returns( "esi" );This method removes node n from the list and returns a pointer to this node in ESI. This method assumes that node n actually is in the list; it does not verify this. Normally, you would invoke the listVar.delete(n) macro rather than call this method directly.
method list.delete_first; @returns( "esi" );This method removes the first node from the list and returns a pointer to this node in ESI. Normally you would not call this method directly but you would invoke the listVar.delete() macro instead.
method list.delete_last; @returns( "esi" );This method removes the last node from the list and returns a pointer to this node in ESI.
18.4 Accessing Nodes in a List
method list.index( posn:dword ); @returns( "esi" );This method returns a pointer to the posnth node in the list in the ESI register. It returns NULL if the list is empty. It returns the address of the last node in the list if posn >= Cnt.
iterator list.itemInList;This iterator returns a pointer to each node in a list in the ESI register. Like most iterators, you normally use this iterator within a FOREACH loop.
method list.numNodes; @returns( "eax" );This function returns the number of nodes currently in the list in the EAX register. You should always call this routine rather than access the list.Cnt field directly.
![]() |
![]() |
![]() |
![]() |
![]() |