Making a type agnostic linked list in ANSI C - (if possible)

This is a discussion on Making a type agnostic linked list in ANSI C - (if possible) within the C Programming forums, part of the General Programming Boards category; I'm fairly new to C (and pointers in general - I have no C++ experience) and am trying to create ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    15

    Question Making a type agnostic linked list in ANSI C - (if possible)

    I'm fairly new to C (and pointers in general - I have no C++ experience) and am trying to create a linked list that I can shove any type of data in. I have to use strict ANSI C only as I want to use this list in an upcoming school project for a class that allows ANSI C only.

    I've got a linked list written already that works well with one type of data (I used strings when I tested it's functionality). I've read that this might be possible using void (a type agnostic bubble sort is explained here Chapter10, and there were a couple forum posts I had dug up that I cant find now)

    From my understanding the only code that would need to be modified would be code that deals directly with the insides of my "Element" struct - being the struct itself, and the functions that handle creating and destroying it. Thus I'm only going to post that code (if you do need more to help just let me know ).

    Other things to mention:
    -I'm planning on storing different types of structs within the list
    -I have to compile using the command: gcc -Wall -Wextra -ansi -pedantic main.c -o main.exe

    IN MAIN
    Code:
    Element *newElement;
            
        printf("\n%d: Enter a string: ", i + 1);    
        gets(input);
        
        sprintf(newElementKey, "%d", (i + 1));    
        newElement = CreateElement(newElementKey, input, sizeof(*input));
    LINKED LIST STUCTS
    Code:
    typedef struct Element
    {
      void *data; /* Pointer to data goes here */
      char *key;
      
    } Element;
    
    typedef struct LLNode
    {
      struct LLNode *next;
      Element *entry;
    } LLNode;
    
    typedef struct LinkedList
    {
      LLNode *start;
      LLNode *current;
    } LinkedList;
    LINKED LIST FUNCTIONS
    Code:
    Element* CreateElement(char *elementKey, void *elementData, size_t dataSize)
    {
      Element *createdElement;
      size_t elementKeyLength;
    
      createdElement = malloc(sizeof(Element));
    
      elementKeyLength = strlen(elementKey);
      createdElement->key = malloc(elementKeyLength * sizeof(char));
      strcpy(createdElement->key, elementKey);
      
      createdElement->data = malloc(dataSize); /* I likely need modifications */
      createdElement->data = *elementData;     /* on these lines */
      
      return createdElement;
    }
    
    /* ... */
    
    Element* DestroyElement(Element *target)
    { 
      if(target != NULL)
      {  
        /* I don't know how this will interact with a "void" pointer */
        free(target->data); 
        free(target->key);
        
        free(target);    
        target = NULL;
      }
      
      return target;
    }

    If I try to compile right now I get the following errors, both on the line "createdElement->data = *elementData;" :
    --warning: dereferencing 'void *' pointer
    --error: void value not ignored as it ought to be

    If I don't dereference elementData here, when I try to print it out
    Code:
    /* warning on this line: char format, void arg (arg 3) */
    printf("\n%s: String: %s", fetchedElement.key, fetchedElement.data)
    
    /* warning on this line: dereferencing 'void *' pointer */
    printf("\n%s: String: %s", fetchedElement.key, *fetchedElement.data)

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    This:

    Quote Originally Posted by Feversaint View Post
    createdElement->data = malloc(dataSize); /* I likely need modifications */
    createdElement->data = *elementData; /* on these lines */
    is a memory leak, since first you assign some memory to data, then you assign something else to it. That memory was not freed and now has no pointer, meaning it will take up space and not be used until the program ends (hence it has "leaked"; these are very nasty in a loop). Presuming elementData was properly allocated already, you can just assign it to data, or you can malloc space for data and copy the contents in.

    You may need more of an explanation there, since you are new to pointers. Just ask for details. This stuff is fundamental; it is very important you get it straight and clear in your head.

    warning: dereferencing 'void *' pointer
    This is because the compiler does not know what type of thing a void* actually points to, so it does not know how much information to pass thru the dereference. You need a cast. Here's an example:

    Code:
    	int n = 5;
    	void *x = &n;
    	int b = *(int*)x;
    You could also just assign to another (typed) pointer, eg, "int *p = x;".

    However, in your case, dereferencing at all is inappropriate. You want to assign the value in one void pointer to another one, so:

    Code:
    createdElement->data = elementData;  // no *
    is fine.

    I did not read thru all of your code, but the concept is sound. Void* is what permits generic (more common term than agnostic) complex data types in C (such as this one). IMO, generic complex data types in C are a good learning exercise (esp. for pointers) but I would not get too gung-ho about it as they are not as useful as you might think (specific "custom" types are more common/less hassle, but again, just an opinion/observation. C programming is sort of rebellious in this sense. Think racing stripes, low weight, and max horsepower).
    Last edited by MK27; 09-18-2011 at 02:35 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    15
    Thanks a ton for your reply. I am trying to learn as much as I can about pointers and this has definitely been a valuable exercise. I think I may just go with the type specific route, as it has been the recommended route virtually everywhere I've seen (including here ).

    One question about the lines you pointed out, to make sure I understand what's happening.

    My post
    Code:
    createdElement->data = malloc(dataSize); /* I likely need modifications */
    createdElement->data = *elementData; /* on these lines */
    Your reply
    Code:
    createdElement->data = elementData;  // no *
    In your reply would I still use malloc() above that line? If not then I think I understand what is happening (data is being pointed at the address that elementData points at), if malloc() is still there then I would be confused. (I'm assuming it's not but I just want to be sure).

    Thanks again for your time and information!

  4. #4
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Correct, you would not use malloc there.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  5. #5
    Registered User
    Join Date
    Sep 2011
    Posts
    15
    Thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 03-22-2009, 05:03 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  4. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  5. Making a doubly linked list
    By mlupo in forum C Programming
    Replies: 1
    Last Post: 10-16-2002, 09:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21