void * allocation.

[Lawson]

Hey guys/girls/other.

got a quick question.

So I'm working on a personal project and I'm trying to make all my data structures general so that I can reuse them. My program is working fine, but I'm not actually sure if it is the correct way to go about it.

Details: So I have a linked list that looks something like this.

ADT

struct Node {
    void *data;
    struct Node *next;
} *List;

In 'my current' instance, void *data is going to be some text from a file.

How I'm getting the data for the ADT

List extracted_text_data(List self)
{
    const unsigned short buffer_size = 31;
    size_t len;    

    char buffer[buffer_size];

    // TODO: prompt user for text location.
    FILE *fp = fopen("./input.text", "r");

    if (fp == NULL) {
        perror("File error");
        exit(EXIT_FAILURE);
    }
    while (fgets(buffer, sizeof(buffer), fp) != NULL) {
        len = strlen(buffer) - 1;

        // need to remove newline characters at the end, otherwise
        // causes issues when traversing through the data in the linked list.
        if(buffer[len] == '\n') {
            buffer[len] = '\0';
        }
        self = insert(self, (void *) format_string(buffer, len), len);
    }
    fclose(fp);

    return self;
}

Is this correct?

static List node_init(void *data, size_t size)
{
    List new_node = malloc(sizeof(*new_node));

    if (new_node == NULL) {
        fprintf(stderr, "Error: allocating memory for new node.\n");
        exit(EXIT_FAILURE);
    }

    // works, but is just allocating a chunk.. feel this could be better.
    new_node->data = malloc(sizeof(size));

    if (new_node->data == NULL) {
        fprintf(stderr, "Error: allocating memory for data\n");
        exit(EXIT_FAILURE);
    }
    memcpy(new_node->data, data, size);

    new_node->next = NULL;

    return new_node;
}

So, the issue is. I'm using a buffer which is 31 chars. The input might not need 31 chars so to save memory I get the size of the buffer to allocate memory for the void *data in my node init.

Bottom line is:

When using void *data how do you correctly allocate it memory to store whatever you are sending it after you've cast it to a void * type? I've just used the size of the char array to get the new strlen to allocate a block.

Or would a better approach be to pass a function pointer where you are actually allocating the correct type?

Some advice/resources would be cool!The whole project can be found here: https://github.com/daniel-k-richardson/PasswordGuesser

[laserlight]

struct Node {
    void *data;
    struct Node *next;
} *List;

I note that the above declares a structure named struct Node, and then defines a (file-scope) pointer named List of type struct Node*. Perhaps you wanted to typedef the pointer type instead, but I would not advise that since the pointer is not an opaque pointer, hence it can be confusing as to why an apparently non-pointer is used with pointer syntax. Personally, I think that it is good to separate the notion of node and linked list, so I would suggest:

struct Node {
    void *data;
    struct Node *next;
};

struct List {
    struct Node *head;
    struct Node *tail; /* maybe? usually good for efficient append */
};

Then you have struct Node* and struct List* parameters as needed. You could turn them into opaque pointers though.

So, the issue is. I'm using a buffer which is 31 chars. The input might not need 31 chars so to save memory I get the size of the buffer to allocate memory for the void *data in my node init.

Although it is a good practical thought, I note that 31 chars might be sufficiently small for this to be a non-issue, especially if you are typically using 20+ chars.

When using void *data how do you correctly allocate it memory to store whatever you are sending it after you've cast it to a void * type?

I think you first need to decide: will the linked list own the data, or will it merely point to the data for which storage is managed elsewhere? If the former, then you can still make it such that the calling code allocates the space for the data, but the responsibility for freeing is passed to the linked list, i.e., there is a transfer of ownership. For the latter, the problems about allocation and deallocation go entirely to the calling code, so the linked list does nothing about that.

Or would a better approach be to pass a function pointer where you are actually allocating the correct type?

It would be a good idea for a deallocation function in that maybe the allocation was not done with malloc, so free would be incorrect. As such, you could provide a linked list init function that allows the caller to pass a pointer to a function that does the cleanup of the data, and another linked list init function for free to be used by default; the function pointer can be saved in the struct List object. With this approach, the insertion functions just assume that the pointer points to already allocated memory that can be deallocated with the deallocation function.

Alternatively, you could provide for an allocation function, but this will need to do a copy, i.e., the insertion functions assume that the pointer points to memory that is read-only, and invoke the allocation function to allocate and copy from the read-only memory. Since the allocation function is custom, it knows the underlying type and so can cast appropriately for the copy.

[Lawson]

I note that the above declares a structure named struct Node, and then defines a (file-scope) pointer named List of type struct Node*. Perhaps you wanted to typedef the pointer type instead, but I would not advise that since the pointer is not an opaque pointer, hence it can be confusing as to why an apparently non-pointer is used with pointer syntax. Personally, I think that it is good to separate the notion of node and linked list, so I would suggest:

Yeah, I have. I added the *List so that the rest of the code snippet makes sense without adding more. I was being lazy.

struct Node {
    void *data;
    struct Node *next;
};

struct List {
    struct Node *head;
    struct Node *tail; /* maybe? usually good for efficient append */
};

Typically if I don't care about the order of the linked list, i'll just insert at front and that way I don't need to traverse to the end of the linked list to insert, can just do it right off the bat, but you do make a good point.

Although it is a good practical thought, I note that 31 chars might be sufficiently small for this to be a non-issue, especially if you are typically using 20+ chars.

In 'this' particular case you're right, but if I want to reuse this code later for larger string it might be worth it.

I think you first need to decide: will the linked list own the data, or will it merely point to the data for which storage is managed elsewhere? If the former, then you can still make it such that the calling code allocates the space for the data, but the responsibility for freeing is passed to the linked list, i.e., there is a transfer of ownership. For the latter, the problems about allocation and deallocation go entirely to the calling code, so the linked list does nothing about that.

Yeah, I agree. I think it would be best for the node to own the data, the string array being passed will be changed as it reads in data and it'll be easier to 'destroy/free' memory with a quick traverse and free function later.


So, I think what I'll do from this point is as follows.

I'll get the size of the buffer * sizeof(char) and use that to allocate a 'block' of memory big enough to store the string and go from there.

Will let you know how it goes.

Thanks for giving me something to think about.