How to efficiently pre-append an array of strings in C?-CodePudding

I have a small framework written in C that allows a user to create dynamically allocated arrays of strings in the C language. The library has one function titled init_string_vector that allows a user to create a dynamically allocated string array, and another function append_string_vector that allows a user to append the array one string at a time. In addition, I have created another function titled preappend_string_vector that allows a user to pre-append the array one string at a time. However, the preappend_string_vector function requires that the array be iteratively re-created one value at a time, which can be time consuming. I have tried to use memmove and memcpy functions to do this faster, but thus far nothing works. Can anyone recommend a solution that is quicker in the time domain? The solution is shown below.

vector.h

typedef enum
{
    FLOAT,
    DOUBLE,
    CHAR,
    INT,
    STRING
} dat_type;
// --------------------------------------------------------------------------------

typedef struct
{
    char **array;
    size_t len;
    int elem;
    dat_type dat;
} StringVector;
// --------------------------------------------------------------------------------

int string_vector_mem_alloc(StringVector *array, size_t num_indices);
// --------------------------------------------------------------------------------

StringVector init_string_vector();
// --------------------------------------------------------------------------------

int append_string_vector(StringVector *s, char *value);
// --------------------------------------------------------------------------------

int preappend_string_vector(StringVector *s, char *value);
// --------------------------------------------------------------------------------

vector.c

int string_vector_mem_alloc(StringVector *array, size_t num_indices) {
    // Determine the total memory allocation and assign to pointer
    void *pointer;
    pointer = malloc(num_indices * array->elem);

    // If memory is full fail gracefully
    if (pointer == NULL) {
        printf("Unable to allocate memory, exiting.\n");
        free(pointer);
        return 0;
    }
    // Allocate resources and instantiate Array
    else {
        array->array = pointer;
        array->len = 0;
        return 1;
    }
}
// --------------------------------------------------------------------------------

StringVector init_string_vector() {
    StringVector array;
    array.dat = STRING;
    array.elem = sizeof(char);
    string_vector_mem_alloc(&array, array.elem);
    return array;
}
// --------------------------------------------------------------------------------

int append_string_vector(StringVector *s, char *value) {
    value = strdup(value);
    if (!value) {
        return -1;
    }
    s->len  ;
    char **resized = realloc(s->array, sizeof(char *)*s->len);
    if (!resized) {
        free(value);
        return -1;
    }
    resized[s->len-1] = value;
    s->array = resized;
    return 0;
}
// --------------------------------------------------------------------------------

int preappend_string_vector(StringVector *s, char *value) {
    if (!value) {
        return -1;
    }
    s->len  ;
    char **resized = malloc(sizeof(char *)*s->len);
    //char **extra_resized = realloc(s->array, sizeof(char *)*s->len);
    if (!resized) {
        free(value);
        return -1;
    }
    resized[0] = value;
    for (int i = 1; i < s->len; i  ) {
        resized[i] = s->array[i - 1];
    }
    s->array = resized;
    return 0;
}

main.c

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

int main(int argc, const char * argv[]) {
    StringVector arr_test = init_string_vector();
    char value[] = "First Value";
    char new_value[] = "Second Value";
    append_string_vector(&arr_test, value);
    preappend_string_vector(&arr_test, new_value);
    printf("%s\n", arr_test.array[0]);
    // yields "Second Value"
}

CodePudding user response：

To prepend an element to a dynamically allocated array:

allocate room for another element (this memory is expanded from the end of the array)
shift all elements by one place towards the end of the array
place the new value in the first index
increment the stored length

In this example I have duplicated the string input, to match the behaviour of your append function. Note the input can be const qualified.

Remember that memmove allows the source and destination memory to overlap.

int prepend_string_vector(StringVector *s, const char *value) {
    char *str;

    if (!value || !(str = strdup(value)))
        return -1;

    void *mem = realloc(s->array, sizeof *s->array * (s->len   1));

    if (!mem) {
        free(str);
        return -1;
    }

    s->array = mem;
    memmove(s->array   1, s->array, sizeof *s->array * s->len);
    s->array[0] = str;
    s->len  ;

    return 0;
}

This operation is O(n). If you want faster prepends, consider a different data structure (e.g., linked list).

CodePudding user response：

Here's my version of what I think you should do. The data type char ** in the structure is appropriate for strings; it is not appropriate for other types. The correct size of strings is sizeof(char *), not sizeof(char). This code avoids reallocating the array every time by keeping track of the amount of space allocated and the amount of space in use. It approximately doubles the space allocated when it does reallocate.

It always copies the string passed in — your code is not consistent. The functions return 0 on success and -1 on failure; your code was not consistent. The inconsistently-named string_vector_mem_alloc() function isn't needed. I'd probably have init_stringvector() take a pointer to the stricture, and maybe a size to preallocate.

/* vector.h */
#ifndef VECTOR_H_INCLUDED
#define VECTOR_H_INCLUDED

#include <stddef.h>     /* size_t */

typedef struct
{
    char **array;
    size_t len;     /* Number of elements in use */
    size_t max;     /* Number of elements allocated */
    size_t elem;    /* Size of each element */
} StringVector;

extern StringVector init_string_vector(void);

extern int append_string_vector(StringVector *s, const char *value);

extern int preappend_string_vector(StringVector *s, const char *value);

extern void destroy_string_vector(StringVector *s);

#endif /* VECTOR_H_INCLUDED */

/* vector.c */

//#include "vector.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

StringVector init_string_vector(void)
{
    StringVector array;
    array.len = 0;
    array.max = 0;
    array.elem = sizeof(char *);
    array.array = NULL;
    return array;
}

void destroy_string_vector(StringVector *s)
{
    if (s != NULL)
    {
        for (size_t i = 0; i < s->len; i  )
            free(s->array[i]);
        free(s->array);
        s->array = NULL;
        s->len = s->max = s->elem = 0;
    }
}

int append_string_vector(StringVector *s, const char *value)
{
    char *copy = strdup(value);
    if (copy == NULL)
        return -1;
    assert(s->len <= s->max);

    if (s->len == s->max)
    {
        size_t new_max = 2 * s->max   2;
        void *new_ptr = realloc(s->array, new_max * s->elem);
        if (new_ptr == NULL)
        {
            free(copy);
            return -1;
        }
        s->max = new_max;
        s->array = new_ptr;
    }

    s->array[s->len  ] = copy;
    return 0;
}

int preappend_string_vector(StringVector *s, const char *value)
{
    char *copy = strdup(value);
    if (!value)
        return -1;

    if (s->len == s->max)
    {
        size_t new_max = 2 * s->max   2;
        void *new_ptr = realloc(s->array, new_max * s->elem);
        if (new_ptr == NULL)
        {
            free(copy);
            return -1;
        }
        s->max = new_max;
        s->array = new_ptr;
    }

    memmove(&s->array[1], &s->array[0], s->len * s->elem);
    s->len  ;
    s->array[0] = copy;
    return 0;
}

static void dump_string_vector(const char *tag, const StringVector * s)
{
    printf("%s (%p):\n", tag, (void *)s);
    if (s != NULL)
    {
        printf("  len = %zu, max = %zu, elem = %zu\n", s->len, s->max, s->elem);
        for (size_t i = 0; i < s->len; i  )
            printf("  %zu [%s]\n", i, s->array[i]);
    }
}

/* main.c */

// #include <stdio.h>
// #include "vector.h"

int main(void)
{
    StringVector arr_test = init_string_vector();
    dump_string_vector("After initialization", &arr_test);
    char value[] = "First Value - appended";
    char new_value[] = "Second Value - prepended";
    append_string_vector(&arr_test, value);
    dump_string_vector("After append", &arr_test);
    printf("%s\n", arr_test.array[0]);
    preappend_string_vector(&arr_test, new_value);
    dump_string_vector("After prepend", &arr_test);
    printf("%s\n", arr_test.array[0]);
    printf("%s\n", arr_test.array[1]);

    size_t counter = 3;
    for (size_t i = 0; i < 4; i  )
    {
        char buffer[32];
        snprintf(buffer, sizeof(buffer), "%zu: appended", counter  );
        append_string_vector(&arr_test, buffer);
        snprintf(buffer, sizeof(buffer), "%zu: prepended", counter  );
        preappend_string_vector(&arr_test, buffer);
    }
    dump_string_vector("After loop", &arr_test);

    destroy_string_vector(&arr_test);
    return 0;
}

Example output:

After initialization (0x7ff7b2bc52b0):
  len = 0, max = 0, elem = 8
After append (0x7ff7b2bc52b0):
  len = 1, max = 2, elem = 8
  0 [First Value - appended]
First Value - appended
After prepend (0x7ff7b2bc52b0):
  len = 2, max = 2, elem = 8
  0 [Second Value - prepended]
  1 [First Value - appended]
Second Value - prepended
First Value - appended
After loop (0x7ff7b2bc52b0):
  len = 10, max = 14, elem = 8
  0 [10: prepended]
  1 [8: prepended]
  2 [6: prepended]
  3 [4: prepended]
  4 [Second Value - prepended]
  5 [First Value - appended]
  6 [3: appended]
  7 [5: appended]
  8 [7: appended]
  9 [9: appended]