ezekit 0 Newbie Poster

SO im trying to get this source code transformed to a double link list
it has two nodes sentinel and header....the source code was used to be a singly linked list.....

nyhow i cant seeem to get this whole thing right..... it works fine when it was on its orginal state but now that ihave changed it...well u get the idea...

just wondering if i did all the pointers right since for the function ...traverse.. insert..may have problems because when u print datas using travesre rather than having a complete 21 set(reading 21 set) it only shows 4
thnx

/*	
    This file contains the definitons of the functions to maintain
	and process a linked list:

    Public Functions:
        createList
        addNode
        removeNode
        searchList
        retrieveNode
        emptyList
        fullList
        listCount
        traverse
        destroyList

    Private Functions:
        _insert
        _delete
        _search
*/

#include <stdlib.h>

#include "linkListADT.h"   /* <== public functions */

/* private functions */
static int  _insert  (LIST*  pList, NODE* pPre,  NODE* pSuc, void* dataInPtr);
static void _delete  (LIST*  pList, NODE*  pPre, NODE*  pLoc, NODE* pSuc, void** dataOutPtr);
static int  _search  (LIST*  pList, NODE** pPre, NODE** pLoc, NODE** pSuc, void*  pArgu);



/* 
    =================================================
    ============== Public Functions =================
    =================================================
*/

/*	=============== createList ==============
	Allocates dynamic memory for a list head
	node and returns its address to caller
	   Pre    compare is address of compare function 
	          used to compare two nodes.
	   Post   head has allocated or error returned
	   Return head node pointer or null if overflow 
*/
LIST* createList (int (*compare) (void* argu1, void* argu2))
{
//	Local Definitions 
	LIST* list;
	NODE* lead;
	NODE* tail;


//	Statements 
	list = (LIST*) malloc (sizeof (LIST));
	lead = (NODE*) malloc (sizeof (NODE));
	tail = (NODE*) malloc (sizeof (NODE));

	if (list)
	   {
		list->head    = lead;
	    list->pos     = NULL;
	    list->rear    = tail;
	    list->count   = 0;

		lead->forw = tail;
		lead->prev = NULL;
		lead->dataPtr = NULL;

		tail->forw = NULL;
		tail->prev = lead;
		tail->dataPtr = NULL;
	    list->compare = compare;
	   } // if 
	
	return list;
}	// createList 

/*	================== addNode =================
	Inserts data into list.
	   Pre    pList is pointer to valid list
	          dataInPtr pointer to insertion data
	   Post   data inserted or error
	   Return -1 if overflow
	           0 if successful
	           1 if dupe key
*/
int addNode (LIST* pList, void* dataInPtr)
{
//	Local Definitions 
	int  found;
	int  success;
	
	NODE* pPre;
	NODE* pLoc;
	NODE* pSuc;
	
//	Statements 
	found = _search (pList, &pPre, &pLoc, &pSuc, dataInPtr);
	if (found)
	   // Duplicate keys not allowed 
	   return (+1);

	success = _insert (pList, pPre, pSuc, dataInPtr);
	if (!success)
	   // Overflow 
	   return (-1);
	return (0);
}	// addNode 


/*	================= removeNode ================ 
	Removes data from list. 
	   Pre    pList pointer to a valid list
	          keyPtr pointer to key to be deleted
	          dataOutPtr pointer to data pointer
	   Post   Node deleted or error returned.
	   Return false not found; true deleted
*/
int removeNode  (LIST*  pList, void*  keyPtr, void** dataOutPtr)
{
//	Local Definitions 
	int  found;
	
	NODE* pPre;
	NODE* pLoc;
	NODE* pSuc;
	
//	Statements 
	found = _search (pList, &pPre, &pLoc, &pSuc, keyPtr);
	if (found)
	   _delete (pList, pPre, pLoc, pSuc, dataOutPtr);
	
	return found;
}	// removeNode 


/*	================== searchList ================= 
	Interface to search function. 
	   Pre    pList pointer to initialized list.
	          pArgu pointer to key being sought
	   Post   pDataOut contains pointer to found data
	     -or- NULL if not found
	   Return boolean true successful; false not found 
*/
int searchList (LIST*  pList, void* pArgu, void** pDataOut)
{
//	Local Definitions 
	int  found;
	
	NODE* pPre;
	NODE* pLoc;
	NODE* pSuc;

//	Statements 
	found = _search (pList, &pPre, &pLoc, &pSuc, pArgu);
	if (found)
	    *pDataOut = pLoc->dataPtr;
	else
	    *pDataOut = NULL;
	return found;
}	// searchList 


/*	================== retrieveNode ================ 
	This algorithm retrieves data in the list without
	changing the list contents. 
	   Pre    pList pointer to initialized list.
	          pArgu pointer to key to be retrieved
	   Post   Data (pointer) passed back to caller
	   Return boolean true success; false underflow
*/
int  retrieveNode (LIST*  pList, void*  pArgu, void** dataOutPtr)
{
//	Local Definitions 
	int  found;
	
	NODE* pPre;
	NODE* pLoc;
	NODE* pSuc;
	
//	Statements 
	found = _search (pList, &pPre, &pLoc, &pSuc, pArgu);
	if (found)
	   {
	    *dataOutPtr = pLoc->dataPtr;
	    return 1;
	   } // if 

	*dataOutPtr = NULL;
	return 0;
}	// retrieveNode 

/*	================= emptyList ================
	Returns boolean indicating whether or not the
	list is empty
	   Pre    pList is a pointer to a valid list 
	   Return boolean true empty; false list has data 
*/
int emptyList (LIST* pList) 
{
//	Statements 
	return (pList->count == 0);
}	// emptyList 

/*	================== fullList =================
	Returns boolean indicating no room for more data.
	This list is full if memory cannot be allocated for
	another node. 
	   Pre    pList pointer to valid list 
	   Return boolean true if full
	                  false if room for node 
*/
int fullList (LIST* pList) 
{
//	Local Definitions 
NODE* temp;

//	Statements 
if ((temp = (NODE*)malloc(sizeof(*(pList->head->forw)))))
	   {
	    free (temp);
	    return 0;
	   } // if 

	// Dynamic memory full 
	return 1;

}	// fullList 

/*	================== listCount ==================
	Returns number of nodes in list.
	   Pre    pList is a pointer to a valid list
	   Return count for number of nodes in list
*/
int listCount(LIST* pList) 
{
//	Statements 

	return pList->count; 
	
}	// listCount 

/*	================== traverse =================
	Traverses a list. Each call either starts at the
	beginning of list or returns the location of the 
	next element in the list.
	   Pre    pList       pointer to a valid list
	          fromWhere   0 to start at first element
	          dataPtrOut  address of pointer to data
	   Post   if more data, address of next node 
	   Return true node located; false if end of list
*/
int traverse (LIST*  pList,
              int    fromWhere,
              void** dataPtrOut)
{
//	Statements 
	if (pList->count == 0)
	    return 0;

	if (fromWhere == 0)
	   {
		 //Start from first node 
	    pList->pos  = pList->head->forw;
	    *dataPtrOut = pList->pos->dataPtr;
	    return 1;
	   } // if fromwhere 
	else
	   {
	    // Start from current position 
	    if (pList->pos->forw == pList->rear)
	        return 0;
	    else
	       {
	        pList->pos  = pList->pos->forw;
	        *dataPtrOut = pList->pos->dataPtr;
	        return 1;
	       } // if else 
	   } // if fromwhere else 
}	// traverse 

/*	================== destroyList =================
	Deletes all data in list and recycles memory
	   Pre    List is a pointer to a valid list.
	   Post   All data and head structure deleted
	   Return null head pointer
*/
LIST* destroyList (LIST* pList) 
{
//	Local Definitions 
	NODE* deletePtr;

//	Statements 
	if (pList)
	   {
	    while (pList->count > 0) 
	       {
	        // First delete data 
	        free (pList->head->dataPtr);
 
	        // Now delete node 
	        deletePtr    = pList->head;
	        pList->head  = pList->head->forw; 
	        pList->count--;
	        free (deletePtr); 
	       } // while 
	    free (pList);
	   } // if 
	return NULL;
}	// destroyList 

/* 
    =================================================
    ============== Private Functions ================
    =================================================
*/
/*	================== _search =================
	Searches list and passes back address of node 
	containing target and its logical predecessor.
	   Pre    pList pointer to initialized list 
	          pPre  pointer variable to predecessor
	          pLoc  pointer variable to receive node
	          pArgu pointer to key being sought
	   Post   pLoc points to first equal/greater key 
	     -or- null if target > key of last node
	          pPre points to largest node < key
	     -or- null if target < key of first node
	   Return boolean true found; false not found 

*/
static int _search (LIST*  pList, NODE** pPre, NODE** pLoc, NODE** pSuc,  void*  pArgu)
{
//	Macro Definition 
//#define COMPARE      ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) )
#define COMPARE      ( pList->compare(pArgu, (*pLoc)->dataPtr) )

//#define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr))
#define COMPARE_LAST ( pList->compare(pArgu, pList->rear->prev->dataPtr) )

//	Local Definitions 
	int result;

//	Statements 
	*pPre  = pList->head;
	*pLoc  = pList->head->forw;
	*pSuc  = pList->rear;
	if (pList->count == 0)
	    return 0;

	// Test for argument > last node in list 
	if ( COMPARE_LAST > 0) 
	   {
		*pPre = pList->rear->prev;
		*pLoc = NULL;
		*pSuc = pList->rear;
	    return 0;
	   } // if 

	while ( (result = COMPARE) > 0 )
	   {
	    // Have not found search argument location 
	    *pPre = *pLoc;
		*pLoc = (*pLoc)->forw;
		*pSuc = (*pLoc)->forw;
	   } // while 
	
	if (result == 0)
	   // argument found--success 
	   return 1;
	else
	   return 0;
}	// _search 

/*	=================== _insert ================== 
	Inserts data pointer into a new node.
	   Pre    pList pointer to a valid list 
	          pPre  pointer to data's predecessor 
	          dataInPtr data pointer to be inserted 
	   Post   data have been inserted in sequence 
	   Return boolean, true  if successful, 
	                   false if memory overflow 
*/
static int _insert (LIST* pList, NODE* pPre, NODE* pSuc, 
                     void* dataInPtr)
{
//	Local Definitions 
	NODE* pNew;

//	Statements 
	if (!(pNew = (NODE*) malloc(sizeof(NODE))))
	   return 0;

	pNew->dataPtr   = dataInPtr; 
	pNew->forw      = pSuc;
	pNew->prev		= pPre;
	pPre->forw      = pNew;
	pSuc->prev      = pNew;

	(pList->count)++;
	return 1;
}	// _insert 

/*	================= _delete ================ 
	Deletes data from a list and returns 
	pointer to data to calling module.
	   Pre    pList pointer to valid list.
	          pPre  pointer to predecessor node
	          pLoc  pointer to target node
	          dataOutPtr pointer to data pointer
	   Post   Data have been deleted and returned 
	          Data memory has been freed
*/
void _delete (LIST* pList, NODE*  pPre,
              NODE* pLoc,  NODE* pSuc, void** dataOutPtr)
{
//	Statements 
	*dataOutPtr = pLoc->dataPtr;
	pPre->forw = pLoc->forw;
	pSuc->prev = pLoc->prev;
		 

	(pList->count)--;
	free (pLoc);

	return;
}	// _delete

and here is the header file

/*	
    This header file contains the functions to maintain
	and process a linked list.
*/

//  Singly-Linked List ADT Type Definitions 


typedef struct node 
{
	struct node* prev;
	struct node* forw;
	void *dataPtr;
} NODE; 

typedef struct
{
	int   count; 
	NODE* pos;
	NODE* head; 
	NODE* rear;
	int    (*compare) (void* argu1, void* argu2); 
} LIST;

//  List ADT Prototype Declarations: public functions 
	LIST* createList   (int (*compare)
	                   (void* argu1, void* argu2));

	LIST* destroyList  (LIST* list);

	int   addNode   (LIST* pList, void* dataInPtr);

	int   removeNode   (LIST*  pList,
	                    void*  keyPtr,
	                    void** dataOutPtr);

	int   searchList   (LIST*  pList,
	                    void*  pArgu,
	                    void** pDataOut);

	int   retrieveNode (LIST*  pList,
	                    void*  pArgu,
	                    void** dataOutPtr);

	int   traverse     (LIST*  pList,
	                    int    fromWhere,
	                    void** dataOutPtr);

	int   listCount    (LIST*  pList);
	int   emptyList    (LIST*  pList);
	int   fullList     (LIST*  pList);
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.