我已经在纯C中实现了ArrayList。
标题(arraylist.h)：
#pragma once
struct ArrayListImpl;
typedef int LISTTYPE;
typedef struct ArrayListImpl ArrayList;
ArrayList* new_ArrayList(int iSize);
void destroy(ArrayList* list);
int indexOf(ArrayList* list, LISTTYPE element);
void add(ArrayList* list, LISTTYPE element);
void addBefore(ArrayList* list, int index, LISTTYPE element);
void clear(ArrayList* list);
_Bool contains(ArrayList* list, LISTTYPE element);
_Bool removeEl(ArrayList* list, LISTTYPE element);
void removeFrom(ArrayList* list, int index);
void set(ArrayList* list, int index, LISTTYPE element);
int size(ArrayList* list);
void print(ArrayList* list);
void printInfo(ArrayList* list);
实现(arraylist.c)：
#include "arraylist.h"
#include <stdlib.h>
#include <stdio.h>
struct ArrayListImpl
{
int size, buffer, origBuffer;
LISTTYPE* data;
};
void incBuffer(ArrayList* list)
{
if (list->size == list->buffer)
{
list->buffer = (int)(list->buffer * 1.5 + 1);
list->data = (LISTTYPE*)realloc(list->data, sizeof(LISTTYPE) * list->buffer);
}
}
void decBuffer(ArrayList* list)
{
if (list->size < list->buffer / 2.5 && list->buffer > list->origBuffer)
{
list->buffer = max(list->origBuffer, list->buffer / 2);
list->data=(LISTTYPE*)realloc(list->data, sizeof(LISTTYPE) * list->buffer);
}
}
void resetBuffer(ArrayList* list)
{
list->buffer = list->origBuffer;
list->data = (LISTTYPE*)realloc(list->data, sizeof(LISTTYPE) * list->buffer);
}
ArrayList* new_ArrayList(int buffer)
{
ArrayList* out;
out = (ArrayList*)malloc(sizeof out);
out->size = 0;
out->buffer = buffer;
out->origBuffer = buffer;
out->data = (LISTTYPE*)malloc(buffer * sizeof(LISTTYPE));
return out;
}
void destroy(ArrayList* list)
{
free(list->data);
}
int indexOf(ArrayList* list, LISTTYPE element)
{
for (int i = 0; i < list->size; ++i)
{
if (list->data[i] == element)
return i;
}
return -1;
}
void add(ArrayList* list, LISTTYPE element)
{
incBuffer(list);
list->data[list->size++] = element;
}
void addBefore(ArrayList* list, int from, LISTTYPE element)
{
if (from < 0 || from > list->size)
{
printf("[ERROR] Trying to add before %d. element of list having size %dn", from, list->size);
return;
}
incBuffer(list);
++list->size;
for (int i = list->size; i > from; --i)
{
list->data[i] = list->data[i - 1];
}
list->data[from] = element;
}
_Bool removeEl(ArrayList* list, LISTTYPE element)
{
int id = indexOf(list, element);
if (id == -1)
return 0;
--list->size;
for (int i = id; i < list->size; ++i)
{
list->data[i] = list->data[i + 1];
}
decBuffer(list);
return 1;
}
void removeFrom(ArrayList* list, int index)
{
if (index < 0 || index >= list->size)
{
printf("[ERROR] Trying to remove %d. element of list having size %dn", index, list->size);
return;
}
--list->size;
for (int i = index; i < list->size; ++i)
{
list->data[i] = list->data[i + 1];
}
decBuffer(list);
}
_Bool contains(ArrayList* list, LISTTYPE element)
{
return indexOf(list, element) != -1;
}
int size(ArrayList* list)
{
return list->size;
}
void clear(ArrayList* list)
{
list->size = 0;
resetBuffer(list);
}
void set(ArrayList* list, int index, LISTTYPE element)
{
if (index < 0 || index >= list->size)
{
printf("[ERROR] Trying to set %d. element of list having size %dn", index, list->size);
return;
}
list->data[index] = element;
}
void print(ArrayList* list)
{
printf("--- ArrayList ---n");
for (int i = 0; i < list->size; ++i)
{
printf("%d.: %dn", i, list->data[i]);
}
printf("n-------------------n");
}
void printInfo(ArrayList* list)
{
printf("--- ArrayList INFO ---nSize: %dnElement size : %dnBuffer : %dn", list->size, sizeof(int), list->buffer);
}
正如您所看到的，它只适用于头文件中定义了LISTTYPE类型的数据。我的问题是，我如何才能使它与任何类型的数据类型通用？例如，以某种方式将LISTTYPE添加到它的构造函数中，而不是它的头。有可能做到这一点吗？或者至少在纯C中做一些类似的事情，而不是在C++中？
您必须将内部列表管理的关注点与客户列表数据的关注点分开。您的列表管理数据必须是强类型的，但您对客户列表数据的视图应该是不透明的(void*)。您的界面设计应该保留这种关注点的分离。
没有必要在arraylist.h中声明或定义ArrayListImpl。您的客户不需要知道它。拥有arraylist类型是很好的，但如果它只是一个不透明的句柄，实现为索引值、哈希或数据指针(void*)就足够了。基本上，无论你给客户提供什么来跟踪他们的列表，他们都应该无法从其声明或使用中了解任何实现细节。如果你给他们一个指向内部管理结构的指针，他们对它的看法应该是无效的。您总是可以从void*转换为任何内部数据结构。
我建议您重新考虑您的界面。只使用ArrayList.h文件编写一些单元测试，并让它们进行编译(它们显然不会链接)。从客户的角度了解如何使用您的界面。另外，在头文件中添加注释。我们不应该猜测iSize是指定数组的大小、元素的数量还是元素的大小。如果客户在初始化列表时指定一个计数和元素大小，可能会更实用。
一些示例代码：
在ArrayList.h 中
#include <stdbool.h>
#include <stdint.h>
// The current implementation of the API defined herein is not thread safe.s
// ArrayList should be treated as an opaque data object, never intended
// to be dereferenced by client code.
typedef void* ArrayList;
// Define default module initialization.
#define ARRAYLIST_DEFAULT_NUM_LISTS 4
#define ARRAYLIST_DEFAULT_INCREMENT_SIZE 8
// InitializeArrayListModule(size_t numLists, size_t incrementSize);
// Optional module initializer. The number of lists can grow until memory
// runs out, but performance may not be optimal and the heap can get
// fragmented.
// Call this function only if you're going to be allocating more or less
// than the default values.
// Arguments:
// numLists Number of lists the internal data structures are preallocated
// for. Internal
// default is ARRAYLIST_DEFAULT_NUM_LISTS.
// incrementSize Number of additional internal data structures to allocate
// when a call to NewArrayList() triggers a realocation of data structures.
// Internal default is DEFAULT_INCREMENT_SIZE.
// Returns:
// true if enough internal data structures can be allocated to support the
// specified number of lists.
// false if allocations failed, the function has been called more than once
// or NewArrayList has
// already been called.
// Notes:
// 1. List management data structures are stored in separate memory from
// client's list data.
bool InitializeArrayListModule(size_t numLists, size_t incrementSize);
// NewArrayList(size_t, size_t)
// The only way to properly initialize an ArrayList object.
// Arguments:
// initialCapacity Number of initial elements to allocate, must not be
// zero.
// sizeofElements Size in bytes of each element, must not be zero.
// Returns:
// A valid ArrayList on success.
// NULL on failure.
ArrayList NewArrayList(size_t initialCapacity, size_t sizeofElement);
// DestroyArrayList(ArrayList arrayList)
// The only way to properly destroy an ArrayList object.
// Arguments:
// arrayList ArrayList object returned from NewArrayList, or NULL.
// Returns:
// NULL.
// Example:
// ArrayList arrayList = NewArrayList(capacity, sizeofElement);
// arrayList = DestroyArrayList(arrayList);
ArrayList DestroyArrayList(ArrayList arrayList);
// AddArrayListItem(ArrayList, void *item)
// Copies elementSize bytes from the memory pointed to by item.
// Arguments:
// arrayList A valid ArrayList object returned from NewArrayList.
// element Pointer to the data to add to the list.
// Returns:
// true if successful.
bool AddArrayListItem(ArrayList arrayList, void *element);
在UTArrayList.c 中
#include <stdbool.h>
#include <stdio.h>
//#include "ArrayList.h"
void _UTShowTestResult(char *testFuncName, bool result)
{
if (result)
{
printf("%s() passed.n", testFuncName);
}
else
{
printf("%s() failed.n", testFuncName);
}
}
#define UTShowTestResult(funcName) _UTShowTestResult(#funcName, funcName##())
// In UTArrayList.c
// TODO: Add logging.
#include <limits.h>
// Smoke test: bool InitializeArrayListModule(size_t numLists, size_t incrementSize);
bool UTInitializeArrayListModule()
{
return InitializeArrayListModule(1, 4);
}
// Smoke test: ArrayList NewArrayList(size_t, size_t).
bool UTNewArrayList()
{
// Happy path...
for (size_t capacity = 1; capacity <= (64 * 1024); capacity += 1024)
{
for (size_t elementSize = 1; elementSize <= (64 * 1024); elementSize += 1024)
{
ArrayList testList = NewArrayList(capacity, elementSize);
if (NULL == testList)
{
return false;
}
}
}
// TODO: Test that expected failure paths fail gracefully.
return true;
}
// Smoke test: ArrayList DestroyArrayList(ArrayList arrayList)
bool UTDestroyArrayList()
{
ArrayList arrayList = NewArrayList(1, 1);
// Verify works with NULL.
if (NULL != DestroyArrayList(NULL))
{
return false;
}
// Verify works with valid arrayList object, but don't let the test overwrite it yet.
if (NULL != DestroyArrayList(&arrayList))
{
return false;
}
// Verify works twice on same value.
arrayList = DestroyArrayList(&arrayList); // The correct way to call DestroyArrayList().
if (NULL != arrayList)
{
return false;
}
return true;
}
// Smoke test: bool AddArrayListItem(ArrayList arrayList, void *element)
bool UTAddArrayListItem()
{
// TODO: Verify list items are correct and remain in proper order over
// list operations, as soon we have an implementation for iterating
// over the list.
// TODO: Verify items of different sizes can added successfully.
const char* str1 = "str1";
ArrayList arrayList = NewArrayList(2, sizeof(char*));
return AddArrayListItem(arrayList, str1);
}
// ArrayList Unit Test Driver.
int main(int argc, char **argv)
{
// TODO: As the interface is fleshed out, add unit test calls.
UTShowTestResult(UTInitializeArrayListModule);
UTShowTestResult(UTNewArrayList);
UTShowTestResult(UTDestroyArrayList);
UTShowTestResult(UTAddArrayListItem);
}
在ArrayList.c 中
#include <stdlib.h>
#include "ArrayList.h"
typedef struct _List
{
size_t capacity;
size_t elementSize;
size_t count;
void* data;
} List;
static size_t _listCapacity = ARRAYLIST_DEFAULT_NUM_LISTS;
static size_t _incrementSize = ARRAYLIST_DEFAULT_INCREMENT_SIZE;
static size_t _count = 0;
static List *_lists = NULL;
static List *_nextList = NULL;
// TODO: Add implementations as interfaces and unit tests are added.
static bool _InitializeModule()
{
// Always fail to initialize twice!
if (NULL == _lists)
{
_lists = calloc(_listCapacity, sizeof(List));
_nextList = _lists;
}
return (_lists != NULL);
}
static bool _ReallocateLists()
{
List *newLists = calloc(_listCapacity + _incrementSize, sizeof(List));
if (NULL != newLists)
{
for (size_t idx = 0; idx < _listCapacity; idx++)
{
newLists[idx] = _lists[idx];
}
List *tmp = _lists;
_lists = newLists;
free(tmp);
_nextList = _lists + _listCapacity;
}
return (NULL != _lists);
}
bool InitializeArrayListModule(size_t numLists, size_t incrementSize)
{
if (NULL == _lists)
{
_listCapacity = numLists;
_incrementSize = incrementSize;
}
return _InitializeModule();
}
ArrayList NewArrayList(size_t initialCapacity, size_t sizeofElement)
{
if (NULL == _lists)
{
if (!_InitializeModule()) return NULL;
}
if (_listCapacity < _count)
{
if (!_ReallocateLists()) return NULL;
}
List *p = &(_lists[_count]);
p->capacity = initialCapacity;
p->elementSize = sizeofElement;
p->data = calloc(initialCapacity, sizeofElement);
return p;
}
ArrayList DestroyArrayList(ArrayList arrayList)
{
List *p = arrayList; // Convert from void* to List*.
List *last = _lists + _listCapacity;
// Sanity checks...
bool isInRange = (p >= _lists) && (p <= last);
bool isAligned = 0 == ((p - _lists) % sizeof(List));
if (isInRange && isAligned)
{
free(p->data);
memset(p, 0, sizeof(List));
}
return NULL;
}
bool AddArrayListItem(ArrayList arrayList, void *item)
{
// TODO: find the list, use similar logic to how _lists is managed, to add this item to that lists data array.
// HINT: memcpy(itemAddress, item, sizeofElement);
return false;
}
上面演示了void指针可以用作不透明的数据对象，以保护您的实现不受客户端数据类型的影响，并保护客户端不受您的影响。所提供的单元测试从客户端的角度演示了API的使用，并为您提供了一个试验API和测试实现的平台。