A Reusable Routine for Doubly-Linked Lists, Part 2
January 26, 2011 Miguel Ortiz Martín and Ted Holt
|
Note: The code accompanying this article is available for download here. In Part 1 of this series, we introduced several concepts, such as managing external storage and defining comparator procedures, that are required for defining a reusable routine for managing doubly-linked lists. In this second part, we:
Creating and Destroying a List Let’s begin with a list of the subprocedures in the DBLLNKLST service program and a brief description of each one. 1. DblLnkLst_init: This procedure initializes a list for use and returns a pointer to the list. The required parameter for this procedure is: The optional parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_destroy: This procedure completely removes a list and frees all the memory allocated for the elements of the list and the list definition. The required parameter for this procedure is: The return value for this procedure is: Adding Elements To a List Three procedures insert elements into the list. One inserts elements at the head (the beginning) of the list, another at the end of list, and the third one inserts at a given position. There is no insertion-sort procedure, because appending elements and sorting afterward is fast, even for large lists. 1. DblLnkLst_append: Inserts an element at the end of the list. This procedure is useful for adding elements with a FIFO/queue policy. The required parameters for this procedure are: The return value for this procedure is: 2. DblLnkLst_prepend: Inserts an element at the head of the list. This procedure is useful for adding elements with a LIFO/Stack policy. The required parameters for this procedure are: The return value for this procedure is: 3. DblLnkLst_insertAt: Inserts an element at a given position. The required parameters for this procedure are: The return value for this procedure is: Extracting Elements From a List Extraction procedures extract (i.e., retrieve and remove) elements from the list. As with the insertion of elements, there are three procedures for extracting elements from the list. One extracts the first element of the list, another extracts the last element, and the third extracts the element at a given position. 1. DblLnkLst_extractFirst: Extracts the element at the head of the list. This procedure is for using a list with a FIFO/queue policy. The required parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_extractLast: Extracts the element at the end of the list. This procedure is for using a list with a LIFO/stack policy. The required parameter for this procedure is: The return value for this procedure is: 3. DblLnkLst_extractAt: Extracts the element at a given position. The required parameters for this procedure are: The return value for this procedure is: Data_p–The address of (a pointer to) the user data held by the first node of the list, or *null if the procedure ended in error. Fetching Elements From a List Fetch procedures differ from extracting methods in that they retrieve elements from the list, but they don’t remove them from it. Three procedures fetch elements from the list. One fetches the first element of the list, another fetches the last element, and the third one fetches the element at a given position. 1. DblLnkLst_fetchFirst: Retrieves the element at the head of the list. The required parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_fetchLast: Retrieves the element at the end of the list. The required parameter for this procedure is: The return value for this procedure is: 3. DblLnkLst_fetchAt: Retrieves the element at a given position. The required parameters for this procedure are: The return value for this procedure is: Finding an Element Within a List The supplied function to find an element within a list searches by direct comparison of data stored in the list against the requested data. The comparison is done by the user-defined comparison method, if one is defined by the user, or by the default comparison method supplied by the DBLLNKLST service program if not. 1. DblLnkLst_locate: Finds the position of an element in a list. The required parameters for this procedure are: The return value for this procedure is: Removing Elements From a List Delete procedures differ from extracting methods in that they remove elements from the list without returning the data value to the client. Three procedures delete elements from the list. One deletes the first element of the list, another deletes the last element of list, and a third one deletes the element at a given position. There is also a procedure–DblLnkLst_clear–that removes all the doubly-linked list elements without deleting the doubly-linked list object itself, which remains as an empty list. 1. DblLnkLst_deleteFirst: Deletes the element at the head of the list. The required parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_deleteLast: Deletes the element at the end of the list. The required parameter for this procedure is: The return value for this procedure is: 3. DblLnkLst_deleteAt: Deletes the element at a given position. The required parameters for this procedure are: The return value for this procedure is: 4. DblLnkLst_clear: Clear the list of all elements. The list is not destroyed. The required parameter for this procedure is: The return value for this procedure is: Traversing a List Three procedures let you traverse (iterate through) the elements of the list, regardless of whether or not it is sorted. The first one–DblLnkLst_iteratorStart–prepares the list to be traversed. It doesn’t return any data. Think of this function as a declaring a cursor to traverse all or some of the elements of your list. The second one–DblLnkLst_iteratorNext–is the one you use to fetch an element of the list in sequential order. It returns a null pointer if the end of the list is reached. The last one–DblLnkLst_iteratorStop–ends the iteration before the last element is reached. It can be useful if you just want only a number of elements, i.e., the 10 first elements, instead of all of them. 1. DblLnkLst_iteratorStart: Starts an iteration session. This function prepares the list to be traversed. The required parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_iteratorNext: Returns the next element in the iteration session. The required parameter for this procedure is: The return value for this procedure is: 3. DblLnkLst_iteratorStop: Ends an iteration session. The required parameter for this procedure is: The return value for this procedure is: Retrieving Information About Your List Several procedures retrieve useful information about a list. 1. DblLnkLst_empty: Indicates whether a list is empty or not. The required parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_size: Returns the number of elements in the list. The required parameter for this procedure is: The return value for this procedure is: 3. DblLnkLst_getMin: Finds and returns the minimum data value of all a list’s elements based on the current comparator procedure active for the list. If there is not a user-defined comparison procedure, the default one provided within DBLLNKLST service program will be used. The required parameter for this procedure is: The return value for this procedure is: 4. DblLnkLst_getMax: Finds and returns the maximum data value of all the list’s elements based on the current comparator procedure active for the list. If there is not a user defined comparison procedure, the default one provided within DBLLNKLST service program will be used. The required parameter for this procedure is: The return value for this procedure is: Sorting A List As described in Part 1, the supplied procedure to sort lists is DblLnkLst_sort. This procedure autonomously chooses which algorithm is best suited for sorting the list between QuickSort and SelectionSort algorithms. SelectionSort is an in-place comparison sort that is noted for its simplicity. It performs better than more complicated algorithms when sorting small lists–say 25 elements or fewer–but is inefficient on large lists. The selection sort algorithm finds the minimum value in a list and swaps it with the value in the first element, then repeats the same steps for the second and subsequent elements in the list. QuickSort is a divide and conquer algorithm that relies on a partition operation. QuickSort chooses an element, called a pivot, moves all lesser elements before the pivot and all greater elements after it, then recursively sorts the two sublists. This process is done efficiently in both time and memory. Optionally, you can use DblLnkLst_changeComparator function to change the comparison function and then sort the list with an alternative order. 1. DblLnkLst_sort: Sorts a list based on the current comparator procedure that is active for the list. If there is not a user-defined comparison procedure, the default comparator procedure provided within DBLLNKLST service program will be used. The required parameter for this procedure is: The return value for this procedure is: 2. DblLnkLst_changeComparator The required parameters for this procedure are: The return value for this procedure is: Saving and Restoring a List Finally, two procedures save (serialize) a list to permanent storage and restore a saved list. Since the DBLLNKLST service program doesn’t know the nature (the kind) of each element’s data, Miguel chose to use a user space as the permanent storage object. This approach gives enough flexibility to store lists of any kind regardless of data type and length. This procedure does not create the user space, so you must create the user space and retrieve a pointer to the user space before calling these procedures. Use the QUSCRTUS and QUSPRTUS APIs to accomplish these tasks. 1. list_serialize_tospc: Serialize the list into a *USRSPC object. The required parameters for this procedure are: The return value for this procedure is: 2. list_restore_fromspc: Restore the list from a *USRSPC object. The required parameter for this procedure is: The return value for this procedure is: Creating the Service Program To create the DBLLNKLST service program, you will need to load the following source members onto your system.
The DBLLNKLST service program relies on two copy members: T_LNKLST and DBLLNKLST. Your programs will have to use either the /COPY or /INCLUDE compiler directives in order to have the procedure prototypes for the subprocedures. Since IBM does not have a standard source physical file name for copybooks, Miguel named his file QRPGLECPY. If your shop has a standard, be sure to adjust the /INCLUDE directives accordingly. The T_LNKLST copybook contains the definitions for all the data types required for creating and manipulating a generic list object. The DBLLNKLST copybook has the specific procedures to create and manipulate doubly-linked lists. The names of the exported procedures of the DBLLNKLST copybook begin with DblLnkLst_. Miguel used this convention in order to accommodate other kinds of lists in the future. Once you’ve loaded the source code to your system, you’re ready to create the service program. First, create a module.
CRTRPGMOD MODULE(xxx/DBLLNKLST)
SRCFILE(xxx/XRPGLESRC)
SRCMBR(DBLLNKLST)
Then create the service program from the module and the binder language.
CRTSRVPGM SRVPGM(xxx/DBLLNKLST) +
MODULE(xxx/DBLLNKLST)
SRCFILE(xxx/QSRVSRC)
You no longer need the module, and you can delete it. An Example Now you’re ready to add a doubly-linked list to an application of your own. To help you get started, here’s a module that creates a doubly-linked list from the data in file QIWS/QCUSTCDT.
//==================================================================//
// CRTRPGMOD MODULE(xxx/CUST_LIST) //
// SRCFILE(xxx/XRPGLESRC) //
// SRCMBR(DBLLNKLST) //
// //
// CRTPGM PGM(xxx/CUST_LIST) //
// MODULE(xxx/CUST_LIST) //
// BNDSRVPGM(xxx/DBLLNKLST) //
// ACTGRP(xxxxxx) //
//==================================================================//
H DatFmt( *iso ) TimFmt( *iso ) DecEdit( '0,' ) AlwNull( *UsrCtl )
H Option( *noDebugIO : *SrcStmt )
fqCustCDT if e Disk ExtFile( 'QIWS/QCUSTCDT' )
FqPrint o f 132 Printer UsrOpn
/include qrpglecpy,t_LnkLst
/include qrpglecpy,DblLnkLstH
//------------------------------------------------------------------//
//Define the data each node of the list will contain //
//------------------------------------------------------------------//
d lstRcd_t ds Qualified
d name 15a
d street 15a
d city 6a
d state 2a
d zipcod 5s 0
//==================================================================//
//Procedure prototypes //
//==================================================================//
d main pr ExtProc( 'CUST_LIST' )
d elem_comparator...
d pr 10i 0
d a_p * Value
d b_p * Value
d size 10i 0 Const
d seq 10i 0 Options( *nopass )
d Const
d END_testActGrp...
d Pr ExtProc( 'CEETREC' )
//==================================================================//
//Global variables //
//==================================================================//
d custRcd e ds ExtName( qCustCDT : *input )
d this_LnkLst s Like( linklist_t )
d elem ds Likeds( lstRcd_t )
d elem_p s * Inz( %addr( elem ))
d minElem ds Likeds( lstRcd_t )
d Based( min_p )
d maxElem ds Likeds( lstRcd_t )
d Based( max_p )
d fstElem ds Likeds( lstRcd_t )
d Based( fst_p )
d lstElem ds Likeds( lstRcd_t )
d Based( lst_p )
d prt ds Likeds( lstRcd_t )
d Based( prt_p )
d idx s 5i 0
//==================================================================//
//Begin main routine //
//==================================================================//
d main pi
/free
// Create a linked list.
this_LnkLst = DblLnkLst_init( %len( elem ) :
%paddr( elem_comparator ));
// Load the linked list
setll 1 qCustCDT;
dou %eof( qCustCDT );
read qCustCDT custRcd;
if %eof( qCustCDT );
leave;
endif;
elem.name = %trim( LSTNAM ) + ', ' + INIT;
elem.street = STREET;
elem.city = CITY;
elem.state = STATE;
elem.zipcod = ZIPCOD;
DblLnkLst_append( this_LnkLst : elem_p );
enddo;
// Print the linked list
open qPrint;
except Head;
if DblLnkLst_iteratorStart( this_LnkLst ) = DBLLNKLST_OK;
prt_p = DblLnkLst_iteratorNext( this_LnkLst );
dow prt_p <> *null;
except Detail;
prt_p = DblLnkLst_iteratorNext( this_LnkLst );
enddo;
endif;
min_p = DblLnkLst_getMin( this_LnkLst );
max_p = DblLnkLst_getMax( this_LnkLst );
except MaxMin;
fst_p = DblLnkLst_fetchFirst( this_LnkLst );
lst_p = DblLnkLst_fetchLast( this_LnkLst );
except FstLst;
close qPrint;
// Sort and print the linked list
DblLnkLst_sort( this_LnkLst );
open qPrint;
except Head;
if DblLnkLst_iteratorStart( this_LnkLst ) = DBLLNKLST_OK;
prt_p = DblLnkLst_iteratorNext( this_LnkLst );
dow prt_p <> *null;
except Detail;
prt_p = DblLnkLst_iteratorNext( this_LnkLst );
enddo;
endif;
min_p = DblLnkLst_getMin( this_LnkLst );
max_p = DblLnkLst_getMax( this_LnkLst );
except MaxMin;
fst_p = DblLnkLst_fetchFirst( this_LnkLst );
lst_p = DblLnkLst_fetchLast( this_LnkLst );
except FstLst;
close qPrint;
// Sort the list in descending order and print it
DblLnkLst_sort( this_LnkLst : DBLLNKLST_SORT_DES );
open qPrint;
except Head;
if DblLnkLst_iteratorStart( this_LnkLst ) = DBLLNKLST_OK;
prt_p = DblLnkLst_iteratorNext( this_LnkLst );
dow prt_p <> *null;
except Detail;
prt_p = DblLnkLst_iteratorNext( this_LnkLst );
enddo;
endif;
min_p = DblLnkLst_getMin( this_LnkLst );
max_p = DblLnkLst_getMax( this_LnkLst );
except MaxMin;
fst_p = DblLnkLst_fetchFirst( this_LnkLst );
lst_p = DblLnkLst_fetchLast( this_LnkLst );
except FstLst;
close qPrint;
// Delete the linked list
if DblLnkLst_clear( this_LnkLst ) = DBLLNKLST_OK;
DblLnkLst_destroy( this_LnkLst );
endif;
END_TestActGrp( );
*inlr = *on;
/end-free
//==================================================================//
OqPrint E Head 2
O 32 'Name '
O +1 'Street '
O +1 'City '
O +1 'ST'
O +1 'zipcod'
O E Head 1
O 32 '---------------'
O +1 '---------------'
O +1 '------'
O +1 '--'
O +1 '------'
O E Detail 1
O prt.name 32
O prt.street +1
O prt.city +1
O prt.state +1
O prt.zipcod +1
O E MaxMin 3
O 28 'MinElem:'
O minElem.zipcod +1
O +4 'MaxElem:'
O maxElem.zipcod +1
O E FstLst 3
O 28 'FirstElem:'
O fstElem.zipcod +1
O +3 'LastElem:'
O lstElem.zipcod +1
//==================================================================//
//Procedure....: elem_comparator //
//Description..: Compare two elements //
//==================================================================//
p elem_comparator...
p b
d pi 10i 0
d a_p * Value
d b_p * Value
d size 10i 0 Const
d seq 10i 0 Options( *nopass )
d Const
//local variables
d a ds Likeds( lstRcd_t )
d Based( a_p )
d b ds Likeds( lstRcd_t )
d Based( b_p )
d result s 10i 0 Inz( 0 )
/free
if a.zipcod < b.zipcod;
result = -1;
elseif a.zipcod > b.zipcod;
result = 1;
else;
if a.city < b.city;
result = -1;
elseif a.city > b.city;
result = 1;
endif;
endif;
if %parms( ) >= 4;
result *= seq;
endif;
return result;
/end-free
p e
You’ll need to read through the code to understand it, of course, but allow us to give an overall explanation.
We’ll leave it to you to work through the code on your own. There are more examples in the downloadable code. That’s How It’s Done This article and its predecessor should give you a good foundation from which to learn about pointer-based data structures, especially linked lists. By using Miguel’s DBLLNKLST service program, you can easily integrate linked lists into your programs. Miguel has done the hard part. Your job is as easy as calling subprocedures. And even though DBLLNKLST is written in RPG, it is also available to other ILE languages. Have fun! Miguel Ortiz-Martin has been working as a software developer in AS/400 environments since 1990. He is currently employed by SEMPSA, a Spanish subsidiary of British Cookson Group, in Madrid, Spain. Send your questions or comments for Miguel to Ted Holt via the IT Jungle Contact page. RELATED STORIES A Reusable Routine for Doubly-Linked Lists, Part 1 Implementing Binary Trees in RPG Implementing Linked Lists in RPG
|
