commit 301536c3a9c8d6a7d270b800112cdc9def2353d5
parent 6267d7cfabed3ad1a444c1309018d2917cd6591d
Author: vaplv <vaplv@free.fr>
Date: Mon, 8 May 2017 11:07:41 +0200
First implementation of the big buffer container
A big buffer is an out of core dynamic array for POD data.
Diffstat:
4 files changed, 415 insertions(+), 0 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -165,6 +165,7 @@ if(NOT NO_TEST)
new_test(test_algorithm)
new_test(test_atomic)
+ new_test(test_big_buffer rsys)
new_test(test_binary_heap rsys)
new_test(test_cstr rsys)
new_test(test_double2 ${MATH_LIB})
diff --git a/src/big_buffer.h b/src/big_buffer.h
@@ -0,0 +1,278 @@
+/* Copyright (C) 2013-2017 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#if !defined(BIGBUF_NAME) && !defined(BIGBUF_DATA)
+#ifndef BIGBUF_H
+#define BIGBUF_H
+
+#include "rsys.h"
+#include "math.h"
+
+#include <stdio.h>
+#include <string.h>
+
+/* Internal enumerate used to define the mode of the buffered data */
+enum bigbuf_mode__ { BIGBUF_READ__, BIGBUF_WRITE__ };
+
+#endif /* BIGBUF_H */
+#else
+
+/*
+ * Generate the big buffer data type and functions wrt the following macros:
+ * - BIGBUF_NAME: prefix of the big buffer functions & type;
+ * - BIGBUF_DATA: type of the data registered into the big buffer;
+ * - BIGBUF_ALIGNMENT: optional alignment of the buffer that stores the in
+ * buffered data of the big buffer. By default use the maximum between the
+ * default alignment of the BIGBUF_DATA and 16 bytes;
+ * - BIGBUIF_BUFSIZE: size in bytes of the buffered data. By default only one
+ * BIGBUF_DATA is buffered
+ *
+ * The name of the generated type is: struct bigbuf_<BIGBUF_NAME> and the
+ * rule to generate the function name is bigbuf_<BIGBUF_NAME>_<FUNCTION_NAME>.
+ */
+
+#ifndef BIGBUF_NAME
+ #error "Missing the BIGBUF_NAME macro defining the structure name"
+#endif
+#ifndef BIGBUF_DATA
+ #error "Missing the BIGBUF_DATA macro defining the buffer data type"
+#endif
+
+#define BIGBUF__ CONCAT(bigbuf_, BIGBUF_NAME)
+#define BIGBUF_FUNC__(Func) CONCAT(CONCAT(CONCAT(bigbuf_, BIGBUF_NAME),_), Func)
+#ifndef BIGBUF_BUFSIZE
+ #define BIGBUF_BUFSIZE 1
+#else
+ STATIC_ASSERT(BIGBUF_BUFSIZE > 0, BIGBUF_BUFSIZE_must_be_greater_than_0);
+#endif
+
+#ifndef BIGBUF_ALIGNMENT
+ #define BIGBUF_ALIGNMENT__ MMAX(ALIGNOF(BIGBUF_DATA), 16)
+#else
+ STATIC_ASSERT(IS_POW2(BIGBUF_ALIGNMENT),
+ BIGBUF_ALIGNMENT_must_be_a_power_of_2);
+ #define BIGBUF_ALIGNMENT__ MMAX(ALIGNOF(BIGBUF_DATA), 16)
+#endif
+
+struct BIGBUF__ {
+ struct { /* Buffered data */
+ BIGBUF_DATA* data;
+ size_t capacity;
+ size_t size;
+ } buf;
+
+ enum bigbuf_mode__ mode; /* Mode of the buffered data */
+
+ FILE* file; /* Stream where buffer data are written */
+ size_t buf_index; /* Id of the first big buffer item store into `buf' */
+ size_t size; /* Number of items stored into the big buffer */
+ long head; /* Head position indicator into `file' of the big buffer data */
+ int temp_file; /* Define if `file' is temporary file or not */
+
+ struct mem_allocator* allocator;
+};
+
+/*******************************************************************************
+ * Big buffer API
+ ******************************************************************************/
+static INLINE void
+BIGBUF_FUNC__(release)(struct BIGBUF__* bigbuf)
+{
+ ASSERT(bigbuf);
+ if(bigbuf->buf.data) MEM_RM(bigbuf->allocator, bigbuf->buf.data);
+ if(bigbuf->file && bigbuf->temp_file) fclose(bigbuf->file);
+}
+
+static INLINE res_T
+BIGBUF_FUNC__(init)
+ (struct mem_allocator* allocator, /* May be NULL <=> use default allocator */
+ FILE* stream, /* May be NULL <=> internally manage the stream */
+ struct BIGBUF__* bigbuf)
+{
+ size_t bufsz_adjusted;
+ res_T res = RES_OK;
+ ASSERT(bigbuf);
+ memset(bigbuf, 0, sizeof(struct BIGBUF__));
+
+ bigbuf->allocator = allocator ? allocator : &mem_default_allocator;
+ bigbuf->buf.capacity = BIGBUF_BUFSIZE / sizeof(BIGBUF_DATA);
+ bigbuf->buf.capacity = MMAX(bigbuf->buf.capacity, 1);
+ bufsz_adjusted = bigbuf->buf.capacity * sizeof(BIGBUF_DATA);
+
+ bigbuf->buf.data = MEM_ALLOC_ALIGNED
+ (bigbuf->allocator, bufsz_adjusted, BIGBUF_ALIGNMENT__);
+ if(!bigbuf->buf.data) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+ memset(bigbuf->buf.data, 0, bufsz_adjusted);
+ bigbuf->buf.size = 0;
+
+ if(stream) {
+ bigbuf->file = stream;
+ bigbuf->temp_file = 0;
+ } else {
+ bigbuf->file = tmpfile();
+ if(!bigbuf->file) {
+ res = RES_IO_ERR;
+ goto error;
+ }
+ bigbuf->temp_file = 1;
+ }
+
+ bigbuf->buf_index = 0;
+ bigbuf->head = ftell(bigbuf->file);
+ bigbuf->size = 0;
+ bigbuf->mode = BIGBUF_WRITE__;
+
+exit:
+ return res;
+error:
+ BIGBUF_FUNC__(release)(bigbuf);
+ goto exit;
+}
+
+static INLINE res_T
+BIGBUF_FUNC__(flush)(struct BIGBUF__* bigbuf)
+{
+ BIGBUF_DATA* buf_data;
+ size_t buf_size, write_size;
+ ASSERT(bigbuf);
+
+ if(bigbuf->mode == BIGBUF_READ__) return RES_OK;
+ if(!bigbuf->buf.size) return RES_OK;
+
+ buf_size = bigbuf->buf.size;
+ buf_data = bigbuf->buf.data;
+ ASSERT(bigbuf->buf_index + buf_size == bigbuf->size);
+
+ fseek(bigbuf->file, 0, SEEK_END);
+ write_size = fwrite(buf_data, sizeof(BIGBUF_DATA), buf_size, bigbuf->file);
+ if(write_size == buf_size) {
+ bigbuf->buf.size = 0; /* Clear buffered data */
+ bigbuf->buf_index = bigbuf->size;
+ return RES_OK;
+ } else if(write_size) {
+ size_t cp_size = buf_size - write_size;
+ memmove(buf_data, buf_data + write_size, cp_size);
+ bigbuf->buf.size = cp_size;
+ bigbuf->buf_index = bigbuf->buf_index + write_size;
+ return RES_IO_ERR;
+ } else {
+ return RES_IO_ERR;
+ }
+}
+
+static INLINE res_T
+BIGBUF_FUNC__(push_back)(struct BIGBUF__* bigbuf, const BIGBUF_DATA* data)
+{
+ ASSERT(bigbuf);
+
+ if(bigbuf->size == SIZE_MAX) return RES_MEM_ERR;
+ if(bigbuf->mode == BIGBUF_READ__) {
+ bigbuf->buf.size = 0; /* Clear buffered data */
+ bigbuf->buf_index = bigbuf->size;
+ }
+
+ ASSERT(bigbuf->buf.size < bigbuf->buf.capacity);
+ bigbuf->buf.data[bigbuf->buf.size++] = *data; /* Push back */
+ bigbuf->mode = BIGBUF_WRITE__;
+ ++bigbuf->size;
+
+ if(bigbuf->buf.size == bigbuf->buf.capacity) {
+ return BIGBUF_FUNC__(flush)(bigbuf);
+ } else {
+ return RES_OK;
+ }
+}
+
+static FINLINE size_t
+BIGBUF_FUNC__(size_get)(const struct BIGBUF__* bigbuf)
+{
+ ASSERT(bigbuf);
+ return bigbuf->size;
+}
+
+static INLINE res_T
+BIGBUF_FUNC__(at)(struct BIGBUF__* bigbuf, const size_t at, BIGBUF_DATA* data)
+{
+ BIGBUF_DATA* buf_data;
+ size_t buf_size;
+ res_T res = RES_OK;
+ ASSERT(bigbuf && data);
+
+ if(at >= bigbuf->size) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ buf_size = bigbuf->buf.size;
+ buf_data = bigbuf->buf.data;
+
+ if(at < bigbuf->buf_index || at >= bigbuf->buf_index + buf_size) {
+ size_t read_size;
+ size_t buf_index;
+ long cur, offset;
+ int err;
+
+ if(bigbuf->mode == BIGBUF_WRITE__) {
+ res = BIGBUF_FUNC__(flush)(bigbuf);
+ if(res != RES_OK) goto error;
+ }
+
+ buf_index = at / bigbuf->buf.capacity * bigbuf->buf.capacity;
+
+ cur = ftell(bigbuf->file);
+ offset = bigbuf->head + (long)(sizeof(BIGBUF_DATA)*buf_index) - cur;
+ err = fseek(bigbuf->file, offset, SEEK_CUR);
+ if(err < 0) {
+ res = RES_IO_ERR;
+ goto error;
+ }
+
+ buf_size = MMIN(bigbuf->size - buf_index, BIGBUF_BUFSIZE);
+ bigbuf->buf.size = buf_size;
+
+ read_size = fread(buf_data, sizeof(BIGBUF_DATA), buf_size, bigbuf->file);
+ bigbuf->buf_index = buf_index;
+ bigbuf->mode = BIGBUF_READ__;
+
+ if(read_size != buf_size) {
+ bigbuf->buf.size = read_size;
+ res = RES_IO_ERR;
+ goto error;
+ }
+ }
+
+ ASSERT(at >= bigbuf->buf_index);
+ *data = buf_data[at - bigbuf->buf_index];
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+#undef BIGBUF_ALIGNMENT
+#undef BIGBUF_BUFSIZE
+#undef BIGBUF_DATA
+#undef BIGBUF_NAME
+
+#undef BIGBUF__
+#undef BIGBUF_ALIGNMENT__
+#undef BIGBUF_FUNC__
+
+#endif /* !BIGBUF_NAME || !BIGBUF_TYPE */
+
diff --git a/src/dynamic_array.h b/src/dynamic_array.h
@@ -245,6 +245,13 @@ DARRAY_FUNC__(size_get)(const struct DARRAY_TYPE__* darray)
return darray->size;
}
+static INLINE size_t
+DARRAY_FUNC__(capacity)(const struct DARRAY_TYPE__* darray)
+{
+ ASSERT(darray);
+ return darray->capacity;
+}
+
static INLINE DARRAY_DATA*
DARRAY_FUNC__(data_get)(struct DARRAY_TYPE__* darray)
{
diff --git a/src/test_big_buffer.c b/src/test_big_buffer.c
@@ -0,0 +1,129 @@
+/* Copyright (C) 2013-2017 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "big_buffer.h"
+#include "test_utils.h"
+
+#include <stdlib.h>
+
+#define BIGBUF_NAME byte
+#define BIGBUF_DATA char
+#define BIGBUF_BUFSIZE 4
+#include "big_buffer.h"
+
+#define BIGBUF_NAME integer
+#define BIGBUF_DATA int
+#define BIGBUF_ALIGNMENT 64
+#define BIGBUF_BUFSIZE 1
+#include "big_buffer.h"
+
+static INLINE double
+rand_canonic(void)
+{
+ return (double)rand()/(double)(RAND_MAX-1);
+}
+
+static void
+test_byte(struct mem_allocator* allocator)
+{
+ struct bigbuf_byte bytes;
+ size_t i;
+ char byte;
+
+ CHECK(bigbuf_byte_init(allocator, NULL, &bytes), RES_OK);
+ CHECK(bigbuf_byte_size_get(&bytes), 0);
+
+ FOR_EACH(i, 0, 32) {
+ byte = (char)i;
+ CHECK(bigbuf_byte_push_back(&bytes, &byte), RES_OK);
+ }
+
+ CHECK(bigbuf_byte_size_get(&bytes), 32);
+ CHECK(bigbuf_byte_at(&bytes, 32, &byte), RES_BAD_ARG);
+
+ FOR_EACH(i, 0, bigbuf_byte_size_get(&bytes)) {
+ CHECK(bigbuf_byte_at(&bytes, i, &byte), RES_OK);
+ CHECK((size_t)byte, i);
+ }
+
+ FOR_EACH(i, 0, 16) {
+ size_t id = (size_t)(rand_canonic() * (double)bigbuf_byte_size_get(&bytes));
+ CHECK(bigbuf_byte_at(&bytes, id, &byte), RES_OK);
+ CHECK((size_t)byte, id);
+ }
+
+ FOR_EACH(i, 0, 32) {
+ byte = (char)(i + 32);
+ CHECK(bigbuf_byte_push_back(&bytes, &byte), RES_OK);
+ }
+
+ FOR_EACH(i, 0, bigbuf_byte_size_get(&bytes)) {
+ CHECK(bigbuf_byte_at(&bytes, i, &byte), RES_OK);
+ CHECK((size_t)byte, i);
+ }
+
+ bigbuf_byte_release(&bytes);
+}
+
+static void
+test_integer(void)
+{
+ struct bigbuf_integer ints;
+ size_t i;
+ int integer;
+
+ CHECK(bigbuf_integer_init(NULL, NULL, &ints), RES_OK);
+
+ FOR_EACH(i, 0, 999) {
+ integer = (int)i;
+ CHECK(bigbuf_integer_push_back(&ints, &integer), RES_OK);
+ }
+
+ FOR_EACH(i, 0, 666) {
+ size_t id = (size_t)(rand_canonic() * (double)bigbuf_integer_size_get(&ints));
+ CHECK(bigbuf_integer_at(&ints, id, &integer), RES_OK);
+ CHECK((size_t)integer, id);
+ }
+
+ FOR_EACH(i, 0, 666) {
+ integer = (int)i + 999;
+ CHECK(bigbuf_integer_push_back(&ints, &integer), RES_OK);
+ }
+
+ FOR_EACH(i, 0, bigbuf_integer_size_get(&ints)) {
+ CHECK(bigbuf_integer_at(&ints, i, &integer), RES_OK);
+ CHECK((size_t)integer, i);
+ }
+
+ bigbuf_integer_release(&ints);
+}
+
+int
+main(int argc, char** argv)
+{
+ struct mem_allocator allocator_proxy;
+ (void)argc, (void)argv;
+
+ mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator);
+
+ test_byte(&allocator_proxy);
+ test_integer();
+
+ check_memory_allocator(&allocator_proxy);
+ mem_shutdown_proxy_allocator(&allocator_proxy);
+ CHECK(mem_allocated_size(), 0);
+ return 0;
+}
+
