|
/**
|
|
* Copyright © 2019, Oracle and/or its affiliates. All rights reserved.
|
|
*
|
|
* Licensed under the Universal Permissive License v 1.0 as shown at
|
|
* http://oss.oracle.com/licenses/upl
|
|
*
|
|
*/
|
|
#define _GNU_SOURCE
|
|
#include "vec.h"
|
|
#include "malloc.h"
|
|
#include <assert.h>
|
|
|
|
struct vec {
|
|
size_t n;
|
|
size_t limit;
|
|
struct vecitem **items;
|
|
};
|
|
|
|
struct vec *mk_vec(void) {
|
|
struct vec *MALLOC(v);
|
|
size_t init = 2;
|
|
struct vecitem **MALLOC_N(items, init);
|
|
*v = (struct vec){0, init, items};
|
|
return v;
|
|
}
|
|
struct vec *vec_destroy(struct vec *vec) {
|
|
assert(vec->n == 0);
|
|
FREE(vec->items);
|
|
FREE(vec);
|
|
return NULL;
|
|
}
|
|
|
|
size_t vec_size(const struct vec *vec) {
|
|
return vec->n;
|
|
}
|
|
|
|
struct vecitem *vec_fetch(const struct vec *vec, size_t i) {
|
|
if (i < vec->n) return vec->items[i];
|
|
else return NULL;
|
|
}
|
|
|
|
void vec_push(struct vec *vec, struct vecitem *item) {
|
|
if (vec->n >= vec->limit) {
|
|
vec->limit *= 2;
|
|
REALLOC(vec->items, vec->limit);
|
|
}
|
|
assert(vec->n < vec->limit);
|
|
vec->items[vec->n++] = item;
|
|
}
|
|
|
|
struct vecitem* vec_pop(struct vec *vec) {
|
|
if (vec->n) {
|
|
if (vec->limit > 4
|
|
&& vec->n * 4 < vec->limit)
|
|
{
|
|
vec->limit /= 2;
|
|
assert(vec->n < vec->limit);
|
|
REALLOC(vec->items, vec->limit);
|
|
}
|
|
return vec->items[--vec->n];
|
|
} else {
|
|
return NULL;
|
|
}
|
|
}
|
|
|
|
struct vecitem* vec_peek(struct vec *vec) {
|
|
if (vec->n) return vec->items[vec->n-1];
|
|
else return NULL;
|
|
}
|
|
|
|
static int vec_compar(const void *av, const void *bv, void *compar_f) {
|
|
struct vecitem * const *ap = av;
|
|
struct vecitem * const *bp = bv;
|
|
int (*compar)(const struct vecitem *, const struct vecitem *) = compar_f;
|
|
return compar(*ap, *bp);
|
|
}
|
|
|
|
void vec_sort(struct vec *vec,
|
|
int (*compar)(const struct vecitem *, const struct vecitem *)) {
|
|
qsort_r(vec->items, vec->n, sizeof(vec->items[0]),
|
|
vec_compar, compar);
|
|
}
|