libds

a collection of simple data structures
Log | Files | Refs | LICENSE

commit b1d8eaab95257c6e823bafb2441e5e78020ca182
Author: sin <sin@2f30.org>
Date:   Mon,  7 Apr 2014 14:38:28 +0100

Initial commit

Diffstat:
ALICENSE | 21+++++++++++++++++++++
AMakefile | 48++++++++++++++++++++++++++++++++++++++++++++++++
Aconfig.mk | 20++++++++++++++++++++
Ads.h | 11+++++++++++
Ahat.c | 107+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 207 insertions(+), 0 deletions(-)

diff --git a/LICENSE b/LICENSE @@ -0,0 +1,21 @@ +MIT/X Consortium License + +© 2014 sin <sin@2f30.org> + +Permission is hereby granted, free of charge, to any person obtaining a +copy of this software and associated documentation files (the "Software"), +to deal in the Software without restriction, including without limitation +the rights to use, copy, modify, merge, publish, distribute, sublicense, +and/or sell copies of the Software, and to permit persons to whom the +Software is furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/Makefile b/Makefile @@ -0,0 +1,48 @@ +# libds - a simple data structures library +# See LICENSE file for copyright and license details. + +include config.mk + +SRC = hat.c +OBJ = ${SRC:.c=.o} +SOUT = ${NAME}.a + +all: options ${SOUT} + +options: + @echo ${NAME} build options: + @echo "CFLAGS = ${CFLAGS}" + @echo "LDFLAGS = ${LDFLAGS}" + @echo "CC = ${CC}" + +.c.o: + @echo CC $< + @${CC} -c ${CFLAGS} $< + +${OBJ}: config.mk + +${SOUT}: ${OBJ} + @ar rcs ${SOUT} ${OBJ} + +clean: + @echo cleaning + @rm -f *.a ${NAME} ${OBJ} + +install: all + @echo installing libraries to ${DESTDIR}${PREFIX}/lib + @mkdir -p ${DESTDIR}${PREFIX}/lib + @cp -f ${NAME}.a ${DESTDIR}${PREFIX}/lib + @chmod 755 ${DESTDIR}${PREFIX}/lib/${NAME}.* + @echo installing header file to ${DESTDIR}${PREFIX}/include + @mkdir -p ${DESTDIR}${PREFIX}/include + @cp -f ds.h ${DESTDIR}${PREFIX}/include + @chmod 644 ${DESTDIR}${PREFIX}/include/ds.h + +uninstall: + @echo removing libraries from ${DESTDIR}${PREFIX}/lib + @rm -f ${DESTDIR}${PREFIX}/lib/${NAME}.a + @echo removing header file from ${DESTDIR}${PREFIX}/include + @rm -f ${DESTDIR}${PREFIX}/include/ds.h + +.PHONY: all options clean install uninstall +# DO NOT DELETE diff --git a/config.mk b/config.mk @@ -0,0 +1,20 @@ +NAME = libds +VERSION = 0.0 + +# Customize below to fit your system + +# paths +PREFIX ?= /usr +MANPREFIX = ${PREFIX}/share/man + +# includes and libs +INCS = -I. -I/usr/include +LIBS = -L/usr/lib -lc + +# flags +CPPFLAGS = -DVERSION=\"${VERSION}\" +CFLAGS = -std=c99 -pedantic -Wall -Os ${INCS} ${CPPFLAGS} +LDFLAGS = ${LIBS} + +# compiler and linker +CC = cc diff --git a/ds.h b/ds.h @@ -0,0 +1,11 @@ +#ifndef LIBDS_H +#define LIBDS_H + +#include <stddef.h> + +struct hat *hat_init(void); +void hat_free(struct hat *); +size_t hat_add(struct hat *, void *); +void *hat_get(struct hat *, size_t); + +#endif diff --git a/hat.c b/hat.c @@ -0,0 +1,107 @@ +#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; +}