casting struct to struct

hi,

I have an exercise in C for my course in Software Development. I can't seem to figure this one out though...

I need to write a generic double linked list. Now I know C isn't very keen on generics, but here's what the task says:

Part 1:

"Create a linked list of struct listhdr elements by implementing the following functions. These expect as their firs argument the 'anchor' of your linked list. This is an element that simultaneously marks the start and end of the list. The next pointer points to the first element in the list, the prev pointer points to the last. In an empty list both point to the 'anchor' itself."

Code:

---

struct listhdr {
  struct listhdr *prev, *next;
};
 
void linkedlist_init(struct listhdr *list);
void linkedlist_insert(struct listhdr *list, struct listhdr *item, struct listhdr *newitem);
void linkedlist_addfront(struct listhdr *list, struct listhdr *item);
void linkedlist_addtail(struct listhdr *list, struct listhdr *item);
void linkedlist_remove(struct listhdr *list, struct listhdr *item);
void linkedlist_swap(struct listhdr *list, struct listhdr *a, struct listhdr *b);

---

Part 2:

"You can use this implementation to create linked list of arbitrary structures (ie. struct mydata), without needing to modify the code from part one. This is possible by adding a field of type struct listhdr in the beginning of your own datastructure (see example). You can simply cast your structure to a struct listhdr (because the first element is a struct listhdr)"

Code:

---

struct mydata {
  struct listhdr list;
  int myint;
  float myfloat;
  ...
};

---

I've failed to find any info on casting structures to other struct types. Does anyone know how this works?

I've tried creating and casting the structs, but can't get it to work any way...

thx in advance

Have you finished doing PART 1 ?
http://c-faq.com/struct/oop.jxh.html

I did a couple of weeks ago when I was first working on this problem, but I lost my source. I'm doing it again right now, should be ready soon.

Last time I tried part 1 didn't seem to be the problem though. I didn't manage to get through part 2 though.

implementation of part 1:

Code:

---

#include "general.h"
#include "LinkedList.h";
#include "LinkedListEntry.h";

/*
struct listhdr {
  struct listhdr *prev, *next;
};
*/

void linkedlist_init(struct listhdr *list){

        list->next=list;
        list->prev=list;
}
void linkedlist_insert(struct listhdr *list, struct listhdr *item, struct listhdr *newitem){
       
        struct listhdr * node=list;

        while(node!=item && node->next!=list)
                node=node->next;

        if(node!=item)                /*        item could not be found in list        */
                return;

        newitem->next=node;
        newitem->prev=node->prev;

        node->prev->next=newitem;
        node->prev=newitem;

}
void linkedlist_addfront(struct listhdr *list, struct listhdr *item){

        item->prev=list;
        item->next=list->next;

        list->next->prev=item;
        list->next=item;

}
void linkedlist_addtail(struct listhdr *list, struct listhdr *item){

        item->prev=list->prev;
        item->next=list;

        list->prev->next=item;
        list->prev=item;

}
void linkedlist_remove(struct listhdr *list, struct listhdr *item){
       
        struct listhdr * node=list;

        while(node!=item && node->next!=list)
                node=node->next;

        if(node!=item)                /*        item could not be found in list        */
                return;

        item->next->prev=item->prev;
        item->prev->next=item->next;

        free(item);
        item=NULL;
}
void linkedlist_swap(struct listhdr *list, struct listhdr *a, struct listhdr *b){
       
        struct listhdr * node=list;

        while(node!=a && node->next!=list)
                node=node->next;

        if(node!=a)                /*        a could not be found in list        */
                return;
       
        node=list;
        while(node!=b && node->next!=list)
                node=node->next;

        if(node!=b)                /*        b could not be found in list        */
                return;


        if(a->next==b){

                node=a->prev;
                a->prev->next=b;
                b->prev=node;
               
                node=b->next;
                b->next->prev=a;
                a->next=node;

                b->next=a;
                a->prev=b;
        }
        else if(b->next==a){

                node=b->prev;
                b->prev->next=a;
                a->prev=node;
               
                node=a->next;
                a->next->prev=b;
                b->next=node;

                a->next=b;
                b->prev=a;
        }
        else{
                a->prev->next=b;
                a->next->prev=b;
               
                b->prev->next=a;
                b->next->prev=a;


                node=a->prev;
                a->prev=b->prev;
                b->prev=node;

                node=a->next;
                a->next=b->next;
                b->next=node;
        }

}

---

EDIT: fixed some errors

Quote:

---

Originally Posted by Bayint Naung

Have you finished doing PART 1 ?
OOP in C

---

jay!! that seems to be what the teach' is talking about :)

Thx alot, I can't believe I wasted like 6-7 hours on that one :s

Code:

---

        l=(struct listhdr *) malloc(sizeof(l));    // you mean sizeof(*l) ?

---

You don't need to cast malloc() return value.
I think your linkedlist_init() function does not need to allocate memory, since you are going to pass struct something whose first member is struct listhdr.

Code:

---

void linkedlist_init(struct listhdr *list)
{
  list->next = list->prev = NULL;
}

// usage , assuming linked list implementation has no problem ;)
struct mydata  list;
struct mydata  item;
linkedlist_init( (void*)&list); 
linkedlist_addfront( (void*)&list,    (void*)&item);

---

@Bayint Naung:

I didn't think the malloc cast was necessary, but it's done the same way in some of the examples we got in class.
And you were right about the init() function :)


Now I've been working on part 2...

I think I've got everything working, but there's one error still bugging me; I wrote (tried to) a destroy function for the linkedlist, but while I can free all list members, I cant seem to free the anchor. I keep getting this error on free(list):

Code:

---

HEAP CORRUPTION DETECTED: after Normal block (#54) at 0x003E3F88.
CRT detected that the application wrote to memory after end of heap buffer.

---

Here are my current source files:


LinkedList.h

Code:

---

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct listhdr {
  struct listhdr *prev, *next;
};
 
void linkedlist_init(struct listhdr *list);
void linkedlist_insert(struct listhdr *list, struct listhdr *item, struct listhdr *newitem);
void linkedlist_addfront(struct listhdr *list, struct listhdr *item);
void linkedlist_addtail(struct listhdr *list, struct listhdr *item);
void linkedlist_remove(struct listhdr *list, struct listhdr *item);
void linkedlist_swap(struct listhdr *list, struct listhdr *a, struct listhdr *b);

void linkedlist_destroy(struct listhdr *list);

void linkedlist_print(struct listhdr *list, int forward);
void linkedlist_print_forwards(struct listhdr *list);
void linkedlist_print_backwards(struct listhdr *list);

#endif

---

LinkedList.c

Code:

---

#include "general.h"
#include "LinkedList.h";
#include "LinkedListEntry.h";

/*
struct listhdr {
  struct listhdr *prev, *next;
};
*/

void linkedlist_init(struct listhdr *list){

        list->next=list;
        list->prev=list;
}
void linkedlist_insert(struct listhdr *list, struct listhdr *item, struct listhdr *newitem){
       
        struct listhdr * node=list;

        while(node!=item && node->next!=list)
                node=node->next;

        if(node!=item)                /*        item could not be found in list        */
                return;

        newitem->next=node;
        newitem->prev=node->prev;

        node->prev->next=newitem;
        node->prev=newitem;

}
void linkedlist_addfront(struct listhdr *list, struct listhdr *item){

        item->prev=list;
        item->next=list->next;

        list->next->prev=item;
        list->next=item;

}
void linkedlist_addtail(struct listhdr *list, struct listhdr *item){

        item->prev=list->prev;
        item->next=list;

        list->prev->next=item;
        list->prev=item;

}
void linkedlist_remove(struct listhdr *list, struct listhdr *item){
       
        struct listhdr * node=list;

        while(node!=item && node->next!=list)
                node=node->next;

        if(node!=item)                /*        item could not be found in list        */
                return;

        item->next->prev=item->prev;
        item->prev->next=item->next;

        free(item);
        item=NULL;
}
void linkedlist_swap(struct listhdr *list, struct listhdr *a, struct listhdr *b){
       
        struct listhdr * node=list;

        while(node!=a && node->next!=list)
                node=node->next;

        if(node!=a)                /*        a could not be found in list        */
                return;
       
        node=list;
        while(node!=b && node->next!=list)
                node=node->next;

        if(node!=b)                /*        b could not be found in list        */
                return;


        if(a->next==b){

                node=a->prev;
                a->prev->next=b;
                b->prev=node;
               
                node=b->next;
                b->next->prev=a;
                a->next=node;

                b->next=a;
                a->prev=b;
        }
        else if(b->next==a){

                node=b->prev;
                b->prev->next=a;
                a->prev=node;
               
                node=a->next;
                a->next->prev=b;
                b->next=node;

                a->next=b;
                b->prev=a;
        }
        else{
                a->prev->next=b;
                a->next->prev=b;
               
                b->prev->next=a;
                b->next->prev=a;


                node=a->prev;
                a->prev=b->prev;
                b->prev=node;

                node=a->next;
                a->next=b->next;
                b->next=node;
        }


}

void linkedlist_print_forwards(struct listhdr *list){               
        linkedlist_print(list, 1);
}
void linkedlist_print_backwards(struct listhdr *list){               
        linkedlist_print(list,0);
}
void linkedlist_print(struct listhdr *list, int forward){

        struct listhdr * node=list;                        /*        cast to (void *) ?        */

        printf("\n --------------------------------------------------------------------------");
        printf("\n|  ID  |    Voornaam    |          Familienaam          |      Tel      |");                /*        "| 4 | 16 | 30 | 13 |"        */
        printf("\n|--------------------------------------------------------------------------|");
        printf("\n|      |                  |                                |              |");

        while( (forward?(node->next!=list):(node->prev!=list)) ){
                node=(forward?node->next:node->prev);
                printf("\n| %4d | %-16s | %-30s | %13s |",
                        ((LLEntry *)node)->id,
                        ((LLEntry *)node)->name,
                        ((LLEntry *)node)->lastname,
                        ((LLEntry *)node)->tel
                        );
        }

        printf("\n|      |                  |                                |              |");
        printf("\n --------------------------------------------------------------------------");
       

}

void linkedlist_destroy(struct listhdr *list){

        while(list->next!=list){
                linkedlist_remove(list,list->next);
        }

        free(list);
        list=NULL;

}

---

LinkedListEntry.h

Code:

---

#ifndef LINKEDLISTENTRY_H
#define LINKEDLISTENTRY_H

struct LinkedListEntry{
        struct listhdr list;
       
        int id;
        char* name;
        char* lastname;
        char* tel;
};
typedef struct LinkedListEntry LLEntry;

LLEntry * LLE_init(int id, char* name, char* lastname, char* tel);

#endif

---

LinkedListEntry.c

Code:

---

#include "general.h"
#include "LinkedList.h"
#include "LinkedListEntry.h"


LLEntry * LLE_init(int id, char* name, char* lastname, char* tel){
        LLEntry * entry;

        entry=(LLEntry *)malloc(sizeof(struct LinkedListEntry));

        entry->id=id;
        entry->name=name;
        entry->lastname=lastname;
        entry->tel=tel;

        return entry;
}

---

general.h

Code:

---

#ifndef GENERAL_H
#define GENERAL_H

#define NULL ((void *)0)

#endif

---

client.c

Code:

---

#include "general.h"
#include "LinkedList.h"
#include "LinkedListEntry.h"

#include <stdlib.h>
#include <crtdbg.h>

int main(void){
       
        //_CrtSetBreakAlloc(54);
        {
                struct listhdr * list;
                LLEntry * entry, * newentry;
                int IDCounter=0;



                list=(struct listhdr *)malloc(sizeof(list));
                linkedlist_init(list);

               

                entry                =LLE_init(IDCounter++, "Filip",        "De Turck",        "+3293314932");                linkedlist_addfront        (list,entry);
                entry                =LLE_init(IDCounter++, "Piet",        "Demeester",        "+3293314920");                linkedlist_addtail        (list,entry);
                entry                =LLE_init(IDCounter++, "Bart",        "Dhoedt",        "+3293314922");                linkedlist_addtail        (list,entry);

                entry                =LLE_init(IDCounter++, "Filip",        "De Turck",        "+3293314922");                linkedlist_addtail        (list,entry);
                newentry        =LLE_init(IDCounter++, "Frank",        "De Gielen",        "+3293314928");                linkedlist_insert        (list,entry,newentry);

                linkedlist_swap(list, entry, newentry);


                linkedlist_print_forwards(list);
                linkedlist_print_backwards(list);

                linkedlist_destroy(list);

        }
        _CrtDumpMemoryLeaks();

        printf("\n\n");
        return 1;
}

---