CODEWITHSUNDEEP
c
user107498
user107498

Reputation:

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

From here: A tidy little C implementation of stretchy buffers (aka C++ vectors) The code's description says this:

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

I should preface this by saying that I only know really a little bit of C, and this is essentially uncharted territory. I have never used double pointers, void pointers, or any memory functions like realloc. Could someone explain what is happening all over this code in plain english? It uses a lot of fancy macro definitions that I do not understand, which leaves me wondering what it would look like written out proper.

The 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;
       }
    }

Upvotes: 10

Views: 5914

Answers (4)

Kiril Osiyuk
Kiril Osiyuk

Reputation: 49

I made my own stretchy buffer for personal use, it is simple. Let's start with testing code, that shows the usage of such 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);
        }
}

From here we see, that ints can point to the array, or NULL. It is actually an array, and you can access elements as usual ints[i]. But it is dynamically allocated, 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 to access that 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 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 is actually some fancy macros, but operations is 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))

The only thing left is one function:

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 — buffer will automatically allocate needed memory based on sizeof(*buf)

You can further extend this 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)

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490778

My initial advice would be to ignore this code and move on to something else. You're unlikely to learn anything of much use from analyzing this code.

If you insist on understanding it, the basic idea is pretty simple. The rest is mostly just fiddly details.

The basics: it manages an array. The first element of the array is used to hold the currently allocated size of the array. The second element is used to hold the number of elements currently in use. It has replacements for the normal operators to let you get to specific elements in "your" part of the array it allocated (i.e., since array[0] and array[1] are used for its own housekeeping, when you ask for element[n], it gives you array[n+2]).

From there, it's mostly a matter of keeping track of the currently used size versus the currently allocated size, and allocating a larger array when needed. It can/will also free the whole array when you tell it to (with stb_free).

Upvotes: 0

Jeremiah Willcock
Jeremiah Willcock

Reputation: 30999

In the code, a stretchy buffer is similar to a struct with three elements

  1. int sbm: The number of elements in the buffer.
  2. int sbn: The number of elements the buffer can grow to without needing to reallocate.
  3. ???: Your data (unknown type and size).

When you create a buffer, the code returns a pointer to the "your data" part, and so uses negative offsets from that to get to the other two fields. Because a NULL buffer pointer is treated as an empty buffer, that needs to be special cased in many places. The code that is like (a) ? x : y is saying that if a is NULL, return x, otherwise return y.

There are a few idioms that are macro versions of common C constructs:

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

Uses of macro parameters are generally put in extra parentheses, as are macro definitions, to make the macro safe to use with expressions as arguments and so the macro can be put into the middle of an expression.

When you add n elements, the code tests whether sbm + n is greater than sbn; if it is, realloc is used to create a new buffer and sbn is reset to the larger size. Your data is then put in.

Upvotes: 3

Keith
Keith

Reputation: 6834

As a start:

// 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 does all the allocation; if initially passed a pointer to null it will create the two integer header automatically.

Upvotes: 2

Related Questions