5

我在 C 中创建了一个简单的动态数组。

typedef struct varray_t
{
    void **memory;
    size_t allocated;
    size_t used;
    int index;              
} varray;

void
varray_init(varray **array)
{
    *array = (varray*) malloc (sizeof(varray));    
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

void
varray_push(varray *array, void *data, size_t size)
{
    if ((array->allocated - array->used) < size) {
        array->memory = realloc(array->memory, array->allocated + size);
        array->allocated = array->allocated + size;
    }

    array->used = array->used + size;   
    array->memory[++array->index] = data;
}

int
varray_length(varray *array)
{
    return array->index + 1;
}

void
varray_clear(varray *array)
{
    int i;
    for(i = 0; i < varray_length(array); i++)
    {
        array->memory[i] = NULL;
    }    
    array->used = 0;
    array->index = -1;
}

void 
varray_free(varray *array)
{
    free(array->memory);
    free(array);
}

void*
varray_get(varray *array, int index)
{
    if (index < 0 || index > array->index)
        return NULL;

    return array->memory[index];
}

这工作正常。但是要将项目添加到数组中，调用者必须传入要添加的元素的大小。我想不出另一种方法来获取传入的大小void*。我想知道是否有更好的设计方法varray_push(varray *array, void *data, size_t size)可以size推断出来？

任何帮助都会很棒

建议后编辑的代码

我的数组将只包含指针元素。我根据 Blastfurnace 的建议修改了代码。新代码将按sizeof(void*)常数比例使用和调整内存大小，以在插入时获得摊销的常数时间。

void
varray_push(varray *array, void *data)
{
    size_t toallocate;
    size_t size = sizeof(void*);
    if ((array->allocated - array->used) < size) {
        toallocate = array->allocated == 0 ? size : (array->allocated * 2);
        array->memory = realloc(array->memory, toallocate);
        array->allocated = array->allocated + toallocate;
    }

    array->memory[++array->index] = data;
    array->used = array->used + size;
}
4

2 回答 2

2

如果数组一次只包含一种类型，那么您可以将数组类型的大小存储在 varray_init 中。

另外，我的建议是，不是为每个元素分配新鲜的内存，而是每次都可以为恒定大小分配内存，即首先为 16 个元素分配内存，然后当你发现数组已满时，将元素重新分配为 16 + 16 = 32 个元素。通过这种方式，您可以避免一次又一次地调用 malloc，并且单独为小尺寸数据保持 malloc 并不是一个好主意。

编辑：在考虑 Blastfurnace 评论之后，我觉得如果您的意图是存储数据而不是指向数据的指针，那么您实际上应该对数据进行 memcpy 而不是分配。

于 2012-05-11T05:42:20.550 回答
0

我有一个简单易用的链表实现，您可以使用它。我不会说这是教科书的质量，但很容易：https ://github.com/inorton/xrlist

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

xr_list_t * mylist = xrlist_new();

xrlist_push(mylist, (void*) ptr1);
xrlist_push(mylist, (void*) ptr2);

你像这样迭代： -

xr_list_item_t * iter = mylist->head;
while ( iter != NULL ) 
{
  printf(" * item [0x%x] contains [%s]\n",
    (unsigned int) iter->object, (char*) iter->object );
  iter = iter->next; 
}

你也有通常的删除/添加/释放功能。在此处查看更多示例。

如果你想要像字典这样的随机访问数据，你也可以试试https://github.com/inorton/xrhash

于 2012-05-11T06:19:13.710 回答