动态数组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);
}