-
Doubly linked list woes
Hi all,
Just having a few dramas with doubly linked lists. I am just trying to write an insert function with the following structures. The insert function does not have to insert the data into a sorted list, so basically it can just add another node to the end of a list.
The trouble I am having is that I figure I can use a for loop to loop through the list until I find the last node.. but my logic is not right. Can anyone make some suggestions?
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#define MAX 50 // The maximum size of the arrays in the struct
typedef struct list DLL;
typedef struct node NODE;
struct node
{
void *data;
NODE *prior;
NODE *next;
};
struct list
{
long int count;
NODE *head;
NODE *tail;
};
typedef struct
{
long int id;
char name[MAX];
char address[MAX];
float salary;
} PERSON;
typedef struct
{
PERSON details;
char department[MAX];
char position[MAX];
} EMPLOYEE;
void init_list(DLL *);
int insert(DLL *, void*, size_t);
int main(void)
{
DLL *pMylist;
EMPLOYEE *pEmployees;
if ((pMylist = (DLL *) malloc (sizeof(DLL))) == NULL)
{
printf("Error: Unable to allocate memory");
exit(1);
}
if ((pEmployees = (EMPLOYEE *) malloc (sizeof(EMPLOYEE))) == NULL)
{
printf("Error: Unable to allocate memory");
exit(1);
}
init_list (pMylist);
printf("Enter a number: ");
while (pEmployees->details.id != 999)
{
scanf("%d", &pEmployees->details.id);
insert(pMylist, pEmployees, sizeof(EMPLOYEE));
printf("Enter a number: ");
}
free (pMylist);
free (pEmployees);
return EXIT_SUCCESS;
}
// The function with all the dramas :)
int insert(DLL *pRoot, void *pData, size_t size)
{
NODE *pNewnode;
NODE *pThis;
NODE *pNext;
// Allocate memory for a new node in the list
if ((pNewnode = (NODE *) malloc(sizeof(NODE))) == NULL)
{
printf("Error: Unable to allocate memory for pNewnode");
exit(EXIT_FAILURE);
}
// Allocate memory for the input from user
if ((pNewnode->data = malloc(size)) == NULL)
{
printf("Error: Unable to allocate memory for pNewnode->data");
exit(EXIT_FAILURE);
}
// Copy user input to node
memcpy(pNewnode->data, pData, size);
// If the first node
if (pRoot->head == NULL)
{
printf("this is the start of a beautiful list");
pRoot->head = pNewnode;
return 1;
}
else
{
// This loop is erroneous
for (pThis = (pRoot->head); (pNext = pThis->next) != NULL; pThis = pNext)
{
// Insert next in list
}
}
return 1;
}
void init_list(DLL *pMylist)
{
pMylist->count = (long) NULL;
pMylist->head = NULL;
pMylist->tail = NULL;
}
This is not the final code obviously, it is a test program to demonstrate the issues that I am having so there could be some other unusual things happening in this code ;)
-
Ok - Got it working! Thanks goes to Salem for a post to a previous thread which held the answer! (Should have used search..)
Ok - new problem. I have modified the insertion code - all I want to do is insert the new data at the end of the list.. no sorting required at this stage.
However - This function is supposed to be generic, so regardless of what kind of data the user of this function wants to store in list, it should be able to do it.
For example I can have a root node:
DLL *root;
internally (not visible to the user) the list is made of nodes of type NODE * as declared in the above code, but the user should be able to create their own lists by passing their data of any type to the function, for example:
EMPLOYEE *pEmployees;
or
int *pTest;
My problem is that the function works fine when I am passing data of type EMPLOYEE *, but if I try to pass a pointer of type int * it fails on the memcpy. Any ideas??
Code:
int insert(DLL *pRoot, void *pData, size_t size)
{
NODE *pNewnode;
// Allocate memory for the next node in the list
if ((pNewnode = (NODE *) malloc(sizeof(NODE))) == NULL)
{
printf("Error: Unable to allocate memory for pNewnode");
fflush(stdout);
exit(EXIT_FAILURE);
}
// Allocate memory for the input from user
if ((pNewnode->data = malloc(size)) == NULL)
{
printf("Error: Unable to allocate memory for pNewnode->data");
fflush(stdout);
exit(EXIT_FAILURE);
}
pNewnode->next = NULL;
pNewnode->prior = NULL;
// Copy the data to the new node
memcpy(pNewnode->data, pData, size);
if (pRoot->head == NULL)
{
pRoot->head = pNewnode;
pRoot->tail = pNewnode;
pRoot->count = 1;
}
else
{
pNewnode->prior = pRoot->tail;
pRoot->tail->next = pNewnode;
pRoot->tail = pNewnode;
pRoot->count += 1; // Increase the count for the number of nodes
}
return 1;
}
-
Look at the flagbits (about 12 bytes worth of info) prepended to the block to tell how big it is. Then just copy that size. coerce to void pointers.
Think generic.
---
If you don't know enough to walk the block pointer for its flagbits, then create a macro that caller calls instead which does a 'sizeof()' of their datablock and then passes the address and the size to your 'insert' function.
enjoy
-
Thanks Sayeh, but I am going to have to plead ignorance here..
Could someone explain this to me?
Is the problem that I am having above the same as the one I am having with this code snippet? I assumed that by using the
sizeof operator I was passing the size of the users data?
Thanks again all :)
Code:
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct
{
void *data;
} NODE;
int main(void)
{
NODE *pNode;
int input;
pNode = (NODE *) malloc (sizeof(NODE));
pNode->data = malloc (sizeof(int));
// Tests for success of memory allocation go here..
printf("Enter an int: ");
scanf("%d", &input);
memcpy (pNode->data, input, sizeof(input));
printf("The number is : %d", pNode->data);
return 0;
}