Implementing growing arrays for C

· 493 words · 3 minute read


A few weeks ago I posted the Implementing Result Types for C article. With the same purpose and reasoning I required a list type which grows depending on the size of the input. Because i like the way slices work and their implementation in the go programming language i decided to port a rudimentary version to C for my SeaScript programming language project.

The concept of slices is build around wrapping array access and therefore enabling bounds checking, dynamic resizing and better memory alignment than for example a linked list.

Lets take a look at a simple example of using go slices and compare it to my ported version:

 1package main
 3import "fmt"
 5func main() {
 6    s := make([]int)
 7    for i := 0; i < 100; i++ {
 8        s = append(s, i)
 9    }
10    for i := 0; i < 100; i++ {
11        fmt.Println(s[i])
12    }
 1#include <stdio.h>
 2#include <stdlib.h>
 4#include "slice.h"
 6int main(void) {
 7    CsSlice *s = CsSliceNew(0);
 8    for (int i = 0; i < 100; i++) {
 9        int *j = (int *)malloc(sizeof(int));
10        *j = i;
11        CsSliceAppend(s, j);
12    }
13    for (size_t i = 0; i < 100; i++) {
14        int *r = (int *)CsUnwrap(CsSliceGet(s, i));
15        printf("%d\n", *r);
16        free(r)
17    }
18    CsSliceFree(s)
19    return EXIT_SUCCESS;

The main difference between c and go here, is the required allocation for storing arbitrary data in the slice, which is needed because the only way i know of to include generic data in c structures is to use void *, which requires an allocation. We also deallocate the stored memory in line 16, because we free the whole slice in line 18.

Memory Ownership for both stored values and the slice itself is required of the library consumer, the slice however doubles in size if insertion requires bigger capacity than currently available.

The following is the header file for the slice package:

 1#ifndef SLICE_H
 2#define SLICE_H
 4#include "result.h"
 5#include <stddef.h>
 7typedef struct CsSlice {
 8  // list of elements
 9  void **elements;
10  // count of elements currenlty in list
11  size_t len;
12  // maxium size of Slice
13  size_t cap;
14} CsSlice;
16// creates and returns a new slice, if initial_size is less than
17// SLICE_MIN_SIZE, initial_size gets set to SLICE_MIN_SIZE.
18CsSlice *CsSliceNew(size_t initial_size);
20// inserts element at the given index, if s.len would be bigger than s.cap
21// after insertion, doubles the size of the underlying array
22void CsSliceAppend(CsSlice *s, void *element);
24// returns the given element if 0 <= index < s.len
25CsResult *CsSliceGet(CsSlice *s, int index);
27// returns pointer to the underlying array
28void **CsSliceGetArray(CsSlice *s);
30// frees the allocated memory region for the given Slice, sets the
31// pointer to point to NULL
32void CsSliceFree(CsSlice *s);


Interested in the implementation of this API? View the source code here.