6828l1.txt0100664000175300003300000000166510152737376011474 0ustar jillljeditListing 1. Function to Insert a New Node void insertAfter(plistNode pNew, T theElm) { plistNode pPrev, pCurrent, pNext; pPrev = NULL; pCurrent = pStart; while (pCurrent) { pNext = NextNode(pCurrent, pPrev); if (pCurrent->elm == theElm) { /* traversal is done */ if (pNext) { /* fix the existing next node */ pNext->ptrdiff = (plistNode) ((int) pNext->ptrdiff ^ (int) pCurrent ^ (int) pNew); /* fix the current node */ pCurrent->ptrdiff = (plistNode) ((int) pNew ^ (int) pNext ^ (int) pCurrent->ptrdiff); /* fix the new node */ pNew->ptrdiff = (plistNode) ((int) pCurrent ^ (int) pNext); break; } pPrev = pCurrent; pCurrent = pNext; } } 6828l2.txt0100664000175300003300000001503610152737366011471 0ustar jillljedit/* Created by Anjuta version 0.1.7 */ /* This file will not be overwritten */ #include #include #include #include // use a single ptr to traverse back and forth // ////////////////////////////////////////////// // | 0 | | 1 | | 2 | | 3 | | 4 | | 5 | // |-----| |-----| |-----| |-----| |-----| |-----| // |(1^0)| |(2^0)| |(3^1)| |(4^2)| |(5^3)| |(4^0)| // // Numerator of a node is the element. // (m^n) is the exclusive or of ptr to m, and ptr to n. // pStart points to element 0, pEnd points to 5 in this example // // // pStart = pEnd = NULL => list is empty // pStart = pEnd <> NULL => list is singleton typedef int T; // // dbly link represented by ptr distance // typedef struct listNode{ T elm; struct listNode * ptrdiff; }; typedef struct listNode *plistNode; // // conventional dbly link representaion // typedef struct dlistNode { T elm; struct dlistNode *next; struct dlistNode *prev; }; typedef struct dlistNode *pdlistNode; // //globls for ptrdiff ds plistNode pStart, pEnd; //glbls for conventional pdlistNode pdHead, pdEnd; // * for ptrdiff plistNode NextNode( plistNode pNode, plistNode pPrevNode) { return ((plistNode) ((int) pNode->ptrdiff ^ ( int)pPrevNode) ); } //conventional pdlistNode dNextNode ( pdlistNode pdNode) { return (pdNode->next ); } pdlistNode dPrevNode ( pdlistNode pdNode) { return (pdNode->prev ); } // ptr.dist list delete void delList () { // plistNode pPrev, pCurrent; pPrev = NULL; pCurrent = pStart; while ( pCurrent ) { pCurrent->ptrdiff = NextNode( pCurrent, pPrev); if (pPrev) free(pPrev); if ( !pCurrent->ptrdiff ){ printf(" Final node being deleted in prt.dist. =%d\n", pCurrent->elm); free(pCurrent); pCurrent = NULL; continue; } pPrev = pCurrent; pCurrent = pCurrent->ptrdiff; } } // conventional list delete void ddelList() { pdlistNode pdCurrent, pdNext; pdCurrent = pdHead; while (pdCurrent) { pdNext = dNextNode(pdCurrent); free(pdCurrent); pdCurrent = pdNext; } } // for dist. ptr. void insertAfter ( plistNode pNew, T theElm ) { plistNode pPrev, pCurrent, pNext; pPrev = NULL; pCurrent = pStart; while (pCurrent) { pNext = NextNode(pCurrent, pPrev); if (pCurrent->elm == theElm ) { /*fw traversal is done */ // if (pNext ) { // fix the existing next node pNext->ptrdiff = (plistNode) ((int)pNext->ptrdiff ^ ( int) pCurrent ^ (int)pNew ); } //fix the current node pCurrent->ptrdiff = (plistNode) ((int)pNew ^ (int)pNext ^ (int)pCurrent->ptrdiff); //fix the new node pNew->ptrdiff = (plistNode) ( (int)pCurrent ^ (int)pNext ); break; } pPrev = pCurrent; pCurrent = pNext; } } // * for conventional insertAfter() void dinsertAfter(pdlistNode pdNew, T theElm ) { pdlistNode pdPrev, pdCurrent, pdNext; pdCurrent= pdHead; while (pdCurrent) { pdNext = dNextNode(pdCurrent); if (pdCurrent->elm == theElm ) { if (pdNext ) {//fix the existing next node pdNext->prev = pdNew; } //fix the current node pdCurrent->next = pdNew; //fix the new node pdNew->next = pdNext; pdNew->prev = pdCurrent; break; } pdCurrent = pdNext; } } // ptr. dist. struct. traversal void traverse( plistNode pRoot ) { // plistNode pCurrent, pPrev, pNext; pPrev = NULL; pCurrent = pRoot; while (pCurrent) { //printf(" -> %d\n", pCurrent->elm) ; pNext = NextNode(pCurrent, pPrev ); pPrev = pCurrent; pCurrent = pNext; } } // conventional forward traversal void dtraversefw( pdlistNode pdHead ) { // pdlistNode pCurrent; pCurrent = pdHead; while (pCurrent) { //printf(" -> %d\n", pCurrent->elm) ; pCurrent = dNextNode(pCurrent); } } // conventional backward traversal void dtraversebw( pdlistNode pdHead ) { // pdlistNode pCurrent; pCurrent = pdHead; while (pCurrent) { //printf(" -> %d\n", pCurrent->elm) ; pCurrent = dPrevNode(pCurrent); } } // // dist. ptr. insertion void insert( T elm) { // plistNode pnewNode = (plistNode)malloc(sizeof(struct listNode) ); if (! pnewNode) { printf(" malloc failed in insert( T elm) \n"); return; } pnewNode->elm = elm; pnewNode->ptrdiff = NULL; //brand new if ( !pStart ) { pStart = pEnd = pnewNode; }else { insertAfter( pnewNode, pEnd->elm); pEnd = pnewNode; } return ; } //conventional insert void dinsert ( T elm) { pdlistNode pdnewNode = (pdlistNode)malloc(sizeof(struct dlistNode) ); if (! pdnewNode) return; pdnewNode->elm = elm; pdnewNode->next = pdnewNode->prev = NULL; //brand new if ( !pdHead ) { pdHead = pdEnd = pdnewNode; }else { dinsertAfter(pdnewNode, pdEnd->elm ); pdEnd = pdnewNode; } return ; } #define NO_OF_ITEM_IN_LIST 30000 //#define EXERCISE_PTR_DIST 1 void doTimeStamp (char * strArg) { char *pcharTime ; time_t c_time; time(&c_time); pcharTime = ctime(&c_time); printf("%s %s\n",strArg, pcharTime); } // exercise the conventional struct void exerciseDlist() { char *pcharTime ; time_t c_time; int i; doTimeStamp("Before conventional insert() " ); for (i = 0; i < NO_OF_ITEM_IN_LIST; i++) dinsert ( (T) i ); doTimeStamp("After conventional insert() " ); printf ("Total Memory taken by conventional structure = %d bytes.\n", NO_OF_ITEM_IN_LIST *sizeof(struct dlistNode) ); //forward doTimeStamp("Before conventioal dtraversefw(pdHead ) " ); dtraversefw(pdHead ); doTimeStamp("After conventioal dtraversefw(pdHead ) " ); //backward doTimeStamp("Before conventioal dtraversebw(pdEnd) " ); dtraversebw(pdEnd); doTimeStamp("After conventioal dtraversebw(pdEnd) " ); //delete doTimeStamp("Before conventioal ddelList () " ); ddelList (); doTimeStamp("After conventioal ddelList () " ); } void exerciseDistptrlist() { int i; doTimeStamp("Before insert(prt.dist.)"); // exercise the ptr distance structure for (i = 0; i < NO_OF_ITEM_IN_LIST ; i++) insert ( (T) i ); doTimeStamp( "After insert(prt.dist.)" ); printf ("Total Memory taken by ptr distance structure = %d bytes.\n", NO_OF_ITEM_IN_LIST *sizeof(struct listNode) ); //forward traversal doTimeStamp ("Before traverse(pStart) of (prt.dist.) "); traverse(pStart); doTimeStamp( "After traverse(pStart) of(prt.dist.) "); //backward traversal doTimeStamp("Before traverse(pEnd) of (prt.dist.) "); traverse(pEnd); doTimeStamp( "After traverse(pEnd) of (prt.dist.) "); //delete the whole list doTimeStamp( "Before delList () of (prt.dist.) "); delList (); doTimeStamp("After delList () of (prt.dist.) "); } int main() { //exerciseDlist(); #ifdef EXERCISE_PTR_DIST exerciseDistptrlist(); #else exerciseDlist(); #endif printf("Hello world\n"); return (0); }