C言語環境では,独自のVectorコンテナを作成する.
16964 ワード
C言語環境では,独自のVectorコンテナを作成する.
王宇がオリジナルで発表した.
最近の仕事では、いくつかの統計データの機能を標準Cで実現する必要があります.開発中に容器がないのはとても不便なので、簡単なVector容器を自分で作成してみました.
一、機能説明:
このVectorの使用方法を一例で説明します.
#include "containers.h"
#include
//
typedef struct tagTextStruct
{
int key;
char* value;
}TestStruct;
//
static void ABORT( char *file,int line)
{
fprintf(stderr ,"*****
ABORT
File %s Line %d
**********
",file,line);
abort();
}
#define Abort () ABORT(__FILE__,__LINE__)
//
static int destructorFunc( void *v)
{
// Vector
TestStruct* ts = (TestStruct*)v;
if(ts->value != NULL )
{
int l = strlen (ts->value);
//
free(ts->value);
ts->value = NULL;
}
return 0;
}
// Vector
static void PrintVector(Vector *AL)
{
size_t i;
TestStruct* ts;
// Vector ，
printf("Count %ld, Capacity %ld
",(long)iVector. Size(AL),(long )iVector.GetCapacity(AL));
// Vector
for (i=0; ikey);
printf("%s
" ,ts->value);
}
printf("
" );
}
// Vector
static int testVector(Vector** AL)
{
int errors=0;
char* s1 = "ts1 value." ;
char* s2 = "ts2 value" ;
char* temp1 = NULL ;
char* temp2 = NULL ;
TestStruct ts1, ts2;
*AL = iVector. Create(sizeof (TestStruct),5);
// ， destructorFunc 。
iVector. SetDestructor(*AL, destructorFunc );
// ，
ts1.key = 1;
temp1 = ( char*)malloc (strlen(s1) + 1);
if(temp1 == NULL)
{
Abort();
}
strcpy(temp1, s1);
ts1.value = temp1;
ts2.key = 2;
temp2 = ( char*)malloc (strlen(s2) + 1);
if(temp2 == NULL)
{
Abort();
}
strcpy(temp2, s2);
ts2.value = temp2;
// Vecotor
iVector. Add(*AL,&ts1);
iVector. Add(*AL,&ts2);
// Vector
iVector. Erase(*AL, &ts1);
//
if (1 != iVector.Size (*AL))
Abort();
return errors;
}
//
int main (void)
{
int errors=0;
Vector* AL = NULL;
// Vector
errors += testVector (&AL);
// Vector
iVector.Finalize(*AL);
return errors;
}
二、Vectorの構造:
宣言Vectorタイプ:
/*----------------------------------------------------------------------------*/
/* Definition of the vector type */
/*----------------------------------------------------------------------------*/
struct _Vector {
VectorInterface *VTable; /* The table of functions */
size_t count; /* number of elements in the array */
unsigned int Flags; /* Read-only or other flags */
size_t ElementSize; /* Size of the elements stored in this array. */
void *contents; /* The contents of the collection */
size_t capacity; /* allocated space in the contents vector */
unsigned timestamp; /* Incremented at each change */
CompareFunction CompareFn; /* Element comparison function */
ErrorFunction RaiseError; /* Error function */
const ContainerAllocator *Allocator;
DestructorFunction DestructorFn;
} ;
Vectorインタフェースの宣言:
/****************************************************************************
* Vectors Interface *
****************************************************************************/
/* Definition of the functions associated with this type. */
typedef struct tagVector {
size_t (* Size)(const Vector *AL);
int (* Clear)(Vector *AL);
int (* Erase)(Vector *AL,const void *);
int (* EraseAll)(Vector *AL,const void *);
int (* Finalize)(Vector *AL);
int (* Apply)(Vector *AL,int (*Applyfn)( void *element,void * arg),void *arg);
int (* Equal)(const Vector *first,const Vector *second);
Vector *(* Copy)(const Vector *AL);
ErrorFunction (* SetErrorFunction)(Vector *AL,ErrorFunction );
size_t (* Sizeof)(const Vector *AL);
Vector *(* Load)(FILE *stream, ReadFunction readFn,void *arg);
size_t (* GetElementSize)(const Vector *AL);
int (* Add)(Vector *AL,const void *newval);
void *(* GetElement)(const Vector *AL,size_t idx);
int (* EraseAt)(Vector *AL,size_t idx);
int (* ReplaceAt)(Vector *AL,size_t idx,void *newval);
int (* IndexOf)(const Vector *AL,const void *data,void *ExtraArgs,size_t *result);
/* Vector container specific fields */
size_t (* GetCapacity)(const Vector *AL);
int (* SetCapacity)(Vector *AL,size_t newCapacity);
CompareFunction (* SetCompareFunction)(Vector *l,CompareFunction fn);
int (* Sort)(Vector *AL);
Vector *(* Create)(size_t elementsize,size_t startsize);
Vector *(* CreateWithAllocator)(size_t elemsiz,size_t startsiz,const ContainerAllocator *mm);
int (* CopyElement)(const Vector *AL,size_t idx,void *outbuf);
void **(* CopyTo)(const Vector *AL);
int (* Append)(Vector *AL1, Vector *AL2);
const ContainerAllocator *(* GetAllocator)(const Vector *AL);
DestructorFunction (* SetDestructor)(Vector *v,DestructorFunction fn);
int (* SearchWithKey)(Vector *vec,size_t startByte,size_t sizeKey,size_t startIndex,void *item,size_t *result);
int (* Resize)(Vector *AL,size_t newSize);
} VectorInterface;
メモリ割り当てオブジェクト:
/************************************************************************** */
/* */
/* Memory allocation object */
/* */
/************************************************************************** */
typedef struct tagAllocator {
void *(* malloc)(size_t); /* Function to allocate memory */
void (* free)(void *); /* Function to release it */
void *(* realloc)(void *,size_t);/* Function to resize a block of memory */
void *(* calloc)(size_t,size_t);
} ContainerAllocator;
三、機能の実現:
1,Vectorの作成
static Vector *CreateWithAllocator (size_t elementsize,size_t startsize,const ContainerAllocator *allocator)
{
Vector *result;
size_t es;
// Vector 。
/* Allocate space for the array list header structure */
result = allocator-> malloc(sizeof (*result));// malloc stdlib.h malloc, ContainerAllocator 。
// 。
if (result == NULL) {
iError.RaiseError( "iVector.Create",CONTAINER_ERROR_NOMEMORY );
return NULL ;
}
// 。
memset(result,0, sizeof(*result));
if (startsize == 0)
startsize = DEFAULT_START_SIZE;
// Vector 。
es = startsize * elementsize; // ， ， 。
result->contents = allocator-> malloc(es); // malloc stdlib.h malloc, ContainerAllocator 。
// 。
if (result->contents == NULL) {
iError.RaiseError( "iVector.Create",CONTAINER_ERROR_NOMEMORY ); // iError
allocator-> free(result); // free stdlib.h free, ContainerAllocator 。
result = NULL;
}
else {
//
memset(result->contents,0,es);
// Vector
result->capacity = startsize;
// Vector
result->VTable = &iVector;
// Vector
result->ElementSize = elementsize;
//
result->CompareFn = DefaultVectorCompareFunction;
result->RaiseError = iError.RaiseError;
//
result->Allocator = (ContainerAllocator *)allocator;
}
return result;
}
// ， ：Vector *(* Create)(size_t elementsize,size_t startsize);
static Vector *Create (size_t elementsize,size_t startsize)
{
return CreateWithAllocator(elementsize,startsize,CurrentAllocator);
}
2.Vectorに要素を追加するには:
// (vector->capacity), 。
static int grow(Vector *AL)
{
size_t newcapacity;
void **oldcontents;
int r = 1;
//
newcapacity = AL->capacity + 1+AL->capacity/4;
oldcontents = ( void **)AL->contents;
//
AL->contents = AL->Allocator->realloc (AL->contents,newcapacity*AL->ElementSize);
if (AL->contents == NULL ) {
NoMemory(AL,"Resize" ); // 。
AL->contents = oldcontents;
r = CONTAINER_ERROR_NOMEMORY;
}
else {
//
AL->capacity = newcapacity;
AL->timestamp++;
}
return r;
}
// ， ： int (* Add)(Vector *AL,const void *newval);
/*------------------------------------------------------------------------
Procedure: Add ID:1
Purpose: Adds an item at the end of the Vector
Input: The Vector and the item to be added
Output: The number of items in the Vector or negative if
error
Errors:
------------------------------------------------------------------------*/
static int Add(Vector *AL, const void *newval)
{
char *p;
//
if (AL == NULL ) {
return NullPtrError ("Add");
}
if (newval == NULL ) {
AL->RaiseError( "iVector.Add",CONTAINER_ERROR_BADARG );
return CONTAINER_ERROR_BADARG ;
}
//
if (AL->count >= AL->capacity) {
int r = grow (AL);
if (r <= 0)
return r;
}
//
p = ( char *)AL->contents;
p += AL-> count*AL->ElementSize;
memcpy(p,newval,AL->ElementSize);
AL->timestamp++;
++AL-> count;
return 1;
}
3、Vectorの要素を削除します.
// index Vector
static int EraseAt(Vector *AL,size_t idx)
{
char *p;
//
if (AL == NULL) {
return NullPtrError ("EraseAt");
}
if (idx >= AL-> count) {
AL->RaiseError( "iVector.Erase",CONTAINER_ERROR_INDEX ,AL,idx);
return CONTAINER_ERROR_INDEX ;
}
//
p = ( char *)AL->contents;
p += AL->ElementSize * idx;
// ，
if (AL->DestructorFn) {
AL->DestructorFn(p);
}
// ，
if (idx < (AL-> count-1)) {
memmove(p,p+AL->ElementSize,(AL->count -idx-1)*AL->ElementSize);
}
AL-> count--;
AL->timestamp++;
return 1;
}
static int EraseInternal(Vector *AL, const void *elem,int all)
{
size_t i;
char *p;
CompareInfo ci;
int result = CONTAINER_ERROR_NOTFOUND;
//
if (AL == NULL) {
return NullPtrError ("Erase");
}
if (elem == NULL) {
AL->RaiseError( "iVector.Erase",CONTAINER_ERROR_BADARG );
return CONTAINER_ERROR_BADARG ;
}
if (AL->Flags & CONTAINER_READONLY)
return ErrorReadOnly(AL,"Erase" );
restart:
p = AL->contents;
ci.ContainerLeft = AL;
ci.ContainerRight = NULL;
ci.ExtraArgs = NULL;
// Vecotr
for (i=0; i count;i++) {
// , CompareFn ， ， Vector
if (!AL->CompareFn(p,elem,&ci)) {
if (i > 0) {
//
p = GetElement(AL,--i);
result = EraseAt(AL,i+1);
} else {
//
result = EraseAt(AL,0);
// all = 0 ， Vector
if (result < 0 || all == 0) return result;
if (all) goto restart;
}
if (all == 0) return result;
result = 1;
}
p += AL->ElementSize;
}
return result;
}
// ， ： int (* Erase)(Vector *AL,const void *);
static int Erase(Vector *AL, const void *elem)
{
// 0 ，
return EraseInternal(AL,elem,0);
}
4、Vectorのサイズを決定する:
// ， ： size_t (* Size)(const Vector *AL);
static size_t Size(const Vector *AL)
{
//
if (AL == NULL) {
NullPtrError("Size" );
return 0;
}
// Vector
return AL-> count;
}
5、Vectorの要素を取得します.
// ， ： void *(* GetElement)(const Vector *AL,size_t idx);
static void *GetElement( const Vector *AL,size_t idx)
{
char *p;
//
if (AL == NULL) {
NullPtrError("GetElement" );
return NULL ;
}
if (idx >=AL-> count ) {
return AL->RaiseError("iVector.GetElement" ,CONTAINER_ERROR_INDEX,AL,idx);
}
//
p = AL->contents;
//
p += idx*AL->ElementSize;
return p;
}
6,Vectorリソースを解放する:
// ， ： int (* Clear)(Vector *AL);
/*------------------------------------------------------------------------
Procedure: Clear ID:1
Purpose: Frees all memory from an array list object without
freeing the object itself
Input: The array list to be cleared
Output: The number of objects that were in the array list
Errors: The array list must be writable
------------------------------------------------------------------------*/
static int Clear(Vector *AL)
{
//
if (AL == NULL) {
return NullPtrError ("Clear");
}
// ， DestructorFn 。 ， destructorFunc()
if (AL->DestructorFn) {
size_t i;
unsigned char *p = (unsigned char *)AL->contents;
// Vector DestructorFn
for(i=0; icount ;i++) {
AL->DestructorFn(p);
p += AL->ElementSize;
}
}
AL-> count = 0;
AL->timestamp = 0;
AL->Flags = 0;
return 1;
}
// ， ： int (* Finalize)(Vector *AL);
/*------------------------------------------------------------------------
Procedure: Finalize ID:1
Purpose: Releases all memory associated with an Vector,
including the Vector structure itself
Input: The Vector to be destroyed
Output: The number of items that the Vector contained or
zero if error
Errors: Input must be writable
------------------------------------------------------------------------*/
static int Finalize(Vector *AL)
{
unsigned Flags;
int result;
//
if (AL == NULL)
return CONTAINER_ERROR_BADARG ;
//
result = Clear(AL);
if (result < 0)
return result;
// Vector
if (AL->VTable != &iVector)
AL->Allocator-> free(AL->VTable); // free stdlib.h free, ContainerAllocator 。
AL->Allocator-> free(AL->contents);
AL->Allocator-> free(AL);
return result;
}
四、まとめ
紙面の都合上、ここではこのVectorの基本的な機能、すなわちCreate、Add、Erase、Size、GetElement、Finalizeのみを紹介した.その他の機能としては、Appent RelaceAt Search IndexOf Sort Resizeなどがあります.ここでは紹介しません.なぜなら、このブログの目的はC言語を勉強し研究する友达のために玉を投げることだけです.私は学習の過程で以下のいくつかの方面の比較的重要な内容を総括して、みんなに参考を提供します.
1、C言語のプログラムを十分に理解して、メモリの中の分布.スタック、スタック、データエリアなど.
2、メモリの割り当てと解放.
3、ポインタとポインタ関数の活用.
4、構造体とポインタ関数を組み合わせて使用し、インタフェースオブジェクトを形成する.