c programm work different ways but i didn't change it

Question

I haved to realise dynamic array in c. Here is the struct of it:

typedef void (*PrintArrayElement)(const void* element);

typedef struct {
    size_t size;
    size_t capacity;
    void** array;
    PrintArrayElement printElement;  // Callback
} dynamic_array;

I have realised function to add element to array:

void arrayAddItem(dynamic_array* container, void* item)
{
    if (container->size == container->capacity)
    {
        void** temp = container->array;
        container->capacity <<= 1;
        container->array = (void **)realloc(container->array, container->capacity * sizeof(void*));
        if (!container->array)
        {
            printf("Out of Memory\n");
            container->array = temp;
            return;
        }
    }
    container->array[container->size] = strdup(item);
    container->size++;
}

Also I have function to find word indexes in string:

dynamic_array* findWord(char str[], char keyword[])
{
    dynamic_array* indexes;
    arrayInit(&indexes, 16, printInt);
    int i = 0;
    int start = 0;
    int end = 0;
    size_t len = strlen(str);
    while (i < len) {
        while (i < len && !isalpha(str[i]))
        {
            i++;
        }
        if (isalpha(str[i]))
        {
            start = i;
            while (i < len && isalpha(str[i]))
            {
                i++;
            }
            end = i;
            char* word = (char*)malloc(end - start + 1);
            strncpy(word, &str[start], end - start);
            word[end - start] = '\0';
            if(strcmp(word, keyword) == 0)
            {
                printf("%d\n", start);
                arrayAddItem(indexes, &start);
            }
            free(word);
        }
    }
    return indexes;
}

So I write dynamic_array* test_find_array1 = findWord("hello, world, hello", "hello"); and waiting for dynamic_array with two elements: 0 and 14, but I have a dynamic_array with pointers. And the main problem is that sometimes I have the correct answer, but I didn't rewrite the code. Why can it happen?

I tried to rewrite findWord function and arrayAddItem but its still going random way. I have nothing ideas whats wrong. Let me know if I should add some code of other functions from project.

Answer 1

1. You should provide a minimal reproducible example program that demonstrate the issue. From the question headers are missing as are the implementations of arrayInit(), printInt() and main(). Presumably a arrayFree() is also missing otherwise your program leaks memory. I added example implementations for you to test your code. printElement is not used so you should eliminate it.

2. arrayAddItem() will fail if capacity is initialized to 0. You expect memory to be allocated but isn't. malloc(0) is implementation defined and could be NULL which now runs afoul of check if realloc() failed. I added a check and default to capacity = 1 if it was 0. It's not wrong to use <<1 but * 2 probably compiles to the same thing and easier to read at lest to me.

   The factor 2 is fine for small values but 2^capacity grows fast. Say, you have 2^10 elements (i.e. 8 MB to store void pointers) do you want want to allocate another 8 MB when you hit that?

   Also it's an optimization so you could see (benchmark) what the overhead is for growing 1 element at a time before doing so in batches. malloc() may have similar optimizations, or others that result in batches being both slower and wasteful of memory.

3. (not fixed) arayAddItem(): capacity could overflow which result in data loss when array shrinks.

4. arrayAddItem() uses strdup() to copy item which means it assumes a string. In findWord() you pass in int so this will most likely segfault. Changing the API to expect caller to provide a copy of the data and caller is also responsible for free'ing said data (for symmetry). Otherwise you need to tell arrayAddItem() how to copy (i.e. size) whatever item points to.

5. arrayAddItem() will return an invalid container->capacity if realloc() fails (new capacity instead of the old capacity). I updated code to use variables and only update container upon success to illustrate it (they are not actually used as the program will now exit on failure).

6. arrayAddItem() error handling strategy is inconsistent. You ignore the possibility of strdup() failing and return corrupt data if realloc() fail. You don't check if arrayInit() fails so I assume you don't return anything. Now code exit(1) upon failure. API needs to change to survive these errors but if you are out of memory you probably will quit anyways.

7. (not fixed) findWord() will fail if either str or keyword is NULL. You could use assert() if it's a error, or you need a check if it's valid run-time condition that you need to handle.

8. findWord(): minimize scope of variables and avoid the start = 0 and end = 0 which initial values art not used.

9. findWord(): strlen() returns a size_t but you use int for start, end and i. Prefer unsigned types.

10. findWord(): It's silly to go through all that effort to copy the string if you only want to record the starting position. The main thing is that you want to malloc space for the position so you can pass a pointer to arrayAddItem(). (As an exercise try pass &start to see why that won't work).

11. (not fixed) findWord(): strings contain a terminating \0. It's common idiom for c code to rely on that instead of calculating the length of a string.

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

typedef struct {
    size_t size;
    size_t capacity;
    void** array;
} dynamic_array;

void arrayInit(dynamic_array **container, size_t capacity)
{
    *container = malloc(sizeof **container);
    if(!*container)
    {
        printf("malloc failed\n");
        exit(1);
    }
    (*container)->size = 0;
    (*container)->capacity = capacity;
    (*container)->array = capacity ? malloc(sizeof *(*container)->array * capacity) : NULL;
    if(capacity && !(*container)->array)
    {
        printf("malloc of array failed\n");
        exit(1);
    }
}

void arrayFree(dynamic_array *container) {
    if(!container) return;
    free(container->array);
    free(container);
}

void arrayAddItem(dynamic_array* container, void* item) {
    if (container->size == container->capacity)
    {
        size_t new_capacity = container->capacity ? container->capacity * 2 : 1;
        void **new_array = realloc(container->array, sizeof *(container->array) * new_capacity);
        if(!new_array)
        {
            printf("malloc failed\n");
            exit(1);
        }
        container->capacity = new_capacity;
        container->array = new_array;
    }
    container->array[container->size] = item;
    container->size++;
}

dynamic_array* findWord(char str[], char keyword[]) {
    dynamic_array* indexes;
    arrayInit(&indexes, 0);
    size_t i = 0;
    size_t len = strlen(str);
    size_t keyword_len = strlen(keyword);
    while (i < len) {
        while (i < len && !isalpha(str[i]))
            i++;
        if (isalpha(str[i]))
        {
            size_t start = i;
            while (i < len && isalpha(str[i]))
                i++;
            size_t end = i;
            if(end - start == keyword_len && !strncmp(str + start, keyword, keyword_len))
            {
                size_t *pos = malloc(sizeof start);
                if(!pos)
                {
                    printf("malloc failed\n");
                    exit(1);
                }
                *pos = start;
                arrayAddItem(indexes, pos);
            }
        }
    }
    return indexes;
}

int main(void)
{
    dynamic_array *container = findWord("hello world hello", "hello");
    for(size_t i = 0; i < container->size; i++)
    {
        printf("%zu ", *(size_t *) container->array[i]);
        free(container->array[i]);
    }
    printf("\n");
    arrayFree(container);
}

and example output:

0 12