动态数组C语言实现

动态数组

 

本文实现了可以存储固定大小数据的动态数组.

动态数组就是在内存中分配连续的区域，存储固定大小的结构数组。并能根据插入或删除的值，自动调节大小。

类似std::vector。

但本文采用C语言实现。

 

/********************************************************************** * darray.h - Dynamic array for any type data * **********************************************************************/ #ifndef DARRAY_H_INCLUDED #define DARRAY_H_INCLUDED #ifdef __cplusplus extern "C" { #endif typedef unsigned int size_t; #define DARRAY_BLOCK_NUMS 128 typedef struct _darray_t *darray, *DARRAY; /* A prototype of callbacked function called by list_destroy(), NULL for no use. */ typedef void(*pfcb_darray_free_element)(void* element); /** create a darray and initialize it * darray arrPts; * darray_create(&arrPts, 128, sizeof(POINT)); * ... * darray_free(arrPts, 0, 0); */ void darray_create(darray *arr, size_t nums, size_t elementsize); /* count of elements */ size_t darray_count(darray arr); /* free a darray */ void darray_free(darray arr, pfcb_darray_free_element pfcbFreeElement, void *element); /* erase elems */ void darray_erase(darray arr, int index, size_t num, pfcb_darray_free_element pfcbFreeElement, void *element); /* clear all elems */ void darray_clear(darray arr, pfcb_darray_free_element pfcbFreeElement, void *element); /* append elem to the end of array */ void darray_push_back(darray arr, void *newelement); /* insert elem to the first of array */ void darray_push_first(darray arr, void *newelement); /* erase last element of array and return pointer to it */ size_t darray_pop_back(darray arr, void *back); /* erase first element of array and return pointer to it */ size_t darray_pop_first(darray arr, void *first); /* replace elem at pos and return the one replaced */ void array_replace_at(darray arr, int index, void *replace_by, void *element); /* get elem at index */ void darray_at(darray arr, int index, void *element); /* */ #ifdef __cplusplus } #endif #endif /* DARRAY_H_INCLUDED */  

 

/********************************************************************** * darray.c * **********************************************************************/ #include "darray.h" #include <assert.h> #include <memory.h> #include <malloc.h> typedef struct _darray_t { unsigned char *pbytes; size_t num_elems; size_t maxsize; /* max capacity of bytes */ size_t elemsize; /* size of element by bytes */ }darray_t; void darray_create(darray *arr, size_t nums, size_t elementsize) { darray_t *p = (darray_t*) malloc(sizeof(darray_t)); assert(p); p->num_elems = 0; p->elemsize = elementsize; p->maxsize = nums * elementsize; p->pbytes = malloc(p->maxsize); *arr = p; } size_t darray_count(darray arr) { return arr->num_elems; } void darray_free(darray arr, pfcb_darray_free_element pfcbFreeElement, void *element) { if (pfcbFreeElement) { size_t i; for (i=0; i<arr->num_elems; i++) { darray_at(arr, i, element); (*pfcbFreeElement) (element); } } free(arr->pbytes); free(arr); } void darray_clear(darray arr, pfcb_darray_free_element pfcbFreeElement, void *elem) { size_t i, nums; nums = arr->num_elems; arr->num_elems = 0; if (pfcbFreeElement) { for (i=0; i<nums; i++) { darray_at(arr, i, elem); (*pfcbFreeElement) (elem); } } } void darray_erase(darray arr, int index, size_t num, pfcb_darray_free_element pfcbFreeElement, void *elem) { size_t i; size_t num_elems = arr->num_elems; for (i=index+num; i<num_elems; i++) { if (pfcbFreeElement) { darray_at(arr, i, elem); (*pfcbFreeElement)(elem); } memcpy(arr->pbytes+(i-num)*arr->elemsize, arr->pbytes+i*arr->elemsize, arr->elemsize); } if (i>index+num) arr->num_elems -= num; if (arr->num_elems <= arr->maxsize/arr->elemsize-DARRAY_BLOCK_NUMS) { arr->maxsize -= DARRAY_BLOCK_NUMS*arr->elemsize; arr->pbytes = realloc(arr->pbytes, arr->maxsize); } } void darray_push_back(darray arr, void *newelement) { if (arr->maxsize < (arr->num_elems+1)*arr->elemsize) { arr->maxsize += (DARRAY_BLOCK_NUMS*arr->elemsize); arr->pbytes = realloc(arr->pbytes, arr->maxsize); assert(arr->pbytes); } memcpy(arr->pbytes+arr->num_elems*arr->elemsize, newelement, arr->elemsize); arr->num_elems++; } void darray_push_first(darray arr, void *newelement) { if (arr->maxsize < (arr->num_elems+1)*arr->elemsize) { arr->maxsize += (DARRAY_BLOCK_NUMS*arr->elemsize); arr->pbytes = realloc(arr->pbytes, arr->maxsize); assert(arr->pbytes); } memcpy(arr->pbytes+arr->elemsize, arr->pbytes, arr->elemsize*arr->num_elems); memcpy(arr->pbytes, newelement, arr->elemsize); arr->num_elems++; } size_t darray_pop_back(darray arr, void *back) { if (arr->num_elems > 0) { if (back) memcpy(back, (arr->pbytes+(arr->num_elems-1)*arr->elemsize), arr->elemsize); arr->num_elems--; if (arr->num_elems <= arr->maxsize/arr->elemsize-DARRAY_BLOCK_NUMS) { arr->maxsize -= DARRAY_BLOCK_NUMS*arr->elemsize; arr->pbytes = realloc(arr->pbytes, arr->maxsize); } } return arr->num_elems; } size_t darray_pop_first(darray arr, void *first) { if (arr->num_elems > 0) { size_t i; if (first) memcpy(first, arr->pbytes, arr->elemsize); for (i=1; i<arr->num_elems; i++) memcpy(arr->pbytes+(i-1)*arr->elemsize, arr->pbytes+i*arr->elemsize, arr->elemsize); arr->num_elems--; if (arr->num_elems <= arr->maxsize/arr->elemsize-DARRAY_BLOCK_NUMS) { arr->maxsize -= DARRAY_BLOCK_NUMS*arr->elemsize; arr->pbytes = realloc(arr->pbytes, arr->maxsize); } } return arr->num_elems; } void array_replace_at(darray arr, int index, void *replace_by, void *element) { assert(index >= 0 && index <(int)arr->num_elems); if (element) memcpy(element, arr->pbytes+index*arr->elemsize, arr->elemsize); memcpy(arr->pbytes+index*arr->elemsize, replace_by, arr->elemsize); } void darray_at(darray arr, int index, void *element) { assert(index >= 0 && index <(int)arr->num_elems); memcpy(element, arr->pbytes+index*arr->elemsize, arr->elemsize); }