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;
} // _deleteand 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);