From: Ezekiel Newren <ezekielnewren@gmail.com>
Date: Sat, 17 Jan 2026 15:58:13 GMT
Subject: Re: [PATCH 01/10] ivec: introduce the C side of ivec
Message-ID: <CAH=ZcbB=Yf=wn2O273adrvpUpE0bJGKwrAjOAjmB8AgJrjz5Bg@mail.gmail.com>
In-Reply-To: <0a306227-5db8-4d12-865c-fa0efe5c6beb@web.de>

On Fri, Jan 16, 2026 at 1:19 PM René Scharfe <l.s.r@web.de> wrote:
>
> On 1/2/26 7:52 PM, Ezekiel Newren via GitGitGadget wrote:
> > diff --git a/compat/ivec.c b/compat/ivec.c
> > new file mode 100644
> > index 0000000000..0a777e78dc
> > --- /dev/null
> > +++ b/compat/ivec.c
> > @@ -0,0 +1,113 @@
> > +#include "ivec.h"
> > +
> > +struct IVec_c_void {
> > +     void *ptr;
> > +     size_t length;
> > +     size_t capacity;
> > +     size_t element_size;
> > +};
> > +
> > +static void _set_capacity(void *self_, size_t new_capacity)
> > +{
> > +     struct IVec_c_void *self = self_;
> > +
> > +     if (new_capacity == self->capacity) {
> > +             return;
> > +     }
> > +     if (new_capacity == 0) {
> > +             free(self->ptr);
> > +             self->ptr = NULL;
> > +     } else {
> > +             self->ptr = realloc(self->ptr, new_capacity * self->element_size);
> > +     }
> > +     self->capacity = new_capacity;
> > +}
> > +
> > +
> > +void ivec_init(void *self_, size_t element_size)
> > +{
> > +     struct IVec_c_void *self = self_;
> > +
> > +     self->ptr = NULL;
> > +     self->length = 0;
> > +     self->capacity = 0;
> > +     self->element_size = element_size;
> > +}
> > +
> > +void ivec_zero(void *self_, size_t capacity)
> > +{
> > +     struct IVec_c_void *self = self_;
> > +
> > +     self->ptr = calloc(capacity, self->element_size);
> > +     self->length = capacity;
> > +     self->capacity = capacity;
> > +     // DO NOT MODIFY element_size!!!
> > +}
> > +
> > +void ivec_reserve_exact(void *self_, size_t additional)
> > +{
> > +     struct IVec_c_void *self = self_;
> > +
> > +     _set_capacity(self, self->capacity + additional);
> > +}
> > +
> > +void ivec_reserve(void *self_, size_t additional)
> > +{
> > +     struct IVec_c_void *self = self_;
> > +
> > +     size_t growby = 128;
> > +     if (self->capacity > growby)
> > +             growby = self->capacity;
> > +     if (additional > growby)
> > +             growby = additional;
> > +
> > +     _set_capacity(self, self->capacity + growby);
> > +}
>
> Constant growth steps like these cause linear growth and quadratic
> complexity.  ALLOC_GROW does exponential growth with factor 1.5 to
> get linear complexity.  Here's an old plea to do the same:
> https://blog.mozilla.org/nnethercote/2014/11/04/please-grow-your-buffers-exponentially/
>
> René

It _is_ exponential. ivec_reserve(&vec, 1) means grow by _at least_ 1.
I'm not using typical memory management as defined in
git-compat-util.h because I'm trying to get ivec to behave very
similarly to Rust's Vec so that when Rust is introduced into the code,
C programmers will already be familiar with how Vec operates _and_ so
that converting from IVec to Vec is as simple as refactoring IVec
declarations to Vec.

Since C does not support generics there is no _proper_ solution. What
I have come up with on the C side for ivec is my best effort
compromise.