The Melodist»Blog

Another std::vector equivalent in C (2/21/2017)

Hey everyone!

As a start to my journey in programming in a more handmade fashion, I decided to test my skills regarding memory management and C in general by attempting to code a C-equivalent of the C++ std::vector. I took inspiration from the stb_stretchy_buffer library.

It's not feature complete yet; just have pop/push, free, and size/cap functions. If you guys have any suggestions or comments, I'd love to hear them!

Here it is:

EDIT: Fixed some issues and implemented a few new features. Thanks for the comments, guys!
EDIT [2]: Threw in a license and uploaded to github

  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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#ifndef _DARRAY_H
#define _DARRAY_H

#include <stdlib.h>
#include <stdint.h>
#include <memory.h>

#define _DARRAY_START_CAP 32

#define da_shrink(a) if(da_size(a) > 0) { _da_shrink((void **)&a, sizeof(a[0])); }
#define da_push(a, e) _da_push((void **)&a, &e, sizeof(e))
#define da_insert(a, e, i) _da_insert((void **)&a, &e, sizeof(e), i)
#define da_pop(a) if(da_size(a)) { _da_pop((void **)&a, sizeof(a[0])); }
#define da_erase(a, i) if(da_size(a)) { _da_erase((void **)&a, sizeof(a[0]), i); }
#define da_free(a) _da_free((void **)&a)

inline uint32_t *_da_raw(void *array) {
    return (uint32_t *)array - 2;
}

inline uint32_t da_size(void *array) {
    if(array) {
        return _da_raw(array)[0];
    }
    return 0;
}

inline uint32_t da_cap(void *array) {
    if(array) {
        return _da_raw(array)[1];
    }
    return 0;
}

inline void _da_free(void **array) {
    if(*array) {
        *array = (void *)(_da_raw(*array));
    }
    free(*array);
    *array = NULL;
}

inline void _da_grow(void **array, size_t element_size) {
    uint32_t new_cap = _DARRAY_START_CAP, size = 0;
    bool need_realloc = true;
    if(*array) {
        size = da_size(*array);
        if(size >= da_cap(*array)) {
            new_cap = da_cap(*array) + (da_cap(*array) / 2);
        }
        else {
            new_cap = da_cap(*array);
            need_realloc = false;
        }
    }

    if(need_realloc) {
        if(*array) {
            *array = (void *)_da_raw(*array);
        }
        *array = realloc(*array, (new_cap * element_size) + (2 * sizeof(uint32_t)));
        *array = (void *)((uint32_t *)(*array) + 2);
        _da_raw(*array)[0] = size;
        _da_raw(*array)[1] = new_cap;
    }
}

inline void _da_shrink(void **array, size_t element_size) {
    if(*array) {
        if(da_size(*array) > 0) {
            if(da_size(*array) <= da_cap(*array) - (da_cap(*array) / 3)) {
                _da_raw(*array)[1] = da_cap(*array) - (da_cap(*array) / 3);

                *array = realloc(_da_raw(*array), (da_cap(*array) * element_size) + (2 * sizeof(uint32_t)));
                *array = (uint32_t *)(*array) + 2;
            }
        }
        else {
            _da_free(array);
        }
    }
}

inline void _da_push(void **array, void *element, size_t element_size) {
    _da_grow(array, element_size);

    memcpy(((uint8_t *)(*array)) + (element_size * da_size(*array)),
           element, element_size);
    _da_raw(*array)[0]++;
}

inline void _da_insert(void **array, void *element, size_t element_size, uint32_t pos) {
    _da_grow(array, element_size);

    memmove(((uint8_t *)(*array)) + (element_size * (pos + 1)),
            ((uint8_t *)(*array)) + (element_size * pos),
            element_size * (da_size(*array) - pos));

    memcpy(((uint8_t *)(*array)) + (element_size * pos),
           element, element_size);
    _da_raw(*array)[0]++;
}

inline void _da_pop(void **array, size_t element_size) {
    if(*array) {
        _da_raw(*array)[0]--;

        if(da_size(*array) < 1) {
            da_free(*array);
            *array = NULL;
        }
    }
}

inline void _da_erase(void **array, size_t element_size, uint32_t pos) {
    if(*array) {
        memmove(((uint8_t *)(*array)) + (element_size * pos),
                ((uint8_t *)(*array)) + (element_size * (pos + 1)),
                element_size * (da_size(*array) - pos - 1));

        _da_raw(*array)[0]--;

        if(da_size(*array) < 1) {
            da_free(*array);
            *array = NULL;
        }
    }
}

#endif


Here's an example usage of it:
 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
#include <stdio.h>
#include "darray.h"

int main() {
    int *ints = NULL;

    for(int i = 0; i < 10; i++) {
        da_push(ints, i);
    }

    da_erase(ints, 4);
    int x = 99;
    da_insert(ints, x, 4);

    printf("ints has the following contents:\n\n", da_cap(ints));

    for(uint32_t i = 0; i < da_size(ints); i++) {
        printf("%i", ints[i]);
        if(i != da_size(ints) - 1) {
            printf(", ");
        }
    }
    da_free(ints);
    printf("\n\n");

    return 0;
}


The output of the above snippet is the following:
1
2
3
ints has the following contents:

0, 1, 2, 3, 99, 5, 6, 7, 8, 9


-Delix
Mārtiņš Možeiko,
1. Don't use double where using just integers is enough.

_da_raw(*array)[1] += _da_raw(*array)[1] / 2;

Similar with divide by 1.5.

2. free function accepts NULL, so check if *array is non-NULL in _da_free function is redundant.

3. You can simplify _da_push function a lot by joining all the cases in one simple condition:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void _da_push(void **array, void *element, size_t element_size)
{
    uint32_t size = da_size(*array);
    uint32_t cap = da_cap(*array);

    if (size == cap)
    {
        uint32_t new_cap = cap ? cap + cap/2 : _DXE_DARRAY_START_CAP;
        uint32_t* new = realloc(_da_raw(*array), new_cap * element_size + 2*sizeof(uint32_t));
        *array = new + 2;
        new[0] = size;
        new[1] = new_cap;
    }
      
    memcpy((uint8_t*)_da_raw(*array) + (size * element_size), element, element_size);
    _da_raw(*array)[0]++;
}

Neo Ar,
Why are you realloc'ing in the pop? RIP performance

if you want to have a way to shrink the cap to fit the size I would have a separate function for that
Alex Baines,
Looks pretty good, one thing I might miss from stb's stretchy buffer though is sb_add.
1
memcpy(sb_add(dst, n), src, n);
works nicely to append to a char* string buffer for example.

Also is this code correct?
1
2
3
4
//get the raw array position
*array = (uint32_t *)(*array) - 2;
//realloc to the new cap
*array = realloc(*array, (da_cap(*array) * element_size) + (2 * sizeof(uint32_t)));

da_cap subtracts 2 from the pointer itself, so I feel like the call in the realloc would be underflowing after manually adjusting the array above.
Ryan Fleury,
@insofaras

Thanks! Also yeah, that would be a great feature; I'll implement that.

Also, you're absolutely correct; that code was not doing what I wanted it to! I fixed it now; I'll post an updated version soon.
Ryan Fleury,
@mio

Fair point, done!
Ryan Fleury, Edited by Ryan Fleury on
@mmozeiko

1. Ah, right; wasn't thinking about this. Implemented this change.

2. Wasn't sure about this; thanks!

3. I see what you're saying. I personally tend to try to stay away from the ternary operator, but I effectively did the same thing without it.

I'll upload an updated version in a minute...
Mārtiņš Možeiko, Edited by Mārtiņš Možeiko on
Your code in _da_insert will do one memcpy too much. You need to start with size-1 index, not with size index.

Also there's no need to use for loop with memcpy in _da_insert. You can do just one memmove instead:
1
2
3
    memmove(((uint8_t *)(*array)) + (element_size * (pos + 1)),
            ((uint8_t *)(*array)) + (element_size * pos),
            element_size * (da_size(*array) - pos - 1));

Same in _da_erase.
Neo Ar, Edited by Neo Ar on
[s]Why did you change the growth factor from 1.5 to 2 and linear instead of exponential?[/s] 2 is the mathematically worst possible growth factor for exponential growth, and linear growth is worse than exponential. Please watch:

https://youtube.com/watch?v=ZnXbh83xtZk?t=4m44s

in _da_growth you have the following:
1
2
3
        if(size >= da_cap(*array)) {
            new_cap = da_cap(*array) + (da_cap(*array) / 2);
        }


size will never be > than cap, shouldn't that be ==?

[s]why are you setting new_cap to be cap + cap/2?[/s] You should grow your buffer exponentially.

1
new_cap = da_cap(*array) * 1.5;


edit: cap + cap/2 is the same as cap * 1.5 isn't it, I'm stupid~

edit2: in _da_shrink you do cap - cap/3 to find the previous cap size, shouldn't that be / 2?

offtopic: why doesn't hmn support strikethrough text and it fails to embed youtube videos with shortlinks and apparently fails to embed them with timestamps also

Mārtiņš Možeiko, Edited by Mārtiņš Možeiko on
@miotatsu: x/1.5 = x/(3/2) = x*2/3 = x*3/3-x/3 = x-x/3
Neo Ar, Edited by Neo Ar on
yeah Delix pointed that out to me on IRC earlier, not a good day for me with math ;)

edit: oh also while I'm thinking of it, Delix timed the memcpy loop vs the memmove and the memcpy loop is apparently faster. My guess is because it ends up being more cache friendly. std::vector is also 2x faster for push according to Delix, I'm curious what they are doing to make it so fast...
Mārtiņš Možeiko,
memcpy could be faster because it supports only non-overlapping regions. memmove needs to test if src and dst regions overlap and then do copy backwards if they do. But not sure why it is 2x slower. It shouldn't be much slower, maybe tiny bit slower. Unless it is used for very small sizes. But then the copy time doesn't really matter, copying small sizes is very fast anyway.

But I doubt that one memmove is slower than hundreds or even thousands memcpy calls. Especially when element_size would be 1 (like char). It should be other way around.