chapter3.htm

嵌入式软件开发.rar

place the code executed in the method exercise() right here in the link list object.  With the 
pointer to the current object, all methods and attributes of the current object are available 
to the link list program.  
<p>	Such an approach would be a mistake.  The way that the classes are laid out here 
with exercise a method of the class object provides gererality that would be lost with the 
above approach.  The thought here is that exercise is a part of the class object, it works on 
object attributes, it is unique to the class object, and it will probably change with different 
classes whose objects might be stored in the linked list.  Therefore, to place any object 
specific code within the boundaries of the linked list program would limit use of the linked 
list object to the specific object type that it was written for, and it would be completely 
ungeneral.
<p>	In the code shown below, it is assumed that a link list exists.  The program is 
cycled through each of the links and the specifice method exercise() is executed for each 
object on the list.  The method parameter is the value stored in current object.  It is 
assumed here that the required method parameter is a pointer to the current parameter. 
The execution of the walk is terminated when the next_link pointer contains a NULL.
<pre><code>
	void walk_list(Link_list *list)
	{
	    Link *start;

	    start=list-&gthead;
	    while(start-&gtnext_link != NULL)
	    {
	        (*start-&gtcurrent_object-&gtexercise)(start-&gtcurrent_object);
	        start=start-&gtnext_link;
	    }
	}
</pre></code><p>

	With the exception of the constructor and the destructor, we have completed the 
discussion of the code for the linklist implementation file.  The code for the parts of this 
file have been presented piece-meal above.  The whole program including the constructor 
and the destructor is pulled together below.  
<pre><code>
	#include "linklist.h"

	/*  This routine receives a list pointer and a pointer to a new
	    link that is to be added to the list.  The new link will be
	    placed at the head of the linked list.   If the list is empty
	    and there is no NULL link to start the list, there is an error
	    and the function returns FALSE.  */
	        
	int add_link(Link_list *list,Link *new_link)  
	{
		Link *start;

		start=list-&gthead;
		if(start==NULL)   /* got an empty list */
		{
			if(new_link-&gtnext_link !=NULL)
				return FALSE;  /* got an error--no NULL link for the end */
			else
			{
				list-&gthead =new_link;
				return TRUE;
			}
		}
		else
		{
	    	new_link-&gtnext_link=start; 
	    	start-&gtprevious_link=new_link;
	   		list-&gthead=new_link;
			return TRUE;
		}
	}

	/*  This routine removes a link.  The linked list is searched from 
    start to the end.  When the link old_link is found, it is removed from 
    the list and then the link destructor is executed.  If the link
    is not found on the list, a FALSE is returned to the calling function
    Otherwise, the function returns a TRUE.    */

	int delete_link(Link_list *list, Link *old_link)
	{	
		Link *start;

		start=list-&gthead;
		if(start==old_link)  /* first list entry */	  
		{
	        start-&gtnext_link-&gtprevious_link=NULL;
			list-&gthead=start-&gtnext_link;
		}
	    else
	    {
	        while(start != old_link && start-&gtnext_link!=NULL)  
	        {										
	   			if(start-&gtnext_link==NULL) /* link not in list */
					return FALSE;
				else
	            	start=start-&gtnext_link;
	   		}
	        start-&gtprevious_link-&gtnext_link=start-&gtnext_link;
	        start-&gtnext_link-&gtprevious_link=start-&gtprevious_link;
	    }
	    link__(old_link);                /* destroy the old link */
	    return TRUE;     
	}

	void walk_list(Link_list *list)
	{
		Link *start;

		start=list-&gthead;
	    while(start-&gtnext_link != NULL)
	    {
	        (*start-&gtcurrent_object-&gtexercise)(start-&gtcurrent_object);
	        start=start-&gtnext_link;
	    }
	}

	/* The constructor */

	Link_list *link_list_(void)
	{
		Link_list *this;
		
		this=(Link_list *)malloc(sizeof(Link_list));
		this-&gthead=NULL;  /* start with empty list */
		return this;
	}
						   
	void link_list__(Link_list *this)
	{
		free(this);
	}  
</pre></code><p>
	The constructor and destructor for the linked list are simple.  link_list_() shown 
above merely allocates space to hold the member of a linked list and places a NULL 
pointer in the head attribute.  There are no other attributes or internal member functions 
for this method.  The destructor frees the memory allocated for this list.
<p>	This linked list program is a primative list that will probably need change.  Among 
the changes that might be desirable are to add some attributes to the class.    What 
changes would we need?   The list as it is constructed here can be a stack or a last-in first-
out operation.  Here, new links are added to the head of the list and links are removed 
from the head of the list.  There are other operations that might be desirable.  A queue, or 
a first-in first-out operation, would require that new links be added to the head of the list 
and links removed from the list would come from the end or the tail of the list.  Our linked 
list can be either a stack or a queue, but there is no really good code to find the tail of the 
list.  A potential attribute of a linked list might contain a pointer to the end of the list.  Yet 
another attribute might be the length, the number of links, of the list. These additional 
attributes would make finding the tail easy so that a queue would be more easily 
implemented.  More of these ideas will be explored as they are needed.  
<p>	A simple example will test the performance of the linked list.  The code shown 
below creates a linked list with five entries.  Each link entry contains an object with a 
different value for count.  The link is walked.  As the routine exercise() is executed for 
each value of count and the computer signal is actuated, you can measure the time 
required to execute the count in each instance. 
<p>	Five objects are created: no1, no2,..no5.  Also, six links are created.  They are 
bel1, bel2,..bel5 and nil.  The first five links will receive the corresponding objects, and the 
the final link, nil,  will be the NULL link that terminates the list.  The objects are 
instantiated with different values of count.  The links are created.  The NULL link nil
is constructed with a NULL parameter.  The remainder of the links are created with 
objects as parameters.  The linked list is then created by adding the links to the list with 
add_link() commands.  After this business is completed, the values of count, extracted 
from the link list, are each printed on the screen.  The list is then walked with walk_link().  
With the paramteres used and the computer on which this program was tested, a count of 
5,000,000 will yield about a seven second delay.   Therefore, the difference in delays is 
easily sensed.  After completion of the walk_list() operation, the links bel5 and bel3 are 
removed from the list.  After their corresponding objects are destroyed the values of count 
are again printed out.  walk_list() is again executed for list and you, the operator, can 
accuractly sense that the links and their corresponding objects have been removed from 
the list. 
<pre><code>
	#include &ltstdio.h&gt
	#include "object.h"
	#include "link.h"
	#include "linklist.h"

	main()
	{
	    Link *bel1,*bel2,*bel3,*bel4,*bel5,*nil;
	    Object *no1,*no2,*no3,*no4,*no5;
	    Link_list *list=link_list_();
	    Link *start;
	    int i;

	    no1=object_(1000000);   /* create the objects */
	    no2=object_(2000000);
	    no3=object_(3000000);
	    no4=object_(4000000);
	    no5=object_(5000000); 
	    
	    nil=link_(NULL);	    /* create the links */
	    bel1=link_(no1);
	    bel2=link_(no2);
	    bel3=link_(no3);
	    bel4=link_(no4);
	    bel5=link_(no5); 
	  	
	    add_link(list,nil);	    /* link the links into a linked list */
	    add_link(list,bel1);
	    add_link(list,bel2);
	    add_link(list,bel3);
	    add_link(list,bel4);
	    add_link(list,bel5);

	    printf("got here 1\n");	/* do some tests */
	    start=list-&gthead;
	    for(i=0;i&lt5;i++)
	    {
	        printf("%ld\n",start-&gtcurrent_object-&gtcount);
	        start=start-&gtnext_link;
	    }
	    walk_list(list);

	    delete_link(list,bel5);	/* delete a couple of links */
	    delete_link(list,bel3);	/* and repeat the tests */
	    object__(no3);
	    object__(no5);
	    printf("got here 2\n");
	    start=list-&gthead;
	    for(i=0;i&lt3;i++)
	    {
	        printf("%ld\n",start-&gtcurrent_object-&gtcount);
		  start=start-&gtnext_link;
	    }
	    walk_list(list);  
	}
</pre></code><p>
	A note of caution.  It may seem silly to delete the object in the above code.  When 
the program is completed, all of the objects created by the program are destroyed anyway.  
Therefore, there is really no need to ever execute a destructor in a program like the one 
above.  True!  However, as your programs become more complicated, and when you are 
working within the limited RAM constraints of a microcontroller, the occasional neglect 
of  execution of the destructor can eventually lead to completely filled RAM with 
unneeded objects.  When this happens, the program will crash on any attempt to create a 
new object.  In Chapter 2, we began to test for the successful allocation of memory each 
time a new object was instantiated.  That practice is absolutly required for all 
microcontroller code:  perhaps, not so important on a desktop machine that has essentially 
infinite memory for the programs that we are executing.  If your code will ever be used on 
a microcontroller, make certain that each malloc() is tested to determine if a proper 
allocation was completed.  Otherwise, the program must enter some type of error 
recovery routine.  Also, make certain that you destroy any object when it goes out of 
scope.  Such a habit will keep the maximum amount of RAM available to the program at 
all times.
<p>	You might note that the test program above was written to run on a desk-top 
computer.  All of the code, with the exception of the test program, has also been compiled 
to run on an M68HC16, and this code executes properly.  You might note that there is no 
change needed when moving the link list program from your PC to a microcontroller.  

<h3><a name="look-up_table">Look-Up Table</a></h3>

<p>	In many instances, some sort of a nonlinear transfer function is used to operate on 
input data to generate a desirable transformation of the data.  This transform can be in the 
form of an equation, a limiting operation, a rounding operation, or even an empirical 
transform that depends on measured data.  Sometimes the work required to execute this 
transform is little, but if a transform consists of a high order equation, it might require 
significant computer time to calculate the output value.  One approach that will allow the 
approximation of an equation or empirical data is the look-up table. With a look-up table, 
a series of samples over the range of the input and their corresponding outputs are either 
calculated or measured.  These inputs and outputs are placed into a table, and the 
transformation is calculated by finding the nearest point to the input data and then 
interpolating between the adjacent points in the table to provide better resolution than the 
basic table represents.  The interpolation is usually a linear interpolation, so the calculation 
is simple.  Usually, four additions or subtractions, one multiplication and one division are 
needed to execute the interpolation.  We shall also see a different way to generate the 
look-up table that will simplify the interpolation calculation to two additions and one 
multiplication for each interpolation. Such a look-up table is a good example of an object 
application that can have significant use in embedded systems.  
<p>	When dealing with control systems or other embedded applications, most data 
inputs are communicated to the computer through either serial inputs or other approaches 
like analog to digital converters.  Most of the time the data format found for these inputs 
is eight bit unsigned data.  In other words, the range of the input data is from 0 to 255 in 
steps of 1.  In such cases, it is probably wise to simply use an unsigned char to contain the 
data values.  It is not expected that the required resoultion of the interpolated data should 
be finer than 1, and the output data range should not exceed seriously the input range. 
<p>	 A header file for a look-up table object is shown below.  The look-up table itself 
must be defined in some manner in this header.  The approach chosen here is to build the 
table of a series on n two BYTE entries.  With this approach, the table can be created in 
either RAM or ROM, and a pointer to the beginning of the table will be passed to the 
object when it is created. Also, the length of the table will be passed.  This approach