chapter3.htm

嵌入式软件开发.rar

	#endif
</pre></code><p>
	The new type Object is defined as a struct object.  Function prototypes of both the 
object constructor and destructor are also included in the header file.  The implementation 
file follows.  Note that the method exercise() is defined as a static function so that visibility 
to the function and the name exercise is limited to the implementation file.  The operation 
contained in the exercise function is to merely execute the while loop count times to cause 
a delay in the program.  Then a bell signal is sent out from the computer.  
<pre><code>
	#include "object.h"

	static void exercise(Object *this)
	{
	    long i=this-&gtcount;
	    while(i--)     /* kill some time */
	        ;
	    putch(0x07);  /* send out a signal */
	}

	Object *object_(long count)
	{
	     Object *this=(Object *)malloc(sizeof(Object));
		
	     this-&gtcount=count;
	     this-&gtexercise=exercise;
	     return this;
	}

	void object__(Object *this)
	{
		free(this);
	} 
</pre></code>
<p>	The constructor first allocates a memory space to hold the the object and then the 
parameter count is placed in the object followed by the placement of a pointer to the static 
function exercise in the proper location in the object.  Finally, the destructor merely 
deallocates the memory that was allocated for the object.  


<h3><a name="link_class">Link Class</a></h3>

<p>	The link header file, link.h is shown below.  This file includes a reference to the 
object header file along with the defines header file shown in Chapter 2.  The structure 
body definition statement contains three attributes that are each pointers to other objects. 
The first is a pointer to the object class associated with this particular link.  The remainder 
of the pointers are to the previous and the next links in the list.  There is no use for these 
link pointers in this class.  Use for these pointers is reserved for the link list class that 
follows.  The remainder of this header file is standard and follows the approach always 
used to include prototypes for the constructor and destructor methods. 

<pre><code>
	#ifndef LINK_H
	#define LINK_H

	#include "defines.h"
	#include "object.h"

	#define LINK_CLASS \
		   struct object *current_object; \ 
	         struct  link *previous_link;   \
		   struct  link *next_link;

	typedef struct  link
	{
		LINK_CLASS
	} Link;

	Link * link_(void *object);
	void  link__(struct link *);

	#endif
</pre></code>
<p>	The link implementation file contains the code for the link constructor and 
destructor.  The constructor allocates memory for the the link object and places the object 
pointer that is passed in as a parameter into the location current_object.  Both 
previous_link and next_link are assigned a value NULL. The pointer to the object, this, is 
returned to the calling program.  Finally the destructor merely frees the memory allocated 
for a specific object.  
<pre><code>
	#include "link.h"

	Link* link_(Object *obj)
	{
	    Link *this;

	    this=(Link *)malloc(sizeof(Link));
	    this-&gtcurrent_object=obj;
	    this-&gtprevious_link=NULL;
	    this-&gtnext_link=NULL;
	    return this;
	}

	void link__(Link *this)
	{
	    free(this);
	}
</pre></code>

<h3><a name="linklist_class">Linklist Class</a></h3>

 <p>	Linklist is an interesting class.  It works by manipulating the values contained in 
previous_link and next_link in the several link objects stored in the list.  The link list must 
be started by entering a NULL object into the list.  A NULL object is what you will get if 
you exercise object_(NULL) which is the object constructor with a NULL parameter.  
This object will have a NULL pointer to each of its three attributes.  When a link is added, 
in this case, it will be placed at the head of the list, or the beginning of the list.  The NULL 
object will always be found at the end or the tail of the list, and the list exists as long as 
this NULL object exists.  The way that the  list is destroyed is to delete all of the  list 
objects along with the NULL object that deliniates the end of the list.  Then the linked list 
can be deleted.  Conversely, the linked list object is created by creating  a linked list, a 
NULL object, a NULL link, adding the NULL link to the linked list, and then adding 
objects needed to the list.
<p>	The class definition contains only one entry, the attribute which is a pointer to the 
void type head.  This parameter points to the beginning of the linked list.  It is possible to 
complete a linked list without this attribute, but then it is a requirement that the program 
using the linked list keep track of the beginning of the list which will change as links or 
nodes are added to or removed from the list.  
<p>	There are three class methods needed for the linklist class.  The first method is 
called walk_list.  This method is given a parameter that is a pointer to the linked list.  It 
will execute the method exercise() for every object stored in the list.  The method 
add_link() places the new method at the beginning of the list, and delete_link will search 
the list for the specified old_link and remove this link from the list.    
<pre><code>
	#ifndef LINKLIST_H
	#define LINKLIST_H

	#include "defines.h"
	#include "object.h"
	#include "link.h"

	#define LINK_LIST void *head;

	typedef struct
	{
		LINK_LIST
	} 	Link_list;


	Link_list *link_list_(void);
	void link_list__(Link_list *);
	void walk_list(Link_list *list);
	int add_link(Link_list *list,Link *new_link);
	int delete_link(Link_list *list, Link *old_link);

	#endif
</pre></code>
<p>	When the program enters the method  add_link(), the value list is a pointer to the 
link list.  The new link will be placed at the head of the list.  Figure 3.1 shows a layout of a 
link list that contains two objects with a proper terminating null link at its end.  Each link 
object contains three pointers: object, next_link, and previous_link.  When the list is 
created, a NULL link with all three attributes equal to a NULL is added to the list.  As 
additional links are added, the previous_link pointer NULL link is pointed to the newly 
added link.  The next_link pointer in the new object is pointed to the NULL link.  The 
previous_link pointer in the new link will be unaltered from the NULL value assigned to it 
when it was created.  Siimilarly, the next_link pointer of the NULL link will point to a 
NULL, as it always will.  Additional links can be added by merely changing the contents of 
the next_link and previous_link pointers.  

<p><img align=middle src="fig3-1.jpg">
 

<h4>Figure 3.1  A complete link list</h4>

<p>	A new link is added to a linked list easily.  The contents of the previous_link of the 
head of the list is set to the address of the new link.   The attribute next_link of the new 
link is set the address of the old list head.  These operations are shown in Figure 3.2.

<p><img align=middle src="fig3-2.jpg">

 

<h4>Figure 3.2 Result of adding a new link to the list</h4>

<p>	The code required to add a new link to the head of the list is shown below.  This 
code merely executes the ideas listed above.  There must be a special treatment to handle 
the addition of a link when the list is newly created.  The first entry must be a NULL link.  
A test is completed when there is no entries in the list to assure that the first entry is a 
NULL link.  Then a functioning link can be added at the head of the list.  The parameter 
head found in the object list is a pointer to the first link in the list.  This method will return 
a TRUE if it executes with no error and a FALSE otherwise. 
<pre><code>	
	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;
		}
	}
</pre></code>

<p>	Removal of a link from  a list involves adjustment of pointers in the two links 
adjacent to the link being deleted.  The value in the next_link of the link being removed is 
moved into the next_link pointer of the preceeding link.  Also, the value of the 
previous_link in the removed link is placed in the previous_link of the link following the 
one being removed.  At that time, the destructor for the link should be executed to free the 
allocated memory for later use.  Note, the object pointed to by the link is not deleted by 
this operation.  It is necessary to remove the object with code in the program that created 
the object in the first place. 

<p><img align=middle src="fig3-3.jpg">
 

<h4>Figure 3.3  Removing a link from a list</h4>

<p>	The code that implements removal of an arbitrary link from the list is shown 
below.  If the first link is being removed, it is merely necessary to make the previous_link 
of the second link equal to a NULL. This operation does not work out so nicely when 
working with other links, so removal of the first link is handled specially.  The first link is 
to be removed whenever the old_link, the link to be removed, equals the list-&gthead  which 
is the address of the first link.  Upon completion of this business, the first link is destroyed 
by a call to link__(old_link).  
<pre><code>
	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;     
	}
</pre></code><p>
	Otherwise, the value of old_link is compared with the pointers to the list objects in 
the link list until a match is found.  When the match is attained, pointers in next_link and 
previous_link of the adjacent links are altered to bypass the link to be removed.  Then 
old_link is destroyed by the destructor function link__(old_link).  An error condition 
occurs when there is no matching link to be found in the list.  In such a case, a FALSE is 
returned from this method.  When there is no error, TRUE is returned.
<p>	The final concern with the linked list at this time is the routine walk_list().  In some 
applications to which a linked list might be applied, it is desirable to execute some function 
for each entry in the list.  The method walk_list() does exactly this operation.  When 
walk_list() is executed, the function exercise() found with object will be executed for each 
object contained in the list. We will see applications of this type of operation later in the 
text.  Some care should be exercised when attempting to design an operation like a 
walk_list().  One of the most common errors that will occur when designing this type of 
class is to place an operation that belongs in the class object here in the linklist class.  For 
example, the code shown below contains the necessary operations to select the proper 
object link from the link list and then execute the specific method associated with the 
object.  Since, the program has a pointer to the current object, one might be tempted to