libds

simple data structures library and utility functions
git clone git://git.2f30.org/libds.git
Log | Files | Refs | LICENSE

commit e11ec1354ead0cc954095dc7c7e75120be2447ea
parent d2d469cf37b49722a1b25213af966eaea23d95da
Author: sin <sin@2f30.org>
Date:   Mon Apr  7 21:44:07 +0100

Rename hat to vector

This really is a dynamic array implementation using hashed-array
trees.

Diffstat:
Makefile | 2+-
TODO | 2+-
ds.h | 10+++++-----
hat.c | 108-------------------------------------------------------------------------------
vector.c | 108+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 115 insertions(+), 115 deletions(-)
diff --git a/Makefile b/Makefile @@ -3,7 +3,7 @@ include config.mk -SRC = hat.c +SRC = vector.c OBJ = ${SRC:.c=.o} SOUT = ${NAME}.a diff --git a/TODO b/TODO @@ -1 +1 @@ -* hat remove operation +* vector remove operation diff --git a/ds.h b/ds.h @@ -3,10 +3,10 @@ #include <stddef.h> -/* hat.c */ -struct hat *hat_init(void); -void hat_free(struct hat *); -size_t hat_add(struct hat *, void *); -void *hat_get(struct hat *, size_t); +/* vector.c */ +struct vector *vector_init(void); +void vector_free(struct vector *); +size_t vector_add(struct vector *, void *); +void *vector_get(struct vector *, size_t); #endif diff --git a/hat.c b/hat.c @@ -1,108 +0,0 @@ -/* Hashed-array tree implementation */ -#include <stdio.h> -#include <stdlib.h> - -struct leaf { - void *data; -}; - -struct hat { - struct leaf **l; - size_t sz; - size_t ne; -}; - -static int -grow(struct hat *hat) -{ - struct leaf **tmp, *l; - size_t i, j, ne = 0; - - tmp = calloc(hat->sz * 2, sizeof(*tmp)); - if (!tmp) - return -1; - for (i = 0; i < hat->sz / 2; i++) { - tmp[i] = calloc(hat->sz * 2, sizeof(**tmp)); - if (!tmp[i]) { - while (--i >= 0) - free(tmp[i]); - free(tmp); - return -1; - } - } - for (i = 0; i < hat->sz; i++) { - l = tmp[ne / (hat->sz * 2)]; - for (j = 0; j < hat->sz; j++) { - l[ne % (hat->sz * 2)].data = hat->l[i][j].data; - ne++; - } - free(hat->l[i]); - } - free(hat->l); - hat->l = tmp; - hat->sz *= 2; - return 0; -} - -struct hat * -hat_init(void) -{ - struct hat *hat; - - hat = calloc(1, sizeof(*hat)); - if (!hat) - return NULL; - hat->sz = 2; - hat->l = calloc(hat->sz, sizeof(*hat->l)); - if (!hat->l) { - free(hat); - return NULL; - } - return hat; -} - -void -hat_free(struct hat *hat) -{ - size_t i; - - for (i = 0; i < hat->sz; i++) - free(hat->l[i]); - free(hat->l); -} - -size_t -hat_add(struct hat *hat, void *data) -{ - size_t index, offset; - struct leaf *l; - - if (hat->ne == hat->sz * hat->sz) - if (grow(hat) < 0) - return -1; - index = hat->ne / hat->sz; - offset = hat->ne % hat->sz; - if (!hat->l[index]) { - hat->l[index] = calloc(hat->sz, sizeof(**hat->l)); - if (!hat->l[index]) - return -1; - } - l = hat->l[index]; - l[offset].data = data; - return hat->ne++; -} - -void * -hat_get(struct hat *hat, size_t i) -{ - size_t index, offset; - struct leaf *l; - - index = i / hat->sz; - offset = i % hat->sz; - if (hat->l[index]) { - l = hat->l[index]; - return l[offset].data; - } - return NULL; -} diff --git a/vector.c b/vector.c @@ -0,0 +1,108 @@ +/* Vector implementation using a hashed-array tree */ +#include <stdio.h> +#include <stdlib.h> + +struct leaf { + void *data; +}; + +struct vector { + struct leaf **l; + size_t sz; + size_t ne; +}; + +static int +grow(struct vector *vector) +{ + struct leaf **tmp, *l; + size_t i, j, ne = 0; + + tmp = calloc(vector->sz * 2, sizeof(*tmp)); + if (!tmp) + return -1; + for (i = 0; i < vector->sz / 2; i++) { + tmp[i] = calloc(vector->sz * 2, sizeof(**tmp)); + if (!tmp[i]) { + while (--i >= 0) + free(tmp[i]); + free(tmp); + return -1; + } + } + for (i = 0; i < vector->sz; i++) { + l = tmp[ne / (vector->sz * 2)]; + for (j = 0; j < vector->sz; j++) { + l[ne % (vector->sz * 2)].data = vector->l[i][j].data; + ne++; + } + free(vector->l[i]); + } + free(vector->l); + vector->l = tmp; + vector->sz *= 2; + return 0; +} + +struct vector * +vector_init(void) +{ + struct vector *vector; + + vector = calloc(1, sizeof(*vector)); + if (!vector) + return NULL; + vector->sz = 2; + vector->l = calloc(vector->sz, sizeof(*vector->l)); + if (!vector->l) { + free(vector); + return NULL; + } + return vector; +} + +void +vector_free(struct vector *vector) +{ + size_t i; + + for (i = 0; i < vector->sz; i++) + free(vector->l[i]); + free(vector->l); +} + +size_t +vector_add(struct vector *vector, void *data) +{ + size_t index, offset; + struct leaf *l; + + if (vector->ne == vector->sz * vector->sz) + if (grow(vector) < 0) + return -1; + index = vector->ne / vector->sz; + offset = vector->ne % vector->sz; + if (!vector->l[index]) { + vector->l[index] = calloc(vector->sz, sizeof(**vector->l)); + if (!vector->l[index]) + return -1; + } + l = vector->l[index]; + l[offset].data = data; + return vector->ne++; +} + +void * +vector_get(struct vector *vector, size_t i) +{ + size_t index, offset; + struct leaf *l; + + index = i / vector->sz; + offset = i % vector->sz; + if (vector->l[index]) { + l = vector->l[index]; + return l[offset].data; + } + return NULL; +}