使C语言动态数组通用化

Question

使C语言动态数组通用化

carraysgenericsdynamic

6

我刚写了一个很好的库，用于处理在C中分配的堆上动态数组。它支持许多操作，使用起来相对简单，感觉几乎像一个普通的老数组。它也很容易模拟基于它的许多数据结构（栈、队列、堆等等）。

它可以处理任何类型的数组，但问题在于每个编译只有一个类型。C没有模板，所以在同一个程序中无法同时拥有int和char类型的动态数组，这是一个问题。

我没有找到任何真正的解决方案，所有我找到的都涉及void*，而且不，我不想要一个void指针数组。能够放置指针很好，但我也想能够有一个原始数据类型的数组。（例如，你可以添加3，并像这样访问它：array.data [i]

我应该：

1.为每种要使用的类型复制/粘贴库（可怕，但它会起作用并且高效） 2.将其制作成巨大的宏，我可以展开所需的类型（因此它将具有与1相同的效果，但更加优雅和可用） 3.使指向元素的大小成为动态数组结构的一部分的变量。大多数情况下都可以工作，但是直接使用动态数组类型的函数将存在问题。void*并不总是一个可行的选项。 4.放弃这个想法，每当我需要这样的高级功能时使用C++。

该库的工作方式如下：用法

/* Variable length array library for C language
 * Usage :
 * Declare a variable length array like this :
 *
 * da my_array;
 *
 * Always initialize like this :
 * 
 * da_init(&da);             // Creates a clean empty array
 *
 * Set a length to an array :
 *
 * da_setlength(&da, n);     // Note : if elements are added they'll be uninitialized
 *                             // If elements are removed, they're permanently lost
 *
 * Always free memory before it goes out of scope (avoid mem leaks !)
 *
 * da_destroy(&da);
 *
 * Access elements much like a normal array :
 *   - No boundary checks :           da.data[i]
 *   - With boundary checks (debug) : da_get(data, i)
 *
 * da.length;    // Return the current length of the variable length array (do NOT set the length by affecting this !! Use da_setlength instead.)
 *
 * You can add single elements at the end and beginning of array with
 *
 * da_add(&da, value);       // Add at the end
 * da_push(&da, value);      // Add at the front
 *
 * Retrieve values at the end and front of array (while removing them) with
 *
 * da_remove(&da);          // From the end
 * da_pop(&da);             // From the front
 *
 * Concatenate it with a standard array or another variable length array of same type with
 *
 * da_append(&da, array, array_length);  // Standard array
 * da_append(&da, &db);                 // Another variable length array
 */

实现（非常抱歉，这是一个庞大的内容，但我必须就问题完整性进行解答）。

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

// Increment by which blocks are reserved on the heap
#define ALLOC_BLOCK_SIZE 16

// The type that the variable length array will contain. In this case it's "int", but it can be anything really (including pointers, arrays, structs, etc...)
typedef int da_type;

// Commend this to disable all kinds of bounds and security checks (once you're sure your program is fully tested, gains efficiency)
#define DEBUG_RUNTIME_CHECK_BOUNDS

// Data structure for variable length array variables
typedef struct
{
    da_type *start; // Points to start of memory allocated region
    da_type *data;      // Points to logical start of array
    da_type *end;       // Points to end of memory allocated region
    size_t length;      // Length of the array
}
da;

// Initialize variable length array, allocate 2 blocks and put start pointer at the beginning
void da_init(da *da)
{
    da_type *ptr = malloc(ALLOC_BLOCK_SIZE * sizeof(da_type));
    if(ptr == 0) exit(1);
    da->start = ptr;
    da->data = ptr;
    da->end = da->start + ALLOC_BLOCK_SIZE;
    da->length = 0;
}

// Set the da size directly
void da_setlength(da *da, size_t newsize)
{
    if(newsize % ALLOC_BLOCK_SIZE != 0)
        newsize += ALLOC_BLOCK_SIZE - newsize % ALLOC_BLOCK_SIZE;

    ptrdiff_t offs = da->data - da->start;
    da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
    if(!ptr) exit(1);

    da->start = ptr;
    da->data = ptr + offs;
    da->end = ptr + newsize;
    da->length = newsize;
}

// Destroy the variable length array (basically just frees memory)
void da_destroy(da* da)
{
    free(da->start);
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
    da->start = NULL;
    da->data = NULL;
    da->end = NULL;
    da->length = 0;
#endif
}

// Get an element of the array with it's index
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
    //Get an element of the array with bounds checking
    da_type da_get(da *da, unsigned int index)
    {
        if(index >= da->length)
        {
            printf("da error : index %u is out of bounds\n", index);
            exit(1);
        }
        return da->data[index];
    }

    //Set an element of the array with bounds checking
    void da_set(da *da, unsigned int index, da_type data)
    {
        if(index >= da->length)
        {
            printf("da error : index %u is out of bounds\n", index);
            exit(1);
        }
        da->data[index] = data;
    }
#else
    //Get an element of the array without bounds checking
    #define da_get(da, index) ((da)->data[(index)])

    //Set an element of the array without bounds checking
    #define da_set(da, index, v) (da_get(da, index) = v)
#endif


// Add an element at the end of the array
void da_add(da *da, da_type i)
{   // If no more memory
    if(da->data + da->length >= da->end)
    {   // Increase size of allocated memory block
        ptrdiff_t offset = da->data - da->start;
        ptrdiff_t newsize = da->end - da->start + ALLOC_BLOCK_SIZE;
        da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
        if(!ptr) exit(1);

        da->data = ptr + offset;
        da->end = ptr + newsize;
        da->start = ptr;
    }
    da->data[da->length] = i;
    da->length += 1;
}

// Remove element at the end of the array (and returns it)
da_type da_remove(da *da)
{
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
    if(da->length == 0)
    {
        printf("Error - try to remove item from empty array");
        exit(1);
    }
#endif
    //Read last element of the array
    da->length -= 1;
    da_type ret_value = da->data[da->length];
    //Remove redundant memory if there is too much of it
    if(da->end - (da->data + da->length) > ALLOC_BLOCK_SIZE)
    {
        ptrdiff_t offset = da->data - da->start;
        ptrdiff_t newsize = da->end - da->start - ALLOC_BLOCK_SIZE;
        da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
        if(!ptr) exit(1);

        da->data = ptr + offset;
        da->end = ptr + newsize;
        da->start = ptr;
    }
    return ret_value;
}

// Add element at the start of array
void da_push(da *da, da_type i)
{   //If array reaches bottom of the allocated space, we need to allocate more
    if(da->data == da->start)
    {
        ptrdiff_t newsize = da->end - da->start + ALLOC_BLOCK_SIZE;
        da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
        if(!ptr) exit(1);
        memmove(ptr + ALLOC_BLOCK_SIZE, ptr, da->length * sizeof(da_type));

        da->data = ptr + ALLOC_BLOCK_SIZE;
        da->start = ptr;
        da->end = ptr + newsize;
    }
    // Store element at start of array
    da->length += 1;
    da->data -= 1;
    da->data[0] = i;
}

//Remove 1st element of array (and return it)
da_type da_pop(da *da)
{
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
    if(da->length == 0)
    {
        printf("Error - try to remove item from empty array");
        exit(1);
    }
#endif
    da_type ret_value = da->data[0];
    da->length -= 1;
    da->data += 1;
    ptrdiff_t offset = da->data - da->start;
    if(offset > ALLOC_BLOCK_SIZE)
    {
        ptrdiff_t newsize = da->end - da->start - ALLOC_BLOCK_SIZE;
        da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
        if(!ptr) exit(1);
        memmove(ptr + offset - ALLOC_BLOCK_SIZE, ptr + offset, da->length * sizeof(da_type));

        da->data = ptr + offset - ALLOC_BLOCK_SIZE;
        da->start = ptr;
        da->end = ptr + newsize;
    }
    return ret_value;
}

// Append array t to s
void da_array_append(da *s, const da_type *t, size_t t_len)
{
    if((s->length + t_len) > (s->end - s->start))
    {   // Should reserve more space in the heap
        ptrdiff_t offset = s->data - s->start;
        ptrdiff_t newsize = s->length + t_len;
        // Guarantees that new size is multiple of alloc block size
        if(t_len % ALLOC_BLOCK_SIZE != 0)
            newsize += ALLOC_BLOCK_SIZE - (t_len % ALLOC_BLOCK_SIZE);

        da_type *ptr = malloc(newsize * sizeof(da_type));
        if(!ptr) exit(1);

        memcpy(ptr, s->data, s->length * sizeof(da_type));
        memcpy(ptr + s->length, t, t_len * sizeof(da_type));
        free(s->start);
        s->data = ptr;
        s->start = ptr;
        s->end = ptr + newsize;
    }
    else
        // Enough space in heap buffer -> do it the simple way
        memmove(s->data + s->length, t, t_len * sizeof(da_type));

    s->length += t_len;
}

// Append a da is a particular case of appending an array
#define da_append(s, t) da_array_append(s, (t)->data, (t)->length)

- Bregalad

2个回答

1

使用 union 来处理你的通用数据...

typedef union
{
    int *pIntArr;
    double *pDblArr;
    struct *pStructArr;
    ... // Etc.
} genericData;

使用结构体来保存这些信息，这样您还可以包含通用数据联合正在保存的数据及其长度。

typedef struct
{
    genericData data;
    int dataType;   // 0 == int, 1 == double, 2 == etc.
    int dataLength; // Number of elements in array
} genericDataType;

- Fiddling Bits

2

如果你想存储一个非常大的结构体，那该怎么办呢？如果存储较小的对象，则会浪费内存。此外，你的解决方案需要在代码后面添加一个开关。 - this

1

@self。不确定您所说的浪费内存是什么意思。 - Fiddling Bits

一个char指针和大小为1000的char数组的联合体有多大？ - this

2

@self。这并不是“浪费内存”——联合体包含指针。并不是有一个联合体的数组。有一个指向不同类型数组（第一个元素）的指针的联合体。这使得差异巨大。(但即使你所声称的情况确实存在，为什么要费心呢？现在内存很便宜。除非这明显导致了大量的内存被多余地保留，否则不值得担心联合体的大小。) - user529758

@H2CO3 说得非常优雅。 - Fiddling Bits

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user529758 · Accepted Answer

我会采用预处理器技巧来解决这个问题。在必要时，您可以添加类型信息，从而实现类似于C++中的模板。

struct da_impl {
    size_t len;
    size_t elem_size;
    size_t allocsize; // or whatever
};

void da_init_impl(struct da_impl *impl, size_t elem_size)
{
    impl->len = 0;
    impl->elem_size = elem_size;
    impl->allocsize = 0;
}

#define DA_TEMPLATE(t) struct { da_impl impl; t *data; }
#define da_init(a) da_init_impl(&a.impl, sizeof(*a.data))

// etc.

然后你可以像这样使用它：

DA_TEMPLATE(int) intArray;
da_init(intArray);

da_append(intArray, 42);

int foo = intArray.data[0];

一个缺点是这会创建一个匿名结构，你不能在其作用域之外真正使用它，但也许你可以接受这一点...