[Bf-blender-cvs] [69692fd] particles_refactor: Original paged buffer implementation.

[Lukas Tönne]

Commit: 69692fdb0f665515f028296f3697004458e01351
Author: Lukas Tönne
Date:   Wed May 22 11:13:17 2013 +0200
https://developer.blender.org/rB69692fdb0f665515f028296f3697004458e01351

Original paged buffer implementation.

===================================================================

M	source/blender/CMakeLists.txt
A	source/blender/blenlib/BLI_pagedbuffer.h
M	source/blender/blenlib/CMakeLists.txt
A	source/blender/blenlib/intern/pagedbuffer.c
A	source/blender/makesdna/DNA_pagedbuffer_types.h

===================================================================

diff --git a/source/blender/CMakeLists.txt b/source/blender/CMakeLists.txt
index 0d30952..3892996 100644
--- a/source/blender/CMakeLists.txt
+++ b/source/blender/CMakeLists.txt
@@ -65,6 +65,7 @@ set(SRC_DNA_INC
 	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_object_force.h
 	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_object_types.h
 	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_outliner_types.h
+	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_pagedbuffer_types.h
 	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_packedFile_types.h
 	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_particle_types.h
 	${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_property_types.h
diff --git a/source/blender/blenlib/BLI_pagedbuffer.h b/source/blender/blenlib/BLI_pagedbuffer.h
new file mode 100644
index 0000000..4bc041e
--- /dev/null
+++ b/source/blender/blenlib/BLI_pagedbuffer.h
@@ -0,0 +1,142 @@
+/*
+ * ***** 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.
+ *
+ * Copyright 2011, Blender Foundation.
+ *
+ * Contributor(s): Lukas Toenne
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef BLI_PAGEDBUFFER_H
+#define BLI_PAGEDBUFFER_H
+
+/** \file BLI_pbuffer.h
+ *  \ingroup bli
+ *  \brief Management and access functions for paged buffers.
+ */
+
+#include "BLI_utildefines.h"
+
+#include "DNA_pagedbuffer_types.h"
+
+
+struct bPagedBuffer;
+struct bPagedBufferLayerInfo;
+struct bPagedBufferIterator;
+struct bPagedBufferPage;
+
+
+typedef struct bPagedBufferIterator
+{
+	int index;
+	short valid;
+	
+	/* constants */
+	int page_size;
+	int index_end;
+
+	/* internals */
+	struct bPagedBufferPage *page;
+	int page_index;
+} bPagedBufferIterator;
+
+
+/* Buffer Management */
+
+void pbufInit(struct bPagedBuffer *pbuf, int page_size);
+void pbufFree(struct bPagedBuffer *pbuf);
+void pbufCopy(struct bPagedBuffer *to, struct bPagedBuffer *from);
+
+void pbufSetPageSize(struct bPagedBuffer *pbuf, int new_page_size);
+
+/* Layers */
+
+struct bPagedBufferLayerInfo *pbufLayerAdd(struct bPagedBuffer *pbuf, const char *name, int stride, const void *default_value);
+void pbufLayerRemove(struct bPagedBuffer *pbuf, struct bPagedBufferLayerInfo *layer);
+
+
+/* Data Access */
+bPagedBufferIterator pbufSetElements(struct bPagedBuffer *pbuf, int totelem);
+bPagedBufferIterator pbufAppendElements(struct bPagedBuffer *pbuf, int num_elements);
+
+typedef int (*bPagedBufferTestFunc)(struct bPagedBufferIterator *pit, void *userdata);
+/* must return -1 if the searched element has lower index than the iterator, 1 if it has higher index and 0 if it is found. */
+typedef int (*bPagedBufferSearchFunction)(struct bPagedBufferIterator *pit, void *userdata);
+/* must return 1 if a comes before b */
+typedef int (*bPagedBufferCompareFunction)(struct bPagedBufferIterator *a, struct bPagedBufferIterator *b);
+
+void pbufReset(struct bPagedBuffer *pbuf);
+void pbufFreeDeadPages(struct bPagedBuffer *pbuf, bPagedBufferTestFunc removetestfunc, void *userdata);
+void pbufCompress(struct bPagedBuffer *pbuf, bPagedBufferTestFunc removetestfunc, void *userdata, struct bPagedBufferLayerInfo *origindex_layer);
+
+struct bPagedBufferIterator pbufGetElement(struct bPagedBuffer *pbuf, int index);
+
+/** Find an element using binary search
+ * If a (partial) ordering is defined on the elements, this function can be used
+ * to find an element using efficient binary search.
+ * \param test The binary test function defining the ordering.
+ * \param data Custom information to pass to the test function.
+ * \param start_index Lower bound for the search space (index >= start_index).
+ * \param end_index Upper bound for the search space (index < end_index).
+ */
+struct bPagedBufferIterator pbufBinarySearchElement(struct bPagedBuffer *pbuf, bPagedBufferSearchFunction testfunc, void *userdata, int start_index, int end_index);
+
+#if 0
+/* access functions for point cache */
+void pbufCacheMerge(struct bPagedBuffer *pbuf, int start, bPagedBufferCompareFunction cmpfunc);
+#endif
+
+/* XXX these could be inlined for performance */
+struct bPagedBufferIterator pit_init(struct bPagedBuffer *pbuf);
+struct bPagedBufferIterator pit_init_at(struct bPagedBuffer *pbuf, int index);
+void pit_next(struct bPagedBufferIterator *it);
+void pit_prev(struct bPagedBufferIterator *it);
+void pit_forward(struct bPagedBufferIterator *it, int delta);
+void pit_backward(struct bPagedBufferIterator *it, int delta);
+void pit_forward_to(struct bPagedBufferIterator *it, int index);
+void pit_backward_to(struct bPagedBufferIterator *it, int index);
+void pit_goto(struct bPagedBufferIterator *it, int index);
+
+
+/* macro for fast, low-level access to raw data */
+#define PBUF_GET_DATA_POINTER(iterator, datalayer, datatype) \
+((datatype*)((iterator)->page->layers[(datalayer)->layer]) + (iterator)->page_index)
+
+#define PBUF_GET_GENERIC_DATA_POINTER(iterator, datalayer) \
+(void*)((char*)((iterator)->page->layers[(datalayer)->layer]) + (iterator)->page_index * (datalayer)->stride)
+
+/* access functions for common data types */
+BLI_INLINE int pit_get_int(struct bPagedBufferIterator *it, struct bPagedBufferLayerInfo *layer)
+{
+	return *PBUF_GET_DATA_POINTER(it, layer, int);
+}
+BLI_INLINE void pit_set_int(struct bPagedBufferIterator *it, struct bPagedBufferLayerInfo *layer, int value)
+{
+	*PBUF_GET_DATA_POINTER(it, layer, int) = value;
+}
+
+BLI_INLINE int pit_get_float(struct bPagedBufferIterator *it, struct bPagedBufferLayerInfo *layer)
+{
+	return *PBUF_GET_DATA_POINTER(it, layer, float);
+}
+BLI_INLINE void pit_set_float(struct bPagedBufferIterator *it, struct bPagedBufferLayerInfo *layer, float value)
+{
+	*PBUF_GET_DATA_POINTER(it, layer, float) = value;
+}
+
+#endif
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 491f988..df6146c 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -82,6 +82,7 @@ set(SRC
 	intern/math_vector_inline.c
 	intern/md5.c
 	intern/noise.c
+	intern/pagedbuffer.c
 	intern/path_util.c
 	intern/polyfill2d.c
 	intern/quadric.c
@@ -153,6 +154,7 @@ set(SRC
 	BLI_memarena.h
 	BLI_mempool.h
 	BLI_noise.h
+	BLI_pagedbuffer.h
 	BLI_path_util.h
 	BLI_polyfill2d.h
 	BLI_quadric.h
diff --git a/source/blender/blenlib/intern/pagedbuffer.c b/source/blender/blenlib/intern/pagedbuffer.c
new file mode 100644
index 0000000..371fbf8
--- /dev/null
+++ b/source/blender/blenlib/intern/pagedbuffer.c
@@ -0,0 +1,956 @@
+/*
+ * ***** 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.
+ *
+ * Copyright 2011, Blender Foundation.
+ *
+ * Contributor(s): Lukas Toenne
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <assert.h>
+
+#include "MEM_guardedalloc.h"
+#include "memory.h"
+
+#include "DNA_pagedbuffer_types.h"
+
+#include "BLI_listbase.h"
+#include "BLI_pagedbuffer.h"
+#include "BLI_string.h"
+#include "BLI_utildefines.h"
+
+
+/************************************************/
+/*				Buffer Management				*/
+/************************************************/
+
+static void set_default_data(void *data, int totdata, bPagedBufferLayerInfo *layer)
+{
+	int i;
+	/* set default values */
+	for (i=0; i < totdata; ++i)
+		memcpy((char*)data + i*layer->stride, layer->default_value, layer->stride);
+}
+
+static void *make_page_layer(int page_size, bPagedBufferLayerInfo *layer)
+{
+	void *data= MEM_callocN(page_size * layer->stride, "bPagedBufferPage layer");
+	set_default_data(data, page_size, layer);
+	return data;
+}
+
+static void init_page(bPagedBuffer *pbuf, bPagedBufferPage *page, int page_size)
+{
+	bPagedBufferLayerInfo *layer;
+	
+	page->layers= MEM_callocN(pbuf->totlayers*sizeof(void*), "bPagedBufferPage layers");
+	for (layer=pbuf->layers.first; layer; layer=layer->next)
+		page->layers[layer->layer] = make_page_layer(page_size, layer);
+}
+
+static void free_page(bPagedBuffer *pbuf, bPagedBufferPage *page)
+{
+	if (page->layers) {
+		int i;
+		for (i=0; i < pbuf->totlayers; ++i)
+			MEM_freeN(page->layers[i]);
+		MEM_freeN(page->layers);
+		page->layers = NULL;
+	}
+}
+
+static void free_all_pages(bPagedBuffer *pbuf)
+{
+	bPagedBufferPage *page;
+	int p;
+	
+	for (p=0, page=pbuf->pages; p < pbuf->totpages; ++p, ++page)
+		free_page(pbuf, page);
+}
+
+
+static bPagedBufferLayerInfo *copy_layer_info(bPagedBufferLayerInfo *layer)
+{
+	bPagedBufferLayerInfo *nlayer = MEM_dupallocN(layer);
+	nlayer->next = nlayer->prev = NULL;
+	
+	nlayer->default_value = MEM_dupallocN(layer->default_value);
+	
+	/* temporary copy pointer for easy mapping */
+	layer->new_layer = nlayer;
+	
+	return nlayer;
+}
+
+static void free_layer_info(bPagedBufferLayerInfo *layer)
+{
+	MEM_freeN(layer->default_value);
+}
+
+/* Generic update function for layer indices.
+ * Note: This could be optimized slightly for each use case,
+ * but not necessary as layer changes are not performance critic

@@ Diff output truncated at 10240 characters. @@