diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-05-02 11:01:00 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-05-02 11:49:22 +0300 |
commit | 915e9eeff12eb0f0e0fc01927fecc876a0cdfdbe (patch) | |
tree | fec10c10aadeaaf1300fe00aa84171e9d9325b8c /source/blender/blenlib | |
parent | c1ca667d4a9f42cda9dd7486f9826db07baacd2a (diff) |
BLI_array_utils: helper for stepping over contiguous ranges
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_array_utils.h | 12 | ||||
-rw-r--r-- | source/blender/blenlib/intern/array_utils.c | 118 |
2 files changed, 129 insertions, 1 deletions
diff --git a/source/blender/blenlib/BLI_array_utils.h b/source/blender/blenlib/BLI_array_utils.h index c5359d56f9c..5ef8421c003 100644 --- a/source/blender/blenlib/BLI_array_utils.h +++ b/source/blender/blenlib/BLI_array_utils.h @@ -64,4 +64,16 @@ void _bli_array_binary_or( CHECK_TYPE_PAIR_INLINE(*(arr), *(arr_b)), \ _bli_array_binary_or(arr, arr_a, arr_b, arr_len, sizeof(*(arr)))) +bool _bli_array_iter_span( + const void *arr, + unsigned int arr_len, size_t arr_stride, + bool use_wrap, bool use_delimit_bounds, + bool (*test_fn)(const void *arr_item, void *user_data), void *user_data, + unsigned int span_step[2], unsigned int *r_span_len); +#define BLI_array_iter_span(arr, arr_len, use_wrap, use_delimit_bounds, test_fn, user_data, \ + span_step, r_span_len) \ + _bli_array_iter_span( \ + arr, arr_len, sizeof(*(arr)), use_wrap, use_delimit_bounds, test_fn, user_data, \ + span_step, r_span_len) + #endif /* __BLI_ARRAY_UTILS_H__ */ diff --git a/source/blender/blenlib/intern/array_utils.c b/source/blender/blenlib/intern/array_utils.c index 52ca835876e..cbc9b49075f 100644 --- a/source/blender/blenlib/intern/array_utils.c +++ b/source/blender/blenlib/intern/array_utils.c @@ -169,4 +169,120 @@ void _bli_array_binary_or( while (i--) { *(dst++) = *(src_a++) | *(src_b++); } -}
\ No newline at end of file +} + +/** + * Utility function to iterate over contiguous items in an array. + * + * \param use_wrap: Detect contiguous ranges across the first/last points. + * In this case the second index of \a span_step may be lower than the first, + * which indicates the values are wrapped. + * \param use_delimit_bounds: When false, ranges that defined by the start/end indices are excluded. + * This option has no effect when \a use_wrap is enabled. + * \param test_fn: Function to test if the item should be included in the range. + * \param user_data: User data for \a test_fn. + * \param span_step: Indices to iterate over, + * initialize both values to the array length to initialize iteration. + * \param: r_span_len: The length of the span, useful when \a use_wrap is enabled, + * where calculating the length isnt a simple subtraction. + */ +bool _bli_array_iter_span( + const void *arr, + unsigned int arr_len, size_t arr_stride, + bool use_wrap, bool use_delimit_bounds, + bool (*test_fn)(const void *arr_item, void *user_data), void *user_data, + unsigned int span_step[2], unsigned int *r_span_len) +{ + if (arr_len == 0) { + return false; + } + + const unsigned int arr_stride_uint = (unsigned int)arr_stride; + const void *item_prev; + bool test_prev; + + unsigned int i_curr; + + if ((span_step[0] == arr_len) && (span_step[1] == arr_len)) { + if (use_wrap) { + item_prev = POINTER_OFFSET(arr, (arr_len - 1) * arr_stride_uint); + i_curr = 0; + test_prev = test_fn(item_prev, user_data); + } + else if (use_delimit_bounds == false) { + item_prev = arr; + i_curr = 1; + test_prev = test_fn(item_prev, user_data); + } + else { + item_prev = NULL; + i_curr = 0; + test_prev = false; + } + } + else if ((i_curr = span_step[1] + 2) < arr_len) { + item_prev = POINTER_OFFSET(arr, (span_step[1] + 1) * arr_stride_uint); + test_prev = test_fn(item_prev, user_data); + } + else { + return false; + } + BLI_assert(i_curr < arr_len); + + const void *item_curr = POINTER_OFFSET(arr, i_curr * arr_stride_uint); + + while (i_curr < arr_len) { + bool test_curr = test_fn(item_curr, user_data); + if ((test_prev == false) && + (test_curr == true)) + { + unsigned int span_len; + unsigned int i_step_prev = i_curr; + + if (use_wrap) { + unsigned int i_step = i_curr + 1; + if (UNLIKELY(i_step == arr_len)) { + i_step = 0; + } + while (test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) { + i_step_prev = i_step; + i_step++; + if (UNLIKELY(i_step == arr_len)) { + i_step = 0; + } + } + + span_len = (i_step_prev - ((i_step_prev >= i_curr) ? i_curr : (i_curr + arr_len))) + 1; + } + else { + unsigned int i_step = i_curr + 1; + while ((i_step != arr_len) && + test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) + { + i_step_prev = i_step; + i_step++; + } + + span_len = (i_step_prev - i_curr) + 1; + + if ((use_delimit_bounds == false) && (i_step_prev == arr_len - 1)) { + return false; + } + } + + span_step[0] = i_curr; + span_step[1] = i_step_prev; + *r_span_len = span_len; + + return true; + } + + test_prev = test_curr; + + item_prev = item_curr; + item_curr = POINTER_OFFSET(item_curr, arr_stride_uint); + i_curr++; + } + + return false; +} |