[Bf-blender-cvs] [dbf603c] particles_refactor: Better macros for low-level ultra fast access to paged buffers.
Lukas Tönne
noreply at git.blender.org
Tue Apr 22 12:05:08 CEST 2014
Commit: dbf603c48852c0f153d71701569d6eaeea2ae5ae
Author: Lukas Tönne
Date: Thu May 23 10:45:21 2013 +0200
https://developer.blender.org/rBdbf603c48852c0f153d71701569d6eaeea2ae5ae
Better macros for low-level ultra fast access to paged buffers.
===================================================================
M source/blender/blenlib/BLI_pagedbuffer.h
M source/blender/blenlib/intern/pagedbuffer.c
===================================================================
diff --git a/source/blender/blenlib/BLI_pagedbuffer.h b/source/blender/blenlib/BLI_pagedbuffer.h
index 050bd80..e9a96f6 100644
--- a/source/blender/blenlib/BLI_pagedbuffer.h
+++ b/source/blender/blenlib/BLI_pagedbuffer.h
@@ -30,6 +30,8 @@
* \brief Management and access functions for paged buffers.
*/
+#include <stdlib.h>
+
#include "BLI_utildefines.h"
#include "DNA_pagedbuffer_types.h"
@@ -41,19 +43,17 @@ struct bPagedBufferIterator;
struct bPagedBufferPage;
-typedef struct bPagedBufferIterator
-{
- int index;
- short valid;
-
- /* constants */
- int page_size;
- int index_end;
+typedef struct bPagedBufferLayerType {
+ int size; /* size in bytes of a single element */
+ int stride; /* space in bytes which an element takes in the buffer */
+} bPagedBufferLayerType;
+
+#define BLI_PBUF_DEF_LAYER_TYPE(ctype) \
+bPagedBufferLayerType BLI_pbuf_layer_type_#ctype = { sizeof(ctype), sizeof(ctype) };
+
+#define BLI_PBUF_DEF_LAYER_TYPE_ALIGNED(ctype, stride) \
+bPagedBufferLayerType BLI_pbuf_layer_type_#ctype = { sizeof(ctype), stride };
- /* internals */
- struct bPagedBufferPage *page;
- int page_index;
-} bPagedBufferIterator;
/* Buffer Management */
@@ -71,6 +71,20 @@ void BLI_pbuf_layer_remove(struct bPagedBuffer *pbuf, struct bPagedBufferLayerIn
/* Data Access */
+typedef struct bPagedBufferIterator
+{
+ int index;
+ bool valid;
+
+ /* constants */
+ int page_size;
+ int index_end;
+
+ /* internals */
+ struct bPagedBufferPage *page;
+ int page_index;
+} bPagedBufferIterator;
+
bPagedBufferIterator BLI_pbuf_set_elements(struct bPagedBuffer *pbuf, int totelem);
bPagedBufferIterator BLI_pbuf_append_elements(struct bPagedBuffer *pbuf, int num_elements);
@@ -84,22 +98,16 @@ void BLI_pbuf_reset(struct bPagedBuffer *pbuf);
void BLI_pbuf_free_dead_pages(struct bPagedBuffer *pbuf, bPagedBufferTestFunc removetestfunc, void *userdata);
void BLI_pbuf_compress(struct bPagedBuffer *pbuf, bPagedBufferTestFunc removetestfunc, void *userdata, struct bPagedBufferLayerInfo *origindex_layer);
-struct bPagedBufferIterator BLI_pbuf_get_element(struct bPagedBuffer *pbuf, int index);
+/* macros for fast, low-level access to raw data */
-/** 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 BLI_pbuf_binary_search_element(struct bPagedBuffer *pbuf, bPagedBufferSearchFunction testfunc, void *userdata, int start_index, int end_index);
+#define PBUF_GET_DATA_POINTER(result, page_ptr, layer, datatype, page_index) \
+ result = (page_ptr)->layers ? ((datatype)*)((page_ptr)->layers[(layer)]) + (page_index) : NULL
-#if 0
-/* access functions for point cache */
-void BLI_pbuf_cache_merge(struct bPagedBuffer *pbuf, int start, bPagedBufferCompareFunction cmpfunc);
-#endif
+#define PBUF_GET_ELEMENT(result, pbuf, layer, datatype, index) \
+{ \
+ div_t result_p = div(index, pbuf->page_size); \
+ PBUF_GET_DATA_POINTER(result, (pbuf)->pages + result_p.quot, (layer), (datatype), (index) - result_p.rem * (pbuf)->page_size) \
+}
/* XXX these could be inlined for performance */
struct bPagedBufferIterator pit_init(struct bPagedBuffer *pbuf);
@@ -112,14 +120,25 @@ 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);
+#define PBUF_ITER_GET_POINTER(result, iter, layer, datatype) \
+ PBUF_GET_DATA_POINTER(result, iter.page, layer, datatype, iter.page_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)
+/** 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 BLI_pbuf_binary_search_element(struct bPagedBuffer *pbuf, bPagedBufferSearchFunction testfunc, void *userdata, int start_index, int end_index);
-#define PBUF_GET_GENERIC_DATA_POINTER(iterator, datalayer) \
-(void*)((char*)((iterator)->page->layers[(datalayer)->layer]) + (iterator)->page_index * (datalayer)->stride)
+#if 0
+/* access functions for point cache */
+void BLI_pbuf_cache_merge(struct bPagedBuffer *pbuf, int start, bPagedBufferCompareFunction cmpfunc);
+#endif
+#if 0
/* access functions for common data types */
BLI_INLINE int pit_get_int(struct bPagedBufferIterator *it, struct bPagedBufferLayerInfo *layer)
{
@@ -138,5 +157,6 @@ BLI_INLINE void pit_set_float(struct bPagedBufferIterator *it, struct bPagedBuff
{
*PBUF_GET_DATA_POINTER(it, layer, float) = value;
}
+#endif
#endif
diff --git a/source/blender/blenlib/intern/pagedbuffer.c b/source/blender/blenlib/intern/pagedbuffer.c
index 8880614..791d834 100644
--- a/source/blender/blenlib/intern/pagedbuffer.c
+++ b/source/blender/blenlib/intern/pagedbuffer.c
@@ -604,171 +604,6 @@ void BLI_pbuf_compress(struct bPagedBuffer *pbuf, bPagedBufferTestFunc removetes
pbuf->totalloc = pbuf->totelem;
}
-/**** Data Access ****/
-
-bPagedBufferIterator BLI_pbuf_get_element(bPagedBuffer *pbuf, int index)
-{
- bPagedBufferIterator pit;
- int p = index / pbuf->page_size;
-
- pit.page_size = pbuf->page_size;
- pit.index_end = pbuf->totelem;
-
- pit.index = index;
- pit.page = pbuf->pages + p;
- pit.page_index = index - p * pbuf->page_size;
- pit.valid = (index < pbuf->totelem && pit.page->layers != NULL);
-
- return pit;
-}
-
-static void binary_search_page(bPagedBufferIterator *pit, bPagedBufferSearchFunction testfunc, void *userdata, int page_start, int start_index, int end_index)
-{
- int left= start_index, right= end_index, mid;
- int result;
- while (left <= right) {
- pit->page_index = mid = (left + right) >> 1;
- pit->index = page_start + mid;
- result = testfunc(pit, userdata);
- if (result == 0) {
- pit->valid = 1;
- return;
- }
- else if (result < 0) {
- right = mid-1;
- }
- else { /* result > 0 */
- left = mid+1;
- }
- }
- /* element not found */
- pit->valid = 0;
-}
-
-bPagedBufferIterator BLI_pbuf_binary_search_element(bPagedBuffer *pbuf, bPagedBufferSearchFunction testfunc, void *userdata, int start_index, int end_index)
-{
- bPagedBufferIterator pit;
- int p, mid_p, start_p, end_p;
- int result;
- int page_size= pbuf->page_size;
- int search_start, search_end;
-
- /* optimized binary search for paged buffers:
- * - first do a binary search on the page ranges by testing first and last elements on pages.
- * - when the page containing the element is found, do a binary search inside that page.
- */
-
- pit.page_size = pbuf->page_size;
- pit.index_end = pbuf->totelem;
-
- if (start_index >= end_index) {
- pit.valid = 0;
- return pit;
- }
-
- start_p = (int)(start_index / page_size);
- end_p = (int)((end_index + page_size-1) / page_size); /* rounding up */
- do {
- mid_p = (start_p + end_p) >> 1;
-
- /* find page less-or-equal mid_p that has data */
- for (p=mid_p, pit.page=pbuf->pages+mid_p; p >= start_p; --p, --pit.page)
- if (pit.page->layers)
- break;
- if (p >= start_p) {
- /* check the first element of page p */
- pit.page_index = 0;
- pit.index = p*page_size;
- if (pit.index < start_index) {
- pit.page_index += start_index - pit.index;
- pit.index = start_index;
- }
- search_start = pit.page_index+1; /* page index search range for actual binary search */
-
- result = testfunc(&pit, userdata);
- if (result == 0) {
- pit.valid = 1;
- return pit;
- }
- else if (result < 0) {
- /* continue checking pages left of p */
- end_p = p-1;
- continue;
- }
- /* result > 0, check the last element of page p */
- pit.page_index = page_size-1;
- pit.index = (p+1)*page_size-1;
- if (pit.index >= end_index) {
- pit.page_index -= pit.index - (end_index-1);
- pit.index = end_index-1;
- }
- search_end = pit.page_index-1; /* page index search range for actual binary search */
-
- result = testfunc(&pit, userdata);
- if (result == 0) {
- pit.valid = 1;
- return pit;
- }
- else if (result < 0) {
- /* element must be on page p (excluding first and last element, we already tested those) */
- binary_search_page(&pit, testfunc, userdata, p*page_size, search_start, search_end);
- return pit;
- }
- }
- /* still here? means element must be greater than mid_p's last */
- /* find page greather than mid_p that has data */
- for (p=mid_p+1, pit.page=pbuf->pages+mid_p+1; p < end_p; ++p, ++pit.page)
- if (pit.page->layers)
- break;
- if (p < end_p) {
- /* check the last element of page p */
- pit.page_index = page_size-1;
- pit.index = (p+1)*page_size-1;
- if (pit.index >= end_index) {
- pit.page_index -= pit.index - (end_index-1);
- pit.index = end_index-1;
- }
- search_end = pit.page_index-1; /* page index search range for actual binary search */
-
- result = testfunc(&pit, userdata);
- if (result == 0) {
- pit.valid = 1;
- return pit;
- }
- else if (result > 0) {
- /* continue checking pages right of p */
- start_p = p+1;
- continue;
- }
- /* result < 0, check the first element of page p */
- pit.page_index = 0;
- pit.index = p*page_size;
- if (pit.index < start_index) {
- pit.page_index += start_index - pit.index;
- pit.index = start_index;
- }
- search_start = pit.page_index+1; /* page index search range for actual binary search */
-
- result = testfunc(&pit, userdata);
- if (resu
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list