Data structure, Array

In this tutorial, we define array interfaces and try to implement them in C.

What is an Array

Array is a container holding multiple values of the same type, and can be read, written with random offset.

Generally, array should support constant time complexity in random access(read and write). An array that supports resize is a dynamic array, otherwise, it is a static size array.

In C++, array is implemented as std::vector. In Python, array is implemented as list. In C, you have to do it yourself.

Given any array type Array, it should support these methods:

void ArrayInit(Array* array, size_t size)

Initial the array conaining size elements.

A impelementation might requires more information in the ArrayInit, such as the type information to manage the resource holded by elements.
void ArrayRelease(Array* array)

Release the array. After this, the array content is invalid. But a implementation might leave the array as initialized with zero.
size_t ArraySize(const Array* array)

Returns the number of elements stored in array.
void ArrayResize(const Array* array, size_t new_size)

Truncates or extends array. It is a fatal error if this failed. Implementation can change the interface to return boolean result.
void* ArrayGet(Array* array, size_t i)

Returns the adress of element at offset i.

An offset should be less than the array size. It is a runtime error if an offset is larger than ArraySize(array). Checking this or not, is a implementation behavior. It is usually good to add this check in debug mode for test, and disable the check in release mode for performance, see assert function.

A non general array type can have type information in these methods. For example, an array of double can be defined by these accessing methods:

void DoubleArrayInit(DoubleArray* array, size_t size)
void DoubleArrayRelease(DoubleArray* array)
size_t DoubleArraySize(const DoubleArray* array)
void DoubleArrayResize(DoubleArray* array, size_t new_size)
double DoubleArrayGet(DoubleArray* array, size_t i)
void DoubleArraySet(DoubleArray* array, size_t i, double v)

Compare this list with the general array, we have simpler and type safe read and write methods. Since it can only be used for double, the implementation can be much simple, and has best performance. In C, a common approach to achieve type safe and best runtime performance, without code duplication for every type, is using preprocessor macro.

Based on these primitive methods, it is quite easy and straight to support more methods, like append an element, insert an element, erase an element, append an array, insert an array, erase an slice.

Array in C

Let us start from the simpler version, a static plain type array.

Single plain type Array

Following C++, We call a type is a plain type, if we do not need to construct and destruct it, the data can be copied from one to another value by memory.

In C, we need to manage all memory manually. In the implementation of DoubleArray, we need to call DoubleArrayInit to initialize an array, and DoubleArrayRelease to release memory allocated intenrally by the array.

File double_array.h

#ifndef FILE_236B6066_3B25_4C9D_A3B2_D2AA3F7827CA_H
#define FILE_236B6066_3B25_4C9D_A3B2_D2AA3F7827CA_H

#include <stddef.h>
#include <stdlib.h>
#include <assert.h>

typedef struct DoubleArray {
  double* data_;
  size_t size_;
  size_t allocated_;
} DoubleArray;

static inline void DoubleArrayResize(DoubleArray* array, size_t new_size);

static inline void DoubleArrayInit(DoubleArray* array, size_t size) {
  memset(array, 0, sizeof(*array));
  if (size > 0) {
    DoubleArrayResize(array, size);
  }
}

static inline void DoubleArrayRelease(DoubleArray* array) {
  free(array->data_);
  memset(array, 0, sizeof(*array));
}

static inline size_t DoubleArraySize(const DoubleArray* array) {
  return array->size_;
}

static inline void DoubleArrayResize(DoubleArray* array, size_t new_size) {
  if (new_size <= array->allocated_) {
    array->size_ = new_size;
    return;
  }
  size_t allocation = new_size;
  if (allocation < array->size_ * 2) {
    allocation = array->size_ * 2;
  }
  void* p = realloc(array->data_, allocation * sizeof(double));
  assert(p);
  array->data_ = (double*)p;
  array->size_ = new_size;
  array->allocated_ = allocation;
}

static inline double DoubleArrayGet(DoubleArray* array, size_t i) {
  assert(i < DoubleArraySize(array));
  return array->data_[i];
}

static inline void DoubleArraySet(DoubleArray* array, size_t i, double v) {
  assert(i < DoubleArraySize(array));
  array->data_[i] = v;
}

#endif  // FILE_236B6066_3B25_4C9D_A3B2_D2AA3F7827CA_H

General type Array

To implement a general type Array, we need to abstract some common routines to manage data of a dynamic type. We need pass these routines in the ArrayInit, and in ArrayRelease, we also need to release resources allocated by array elements. The initialization and release might also happen in array management, like resize, append, erase.

We abstract a general type management routines as struct TypeInfo, and believe this can be allocated statistically(or in stack), so a const pointer of TypeInfo can be passed to ArrayInit without life time problem.

File array.h

#ifndef FILE_77037415_78E5_414C_9AB9_A332A85C2B3B_H
#define FILE_77037415_78E5_414C_9AB9_A332A85C2B3B_H

#include <string.h>
#include <stddef.h>
#include <stdlib.h>
#include <assert.h>

typedef struct TypeInfo {
  // Common opaque data passed to all methods.
  void* data_;

  // Compile time size of this type.
  size_t size_;

  void (*init_)(void* data, void* p);

  void (*release_)(void* data, void* p);

  // Assume dest is already initialized. After this, resource managed by src is
  // moved to dest.
  void (*move_)(void* data, void* dest, void* src);

  // Assume dest is already initialized.
  void (*copy_)(void* data, void* dest, const void* src);
} TypeInfo;

// Initializes the TypeInfo for a plain type.
void TypeInfoInitPlain(TypeInfo* info, size_t size);

typedef struct Array {
  void* data_;
  size_t size_;
  size_t allocated_;
  const TypeInfo* element_info_;
} Array;

void TypeInfoInitArray(TypeInfo* info, const TypeInfo* element_info);

void ArrayInit(Array* array, size_t size, const TypeInfo* element_info);

void ArrayRelease(Array* array);

// Returns the size of the array, i.e. the number of elements in the array.
size_t ArraySize(const Array* array);

// Resize the array.
void ArrayResize(Array* array, size_t new_size);

// Returns the pointer of element at array with offset i.
void* ArrayGet(const Array* array, size_t i);

// Erase a sub range from array.
void ArrayErase(Array* array, size_t offset, size_t len);

// Insert a sub range with initialized values into array.
void ArrayInsertInitValues(Array* array, size_t offset, size_t len);

// Inserts a buffer into array. src should not be conatined by array.
void ArrayInsertBuffer(Array* array, size_t offset, const void* src,
                       size_t len);

// Inserts a buffer with values moved into array.
void ArrayMoveBuffer(Array* array, size_t offset, void* src, size_t len);

// Replace dest[dest_offset:dest_len] with src[0:src_len].
void ArraySpliceBuffer(Array* dest, size_t dest_offset, size_t dest_len,
                       const void* src, size_t src_len);

// Replace dest[dest_offset:dest_len] with src[0:src_len].
void ArraySpliceMoveBuffer(Array* dest, size_t dest_offset, size_t dest_len,
                           void* src, size_t src_len);

// Remove dest[dest_offset...], and copy src[src_offset...] into
// dest[dest_offset ...]
void ArraySplice(Array* dest, size_t dest_offset, size_t dest_len,
                 const Array* src, size_t src_offset, size_t src_len);

// Remove dest[dest_offset...], and move src[src_offset...] into
// dest[dest_offset ...]
void ArraySpliceMove(Array* dest, size_t dest_offset, size_t dest_len,
                     Array* src, size_t src_offset, size_t src_len);

// Remove dest[dest_offset...], and move src[src_offset...] into
// dest[dest_offset ...], and then erase src[src_offset...].
void ArraySpliceCut(Array* dest, size_t dest_offset, size_t dest_len,
                    Array* src, size_t src_offset, size_t src_len);

// Appends one value into the end of array.
void ArrayAppend(Array* array, void* value);

// Removes last value from array.
void ArrayPop(Array* array);

#endif  // FILE_77037415_78E5_414C_9AB9_A332A85C2B3B_H

File array_test.c

#include "array.h"

#include "double_array.h"

#include <stdio.h>

int test_failed = 0;

#define EXPECT(cond, format, ...)                                \
  if (!(cond)) {                                                 \
    fprintf(stderr,                                              \
            "%s %s:%d "                                          \
            "check '%s' failed:\n" format "\n",                  \
            __func__, __FILE__, __LINE__, #cond, ##__VA_ARGS__); \
    test_failed++;                                               \
  }

#define ASSERT(cond, format, ...)        \
  {                                      \
    int old_test_failed = test_failed;   \
    EXPECT(cond, format, ##__VA_ARGS__); \
    if (test_failed > old_test_failed) { \
      return;                            \
    }                                    \
  }

#define RUN_TEST(test)                         \
  fprintf(stderr, "==Testing %s ...\n", #test);   \
  test_failed = 0;                             \
  test();                                      \
  if (test_failed) {                           \
    fprintf(stderr, "==Failed %s\n\n", #test); \
  } else {                                     \
    fprintf(stderr, "==Passed %s\n\n", #test); \
  }

void TestArrayOfDouble() {
  Array a[1];
  TypeInfo double_info[1];
  TypeInfoInitPlain(double_info, sizeof(double));
  ArrayInit(a, 1, double_info);
  ASSERT(ArraySize(a) == 1, "array size(%zd) is not 1", ArraySize(a));
  ArrayResize(a, 10);
  ASSERT(ArraySize(a) == 10, "array size(%zd) is not 10", ArraySize(a));
  double sum_check = 0;
  for (size_t i = 0; i < 10; ++i) {
    double v = 1.0 / (i + 1);
    sum_check += v;
    double* p = ArrayGet(a, i);
    ASSERT(*p == 0, "init does not set zero, value %lf", *p);
    *(double*)ArrayGet(a, i) = v;
  }
  double s = 0;
  for (size_t i = 0; i < ArraySize(a); ++i) {
    double* p = ArrayGet(a, i);
    ASSERT(*p == 1.0 / (i + 1), "read got %lf does not match last set %lf", *p,
           1.0 / (i + 1));
    s += *(double*)ArrayGet(a, i);
  }
  ASSERT(s == sum_check, "sum(%lf) does not match(%lf)", s, sum_check);

  ArrayRelease(a);
}

void TestArrayOfArray() {
  Array a[1];
  TypeInfo double_info[1];
  TypeInfo array_info[1];
  TypeInfoInitPlain(double_info, sizeof(double));
  TypeInfoInitArray(array_info, double_info);

  size_t m = 40;
  ArrayInit(a, m - 1, array_info);
  ASSERT(ArraySize(a) == m - 1, "array size(%zd) is not %zd", ArraySize(a),
         m - 1);
  ArrayResize(a, m);
  ASSERT(ArraySize(a) == m, "array size(%zd) is not %zd", ArraySize(a), m);

  double sum_check = 0;
  for (size_t i = 0; i < m; ++i) {
    Array* row = (Array*)ArrayGet(a, i);
    ASSERT(ArraySize(row) == 0, "array size(%zd) is not 0", ArraySize(a));
    ArrayResize(row, i + 1);
    for (size_t j = 0; j <= i; ++j) {
      *(double*)ArrayGet(row, j) = 1.0 / (i + j + 1);
      sum_check += 1.0 / (i + j + 1);
    }
  }

  double s = 0;
  for (size_t i = 0; i < ArraySize(a); ++i) {
    Array* row = (Array*)ArrayGet(a, i);
    for (size_t j = 0; j < ArraySize(row); ++j) {
      s += *(double*)ArrayGet(row, j);
    }
  }
  ASSERT(s == sum_check, "sum(%lf) miss match %lf", s, sum_check);

  ArrayRelease(a);
}

void DoubleArray_init(void* data, void* p) {
  DoubleArrayInit((DoubleArray*)p, 0);
}

void DoubleArray_release(void* data, void* p) {
  DoubleArrayRelease((DoubleArray*)p);
}

void DoubleArray_move(void* data, void* dest, void* src) {
  DoubleArray* d = (DoubleArray*)dest;
  DoubleArray* s = (DoubleArray*)src;
  DoubleArrayRelease(d);
  memmove(d, s, sizeof(DoubleArray));
  DoubleArrayInit(s, 0);
}

void DoubleArray_copy(void* data, void* dest, const void* src) {
  DoubleArray* d = (DoubleArray*)dest;
  DoubleArray* s = (DoubleArray*)src;
  DoubleArrayRelease(d);
  DoubleArrayInit(d, DoubleArraySize(s));
  for (size_t i = 0,n = DoubleArraySize(d); i < n; ++i) {
    DoubleArraySet(d, i, DoubleArrayGet(s, i));
  }
}

void TypeInfoInitDoubleArray(TypeInfo* info) {
  TypeInfoInitPlain(info, sizeof(DoubleArray));
  info->init_ = DoubleArray_init;
  info->release_ = DoubleArray_release;
  info->move_ = DoubleArray_move;
  info->copy_ = DoubleArray_copy;
}

void TestArrayOfDoubleArray() {
  Array a[1];
  TypeInfo double_array_info[1];
  TypeInfoInitDoubleArray(double_array_info);

  size_t m = 40;
  ArrayInit(a, m - 1, double_array_info);
  ASSERT(ArraySize(a) == m - 1, "array size(%zd) is not %zd", ArraySize(a),
         m - 1);
  ArrayResize(a, m);
  ASSERT(ArraySize(a) == m, "array size(%zd) is not %zd", ArraySize(a), m);

  double sum_check = 0;
  for (size_t i = 0; i < m; ++i) {
    DoubleArray* row = (DoubleArray*)ArrayGet(a, i);
    ASSERT(DoubleArraySize(row) == 0, "array size(%zd) is not 0", ArraySize(a));
    DoubleArrayResize(row, i + 1);
    for (size_t j = 0; j <= i; ++j) {
      DoubleArraySet(row, j, 1.0 / (i + j + 1));
      sum_check += 1.0 / (i + j + 1);
    }
  }

  double s = 0;
  for (size_t i = 0; i < ArraySize(a); ++i) {
    DoubleArray* row = (DoubleArray*)ArrayGet(a, i);
    for (size_t j = 0; j < DoubleArraySize(row); ++j) {
      s += DoubleArrayGet(row, j);
    }
  }
  ASSERT(s == sum_check, "sum(%lf) miss match %lf", s, sum_check);

  ArrayRelease(a);
}

static int ExpectArrayDoubleEq(Array* a, const double* buf, size_t len) {
  int old_test_failed = test_failed;
  EXPECT(a->element_info_->size_ == sizeof(double),
         "The array has elment size %zd, not equal to double %zd",
         a->element_info_->size_, sizeof(double));
  EXPECT(ArraySize(a) == len, "array size %zd is not %zd", ArraySize(a), len);
  for (size_t i = 0, n = ArraySize(a); i < n && i < len; ++i) {
    EXPECT(*(double*)ArrayGet(a, i) == buf[i],
           "The value %lf at %zd is not %lf", *(double*)ArrayGet(a, i), i,
           buf[i]);
  }
  return old_test_failed == test_failed;
}

void TestArraySplice() {
  Array a[1], b[1];
  TypeInfo double_info[1];
  TypeInfoInitPlain(double_info, sizeof(double));
  ArrayInit(a, 0, double_info);
  ArrayInit(b, 0, double_info);
  ArraySplice(a, 0, 0, b, 0, 0);
  ASSERT(ArraySize(a) == 0, "a.size=%zd", ArraySize(a));
  ArrayInsertBuffer(a, 0, (double[]){1.1, 2.2, 3.3, 4.4}, 4);
  ArrayInsertBuffer(a, 4, (double[]){5.5, 6.6, 7.7}, 3);
  ASSERT(
      ExpectArrayDoubleEq(a, (double[]){1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7}, 7),
      "");
  ArraySplice(a, 0, 0, b, 0, 0);
  ASSERT(
      ExpectArrayDoubleEq(a, (double[]){1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7}, 7),
      "");
  ArraySplice(a, 1, 0, b, 0, 0);
  ASSERT(
      ExpectArrayDoubleEq(a, (double[]){1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7}, 7),
      "");
  ArraySplice(a, 1, 2, b, 0, 0);
  ASSERT(ExpectArrayDoubleEq(a, (double[]){1.1, 4.4, 5.5, 6.6, 7.7}, 5), "");

  ArrayInsertBuffer(b, 0, (double[]){1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7}, 7);

  ArraySplice(a, 1, 0, b, 1, 2);
  ASSERT(
      ExpectArrayDoubleEq(a, (double[]){1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7}, 7),
      "");

  ArraySplice(a, 1, 2, b, 4, 3);
  ASSERT(ExpectArrayDoubleEq(
             a, (double[]){1.1, 5.5, 6.6, 7.7, 4.4, 5.5, 6.6, 7.7}, 8),
         "");

  ArrayErase(a, 2, 6);
  ArrayAppend(a, (double[]){2.8});
  ASSERT(ExpectArrayDoubleEq(a, (double[]){1.1, 5.5, 2.8}, 3), "");

  ArrayPop(a);
  ASSERT(ExpectArrayDoubleEq(a, (double[]){1.1, 5.5}, 2), "");

  ArrayRelease(a);
  ArrayRelease(b);
}

int main(int argc, char* argv[]) {
  RUN_TEST(TestArrayOfDouble);

  RUN_TEST(TestArrayOfArray);

  RUN_TEST(TestArrayOfDoubleArray);

  RUN_TEST(TestArraySplice);

  return 0;
}

File array.c

Before reading this file, you are encouraged to implement yourself version, to make array_test pass, see Problems sections.

#include "array.h"

#include <stdint.h>

static void Plain_copy(void* data, void* dest, const void* src) {
  memcpy(dest, src, (intptr_t)data);
}

static void Plain_move(void* data, void* dest, void* src) {
  memmove(dest, src, (intptr_t)data);
}

static void Plain_init(void* data, void* p) { memset(p, 0, (intptr_t)data); }

static void Plain_release(void* data, void* p) { memset(p, 0, (intptr_t)data); }

void TypeInfoInitPlain(TypeInfo* info, size_t size) {
  memset(info, 0, sizeof(TypeInfo));
  info->data_ = (void*)(intptr_t)size;
  info->size_ = size;
  info->init_ = Plain_init;
  info->release_ = Plain_release;
  info->copy_ = Plain_copy;
  info->move_ = Plain_move;
}

// A help routine.
static inline void* Offset(const void* data, size_t n) {
  return &((char*)data)[n];
}

static void Array_init(void* data, void* p) {
  ArrayInit(p, 0, (TypeInfo*)data);
}

static void Array_release(void* data, void* p) {
  assert(data == ((Array*)p)->element_info_);
  ArrayRelease(p);
}

static void Array_move(void* data, void* dest, void* src) {
  Array* d = (Array*)dest;
  Array* s = (Array*)src;
  assert(d != s);
  assert(data == ((Array*)d)->element_info_);
  assert(data == ((Array*)s)->element_info_);
  // Swap *d and *s.
  Array t = *d;
  *d = *s;
  *s = t;
}

static void Array_copy(void* data, void* dest, const void* src) {
  Array* d = (Array*)dest;
  Array* s = (Array*)src;
  assert(d != s);
  assert(data == ((Array*)d)->element_info_);
  assert(data == ((Array*)s)->element_info_);
  ArraySplice(d, 0, ArraySize(d), s, 0, ArraySize(s));
}

void TypeInfoInitArray(TypeInfo* info, const TypeInfo* element_info) {
  TypeInfoInitPlain(info, sizeof(Array));
  info->data_ = (void*)element_info;
  info->init_ = Array_init;
  info->release_ = Array_release;
  info->copy_ = Array_copy;
  info->move_ = Array_move;
}

void ArrayInit(Array* array, size_t size, const TypeInfo* element_info) {
  memset(array, 0, sizeof(Array));
  array->element_info_ = element_info;
  if (size > 0) {
    ArrayResize(array, size);
  }
}

void ArrayRelease(Array* array) {
  // Resize to 0 to release elements.
  ArrayResize(array, 0);
  free(array->data_);
  // Leave an empty valid array.
  ArrayInit(array, 0, array->element_info_);
}

size_t ArraySize(const Array* array) { return array->size_; }

void ArrayResize(Array* array, size_t new_size) {
  const TypeInfo* info = array->element_info_;
  if (new_size <= array->allocated_) {
    size_t old_size = array->size_;
    for (size_t i = new_size; i < old_size; ++i) {
      info->release_(info->data_, Offset(array->data_, i * info->size_));
    }
    for (size_t i = old_size; i < new_size; ++i) {
      info->init_(info->data_, Offset(array->data_, i * info->size_));
    }
    array->size_ = new_size;
    return;
  }
  size_t allocation = new_size;
  if (allocation < array->size_ * 2) {
    allocation = array->size_ * 2;
  }
  void* p = malloc(allocation * info->size_);
  assert(p);
  for (size_t i = 0; i < new_size; ++i) {
    info->init_(info->data_, Offset(p, i * info->size_));
  }
  size_t common_size = new_size < array->size_ ? new_size : array->size_;
  for (size_t i = 0; i < common_size; ++i) {
    info->move_(info->data_, Offset(p, i * info->size_),
                Offset(array->data_, i * info->size_));
  }
  for (size_t i = 0; i < array->size_; ++i) {
    info->release_(info->data_, Offset(array->data_, i * info->size_));
  }
  free(array->data_);
  array->data_ = p;
  array->size_ = new_size;
  array->allocated_ = allocation;
}

void* ArrayGet(const Array* array, size_t i) {
  assert(i < ArraySize(array));
  return Offset(array->data_, i * array->element_info_->size_);
}

void ArrayErase(Array* array, size_t offset, size_t len) {
  assert(offset + len <= ArraySize(array));
  if (!len) {
    return;
  }
  const TypeInfo* info = array->element_info_;
  size_t old_size = ArraySize(array);
  for (size_t i = offset + len; i < old_size; ++i) {
    info->move_(info->data_, Offset(array->data_, (i - len) * info->size_),
                Offset(array->data_, i * info->size_));
  }
  ArrayResize(array, old_size - len);
}

void ArrayInsertInitValues(Array* array, size_t offset, size_t len) {
  assert(offset <= ArraySize(array));
  if (!len) {
    return;
  }
  const TypeInfo* info = array->element_info_;
  size_t old_size = ArraySize(array);
  ArrayResize(array, old_size + len);
  for (size_t i = old_size; i-- > offset;) {
    info->move_(info->data_, Offset(array->data_, (i + len) * info->size_),
                Offset(array->data_, i * info->size_));
  }
}

void ArrayInsertBuffer(Array* array, size_t offset, const void* src,
                       size_t len) {
  assert(offset <= ArraySize(array));
  if (!len) {
    return;
  }
  const TypeInfo* info = array->element_info_;
  ArrayInsertInitValues(array, offset, len);
  for (size_t i = 0; i < len; ++i) {
    info->copy_(info->data_, Offset(array->data_, (i + offset) * info->size_),
                Offset(src, i * info->size_));
  }
}

void ArrayMoveBuffer(Array* array, size_t offset, void* src, size_t len) {
  assert(offset <= ArraySize(array));
  if (!len) {
    return;
  }
  const TypeInfo* info = array->element_info_;
  ArrayInsertInitValues(array, offset, len);
  for (size_t i = 0; i < len; ++i) {
    info->move_(info->data_, Offset(array->data_, (i + offset) * info->size_),
                Offset(src, i * info->size_));
  }
}

void ArraySpliceBuffer(Array* dest, size_t dest_offset, size_t dest_len,
                       const void* src, size_t src_len) {
  assert(dest_offset + dest_len <= ArraySize(dest));
  const TypeInfo* info = dest->element_info_;
  size_t old_size = ArraySize(dest);
  size_t common_len = dest_len < src_len ? dest_len : src_len;
  for (size_t i = 0; i < common_len; ++i) {
    info->copy_(info->data_,
                Offset(dest->data_, (i + dest_offset) * info->size_),
                Offset(src, i * info->size_));
  }
  if (src_len < dest_len) {
    ArrayErase(dest, dest_offset + src_len, dest_len - src_len);
  } else if (src_len > dest_len) {
    ArrayInsertBuffer(dest, dest_offset + dest_len,
                      Offset(src, dest_len * info->size_), src_len - dest_len);
  }
  assert(ArraySize(dest) == old_size + src_len - dest_len);
}

void ArraySpliceMoveBuffer(Array* dest, size_t dest_offset, size_t dest_len,
                           void* src, size_t src_len) {
  assert(dest_offset + dest_len <= ArraySize(dest));
  const TypeInfo* info = dest->element_info_;
  size_t old_size = ArraySize(dest);
  size_t common_len = dest_len < src_len ? dest_len : src_len;
  for (size_t i = 0; i < common_len; ++i) {
    info->move_(info->data_,
                Offset(dest->data_, (i + dest_offset) * info->size_),
                Offset(src, i * info->size_));
  }
  if (src_len < dest_len) {
    ArrayErase(dest, dest_offset + src_len, dest_len - src_len);
  } else if (src_len > dest_len) {
    ArrayMoveBuffer(dest, dest_offset + dest_len,
                    Offset(src, dest_len * info->size_), src_len - dest_len);
  }
  assert(ArraySize(dest) == old_size + src_len - dest_len);
}

void ArraySplice(Array* dest, size_t dest_offset, size_t dest_len,
                 const Array* src, size_t src_offset, size_t src_len) {
  assert(dest_offset + dest_len <= ArraySize(dest));
  assert(dest->element_info_ == src->element_info_);
  assert(src_offset + src_len <= ArraySize(src));
  assert(dest->element_info_ == src->element_info_);
  ArraySpliceBuffer(dest, dest_offset, dest_len,
                    src_len ? ArrayGet(src, src_offset) : NULL, src_len);
}

void ArraySpliceMove(Array* dest, size_t dest_offset, size_t dest_len,
                     Array* src, size_t src_offset, size_t src_len) {
  assert(dest_offset + dest_len <= ArraySize(dest));
  assert(dest->element_info_ == src->element_info_);
  assert(src_offset + src_len <= ArraySize(src));
  assert(dest->element_info_ == src->element_info_);
  ArraySpliceMoveBuffer(dest, dest_offset, dest_len,
                        src_len ? ArrayGet(src, src_offset) : NULL, src_len);
}

void ArraySpliceCut(Array* dest, size_t dest_offset, size_t dest_len,
                    Array* src, size_t src_offset, size_t src_len) {
  ArraySpliceMove(dest, dest_offset, dest_len, src, src_offset, src_len);
  ArrayErase(src, src_offset, src_len);
}

void ArrayAppend(Array* a, void* value) {
  ArrayInsertBuffer(a, ArraySize(a), value, 1);
}

void ArrayPop(Array* array) {
  assert(ArraySize(array) > 0);
  ArrayResize(array, ArraySize(array) - 1);
}

Compile and test

Assume we copy the relative code to file double_array.h, array.h, array.c and array_test.c respectively, this code can be compiled and tested as:

# clang can be replacce by gcc, or cc
clang -std=c11 -Wall -O0 -g array_test.cc array.c -o array_test
./arary_test
# If valgrind is installed.
valgrind ./array_test

If you implement yourself version array.c in another file array_ya.c, then it can be tested as:

clang -std=c11 -Wall -O0 -g array_test.cc array_ya.c -o array_ya_test
./arary_ya_test
# If valgrind is installed.
valgrind ./array_ya_test

Problems

Problem This code is not tested, please write some code to test this implementation.

Problem Implement double Sum(DoubleArray*array), returns the summation of all values in the array.

Problem Implement size_t ArgMax(DoubleArray*array), which returns the index of max value in the array, and returns zero for empty array.

Problem Implement void DoubleArrayAppend(DoubleArray* array, double v) based on the other access methods in above, without touching DoubleArray fields.

Problem Since the DoubleArray's implementation is quite simple, we can copy code and rename the type for IntArray, Int64Array. Try to define a macro PLAIN_ARRAY(name, type), which generate array code automatically. For example, PLAIN_ARRAY(DoubleArray, double) can generate the code for DoubleArray, PLAIN_ARRAY(IVec, int) generate code for int array, with all methods prefixed by IVec.

Problem Re-implement all Array methods.

Problem Implement a function to swap two non interleaved ranges of array:

void ArraySwapRanges(Array* array, size_t first_offset, size_t first_len, size_t second_offset, size_t second_len)

For example, for arary [1, 2, 3, 4, 5, 6, 7, 8], calling ArraySwapRanges(array, 1, 2, 4, 3) will modifiy the array into [1, 5, 6, 7, 4, 2, 3, 8].

Tutorial, Array