3
\$\begingroup\$

Based on my googling around generic lists in C I stumbled upon tagged unions. What I wanted to create was a data structure that can hold int, float, double and char, all in one list. There is a function to add an item to which type information has to be passed. What I am unsure about: I read that casting void pointers is bad practice, but since I know the type of the variable the void pointer points to I think it's safe. The structure is kind of inspired by VBA recordsets, where the list has a cursor that tells the function where the record is to be inserted. The actual data is stored within an array of structs inside of a struct. The outside struct contains cursor and length information.

Questions:

  1. Possibly unsafe?
  2. If adding a new item fails, the cursor is incremented regardless - I don't know how to implement a check for successful insert of the record.
  3. Code contains switches that depend on type information; there may be a more efficient way to handle different types.
  4. I am unsure about the best way to allocate the outer list struct - do I define it first, then pass to a function to allocate or do I define and allocate inside of a function, returning a pointer? Right know, I use the latter.
  5. I reallocate the list array by doubling its allocated size; for a large list, this will be inefficient I guess?
  6. I am unsure what the best way to address the items of the my_list_elem in the array of structs in the outer struct, my_list, is.

Code:

#include <stdio.h>
#include <stdlib.h>

#define DEFAULT_LIST_LENGTH 5

//an actual list element, contains type information
typedef struct list_elem {
    enum {is_int = 1, is_float, is_double, is_char} type;
    union {
        int i_val;
        float f_val;
        double d_val;
        char* c_val;
    } value;
} my_list_elem;

/* list container, contains array of list elements
   as well as cursor and length of list
*/
typedef struct list {
    my_list_elem *element;
    unsigned int length; //number of elements, not bytes
    unsigned int cursor;
} my_list;

//allocate a new my_list and return pointer
my_list * alloc_list() {
    my_list *in_list = malloc(sizeof(my_list));
    in_list->element = malloc(sizeof(my_list_elem) * DEFAULT_LIST_LENGTH);
    in_list->length = DEFAULT_LIST_LENGTH;
    in_list->cursor = 0;
    
    return in_list;
}

//add new element to list
void add_element(my_list *dest, void *in_value, const int type) {
    unsigned int tmp_cursor = 0;
    tmp_cursor = dest->cursor;
    
    //double list size if not big enough, to reduce number of realloc calls
    if(tmp_cursor == dest->length) {
        dest->element = realloc(dest->element, dest->length * sizeof(my_list_elem) * 2);
        dest->length *= 2;
    }
    
    (dest->element[tmp_cursor]).type = type;
    switch(type) {
        case is_int:
            (dest->element[tmp_cursor]).value.i_val = *(int *)in_value;
            break;
        case is_float:
            (dest->element[tmp_cursor]).value.f_val = *(float *)in_value;
            break;
        case is_double:
            (dest->element[tmp_cursor]).value.d_val = *(double *)in_value;
            break;
        case is_char:
            (dest->element[tmp_cursor]).value.c_val = (char *)in_value;
            break;
    }
    
    dest->cursor += 1;
}

//free list
void free_list(my_list *in_list) {
    free(in_list->element);
    free(in_list);
}

//print list report (total list)
void print_report(my_list* src) {
    printf("Current stats of list: \n");
    printf("========================\n");
    printf("Current cursor: %d\n",src->cursor);
    printf("Length (allocated): %d\n", src->length);
    printf("========================\n");
    
    for(int i = 0; i < src->cursor ; i++) {
        switch(src->element[i].type) {
            case is_int:
                printf("Type: %d Value: %d\n", src->element[i].type, src->element[i].value.i_val);
                break;
            case is_float:
                printf("Type: %d Value: %f\n", src->element[i].type, src->element[i].value.f_val);
                break;
            case is_double:
                printf("Type: %d Value: %lf\n", src->element[i].type, src->element[i].value.d_val);
                break;
            case is_char:
                printf("Type: %d Value: %s\n", src->element[i].type, src->element[i].value.c_val);
                break;
        }
    }
    printf("\n\nEND.\n");
}

int main()
{
    my_list *new_list = alloc_list();
    
    int my_val = 45;
    void *ptr_my_val = &my_val;
    
    add_element(new_list,ptr_my_val,1);
    
    char *ptr_my_string = "TEST";
    add_element(new_list, ptr_my_string, 4);
    
    double my_double = 0.56843;
    double* ptr_my_double = &my_double;
    add_element(new_list, ptr_my_double, 3);

    print_report(new_list);
    
    free(new_list);
    
    return 0;
}

Tried it using OnlineGDB, works fine.

If anyone answers this post: thanks in advance, you're really helping me learn!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to CodeReview@SE. Tried it using OnlineGDB, works fine. next thing would automated unit tests. \$\endgroup\$
    – greybeard
    Sep 17, 2020 at 6:27

2 Answers 2

3
\$\begingroup\$

General Observations and Answers

Welcome to Code Review, this is a pretty good first question, definitely well focused. The structure of the program is pretty good and the functions seem to follow the Single Responsibility Principle.

It might be better if Problems: was either Questions: or Possible Issues:, to some users Problems: would indicate the code isn't working as expected.

One of the problems with free online compilers is that they may not report all warning messages, the following line has a type mismatch between int and unsigned:

    for (int i = 0; i < src->cursor; i++) {

since i is declared as int. You might want to use size_t for both.

  1. Possibly unsafe?

In most modern programing languages such as C# and VBA memory management is handled for you, this isn't the case in C or C++. In C (not C++, C++ throws an exception when memory allocation fails) the use of any of the memory allocation functions (malloc(), calloc() and realloc()) may fail. While memory allocation failure is rare these days due to the larger memories most processors contain it can still occur, especially on embedded systems with limited memory. If the memory allocation fails the value of the pointer returned from the function is NULL and reference through a NULL pointer causes Undefined Behavior. Sometimes this is easy to detect because it causes a Segmentation Violation, other times it is very hard to detect because it corrupts the memory. In all cases memory allocation should be followed by a test of the pointer value returned:

My_List* alloc_list() {
    My_List* in_list = malloc(sizeof(My_List));
    if (in_list == NULL)
    {
        fprintf(stderr, "Memory allocation for in_list failed in alloc_list()\n");
        return NULL;
    }

    in_list->element = malloc(sizeof(My_List_Elem) * DEFAULT_LIST_LENGTH);
    if (in_list->element == NULL)
    {
        fprintf(stderr, "Memory allocation for in_list->element failed in alloc_list()\n");
        return NULL;
    }

    in_list->length = DEFAULT_LIST_LENGTH;
    in_list->cursor = 0;

    return in_list;
}

int main()
{
    My_List* new_list = alloc_list();
    if (new_list == NULL)
    {
        return EXIT_FAILURE;
    }

    ...

    free_list(new_list);

    return EXIT_SUCCESS;
}

The macros EXIT_FAILURE and EXIT_SUCCESS are standard C macros defined in stdlib.h and make the code easier to read and maintain.

The preceding code should answer Problem :4.

The unused function free_list() should be used otherwise there is a memory leak.

  1. If adding a new item fails, the cursor is incremented regardless - I don't know how to implement a check for successful insert of the record.

This is a feature request and that is off-topic for code review, however, if the code returns from the function add_element() early in the case of an error the cursor won't be updated.

  1. Code contains switches that depend on type information; there may be a more efficient way to handle different types.

When you use switch statements coupled with with enums it is always a good idea to provide a default: case that will handle an unknow enum type:

    switch (type) {
    case is_int:
        (dest->element[tmp_cursor]).value.i_val = *(int*)in_value;
        break;
    case is_float:
        (dest->element[tmp_cursor]).value.f_val = *(float*)in_value;
        break;
    case is_double:
        (dest->element[tmp_cursor]).value.d_val = *(double*)in_value;
        break;
    case is_char:
        (dest->element[tmp_cursor]).value.c_val = (char*)in_value;
        break;
    default:
        printf("Unknown type in function add_element\n");
        break;
    }

A possibly more efficient as well as expandable way is to have an array of one line functions that take in_value and the dest pointer and perform the proper storage operation.

  1. I am unsure about the best way to allocate the outer list struct - do I define it first, then pass to a function to allocate or do I define and allocate inside of a function, returning a pointer? Right know, I use the latter.

There are benefits to both, one saves some memory allocation(not much) and one doesn't, the code is fine the way it is.

  1. I reallocate the list array by doubling its allocated size; for a large list, this will be inefficient I guess?

This is fine, sometimes 1.5 is used rather than 2, but overall this is efficient. I would use a symbolic constant (macro) rather than a hard coded 2 to make this more readable and easier to maintain.

  1. I am unsure what the best way to address the items of the my_list_elem in the array of structs in the outer struct, my_list, is.

This question is unclear and if it is a feature request it is off-topic.

ENUMS

The numerical value of an enum type generally starts at zero rather than one (this is the default if you don't specify it), if you want to use an array indexed by enums as I suggested above then starting with zero would be better.

Due to the fact that the enum type is declared in the struct my_list_elem rather than having it's own typedef the enum can't easily be used as a type and that would make the code more readable and easier to maintain.

typedef enum My_Type
{
    TYPE_INT,
    TYPE_FLOAT,
    TYPE_DOUBLE,
    TYPE_CHAR
} My_Type;

typedef struct list_elem {
    My_Type type;
    union {
        int i_val;
        float f_val;
        double d_val;
        char* c_val;
    } value;
} My_List_Elem;

void add_element(My_List* dest, void* in_value, const My_Type type) {
    unsigned int tmp_cursor = 0;
    tmp_cursor = dest->cursor;

    //double list size if not big enough, to reduce number of realloc calls
    if (tmp_cursor == dest->length) {
        dest->element = realloc(dest->element, dest->length * sizeof(My_List_Elem) * 2);
        dest->length *= 2;
    }

    (dest->element[tmp_cursor]).type = type;
    switch (type) {
    case TYPE_INT:
        (dest->element[tmp_cursor]).value.i_val = *(int*)in_value;
        break;
    case TYPE_FLOAT:
        (dest->element[tmp_cursor]).value.f_val = *(float*)in_value;
        break;
    case TYPE_DOUBLE:
        (dest->element[tmp_cursor]).value.d_val = *(double*)in_value;
        break;
    case TYPE_CHAR:
        (dest->element[tmp_cursor]).value.c_val = (char*)in_value;
        break;
    default:
        printf("Unknown type in function add_element\n");
        break;
    }

    dest->cursor += 1;
}

Capitalize your created types so they are easily identified as shown above.

Answer Update Based on Comments

As noted in the comments, you can de-reference the elements like this

void add_element(My_List* dest, void* in_value, const My_Type type) {

    //double list size if not big enough, to reduce number of realloc calls
    if (dest->cursor == dest->length) {
        dest->element = realloc(dest->element, dest->length * sizeof(My_List_Elem) * 2);
        dest->length *= 2;
    }

    My_List_Elem* current_element = &dest->element[dest->cursor];

    current_element->type = type;
    switch (type) {
    case TYPE_INT:
        current_element->value.i_val = *(int*)in_value;
        break;
    case TYPE_FLOAT:
        current_element->value.f_val = *(float*)in_value;
        break;
    case TYPE_DOUBLE:
        current_element->value.d_val = *(double*)in_value;
        break;
    case TYPE_CHAR:
        current_element->value.c_val = (char*)in_value;
        break;
    default:
        printf("Unknown type in function add_element\n");
        break;
    }

    dest->cursor += 1;
}

It could be de-referenced more or less to make maintenance easier.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks for the very detailed answer. If there are no more answers in a couple of hours, I will mark it as accepted. What I meant in "problem" 6 is: "Is dest->element[tmp_cursor]).value.i_val a safe way to adress the union members in the struct? I know it could segfault if the cursor value isn't correct, but what else might go wrong? \$\endgroup\$
    – NXP5Z
    Sep 17, 2020 at 15:27
  • 1
    \$\begingroup\$ You can wait a day or 2 to accept. Working on an answer for # 6 \$\endgroup\$
    – pacmaninbw
    Sep 17, 2020 at 19:09
  • 1
    \$\begingroup\$ You can use more temporary variables in that function to reduce the complexity of the statement my_list_elem *tmp_elements = dest->element; Then treat tmp_elements as an array. tmp_elements[tmp_cursor].value.ival This might actually improve performance, it will definitely improve performance in print_report. A second option also includes de-referencing it even more my_list_elem *current_element = dest->element[tmp_cursor]; and just use that pointer. \$\endgroup\$
    – pacmaninbw
    Sep 17, 2020 at 19:28
  • \$\begingroup\$ Some finetuning is always possible, but at least there appear to be no gross errors in this method. Thanks! \$\endgroup\$
    – NXP5Z
    Sep 17, 2020 at 19:38
  • \$\begingroup\$ Rather than code realloc(dest->element, dest->length * sizeof(My_List_Elem) * 2), consider sizing to the referenced object realloc(dest->element, dest->length * sizeof *(dest->length) * 2). Less like to code wrong, easier to review and maintain. \$\endgroup\$ Sep 17, 2020 at 21:23
1
\$\begingroup\$

regarding;

typedef struct list 
{
    my_list_elem *element;
    unsigned int length; //number of elements, not bytes
    unsigned int cursor;
} my_list;

and

for(int i = 0; i < src->cursor ; i++) {

The src->cursor is an unsigned type, but the for() statement is comparing it to a signed type. Usually this will have the desired results, but it is much better to change the for() statement to:

for( unsigned i = 0; i < src->cursor; i++ ) {

when compiling, always enable the warnings, then fix those warnings for gcc, at a minimum, use:

-Wall -Wextra -Wconversion -pedantic -std-gnu11

regarding:

dest->element = realloc(dest->element, dest->length * sizeof(my_list_elem) * 2);

Never directly assign the returned value from realloc() to the target pointer. WHEN realloc() fails, the original pointer will be lost, resulting in a memory leak. Suggest:

void temp = realloc(dest->element, dest->length * sizeof(my_list_elem) * 2);
if( !temp ) {
    // then realloc failed
    perror( "realloc failed" );
    // cleanup
    exit( EXIT_FAILURE );
}

// implied else, realloc successful

dest->element = temp;

regarding statements like:

my_list *in_list = malloc(sizeof(my_list));

always check (!=NULL) the returned value to assure the operation was successful.

if( !in_list ) {
    // malloc failed
    perror( "malloc failed" );
    exit( EXIT_FAILURE );
}

// implied else, malloc successful
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.