a.capacity Generic dynamic array in 60 lines of C
81–90 of 110 posts
Re: Generic dynamic array in 60 lines of C
#82Not an entirely uncommon idea. I've written one. There's also a well-known one here, in klib: https://github.com/attractivechaos/klib/blob/master/kvec.h
Who didn't. Almost any C program dealing with strings and collections has to have their own implementation or import one. Part of the reason why C developers "feel" productive, but can't produce anything of meaningful complexity.
Have you ever heard of Linux?
Re: Generic dynamic array in 60 lines of C
#83Not an entirely uncommon idea. I've written one. There's also a well-known one here, in klib: https://github.com/attractivechaos/klib/blob/master/kvec.h
[deleted]
Re: Generic dynamic array in 60 lines of C
#84Not an entirely uncommon idea. I've written one. There's also a well-known one here, in klib: https://github.com/attractivechaos/klib/blob/master/kvec.h
Probably many have written a vector header like this. It baffles me why this one reaches the front page of HN given that the implementation is not that great. A few problems (some have been mentioned by others as well).
1. not using "do {} while (0)". This may lead to compile errors.
2. using uint32_t for capacity. On 64-bit machine, this doesn't save memory.
3. DYN_ARR_RESIZE() may have a quadratic time complexity if some is calling DYN_ARR_RESIZE(a, 10); DYN_ARR_RESIZE(a, 11); DYN_ARR_RESIZE(a, 12) etc in a loop. kv_resize() in kvec.h wouldn't have this problem.
4. Segfault if capacity is 0.
Re: Generic dynamic array in 60 lines of C
#85I don't like the use of macros for things like this. Macros in general should rarely or sparingly be used. I'm also not certain one should use "end pointers." Conventionally, it seems more advisable to use `size_t capacity`, `size_t length`, and `void *data`. Great use of Cunningham's Law, though! I appreciate C posts on Hacker News.
Amusingly, Ward Cunningham denies inventing Cunningham's law and I feel compelled to correct that potential misunderstanding.
How meta...
Re: Generic dynamic array in 60 lines of C
#86I don't like the use of macros for things like this. Macros in general should rarely or sparingly be used. I'm also not certain one should use "end pointers." Conventionally, it seems more advisable to use `size_t capacity`, `size_t length`, and `void *data`. Great use of Cunningham's Law, though! I appreciate C posts on Hacker News.
One should always use size_t to keep lengths. Reallocating the array invalidates all pointers but does not invalidate offsets.
Great point, thank you. I've never actually heard it expressed this way before, but now I have another reason to prefer explicit lengths.
Re: Generic dynamic array in 60 lines of C
#87Earlier quoted context omitted.
Where do you check that capacity is nonzero? When capacity is zero, what happens on this line? a.capacity "all c code is unsafe" is not an excuse to permit bloody obvious, undocumented memory overruns. I write a lot of c. Avoiding the unsafe bits, avoiding UB, is the skill required to write good c. "C code is unsafe" is a Rustacean marketing slogan. Don't believe it, but definitely don't practice it.
just don't initialize it with 0 capacity :-)
For a library, if the user input is wrong, throw an error or an assertion failure. It shouldn't be causing an uninformative segmentation fault which your library does. The fix is a trivial. Why so defensive?
Re: Generic dynamic array in 60 lines of C
#88a.capacity That's not ideal. Imagine you are at 32GB capacity, the next realloc will ask for 64GB which is pretty excessive.
My understanding is that this is the typical behavior of dynamic arrays
Re: Generic dynamic array in 60 lines of C
#89Earlier quoted context omitted.
One should always use size_t to keep lengths. Reallocating the array invalidates all pointers but does not invalidate offsets.
Great point, thank you. I've never actually heard it expressed this way before, but now I have another reason to prefer explicit lengths.
A concrete example that I've been working on recently: a parser/lexer backed by an input buffer. Its state looks like this:
struct parser {
struct {
unsigned char *buffer;
size_t capacity;
} buffer;
struct {
size_t read;
size_t write;
} position;
};
Had they been pointers within the [buffer, capacity[ range, they would have become invalid whenever buffer is reallocated for expansion since its location in memory would change. So I chose to implement the read and write heads as offsets to the buffer's base address and calculating those pointers only when they're needed.
Re: Generic dynamic array in 60 lines of C
#90a.capacity That's not ideal. Imagine you are at 32GB capacity, the next realloc will ask for 64GB which is pretty excessive.
This isn't suitable for arrays that large regardless of the resizing multiplier.
realloc() generally allocates a new block of memory of the new size, copies the entire content over, and then frees the old block. Only sometimes you get to be lucky and have enough spare room after the existing data in the virtual address map to not need that copy.
By the point this copying becomes relevant, a continuous dynamic array like this becomes fundamentally the wrong data structure.