Basically a reprint from http://nullprogram.com/blog/2016/10/07/

The following snippet shows how to write a simple vector, where all memory is allocated dynamically. Then, apply small-size optimization (embed the static memory in the struct for small sizes) to avoid dynamic memory allocation for small size data.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>
#include <errno.h>
#include <unistd.h>
#include <assert.h>
#include <stdbool.h>
#include <ctype.h>

typedef struct vec_simple {
  size_t size;
  size_t count;
  long *values;
} vec_simple;

bool vec_simple_init(vec_simple *v, size_t hint)
{
  assert(hint && (hint & (hint-1)) == 0);
  v->size = hint;
  v->count = 0;
  v->values = malloc(sizeof(v->values[0]) * v->size);
  return !!v->values;
}

bool vec_simple_push(vec_simple *v, long x)
{
  if (v->count == v->size) {
    size_t value_size = sizeof(v->values[0]);
    size_t new_size = v->size * 2;
    if (!new_size || value_size > SIZE_MAX/new_size) { return false; }
    void *new_values = realloc(v->values, new_size * value_size);
    if (!new_values) { return false; }
    v->size = new_size;
    v->values = new_values;
  }
  v->values[v->count++] = x;
  return true;
}

void vec_simple_free(vec_simple *v)
{
  free(v->values);
}

typedef struct vec_small {
  size_t size;
  size_t count;
  long *values;
  long tmp[16];
} vec_small;

void vec_small_init(vec_small *v, size_t _hint)
{
  v->size = sizeof(v->tmp)/sizeof(v->tmp[0]);
  v->count = 0;
  v->values = v->tmp;
}

bool vec_small_push(vec_small *v, long x)
{
  if (v->count == v->size) {
    size_t value_size = sizeof(v->values[0]);
    size_t new_size = v->size * 2;
    if (!new_size || value_size > SIZE_MAX/new_size) { return false; }
    void *new_values;
    if (v->values == v->tmp) {
      new_values = malloc(sizeof(value_size) * new_size);
      if (new_values) { memcpy(v->values, v->tmp, sizeof(v->tmp)); }
    } else {
      new_values = realloc(v->values, sizeof(value_size) * new_size);
    }
    if (!new_values) { return false; }
    v->size = new_size;
    v->values = new_values;
  }
  v->values[v->count++] = x;
  return true;
}

void vec_small_free(vec_small *v)
{
  if (v->values != v->tmp) { free(v->values); }
}

int main()
{
  return 0;
}