Wu Yudong's Blog

本文针对一个开源的使用C实现的一个类型安全的动态数组，进行源代码分析，进一步学习提升C语言

项目源代码在这里，代码只包含两个文件：vec.h和vec.c，下面来剖析一下里面的代码

本文地址：http://wuyudong.com/2016/11/16/3026.html，转载请注明出处。

vec.h 代码：

常规的C数组，只包含数组的首地址，长度在初始化的时候已经定了，后面不能再更改，这里要实现动态数组，必须在原来的基础上添加几个字段，数组长度(length)和数组容量(capacity)，而且数组的类型不定，设计成泛型，综合以上几点，这里使用宏实现，代码如下：

#define vec_t(T)\
  struct { T *data; int length, capacity; }

初始化数组，使用memset函数：

#define vec_init(v)\
  memset((v), 0, sizeof(*(v)))

销毁数组，释放资源：

#define vec_deinit(v)\
  ( free((v)->data),\
    vec_init(v) )

数组拆包：

#define vec_unpack_(v)\
  (char**)&(v)->data, &(v)->length, &(v)->capacity, sizeof(*(v)->data)

获取数组顶部（最后一个）元素，有点类似栈：

#define vec_pop(v)\
  (v)->data[--(v)->length]

将vec_splice_进行封装，减少参数个数：

#define vec_splice(v, start, count)\
  ( vec_splice_(vec_unpack_(v), start, count),\
    (v)->length -= (count) )

将vec_swapsplice_进行封装，减少参数个数：

#define vec_swapsplice(v, start, count)\
  ( vec_swapsplice_(vec_unpack_(v), start, count),\
    (v)->length -= (count) )

插入一个元素到数组，失败返回-1，成功返回0：

#define vec_push(v, val)\
  ( vec_expand_(vec_unpack_(v)) ? -1 :\
    ((v)->data[(v)->length++] = (val), 0), 0 )

将vec_insert_进行封装，减少参数个数：

#define vec_insert(v, idx, val)\
  ( vec_insert_(vec_unpack_(v), idx) ? -1 :\
    ((v)->data[idx] = (val), 0), (v)->length++, 0 )

清除数组元素：

#define vec_clear(v)\
  ((v)->length = 0)

缩短数组长度：

#define vec_truncate(v, len)\
  ((v)->length = (len) < (v)->length ? (len) : (v)->length)

获取数组第一个元素：

#define vec_first(v)\
  (v)->data[0]

获取数组最后一个元素：

#define vec_last(v)\
  (v)->data[(v)->length - 1]

将vec_reserve_进行封装，通过宏vec_unpack_减少参数个数：

#define vec_reserve(v, n)\
  vec_reserve_(vec_unpack_(v), n)

将vec_compact_进行封装，通过宏vec_unpack_减少参数个数：

#define vec_compact(v)\
  vec_compact_(vec_unpack_(v))

将arr数组的count个元素依次插入到数组v的末端：

#define vec_pusharr(v, arr, count)\
  do {\
    int i__, n__ = (count);\
    if (vec_reserve_po2_(vec_unpack_(v), (v)->length + n__) != 0) break;\
    for (i__ = 0; i__ < n__; i__++) {\
      (v)->data[(v)->length++] = (arr)[i__];\
    }\
  } while (0)

注意：i__的作用是防止在程序中出现局部变量i产生冲突

调用宏实现将数组v2依次插入数组v末端：

#define vec_extend(v, v2)\
  vec_pusharr((v), (v2)->data, (v2)->length)

查找一个元素是否在数组中：

#define vec_find(v, val, idx)\
  do {\
    for ((idx) = 0; (idx) < (v)->length; (idx)++) {\
      if ((v)->data[(idx)] == (val)) break;\
    }\
    if ((idx) == (v)->length) (idx) = -1;\
  } while (0)

删除数组中的一个元素：

#define vec_remove(v, val)\
  do {\
    int idx__;\
    vec_find(v, val, idx__);\
    if (idx__ != -1) vec_splice(v, idx__, 1);\
  } while (0)

给数组元素排序，fn为函数指针，表明升降序：

#define vec_sort(v, fn)\
  qsort((v)->data, (v)->length, sizeof(*(v)->data), fn)

将vec_swap_进行封装，减少参数个数：

#define vec_swap(v, idx1, idx2)\
  vec_swap_(vec_unpack_(v), idx1, idx2)

将数组元素位置反转：

#define vec_reverse(v)\
  do {\
    int i__ = (v)->length / 2;\
    while (i__--) {\
      vec_swap((v), i__, (v)->length - (i__ + 1));\
    }\
  } while (0)

正向遍历数组元素：

#define vec_foreach(v, var, iter)\
  if  ( (v)->length > 0 )\
  for ( (iter) = 0;\
        (iter) < (v)->length && (((var) = (v)->data[(iter)]), 1);\
        ++(iter))

注意：(iter) >= 0 && (((var) = (v)->data[(iter)]), 1); 最后的1，表示当var是NULL的时候，还能继续执行for循环

逆向遍历数组元素：

#define vec_foreach_rev(v, var, iter)\
  if  ( (v)->length > 0 )\
  for ( (iter) = (v)->length - 1;\
        (iter) >= 0 && (((var) = (v)->data[(iter)]), 1);\
        --(iter))

正向遍历指向数组元素的指针：

#define vec_foreach_ptr(v, var, iter)\
  if  ( (v)->length > 0 )\
  for ( (iter) = 0;\
        (iter) < (v)->length && (((var) = &(v)->data[(iter)]), 1);\
        ++(iter))

逆向遍历指向数组元素的指针：

#define vec_foreach_ptr_rev(v, var, iter)\
  if  ( (v)->length > 0 )\
  for ( (iter) = (v)->length - 1;\
        (iter) >= 0 && (((var) = &(v)->data[(iter)]), 1);\
        --(iter))

vec.c 代码

1、容量扩充函数vec_expand_()：

int vec_expand_(char **data, int *length, int *capacity, int memsz) {
  if (*length + 1 > *capacity) { //当length==capacity,扩充容量
    void *ptr;
    int n = (*capacity == 0) ? 1 : *capacity << 1; 
    //当起始容量为0，分配一个单位，否则为原来的一倍

    ptr = realloc(*data, n * memsz); //memsz为元素大小
    if (ptr == NULL) return -1;
    *data = ptr;
    *capacity = n;
  }
  return 0;
}

2、数组容量预留函数vec_reserve_()：

int vec_reserve_(char **data, int *length, int *capacity, int memsz, int n) {
  (void) length;
  if (n > *capacity) {
    void *ptr = realloc(*data, n * memsz);
    if (ptr == NULL) return -1;
    *data = ptr;
    *capacity = n;
  }
  return 0;
}

3、数组容量预留函数vec_reserve_po2_()：

//数组预留空间不小于n的空间n2，且n2为2的幂
int vec_reserve_po2_(char **data, int *length, int *capacity, int memsz, int n) {
  int n2 = 1;
  if (n == 0) return 0;
  while (n2 < n) n2 <<= 1;
  return vec_reserve_(data, length, capacity, memsz, n2);
}

4、在数组的指定位置插入元素函数vec_insert_()：

int vec_insert_(char **data, int *length, int *capacity, int memsz, int idx) {
  int err = vec_expand_(data, length, capacity, memsz); 
  if (err) return err; 
  memmove(*data + (idx + 1) * memsz,
          *data + idx * memsz,
          (*length - idx) * memsz);
  return 0;
}

说明一下memmove函数，函数原型如下：

void *memmove(void *dst,  const void *src,  size_t count);

将src开始的count数量的内存块内容到dst开始的内存块，与memcpy函数的区别为当内存发生局部重叠的时候，memmove保证拷贝的结果是正确的。

由src所指内存区域复制count个字节到dest所指内存区域。src和dest所指内存区域可以重叠，但复制后dest内容会被更改。函数返回指向dest的指针。

memmove的处理措施：

（1）当源内存的首地址等于目标内存的首地址时，不进行任何拷贝

（2）当源内存的首地址大于目标内存的首地址时，实行正向拷贝

（3）当源内存的首地址小于目标内存的首地址时，实行反向拷贝

vec_insert_函数的原理是将数组的索引idx位置到数组最后元素之间的元素全部后移一个元素位，空出一个位来存放待插入的元素

5、元素覆盖函数vec_splice_()：

void vec_splice_(char **data, int *length, int *capacity, int memsz, int start, int count) {
  (void) capacity;
  memmove(*data + start * memsz,
          *data + (start + count) * memsz,
          (*length - start - count) * memsz);
}

将start位置处开始的count个元素由start+count开始的count个元素替换。

注意：(void) capacity; 这条语句对程序上来说是没有意义的，只是告诉编译器，这个变量我（假装）使用了，不要提示变量未使用的警告。（这个变量在程序中未使用的情况下）

6、交换数组指定位置的两个元素vec_swap_()：

void vec_swap_(char **data, int *length, int *capacity, int memsz, int idx1, int idx2) {
  unsigned char *a, *b, tmp;
  int count;
  (void) length;
  (void) capacity;
  if (idx1 == idx2) return;
  a = (unsigned char*) *data + idx1 * memsz;
  b = (unsigned char*) *data + idx2 * memsz;
  count = memsz;
  while (count--) {
    tmp = *a;
    *a = *b;
    *b = tmp;
    a++, b++;
  }
}

通过阅读理解源代码，学到不少关于C语言编程技巧