tabular

dvec.h (4568B)

#pragma once

#include "allocator.h"

#include <sys/types.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>

#define DVEC_ERRNO(rc) ((rc) > 0 && (rc) & (1 << 30) ? (rc) & ~(1 << 30) : 0)
#define DVEC_ERR(lut, rc) errx(1, "libdvec: %s", \
	(rc) == DVEC_BAD ? lut[0] : (DVEC_ERRNO(rc) ? strerror(DVEC_ERRNO(rc)) : lut[rc+1]))

#define DVEC_ITER(dvec, p)     (p) = NULL; ((p) = dvec_iter_fwd((dvec), (p)));
#define DVEC_ITER_BWD(dvec, p) (p) = NULL; ((p) = dvec_iter_bwd((dvec), (p)));

#define DVEC_STRERR_INIT \
	[0] = "Failure", \
	[1+DVEC_OK] = "Success", \
	[1+DVEC_LOCKED] = "Locked", \
	[1+DVEC_MODIFIED] = "Modified"

#ifdef LIBDVEC_ASSERT_ARGS
#include "stdlib.h"
#define LIBDVEC_ABORT_ON_ARGS(cond) do { if (cond) abort(); } while (0)
#else
#define LIBDVEC_ABORT_ON_ARGS(cond)
#endif

#ifdef LIBDVEC_ASSERT_ALLOC
#include "stdlib.h"
#define LIBDVEC_ABORT_ON_ALLOC(cond) do { if (cond) abort(); } while (0)
#else
#define LIBDVEC_ABORT_ON_ALLOC(cond)
#endif

enum {
	DVEC_BAD = -1 & INT_MAX,
	DVEC_OK = 0,
	DVEC_LOCKED = 1 << 0,
	DVEC_MODIFIED = 1 << 1
};

struct dvec {
	size_t dsize;
	size_t len, cap;
	uint8_t *data;
	uint8_t locked : 1; /* prevents resizes */
	uint8_t fused : 1; /* single allocation w/ data */
	const struct allocator *allocator;
};

typedef bool (*dvec_sort_order_fn)(const void *left, const void *right, const void *user);
typedef int (*dvec_search_cmp_fn)(const void *other, const void *user);

int dvec_init(struct dvec *dvec, size_t dsize, size_t cap,
	const struct allocator *allocator);
int dvec_deinit(struct dvec *dvec);

struct dvec *dvec_alloc(size_t dsize, size_t cap,
	const struct allocator *allocator, int *rc);
struct dvec *dvec_alloc_fused(size_t dsize, size_t cap,
	const struct allocator *allocator, int *rc);
int dvec_free(struct dvec *dvec);

int dvec_copy(struct dvec *dst, struct dvec *src);
void dvec_move(struct dvec *dst, struct dvec *src);
void dvec_swap(struct dvec *dst, struct dvec *src);

void dvec_clear(struct dvec *dvec);
int dvec_reserve(struct dvec *dvec, size_t cap);
int dvec_shrink(struct dvec *dvec);

int dvec_add(struct dvec *dvec, size_t index, size_t count);
void dvec_rm(struct dvec *dvec, size_t index, size_t count);
void dvec_replace(struct dvec *dvec, size_t index,
	const void *data, size_t count);

void *dvec_iter_fwd(const struct dvec *dvec, const void *p);
void *dvec_iter_bwd(const struct dvec *dvec, const void *p);

int dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
	void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user);
int dvec_quick_sort_ex(struct dvec *dvec, const struct allocator *allocator,
	void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user);

ssize_t dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp,
	void *user, ssize_t *lower, ssize_t *higher);

static inline void *
dvec_at(const struct dvec *dvec, size_t index)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec || index >= dvec->len);

	return dvec->data + index * dvec->dsize;
}

static inline void *
dvec_at_back(const struct dvec *dvec, size_t index)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec || !index || index >= dvec->len);

	return dvec->data + (dvec->len  - 1 - index) * dvec->dsize;
}

static inline void *
dvec_front(const struct dvec *dvec)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec);

	return dvec->data;
}

static inline void *
dvec_back(const struct dvec *dvec)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec);

	return dvec->data + (dvec->len - 1) * dvec->dsize;
}

static inline bool
dvec_empty(const struct dvec *dvec)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec);

	return !dvec->len;
}

static inline size_t
dvec_len(const struct dvec *dvec)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec);

	return dvec->len;
}

static inline int
dvec_add_back(struct dvec *dvec, size_t count)
{
	return dvec_add(dvec, dvec->len, count);
}

static inline void
dvec_rm_back(struct dvec *dvec, size_t count)
{
	dvec_rm(dvec, dvec->len - count, count);
}

static inline void
dvec_lock(struct dvec *dvec, bool lock)
{
	dvec->locked = lock;
}

static inline void *
dvec_push(struct dvec *dvec)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec);

	dvec_reserve(dvec, dvec->len + 1);

	return dvec->data + dvec->len++ * dvec->dsize;
}

static inline void *
dvec_pop(struct dvec *dvec)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec || !dvec->len);

	return dvec->data + --dvec->len * dvec->dsize;
}

static inline size_t
dvec_idx(struct dvec *dvec, const void *p)
{
	LIBDVEC_ABORT_ON_ARGS(!dvec || p < dvec->data
		|| p >= dvec->data + dvec->dsize * dvec->len);

	return (size_t) ((uint8_t *)p - dvec->data) / dvec->dsize;
}