Having trouble in C... help... somebody.

[Gat Pelsinger]

Man, now I am actually starting to understand all those programming memes. Pointers and lack of generics and data structures in C really makes it painful. I am currently coding an array list data structure in C and I am having real problems. My code so far - 

Header file-

#ifndef H_ARRAY_LIST
#define H_ARRAY_LIST
#include <stdint.h>

typedef struct{
    void *array;
    size_t length;
    size_t capacity;
} ArrayList;

void initArrayList(ArrayList* restrict list, size_t  size)__attribute__((noreturn))__attribute__((pure))__attribute__((malloc));
void add(ArrayList* restrict list, void* restrict element)__attribute__((noreturn))__attribute__((pure));
void remove(ArrayList* restrict list, void* restrict element);
void _delete();

#endif

C file-

 

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

void initArrayList(ArrayList* restrict list, size_t  size){
    list->array = (void *)malloc(size);
    if (size > 0){
        if (list->array == NULL){
            fprintf(stderr, "MemoryAllocationFailedException");
            exit(1);
        }
    }
    list->capacity = size;
    list->length = 0;
}

void add(ArrayList* restrict list, void* restrict element){
    list->array = (void*)realloc(list->array, list->capacity + sizeof(element));
    if (list->array == NULL){
        fprintf(stderr, "MemoryAllocationFailedException");
        exit(1);
    }
    list->array[list->length] = element; //not modifiable lvalue error.

}
void remove(ArrayList* restrict list, void* restrict element){}
void _delete(){}

 

I am getting a not modifiable lvalue error where I have layed a comment. I don't know how to fix it, and also I would like to know how to improve the code further. You can see and tell I am clearly not interested right now and really tired. Still having a hard time to understand pointers and C mechanics and upon that ChatGPT gives like a million different code samples to understand and destroy my brain even further. I don't know why I am doing this, I should be studying for my exams, or at least study and learn stuff rather than pulling of an Einstein my self.

 

btw - ChatGPT gave me something and you might check it out might be helpful- https://chat.openai.com/share/53690fa5-bf15-4565-95f4-a2c30fd393d7.

[trag1c]

This more or less comes down to typing... or lack there of it. void* ptr = (void*)somePtr is perfectly valid because you're assigning the pointer to memory address.  However, trying to access it as a pointer + offset won't work because the compiler has no idea what the stride (sizeof(void) which doesn't exist) is. However by declaring array pointer to pointer you can now address elements because it's data type is better defined as void pointer to void pointer which does exist as sizeof(void*) which is just the size of standard pointer. 

 

So if you declare your array as void** the compiler will now see its pointer to pointer and as such you can address it as pointer + offset to retrieve a pointer to an element.

[Eigenvektor]

Just want to add something that is not directly related to the question.

 

Reallocating any time an element is added is bad for performance.

 

The way most libraries do it is to initialize the array for a certain number of elements, then e.g. double it in size when it is filled to capacity.

 

And since you expect your list to only contain a specific type of element you could also determine sizeof once and store it.

[wanderingfool2]

1 hour ago, trag1c said:

This more or less comes down to typing... or lack there of it. void* ptr = (void*)somePtr is perfectly valid because you're assigning the pointer to memory address.  However, trying to access it as a pointer + offset won't work because the compiler has no idea what the stride (sizeof(void) which doesn't exist) is. However by declaring array pointer to pointer you can now address elements because it's data type is better defined as void pointer to void pointer which does exist as sizeof(void*) which is just the size of standard pointer. 

 

So if you declare your array as void** the compiler will now see its pointer to pointer and as such you can address it as pointer + offset to retrieve a pointer to an element.

Could be wrong, but I think that might be the wrong answer.  sizeof(variablename) in this case will return the size of the pointer...since that's the type...so the capacity + sizeof should still be working as intended.

 

 

@Gat Pelsinger

What I think, and I don't know because I haven't really dealt with writing C99 with the restrict keyword, but from my understanding of restrict key you are essentially violating what restrict is meant for...which is why you are getting an lvalue error.

 

So restrict tells the compiler that there will only ever be one copy of that pointer used within the function (and that is the parameter passed in).  It allows it to make optimizations that there won't be overlapping pieces in memory.

 

Now I could be wrong here, as I haven't looked at the nitty gritty of the specification, but I suspect it's throwing that error because you are creating a second pointer to the object which you already guaranteed you would only have one pointer to it.

 

Like consider the following

//Essentially you are saying that the memory being used in this section is unique and won't overlap
void add(int *restrict a, int *restrict b, int *restrict result) {
	*result = *a + *b;
}

//Now the above, it gets to optimize because it knows that result won't contain a or b in it...like I can't do something like this
int a = 1, b = 2;
add(&a, &b, &a);

//Now without the keyword restrict, it would compile and work...and the result would be 3 is now stored in a...but by doing so it effectively had to do the following
void add(int *a, int *b, int *result) {
	int tmp = *a;
    int tmp2 = *b;
    *result = tmp + tmp2;
}

//Where as the restrict doesn't have to create the tmp variables because it knows that result won't have overlap (NOTE this is an oversimplification and doesn't 100% match up what would happen)

//Now lets look at the following code
void double(int *restrict a, int *restrict b) {
	int *failure = a;
    *failure = *a + *b;
}

//This fails because we created a scenario like above, in order to "store" failure the code to properly store failure it would have to create a temp variable...but restrict essentially said you didn't have to.  So you are violating what restrict was meant to be.

The tl;dr, remove restrict from element and I think you should be fine.

 

 

Also as what @Eigenvektor said, it's not good to realloc each time you add a new element...actually calling realloc has more penalties than using the keyword restrict.

 

What normally happens is you lets say "double" the capacity; or you choose some multiple or fixed increased size (if you know based on the application).  Generally I think a beginners guide to expansion you should stick to some multiple like capacity * 2.

 

Oh, while I'm at it...you forgot to increment length after adding the element...actually also missed adding to the capacity

[Gat Pelsinger]

@wanderingfool2 I already tried removing restrict. It didn't help. That is why I kept it.

[Dat Guy]

4 hours ago, Gat Pelsinger said:

lack of (...) data structures in C

 

structs exist.

[wanderingfool2]

9 hours ago, wanderingfool2 said:

Could be wrong, but I think that might be the wrong answer.  sizeof(variablename) in this case will return the size of the pointer...since that's the type...so the capacity + sizeof should still be working as intended.

Okay yea, I reread what you wrote; I'm just stupid with a few hours of sleep.

 

Although maybe a better way to phrase it is that he dereferenced a pointer to void with the array, but is assigning a pointer to it...instead of creating an array to a pointer to void*.

 

Oh, not really relavant to the problem...but one thing that can be handy is something like this

typedef union {
    int i;
    float f;
    double d;
    const char* str;
} ArrayDataType;

typedef struct {
    ArrayDataType value;
    int dataID;
    int capacity;
    int totalElements;
} ArrayList;

If lets say you know that you will be wanting to work with specific datatypes...union essentially stores them in the same memory blob.

[Gat Pelsinger]

@Eigenvektor @wanderingfool2

Another question, the program will have an unexpected behavior if I pass the address of a non ArrayList object. So, how do I check if the argument passed is the address of an ArrayList object?

[Kilrah]

If you define the parameter as being of type ArrayList the compiler should moan if you pass it something else.

[Gat Pelsinger]

1 hour ago, Kilrah said:

If you define the parameter as being of type ArrayList the compiler should moan if you pass it something else.

So no runtime error, only compilation error, right?

[Kilrah]

Yeah.

[Gat Pelsinger]

6 minutes ago, Kilrah said:

Yeah.

Another question popped up to me, how do I make variables only visible to the outside code, but not modifiable, while being completely modifiable inside the local code. For example, somebody might change the size variable and there will be memory issues. How do I make it so that the size variable is only visible when asked by the external code but not modifiable? But I obviously want it to be modifiable with the ArrayList code. 

[Kilrah]

You use C++ 

 

What you can do is put your arrayList code in its own file, and have size declared there. It won't be easily accessible from outside then, but if someone wants they could still declare extern size_t size; in another file and access it.

[Gat Pelsinger]

@Kilrah

 

What? Can I not just create an object of ArrayList, and do obj.size = x? Isn't it as easy as that to modify that?

[wanderingfool2]

7 hours ago, Gat Pelsinger said:

Another question popped up to me, how do I make variables only visible to the outside code, but not modifiable, while being completely modifiable inside the local code. For example, somebody might change the size variable and there will be memory issues. How do I make it so that the size variable is only visible when asked by the external code but not modifiable? But I obviously want it to be modifiable with the ArrayList code. 

That's the thing, you don't really have control over people modifying it if you expose it externally.  (I'm more studied in ANSI C so not really sure about more modern stuff, or just something that I've overlooked by not using C for years now)

 

If someone is using your code, and sees it, they should be able to know that they shouldn't be just modifying the length (or just document it).

[Kilrah]

10 hours ago, Gat Pelsinger said:

Can I not just create an object of ArrayList, and do obj.size = x?

You can 

ArrayList list;

list.size=x

 

although it's creating an instance of the struct you defined, there are no "objects" in C.

 

Just not getting what you're asking for I guess

[Gat Pelsinger]

I want to have a struct such that the members of the struct are not modifiable by the object itself, BUT are modifiable by the local file it is in. Ya, it sounds crazy. I don't even know if this possible as the objects have full access on the data members, but is there any possible way to restrict them while having no restriction for the local code?

 

Initially I made a mistake by not using a struct at all (the object would just a normal pointer) and all the variables would be in the local file but then if more than one pointer would call the functions, the variables would be common to all pointers, and not unique. So I guess I need some container like struct, right?

 

ChatGPT suggested me to half declare the struct in the header file, meaning no data members, and fully declare it in the local C file. But this way, my external code can't even create an object on the struct as it is not fully declared. I did try putting the curly brackets to the incomplete struct definition, but that just makes it defined without any data members, BUT what I am wondering is that is the full declaration in my C file even pointing to the same struct in my header file? I have the same names and even keywords. This is necessary because my functions expect a pointer of that struct, and if there are 2 different structs and if the object is pointing to one while my functions are pointing to the other, it is not going to work.

[Kilrah]

Merged since it's the same thing.

 

Again there are no "objects" in C. If you can access something through a pointer to write it you can read it. You'd need a C++ class to be able to make a member private.

 

If you don't want struct members to be accessible then you could create setter/getter functions. In your thing's code file you create functions to create, modify, update or delete the item, those functions keep track of the created instances and e.g. pass only a handle to them that is meaningless unless you go through the functions to interact with the actual instance.

 

[Gat Pelsinger]

@Kilrah I didn't quite get that. Can you elaborate more?

[Gat Pelsinger]

@Kilrah One more thing, I am writing the remove function to remove the element. In my head comes 2 versions of this and I might code both of them. First version is simple, I shift all the elements and realloc. Second, instead of sorting and reallocing all the time, I can leave the memory fragmented. Meaning, I put the index of the element that has to be removed in an array (my own ArrayList itself?), and in the future if somebody asks to read an element, I check through my array if that the element's index is past any element's index that was supposed to be removed (their indexes stored in the new array), and if true, in a loop I will increment the given element's index to read from till the amount of indexes stored in the new array. 

And for actually using the virtually freed memory, when adding an element, in a loop I will first check if the size of the  memory at the stored indexes is sufficient to store the element or not. If yes, the element is stored there and the indexes are adjusted and if not, the element is stored in a new memory space and if the fragmented memory is being used after multiple function calls, we trim the array and realloc to actually free the memory.

 

If you understood what I am saying, is this worth it than always calling sorting and reallocing the array? Of course, it will be upon the user to choose which removal function it wants.

[dcgreen2k]

The usual way to remove an element from an array-backed list is to just shift all of the elements that come after it back 1 space. There's no need to use realloc here. The second version seems very complex for such a simple removal task.

 

As for your question about having variables only be modifiable inside a single source file, I don't think that's possible in C. Those are called private variables, and C doesn't have them.

 

In cases like this where you want a variable to be private but your programming language doesn't support it (like C and Python), it's common to prefix the variable or function name with an underscore. This doesn't actually prevent you from accessing it, but it signals to yourself and other developers, "hey please don't use this variable/function directly."

[Kilrah]

6 hours ago, Gat Pelsinger said:

@Kilrah I didn't quite get that. Can you elaborate more?

You have a file with your ArrayList stuff. You write functions such as

int createArrayList()

bool addItem(int handle, <whatever> element)

...

 

When you call createArrayList you receive back a handle, e.g. 1

The function allocates an ArrayList, stores its pointer into a table that is declared in the ArrayList file (i.e. not directly accessible outside) at index 1, returns 1

When you want to add an item you call addItem(1, <whatever>), the function looks up in the table at index 1, gets the pointer to the ArrayList and updates it

 

That way stuff outside never gets to see the pointer so can't directly interact with it.

Obviously that has overhead, and of course the other file can still declare extern thetable; and then access it if it really wants it.

[Gat Pelsinger]

@Kilrah @dcgreen2k

 

Probably the last comment on the thread. I almost finally completed the ArrayList data structure and I would like you review it. Note that I already have one problem. In multiple functions, element is a void pointer, which is another problem by itself as I was forced to use a pointer because I don't know the type of the element, so I would like to know if there is a better way to to this, but the main problem is that I am using "sizeof(element)" to get the size of the actual element in the array, but doesn't this give the size of the element pointer itself? And so to get around this, do I need to dereference the element pointer to be able to get the size of the actual element? Here is the code - 

 

ArrayList.h - 

 

#ifndef H_ARRAY_LIST
#define H_ARRAY_LIST
#include <stdint.h>

enum{
    HOT, WARM, COLD
};

typedef struct ArrayList {
    void** array;
    size_t length, capacity, filled_mem;
    uint8_t alloc_type;
}ArrayList;

void ArrayList_init(ArrayList* restrict list, size_t  size)__attribute__((pure))__attribute__((malloc))__attribute__((noreturn));
void ArrayList_add(ArrayList* restrict list, void* restrict const element)__attribute__((pure))__attribute__((malloc))__attribute__((noreturn));
void ArrayList_remove(ArrayList* restrict list, size_t const index)__attribute__((pure))__attribute((malloc))__attribute__((noreturn));
void ArrayList_QuickRemove(ArrayList* restrict list, size_t const index);
void ArrayList_delete(ArrayList* restrict list);__attribute((pure))__attribute__((noreturn));
void ArrayList_get(ArrayList* restrict list, size_t const index)__attribute((pure));
void ArrayList_pop(ArrayList* restrict list)__attribute__((pure))__attribute__((malloc))__attribute__((noreturn));
void ArrayList_length(ArrayList* restrict list)__attribute__((pure));
void ArrayList_MemTrim(ArrayList* restrict list)__attribute__((pure))__attribute__((malloc))__attribute__((noreturn));
void ArrayList_ChangeAllocType(ArrayList* restrict list, uint8_t value)__attribute__((pure))__attribute__((noreturn));

#endif

 

ArrayList.c - 

 

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


void ArrayList_init(ArrayList* restrict list, size_t  size){
    if (size > 1000)size = 1000;
    if (size < 0)size = 0;
    list->array = NULL;
    if (size > 0){
        list->array = (void**)malloc(size);
        if (list->array == NULL){
            fprintf(stderr, "MemoryAllocationFailedException");
            exit(1);
        }
    }
    list->length = 0;
    list->capacity = size;
    list->filled_mem = 0;
}

void ArrayList_add(ArrayList* restrict list, void* restrict const element){
    if (list->capacity == 0){
        ArrayList_init(list, (sizeof(element)) * list->alloc_type == HOT? 4 : list->alloc_type == WARM? 2 : 1);
        if (list->array == NULL){
            fprintf(stderr, "MemoryAllocationFailedException");
            exit(1);
        }
    }
    else {
        if ((list->capacity - list->filled_mem) < sizeof(element)){
            list->capacity = sizeof(element) - (list->capacity - list->filled_mem) * (list->alloc_type == HOT? 4 : list->alloc_type == WARM? 2 : 1);
            list->array = (void**)realloc(list->array, list->capacity);
            if (list->array == NULL){
                fprintf(stderr, "MemoryAllocationFailedException");
                exit(1);
            }
        }
    }

    list->array[list->length] = element;
    list->length++;
    list->filled_mem += sizeof(element);
}
void ArrayList_remove(ArrayList* restrict list, size_t const index){
    if (list == NULL){fprintf(stderr, "ArrayListNULLException"); exit(1);}
    if (index < 0 || index >= list->length){fprintf(stderr, "InvalidArrayListIndexException"); exit(1);}
    void** array = (void**)malloc(sizeof(list->array) - sizeof(list->array[index]));
    if (array == NULL){fprintf(stderr, "MemoryAllocationFailedException"); exit(1);}
    list->capacity -= sizeof(list->array[index]);
    list->filled_mem -= sizeof(list->array[index]);
    size_t i = 0;
    while (i < index){
        array[i] = list->array[i];
        i++;
    }
    while (i < list->length - 1){
        array[i] = list->array[i + 1];
        i++;
    }
    free(list->array);
    list->array = array;
    list->length--;

}
void ArrayList_QuickRemove(ArrayList* restrict list, size_t const index){
    //Under Construction
}
void ArrayList_delete(ArrayList* restrict list){
    free(list->array);
    list->array = NULL;
    list->length = 0;
    list->capacity = 0;
    list->filled_mem = 0;
}
void ArrayList_get(ArrayList* restrict list, size_t const index){
    return list->array[index];
}
void ArrayList_pop(ArrayList* restrict list){
    list->array = (void**)realloc(list->array, list->capacity - sizeof(list->array[list->length - 1]));
    list->capacity -= sizeof(list->array[list->length - 1]);
    list->filled_mem -= sizeof(list->array[list->length - 1]);
    list->length--;
}
void ArrayList_length(ArrayList* restrict list){
    return list->length;
}
void ArrayList_MemTrim(ArrayList* restrict list){
    list->array = (void**)realloc(list->array, list->filled_mem);
}
void ArrayList_ChangeAllocType(ArrayList* restrict list, uint8_t value){
    if (value >= 0 && value < 3)
    list->alloc_type = value;
}

Please tell me about the size of element problem.

[dcgreen2k]

First, there was a bit of work to do before your code would build and run properly. The attributes applied to the function declarations were one source of the issues:

1. The pure and malloc attributes only work on functions that return a value (i.e, not void)
2. The noreturn attribute should only be used on functions that contain an infinite loop

Also, some function declarations have incorrect return types:

1. ArrayList_get should return a void* instead of void
2. ArrayList_length should return size_t instead of void

One thing I noticed but doesn't cause a compiler warning is that some functions don't have list size or bounds checking, like ArrayList_get and ArrayList_pop. Those will cause a runtime error when you try to get an out of bounds index or call pop on an empty list.

 

After getting the code running, I tested the init, add, remove, get, and length functions and they seemed to work fine with operations that avoided error cases.

 

About your question relating to getting the size of an element, there's no way to do that using only void pointers like your ArrayList does now. This is because casting a pointer to void* discards any size information related to the original data. Here's how we can test what happens when you try to dereference a void* and use sizeof on the result:

#include <stdio.h>
#include <stddef.h>

size_t getsize(void* data) {
    return sizeof(data);
}

size_t getsize_deref(void* data) {
    return sizeof(*data);
}

int main() {
    int a = 123;
    printf("%zu\n", getsize((void*)&a));
    printf("%zu\n", getsize_deref((void*)&a));
    return 0;
}

And this prints out:

 

Why does this happen? Put simply, a void* points to a single byte in memory and there's no way to go back to the original data type unless the programmer remembers what type it was.

 

The solution to this problem is to take the size of the data type when you first initialize the list and store it inside the ArrayList struct. Then, whenever you need to know the size of an individual element inside the list, you just use that stored value. Here's what the new init function might look like:

void ArrayList_init(ArrayList* restrict list, size_t capacity, size_t elemSize);

And here's how you might use it to store a list of ints:

#include "ArrayList.h"

int main() {
    ArrayList intList;
    ArrayList_init(&intList, 100, sizeof(int));
    return 0;
}

 

Lastly, there's no good way to get around using void pointers in cases like this when using C. That's just how C works. There's a good reason newer languages have support for templates and generics, so programmers don't have to write error-prone code like this.

[Gat Pelsinger]

@dcgreen2k But, what if I have to store strings as an element in the array? Then I can't preset the size of every element in ArrayList_init function. So, a better way would be to take in the element size in my add function?