Always Design for C Arrays — the copy subroutine

Wolfgang hasslemann — unsplash

Last time, Always Design for C arrays — from subarray to range and back, we introduced subarrays with the c array, we also showed how to map ranges to size.

A quick recap. A range [i, j) is a sequence of integers i, i+1, . . ., j-1 and has exactly j-i elements.

Copying subarrays

Given an array

const size_t n = 256;
int buf[n];

We can fill it with consecutive integers

fillIota(&buf[0], n, 0);

where fillIota is defined as

template <class T>
// requires T is integer type or real type
inline void
fillIota(T* f, int64_t n, const T& val) {
  int64_t i;
  for (i=0; i<n; ++i, ++val) f[i] = val;
}

What if we want to copy the values of a subarray | &buf[i], j-i | of range [i, j) to a subarray | &buf[k], l-k | of range [k, l) ?

Like,

size_t i = 2, j = 5, k = 7;
copy(&buf[i], j-i, &buf[k]);

Here we assume that the subarray starting at index k has enough space to contain j-i elements. Notice also that there is no need to specify the size of the subarray starting at &buf[k].

The copy subroutine can be defined as

template <class T>
inline void
copy (T* in, int64_t n, T* out) {
  int64_t i;
  for (i=0; i<n; ++i) out[i] = in[i];
}

There is no need returning the number of elements copied since this is already known by the value n from the caller of the subroutine.

Using copy to make room for Inserted element

What if we want our array to have more room in case we want to append or insert a new element at a specific location?

We bring in the concept of capacity.

Consider the array,

size_t cap = 256, len = 200;
int buf[cap];

Here, we differentiate the size from the capacity denoted by variables len and cap respectively.

We can fill in the array of size len with,

fillIota(&buf[0], len, 0);

What if we want to insert the value 400 at position 100 of the array? Well we can do that as shown below

insert(&buf[0], len, 100, 400);

where insert is defined as

template <class T>
inline void
insert(T* f, int64_t n, int64_t i, const T& val) {
  copy(f+i, n-i, f+i+1);
  f[i] = val;
}

Here we use pointer arithmetic as arguments to the copy subroutine.

Given a pointer p and an index i as shown below

int* p = &buf[0];
size_t i = 100;

The following two expressions

p + i

and

buf[i]

references the same element.

If we were to write the insert subroutine as a routine in the block where array buf is defined, we would have,

size_t i = 100;
int val = 400;
copy(&buf[i], len-i, &buf[i+1]);
buf[i] = val;