[Bf-blender-cvs] [913d8ec6082] blender2.8: BLI_memiter: Small API for many small allocations
Campbell Barton
noreply at git.blender.org
Sat Jul 29 15:54:46 CEST 2017
Commit: 913d8ec6082c4b42cd7957912078645af10ad024
Author: Campbell Barton
Date: Sat Jul 29 23:38:20 2017 +1000
Branches: blender2.8
https://developer.blender.org/rB913d8ec6082c4b42cd7957912078645af10ad024
BLI_memiter: Small API for many small allocations
- Each allocation can be a different size
(but should be smaller than the chunk size).
- Result can be looped over in order of allocation.
- Allocations are aligned to pointer size to avoid unaligned reads.
===================================================================
A source/blender/blenlib/BLI_memiter.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/BLI_memiter.c
A tests/gtests/blenlib/BLI_memiter_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_memiter.h b/source/blender/blenlib/BLI_memiter.h
new file mode 100644
index 00000000000..96a47d53984
--- /dev/null
+++ b/source/blender/blenlib/BLI_memiter.h
@@ -0,0 +1,72 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_MEMITER_H__
+#define __BLI_MEMITER_H__
+
+/** \file BLI_memiter.h
+ * \ingroup bli
+ */
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include "BLI_compiler_attrs.h"
+#include "BLI_compiler_compat.h"
+
+/* 512kb, good default for small elems. */
+#define BLI_MEMITER_DEFAULT_SIZE (2 << 18)
+
+struct BLI_memiter;
+struct BLI_memiter_chunk;
+
+typedef struct BLI_memiter BLI_memiter;
+
+/* warning, ATTR_MALLOC flag on BLI_memiter_alloc causes crash, see: D2756 */
+BLI_memiter *BLI_memiter_create(unsigned int chunk_size) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
+void *BLI_memiter_alloc(BLI_memiter *mi, unsigned int size) ATTR_RETURNS_NONNULL ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+void BLI_memiter_alloc_from(BLI_memiter *mi, uint elem_size, const void *data_from) ATTR_NONNULL(1, 3);
+void *BLI_memiter_calloc(BLI_memiter *mi, unsigned int size) ATTR_RETURNS_NONNULL ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+void BLI_memiter_destroy(BLI_memiter *mi) ATTR_NONNULL(1);
+void BLI_memiter_clear(BLI_memiter *mi) ATTR_NONNULL(1);
+unsigned int BLI_memiter_count(const BLI_memiter *mi) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+
+/* utils */
+void *BLI_memiter_elem_first(BLI_memiter *mi);
+void *BLI_memiter_elem_first_size(BLI_memiter *mi, unsigned int *r_size);
+
+/* private structure */
+typedef struct BLI_memiter_handle {
+ struct BLI_memiter_elem *elem;
+ uint elem_left;
+} BLI_memiter_handle;
+
+void BLI_memiter_iter_init(BLI_memiter *mi, BLI_memiter_handle *iter) ATTR_NONNULL();
+bool BLI_memiter_iter_done(BLI_memiter_handle *iter) ATTR_NONNULL();
+void *BLI_memiter_iter_step(BLI_memiter_handle *iter) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+void *BLI_memiter_iter_step_size(BLI_memiter_handle *iter, uint *r_size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __BLI_MEMITER_H__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index dc81ce000ea..1d865f99239 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -50,6 +50,7 @@ set(SRC
intern/BLI_kdtree.c
intern/BLI_linklist.c
intern/BLI_memarena.c
+ intern/BLI_memiter.c
intern/BLI_mempool.c
intern/DLRB_tree.c
intern/array_store.c
@@ -179,6 +180,7 @@ set(SRC
BLI_math_statistics.h
BLI_math_vector.h
BLI_memarena.h
+ BLI_memiter.h
BLI_memory_utils.h
BLI_mempool.h
BLI_noise.h
diff --git a/source/blender/blenlib/intern/BLI_memiter.c b/source/blender/blenlib/intern/BLI_memiter.c
new file mode 100644
index 00000000000..4d365680e8a
--- /dev/null
+++ b/source/blender/blenlib/intern/BLI_memiter.c
@@ -0,0 +1,354 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/blenlib/intern/BLI_memiter.c
+ * \ingroup bli
+ *
+ * Simple, fast memory allocator for allocating many small elements of different sizes
+ * in fixed size memory chunks,
+ * although allocations bigger than the chunk size are supported.
+ * They will reduce the efficiency of this data-structure.
+ * Elements are pointer aligned.
+ *
+ * Supports:
+ *
+ * - Allocation of mixed sizes.
+ * - Iterating over allocations in-order.
+ * - Clearing for re-use.
+ *
+ * Unsupported:
+ *
+ * - Freeing individual elements.
+ *
+ * \note We could inline iteration stepping,
+ * but tests show this doesn't give noticeable speedup.
+ */
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "BLI_utildefines.h"
+
+#include "BLI_memiter.h" /* own include */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_strict_flags.h" /* keep last */
+
+typedef uintptr_t data_t;
+typedef intptr_t offset_t;
+
+/* Write the chunk terminator on adding each element.
+ * typically we rely on the 'count' to avoid iterating past the end. */
+// #define USE_TERMINATE_PARANOID
+
+/* Currently totalloc isnt used. */
+ // #define USE_TOTALLOC
+
+/* pad must be power of two */
+#define PADUP(num, pad) (((num) + ((pad) - 1)) & ~((pad) - 1))
+
+typedef struct BLI_memiter_elem {
+ offset_t size;
+ data_t data[0];
+} BLI_memiter_elem;
+
+typedef struct BLI_memiter_chunk {
+ struct BLI_memiter_chunk *next;
+ /**
+ * internal format is:
+ * ``[next_pointer, size:data, size:data, ..., negative_offset]``
+ *
+ * Where negative offset rewinds to the start.
+ */
+ data_t data[0];
+} BLI_memiter_chunk;
+
+typedef struct BLI_memiter {
+ /* A pointer to 'head' is needed*/
+ struct BLI_memiter_chunk *head, *tail;
+ data_t *data_curr;
+ data_t *data_last;
+ /* Used unless a large element is requested.
+ * (which should be very rare!). */
+ uint chunk_size_in_bytes_min;
+ uint count;
+#ifdef USE_TOTALLOC
+ uint totalloc;
+#endif
+} BLI_memiter;
+
+
+BLI_INLINE uint data_offset_from_size(uint size)
+{
+ return (PADUP(size, (uint)sizeof(data_t))) / (uint)sizeof(data_t);
+}
+
+static void memiter_set_rewind_offset(BLI_memiter *mi)
+{
+ BLI_memiter_elem *elem = (BLI_memiter_elem *)mi->data_curr;
+ elem->size = (offset_t)(((data_t *)mi->tail) - mi->data_curr);
+ BLI_assert(elem->size < 0);
+}
+
+static void memiter_init(BLI_memiter *mi)
+{
+ mi->head = NULL;
+ mi->tail = NULL;
+ mi->data_curr = NULL;
+ mi->data_last = NULL;
+ mi->count = 0;
+#ifdef USE_TOTALLOC
+ mi->totalloc = 0;
+#endif
+}
+
+/* -------------------------------------------------------------------- */
+
+/** \name Public API's
+ * \{ */
+
+/**
+ * \param chunk_size_min: Should be a power of two and
+ * significantly larger than the average element size used.
+ *
+ * While allocations of any size are supported, they won't be efficient
+ * (effectively becoming a single-linked list).
+ *
+ * Its intended that many elements can be stored per chunk.
+ */
+BLI_memiter *BLI_memiter_create(uint chunk_size_min)
+{
+ BLI_memiter *mi = MEM_mallocN(sizeof(BLI_memiter), STRINGIFY(BLI_memiter));
+ memiter_init(mi);
+
+ /* Small values are used for tests to check for correctness,
+ * but otherwise not that useful. */
+ const uint slop_space = (sizeof(BLI_memiter_chunk) + MEM_SIZE_OVERHEAD);
+ if (chunk_size_min >= 1024) {
+ /* As long as the input is a power of 2, this will give efficient sizes. */
+ chunk_size_min -= slop_space;
+ }
+
+ mi->chunk_size_in_bytes_min = (offset_t)chunk_size_min;
+ return mi;
+}
+
+void *BLI_memiter_alloc(BLI_memiter *mi, uint elem_size)
+{
+ const uint data_offset = data_offset_from_size(elem_size);
+ data_t *data_curr_next = mi->data_curr + (1 + data_offset);
+
+ if (UNLIKELY(mi->data_curr == NULL) || (data_curr_next > mi->data_last)) {
+
+#ifndef USE_TERMINATE_PARANOID
+ if (mi->data_curr != NULL) {
+ memiter_set_rewind_offset(mi);
+ }
+#endif
+
+ uint chunk_size_in_bytes = mi->chunk_size_in_bytes_min;
+ if (UNLIKELY(chunk_size_in_bytes < elem_size + (uint)sizeof(data_t[2]))) {
+ chunk_size_in_bytes = elem_size + (uint)sizeof(data_t[2]);
+ }
+ uint chunk_size = data_offset_from_size(chunk_size_in_bytes);
+ BLI_memiter_chunk *chunk = MEM_mallocN(
+ sizeof(BLI_memiter_chunk) +
+ (chunk_size * sizeof(data_t)),
+ STRINGIFY(BLI_memiter_chunk));
+
+ if (mi->head == NULL) {
+ BLI_assert(mi->tail == NULL);
+ mi->head = chunk;
+ }
+ else {
+ mi->tail->next = chunk;
+ }
+ mi->tail = chunk;
+ chunk->next = NULL;
+
+ mi->data_curr = chunk->data;
+ mi->data_last = chunk->data + (chunk_size - 1);
+ data_curr_next = mi->data_curr + (1 + data_offset);
+ }
+
+ BLI_assert(data_curr_next <= mi->data_last);
+
+ BLI_memiter_elem *elem = (BLI_memiter_elem *)mi->data_curr;
+ elem->size = elem_size;
+ mi->data_curr = data_curr_next;
+
+#ifdef USE_TERMINATE_PARANOID
+ memiter_set_rewind_offset(mi);
+#endif
+
+ mi->count += 1;
+
+#ifdef USE_TOTALLOC
+ mi->totalloc += elem_size;
+#endif
+
+ return elem->data;
+}
+
+void *BLI_memiter_calloc(BLI_memiter *mi, uint elem_size)
+{
+ void *data = BLI_memiter_alloc(mi, elem_size);
+ memset(data, 0, elem_size);
+ return data;
+}
+
+void BLI_memiter_alloc_from(BLI_memiter *mi, uint elem_size, const void *data_from)
+{
+ void *data = BLI_memiter_alloc(mi, elem_size);
+ memcpy(data, data_from, elem_size);
+}
+
+static void memiter_free_data(BLI_memiter *mi)
+{
+ BLI_memiter_chunk *chunk = mi->head;
+ while (chunk) {
+ BLI_memiter_chunk *chunk_next = chunk->next;
+ MEM_freeN(chunk);
+ chunk = chunk_next;
+ }
+}
+
+void BLI_memiter_destroy(BLI_memiter *mi)
+{
+ memiter_free_data(mi);
+ MEM_freeN(mi);
+}
+
+void BLI_memiter_clear(BLI_memiter *mi)
+{
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list