This is an implementation of a vector in C in 27 lines written by Sean Barrett. Can someone explain to me how this works?

Question

Hence: An ordered small implementation of C from elastic buffers (the so-called C ++ vectors). The code description says the following:

declare an empty buffer with something like "mytype myarray = NULL", and then use the sb () functions to control; read / write individual items by indexing as usual

I must state this by saying that I know only a little C, and this is essentially uncharted territory. I have never used double pointers, void pointers or any memory functions like realloc. Can someone explain what happens in all of this code in plain English? It uses a lot of fantastic macro definitions that I don’t understand, which leaves me wondering how this will look right.

Code:

// stretchy buffer // init: NULL // free: sbfree() // push_back: sbpush() // size: sbcount() // #define sbfree(a) ((a) ? free(stb__sbraw(a)),0 : 0) #define sbpush(a,v) (stb__sbmaybegrow(a,1), (a)[stb__sbn(a)++] = (v)) #define sbcount(a) ((a) ? stb__sbn(a) : 0) #define sbadd(a,n) (stb__sbmaybegrow(a,n), stb__sbn(a)+=(n), &(a)[stb__sbn(a)-(n)]) #define sblast(a) ((a)[stb__sbn(a)-1]) #include <stdlib.h> #define stb__sbraw(a) ((int *) (a) - 2) #define stb__sbm(a) stb__sbraw(a)[0] #define stb__sbn(a) stb__sbraw(a)[1] #define stb__sbneedgrow(a,n) ((a)==0 || stb__sbn(a)+n >= stb__sbm(a)) #define stb__sbmaybegrow(a,n) (stb__sbneedgrow(a,(n)) ? stb__sbgrow(a,n) : 0) #define stb__sbgrow(a,n) stb__sbgrowf((void **) &(a), (n), sizeof(*(a))) static void stb__sbgrowf(void **arr, int increment, int itemsize) { int m = *arr ? 2*stb__sbm(*arr)+increment : increment+1; void *p = realloc(*arr ? stb__sbraw(*arr) : 0, itemsize * m + sizeof(int)*2); assert(p); if (p) { if (!*arr) ((int *) p)[1] = 0; *arr = (void *) ((int *) p + 2); stb__sbm(*arr) = m; } } 

Answer 1

My initial advice is to ignore this code and move on to something else. You are unlikely to learn much from analyzing this code.

If you insist on understanding this, the basic idea is pretty simple. The rest is basically just details.

Basics: It manages an array. The first element of the array is used to store the currently selected array size. The second element is used to store the number of elements used. It has replacements for normal operators, so that you can go to specific elements in the “your” part of the allocated array (ie, since array [0] and array [1] are used for your own household when you request element [n], it gives you an array [n + 2]).

From there, it’s mainly a matter of tracking the size currently used compared to the current distributed size and allocating a larger array if necessary. It can / will also free the entire array when you say it (using stb_free ).

Answer 2

In code, a stretched buffer is like a struct with three elements

• int sbm : number of elements in the buffer.
• int sbn : the number of elements that the buffer can grow without the need for redistribution.
• ??? : Your data (unknown type and size).

When you create a buffer, the code returns a pointer to the “your data” part and therefore uses negative offsets from this to go to two other fields. Since the NULL buffer pointer NULL considered an empty buffer, this has to be specially overlaid in many places. Code similar to (a) ? x : y (a) ? x : y , says that if a is NULL , return x , otherwise return y .

There are several idioms that are macro versions of common C constructs:

• a, b == a; b; a; b; .
• p ? x : y p ? x : y == if (p) a; else b; if (p) a; else b; .

The use of macro parameters is usually placed in extra parentheses, as well as macro definitions, to make the macro safe for use with expressions as arguments, and therefore the macro can be placed in the middle of the expression.

When you add n elements, the code checks to see if sbm + n sbn ; if so, realloc used to create a new buffer, and sbn is reset for a larger size. Then your data is placed.

Answer 3

At the beginning:

 // Given a, return a 'raw a', being two integers below a. // Those two access by the following calls. #define stb__sbraw(a) ((int *) (a) - 2) // The current number opf elements in the array; same as count #define stb__sbm(a) stb__sbraw(a)[0] // The number of elements available to the current storage #define stb__sbn(a) stb__sbraw(a)[1] 

So:

 // Free the raw storage #define sbfree(a) ((a) ? free(stb__sbraw(a)),0 : 0) 

stb__sbgrowf performs all distribution; if a pointer to zero is initially passed, it will automatically create two whole headers.

Answer 4

I made my own elastic buffer for personal use, it's simple. Let's start with a test code that shows the use of such a buffer / vector.

 void buf_test() { int *ints = NULL; enum { N = 1024 }; for (int i = 0; i < N; i++) { buf_push(ints, i); } assert(buf_len(ints) == N); for (int i = 0; i < buf_len(ints); i++) { assert(ints[i] == i); } } 

This shows that ints can point to an array or NULL . It is actually an array, and you can access elements as usual ints[i] . But it stands out dynamically, and somehow we need to store its length and capacity .

 typedef struct { size_t len; size_t cap; char buf[0]; } Bufhdr; 

Some macros help us access this structure.

 #define buf__hdr(b) ((Bufhdr *) ((size_t *) b - 2)) #define buf__len(b) ((b) ? buf__hdr(b)->len : 0) #define buf__cap(b) ((b) ? buf__hdr(b)->cap : 0) 

And decide when you need to grow our vector.

 #define buf__fits(b, n) (buf__len(b) + (n) <= buf__cap(b)) #define buf__grow(b, n) buf_grow((b), buf__len(b) + (n), sizeof(*(b))) #define buf__fit(b, n) (buf__fits(b, n) ? 0 : ((b) = buf__grow(b, n))) 

buf_push and buf_len are actually fancy macros, but the operations are simple. It is common practice to implement certain data structures using macros.

 #define buf_len(b) buf__hdr(b)->len #define buf_push(b, x) (buf__fit(b, 1), b[buf_len(b)++] = (x)) 

Only one function remains:

 void *buf_grow(const void *buf, size_t len, size_t elem_size) { size_t new_cap, new_size; Bufhdr *hdr; new_cap = buf__cap(buf) ? 2 * buf__cap(buf) : len; assert(len <= new_cap); new_size = offsetof(Bufhdr, buf) + new_cap * elem_size; if (buf) { hdr = realloc(buf__hdr(buf), new_size); } else { hdr = malloc(new_size); hdr->len = 0; } hdr->cap = new_cap; return hdr->buf; } 

You can use a pointer to any type - the buffer automatically allocates the necessary memory based on sizeof(*buf)

You can expand it to your needs, for example

 #define buf_reserve(b, n) buf_grow((b), (n), sizeof(*(b)) #define buf_free(b) ((b) ? free(buf__hdr(b)) : 0)