From: René Scharfe <l.s.r@web.de>
Date: Fri, 16 Jan 2026 20:19:02 GMT
Subject: Re: [PATCH 01/10] ivec: introduce the C side of ivec
Message-ID: <0a306227-5db8-4d12-865c-fa0efe5c6beb@web.de>
In-Reply-To: <adf1395d201e916f23accc7644d21aff4f58368b.1767379944.git.gitgitgadget@gmail.com>

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é