105 lines
2.6 KiB
C
105 lines
2.6 KiB
C
/* Copyright (C) 2024 Aryadev Chavali
|
|
* Created: 2024-08-11
|
|
* Author: Aryadev Chavali
|
|
* Description: A fast vector
|
|
*/
|
|
|
|
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#define MAX(A, B) ((A) > (B) ? (A) : (B))
|
|
#define MIN(A, B) ((A) < (B) ? (A) : (B))
|
|
|
|
/**
|
|
@brief A vector, consisting of a header and some payload (data).
|
|
@details The idea is that the user must never actually interact with this
|
|
structure directly, only the data involved. Any vector related functions
|
|
will take the pointer to the data and look behind it to get the header.
|
|
*/
|
|
typedef struct
|
|
{
|
|
uint64_t size;
|
|
uint64_t capacity;
|
|
uint8_t data[];
|
|
} vec_t;
|
|
|
|
#define VEC_SIZE(VEC) (((vec_t *)(VEC))[-1].size)
|
|
#define VEC_CAPACITY(VEC) (((vec_t *)(VEC))[-1].capacity)
|
|
|
|
void vec_make(uint8_t **data, uint64_t initial_capacity)
|
|
{
|
|
if (!data)
|
|
return;
|
|
initial_capacity = MAX(initial_capacity, 8);
|
|
vec_t *vector = calloc(1, sizeof(vec_t) + initial_capacity);
|
|
vector->size = 0;
|
|
vector->capacity = initial_capacity;
|
|
*data = vector->data;
|
|
}
|
|
|
|
void vec_free(uint8_t **data)
|
|
{
|
|
if (!data || !*data)
|
|
return;
|
|
free(((vec_t *)*data) - 1);
|
|
}
|
|
|
|
void vec_expand(uint8_t **data, uint64_t extra)
|
|
{
|
|
if (!data)
|
|
return;
|
|
|
|
// Move *data such that it is exactly at the vector header
|
|
vec_t *original = ((vec_t *)(*data)) - 1;
|
|
uint64_t new_cap = MAX(original->capacity * 2, original->capacity + extra);
|
|
vec_t *new_data = calloc(1, sizeof(vec_t) + new_cap);
|
|
|
|
new_data->size = original->size;
|
|
new_data->capacity = new_cap;
|
|
memcpy(new_data->data, original->data, original->size);
|
|
free(original);
|
|
|
|
*data = new_data->data;
|
|
}
|
|
|
|
void vec_append_byte(uint8_t **data, uint8_t byte)
|
|
{
|
|
if ((VEC_CAPACITY(*data) - VEC_SIZE(*data)) == 0)
|
|
vec_expand(data, 1);
|
|
|
|
(*data)[VEC_SIZE(*data)++] = byte;
|
|
}
|
|
|
|
void vec_append_bytes(uint8_t **data, const uint8_t *bytes, uint64_t size)
|
|
{
|
|
if ((VEC_CAPACITY(*data) - VEC_SIZE(*data)) < size)
|
|
vec_expand(data, size);
|
|
printf("%p, %p\n", *data, (((vec_t *)*data) - 1));
|
|
memcpy(*data + VEC_SIZE(*data), bytes, size);
|
|
VEC_SIZE(*data) += size;
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
const uint8_t *strings[] = {
|
|
(uint8_t *)"This",
|
|
(uint8_t *)"is",
|
|
(uint8_t *)"a",
|
|
(uint8_t *)"string",
|
|
};
|
|
uint8_t *vec = NULL;
|
|
vec_make(&vec, 1);
|
|
for (uint64_t i = 0; i < sizeof(strings) / sizeof(strings[0]); ++i)
|
|
{
|
|
// need sizeof(...) - 1 because of '\0'
|
|
vec_append_bytes(&vec, strings[i], sizeof(strings[i]) - 1);
|
|
vec_append_byte(&vec, ' ');
|
|
}
|
|
printf("%.*s\n", (int)VEC_SIZE(vec), vec);
|
|
|
|
vec_free(&vec);
|
|
return 0;
|
|
}
|