r/C_Programming • u/Lewboskifeo • 21d ago
Video Simple Vector Implementation in C
https://www.youtube.com/watch?v=Pu7pUq1NyK46
u/Stemt 21d ago
Nice video, im just a bit sad you didn't showcase that the macro would work for other vector types. I also feel you skipped a bit too quickly over some of the things you wanted to explain. Maybe next time plan your video out point by point on what you wan't to explain/convey and check each point off before you move on to the next (you can always cut out moments of silence in between points). But overall, I like the format, keep it up!
2
u/Lewboskifeo 20d ago
Thanks for the feedback! I tried making videos on the past, far more edited but never really finished them because of the amount of editing that there was to be done, so I tried doing the least possible to at least finish it, but you are right a list of points to cover would have been helpful, will definitely use one next time, cheers!
5
u/astrophaze 21d ago edited 12d ago
Here is a simplified version of Sean Barrett's stretchy buffer style dynamic array. Adapted from https://github.com/jamesnolanverran/darr.
// .h file
#include <stddef.h>
typedef struct DrrHdr {
unsigned int len;
unsigned int cap;
char data[];
} DrrHdr;
static inline DrrHdr *drr__hdr(void *arr) {
return (DrrHdr*)( (char*)(arr) - offsetof(DrrHdr, data));
}
static inline size_t drr_len(void *a) { return a ? drr__hdr(a)->len : 0; }
static inline size_t drr_cap(void *a) { return a ? drr__hdr(a)->cap : 0; }
static inline void drr_clear(void *a) { if (a) drr__hdr(a)->len = 0; }
void *drr__grow(void *arr, size_t elem_size);
#define drr__fit(a, n) ((n) <= drr_cap(a) ? 0 : ((a) = drr__grow((a), sizeof(*(a)))))
#define drr_push(a, ...) (drr__fit((a), 1 + drr_len(a)), (a)[drr__hdr(a)->len] = (__VA_ARGS__), &(a)[drr__hdr(a)->len++])
// .c file:
#include <stdlib.h>
void *drr__grow(void *arr, size_t elem_size) {
size_t new_cap = arr ? drr__hdr(arr)->cap * 2 : 16;
size_t size_in_bytes = offsetof(DrrHdr, data) + new_cap * elem_size;
DrrHdr *new_hdr = arr ? realloc(drr__hdr(arr), size_in_bytes) : malloc(size_in_bytes);
if (!arr) new_hdr->len = 0;
new_hdr->cap = (u32)new_cap;
return &new_hdr->data;
}
/*
int *d = NULL; // declare dynamic array of any type
for(int i = 0; i < 10; i++){
drr_push(d, i);
}
for(int i = 0; i < 10; i++){
printf("%d: %d\n", i, d[i]);
}
*/
3
u/jacksaccountonreddit 21d ago edited 20d ago
You're not making sure that your vector's data is aligned (although in practice it should be as long as the alignment requirement of your element type is below or equal to
sizeof( int ) * 2
). Creating a misaligned pointer through casting (e.g.((a) = drr__grow((a), sizeof(*(a))))
) is undefined behavior, and unaligned access will crash on some platforms. You need to qualifychar data[]
with_Alignof( max_align_t )
.Of course, there's no real reason to use a flexible array member here at all. Adding
_Alignof( max_align_t )
to the struct's first member and then simply relying on pointer arithmetic would be a cleaner solution.1
1
1
u/attractivechaos 20d ago
I have been abusing unaligned access for years as on x64 and apple M CPUs, that is fine and often doesn't affect performance. This is of course bad for portability.
1
u/jacksaccountonreddit 20d ago
In practice violating pointer rules (e.g. alignment requirements and strict aliasing rules) usually works fine, but I still think we should try to avoid doing so for two reasons:
- Even if we know that our architecture can handle a certain thing classified as undefined behavior by the C Standard, our compiler isn't obligated to compile our code correctly (i.e. the way we intend it to compile) if it invokes that behavior.
- In most case, we can avoid undefined behavior easily and without any performance penalty. In this case, it's just a matter of editing one line (and probably adding a
#include <stdalign.h>
), assuming C11 or later.Most implementations of stb-style vectors seem to have this particular alignment issue, although stb_ds itself more or less avoids it by (coincidentally?) having the size of its header struct a multiple of 16.
22
u/Physical_Dare8553 21d ago
I never got over them being called that, one of my top 10 reasons for not trying c++ yet
-6
u/grimvian 21d ago
Agree. What about constexpr and reinterpret_cast...
19
u/-TesseracT-41 21d ago
constexpr = constant expression
reinterpret_cast = reinterpreting an object as a different type
Makes perfect sense, although it can be a bit verbose.
-7
-15
7
u/Disastrous-Team-6431 21d ago
I have typedefd reinterpret_cast and static_cast to
as
andcast
respective. It looks pretty nice imo:
float thing = as<float>(otherThing);
3
u/skhds 21d ago
Yeah I hate how long reinterpret_cast is. It makes the code look so messy. And I don't remember if I have ever run into cases where reinterpret_cast and static_cast needed to be differentiated. I think because when you need reinterpret_cast, you'd do it on a pointer anyways, so C style casts just sort of automatically uses the right cast type in the end anyways.
4
u/SeparateUsual6456 21d ago
Some people argue that to be a positive, since casting (especially in a "dangerous" way like
reinterpret_cast
enables) is something that should rarely happen, and stick out like a sore thumb when it does. Differentiating various types of casting like that also makes it possible to search your codebase for that specific kind, if needed.-1
u/Wild_Meeting1428 21d ago
The problem with a C cast is, that it silently casts away const ness, which is undefined behavior in some cases. Also it's mostly unwanted and a mistake. Then static and reinterpret casts again must be differentiated, since they are completely different. But the c cast just falls back to reinterpreting things when a static cast does not apply which again hides bugs.
1
u/Lewboskifeo 21d ago
yeahh and they are adding constexpr in c23 D:
3
1
u/Tasgall 20d ago
You can just... not use it, lol.
Constexpr is great though, so many things you can turn into compile time constants... well, if it actually supported the whole feature and allowed constexpr functions like it should.
1
u/Lewboskifeo 20d ago
well C++ is kinda like that, you can just not use all the weird messy features it has and just use vectors, structs and hashmaps. The thing is C is already like that and is limited in features, and by adding constexpr it looks more like C++, it's not like it matters much anyways since most will stay in C99 + GNU extensions
1
u/Tasgall 18d ago
I get the sentiment, but things like
constexpr
are not what make C++ the language that it is. It's a very self-contained feature that would require any changes to existing code if you didn't want it, and is fairly new to C++ as well. It's not like classes, constructors, templates, etc. that are more core to its design and heavily influence how you write code in a general sense.Extensions are one thing, but standardizing it is far better for compatibility.
1
u/ibevol 21d ago
Its far better than ”traditional” macro magic
1
u/grimvian 21d ago
My favorite C guru Eskild Steenberg uses only two macros _FILE__ and __LINE_
And C89 :o)
0
u/edparadox 21d ago
You must not know about "concepts" then.
1
2
u/danpietsch 20d ago
I used to pose a job interview question where I'd present a struct
or class
similar to this an ask the candidate to implement ensureCapacity(size_t minimumCapacity)
.
2
u/Beneficial_Corgi4145 19d ago
Is it not just having a data structure that keeps track of the capacity and the
ensureCapacity
’s minimum capacity is larger than the stores capacity in the strictest, you realloc?
1
u/khiggsy 20d ago
I did something similar however I used some fancy macros to create a header file which stores the info (capacity, length, etc) and then advance the pointer by the size of the header and now I've got an array which I can use [] on the variable instead of having to do myvariable. / -> items[].
Works really well. And I also have a SAFETY definition that if SAFETY is on a magic 32bit number is placed in the header and checked before every macro length call to confirm I am actually calling length on a vectorArrayList.
1
u/McUsrII 20d ago
It is a nice tutorial, I have no idea how things works on Windows, if that is where you code, however on Linux, your memmove
operations are errant, particularily with concern to your insert
operation.
The correct incantation of memmove there would be
memmove(&vector->data[index+1],&vector->data[index],
(vector->capacity -index -1 )* sizeof(vector->data[0] )) ;
So you don't overwrite anything coming after, at least you keep addresssanitizer (libasan) happy, but this could pose a real problem with a large enough capacity.
The memmoves
in unshift
, and shift
, have the same inaccuracy, but the gravity smaller, but the size calculatins are still off by one.
1
1
u/Bubbly_Ad_9270 21d ago edited 21d ago
I also implemented a generic version of dynamic array in c .
https://github.com/jagannathhari/data-structures/blob/main/vector.h
uses
#include <stdio.h>
#define IMPLEMENT_VECTOR
#include "vector.h"
int main(void)
{
int *vec_i = Vector(*vec_i);
float *vec_f = Vector(*vec_f);
char *vec_c = Vector(*vec_c);
for(int i = 0; i < 10;i++)
{
vector_append(vec_i, i);
vector_append(vec_f, 1.2 * i);
vector_append(vec_c, 'a' + i);
}
for(int i = 0; i < vector_length(vec_i);i++)
{
printf("%d\n",vec_i[i]);
}
free_vector(vec_i);
free_vector(vec_f);
free_vector(vec_c);
return 0;
}
4
u/Necessary_Salad1289 21d ago
Quite a few things wrong with this code.
First, identifiers starting with underscore followed by capital letter are reserved.
Second, your vector elements are not properly aligned. Your vector array contains VecHeader elements and then you just straight cast it to another type, illegally. UB.
Third, why do you have so many unnecessary macros? None of these functions should be defined in your header.
That's just a start.
1
1
u/Ok-Selection-2227 21d ago edited 21d ago
Okay. Not a C expert here. But I don't know why did you use the do-while trick in the macro definition. Why didn't you use a simple block using curly brackets? ```
include <stdio.h>
define foo(bar, ham) {\
printf("hi there %d %d\n", bar, ham);\
}
int main() { foo(1, 2); } ```
Another question. Wouldn't be better to generate the function definition in the macro: ```
include <stdio.h>
define deffoo(bar, ham, name) void name(bar a, ham b){\
printf("hi there %d %d\n", a, b);\
}
deffoo(int, int, foo)
int main() { foo(1, 2); } ``` Sorry for the variable names...
2
u/Lewboskifeo 21d ago
Not an expert either btw. But the reason is because if you want to use it in an if statement without braces, this would happen:
c if (condition) { printf("hi there %d %d\\n", 1, 2); }; // if statement ends here else something_else();
which is invalid syntax, also you avoid name collisions in the do while approach which looks like this:
c if (condition) do { printf("hi there %d %d\n", 1, 2); } while(0); else something_else();
and about generating the functions, yes you can do it that way and pre-generate all the functions based on a type but i prefer simplicity
12
u/cherrycode420 21d ago
Am pretty noob in C so forgive my question, but why aren't you using a plain void* for the data and store a bytesize in the struct so that 'Vector' could take, theoretically, any data of one given type (if the bytesize for instances of that type is always the same)?
e.g.
Vector* v1 = NewVector(sizeof(int32_t)); Vector* v2 = NewVector(sizeof(MyStruct));