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

[dcgreen2k]

1 hour ago, Gat Pelsinger said:

@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?

In an array, all elements must have the same size. A C string is just an array of chars with a null byte at the end, accessed using a pointer to its first element. If you have a string, then the memory to hold its chars must already be allocated. All you need to do to put a string in your ArrayList is add the pointer to its first element. Since all pointers are 8 bytes on a 64-bit machine, the element size is constant.

 

In other words, you wouldn't be storing entire char arrays, only the char*.

 

Here's how your ArrayList would store strings:

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

int main() {

    ArrayList a;
    ArrayList_init(&a, 100);

    char *hello = "Hello ";
    char *world = "World!\n";
    ArrayList_add(&a, (void *) hello);
    ArrayList_add(&a, (void *) world);

    printf("%s", (char *) ArrayList_get(&a, 0));
    printf("%s", (char *) ArrayList_get(&a, 1));

    return 0;
}

And here's what the code outputs:

 

 

[Gat Pelsinger]

@dcgreen2k Isn't this the same thing I have done in the code? My add function takes in a void pointer named element. And here, you are passing a char pointer type casted to void. But again, how do I get the size of the string? dereference the pointer and use sizeof on it? Also, how can the size of a string be pre-allocated? A string's size can vary upon the amount of characters are in it, right?

[Gat Pelsinger]

@dcgreen2k Oh wait, I think I get it now. So basically, I am not even storing the whole char array as an element in the array, but instead I am storing its pointer or something? But that still doesn't explain how I will get its size.

[dcgreen2k]

Just now, Gat Pelsinger said:

@dcgreen2k Oh wait, I think I get it now. So basically, I am not even storing the whole char array as an element in the array, but instead I am storing its pointer or something? But that still doesn't explain how I will get its size.

That's exactly it. You only need to store the pointer to the first character in the string.

 

sizeof() doesn't work on strings because it returns the size of the data type, which is char*.

#include <stdio.h>

int main() {
    char *hello = "Hello";
    printf("%zu\n", sizeof(hello));

    char *wait = "Wait a minute what's going on here";
    printf("%zu\n", sizeof(wait));

    return 0;
}

This prints:

 

Instead, you need to use strlen() when working with strings.

#include <stdio.h>
#include <string.h>

int main() {
    char *hello = "Hello";
    printf("%zu\n", strlen(hello));

    char *wait = "Wait a minute what's going on here";
    printf("%zu\n", strlen(wait));

    return 0;
}

This prints:

 

strlen() works by iterating over each character in the string, incrementing a counter until it reaches the end. The end of a C string will always be a null byte, or hexadecimal 00.

[Gat Pelsinger]

@dcgreen2k Ah yes strlen does work I was about to tell you that.

[Gat Pelsinger]

@dcgreen2k But there is another problem. If I use strlen on a non string value, I get a segfault. How do I know if the element is a string or not?

[dcgreen2k]

1 minute ago, Gat Pelsinger said:

@dcgreen2k But there is another problem. If I use strlen on a non string value, I get a segfault. How do I know if the element is a string or not?

If you're talking about knowing that from inside your ArrayList functions, you don't. The ArrayList doesn't know anything about the type of the data it stores, only the size of an individual element if we consider the ArrayList_init() change I mentioned previously.

 

What are you trying to do that requires you to know the length of the string?

[Gat Pelsinger]

@dcgreen2k to add it, I need to know the length of the string to see if I have enough space for it or not. Anyways, I think the only solution is to pass the size of the element from outside the function into the function.

[dcgreen2k]

3 minutes ago, Gat Pelsinger said:

@dcgreen2k to add it, I need to know the length of the string to see if I have enough space for it or not.

I don't think we're on the same page here. You don't need to know the length of the string to add it to your ArrayList. Just add the string's pointer to the list and you're done, nothing else to do.

 

Here's a simplified version of how adding strings to the backing array would work:

#include <malloc.h>

int main() {
    char* s1 = "blah blah blah";
    char* s2 = "This is waaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaay longer than 16 bytes";

    // The backing array for your ArrayList
    // Let's say it has a capacity of 2 elements, for a total of 16 bytes (2 * sizeof(void*) == 16)
    void** data = malloc(2);

    // Next, add the strings. Notice how we don't need the length of the strings to do this
    data[0] = (void*) s1;
    data[1] = (void*) s2;

    // And now we retrieve the strings
    printf("%s\n", (char*) data[0]);
    printf("%s\n", (char*) data[1]);

    return 0;
}

This prints out:

 

No sizeof() or strlen() needed.

[Gat Pelsinger]

@dcgreen2k So basically, I still can (and want to) use sizeof to check if I have enough space and for other stuff, but I am not considering the size of the string, but the size of the pointer, because that is what I have to add. And so, if I am not even using strings, let's say int, I am still only adding their pointers, and not the actual variable? But this way, I won't be able to use the same pointer for multiple function calls, as the element in the array is tied to the char pointer. So I have to keep creating new pointers to be able to add in the array? That is unreliable.

[dcgreen2k]

On 12/24/2023 at 10:59 PM, Gat Pelsinger said:

@dcgreen2k So basically, I still can (and want to) use sizeof to check if I have enough space and for other stuff, but I am not considering the size of the string, but the size of the pointer, because that is what I have to add.

Your point about considering the size of the pointer instead of the string is correct. I wouldn't use sizeof() to check if you have enough space, because that should be handled by the length and capacity variables stored in the ArrayList struct.

 

On 12/24/2023 at 10:59 PM, Gat Pelsinger said:

And so, if I am not even using strings, let's say int, I am still only adding their pointers, and not the actual variable?

If you're adding something like an int, then you're adding the actual variable to the ArrayList. You'll typically add the pointer instead when working with arrays (which strings are, at the base level) and large structs.

 

On 12/24/2023 at 10:59 PM, Gat Pelsinger said:

But this way, I won't be able to use the same pointer for multiple function calls, as the element in the array is tied to the char pointer. So I have to keep creating new pointers to be able to add in the array? That is unreliable.

I'm not really sure what you mean by this.

 

Here are a few simplified ArrayList functions I wrote based on your code. In my code, I made certain that the ArrayList is storing the actual variables instead of just pointers (where applicable). The add and get functions still use void* because we want to say "this can be any type" in C. Doing this requires a bit of pointer arithmetic and you'll notice that the backing array for the ArrayList struct is now just a uint8_t* (not void*, since void pointer arithmetic is non-standard) instead of void**. In my testing code, I show how this ArrayList can store ints or strings. Lastly, the only place sizeof() is ever used is during the call to ArrayList_init, and strlen() is never used.

 

ArrayList.h

#ifndef ARRAYLIST_H
#define ARRAYLIST_H

#include <stddef.h>
#include <stdint.h>

typedef struct ArrayList {
    uint8_t* array;
    size_t length, capacity, elemSize; // Added elemSize, removed filled_mem
} ArrayList;

// By passing in the size of an individual element, we can store the actual
// elements inside the ArrayList instead of just pointers
void ArrayList_init(ArrayList* list, size_t capacity, size_t elemSize);
void ArrayList_add(ArrayList* list, const void* element);
void* ArrayList_get(ArrayList* list, size_t index);
void ArrayList_remove(ArrayList* list, size_t index);

#endif

 

ArrayList.c

#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include "ArrayList.h"

void ArrayList_init(ArrayList* list, size_t capacity, size_t elemSize) {
    // Capacity must be at least 1
    if (capacity < 1) {
        fprintf(stderr, "Capacity must be at least 1");
        exit(1);
    }

    // We're going to be storing the actual elements, not just pointers
    list->array = malloc(capacity * elemSize);
    // Make sure the allocation didn't fail
    if (list->array == NULL) {
        fprintf(stderr, "Memory allocation failed");
        exit(1);
    }

    list->length = 0;
    list->capacity = capacity;
    list->elemSize = elemSize;
}

void ArrayList_add(ArrayList* list, const void* const element) {
    // If the list is full, double its capacity
    if (list->length == list->capacity) {
        list->array = realloc(list->array, list->capacity * list->elemSize * 2);
        list->capacity *= 2;
    }

    // Now add the new element
    memcpy(list->array + list->length * list->elemSize, element, list->elemSize);
    list->length++;
}

void* ArrayList_get(ArrayList* list, size_t index) {
    // Check if the index is valid
    if (index >= list->length) {
        fprintf(stderr, "Index out of bounds");
        exit(1);
    }

    // Return the address of the element associated with that index
    return list->array + (index * list->elemSize);
}

void ArrayList_remove(ArrayList* list, size_t index) {
    // Got too tired sorry
    // I'll probably do this tomorrow
}

 

main.c

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

int main() {
    // Basic testing code
    // Let's start with a list of ints
    ArrayList intList;
    ArrayList_init(&intList, 100, sizeof(int));

    // Add some ints
    int i1 = 123;
    int i2 = 456;
    ArrayList_add(&intList, (void*) &i1);
    ArrayList_add(&intList, (void*) &i2);
    ArrayList_add(&intList, (void*) &i2);

    // Retrieve those ints
    printf("%d\n", *((int*) ArrayList_get(&intList, 0)));
    printf("%d\n", *((int*) ArrayList_get(&intList, 1)));
    printf("%d\n", *((int*) ArrayList_get(&intList, 2)));

    // How about a list of strings now?
    ArrayList strList;
    ArrayList_init(&strList, 100, sizeof(char*));

    // Add some strings
    char* s1 = "blah blah blah";
    char* s2 = "C go brrrrrr";
    ArrayList_add(&strList, (void*) &s1);
    ArrayList_add(&strList, (void*) &s2);
    ArrayList_add(&strList, (void*) &s2);

    // Retrieve those strings
    printf("%s\n", *((char**) ArrayList_get(&strList, 0)));
    printf("%s\n", *((char**) ArrayList_get(&strList, 1)));
    printf("%s\n", *((char**) ArrayList_get(&strList, 2)));

    return 0;
}

 

I hope this code clears up some confusion, just wanted to show how you could simplify the ArrayList code and get the same results.

[Gat Pelsinger]

@dcgreen2k So I have a few questions.

1) I didn't understand these 2 lines - 

memcpy(list->array + list->length * list->elemSize, element, list->elemSize);

 

 return list->array + (index * list->elemSize);

Just explain what every token returns as I think I have a different understanding of what is happening.

 

2) Is creating a pointer and passing the pointer same as creating a variable (or array) and passing it by reference in both ints and strings?

 

3) You made a char pointer and passed the pointer by reference. What is the difference between passing the pointer itself and passing the address of the pointer?

 

4) In the add function, you are not checking if the list has enough space to store the element or not, which would require sizeof(), right?

 

5) So are you passing the whole string, or only its pointer in the list? Then can I use the char pointer I used to pass for a different purpose?

[wasab]

14 hours ago, Gat Pelsinger said:

@dcgreen2k So I have a few questions.

1) I didn't understand these 2 lines - 

memcpy(list->array + list->length * list->elemSize, element, list->elemSize);

 

 return list->array + (index * list->elemSize);

Just explain what every token returns as I think I have a different understanding of what is happening.

 

2) Is creating a pointer and passing the pointer same as creating a variable (or array) and passing it by reference in both ints and strings?

 

3) You made a char pointer and passed the pointer by reference. What is the difference between passing the pointer itself and passing the address of the pointer?

 

4) In the add function, you are not checking if the list has enough space to store the element or not, which would require sizeof(), right?

 

5) So are you passing the whole string, or only its pointer in the list? Then can I use the char pointer I used to pass for a different purpose?

1) you can check the linux manpage. https://www.man7.org/linux/man-pages/man3/memcpy.3.html

 

First arg is the source ptr, 2nd is the destination ptr, third is the len to be copied and the return value is the ptr to the destination. The return ptr should point to the starting address of your destination buffer. 

 

2) treat pointers like an 8-byte long unsigned integer. All pointers are, well assuming you are on a modern x86 64 bit machine and using mainstream compilers, 8 bytes in length. If you do sizeof(someptr) for example, it will spit out the same number. Ptr contains an address in memory. When you pass it around to another function, there will be a local copy of it made in the function stacks. You can then use it to dereference the same data it pointed to on the heap or in the parent caller stack. When you said passing by reference, i am assuming you mean when you pass like &xyz in the params? well, what does &xyz do? it gets you a pointer. so you are passing in pointers.  note: NEVER RETURN A PTR OF A LOCAL VARIABLE. all the local variables inside a function stack are no longer valid after the function finishes and pop off the call stack so don't do things like int x = 12312; return &x;

 

3) ptr is address memory which can point to the same address. You can literally do something like this 

char * ptr = (char *)0x28ff44;

this sets the value of ptr to an address of 0x28ff44. you can assign ptr like this and pass ptr around like this as well. If values of the ptr are the same, it doesn't matter how you pass them around or assign them, they will deference the same data in memory. if another pointer is 0x28ff44 then both point to the same address and thus will derefrence the same stuff when you do *ptr. so no difference if both ptr contains the same address memory.

 

Edit: maybe i am understanding the question wrong. ptr can have its own memory address and also its own ptr. you can do something like this *(*ptr) if ptr is a pointer of a pointer. this happens a lot if the data is like a 2d to 2+nth d array for example in which an array is a pointer containing list of pointers to a list of arrays. 

 

4) it is, that's the third arg. Please check the memeset/memcpy api doc. As programmers, we read up on api docs all the time. No way to get around this.

 

5) only ptr is passed whose value is then copied in the local function's stack. All params in c are passed by copied like many languages. People often do type casting to perform pointer arithmetic on some generic data. E.g. if you do charptr + 1, this will increment the address that ptr points to by one byte down since char is one byte in size, useful if you only want to copy a few bytes of a buffer instead of the entire data structure for example. If you do intptr + 1 however, this will increment the intptr by 4 bytes since int is 4 bytes in size (assuming you are using modern day x86 computer and mainstream computer)  which is a problem if you just wanna manipulate the first byte for whatever reason. Same things with struct and other data structures. So, besides type safety, casting is handy for doing pointer arithmetic and raw manual memory manipulation which is a very low-level feature that c has.

 

btw, if you use gcc compiler, void ptr is treated as a ptr to a data of single byte in length. It is similar to a char ptr and allows you to do pointer arithmetic. this is not a standard convention(void pointer arithmetic) so please don't do this. it will probably break or result in some very odd behaviors if you try to port it and compile it with some other compilers. 

 

Please read up on the c programming language by Brian Kernighan and Dennis Ritchie. you seem to lack some of the basic understanding. you will want to have a solid grasp of it before moving on to more complicated topics like pointer artimetrics, type castings, and whatnot. 

 

youtube tutorials also help. some textbooks are written like jargons so if you dont understand, visual learning helps

 

[dcgreen2k]

7 hours ago, wasab said:

this is not a standard convention(void pointer arithmetic) so please don't do this. it will probably break or result in some very odd behaviors if you try to port it and compile it with some other compilers.

 

You're right, it's been a while since I last worked with byte-level pointer arithmetic. You're supposed to use something like uint8_t* or char* instead of void* when doing pointer arithmetic like I showed previously. This is because void is an incomplete type and has no size, and GCC only allows us to use void* here because of an extension (i.e, it's non-standard). Compiling with -Wpedantic would have caught this.

 

I've corrected the code I posted previously, in case someone wants to use it in the future.