diff options
Diffstat (limited to 'source/blender/blenlib')
72 files changed, 2610 insertions, 823 deletions
diff --git a/source/blender/blenlib/BLI_array_utils.h b/source/blender/blenlib/BLI_array_utils.h index 0dd1439e58c..ff7976dc701 100644 --- a/source/blender/blenlib/BLI_array_utils.h +++ b/source/blender/blenlib/BLI_array_utils.h @@ -34,6 +34,14 @@ void _bli_array_wrap(void *arr, unsigned int arr_len, size_t arr_stride, int dir #define BLI_array_wrap(arr, arr_len, dir) \ _bli_array_wrap(arr, arr_len, sizeof(*(arr)), dir) +void _bli_array_permute( + void *arr, const unsigned int arr_len, const size_t arr_stride, + const unsigned int *index, void *arr_temp); +#define BLI_array_permute(arr, arr_len, order) \ + _bli_array_permute(arr, arr_len, sizeof(*(arr)), order, NULL) +#define BLI_array_permute_ex(arr, arr_len, index, arr_temp) \ + _bli_array_permute(arr, arr_len, sizeof(*(arr)), order, arr_temp) + int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p); #define BLI_array_findindex(arr, arr_len, p) \ _bli_array_findindex(arr, arr_len, sizeof(*(arr)), p) diff --git a/source/blender/blenlib/BLI_astar.h b/source/blender/blenlib/BLI_astar.h index b99a2534d33..5e9434a1d56 100644 --- a/source/blender/blenlib/BLI_astar.h +++ b/source/blender/blenlib/BLI_astar.h @@ -86,6 +86,15 @@ void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_sol void BLI_astar_solution_clear(BLI_AStarSolution *as_solution); void BLI_astar_solution_free(BLI_AStarSolution *as_solution); +/** + * Callback computing the current cost (distance) to next node, and the estimated overall cost to destination node + * (A* expects this estimation to always be less or equal than actual shortest path from next node to destination one). + * + * \param link the graph link between current node and next one. + * \param node_idx_curr current node index. + * \param node_idx_next next node index. + * \param node_idx_dst destination node index. + */ typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link, const int node_idx_curr, const int node_idx_next, const int node_idx_dst); diff --git a/source/blender/blenlib/BLI_blenlib.h b/source/blender/blenlib/BLI_blenlib.h index 03b75975af4..06bbf29a223 100644 --- a/source/blender/blenlib/BLI_blenlib.h +++ b/source/blender/blenlib/BLI_blenlib.h @@ -58,7 +58,6 @@ #ifndef __BLI_BLENLIB_H__ #define __BLI_BLENLIB_H__ -struct ListBase; #include <stdlib.h> diff --git a/source/blender/blenlib/BLI_callbacks.h b/source/blender/blenlib/BLI_callbacks.h index 7cf524749c2..fdffbeb4c8d 100644 --- a/source/blender/blenlib/BLI_callbacks.h +++ b/source/blender/blenlib/BLI_callbacks.h @@ -25,7 +25,6 @@ #ifndef __BLI_CALLBACKS_H__ #define __BLI_CALLBACKS_H__ -struct bContext; struct Main; struct ID; diff --git a/source/blender/blenlib/BLI_compiler_compat.h b/source/blender/blenlib/BLI_compiler_compat.h index 876d2c459c5..92928889c52 100644 --- a/source/blender/blenlib/BLI_compiler_compat.h +++ b/source/blender/blenlib/BLI_compiler_compat.h @@ -37,7 +37,7 @@ # include <malloc.h> #endif -#if defined(__cplusplus) && ((__cplusplus >= 201103L) || (defined(_MSC_VER) && _MSC_VER >= 1800)) +#if defined(__cplusplus) && ((__cplusplus >= 201103L) || defined(_MSC_VER)) # define HAS_CPP11_FEATURES #endif diff --git a/source/blender/blenlib/BLI_compiler_typecheck.h b/source/blender/blenlib/BLI_compiler_typecheck.h index 652c4a954b9..b9fb3ebf47a 100644 --- a/source/blender/blenlib/BLI_compiler_typecheck.h +++ b/source/blender/blenlib/BLI_compiler_typecheck.h @@ -381,4 +381,303 @@ # define CHECK_TYPE_ANY(...) (void)0 #endif + +/** + * GENERIC_TYPE_ANY: handy macro to reuse a single expression for multiple types, eg: + * + * \code{.c} + * _Generic(value, + * GENERIC_TYPE_ANY(result_a, Foo *, Bar *, Baz *), + * GENERIC_TYPE_ANY(result_b, Spam *, Spaz *, Spot *), + * ) + * \endcode + * + * excuse ridiculously long generated args. + * \code{.py} + * for i in range(63): + * args = [(chr(ord('a') + (c % 26)) + (chr(ord('0') + (c // 26)))) for c in range(i + 1)] + * print("#define _VA_GENERIC_TYPE_ANY%d(r, %s) \\" % (i + 2, ", ".join(args))) + * print(" %s: r " % (": r, ".join(args))) + * \endcode + */ +#define _VA_GENERIC_TYPE_ANY2(r, a0) \ + a0: r +#define _VA_GENERIC_TYPE_ANY3(r, a0, b0) \ + a0: r, b0: r +#define _VA_GENERIC_TYPE_ANY4(r, a0, b0, c0) \ + a0: r, b0: r, c0: r +#define _VA_GENERIC_TYPE_ANY5(r, a0, b0, c0, d0) \ + a0: r, b0: r, c0: r, d0: r +#define _VA_GENERIC_TYPE_ANY6(r, a0, b0, c0, d0, e0) \ + a0: r, b0: r, c0: r, d0: r, e0: r +#define _VA_GENERIC_TYPE_ANY7(r, a0, b0, c0, d0, e0, f0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r +#define _VA_GENERIC_TYPE_ANY8(r, a0, b0, c0, d0, e0, f0, g0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r +#define _VA_GENERIC_TYPE_ANY9(r, a0, b0, c0, d0, e0, f0, g0, h0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r +#define _VA_GENERIC_TYPE_ANY10(r, a0, b0, c0, d0, e0, f0, g0, h0, i0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r +#define _VA_GENERIC_TYPE_ANY11(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r +#define _VA_GENERIC_TYPE_ANY12(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r +#define _VA_GENERIC_TYPE_ANY13(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r +#define _VA_GENERIC_TYPE_ANY14(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r +#define _VA_GENERIC_TYPE_ANY15(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r +#define _VA_GENERIC_TYPE_ANY16(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r +#define _VA_GENERIC_TYPE_ANY17(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r +#define _VA_GENERIC_TYPE_ANY18(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r +#define _VA_GENERIC_TYPE_ANY19(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r +#define _VA_GENERIC_TYPE_ANY20(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r +#define _VA_GENERIC_TYPE_ANY21(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r +#define _VA_GENERIC_TYPE_ANY22(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r +#define _VA_GENERIC_TYPE_ANY23(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r +#define _VA_GENERIC_TYPE_ANY24(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r +#define _VA_GENERIC_TYPE_ANY25(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r +#define _VA_GENERIC_TYPE_ANY26(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r +#define _VA_GENERIC_TYPE_ANY27(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r +#define _VA_GENERIC_TYPE_ANY28(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r +#define _VA_GENERIC_TYPE_ANY29(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r +#define _VA_GENERIC_TYPE_ANY30(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r +#define _VA_GENERIC_TYPE_ANY31(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r +#define _VA_GENERIC_TYPE_ANY32(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r +#define _VA_GENERIC_TYPE_ANY33(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r +#define _VA_GENERIC_TYPE_ANY34(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r +#define _VA_GENERIC_TYPE_ANY35(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r +#define _VA_GENERIC_TYPE_ANY36(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r +#define _VA_GENERIC_TYPE_ANY37(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r +#define _VA_GENERIC_TYPE_ANY38(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r +#define _VA_GENERIC_TYPE_ANY39(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r +#define _VA_GENERIC_TYPE_ANY40(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r +#define _VA_GENERIC_TYPE_ANY41(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r +#define _VA_GENERIC_TYPE_ANY42(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r +#define _VA_GENERIC_TYPE_ANY43(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r +#define _VA_GENERIC_TYPE_ANY44(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r +#define _VA_GENERIC_TYPE_ANY45(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r +#define _VA_GENERIC_TYPE_ANY46(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r +#define _VA_GENERIC_TYPE_ANY47(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r +#define _VA_GENERIC_TYPE_ANY48(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r +#define _VA_GENERIC_TYPE_ANY49(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r +#define _VA_GENERIC_TYPE_ANY50(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r +#define _VA_GENERIC_TYPE_ANY51(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r +#define _VA_GENERIC_TYPE_ANY52(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r +#define _VA_GENERIC_TYPE_ANY53(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r +#define _VA_GENERIC_TYPE_ANY54(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r +#define _VA_GENERIC_TYPE_ANY55(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r +#define _VA_GENERIC_TYPE_ANY56(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r +#define _VA_GENERIC_TYPE_ANY57(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r +#define _VA_GENERIC_TYPE_ANY58(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r +#define _VA_GENERIC_TYPE_ANY59(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2, f2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r, f2: r +#define _VA_GENERIC_TYPE_ANY60(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2, f2, g2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r, f2: r, g2: r +#define _VA_GENERIC_TYPE_ANY61(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2, f2, g2, h2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r, f2: r, g2: r, h2: r +#define _VA_GENERIC_TYPE_ANY62(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2, f2, g2, h2, i2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r, f2: r, g2: r, h2: r, i2: r +#define _VA_GENERIC_TYPE_ANY63(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2, f2, g2, h2, i2, j2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r, f2: r, g2: r, h2: r, i2: r, j2: r +#define _VA_GENERIC_TYPE_ANY64(r, a0, b0, c0, d0, e0, f0, g0, h0, i0, j0, k0, l0, m0, n0, o0, p0, q0, r0, s0, t0, \ + u0, v0, w0, x0, y0, z0, a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1, p1, q1, r1, s1, t1, u1, v1, \ + w1, x1, y1, z1, a2, b2, c2, d2, e2, f2, g2, h2, i2, j2, k2) \ + a0: r, b0: r, c0: r, d0: r, e0: r, f0: r, g0: r, h0: r, i0: r, j0: r, k0: r, l0: r, m0: r, n0: r, o0: r, p0: r, \ + q0: r, r0: r, s0: r, t0: r, u0: r, v0: r, w0: r, x0: r, y0: r, z0: r, a1: r, b1: r, c1: r, d1: r, e1: r, f1: r, \ + g1: r, h1: r, i1: r, j1: r, k1: r, l1: r, m1: r, n1: r, o1: r, p1: r, q1: r, r1: r, s1: r, t1: r, u1: r, v1: r, \ + w1: r, x1: r, y1: r, z1: r, a2: r, b2: r, c2: r, d2: r, e2: r, f2: r, g2: r, h2: r, i2: r, j2: r, k2: r + +# define GENERIC_TYPE_ANY(...) VA_NARGS_CALL_OVERLOAD(_VA_GENERIC_TYPE_ANY, __VA_ARGS__) + #endif /* __BLI_COMPILER_TYPECHECK_H__ */ diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index ded4b163f71..20272dd97cd 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -54,6 +54,7 @@ bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned in void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val_default) ATTR_WARN_UNUSED_RESULT; void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; +bool BLI_edgehash_ensure_p(EdgeHash *eh, unsigned int v0, unsigned int v1, void ***r_val) ATTR_WARN_UNUSED_RESULT; bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp); void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/blenlib/BLI_fileops.h b/source/blender/blenlib/BLI_fileops.h index 7898a54002f..01aa5d39b96 100644 --- a/source/blender/blenlib/BLI_fileops.h +++ b/source/blender/blenlib/BLI_fileops.h @@ -51,7 +51,6 @@ extern "C" { # define PATH_MAX 4096 #endif -struct gzFile; /* Common */ diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index d1195d4cba7..b1864665e76 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -45,8 +45,8 @@ typedef unsigned int (*GHashHashFP) (const void *key); typedef bool (*GHashCmpFP) (const void *a, const void *b); typedef void (*GHashKeyFreeFP) (void *key); typedef void (*GHashValFreeFP) (void *val); -typedef void *(*GHashKeyCopyFP) (void *key); -typedef void *(*GHashValCopyFP) (void *val); +typedef void *(*GHashKeyCopyFP) (const void *key); +typedef void *(*GHashValCopyFP) (const void *val); typedef struct GHash GHash; @@ -80,13 +80,15 @@ bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfre void *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT; void **BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; -bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT; +bool BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_val, GHashKeyCopyFP keycopyfp) ATTR_WARN_UNUSED_RESULT; +bool BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const unsigned int nentries_reserve); -void *BLI_ghash_popkey(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT; +void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT; bool BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; -int BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT; +unsigned int BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT; void BLI_ghash_flag_set(GHash *gh, unsigned int flag); void BLI_ghash_flag_clear(GHash *gh, unsigned int flag); @@ -153,6 +155,7 @@ bool BLI_ghashutil_strcmp(const void *a, const void *b); unsigned int BLI_ghashutil_uinthash(unsigned int key); unsigned int BLI_ghashutil_inthash_p(const void *ptr); unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr); +unsigned int BLI_ghashutil_inthash_p_simple(const void *ptr); bool BLI_ghashutil_intcmp(const void *a, const void *b); @@ -224,7 +227,7 @@ GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; GSet *BLI_gset_copy(GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; -int BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT; +unsigned int BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT; void BLI_gset_flag_set(GSet *gs, unsigned int flag); void BLI_gset_flag_clear(GSet *gs, unsigned int flag); void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp); @@ -232,7 +235,7 @@ void BLI_gset_insert(GSet *gh, void *key); bool BLI_gset_add(GSet *gs, void *key); bool BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp); bool BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; -bool BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp); +bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp); void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const unsigned int nentries_reserve); void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp); diff --git a/source/blender/blenlib/BLI_linklist.h b/source/blender/blenlib/BLI_linklist.h index 8dbf7b4a908..67cb30e8d17 100644 --- a/source/blender/blenlib/BLI_linklist.h +++ b/source/blender/blenlib/BLI_linklist.h @@ -35,45 +35,59 @@ * */ +#include "BLI_compiler_attrs.h" + struct MemArena; struct BLI_mempool; typedef void (*LinkNodeFreeFP)(void *link); typedef void (*LinkNodeApplyFP)(void *link, void *userdata); -struct LinkNode; typedef struct LinkNode { struct LinkNode *next; void *link; } LinkNode; -int BLI_linklist_length(struct LinkNode *list); -int BLI_linklist_index(struct LinkNode *list, void *ptr); +/** + * Use for append (single linked list, storing the last element). + * + * \note list manipulation functions don't operate on this struct. + * This is only to be used while appending. + */ +typedef struct LinkNodePair { + LinkNode *list, *last_node; +} LinkNodePair; + +int BLI_linklist_count(LinkNode *list) ATTR_WARN_UNUSED_RESULT; +int BLI_linklist_index(LinkNode *list, void *ptr) ATTR_WARN_UNUSED_RESULT; -struct LinkNode *BLI_linklist_find(struct LinkNode *list, int index); +LinkNode *BLI_linklist_find(LinkNode *list, int index) ATTR_WARN_UNUSED_RESULT; -void BLI_linklist_reverse(struct LinkNode **listp); +void BLI_linklist_reverse(LinkNode **listp) ATTR_NONNULL(1); -void BLI_linklist_move_item(struct LinkNode **listp, int curr_index, int new_index); +void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index) ATTR_NONNULL(1); -void BLI_linklist_prepend_nlink(struct LinkNode **listp, void *ptr, struct LinkNode *nlink); -void BLI_linklist_prepend(struct LinkNode **listp, void *ptr); -void BLI_linklist_prepend_arena(struct LinkNode **listp, void *ptr, struct MemArena *ma); -void BLI_linklist_prepend_pool(struct LinkNode **listp, void *ptr, struct BLI_mempool *mempool); +void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) ATTR_NONNULL(1, 3); +void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1); +void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1, 3); +void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1, 3); -void BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink); -void BLI_linklist_append(struct LinkNode **listp, void *ptr); -void BLI_linklist_append_arena(LinkNode **listp, void *ptr, struct MemArena *ma); -void BLI_linklist_append_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool); +/* use LinkNodePair to avoid full search */ +void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink) ATTR_NONNULL(1, 3); +void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) ATTR_NONNULL(1); +void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, struct MemArena *ma) ATTR_NONNULL(1, 3); +void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1, 3); -void *BLI_linklist_pop(struct LinkNode **listp); -void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool); -void BLI_linklist_insert_after(struct LinkNode **listp, void *ptr); +void *BLI_linklist_pop(LinkNode **listp) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +void *BLI_linklist_pop_pool(LinkNode **listp, struct BLI_mempool *mempool) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2); +void BLI_linklist_insert_after(LinkNode **listp, void *ptr) ATTR_NONNULL(1); -void BLI_linklist_free(struct LinkNode *list, LinkNodeFreeFP freefunc); -void BLI_linklist_freeN(struct LinkNode *list); -void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool); -void BLI_linklist_apply(struct LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata); +void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc); +void BLI_linklist_freeN(LinkNode *list); +void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool); +void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata); +LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(2); +LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(2); #define BLI_linklist_prepend_alloca(listp, ptr) \ BLI_linklist_prepend_nlink(listp, ptr, alloca(sizeof(LinkNode))) diff --git a/source/blender/blenlib/BLI_linklist_stack.h b/source/blender/blenlib/BLI_linklist_stack.h index 9ac233a8fa4..a4b8f77bfa6 100644 --- a/source/blender/blenlib/BLI_linklist_stack.h +++ b/source/blender/blenlib/BLI_linklist_stack.h @@ -168,6 +168,16 @@ #define BLI_SMALLSTACK_IS_EMPTY(var) \ ((_BLI_SMALLSTACK_CAST(var) _##var##_stack) == NULL) +/* fill in a lookup table */ +#define BLI_SMALLSTACK_AS_TABLE(var, data) \ +{ \ + LinkNode *_##var##_iter; \ + unsigned int i; \ + for (_##var##_iter = _##var##_stack, i = 0; _##var##_iter; _##var##_iter = _##var##_iter->next, i++) { \ + (data)[i] = _BLI_SMALLSTACK_CAST(var) (_##var##_iter->link); \ + } \ +} ((void)0) + /* loop over stack members last-added-first */ #define BLI_SMALLSTACK_ITER_BEGIN(var, item) \ { \ diff --git a/source/blender/blenlib/BLI_listbase.h b/source/blender/blenlib/BLI_listbase.h index 2e01f743f9e..9dfa80006de 100644 --- a/source/blender/blenlib/BLI_listbase.h +++ b/source/blender/blenlib/BLI_listbase.h @@ -68,7 +68,7 @@ void BLI_addhead(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1); void BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1); void BLI_insertlinkafter(struct ListBase *listbase, void *vprevlink, void *vnewlink) ATTR_NONNULL(1); void BLI_listbase_sort(struct ListBase *listbase, int (*cmp)(const void *, const void *)) ATTR_NONNULL(1, 2); -void BLI_listbase_sort_r(ListBase *listbase, void *thunk, int (*cmp)(void *, const void *, const void *)) ATTR_NONNULL(1, 3); +void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk) ATTR_NONNULL(1, 2); void BLI_freelist(struct ListBase *listbase) ATTR_NONNULL(1); int BLI_listbase_count_ex(const struct ListBase *listbase, const int count_max) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); int BLI_listbase_count(const struct ListBase *listbase) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); diff --git a/source/blender/blenlib/BLI_math.h b/source/blender/blenlib/BLI_math.h index db2fed433da..ce0183eee68 100644 --- a/source/blender/blenlib/BLI_math.h +++ b/source/blender/blenlib/BLI_math.h @@ -30,18 +30,32 @@ * \ingroup bli * \section mathabbrev Abbreviations * - * - fl = float - * - db = double - * - v2 = vec2 = vector 2 - * - v3 = vec3 = vector 3 - * - v4 = vec4 = vector 4 - * - qt = quat = quaternion - * - dq = dquat = dual quaternion - * - m2 = mat2 = matrix 2x2 - * - m3 = mat3 = matrix 3x3 - * - m4 = mat4 = matrix 4x4 - * - eul = euler rotation - * - eulO = euler with order + * - ``fl`` = float + * - ``db`` = double + * - ``v2`` = vec2 = vector 2 + * - ``v3`` = vec3 = vector 3 + * - ``v4`` = vec4 = vector 4 + * - ``vn`` = vec4 = vector N dimensions, *passed as an arg, after the vector*. + * - ``qt`` = quat = quaternion + * - ``dq`` = dquat = dual quaternion + * - ``m2`` = mat2 = matrix 2x2 + * - ``m3`` = mat3 = matrix 3x3 + * - ``m4`` = mat4 = matrix 4x4 + * - ``eul`` = euler rotation + * - ``eulO`` = euler with order + * - ``plane`` = plane 4, (vec3, distance) + * - ``plane3`` = plane 3 (same as a ``plane`` with a zero 4th component) + * + * \subsection mathabbrev_all Function Type Abbreviations + * + * For non float versions of functions (which typically operate on floats), + * use single suffix abbreviations. + * + * - ``_d`` = double + * - ``_i`` = int + * - ``_u`` = unsigned int + * - ``_char`` = char + * - ``_uchar`` = unsigned char * * \section mathvarnames Variable Names * @@ -61,4 +75,3 @@ #include "BLI_math_interp.h" #endif /* __BLI_MATH_H__ */ - diff --git a/source/blender/blenlib/BLI_math_base.h b/source/blender/blenlib/BLI_math_base.h index daa7db8e3cf..39c1b22a632 100644 --- a/source/blender/blenlib/BLI_math_base.h +++ b/source/blender/blenlib/BLI_math_base.h @@ -90,7 +90,7 @@ static const int NAN_INT = 0x7FC00000; #endif /* do not redefine functions from C99, POSIX.1-2001 or MSVC12 (partial C99) */ -#if !(defined(_ISOC99_SOURCE) || (defined(_POSIX_C_SOURCE) && _POSIX_C_SOURCE >= 200112L) || (defined(_MSC_VER) && _MSC_VER >= 1800)) +#if !(defined(_ISOC99_SOURCE) || (defined(_POSIX_C_SOURCE) && _POSIX_C_SOURCE >= 200112L) || defined(_MSC_VER)) #ifndef sqrtf #define sqrtf(a) ((float)sqrt(a)) @@ -214,9 +214,7 @@ MINLINE int iroundf(float a); MINLINE int divide_round_i(int a, int b); MINLINE int mod_i(int i, int n); -MINLINE unsigned int highest_order_bit_i(unsigned int n); -MINLINE unsigned short highest_order_bit_s(unsigned short n); - +int pow_i(int base, int exp); double double_round(double x, int ndigits); #ifdef BLI_MATH_GCC_WARN_PRAGMA diff --git a/source/blender/blenlib/BLI_math_bits.h b/source/blender/blenlib/BLI_math_bits.h new file mode 100644 index 00000000000..876c0d92e31 --- /dev/null +++ b/source/blender/blenlib/BLI_math_bits.h @@ -0,0 +1,51 @@ +/* + * ***** 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_MATH_BITS_H__ +#define __BLI_MATH_BITS_H__ + +/** \file BLI_math_bits.h + * \ingroup bli + */ + +#ifdef __cplusplus +extern "C" { +#endif + +#include "BLI_math_inline.h" + +MINLINE unsigned int highest_order_bit_i(unsigned int n); +MINLINE unsigned short highest_order_bit_s(unsigned short n); + +#ifdef __GNUC__ +# define count_bits_i(i) __builtin_popcount(i) +#else +MINLINE int count_bits_i(unsigned int n); +#endif + +#if BLI_MATH_DO_INLINE +#include "intern/math_bits_inline.c" +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_MATH_BITS_H__ */ diff --git a/source/blender/blenlib/BLI_math_color.h b/source/blender/blenlib/BLI_math_color.h index 5652c8056c0..d70dfcd9e58 100644 --- a/source/blender/blenlib/BLI_math_color.h +++ b/source/blender/blenlib/BLI_math_color.h @@ -129,6 +129,9 @@ void rgba_float_to_uchar(unsigned char r_col[4], const float col_f[4]); void xyz_to_lab(float x, float y, float z, float *l, float *a, float *b); +MINLINE float rgb_to_grayscale(const float rgb[3]); +MINLINE unsigned char rgb_to_grayscale_byte(const unsigned char rgb[3]); + MINLINE int compare_rgb_uchar(const unsigned char a[3], const unsigned char b[3], const int limit); MINLINE float dither_random_value(float s, float t); diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 4f7a3310ee6..2c91aca27ef 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -102,6 +102,12 @@ float dist_squared_to_plane_v3(const float p[3], const float plane[4]); float dist_signed_to_plane_v3(const float p[3], const float plane[4]); float dist_to_plane_v3(const float p[3], const float plane[4]); +/* plane3 versions */ +float dist_signed_squared_to_plane3_v3(const float p[3], const float plane[4]); +float dist_squared_to_plane3_v3(const float p[3], const float plane[4]); +float dist_signed_to_plane3_v3(const float p[3], const float plane[4]); +float dist_to_plane3_v3(const float p[3], const float plane[4]); + float dist_squared_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]); float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]); float dist_squared_to_line_v3(const float p[3], const float l1[3], const float l2[3]); @@ -142,7 +148,7 @@ int isect_line_line_v2(const float a1[2], const float a2[2], const float b1[2], int isect_line_line_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]); int isect_line_sphere_v3(const float l1[3], const float l2[3], const float sp[3], const float r, float r_p1[3], float r_p2[3]); int isect_line_sphere_v2(const float l1[2], const float l2[2], const float sp[2], const float r, float r_p1[2], float r_p2[2]); -int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[2], const float v4[2], float vi[2]); +int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float vi[2]); bool isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]); int isect_line_line_epsilon_v3( @@ -259,6 +265,7 @@ void resolve_tri_uv_v3(float r_uv[2], const float st[3], const float st0[3], con void resolve_quad_uv_v2(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2]); void resolve_quad_uv_v2_deriv(float r_uv[2], float r_deriv[2][2], const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2]); +float resolve_quad_u_v2(const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2]); /* use to find the point of a UV on a face */ void interp_bilinear_quad_v3(float data[4][3], float u, float v, float res[3]); diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h index 45972d03175..f7eeb1ec7a1 100644 --- a/source/blender/blenlib/BLI_math_matrix.h +++ b/source/blender/blenlib/BLI_math_matrix.h @@ -106,6 +106,7 @@ void mul_v2_m4v3(float r[2], float M[4][4], const float v[3]); void mul_v2_m2v2(float r[2], float M[2][2], const float v[2]); void mul_m2v2(float M[2][2], float v[2]); void mul_mat3_m4_v3(float M[4][4], float r[3]); +void mul_v3_mat3_m4v3(float r[3], float M[4][4], const float v[3]); void mul_m4_v4(float M[4][4], float r[4]); void mul_v4_m4v4(float r[4], float M[4][4], const float v[4]); void mul_project_m4_v3(float M[4][4], float vec[3]); diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index de712cbaa12..9bc1121801e 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -158,6 +158,8 @@ MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESU MINLINE float dot_v3v3v3(const float p[3], const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT; MINLINE float dot_v4v4(const float a[4], const float b[4]) ATTR_WARN_UNUSED_RESULT; +MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT; + MINLINE float cross_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT; MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3]); @@ -271,6 +273,8 @@ void angle_poly_v3(float *angles, const float *verts[3], int len); void project_v2_v2v2(float c[2], const float v1[2], const float v2[2]); void project_v3_v3v3(float r[3], const float p[3], const float n[3]); +void project_plane_v3_v3v3(float c[3], const float v[3], const float v_plane[3]); +void project_plane_v2_v2v2(float c[2], const float v[2], const float v_plane[2]); void project_v3_plane(float v[3], const float n[3], const float p[3]); void reflect_v3_v3v3(float r[3], const float v[3], const float n[3]); void ortho_basis_v3v3_v3(float r_n1[3], float r_n2[3], const float n[3]); @@ -306,12 +310,13 @@ void dist_ensure_v2_v2fl(float v1[2], const float v2[2], const float dist); void axis_sort_v3(const float axis_values[3], int r_axis_order[3]); /***************************** Array Functions *******************************/ -/* attempted to follow fixed length vertex functions. names could be improved*/ +/* follow fixed length vector function conventions. */ double dot_vn_vn(const float *array_src_a, const float *array_src_b, const int size) ATTR_WARN_UNUSED_RESULT; double len_squared_vn(const float *array, const int size) ATTR_WARN_UNUSED_RESULT; float normalize_vn_vn(float *array_tar, const float *array_src, const int size); float normalize_vn(float *array_tar, const int size); void range_vn_i(int *array_tar, const int size, const int start); +void range_vn_u(unsigned int *array_tar, const int size, const unsigned int start); void range_vn_fl(float *array_tar, const int size, const float start, const float step); void negate_vn(float *array_tar, const int size); void negate_vn_vn(float *array_tar, const float *array_src, const int size); @@ -326,11 +331,15 @@ void sub_vn_vnvn(float *array_tar, const float *array_src_a, const float *array_ void msub_vn_vn(float *array_tar, const float *array_src, const float f, const int size); void msub_vn_vnvn(float *array_tar, const float *array_src_a, const float *array_src_b, const float f, const int size); void interp_vn_vn(float *array_tar, const float *array_src, const float t, const int size); -void fill_vn_i(int *array_tar, const int size, const int val); -void fill_vn_short(short *array_tar, const int size, const short val); -void fill_vn_ushort(unsigned short *array_tar, const int size, const unsigned short val); -void fill_vn_uchar(unsigned char *array_tar, const int size, const unsigned char val); -void fill_vn_fl(float *array_tar, const int size, const float val); +void copy_vn_i(int *array_tar, const int size, const int val); +void copy_vn_short(short *array_tar, const int size, const short val); +void copy_vn_ushort(unsigned short *array_tar, const int size, const unsigned short val); +void copy_vn_uchar(unsigned char *array_tar, const int size, const unsigned char val); +void copy_vn_fl(float *array_tar, const int size, const float val); + +void add_vn_vn_d(double *array_tar, const double *array_src, const int size); +void add_vn_vnvn_d(double *array_tar, const double *array_src_a, const double *array_src_b, const int size); +void mul_vn_db(double *array_tar, const int size, const double f); /**************************** Inline Definitions ******************************/ diff --git a/source/blender/blenlib/BLI_path_util.h b/source/blender/blenlib/BLI_path_util.h index d99df24aaf7..c9a54c33f21 100644 --- a/source/blender/blenlib/BLI_path_util.h +++ b/source/blender/blenlib/BLI_path_util.h @@ -38,7 +38,6 @@ extern "C" { #include "BLI_compiler_attrs.h" struct ListBase; -struct direntry; #ifdef WIN32 #define SEP '\\' @@ -79,6 +78,11 @@ void BLI_del_slash(char *string) ATTR_NONNULL(); const char *BLI_first_slash(const char *string) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; void BLI_path_native_slash(char *path) ATTR_NONNULL(); +#ifdef _WIN32 +bool BLI_path_program_extensions_add_win32(char *name, const size_t maxlen); +#endif +bool BLI_path_program_search(char *fullname, const size_t maxlen, const char *name); + void BLI_getlastdir(const char *dir, char *last, const size_t maxlen); bool BLI_testextensie(const char *str, const char *ext) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; bool BLI_testextensie_n(const char *str, ...) ATTR_NONNULL(1) ATTR_SENTINEL(0); @@ -128,6 +132,8 @@ bool BLI_parent_dir(char *path) ATTR_NONNULL(); bool BLI_path_abs(char *path, const char *basepath) ATTR_NONNULL(); bool BLI_path_frame(char *path, int frame, int digits) ATTR_NONNULL(); bool BLI_path_frame_range(char *path, int sta, int end, int digits) ATTR_NONNULL(); +bool BLI_path_frame_get(char *path, int *r_frame, int *numdigits) ATTR_NONNULL(); +void BLI_path_frame_strip(char *path, bool setsharp, char *ext) ATTR_NONNULL(); bool BLI_path_frame_check_chars(const char *path) ATTR_NONNULL(); bool BLI_path_cwd(char *path) ATTR_NONNULL(); void BLI_path_rel(char *file, const char *relfile) ATTR_NONNULL(); diff --git a/source/blender/blenlib/BLI_quadric.h b/source/blender/blenlib/BLI_quadric.h index 82c39463dd2..eaf9c7a0738 100644 --- a/source/blender/blenlib/BLI_quadric.h +++ b/source/blender/blenlib/BLI_quadric.h @@ -31,14 +31,14 @@ */ typedef struct Quadric { - float a2, ab, ac, ad, - b2, bc, bd, - c2, cd, - d2; + double a2, ab, ac, ad, + b2, bc, bd, + c2, cd, + d2; } Quadric; /* conversion */ -void BLI_quadric_from_v3_dist(Quadric *q, const float v[3], const float offset); +void BLI_quadric_from_plane(Quadric *q, const double v[4]); void BLI_quadric_to_tensor_m3(const Quadric *q, float m[3][3]); void BLI_quadric_to_vector_v3(const Quadric *q, float v[3]); @@ -47,10 +47,10 @@ void BLI_quadric_clear(Quadric *q); /* math */ void BLI_quadric_add_qu_qu(Quadric *a, const Quadric *b); void BLI_quadric_add_qu_ququ(Quadric *r, const Quadric *a, const Quadric *b); -void BLI_quadric_mul(Quadric *a, const float scalar); +void BLI_quadric_mul(Quadric *a, const double scalar); /* solve */ -float BLI_quadric_evaluate(const Quadric *q, const float v[3]); +double BLI_quadric_evaluate(const Quadric *q, const float v_fl[3]); bool BLI_quadric_optimize(const Quadric *q, float v[3], const float epsilon); #endif /* __BLI_QUADRIC_H__ */ diff --git a/source/blender/blenlib/BLI_rect.h b/source/blender/blenlib/BLI_rect.h index a132ac40206..242ba9f860a 100644 --- a/source/blender/blenlib/BLI_rect.h +++ b/source/blender/blenlib/BLI_rect.h @@ -78,6 +78,10 @@ bool BLI_rctf_isect_x(const rctf *rect, const float x); bool BLI_rctf_isect_y(const rctf *rect, const float y); bool BLI_rctf_isect_pt(const struct rctf *rect, const float x, const float y); bool BLI_rctf_isect_pt_v(const struct rctf *rect, const float xy[2]); +int BLI_rcti_length_x(const rcti *rect, const int x); +int BLI_rcti_length_y(const rcti *rect, const int y); +float BLI_rctf_length_x(const rctf *rect, const float x); +float BLI_rctf_length_y(const rctf *rect, const float y); bool BLI_rcti_isect_segment(const struct rcti *rect, const int s1[2], const int s2[2]); bool BLI_rctf_isect_segment(const struct rctf *rect, const float s1[2], const float s2[2]); bool BLI_rcti_isect_circle(const struct rcti *rect, const float xy[2], const float radius); @@ -89,6 +93,8 @@ void BLI_rctf_union(struct rctf *rctf1, const struct rctf *rctf2); void BLI_rcti_rctf_copy(struct rcti *dst, const struct rctf *src); void BLI_rctf_rcti_copy(struct rctf *dst, const struct rcti *src); +void BLI_rctf_rotate_expand(rctf *dst, const rctf *src, const float angle); + void print_rctf(const char *str, const struct rctf *rect); void print_rcti(const char *str, const struct rcti *rect); diff --git a/source/blender/blenlib/BLI_stack.h b/source/blender/blenlib/BLI_stack.h index a8c4478c450..222005ee92e 100644 --- a/source/blender/blenlib/BLI_stack.h +++ b/source/blender/blenlib/BLI_stack.h @@ -44,10 +44,12 @@ void *BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL(); void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL(); +void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL(); void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL(); void *BLI_stack_peek(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BLI_stack_discard(BLI_Stack *stack) ATTR_NONNULL(); +void BLI_stack_clear(BLI_Stack *stack) ATTR_NONNULL(); size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); diff --git a/source/blender/blenlib/BLI_stackdefines.h b/source/blender/blenlib/BLI_stackdefines.h index 864a7704aa9..2d8d6e4482d 100644 --- a/source/blender/blenlib/BLI_stackdefines.h +++ b/source/blender/blenlib/BLI_stackdefines.h @@ -40,7 +40,7 @@ # define _STACK_SIZETEST(stack, off) (void)(stack), (void)(off) # define _STACK_SWAP_TOTALLOC(stack_a, stack_b) (void)(stack_a), (void)(stack_b) #endif -#define _STACK_BOUNDSTEST(stack, index) ((void)stack, BLI_assert(index >= 0 && index < _##stack##_index)) +#define _STACK_BOUNDSTEST(stack, index) ((void)stack, BLI_assert((unsigned int)index < _##stack##_index)) #define STACK_SIZE(stack) ((void)stack, (_##stack##_index)) diff --git a/source/blender/blenlib/BLI_string.h b/source/blender/blenlib/BLI_string.h index c4853e37398..c8491f4c8f1 100644 --- a/source/blender/blenlib/BLI_string.h +++ b/source/blender/blenlib/BLI_string.h @@ -59,8 +59,10 @@ char *BLI_str_quoted_substrN(const char *__restrict str, const char *__restrict char *BLI_replacestrN(const char *__restrict str, const char *__restrict substr_old, const char *__restrict substr_new) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL() ATTR_MALLOC; size_t BLI_snprintf(char *__restrict dst, size_t maxncpy, const char *__restrict format, ...) ATTR_NONNULL(1, 3) ATTR_PRINTF_FORMAT(3, 4); +size_t BLI_snprintf_rlen(char *__restrict dst, size_t maxncpy, const char *__restrict format, ...) ATTR_NONNULL(1, 3) ATTR_PRINTF_FORMAT(3, 4); size_t BLI_vsnprintf(char *__restrict dst, size_t maxncpy, const char *__restrict format, va_list arg) ATTR_PRINTF_FORMAT(3, 0); +size_t BLI_vsnprintf_rlen(char *__restrict buffer, size_t maxncpy, const char *__restrict format, va_list arg) ATTR_PRINTF_FORMAT(3, 0); char *BLI_sprintfN(const char *__restrict format, ...) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_PRINTF_FORMAT(1, 2); @@ -88,9 +90,11 @@ int BLI_str_index_in_array(const char *__restrict str, const char **__restrict s bool BLI_str_endswith(const char *__restrict str, const char *__restrict end) ATTR_NONNULL(); bool BLI_strn_endswith(const char *__restrict str, const char *__restrict end, size_t length) ATTR_NONNULL(); -size_t BLI_str_partition(const char *str, const char delim[], char **sep, char **suf) ATTR_NONNULL(); -size_t BLI_str_rpartition(const char *str, const char delim[], char **sep, char **suf) ATTR_NONNULL(); -size_t BLI_str_partition_ex(const char *str, const char delim[], char **sep, char **suf, const bool from_right) ATTR_NONNULL(); +size_t BLI_str_partition(const char *str, const char delim[], const char **sep, const char **suf) ATTR_NONNULL(); +size_t BLI_str_rpartition(const char *str, const char delim[], const char **sep, const char **suf) ATTR_NONNULL(); +size_t BLI_str_partition_ex( + const char *str, const char *end, const char delim[], const char **sep, const char **suf, const bool from_right) + ATTR_NONNULL(1, 3, 4, 5); #ifdef __cplusplus } diff --git a/source/blender/blenlib/BLI_string_utf8.h b/source/blender/blenlib/BLI_string_utf8.h index 3e599865416..0740b574c1a 100644 --- a/source/blender/blenlib/BLI_string_utf8.h +++ b/source/blender/blenlib/BLI_string_utf8.h @@ -67,9 +67,11 @@ int BLI_wcswidth(const wchar_t *pwcs, size_t n) ATTR_NONNULL(); int BLI_str_utf8_char_width(const char *p) ATTR_NONNULL(); /* warning, can return -1 on bad chars */ int BLI_str_utf8_char_width_safe(const char *p) ATTR_NONNULL(); -size_t BLI_str_partition_utf8(const char *str, const unsigned int delim[], char **sep, char **suf) ATTR_NONNULL(); -size_t BLI_str_rpartition_utf8(const char *str, const unsigned int delim[], char **sep, char **suf) ATTR_NONNULL(); -size_t BLI_str_partition_ex_utf8(const char *str, const unsigned int delim[], char **sep, char **suf, const bool from_right) ATTR_NONNULL(); +size_t BLI_str_partition_utf8(const char *str, const unsigned int delim[], const char **sep, const char **suf) ATTR_NONNULL(); +size_t BLI_str_rpartition_utf8(const char *str, const unsigned int delim[], const char **sep, const char **suf) ATTR_NONNULL(); +size_t BLI_str_partition_ex_utf8( + const char *str, const char *end, const unsigned int delim[], const char **sep, const char **suf, const bool from_right) + ATTR_NONNULL(1, 3, 4, 5); #define BLI_UTF8_MAX 6 /* mem */ #define BLI_UTF8_WIDTH_MAX 2 /* columns */ diff --git a/source/blender/blenlib/BLI_task.h b/source/blender/blenlib/BLI_task.h index 2eaec024ce2..780b0bfbbd6 100644 --- a/source/blender/blenlib/BLI_task.h +++ b/source/blender/blenlib/BLI_task.h @@ -88,6 +88,9 @@ void BLI_task_pool_cancel(TaskPool *pool); /* stop all worker threads */ void BLI_task_pool_stop(TaskPool *pool); +/* get number of threads allowed to be used by this pool */ +int BLI_pool_get_num_threads(TaskPool *pool); + /* set number of threads allowed to be used by this pool */ void BLI_pool_set_num_threads(TaskPool *pool, int num_threads); diff --git a/source/blender/blenlib/BLI_threads.h b/source/blender/blenlib/BLI_threads.h index 74291ca305e..b2ead15af22 100644 --- a/source/blender/blenlib/BLI_threads.h +++ b/source/blender/blenlib/BLI_threads.h @@ -89,6 +89,7 @@ int BLI_system_num_threads_override_get(void); #define LOCK_MOVIECLIP 7 #define LOCK_COLORMANAGE 8 #define LOCK_FFTW 9 +#define LOCK_VIEW3D 10 void BLI_lock_thread(int type); void BLI_unlock_thread(int type); @@ -174,6 +175,7 @@ void BLI_thread_queue_push(ThreadQueue *queue, void *work); void *BLI_thread_queue_pop(ThreadQueue *queue); void *BLI_thread_queue_pop_timeout(ThreadQueue *queue, int ms); int BLI_thread_queue_size(ThreadQueue *queue); +bool BLI_thread_queue_is_empty(ThreadQueue *queue); void BLI_thread_queue_wait_finish(ThreadQueue *queue); void BLI_thread_queue_nowait(ThreadQueue *queue); diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 2ddc8faa8b1..8f2f906ed17 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -435,7 +435,7 @@ extern "C" { } (void)0 /* assuming a static array */ -#if defined(__GNUC__) && !defined(__cplusplus) +#if defined(__GNUC__) && !defined(__cplusplus) && !defined(__clang__) # define ARRAY_SIZE(arr) \ ((sizeof(struct {int isnt_array : ((const void *)&(arr) == &(arr)[0]);}) * 0) + \ (sizeof(arr) / sizeof(*(arr)))) @@ -493,8 +493,11 @@ extern "C" { #define OFFSETOF_STRUCT(_struct, _member) \ ((((char *)&((_struct)->_member)) - ((char *)(_struct))) + sizeof((_struct)->_member)) -/* memcpy, skipping the first part of a struct, - * ensures 'struct_dst' isn't const and that the offset can be computed at compile time */ +/** + * memcpy helper, skipping the first part of a struct, + * ensures 'struct_dst' isn't const and the offset can be computed at compile time. + * This isn't inclusive, the value of \a member isn't copied. + */ #define MEMCPY_STRUCT_OFS(struct_dst, struct_src, member) { \ CHECK_TYPE_NONCONST(struct_dst); \ ((void)(struct_dst == struct_src), \ @@ -503,6 +506,13 @@ extern "C" { sizeof(*(struct_dst)) - OFFSETOF_STRUCT(struct_dst, member))); \ } (void)0 +#define MEMSET_STRUCT_OFS(struct_var, value, member) { \ + CHECK_TYPE_NONCONST(struct_var); \ + memset((char *)(struct_var) + OFFSETOF_STRUCT(struct_var, member), \ + value, \ + sizeof(*(struct_var)) - OFFSETOF_STRUCT(struct_var, member)); \ +} (void)0 + /* Warning-free macros for storing ints in pointers. Use these _only_ * for storing an int in a pointer, not a pointer in an int (64bit)! */ #define SET_INT_IN_POINTER(i) ((void *)(intptr_t)(i)) diff --git a/source/blender/blenlib/BLI_winstuff.h b/source/blender/blenlib/BLI_winstuff.h index f40359ec3dc..8cf6f188e19 100644 --- a/source/blender/blenlib/BLI_winstuff.h +++ b/source/blender/blenlib/BLI_winstuff.h @@ -132,17 +132,8 @@ struct dirent { char *d_name; }; -typedef struct _DIR { - HANDLE handle; - WIN32_FIND_DATAW data; - char path[MAX_PATH]; - long dd_loc; - long dd_size; - char dd_buf[4096]; - void *dd_direct; - - struct dirent direntry; -} DIR; +/* intentionally opaque to users */ +typedef struct __dirstream DIR; DIR *opendir(const char *path); struct dirent *readdir(DIR *dp); diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index e614a2a0663..37c9afd3a6d 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -23,8 +23,6 @@ # # ***** END GPL LICENSE BLOCK ***** -# XXX allowing blenkernel and RNA includes in blenlib is a hack, -# but needed in a few places atm (bpath.c for instance) set(INC . # ../blenkernel # dont add this back! @@ -44,6 +42,7 @@ set(SRC intern/BLI_array.c intern/BLI_dial.c intern/BLI_dynstr.c + intern/BLI_filelist.c intern/BLI_ghash.c intern/BLI_heap.c intern/BLI_kdopbvh.c @@ -71,9 +70,11 @@ set(SRC intern/hash_mm2a.c intern/jitter.c intern/lasso.c + intern/list_sort_impl.h intern/listbase.c intern/math_base.c intern/math_base_inline.c + intern/math_bits_inline.c intern/math_color.c intern/math_color_blend_inline.c intern/math_color_inline.c @@ -153,6 +154,7 @@ set(SRC BLI_listbase.h BLI_math.h BLI_math_base.h + BLI_math_bits.h BLI_math_color.h BLI_math_color_blend.h BLI_math_geom.h @@ -205,10 +207,15 @@ if(WIN32) ) endif() -blender_add_lib(bf_blenlib "${SRC}" "${INC}" "${INC_SYS}") +# no need to compile object files for inline headers. +set_source_files_properties( + intern/math_base_inline.c + intern/math_bits_inline.c + intern/math_color_blend_inline.c + intern/math_color_inline.c + intern/math_geom_inline.c + intern/math_vector_inline.c + PROPERTIES HEADER_FILE_ONLY TRUE +) -if(MSVC) - # Quiet warning about inline math library files that do not export symbols. - # (normally you'd exclude from project, but we still want to see the files in MSVC) - set_target_properties(bf_blenlib PROPERTIES STATIC_LIBRARY_FLAGS /ignore:4221) -endif() +blender_add_lib(bf_blenlib "${SRC}" "${INC}" "${INC_SYS}") diff --git a/source/blender/blenlib/intern/BLI_dynstr.c b/source/blender/blenlib/intern/BLI_dynstr.c index 8617132e988..80cbce7e256 100644 --- a/source/blender/blenlib/intern/BLI_dynstr.c +++ b/source/blender/blenlib/intern/BLI_dynstr.c @@ -258,11 +258,11 @@ int BLI_dynstr_get_len(DynStr *ds) /** * Get a DynStr's contents as a c-string. - * <i> The str argument must be allocated to be at - * least the size of BLI_dynstr_get_len(ds) + 1. </i> + * he \a rets argument must be allocated to be at + * least the size of ``BLI_dynstr_get_len(ds) + 1``. * - * \param ds The DynStr of interest. - * \param str The string to fill. + * \param ds: The DynStr of interest. + * \param rets: The string to fill. */ void BLI_dynstr_get_cstring_ex(DynStr *__restrict ds, char *__restrict rets) { diff --git a/source/blender/blenlib/intern/BLI_filelist.c b/source/blender/blenlib/intern/BLI_filelist.c new file mode 100644 index 00000000000..786eaa74df8 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_filelist.c @@ -0,0 +1,392 @@ +/* + * ***** 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_filelist.c + * \ingroup bli + */ + +#include <sys/types.h> +#include <stdio.h> +#include <stdlib.h> + +#ifndef WIN32 +# include <dirent.h> +#endif + +#include <time.h> +#include <sys/stat.h> +#include <string.h> /* strcpy etc.. */ + +#ifdef WIN32 +# include <io.h> +# include <direct.h> +# include "BLI_winstuff.h" +# include "utfconv.h" +#else +# include <sys/ioctl.h> +# include <unistd.h> +# include <pwd.h> +#endif + +/* lib includes */ +#include "MEM_guardedalloc.h" + +#include "DNA_listBase.h" + +#include "BLI_listbase.h" +#include "BLI_string.h" +#include "BLI_fileops.h" +#include "BLI_fileops_types.h" +#include "BLI_path_util.h" + +#include "../imbuf/IMB_imbuf.h" + + +/* + * Ordering function for sorting lists of files/directories. Returns -1 if + * entry1 belongs before entry2, 0 if they are equal, 1 if they should be swapped. + */ +static int bli_compare(struct direntry *entry1, struct direntry *entry2) +{ + /* type is equal to stat.st_mode */ + + /* directories come before non-directories */ + if (S_ISDIR(entry1->type)) { + if (S_ISDIR(entry2->type) == 0) return (-1); + } + else { + if (S_ISDIR(entry2->type)) return (1); + } + /* non-regular files come after regular files */ + if (S_ISREG(entry1->type)) { + if (S_ISREG(entry2->type) == 0) return (-1); + } + else { + if (S_ISREG(entry2->type)) return (1); + } + /* arbitrary, but consistent, ordering of different types of non-regular files */ + if ((entry1->type & S_IFMT) < (entry2->type & S_IFMT)) return (-1); + if ((entry1->type & S_IFMT) > (entry2->type & S_IFMT)) return (1); + + /* OK, now we know their S_IFMT fields are the same, go on to a name comparison */ + /* make sure "." and ".." are always first */ + if (FILENAME_IS_CURRENT(entry1->relname)) return (-1); + if (FILENAME_IS_CURRENT(entry2->relname)) return (1); + if (FILENAME_IS_PARENT(entry1->relname)) return (-1); + if (FILENAME_IS_PARENT(entry2->relname)) return (1); + + return (BLI_natstrcmp(entry1->relname, entry2->relname)); +} + + +struct BuildDirCtx { + struct direntry *files; /* array[nrfiles] */ + int nrfiles; +}; + +/** + * Scans the directory named *dirname and appends entries for its contents to files. + */ +static void bli_builddir(struct BuildDirCtx *dir_ctx, const char *dirname) +{ + struct ListBase dirbase = {NULL, NULL}; + int newnum = 0; + DIR *dir; + + if ((dir = opendir(dirname)) != NULL) { + const struct dirent *fname; + bool has_current = false, has_parent = false; + + while ((fname = readdir(dir)) != NULL) { + struct dirlink * const dlink = (struct dirlink *)malloc(sizeof(struct dirlink)); + if (dlink != NULL) { + dlink->name = BLI_strdup(fname->d_name); + if (FILENAME_IS_PARENT(dlink->name)) { + has_parent = true; + } + else if (FILENAME_IS_CURRENT(dlink->name)) { + has_current = true; + } + BLI_addhead(&dirbase, dlink); + newnum++; + } + } + + if (!has_parent) { + char pardir[FILE_MAXDIR]; + + BLI_strncpy(pardir, dirname, sizeof(pardir)); + if (BLI_parent_dir(pardir) && (BLI_access(pardir, R_OK) == 0)) { + struct dirlink * const dlink = (struct dirlink *)malloc(sizeof(struct dirlink)); + if (dlink != NULL) { + dlink->name = BLI_strdup(FILENAME_PARENT); + BLI_addhead(&dirbase, dlink); + newnum++; + } + } + } + if (!has_current) { + struct dirlink * const dlink = (struct dirlink *)malloc(sizeof(struct dirlink)); + if (dlink != NULL) { + dlink->name = BLI_strdup(FILENAME_CURRENT); + BLI_addhead(&dirbase, dlink); + newnum++; + } + } + + if (newnum) { + if (dir_ctx->files) { + void * const tmp = MEM_reallocN(dir_ctx->files, (dir_ctx->nrfiles + newnum) * sizeof(struct direntry)); + if (tmp) { + dir_ctx->files = (struct direntry *)tmp; + } + else { /* realloc fail */ + MEM_freeN(dir_ctx->files); + dir_ctx->files = NULL; + } + } + + if (dir_ctx->files == NULL) + dir_ctx->files = (struct direntry *)MEM_mallocN(newnum * sizeof(struct direntry), __func__); + + if (dir_ctx->files) { + struct dirlink * dlink = (struct dirlink *) dirbase.first; + struct direntry *file = &dir_ctx->files[dir_ctx->nrfiles]; + while (dlink) { + char fullname[PATH_MAX]; + memset(file, 0, sizeof(struct direntry)); + file->relname = dlink->name; + file->path = BLI_strdupcat(dirname, dlink->name); + BLI_join_dirfile(fullname, sizeof(fullname), dirname, dlink->name); + if (BLI_stat(fullname, &file->s) != -1) { + file->type = file->s.st_mode; + } + else if (FILENAME_IS_CURRPAR(file->relname)) { + /* Hack around for UNC paths on windows - does not support stat on '\\SERVER\foo\..', sigh... */ + file->type |= S_IFDIR; + } + file->flags = 0; + dir_ctx->nrfiles++; + file++; + dlink = dlink->next; + } + } + else { + printf("Couldn't get memory for dir\n"); + exit(1); + } + + BLI_freelist(&dirbase); + if (dir_ctx->files) { + qsort(dir_ctx->files, dir_ctx->nrfiles, sizeof(struct direntry), (int (*)(const void *, const void *))bli_compare); + } + } + else { + printf("%s empty directory\n", dirname); + } + + closedir(dir); + } + else { + printf("%s non-existent directory\n", dirname); + } +} + +/** + * Fills in the "mode[123]", "size" and "string" fields in the elements of the files + * array with descriptive details about each item. "string" will have a format similar to "ls -l". + */ +static void bli_adddirstrings(struct BuildDirCtx *dir_ctx) +{ + const char *types[8] = {"---", "--x", "-w-", "-wx", "r--", "r-x", "rw-", "rwx"}; + /* symbolic display, indexed by mode field value */ + int num; + double size; + struct direntry *file; + struct tm *tm; + time_t zero = 0; + +#ifndef WIN32 + int mode; +#endif + + for (num = 0, file = dir_ctx->files; num < dir_ctx->nrfiles; num++, file++) { + + /* Mode */ +#ifdef WIN32 + BLI_strncpy(file->mode1, types[0], sizeof(file->mode1)); + BLI_strncpy(file->mode2, types[0], sizeof(file->mode2)); + BLI_strncpy(file->mode3, types[0], sizeof(file->mode3)); +#else + mode = file->s.st_mode; + + BLI_strncpy(file->mode1, types[(mode & 0700) >> 6], sizeof(file->mode1)); + BLI_strncpy(file->mode2, types[(mode & 0070) >> 3], sizeof(file->mode2)); + BLI_strncpy(file->mode3, types[(mode & 0007)], sizeof(file->mode3)); + + if (((mode & S_ISGID) == S_ISGID) && (file->mode2[2] == '-')) file->mode2[2] = 'l'; + + if (mode & (S_ISUID | S_ISGID)) { + if (file->mode1[2] == 'x') file->mode1[2] = 's'; + else file->mode1[2] = 'S'; + + if (file->mode2[2] == 'x') file->mode2[2] = 's'; + } + + if (mode & S_ISVTX) { + if (file->mode3[2] == 'x') file->mode3[2] = 't'; + else file->mode3[2] = 'T'; + } +#endif + + + /* User */ +#ifdef WIN32 + strcpy(file->owner, "user"); +#else + { + struct passwd *pwuser; + pwuser = getpwuid(file->s.st_uid); + if (pwuser) { + BLI_strncpy(file->owner, pwuser->pw_name, sizeof(file->owner)); + } + else { + BLI_snprintf(file->owner, sizeof(file->owner), "%u", file->s.st_uid); + } + } +#endif + + + /* Time */ + tm = localtime(&file->s.st_mtime); + // prevent impossible dates in windows + if (tm == NULL) tm = localtime(&zero); + strftime(file->time, sizeof(file->time), "%H:%M", tm); + strftime(file->date, sizeof(file->date), "%d-%b-%y", tm); + + + /* Size */ + /* + * Seems st_size is signed 32-bit value in *nix and Windows. This + * will buy us some time until files get bigger than 4GB or until + * everyone starts using __USE_FILE_OFFSET64 or equivalent. + */ + size = (double)file->s.st_size; + + if (size > 1024.0 * 1024.0 * 1024.0 * 1024.0) { + BLI_snprintf(file->size, sizeof(file->size), "%.1f TiB", size / (1024.0 * 1024.0 * 1024.0 * 1024.0)); + } + else if (size > 1024.0 * 1024.0 * 1024.0) { + BLI_snprintf(file->size, sizeof(file->size), "%.1f GiB", size / (1024.0 * 1024.0 * 1024.0)); + } + else if (size > 1024.0 * 1024.0) { + BLI_snprintf(file->size, sizeof(file->size), "%.1f MiB", size / (1024.0 * 1024.0)); + } + else if (size > 1024.0) { + BLI_snprintf(file->size, sizeof(file->size), "%.1f KiB", size / 1024.0); + } + else { + BLI_snprintf(file->size, sizeof(file->size), "%d B", (int)size); + } + } +} + +/** + * Scans the contents of the directory named *dirname, and allocates and fills in an + * array of entries describing them in *filelist. + * + * \return The length of filelist array. + */ +unsigned int BLI_filelist_dir_contents(const char *dirname, struct direntry **filelist) +{ + struct BuildDirCtx dir_ctx; + + dir_ctx.nrfiles = 0; + dir_ctx.files = NULL; + + bli_builddir(&dir_ctx, dirname); + bli_adddirstrings(&dir_ctx); + + if (dir_ctx.files) { + *filelist = dir_ctx.files; + } + else { + // keep blender happy. Blender stores this in a variable + // where 0 has special meaning..... + *filelist = MEM_mallocN(sizeof(**filelist), __func__); + } + + return dir_ctx.nrfiles; +} + +/** + * Deep-duplicate of an array of direntries, including the array itself. + * + * \param dup_poin If given, called for each non-NULL direntry->poin. Otherwise, pointer is always simply copied over. + */ +void BLI_filelist_duplicate( + struct direntry **dest_filelist, struct direntry *src_filelist, unsigned int nrentries, + void *(*dup_poin)(void *)) +{ + unsigned int i; + + *dest_filelist = MEM_mallocN(sizeof(**dest_filelist) * (size_t)(nrentries), __func__); + for (i = 0; i < nrentries; ++i) { + struct direntry * const src = &src_filelist[i]; + struct direntry *dest = &(*dest_filelist)[i]; + *dest = *src; + if (dest->image) { + dest->image = IMB_dupImBuf(src->image); + } + if (dest->relname) { + dest->relname = MEM_dupallocN(src->relname); + } + if (dest->path) { + dest->path = MEM_dupallocN(src->path); + } + if (dest->poin && dup_poin) { + dest->poin = dup_poin(src->poin); + } + } +} + +/** + * frees storage for an array of direntries, including the array itself. + */ +void BLI_filelist_free(struct direntry *filelist, unsigned int nrentries, void (*free_poin)(void *)) +{ + unsigned int i; + for (i = 0; i < nrentries; ++i) { + struct direntry *entry = filelist + i; + if (entry->image) { + IMB_freeImBuf(entry->image); + } + if (entry->relname) + MEM_freeN(entry->relname); + if (entry->path) + MEM_freeN(entry->path); + if (entry->poin && free_poin) + free_poin(entry->poin); + } + + if (filelist != NULL) { + MEM_freeN(filelist); + } +} diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 83602645192..9901d52a273 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -162,7 +162,7 @@ BLI_INLINE unsigned int ghash_bucket_index(GHash *gh, const unsigned int hash) #ifdef GHASH_USE_MODULO_BUCKETS return hash % gh->nbuckets; #else - return full_hash & gh->bucket_mask; + return hash & gh->bucket_mask; #endif } @@ -298,14 +298,14 @@ static void ghash_buckets_contract( #ifdef GHASH_USE_MODULO_BUCKETS while ((nentries < gh->limit_shrink) && - (gh->cursize > gh->size_min)) + (gh->cursize > gh->size_min)) { new_nbuckets = hashsizes[--gh->cursize]; gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets); } #else while ((nentries < gh->limit_shrink) && - (gh->bucket_bit > gh->bucket_bit_min)) + (gh->bucket_bit > gh->bucket_bit_min)) { new_nbuckets = 1u << --gh->bucket_bit; gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets); @@ -445,19 +445,35 @@ BLI_INLINE void ghash_insert_ex( } /** + * Insert function that takes a pre-allocated entry. + */ +BLI_INLINE void ghash_insert_ex_keyonly_entry( + GHash *gh, void *key, const unsigned int bucket_index, + Entry *e) +{ + BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0)); + + e->next = gh->buckets[bucket_index]; + e->key = key; + gh->buckets[bucket_index] = e; + + ghash_buckets_expand(gh, ++gh->nentries, false); +} + +/** * Insert function that doesn't set the value (use for GSet) */ BLI_INLINE void ghash_insert_ex_keyonly( GHash *gh, void *key, const unsigned int bucket_index) { - GSetEntry *e = BLI_mempool_alloc(gh->entrypool); + Entry *e = BLI_mempool_alloc(gh->entrypool); BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0)); BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0); e->next = gh->buckets[bucket_index]; e->key = key; - gh->buckets[bucket_index] = (Entry *)e; + gh->buckets[bucket_index] = e; ghash_buckets_expand(gh, ++gh->nentries, false); } @@ -498,7 +514,7 @@ BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool overr { const unsigned int hash = ghash_keyhash(gh, key); const unsigned int bucket_index = ghash_bucket_index(gh, hash); - GSetEntry *e = ghash_lookup_entry_ex(gh, key, bucket_index); + Entry *e = ghash_lookup_entry_ex(gh, key, bucket_index); BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0); @@ -519,13 +535,13 @@ BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool overr * Remove the entry and return it, caller must free from gh->entrypool. */ static Entry *ghash_remove_ex( - GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, + GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const unsigned int bucket_index) { Entry *e_prev; Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, bucket_index); - BLI_assert(!valfreefp|| !(gh->flag & GHASH_FLAG_IS_GSET)); + BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET)); if (e) { if (keyfreefp) keyfreefp(e->key); @@ -992,9 +1008,9 @@ void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve) /** * \return size of the GHash. */ -int BLI_ghash_size(GHash *gh) +unsigned int BLI_ghash_size(GHash *gh) { - return (int)gh->nentries; + return gh->nentries; } /** @@ -1065,6 +1081,58 @@ void **BLI_ghash_lookup_p(GHash *gh, const void *key) } /** + * Ensure \a key is exists in \a gh. + * + * This handles the common situation where the caller needs ensure a key is added to \a gh, + * constructing a new value in the case the key isn't found. + * Otherwise use the existing value. + * + * Such situations typically incur multiple lookups, however this function + * avoids them by ensuring the key is added, + * returning a pointer to the value so it can be used or initialized by the caller. + * + * \returns true when the value didn't need to be added. + * (when false, the caller _must_ initialize the value). + */ +bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) +{ + const unsigned int hash = ghash_keyhash(gh, key); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index); + const bool haskey = (e != NULL); + + if (!haskey) { + e = BLI_mempool_alloc(gh->entrypool); + ghash_insert_ex_keyonly_entry(gh, key, bucket_index, (Entry *)e); + } + + *r_val = &e->val; + return haskey; +} + +/** + * A version of #BLI_ghash_ensure_p copies the key on insertion. + */ +bool BLI_ghash_ensure_p_ex( + GHash *gh, const void *key, void ***r_val, + GHashKeyCopyFP keycopyfp) +{ + const unsigned int hash = ghash_keyhash(gh, key); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index); + const bool haskey = (e != NULL); + + if (!haskey) { + /* keycopyfp(key) is the only difference to BLI_ghash_ensure_p */ + e = BLI_mempool_alloc(gh->entrypool); + ghash_insert_ex_keyonly_entry(gh, keycopyfp(key), bucket_index, (Entry *)e); + } + + *r_val = &e->val; + return haskey; +} + +/** * Remove \a key from \a gh, or return false if the key wasn't found. * * \param key The key to remove. @@ -1072,7 +1140,7 @@ void **BLI_ghash_lookup_p(GHash *gh, const void *key) * \param valfreefp Optional callback to free the value. * \return true if \a key was removed from \a gh. */ -bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) +bool BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { const unsigned int hash = ghash_keyhash(gh, key); const unsigned int bucket_index = ghash_bucket_index(gh, hash); @@ -1095,7 +1163,7 @@ bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFr * \param keyfreefp Optional callback to free the key. * \return the value of \a key int \a gh or NULL. */ -void *BLI_ghash_popkey(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) +void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) { const unsigned int hash = ghash_keyhash(gh, key); const unsigned int bucket_index = ghash_bucket_index(gh, hash); @@ -1452,7 +1520,7 @@ unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]) } unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]) { - return BLI_hash_mm2((const unsigned char *)key, sizeof(key), 0); + return BLI_hash_mm2((const unsigned char *)key, sizeof(int) * 4 /* sizeof(key) */, 0); } bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b) @@ -1493,6 +1561,11 @@ unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr) return BLI_hash_mm2((const unsigned char *)&key, sizeof(key), 0); } +unsigned int BLI_ghashutil_inthash_p_simple(const void *ptr) +{ + return GET_UINT_FROM_POINTER(ptr); +} + bool BLI_ghashutil_intcmp(const void *a, const void *b) { return (a != b); @@ -1640,9 +1713,9 @@ GSet *BLI_gset_copy(GSet *gs, GHashKeyCopyFP keycopyfp) return (GSet *)ghash_copy((GHash *)gs, keycopyfp, NULL); } -int BLI_gset_size(GSet *gs) +unsigned int BLI_gset_size(GSet *gs) { - return (int)((GHash *)gs)->nentries; + return ((GHash *)gs)->nentries; } /** @@ -1678,7 +1751,7 @@ bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) return ghash_insert_safe_keyonly((GHash *)gs, key, true, keyfreefp); } -bool BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) +bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp) { return BLI_ghash_remove((GHash *)gs, key, keyfreefp, NULL); } diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index 66dfa87b7b9..c0f338a1918 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -183,8 +183,8 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) node = (HeapNode *)BLI_memarena_alloc(heap->arena, sizeof(*node)); } - node->value = value; node->ptr = ptr; + node->value = value; node->index = heap->size; heap->tree[node->index] = node; diff --git a/source/blender/blenlib/intern/BLI_linklist.c b/source/blender/blenlib/intern/BLI_linklist.c index 391f3ef7702..1da39967945 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -30,6 +30,7 @@ * \ingroup bli */ +#include <stdlib.h> #include "MEM_guardedalloc.h" @@ -38,7 +39,9 @@ #include "BLI_memarena.h" #include "BLI_mempool.h" -int BLI_linklist_length(LinkNode *list) +#include "BLI_strict_flags.h" + +int BLI_linklist_count(LinkNode *list) { int len; @@ -188,40 +191,39 @@ void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool /** * A version of append that takes the allocated link. */ -void BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) +void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink) { - LinkNode *node = *listp; - nlink->link = ptr; nlink->next = NULL; - if (node == NULL) { - *listp = nlink; + if (list_pair->list) { + BLI_assert((list_pair->last_node != NULL) && (list_pair->last_node->next == NULL)); + list_pair->last_node->next = nlink; } else { - while (node->next != NULL) { - node = node->next; - } - node->next = nlink; + BLI_assert(list_pair->last_node == NULL); + list_pair->list = nlink; } + + list_pair->last_node = nlink; } -void BLI_linklist_append(LinkNode **listp, void *ptr) +void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) { LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); - BLI_linklist_append_nlink(listp, ptr, nlink); + BLI_linklist_append_nlink(list_pair, ptr, nlink); } -void BLI_linklist_append_arena(LinkNode **listp, void *ptr, MemArena *ma) +void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, MemArena *ma) { LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink)); - BLI_linklist_append_nlink(listp, ptr, nlink); + BLI_linklist_append_nlink(list_pair, ptr, nlink); } -void BLI_linklist_append_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool) +void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, BLI_mempool *mempool) { LinkNode *nlink = BLI_mempool_alloc(mempool); - BLI_linklist_append_nlink(listp, ptr, nlink); + BLI_linklist_append_nlink(list_pair, ptr, nlink); } void *BLI_linklist_pop(struct LinkNode **listp) @@ -230,7 +232,7 @@ void *BLI_linklist_pop(struct LinkNode **listp) void *link = (*listp)->link; void *next = (*listp)->next; - MEM_freeN((*listp)); + MEM_freeN(*listp); *listp = next; return link; @@ -308,3 +310,40 @@ void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdat for (; list; list = list->next) applyfunc(list->link, userdata); } + +/* -------------------------------------------------------------------- */ +/* Sort */ +#define SORT_IMPL_LINKTYPE LinkNode +#define SORT_IMPL_LINKTYPE_DATA link + +/* regular call */ +#define SORT_IMPL_FUNC linklist_sort_fn +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC + +/* reentrant call */ +#define SORT_IMPL_USE_THUNK +#define SORT_IMPL_FUNC linklist_sort_fn_r +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC +#undef SORT_IMPL_USE_THUNK + +#undef SORT_IMPL_LINKTYPE +#undef SORT_IMPL_LINKTYPE_DATA + + +LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)) +{ + if (list && list->next) { + list = linklist_sort_fn(list, cmp); + } + return list; +} + +LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk) +{ + if (list && list->next) { + list = linklist_sort_fn_r(list, cmp, thunk); + } + return list; +} diff --git a/source/blender/blenlib/intern/array_utils.c b/source/blender/blenlib/intern/array_utils.c index 173effbc434..6c5dc5a7f1e 100644 --- a/source/blender/blenlib/intern/array_utils.c +++ b/source/blender/blenlib/intern/array_utils.c @@ -25,23 +25,28 @@ #include <string.h> #include <stdlib.h> +#include "MEM_guardedalloc.h" + #include "BLI_array_utils.h" #include "BLI_sys_types.h" #include "BLI_utildefines.h" #include "BLI_alloca.h" +#include "BLI_strict_flags.h" + void _bli_array_reverse(void *arr_v, unsigned int arr_len, size_t arr_stride) { - const unsigned int arr_half_stride = (arr_len / 2) * arr_stride; + const unsigned int arr_stride_uint = (unsigned int)arr_stride; + const unsigned int arr_half_stride = (arr_len / 2) * arr_stride_uint; unsigned int i, i_end; char *arr = arr_v; char *buf = BLI_array_alloca(buf, arr_stride); - for (i = 0, i_end = (arr_len - 1) * arr_stride; + for (i = 0, i_end = (arr_len - 1) * arr_stride_uint; i < arr_half_stride; - i += arr_stride, i_end -= arr_stride) + i += arr_stride_uint, i_end -= arr_stride_uint) { memcpy(buf, &arr[i], arr_stride); memcpy(&arr[i], &arr[i_end], arr_stride); @@ -69,6 +74,36 @@ void _bli_array_wrap(void *arr_v, unsigned int arr_len, size_t arr_stride, int d } } +void _bli_array_permute( + void *arr_v, const unsigned int arr_len, const size_t arr_stride, + const unsigned int *order, void *arr_temp) +{ + const size_t len = arr_len * arr_stride; + const unsigned int arr_stride_uint = (unsigned int)arr_stride; + void *arr_orig; + unsigned int i; + + if (arr_temp == NULL) { + arr_orig = MEM_mallocN(len, __func__); + } + else { + arr_orig = arr_temp; + } + + memcpy(arr_orig, arr_v, len); + + for (i = 0; i < arr_len; i++) { + BLI_assert(order[i] < arr_len); + memcpy(POINTER_OFFSET(arr_v, arr_stride_uint * i), + POINTER_OFFSET(arr_orig, arr_stride_uint * order[i]), + arr_stride); + } + + if (arr_temp == NULL) { + MEM_freeN(arr_orig); + } +} + /** * \note Not efficient, use for error checks/asserts. */ diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c index b7b41d2497e..21d974de1c4 100644 --- a/source/blender/blenlib/intern/astar.c +++ b/source/blender/blenlib/intern/astar.c @@ -165,18 +165,6 @@ void BLI_astar_solution_free(BLI_AStarSolution *as_solution) } /** - * Callback computing the current cost (distance) to next node, and the estimated overall cost to destination node - * (A* expects this estimation to always be less or equal than actual shortest path from next node to destination one). - * - * \param link the graph link between current node and next one. - * \param node_idx_curr current node index. - * \param node_idx_next next node index. - * \param node_idx_dst destination node index. - */ -typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link, - const int node_idx_curr, const int node_idx_next, const int node_idx_dst); - -/** * Init an A* graph. Total number of nodes must be known. * * Nodes might be e.g. vertices, faces, ... @@ -229,7 +217,7 @@ bool BLI_astar_graph_solve( r_solution->steps = 0; prev_nodes[node_index_src] = -1; BLI_BITMAP_SET_ALL(done_nodes, false, as_graph->node_num); - fill_vn_fl(g_costs, as_graph->node_num, FLT_MAX); + copy_vn_fl(g_costs, as_graph->node_num, FLT_MAX); g_costs[node_index_src] = 0.0f; g_steps[node_index_src] = 0; diff --git a/source/blender/blenlib/intern/convexhull2d.c b/source/blender/blenlib/intern/convexhull2d.c index 5f64088f433..740f3cce4a4 100644 --- a/source/blender/blenlib/intern/convexhull2d.c +++ b/source/blender/blenlib/intern/convexhull2d.c @@ -239,7 +239,7 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) * * Intended to be used with #BLI_convexhull_2d * - * \param points Orded hull points + * \param points_hull Ordered hull points * (result of #BLI_convexhull_2d mapped to a contiguous array). * * \note we could return the index of the best edge too if its needed. diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 82d57dad753..cde4a8bf59d 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -240,6 +240,30 @@ BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsign e->next = eh->buckets[hash]; e->v0 = v0; e->v1 = v1; + eh->buckets[hash] = e; + + if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { + edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); + } +} + +/** + * Insert function that doesn't set the value (use for EdgeSet) + */ +BLI_INLINE void edgehash_insert_ex_keyonly_entry( + EdgeHash *eh, unsigned int v0, unsigned int v1, + unsigned int hash, + EdgeEntry *e) +{ + BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); + + /* this helps to track down errors with bad edge data */ + BLI_assert(v0 < v1); + BLI_assert(v0 != v1); + + e->next = eh->buckets[hash]; + e->v0 = v0; + e->v1 = v1; /* intentionally leave value unset */ eh->buckets[hash] = e; @@ -373,6 +397,40 @@ void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) } /** + * Ensure \a (v0, v1) is exists in \a eh. + * + * This handles the common situation where the caller needs ensure a key is added to \a eh, + * constructing a new value in the case the key isn't found. + * Otherwise use the existing value. + * + * Such situations typically incur multiple lookups, however this function + * avoids them by ensuring the key is added, + * returning a pointer to the value so it can be used or initialized by the caller. + * + * \returns true when the value didn't need to be added. + * (when false, the caller _must_ initialize the value). + */ +bool BLI_edgehash_ensure_p(EdgeHash *eh, unsigned int v0, unsigned int v1, void ***r_val) +{ + unsigned int hash; + EdgeEntry *e; + bool haskey; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + e = edgehash_lookup_entry_ex(eh, v0, v1, hash); + haskey = (e != NULL); + + if (!haskey) { + e = BLI_mempool_alloc(eh->epool); + edgehash_insert_ex_keyonly_entry(eh, v0, v1, hash, e); + } + + *r_val = &e->val; + return haskey; +} + +/** * Return value for given edge (\a v0, \a v1), or NULL if * if key does not exist in hash. (If need exists * to differentiate between key-value being NULL and @@ -396,9 +454,9 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1 } /** - * Remove \a key from \a eh, or return false if the key wasn't found. + * Remove \a key (v0, v1) from \a eh, or return false if the key wasn't found. * - * \param key The key to remove. + * \param v0, v1: The key to remove. * \param valfreefp Optional callback to free the value. * \return true if \a key was removed from \a eh. */ @@ -422,9 +480,9 @@ bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHas /* same as above but return the value, * no free value argument since it will be returned */ /** - * Remove \a key from \a eh, returning the value or NULL if the key wasn't found. + * Remove \a key (v0, v1) from \a eh, returning the value or NULL if the key wasn't found. * - * \param key The key to remove. + * \param v0, v1: The key to remove. * \return the value of \a key int \a eh or NULL. */ void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c index d6fe5e52b95..c3e889842c1 100644 --- a/source/blender/blenlib/intern/fileops.c +++ b/source/blender/blenlib/intern/fileops.c @@ -657,21 +657,29 @@ static int delete_single_file(const char *from, const char *UNUSED(to)) FILE *BLI_fopen(const char *filename, const char *mode) { + BLI_assert(!BLI_path_is_rel(filename)); + return fopen(filename, mode); } void *BLI_gzopen(const char *filename, const char *mode) { + BLI_assert(!BLI_path_is_rel(filename)); + return gzopen(filename, mode); } int BLI_open(const char *filename, int oflag, int pmode) { + BLI_assert(!BLI_path_is_rel(filename)); + return open(filename, oflag, pmode); } int BLI_access(const char *filename, int mode) { + BLI_assert(!BLI_path_is_rel(filename)); + return access(filename, mode); } @@ -682,6 +690,8 @@ int BLI_access(const char *filename, int mode) */ int BLI_delete(const char *file, bool dir, bool recursive) { + BLI_assert(!BLI_path_is_rel(file)); + if (recursive) { return recursive_operation(file, NULL, NULL, delete_single_file, delete_callback_post); } diff --git a/source/blender/blenlib/intern/freetypefont.c b/source/blender/blenlib/intern/freetypefont.c index b3392e28223..8719c92a2a6 100644 --- a/source/blender/blenlib/intern/freetypefont.c +++ b/source/blender/blenlib/intern/freetypefont.c @@ -507,8 +507,7 @@ VChar *BLI_vfontchar_from_freetypefont(VFont *vfont, unsigned long character) /* Freetype2 Outline struct */ -typedef struct FT_Outline_ -{ +typedef struct FT_Outline_ { short n_contours; /* number of contours in glyph */ short n_points; /* number of points in the glyph */ diff --git a/source/blender/blenlib/intern/gsqueue.c b/source/blender/blenlib/intern/gsqueue.c index 94d18ce3c77..f1aff76b358 100644 --- a/source/blender/blenlib/intern/gsqueue.c +++ b/source/blender/blenlib/intern/gsqueue.c @@ -96,8 +96,8 @@ int BLI_gsqueue_size(GSQueue *gq) * Access the item at the head of the queue * without removing it. * - * \param item_r A pointer to an appropriately - * sized structure (the size passed to BLI_gsqueue_new) + * \param r_item: A pointer to an appropriately + * sized structure (the size passed to #BLI_gsqueue_new) */ void BLI_gsqueue_peek(GSQueue *gq, void *r_item) { @@ -108,8 +108,8 @@ void BLI_gsqueue_peek(GSQueue *gq, void *r_item) * Access the item at the head of the queue * and remove it. * - * \param item_r A pointer to an appropriately - * sized structure (the size passed to BLI_gsqueue_new). + * \param r_item: A pointer to an appropriately + * sized structure (the size passed to #BLI_gsqueue_new). * Can be NULL if desired. */ void BLI_gsqueue_pop(GSQueue *gq, void *r_item) diff --git a/source/blender/blenlib/intern/hash_md5.c b/source/blender/blenlib/intern/hash_md5.c index 4eec38278e9..d98b915983c 100644 --- a/source/blender/blenlib/intern/hash_md5.c +++ b/source/blender/blenlib/intern/hash_md5.c @@ -81,8 +81,7 @@ * 'BLI_hash_md5_stream' and 'BLI_hash_md5_buffer'. */ /* Structure to save state of computation between the single steps. */ -struct md5_ctx -{ +struct md5_ctx { md5_uint32 A; md5_uint32 B; md5_uint32 C; diff --git a/source/blender/blenlib/intern/list_sort_impl.h b/source/blender/blenlib/intern/list_sort_impl.h new file mode 100644 index 00000000000..249ed470d6e --- /dev/null +++ b/source/blender/blenlib/intern/list_sort_impl.h @@ -0,0 +1,341 @@ +/* + * ***** 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/list_sort_impl.h + * \ingroup bli + * + * Common implementation of linked-list a non-recursive mergesort. + * + * Originally from Mono's eglib, adapted for portable inclusion. + * This file is to be directly included in C-source, + * with defines to control its use. + * + * This code requires a typedef named `SORT_IMPL_LINKTYPE` for the list node. + * It is assumed that the list type is the type of a pointer to a list + * node, and that the node has a field named 'next' that implements to + * the linked list. No additional invariant is maintained + * (e.g. the `prev` pointer of a doubly-linked list node is _not_ updated). + * Any invariant would require a post-processing pass to update `prev`. + * + * Source file including this must define: + * - `SORT_IMPL_LINKTYPE`: + * Struct type for sorting. + * - `SORT_IMPL_LINKTYPE_DATA`: + * Data pointer or leave undefined to pass the link its self. + * - `SORT_IMPL_FUNC`: + * Function name of the sort function. + * + * Optionally: + * - `SORT_IMPL_USE_THUNK`: + * Takes an argument for the sort function (like `qsort_r`). + */ + +/* -------------------------------------------------------------------- */ +/* Handle External Defines */ + +/* check we're not building directly */ +#if !defined(SORT_IMPL_LINKTYPE) || !defined(SORT_IMPL_FUNC) +# error "This file can't be compiled directly, include in another source file" +#endif + +#define list_node SORT_IMPL_LINKTYPE +#define list_sort_do SORT_IMPL_FUNC + +#ifdef SORT_IMPL_LINKTYPE_DATA +# define SORT_ARG(n) ((n)->SORT_IMPL_LINKTYPE_DATA) +#else +# define SORT_ARG(n) (n) +#endif + +#ifdef SORT_IMPL_USE_THUNK +# define THUNK_APPEND1(a, thunk) a, thunk +# define THUNK_PREPEND2(thunk, a, b) thunk, a, b +#else +# define THUNK_APPEND1(a, thunk) a +# define THUNK_PREPEND2(thunk, a, b) a, b +#endif + +#define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2 +#define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) +#define _SORT_PREFIX(id) _CONCAT(SORT_IMPL_FUNC, _##id) + +/* local identifiers */ +#define SortInfo _SORT_PREFIX(SortInfo) +#define CompareFn _SORT_PREFIX(CompareFn) +#define init_sort_info _SORT_PREFIX(init_sort_info) +#define merge_lists _SORT_PREFIX(merge_lists) +#define sweep_up _SORT_PREFIX(sweep_up) +#define insert_list _SORT_PREFIX(insert_list) + +typedef int (* CompareFn)( +#ifdef SORT_IMPL_USE_THUNK + void *thunk, +#endif + const void *, + const void *); + + +/* -------------------------------------------------------------------- */ +/* MIT license from original source */ + +/* + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + * Author: + * Raja R Harinath (rharinath@novell.com) + */ + +/** + * The maximum possible depth of the merge tree + * - `ceiling(log2(maximum number of list nodes))` + * - `ceiling(log2(maximum possible memory size/size of each list node))` + * - number of bits in `'size_t' - floor(log2(sizeof(list_node *)))` + * + * Also, each list in #SortInfo is at least 2 nodes long: + * we can reduce the depth by 1. + */ +#define FLOOR_LOG2(x) \ + (((x) >= 2) + ((x) >= 4) + ((x) >= 8) + ((x) >= 16) + ((x) >= 32) + ((x) >= 64) + ((x) >= 128)) +#define MAX_RANKS \ + ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1) + +struct SortInfo { + unsigned int min_rank, n_ranks; + CompareFn func; + +#ifdef SORT_IMPL_USE_THUNK + void *thunk; +#endif + + /** + * Invariant: `ranks[i] == NULL || length(ranks[i]) >= 2**(i+1)`. + * + * ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */ + list_node *ranks[MAX_RANKS]; +}; + +BLI_INLINE void init_sort_info( + struct SortInfo *si, + CompareFn func +#ifdef SORT_IMPL_USE_THUNK + , + void *thunk +#endif + ) +{ + si->min_rank = si->n_ranks = 0; + si->func = func; + /* we don't need to initialize si->ranks, + * since we never lookup past si->n_ranks. */ + +#ifdef SORT_IMPL_USE_THUNK + si->thunk = thunk; +#endif +} + +BLI_INLINE list_node *merge_lists( + list_node *first, list_node *second, + CompareFn func +#ifdef SORT_IMPL_USE_THUNK + , + void *thunk +#endif + ) +{ + /* merge the two lists */ + list_node *list = NULL; + list_node **pos = &list; + while (first && second) { + if (func(THUNK_PREPEND2(thunk, SORT_ARG(first), SORT_ARG(second))) > 0) { + *pos = second; + second = second->next; + } + else { + *pos = first; + first = first->next; + } + pos = &((*pos)->next); + } + *pos = first ? first : second; + return list; +} + +/** + * Pre-condition: + * `upto <= si->n_ranks, list == NULL || length(list) == 1` + */ +BLI_INLINE list_node *sweep_up(struct SortInfo *si, list_node *list, unsigned int upto) +{ + unsigned int i; + for (i = si->min_rank; i < upto; i++) { + list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk)); + si->ranks[i] = NULL; + } + return list; +} + +/** + * The 'ranks' array essentially captures the recursion stack of a mergesort. + * The merge tree is built in a bottom-up manner. The control loop for + * updating the 'ranks' array is analogous to incrementing a binary integer, + * and the `O(n)` time for counting upto n translates to `O(n)` merges when + * inserting `rank-0` lists. + * When we plug in the sizes of the lists involved in those merges, + * we get the `O(n log n)` time for the sort. + * + * Inserting higher-ranked lists reduce the height of the merge tree, + * and also eliminate a lot of redundant comparisons when merging two lists + * that would've been part of the same run. + * Adding a `rank-i` list is analogous to incrementing a binary integer by + * `2**i` in one operation, thus sharing a similar speedup. + * + * When inserting higher-ranked lists, we choose to clear out the lower ranks + * in the interests of keeping the sort stable, but this makes analysis harder. + * Note that clearing the lower-ranked lists is `O(length(list))--` thus it + * shouldn't affect the `O(n log n)` behaviour. + * In other words, inserting one `rank-i` list is equivalent to inserting + * `2**i` `rank-0` lists, thus even if we do `i` additional merges + * in the clearing-out (taking at most `2**i` time) we are still fine. + */ + +/** + * Pre-condition: + * `2**(rank+1) <= length(list) < 2**(rank+2)` + * (therefore: `length(list) >= 2`) + */ +BLI_INLINE void insert_list( + struct SortInfo *si, + list_node *list, + unsigned int rank) +{ + unsigned int i; + + if (rank > si->n_ranks) { + if (UNLIKELY(rank > MAX_RANKS)) { + // printf("Rank '%d' should not exceed " STRINGIFY(MAX_RANKS), rank); + rank = MAX_RANKS; + } + list = merge_lists(sweep_up(si, NULL, si->n_ranks), list, THUNK_APPEND1(si->func, si->thunk)); + for (i = si->n_ranks; i < rank; ++i) { + si->ranks[i] = NULL; + } + } + else { + if (rank) { + list = merge_lists(sweep_up(si, NULL, rank), list, THUNK_APPEND1(si->func, si->thunk)); + } + for (i = rank; i < si->n_ranks && si->ranks[i]; ++i) { + list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk)); + si->ranks[i] = NULL; + } + } + + /* Will _never_ happen: so we can just devolve into quadratic ;-) */ + if (UNLIKELY(i == MAX_RANKS)) { + i--; + } + + if (i >= si->n_ranks) { + si->n_ranks = i + 1; + } + + si->min_rank = i; + si->ranks[i] = list; +} + +#undef MAX_RANKS +#undef FLOOR_LOG2 + +/** + * Main sort function. + */ +BLI_INLINE list_node *list_sort_do( + list_node *list, + CompareFn func +#ifdef SORT_IMPL_USE_THUNK + , + void *thunk +#endif + ) +{ + struct SortInfo si; + + init_sort_info( + &si, + func +#ifdef SORT_IMPL_USE_THUNK + , + thunk +#endif + ); + + while (list && list->next) { + list_node *next = list->next; + list_node *tail = next->next; + + if (func(THUNK_PREPEND2(thunk, SORT_ARG(list), SORT_ARG(next))) > 0) { + next->next = list; + next = list; + list = list->next; + } + next->next = NULL; + + insert_list(&si, list, 0); + + list = tail; + } + + return sweep_up(&si, list, si.n_ranks); +} + +#undef _CONCAT_AUX +#undef _CONCAT +#undef _SORT_PREFIX + +#undef SortInfo +#undef CompareFn +#undef init_sort_info +#undef merge_lists +#undef sweep_up +#undef insert_list + +#undef list_node +#undef list_sort_do + +#undef THUNK_APPEND1 +#undef THUNK_PREPEND2 +#undef SORT_ARG diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c index d52c09790f9..ebee2c7941c 100644 --- a/source/blender/blenlib/intern/listbase.c +++ b/source/blender/blenlib/intern/listbase.c @@ -42,6 +42,8 @@ #include "BLI_listbase.h" +#include "BLI_strict_flags.h" + /* implementation */ /** @@ -205,53 +207,56 @@ void BLI_freelinkN(ListBase *listbase, void *vlink) MEM_freeN(link); } +/** + * Assigns all #Link.prev pointers from #Link.next + */ +static void listbase_double_from_single(Link *iter, ListBase *listbase) +{ + Link *prev = NULL; + listbase->first = iter; + do { + iter->prev = prev; + prev = iter; + } while ((iter = iter->next)); + listbase->last = prev; +} + +#define SORT_IMPL_LINKTYPE Link + +/* regular call */ +#define SORT_IMPL_FUNC listbase_sort_fn +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC + +/* reentrant call */ +#define SORT_IMPL_USE_THUNK +#define SORT_IMPL_FUNC listbase_sort_fn_r +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC +#undef SORT_IMPL_USE_THUNK + +#undef SORT_IMPL_LINKTYPE /** * Sorts the elements of listbase into the order defined by cmp - * (which should return 1 iff its first arg should come after its second arg). + * (which should return 1 if its first arg should come after its second arg). * This uses insertion sort, so NOT ok for large list. */ void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *)) { - Link *current = NULL; - Link *previous = NULL; - Link *next = NULL; - if (listbase->first != listbase->last) { - for (previous = listbase->first, current = previous->next; current; current = next) { - next = current->next; - previous = current->prev; - - BLI_remlink(listbase, current); - - while (previous && cmp(previous, current) == 1) { - previous = previous->prev; - } - - BLI_insertlinkafter(listbase, previous, current); - } + Link *head = listbase->first; + head = listbase_sort_fn(head, cmp); + listbase_double_from_single(head, listbase); } } -void BLI_listbase_sort_r(ListBase *listbase, void *thunk, int (*cmp)(void *, const void *, const void *)) +void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk) { - Link *current = NULL; - Link *previous = NULL; - Link *next = NULL; - if (listbase->first != listbase->last) { - for (previous = listbase->first, current = previous->next; current; current = next) { - next = current->next; - previous = current->prev; - - BLI_remlink(listbase, current); - - while (previous && cmp(thunk, previous, current) == 1) { - previous = previous->prev; - } - - BLI_insertlinkafter(listbase, previous, current); - } + Link *head = listbase->first; + head = listbase_sort_fn_r(head, cmp, thunk); + listbase_double_from_single(head, listbase); } } diff --git a/source/blender/blenlib/intern/math_base.c b/source/blender/blenlib/intern/math_base.c index 3ff1af3513e..0a1e9e8a8a1 100644 --- a/source/blender/blenlib/intern/math_base.c +++ b/source/blender/blenlib/intern/math_base.c @@ -31,41 +31,20 @@ #include "BLI_strict_flags.h" -/* WARNING: MSVC compiling hack for double_round() */ -#if (defined(WIN32) || defined(WIN64)) && !(defined(FREE_WINDOWS)) - -/* from python 3.1 pymath.c */ -double copysign(double x, double y) +int pow_i(int base, int exp) { - /* use atan2 to distinguish -0.0 from 0.0 */ - if (y > 0.0 || (y == 0.0 && atan2(y, -1.0) > 0.0)) { - return fabs(x); - } - else { - return -fabs(x); + int result = 1; + BLI_assert(exp >= 0); + while (exp) { + if (exp & 1) { + result *= base; + } + exp >>= 1; + base *= base; } -} -/* from python 3.1 pymath.c */ -double round(double x) -{ - double absx, y; - absx = fabs(x); - y = floor(absx); - if (absx - y >= 0.5) - y += 1.0; - return copysign(y, x); + return result; } -#else /* OpenSuse 11.1 seems to need this. */ -# ifdef __GNUC__ -# pragma GCC diagnostic push -# pragma GCC diagnostic ignored "-Wredundant-decls" -# endif -double round(double x); -# ifdef __GNUC__ -# pragma GCC diagnostic pop -# endif -#endif /* from python 3.1 floatobject.c * ndigits must be between 0 and 21 */ diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index f5713824296..facee8b0a89 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -198,25 +198,6 @@ MINLINE int mod_i(int i, int n) return (i % n + n) % n; } -MINLINE unsigned int highest_order_bit_i(unsigned int n) -{ - n |= (n >> 1); - n |= (n >> 2); - n |= (n >> 4); - n |= (n >> 8); - n |= (n >> 16); - return n - (n >> 1); -} - -MINLINE unsigned short highest_order_bit_s(unsigned short n) -{ - n |= (n >> 1); - n |= (n >> 2); - n |= (n >> 4); - n |= (n >> 8); - return (unsigned short)(n - (n >> 1)); -} - MINLINE float min_ff(float a, float b) { return (a < b) ? a : b; diff --git a/source/blender/blenlib/intern/math_bits_inline.c b/source/blender/blenlib/intern/math_bits_inline.c new file mode 100644 index 00000000000..11ee6e7fa5b --- /dev/null +++ b/source/blender/blenlib/intern/math_bits_inline.c @@ -0,0 +1,59 @@ +/* + * ***** 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/math_bits_inline.c + * \ingroup bli + */ + +#ifndef __MATH_BITS_INLINE_C__ +#define __MATH_BITS_INLINE_C__ + +#include "BLI_math_bits.h" + +MINLINE unsigned int highest_order_bit_i(unsigned int n) +{ + n |= (n >> 1); + n |= (n >> 2); + n |= (n >> 4); + n |= (n >> 8); + n |= (n >> 16); + return n - (n >> 1); +} + +MINLINE unsigned short highest_order_bit_s(unsigned short n) +{ + n |= (n >> 1); + n |= (n >> 2); + n |= (n >> 4); + n |= (n >> 8); + return (unsigned short)(n - (n >> 1)); +} + +#ifndef __GNUC__ +MINLINE int count_bits_i(unsigned int i) +{ + /* variable-precision SWAR algorithm. */ + i = i - ((i >> 1) & 0x55555555); + i = (i & 0x33333333) + ((i >> 2) & 0x33333333); + return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; +} +#endif + +#endif /* __MATH_BITS_INLINE_C__ */ diff --git a/source/blender/blenlib/intern/math_color_inline.c b/source/blender/blenlib/intern/math_color_inline.c index 0e955c1602e..45466226e72 100644 --- a/source/blender/blenlib/intern/math_color_inline.c +++ b/source/blender/blenlib/intern/math_color_inline.c @@ -211,20 +211,30 @@ MINLINE void cpack_cpy_3ub(unsigned char r_col[3], const unsigned int pack) * * \{ */ -/* non-linear luma from ITU-R BT.601-2 - * see: http://www.poynton.com/notes/colour_and_gamma/ColorFAQ.html#RTFToC11 - * note: the values used for are not exact matches to those documented above, - * but they are from the same */ +/** + * ITU-R BT.709 primaries + * http://en.wikipedia.org/wiki/Relative_luminance + * + * Real values are: + * ``Y = 0.2126390059(R) + 0.7151686788(G) + 0.0721923154(B)`` + * according to: "Derivation of Basic Television Color Equations", RP 177-1993 + * + * As this sums slightly above 1.0, the document recommends to use: + * ``0.2126(R) + 0.7152(G) + 0.0722(B)``, as used here. + * + * The high precision values are used to calculate the rounded byte weights so they add up to 255: + * ``54(R) + 182(G) + 19(B)`` + */ MINLINE float rgb_to_grayscale(const float rgb[3]) { - return 0.3f * rgb[0] + 0.58f * rgb[1] + 0.12f * rgb[2]; + return (0.2126f * rgb[0]) + (0.7152f * rgb[1]) + (0.0722f * rgb[2]); } MINLINE unsigned char rgb_to_grayscale_byte(const unsigned char rgb[3]) { - return (unsigned char)(((76 * (unsigned short)rgb[0]) + - (148 * (unsigned short)rgb[1]) + - (31 * (unsigned short)rgb[2])) / 255); + return (unsigned char)(((54 * (unsigned short)rgb[0]) + + (182 * (unsigned short)rgb[1]) + + (19 * (unsigned short)rgb[2])) / 255); } /** \} */ diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index ba1f4480659..7329a1177a8 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -442,6 +442,22 @@ float dist_squared_to_plane_v3(const float pt[3], const float plane[4]) return len_sq * (fac * fac); } +float dist_signed_squared_to_plane3_v3(const float pt[3], const float plane[3]) +{ + const float len_sq = len_squared_v3(plane); + const float side = dot_v3v3(plane, pt); /* only difference with 'plane[4]' version */ + const float fac = side / len_sq; + return copysignf(len_sq * (fac * fac), side); +} +float dist_squared_to_plane3_v3(const float pt[3], const float plane[3]) +{ + const float len_sq = len_squared_v3(plane); + const float side = dot_v3v3(plane, pt); /* only difference with 'plane[4]' version */ + const float fac = side / len_sq; + /* only difference to code above - no 'copysignf' */ + return len_sq * (fac * fac); +} + /** * Return the signed distance from the point to the plane. */ @@ -457,6 +473,18 @@ float dist_to_plane_v3(const float pt[3], const float plane[4]) return fabsf(dist_signed_to_plane_v3(pt, plane)); } +float dist_signed_to_plane3_v3(const float pt[3], const float plane[3]) +{ + const float len_sq = len_squared_v3(plane); + const float side = dot_v3v3(plane, pt); /* only difference with 'plane[4]' version */ + const float fac = side / len_sq; + return sqrtf(len_sq) * fac; +} +float dist_to_plane3_v3(const float pt[3], const float plane[3]) +{ + return fabsf(dist_signed_to_plane3_v3(pt, plane)); +} + /* distance v1 to line-piece l1-l2 in 3D */ float dist_squared_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]) { @@ -514,9 +542,10 @@ float dist_signed_squared_to_corner_v3v3v3( const float axis_ref[3]) { float dir_a[3], dir_b[3]; - float plane_a[4], plane_b[4]; + float plane_a[3], plane_b[3]; float dist_a, dist_b; float axis[3]; + float s_p_v2[3]; bool flip = false; sub_v3_v3v3(dir_a, v1, v2); @@ -537,16 +566,20 @@ float dist_signed_squared_to_corner_v3v3v3( cross_v3_v3v3(plane_b, axis, dir_b); #if 0 - plane_from_point_normal_v3(plane_a, center, l1); - plane_from_point_normal_v3(plane_b, center, l2); -#else - /* do inline */ - plane_a[3] = -dot_v3v3(plane_a, v2); - plane_b[3] = -dot_v3v3(plane_b, v2); -#endif + plane_from_point_normal_v3(plane_a, v2, plane_a); + plane_from_point_normal_v3(plane_b, v2, plane_b); dist_a = dist_signed_squared_to_plane_v3(p, plane_a); dist_b = dist_signed_squared_to_plane_v3(p, plane_b); +#else + /* calculate without he planes 4th component to avoid float precision issues */ + sub_v3_v3v3(s_p_v2, p, v2); + + dist_a = dist_signed_squared_to_plane3_v3(s_p_v2, plane_a); + dist_b = dist_signed_squared_to_plane3_v3(s_p_v2, plane_b); +#endif + + if (flip) { return min_ff(dist_a, dist_b); @@ -697,37 +730,73 @@ int isect_line_line_v2(const float v1[2], const float v2[2], const float v3[2], * -1: collinear * 1: intersection */ -int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[2], const float v4[2], float vi[2]) +int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2]) { - float a1, a2, b1, b2, c1, c2, d; - float u, v; + float s10[2], s32[2], s30[2], d; const float eps = 1e-6f; const float eps_sq = eps * eps; - a1 = v2[0] - v1[0]; - b1 = v4[0] - v3[0]; - c1 = v1[0] - v4[0]; + sub_v2_v2v2(s10, v1, v0); + sub_v2_v2v2(s32, v3, v2); + sub_v2_v2v2(s30, v3, v0); + + d = cross_v2v2(s10, s32); + + if (d != 0) { + float u, v; + + u = cross_v2v2(s30, s32) / d; + v = cross_v2v2(s10, s30) / d; + + if ((u >= -eps && u <= 1.0f + eps) && + (v >= -eps && v <= 1.0f + eps)) + { + /* intersection */ + float vi_test[2]; + float s_vi_v2[2]; - a2 = v2[1] - v1[1]; - b2 = v4[1] - v3[1]; - c2 = v1[1] - v4[1]; + madd_v2_v2v2fl(vi_test, v0, s10, u); - d = a1 * b2 - a2 * b1; + /* When 'd' approaches zero, float precision lets non-overlapping co-linear segments + * detect as an intersection. So re-calculate 'v' to ensure the point overlaps both. + * see T45123 */ - if (d == 0) { - if (a1 * c2 - a2 * c1 == 0.0f && b1 * c2 - b2 * c1 == 0.0f) { /* equal lines */ - float a[2], b[2], c[2]; - float u2; + /* inline since we have most vars already */ +#if 0 + v = line_point_factor_v2(ix_test, v2, v3); +#else + sub_v2_v2v2(s_vi_v2, vi_test, v2); + v = (dot_v2v2(s32, s_vi_v2) / dot_v2v2(s32, s32)); +#endif + if (v >= -eps && v <= 1.0f + eps) { + copy_v2_v2(r_vi, vi_test); + return 1; + } + } - if (equals_v2v2(v1, v2)) { - if (len_squared_v2v2(v3, v4) > eps_sq) { + /* out of segment intersection */ + return -1; + } + else { + if ((cross_v2v2(s10, s30) == 0.0f) && + (cross_v2v2(s32, s30) == 0.0f)) + { + /* equal lines */ + float s20[2]; + float u_a, u_b; + + if (equals_v2v2(v0, v1)) { + if (len_squared_v2v2(v2, v3) > eps_sq) { /* use non-point segment as basis */ + SWAP(const float *, v0, v2); SWAP(const float *, v1, v3); - SWAP(const float *, v2, v4); + + sub_v2_v2v2(s10, v1, v0); + sub_v2_v2v2(s30, v3, v0); } else { /* both of segments are points */ - if (equals_v2v2(v1, v3)) { /* points are equal */ - copy_v2_v2(vi, v1); + if (equals_v2v2(v0, v2)) { /* points are equal */ + copy_v2_v2(r_vi, v0); return 1; } @@ -736,19 +805,21 @@ int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[ } } - sub_v2_v2v2(a, v3, v1); - sub_v2_v2v2(b, v2, v1); - sub_v2_v2v2(c, v2, v1); - u = dot_v2v2(a, b) / dot_v2v2(c, c); + sub_v2_v2v2(s20, v2, v0); - sub_v2_v2v2(a, v4, v1); - u2 = dot_v2v2(a, b) / dot_v2v2(c, c); + u_a = dot_v2v2(s20, s10) / dot_v2v2(s10, s10); + u_b = dot_v2v2(s30, s10) / dot_v2v2(s10, s10); - if (u > u2) SWAP(float, u, u2); + if (u_a > u_b) + SWAP(float, u_a, u_b); - if (u > 1.0f + eps || u2 < -eps) return -1; /* non-ovlerlapping segments */ - else if (max_ff(0.0f, u) == min_ff(1.0f, u2)) { /* one common point: can return result */ - interp_v2_v2v2(vi, v1, v2, max_ff(0, u)); + if (u_a > 1.0f + eps || u_b < -eps) { + /* non-overlapping segments */ + return -1; + } + else if (max_ff(0.0f, u_a) == min_ff(1.0f, u_b)) { + /* one common point: can return result */ + madd_v2_v2v2fl(r_vi, v0, s10, max_ff(0, u_a)); return 1; } } @@ -756,22 +827,13 @@ int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[ /* lines are collinear */ return -1; } - - u = (c2 * b1 - b2 * c1) / d; - v = (c1 * a2 - a1 * c2) / d; - - if (u >= -eps && u <= 1.0f + eps && v >= -eps && v <= 1.0f + eps) { /* intersection */ - interp_v2_v2v2(vi, v1, v2, u); - return 1; - } - - /* out of segment intersection */ - return -1; } bool isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]) { -#define CCW(A, B, C) ((C[1] - A[1]) * (B[0] - A[0]) > (B[1]-A[1]) * (C[0]-A[0])) +#define CCW(A, B, C) \ + ((C[1] - A[1]) * (B[0] - A[0]) > \ + (B[1] - A[1]) * (C[0] - A[0])) return CCW(v1, v3, v4) != CCW(v2, v3, v4) && CCW(v1, v2, v3) != CCW(v1, v2, v4); @@ -2337,7 +2399,7 @@ void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3]) transpose_m3(r_mat); BLI_assert(!is_negative_m3(r_mat)); - BLI_assert(fabsf(dot_m3_v3_row_z(r_mat, normal) - 1.0f) < BLI_ASSERT_UNIT_EPSILON); + BLI_assert((fabsf(dot_m3_v3_row_z(r_mat, normal) - 1.0f) < BLI_ASSERT_UNIT_EPSILON) || is_zero_v3(normal)); } /****************************** Interpolation ********************************/ @@ -3101,6 +3163,43 @@ void resolve_quad_uv_v2_deriv(float r_uv[2], float r_deriv[2][2], } } +/* a version of resolve_quad_uv_v2 that only calculates the 'u' */ +float resolve_quad_u_v2( + const float st[2], + const float st0[2], const float st1[2], const float st2[2], const float st3[2]) +{ + const double signed_area = (st0[0] * st1[1] - st0[1] * st1[0]) + (st1[0] * st2[1] - st1[1] * st2[0]) + + (st2[0] * st3[1] - st2[1] * st3[0]) + (st3[0] * st0[1] - st3[1] * st0[0]); + + /* X is 2D cross product (determinant) + * A = (p0 - p) X (p0 - p3)*/ + const double a = (st0[0] - st[0]) * (st0[1] - st3[1]) - (st0[1] - st[1]) * (st0[0] - st3[0]); + + /* B = ( (p0 - p) X (p1 - p2) + (p1 - p) X (p0 - p3) ) / 2 */ + const double b = 0.5 * (double)(((st0[0] - st[0]) * (st1[1] - st2[1]) - (st0[1] - st[1]) * (st1[0] - st2[0])) + + ((st1[0] - st[0]) * (st0[1] - st3[1]) - (st1[1] - st[1]) * (st0[0] - st3[0]))); + + /* C = (p1-p) X (p1-p2) */ + const double fC = (st1[0] - st[0]) * (st1[1] - st2[1]) - (st1[1] - st[1]) * (st1[0] - st2[0]); + double denom = a - 2 * b + fC; + + if (IS_ZERO(denom) != 0) { + const double fDen = a - fC; + if (IS_ZERO(fDen) == 0) + return (float)(a / fDen); + else + return 0.0f; + } + else { + const double desc_sq = b * b - a * fC; + const double desc = sqrt(desc_sq < 0.0 ? 0.0 : desc_sq); + const double s = signed_area > 0 ? (-1.0) : 1.0; + + return (float)(((a - b) + s * desc) / denom); + } +} + + #undef IS_ZERO /* reverse of the functions above */ diff --git a/source/blender/blenlib/intern/math_interp.c b/source/blender/blenlib/intern/math_interp.c index 67850463fe2..b45d8b4c13b 100644 --- a/source/blender/blenlib/intern/math_interp.c +++ b/source/blender/blenlib/intern/math_interp.c @@ -112,10 +112,10 @@ BLI_INLINE void bicubic_interpolation(const unsigned char *byte_buffer, const fl /* sample area entirely outside image? */ if (ceil(u) < 0 || floor(u) > width - 1 || ceil(v) < 0 || floor(v) > height - 1) { if (float_output) { - fill_vn_fl(float_output, components, 0.0f); + copy_vn_fl(float_output, components, 0.0f); } if (byte_output) { - fill_vn_uchar(byte_output, components, 0); + copy_vn_uchar(byte_output, components, 0); } return; } @@ -281,7 +281,7 @@ BLI_INLINE void bilinear_interpolation(const unsigned char *byte_buffer, const f /* sample area entirely outside image? */ if (x2 < 0 || x1 > width - 1 || y2 < 0 || y1 > height - 1) { - fill_vn_fl(float_output, components, 0.0f); + copy_vn_fl(float_output, components, 0.0f); return; } @@ -323,7 +323,7 @@ BLI_INLINE void bilinear_interpolation(const unsigned char *byte_buffer, const f /* sample area entirely outside image? */ if (x2 < 0 || x1 > width - 1 || y2 < 0 || y1 > height - 1) { - fill_vn_uchar(byte_output, components, 0); + copy_vn_uchar(byte_output, components, 0); return; } diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c index 1b4bbafdb04..a9afed7a63d 100644 --- a/source/blender/blenlib/intern/math_matrix.c +++ b/source/blender/blenlib/intern/math_matrix.c @@ -504,6 +504,16 @@ void mul_mat3_m4_v3(float mat[4][4], float vec[3]) vec[2] = x * mat[0][2] + y * mat[1][2] + mat[2][2] * vec[2]; } +void mul_v3_mat3_m4v3(float r[3], float mat[4][4], const float vec[3]) +{ + const float x = vec[0]; + const float y = vec[1]; + + r[0] = x * mat[0][0] + y * mat[1][0] + mat[2][0] * vec[2]; + r[1] = x * mat[0][1] + y * mat[1][1] + mat[2][1] * vec[2]; + r[2] = x * mat[0][2] + y * mat[1][2] + mat[2][2] * vec[2]; +} + void mul_project_m4_v3(float mat[4][4], float vec[3]) { const float w = mul_project_m4_v3_zfac(mat, vec); @@ -1149,7 +1159,7 @@ bool is_orthogonal_m3(float m[3][3]) for (i = 0; i < 3; i++) { for (j = 0; j < i; j++) { - if (fabsf(dot_v3v3(m[i], m[j])) > 1.5f * FLT_EPSILON) + if (fabsf(dot_v3v3(m[i], m[j])) > 1e-5f) return false; } } @@ -1163,7 +1173,7 @@ bool is_orthogonal_m4(float m[4][4]) for (i = 0; i < 4; i++) { for (j = 0; j < i; j++) { - if (fabsf(dot_v4v4(m[i], m[j])) > 1.5f * FLT_EPSILON) + if (fabsf(dot_v4v4(m[i], m[j])) > 1e-5f) return false; } @@ -1178,7 +1188,7 @@ bool is_orthonormal_m3(float m[3][3]) int i; for (i = 0; i < 3; i++) - if (fabsf(dot_v3v3(m[i], m[i]) - 1) > 1.5f * FLT_EPSILON) + if (fabsf(dot_v3v3(m[i], m[i]) - 1) > 1e-5f) return false; return true; @@ -1193,7 +1203,7 @@ bool is_orthonormal_m4(float m[4][4]) int i; for (i = 0; i < 4; i++) - if (fabsf(dot_v4v4(m[i], m[i]) - 1) > 1.5f * FLT_EPSILON) + if (fabsf(dot_v4v4(m[i], m[i]) - 1) > 1e-5f) return false; return true; @@ -1465,39 +1475,14 @@ float mat4_to_scale(float mat[4][4]) void mat3_to_rot_size(float rot[3][3], float size[3], float mat3[3][3]) { - float mat3_n[3][3]; /* mat3 -> normalized, 3x3 */ - float imat3_n[3][3]; /* mat3 -> normalized & inverted, 3x3 */ - - /* rotation & scale are linked, we need to create the mat's - * for these together since they are related. */ - - /* so scale doesn't interfere with rotation [#24291] */ - /* note: this is a workaround for negative matrix not working for rotation conversion, FIXME */ - normalize_m3_m3(mat3_n, mat3); - if (is_negative_m3(mat3)) { - negate_m3(mat3_n); - } - - /* rotation */ /* keep rot as a 3x3 matrix, the caller can convert into a quat or euler */ - copy_m3_m3(rot, mat3_n); - - /* scale */ - /* note: mat4_to_size(ob->size, mat) fails for negative scale */ - invert_m3_m3(imat3_n, mat3_n); - - /* better not edit mat3 */ -#if 0 - mul_m3_m3m3(mat3, imat3_n, mat3); - - size[0] = mat3[0][0]; - size[1] = mat3[1][1]; - size[2] = mat3[2][2]; -#else - size[0] = dot_m3_v3_row_x(imat3_n, mat3[0]); - size[1] = dot_m3_v3_row_y(imat3_n, mat3[1]); - size[2] = dot_m3_v3_row_z(imat3_n, mat3[2]); -#endif + size[0] = normalize_v3_v3(rot[0], mat3[0]); + size[1] = normalize_v3_v3(rot[1], mat3[1]); + size[2] = normalize_v3_v3(rot[2], mat3[2]); + if (UNLIKELY(is_negative_m3(rot))) { + negate_m3(rot); + negate_v3(size); + } } void mat4_to_loc_rot_size(float loc[3], float rot[3][3], float size[3], float wmat[4][4]) @@ -2251,7 +2236,7 @@ void svd_m4(float U[4][4], float s[4], float V[4][4], float A_[4][4]) void pseudoinverse_m4_m4(float Ainv[4][4], float A_[4][4], float epsilon) { - /* compute moon-penrose pseudo inverse of matrix, singular values + /* compute Moore-Penrose pseudo inverse of matrix, singular values * below epsilon are ignored for stability (truncated SVD) */ float A[4][4], V[4][4], W[4], Wm[4][4], U[4][4]; int i; diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index 3d5d47bc2e0..5f039e89e89 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -1043,11 +1043,12 @@ void expmap_to_quat(float r[4], const float expmap[3]) float angle; /* Obtain axis/angle representation. */ - angle = normalize_v3_v3(axis, expmap); - angle = angle_wrap_rad(angle); - - /* Convert to quaternion. */ - axis_angle_to_quat(r, axis, angle); + if (LIKELY((angle = normalize_v3_v3(axis, expmap)) != 0.0f)) { + axis_angle_normalized_to_quat(r, axis, angle_wrap_rad(angle)); + } + else { + unit_qt(r); + } } /******************************** XYZ Eulers *********************************/ @@ -1322,12 +1323,21 @@ static const RotOrderInfo rotOrders[] = { * NOTE: since we start at 1 for the values, but arrays index from 0, * there is -1 factor involved in this process... */ -#define GET_ROTATIONORDER_INFO(order) (assert(order >= 0 && order <= 6), (order < 1) ? &rotOrders[0] : &rotOrders[(order) - 1]) +static const RotOrderInfo *get_rotation_order_info(const short order) +{ + assert(order >= 0 && order <= 6); + if (order < 1) + return &rotOrders[0]; + else if (order < 6) + return &rotOrders[order - 1]; + else + return &rotOrders[5]; +} /* Construct quaternion from Euler angles (in radians). */ void eulO_to_quat(float q[4], const float e[3], const short order) { - const RotOrderInfo *R = GET_ROTATIONORDER_INFO(order); + const RotOrderInfo *R = get_rotation_order_info(order); short i = R->axis[0], j = R->axis[1], k = R->axis[2]; double ti, tj, th, ci, cj, ch, si, sj, sh, cc, cs, sc, ss; double a[3]; @@ -1372,7 +1382,7 @@ void quat_to_eulO(float e[3], short const order, const float q[4]) /* Construct 3x3 matrix from Euler angles (in radians). */ void eulO_to_mat3(float M[3][3], const float e[3], const short order) { - const RotOrderInfo *R = GET_ROTATIONORDER_INFO(order); + const RotOrderInfo *R = get_rotation_order_info(order); short i = R->axis[0], j = R->axis[1], k = R->axis[2]; double ti, tj, th, ci, cj, ch, si, sj, sh, cc, cs, sc, ss; @@ -1413,7 +1423,7 @@ void eulO_to_mat3(float M[3][3], const float e[3], const short order) /* returns two euler calculation methods, so we can pick the best */ static void mat3_to_eulo2(float M[3][3], float eul1[3], float eul2[3], const short order) { - const RotOrderInfo *R = GET_ROTATIONORDER_INFO(order); + const RotOrderInfo *R = get_rotation_order_info(order); short i = R->axis[0], j = R->axis[1], k = R->axis[2]; float mat[3][3]; float cy; @@ -1549,7 +1559,7 @@ void rotate_eulO(float beul[3], const short order, char axis, float ang) /* the matrix is written to as 3 axis vectors */ void eulO_to_gimbal_axis(float gmat[3][3], const float eul[3], const short order) { - const RotOrderInfo *R = GET_ROTATIONORDER_INFO(order); + const RotOrderInfo *R = get_rotation_order_info(order); float mat[3][3]; float teul[3]; @@ -1606,7 +1616,7 @@ void eulO_to_gimbal_axis(float gmat[3][3], const float eul[3], const short order void mat4_to_dquat(DualQuat *dq, float basemat[4][4], float mat[4][4]) { - float *t, *q, dscale[3], scale[3], basequat[4]; + float *t, *q, dscale[3], scale[3], basequat[4], mat3[3][3]; float baseRS[4][4], baseinv[4][4], baseR[4][4], baseRinv[4][4]; float R[4][4], S[4][4]; @@ -1619,7 +1629,9 @@ void mat4_to_dquat(DualQuat *dq, float basemat[4][4], float mat[4][4]) dscale[1] = scale[1] - 1.0f; dscale[2] = scale[2] - 1.0f; - if ((determinant_m4(mat) < 0.0f) || len_v3(dscale) > 1e-4f) { + copy_m3_m4(mat3, mat); + + if (!is_orthonormal_m3(mat3) || (determinant_m4(mat) < 0.0f) || len_v3(dscale) > 1e-4f) { /* extract R and S */ float tmp[4][4]; diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c index 814180bba24..6da0e87355d 100644 --- a/source/blender/blenlib/intern/math_vector.c +++ b/source/blender/blenlib/intern/math_vector.c @@ -572,6 +572,27 @@ void project_v3_v3v3(float c[3], const float v1[3], const float v2[3]) c[2] = mul * v2[2]; } +/** + * In this case plane is a 3D vector only (no 4th component). + * + * Projecting will make \a c a copy of \a v orthogonal to \a v_plane. + * + * \note If \a v is exactly perpendicular to \a v_plane, \a c will just be a copy of \a v. + */ +void project_plane_v3_v3v3(float c[3], const float v[3], const float v_plane[3]) +{ + float delta[3]; + project_v3_v3v3(delta, v, v_plane); + sub_v3_v3v3(c, v, delta); +} + +void project_plane_v2_v2v2(float c[2], const float v[2], const float v_plane[2]) +{ + float delta[2]; + project_v2_v2v2(delta, v, v_plane); + sub_v2_v2v2(c, v, delta); +} + /* project a vector on a plane defined by normal and a plane point p */ void project_v3_plane(float v[3], const float n[3], const float p[3]) { @@ -855,7 +876,7 @@ float normalize_vn_vn(float *array_tar, const float *array_src, const int size) mul_vn_vn_fl(array_tar, array_src, size, 1.0f / d_sqrt); } else { - fill_vn_fl(array_tar, size, 0.0f); + copy_vn_fl(array_tar, size, 0.0f); d_sqrt = 0.0f; } return d_sqrt; @@ -876,6 +897,16 @@ void range_vn_i(int *array_tar, const int size, const int start) } } +void range_vn_u(unsigned int *array_tar, const int size, const unsigned int start) +{ + unsigned int *array_pt = array_tar + (size - 1); + unsigned int j = start + (unsigned int)(size - 1); + int i = size; + while (i--) { + *(array_pt--) = j--; + } +} + void range_vn_fl(float *array_tar, const int size, const float start, const float step) { float *array_pt = array_tar + (size - 1); @@ -1020,7 +1051,7 @@ void interp_vn_vn(float *array_tar, const float *array_src, const float t, const } } -void fill_vn_i(int *array_tar, const int size, const int val) +void copy_vn_i(int *array_tar, const int size, const int val) { int *tar = array_tar + (size - 1); int i = size; @@ -1029,7 +1060,7 @@ void fill_vn_i(int *array_tar, const int size, const int val) } } -void fill_vn_short(short *array_tar, const int size, const short val) +void copy_vn_short(short *array_tar, const int size, const short val) { short *tar = array_tar + (size - 1); int i = size; @@ -1038,7 +1069,7 @@ void fill_vn_short(short *array_tar, const int size, const short val) } } -void fill_vn_ushort(unsigned short *array_tar, const int size, const unsigned short val) +void copy_vn_ushort(unsigned short *array_tar, const int size, const unsigned short val) { unsigned short *tar = array_tar + (size - 1); int i = size; @@ -1047,7 +1078,7 @@ void fill_vn_ushort(unsigned short *array_tar, const int size, const unsigned sh } } -void fill_vn_uchar(unsigned char *array_tar, const int size, const unsigned char val) +void copy_vn_uchar(unsigned char *array_tar, const int size, const unsigned char val) { unsigned char *tar = array_tar + (size - 1); int i = size; @@ -1056,7 +1087,7 @@ void fill_vn_uchar(unsigned char *array_tar, const int size, const unsigned char } } -void fill_vn_fl(float *array_tar, const int size, const float val) +void copy_vn_fl(float *array_tar, const int size, const float val) { float *tar = array_tar + (size - 1); int i = size; @@ -1064,3 +1095,38 @@ void fill_vn_fl(float *array_tar, const int size, const float val) *(tar--) = val; } } + +/** \name Double precision versions 'db'. + * \{ */ + +void add_vn_vn_d(double *array_tar, const double *array_src, const int size) +{ + double *tar = array_tar + (size - 1); + const double *src = array_src + (size - 1); + int i = size; + while (i--) { + *(tar--) += *(src--); + } +} + +void add_vn_vnvn_d(double *array_tar, const double *array_src_a, const double *array_src_b, const int size) +{ + double *tar = array_tar + (size - 1); + const double *src_a = array_src_a + (size - 1); + const double *src_b = array_src_b + (size - 1); + int i = size; + while (i--) { + *(tar--) = *(src_a--) + *(src_b--); + } +} + +void mul_vn_db(double *array_tar, const int size, const double f) +{ + double *array_pt = array_tar + (size - 1); + int i = size; + while (i--) { + *(array_pt--) *= f; + } +} + +/** \} */ diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c index 621d5fbfbfe..fb33fed33e4 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -680,6 +680,11 @@ MINLINE float dot_v4v4(const float a[4], const float b[4]) return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + a[3] * b[3]; } +MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) +{ + return a[0] * (double)b[0] + a[1] * (double)b[1] + a[2] * (double)b[2]; +} + MINLINE float cross_v2v2(const float a[2], const float b[2]) { return a[0] * b[1] - a[1] * b[0]; diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c index 72739018399..b1a7d74e46f 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -57,6 +57,9 @@ # include <shlobj.h> # include "BLI_winstuff.h" # include "MEM_guardedalloc.h" +# include "BLI_alloca.h" +#else +# include "unistd.h" #endif /* WIN32 */ /* local */ @@ -743,7 +746,7 @@ bool BLI_parent_dir(char *path) BLI_cleanup_dir(NULL, tmp); /* does all the work of normalizing the path for us */ if (!BLI_testextensie(tmp, parent_dir)) { - BLI_strncpy(path, tmp, sizeof(tmp)); + strcpy(path, tmp); /* We assume pardir is always shorter... */ return true; } else { @@ -856,6 +859,111 @@ bool BLI_path_frame_range(char *path, int sta, int end, int digits) } /** + * Get the frame from a filename formatted by blender's frame scheme + */ +bool BLI_path_frame_get(char *path, int *r_frame, int *r_numdigits) +{ + if (path && *path) { + char *file = (char *)BLI_last_slash(path); + char *c; + int len, numdigits; + + numdigits = *r_numdigits = 0; + + if (file == NULL) + file = path; + + /* first get the extension part */ + len = strlen(file); + + c = file + len; + + /* isolate extension */ + while (--c != file) { + if (*c == '.') { + c--; + break; + } + } + + /* find start of number */ + while (c != (file - 1) && isdigit(*c)) { + c--; + numdigits++; + } + + if (numdigits) { + char prevchar; + + c++; + prevchar = c[numdigits]; + c[numdigits] = 0; + + /* was the number really an extension? */ + *r_frame = atoi(c); + c[numdigits] = prevchar; + + *r_numdigits = numdigits; + + return true; + } + } + + return false; +} + +void BLI_path_frame_strip(char *path, bool setsharp, char *ext) +{ + if (path && *path) { + char *file = (char *)BLI_last_slash(path); + char *c, *suffix; + int len; + int numdigits = 0; + + if (file == NULL) + file = path; + + /* first get the extension part */ + len = strlen(file); + + c = file + len; + + /* isolate extension */ + while (--c != file) { + if (*c == '.') { + c--; + break; + } + } + + suffix = c + 1; + + /* find start of number */ + while (c != (file - 1) && isdigit(*c)) { + c--; + numdigits++; + } + + c++; + + if (numdigits) { + /* replace the number with the suffix and terminate the string */ + while (numdigits--) { + if (ext) *ext++ = *suffix; + + if (setsharp) *c++ = '#'; + else *c++ = *suffix; + + suffix++; + } + *c = 0; + if (ext) *ext = 0; + } + } +} + + +/** * Check if we have '#' chars, usable for #BLI_path_frame, #BLI_path_frame_range */ bool BLI_path_frame_check_chars(const char *path) @@ -1018,6 +1126,114 @@ bool BLI_path_cwd(char *path) return wasrelative; } +#ifdef _WIN32 +/** + * Tries appending each of the semicolon-separated extensions in the PATHEXT + * environment variable (Windows-only) onto *name in turn until such a file is found. + * Returns success/failure. + */ +bool BLI_path_program_extensions_add_win32(char *name, const size_t maxlen) +{ + bool retval = false; + int type; + + type = BLI_exists(name); + if ((type == 0) || S_ISDIR(type)) { + /* typically 3-5, ".EXE", ".BAT"... etc */ + const int ext_max = 12; + const char *ext = getenv("PATHEXT"); + if (ext) { + const int name_len = strlen(name); + char *filename = alloca(name_len + ext_max); + char *filename_ext; + const char *ext_next; + + /* null terminated in the loop */ + memcpy(filename, name, name_len); + filename_ext = filename + name_len; + + do { + int ext_len; + ext_next = strchr(ext, ';'); + ext_len = ext_next ? ((ext_next++) - ext) : strlen(ext); + + if (LIKELY(ext_len < ext_max)) { + memcpy(filename_ext, ext, ext_len); + filename_ext[ext_len] = '\0'; + + type = BLI_exists(filename); + if (type && (!S_ISDIR(type))) { + retval = true; + BLI_strncpy(name, filename, maxlen); + break; + } + } + } while ((ext = ext_next)); + } + } + else { + retval = true; + } + + return retval; +} +#endif /* WIN32 */ + +/** + * Search for a binary (executable) + */ +bool BLI_path_program_search( + char *fullname, const size_t maxlen, + const char *name) +{ + const char *path; + bool retval = false; + +#ifdef _WIN32 + const char separator = ';'; +#else + const char separator = ':'; +#endif + + path = getenv("PATH"); + if (path) { + char filename[FILE_MAX]; + const char *temp; + + do { + temp = strchr(path, separator); + if (temp) { + strncpy(filename, path, temp - path); + filename[temp - path] = 0; + path = temp + 1; + } + else { + strncpy(filename, path, sizeof(filename)); + } + + BLI_path_append(filename, maxlen, name); + if ( +#ifdef _WIN32 + BLI_path_program_extensions_add_win32(filename, maxlen) +#else + BLI_exists(filename) +#endif + ) + { + BLI_strncpy(fullname, filename, maxlen); + retval = true; + break; + } + } while (temp); + } + + if (retval == false) { + *fullname = '\0'; + } + + return retval; +} + /** * Copies into *last the part of *dir following the second-last slash. */ @@ -1109,33 +1325,18 @@ void BLI_char_switch(char *string, char from, char to) */ void BLI_make_exist(char *dir) { - int a; - char par_path[PATH_MAX + 3]; + bool valid_path = true; - BLI_char_switch(dir, ALTSEP, SEP); + /* Loop as long as cur path is not a dir, and we can get a parent path. */ + while ((BLI_access(dir, R_OK) != 0) && (valid_path = BLI_parent_dir(dir))); - a = strlen(dir); - - for (BLI_join_dirfile(par_path, sizeof(par_path), dir, FILENAME_PARENT); - !(BLI_is_dir(dir) && BLI_exists(par_path)); - BLI_join_dirfile(par_path, sizeof(par_path), dir, FILENAME_PARENT)) - { - a--; - while (dir[a] != SEP) { - a--; - if (a <= 0) break; - } - if (a >= 0) { - dir[a + 1] = '\0'; - } - else { + /* If we could not find an existing dir, use default root... */ + if (!valid_path || !dir[0]) { #ifdef WIN32 - get_default_root(dir); + get_default_root(dir); #else - strcpy(dir, "/"); + strcpy(dir, "/"); #endif - break; - } } } diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c index 3aadbe5f1df..df6caa4b65a 100644 --- a/source/blender/blenlib/intern/polyfill2d.c +++ b/source/blender/blenlib/intern/polyfill2d.c @@ -61,6 +61,9 @@ # define USE_KDTREE #endif +/* disable in production, it can fail on near zero area ngons */ +// #define USE_STRICT_ASSERT + // #define DEBUG_TIME #ifdef DEBUG_TIME # include "PIL_time_utildefines.h" @@ -179,7 +182,7 @@ BLI_INLINE eSign signum_enum(float a) * alternative version of #area_tri_signed_v2 * needed because of float precision issues * - * \note removes / 2 since its not needed since we only need ths sign. + * \note removes / 2 since its not needed since we only need the sign. */ BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2]) { @@ -797,6 +800,7 @@ static void polyfill_prepare( } else { /* chech we're passing in correcty args */ +#ifdef USE_STRICT_ASSERT #ifndef NDEBUG if (coords_sign == 1) { BLI_assert(cross_poly_v2(coords, coords_tot) >= 0.0f); @@ -805,6 +809,7 @@ static void polyfill_prepare( BLI_assert(cross_poly_v2(coords, coords_tot) <= 0.0f); } #endif +#endif } if (coords_sign == 1) { diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c index ba71f52b530..46f9251bea7 100644 --- a/source/blender/blenlib/intern/polyfill2d_beautify.c +++ b/source/blender/blenlib/intern/polyfill2d_beautify.c @@ -430,17 +430,19 @@ void BLI_polyfill_beautify( } if (!is_boundary_edge(e_pair[0], e_pair[1], coord_last)) { - struct PolyEdge *e = BLI_edgehash_lookup(ehash, e_pair[0], e_pair[1]); - if (e == NULL) { + struct PolyEdge *e; + void **val_p; + + if (!BLI_edgehash_ensure_p(ehash, e_pair[0], e_pair[1], &val_p)) { e = &edges[edges_tot_used++]; - BLI_edgehash_insert(ehash, e_pair[0], e_pair[1], e); + *val_p = e; memcpy(e->verts, e_pair, sizeof(e->verts)); #ifndef NDEBUG e->faces[!e_index] = (unsigned int)-1; #endif } else { - + e = *val_p; /* ensure each edge only ever has 2x users */ #ifndef NDEBUG BLI_assert(e->faces[e_index] == (unsigned int)-1); diff --git a/source/blender/blenlib/intern/quadric.c b/source/blender/blenlib/intern/quadric.c index 814d05ca80e..588cd9c2cb5 100644 --- a/source/blender/blenlib/intern/quadric.c +++ b/source/blender/blenlib/intern/quadric.c @@ -29,20 +29,24 @@ * \note This isn't fully complete, * possible there are other useful functions to add here. * - * \note try to follow BLI_math naming convention here. + * \note follow BLI_math naming convention here. + * + * \note this uses doubles for internal calculations, + * even though input/output are floats in some cases. + * + * This is done because the cases quadrics are useful + * often need high precision, see T44780. */ -//#include <string.h> - #include "BLI_math.h" #include "BLI_strict_flags.h" #include "BLI_quadric.h" /* own include */ -#define QUADRIC_FLT_TOT (sizeof(Quadric) / sizeof(float)) +#define QUADRIC_FLT_TOT (sizeof(Quadric) / sizeof(double)) -void BLI_quadric_from_v3_dist(Quadric *q, const float v[3], const float offset) +void BLI_quadric_from_plane(Quadric *q, const double v[4]) { q->a2 = v[0] * v[0]; q->b2 = v[1] * v[1]; @@ -52,33 +56,33 @@ void BLI_quadric_from_v3_dist(Quadric *q, const float v[3], const float offset) q->ac = v[0] * v[2]; q->bc = v[1] * v[2]; - q->ad = v[0] * offset; - q->bd = v[1] * offset; - q->cd = v[2] * offset; + q->ad = v[0] * v[3]; + q->bd = v[1] * v[3]; + q->cd = v[2] * v[3]; - q->d2 = offset * offset; + q->d2 = v[3] * v[3]; } void BLI_quadric_to_tensor_m3(const Quadric *q, float m[3][3]) { - m[0][0] = q->a2; - m[0][1] = q->ab; - m[0][2] = q->ac; + m[0][0] = (float)q->a2; + m[0][1] = (float)q->ab; + m[0][2] = (float)q->ac; - m[1][0] = q->ab; - m[1][1] = q->b2; - m[1][2] = q->bc; + m[1][0] = (float)q->ab; + m[1][1] = (float)q->b2; + m[1][2] = (float)q->bc; - m[2][0] = q->ac; - m[2][1] = q->bc; - m[2][2] = q->c2; + m[2][0] = (float)q->ac; + m[2][1] = (float)q->bc; + m[2][2] = (float)q->c2; } void BLI_quadric_to_vector_v3(const Quadric *q, float v[3]) { - v[0] = q->ad; - v[1] = q->bd; - v[2] = q->cd; + v[0] = (float)q->ad; + v[1] = (float)q->bd; + v[2] = (float)q->cd; } void BLI_quadric_clear(Quadric *q) @@ -88,25 +92,26 @@ void BLI_quadric_clear(Quadric *q) void BLI_quadric_add_qu_qu(Quadric *a, const Quadric *b) { - add_vn_vn((float *)a, (float *)b, QUADRIC_FLT_TOT); + add_vn_vn_d((double *)a, (double *)b, QUADRIC_FLT_TOT); } void BLI_quadric_add_qu_ququ(Quadric *r, const Quadric *a, const Quadric *b) { - add_vn_vnvn((float *)r, (const float *)a, (const float *)b, QUADRIC_FLT_TOT); + add_vn_vnvn_d((double *)r, (const double *)a, (const double *)b, QUADRIC_FLT_TOT); } -void BLI_quadric_mul(Quadric *a, const float scalar) +void BLI_quadric_mul(Quadric *a, const double scalar) { - mul_vn_fl((float *)a, QUADRIC_FLT_TOT, scalar); + mul_vn_db((double *)a, QUADRIC_FLT_TOT, scalar); } -float BLI_quadric_evaluate(const Quadric *q, const float v[3]) +double BLI_quadric_evaluate(const Quadric *q, const float v_fl[3]) { - return (v[0] * v[0] * q->a2 + 2.0f * v[0] * v[1] * q->ab + 2.0f * v[0] * v[2] * q->ac + 2.0f * v[0] * q->ad + - v[1] * v[1] * q->b2 + 2.0f * v[1] * v[2] * q->bc + 2.0f * v[1] * q->bd + - v[2] * v[2] * q->c2 + 2.0f * v[2] * q->cd + - q->d2); + const double v[3] = {UNPACK3(v_fl)}; + return ((q->a2 * v[0] * v[0]) + (q->ab * 2 * v[0] * v[1]) + (q->ac * 2 * v[0] * v[2]) + (q->ad * 2 * v[0]) + + (q->b2 * v[1] * v[1]) + (q->bc * 2 * v[1] * v[2]) + (q->bd * 2 * v[1]) + + (q->c2 * v[2] * v[2]) + (q->cd * 2 * v[2]) + + (q->d2)); } bool BLI_quadric_optimize(const Quadric *q, float v[3], const float epsilon) diff --git a/source/blender/blenlib/intern/rand.c b/source/blender/blenlib/intern/rand.c index a03b236b5c6..66c568a7ff3 100644 --- a/source/blender/blenlib/intern/rand.c +++ b/source/blender/blenlib/intern/rand.c @@ -68,6 +68,9 @@ RNG *BLI_rng_new(unsigned int seed) return rng; } +/** + * A version of #BLI_rng_new that hashes the seed. + */ RNG *BLI_rng_new_srandom(unsigned int seed) { RNG *rng = MEM_mallocN(sizeof(*rng), "rng"); @@ -87,6 +90,9 @@ void BLI_rng_seed(RNG *rng, unsigned int seed) rng->X = (((uint64_t) seed) << 16) | LOWSEED; } +/** + * Use a hash table to create better seed. + */ void BLI_rng_srandom(RNG *rng, unsigned int seed) { BLI_rng_seed(rng, seed + hash[seed & 255]); @@ -113,11 +119,17 @@ unsigned int BLI_rng_get_uint(RNG *rng) return (unsigned int) (rng->X >> 17); } +/** + * \return Random value (0..1), but never 1.0. + */ double BLI_rng_get_double(RNG *rng) { return (double) BLI_rng_get_int(rng) / 0x80000000; } +/** + * \return Random value (0..1), but never 1.0. + */ float BLI_rng_get_float(RNG *rng) { return (float) BLI_rng_get_int(rng) / 0x80000000; @@ -172,7 +184,7 @@ void BLI_rng_get_tri_sample_float_v2( void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_tot) { - const size_t elem_size = (unsigned int)elem_size_i; + const size_t elem_size = (size_t)elem_size_i; unsigned int i = elem_tot; void *temp; @@ -196,6 +208,11 @@ void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsig free(temp); } +/** + * Simulate getting \a n random values. + * + * \note Useful when threaded code needs consistent values, independent of task division. + */ void BLI_rng_skip(RNG *rng, int n) { while (n--) { @@ -208,7 +225,6 @@ void BLI_rng_skip(RNG *rng, int n) /* initialize with some non-zero seed */ static RNG theBLI_rng = {611330372042337130}; -/* using hash table to create better seed */ void BLI_srandom(unsigned int seed) { BLI_rng_srandom(&theBLI_rng, seed); diff --git a/source/blender/blenlib/intern/rct.c b/source/blender/blenlib/intern/rct.c index 61e5783cd3e..8de5d2ef172 100644 --- a/source/blender/blenlib/intern/rct.c +++ b/source/blender/blenlib/intern/rct.c @@ -123,6 +123,38 @@ bool BLI_rctf_isect_pt_v(const rctf *rect, const float xy[2]) } /** + * \returns shortest distance from \a rect to x/y (0 if inside) +*/ + +int BLI_rcti_length_x(const rcti *rect, const int x) +{ + if (x < rect->xmin) return rect->xmin - x; + if (x > rect->xmax) return x - rect->xmax; + return 0; +} + +int BLI_rcti_length_y(const rcti *rect, const int y) +{ + if (y < rect->ymin) return rect->ymin - y; + if (y > rect->ymax) return y - rect->ymax; + return 0; +} + +float BLI_rctf_length_x(const rctf *rect, const float x) +{ + if (x < rect->xmin) return rect->xmin - x; + if (x > rect->xmax) return x - rect->xmax; + return 0.0f; +} + +float BLI_rctf_length_y(const rctf *rect, const float y) +{ + if (y < rect->ymin) return rect->ymin - y; + if (y > rect->ymax) return y - rect->ymax; + return 0.0f; +} + +/** * is \a rct_b inside \a rct_a */ bool BLI_rctf_inside_rctf(rctf *rct_a, const rctf *rct_b) @@ -571,3 +603,46 @@ void print_rcti(const char *str, const rcti *rect) printf("%s: xmin %d, xmax %d, ymin %d, ymax %d (%dx%d)\n", str, rect->xmin, rect->xmax, rect->ymin, rect->ymax, BLI_rcti_size_x(rect), BLI_rcti_size_y(rect)); } + + +/* -------------------------------------------------------------------- */ +/* Comprehensive math (float only) */ + +/** \name Rect math functions + * \{ */ + +#define ROTATE_SINCOS(r_vec, mat2, vec) { \ + (r_vec)[0] = (mat2)[1] * (vec)[0] + (+(mat2)[0]) * (vec)[1]; \ + (r_vec)[1] = (mat2)[0] * (vec)[0] + (-(mat2)[1]) * (vec)[1]; \ +} ((void)0) + +/** + * Expand the rectangle to fit a rotated \a src. + */ +void BLI_rctf_rotate_expand(rctf *dst, const rctf *src, const float angle) +{ + const float mat2[2] = {sinf(angle), cosf(angle)}; + const float cent[2] = {BLI_rctf_cent_x(src), BLI_rctf_cent_y(src)}; + float corner[2], corner_rot[2], corder_max[2]; + + /* x is same for both corners */ + corner[0] = src->xmax - cent[0]; + corner[1] = src->ymax - cent[1]; + ROTATE_SINCOS(corner_rot, mat2, corner); + corder_max[0] = fabsf(corner_rot[0]); + corder_max[1] = fabsf(corner_rot[1]); + + corner[1] *= -1; + ROTATE_SINCOS(corner_rot, mat2, corner); + corder_max[0] = MAX2(corder_max[0], fabsf(corner_rot[0])); + corder_max[1] = MAX2(corder_max[1], fabsf(corner_rot[1])); + + dst->xmin = cent[0] - corder_max[0]; + dst->xmax = cent[0] + corder_max[0]; + dst->ymin = cent[1] - corder_max[1]; + dst->ymax = cent[1] + corder_max[1]; +} + +#undef ROTATE_SINCOS + +/** \} */ diff --git a/source/blender/blenlib/intern/scanfill_utils.c b/source/blender/blenlib/intern/scanfill_utils.c index a606ac41aa1..059d5cb05a4 100644 --- a/source/blender/blenlib/intern/scanfill_utils.c +++ b/source/blender/blenlib/intern/scanfill_utils.c @@ -112,11 +112,13 @@ void BLI_scanfill_view3d_dump(ScanFillContext *sf_ctx) static ListBase *edge_isect_ls_ensure(GHash *isect_hash, ScanFillEdge *eed) { ListBase *e_ls; - e_ls = BLI_ghash_lookup(isect_hash, eed); - if (e_ls == NULL) { - e_ls = MEM_callocN(sizeof(ListBase), __func__); - BLI_ghash_insert(isect_hash, eed, e_ls); + void **val_p; + + if (!BLI_ghash_ensure_p(isect_hash, eed, &val_p)) { + *val_p = MEM_callocN(sizeof(ListBase), __func__); } + e_ls = *val_p; + return e_ls; } @@ -265,7 +267,7 @@ static bool scanfill_preprocess_self_isect( } if (BLI_listbase_is_single(e_ls) == false) { - BLI_listbase_sort_r(e_ls, eed->v2->co, edge_isect_ls_sort_cb); + BLI_listbase_sort_r(e_ls, edge_isect_ls_sort_cb, eed->v2->co); } /* move original edge to filledgebase and add replacement diff --git a/source/blender/blenlib/intern/stack.c b/source/blender/blenlib/intern/stack.c index 2d3a2f77a3e..084d692fcf0 100644 --- a/source/blender/blenlib/intern/stack.c +++ b/source/blender/blenlib/intern/stack.c @@ -125,8 +125,10 @@ void BLI_stack_free(BLI_Stack *stack) } /** - * Copies the source value onto the stack (note that it copies - * elem_size bytes from 'src', the pointer itself is not stored) + * Push a new item onto the stack. + * + * \return a pointer #BLI_Stack.elem_size + * bytes of uninitialized memory (caller must fill in). */ void *BLI_stack_push_r(BLI_Stack *stack) { @@ -158,6 +160,14 @@ void *BLI_stack_push_r(BLI_Stack *stack) return CHUNK_LAST_ELEM(stack); } +/** + * Copies the source value onto the stack + * + * \note This copies #BLI_Stack.elem_size bytes from \a src, + * (the pointer itself is not stored). + * + * \param src: source data to be copied to the stack. + */ void BLI_stack_push(BLI_Stack *stack, const void *src) { void *dst = BLI_stack_push_r(stack); @@ -179,6 +189,15 @@ void BLI_stack_pop(BLI_Stack *stack, void *dst) BLI_stack_discard(stack); } +/** + * A version of #BLI_stack_pop which which fills in an array. + * + * \param dst: The destination array, + * must be at least (#BLI_Stack.elem_size * \a n) bytes long. + * \param n: The number of items to pop. + * + * \note The first item in the array will be last item added to the stack. + */ void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) { BLI_assert(n <= BLI_stack_count(stack)); @@ -189,6 +208,23 @@ void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) } } +/** + * A version of #BLI_stack_pop_n which which fills in an array (in the reverse order). + * + * \note The first item in the array will be first item added to the stack. + */ +void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) +{ + BLI_assert(n <= BLI_stack_count(stack)); + + dst = (void *)((char *)dst + (stack->elem_size * n)); + + while (n--) { + dst = (void *)((char *)dst - stack->elem_size); + BLI_stack_pop(stack, dst); + } +} + void *BLI_stack_peek(BLI_Stack *stack) { BLI_assert(BLI_stack_is_empty(stack) == false); @@ -196,6 +232,9 @@ void *BLI_stack_peek(BLI_Stack *stack) return CHUNK_LAST_ELEM(stack); } +/** + * Removes the top element from the stack. + */ void BLI_stack_discard(BLI_Stack *stack) { BLI_assert(BLI_stack_is_empty(stack) == false); @@ -216,6 +255,41 @@ void BLI_stack_discard(BLI_Stack *stack) } } +/** + * Discards all elements without freeing. + */ +void BLI_stack_clear(BLI_Stack *stack) +{ +#ifdef USE_TOTELEM + if (UNLIKELY(stack->totelem == 0)) { + return; + } + stack->totelem = 0; +#else + if (UNLIKELY(stack->chunk_curr == NULL)) { + return; + } +#endif + + stack->chunk_index = stack->chunk_elem_max - 1; + + if (stack->chunk_free) { + if (stack->chunk_curr) { + /* move all used chunks into tail of free list */ + struct StackChunk *chunk_free_last = stack->chunk_free; + while (chunk_free_last->next) { + chunk_free_last = chunk_free_last->next; + } + chunk_free_last->next = stack->chunk_curr; + stack->chunk_curr = NULL; + } + } + else { + stack->chunk_free = stack->chunk_curr; + stack->chunk_curr = NULL; + } +} + size_t BLI_stack_count(const BLI_Stack *stack) { #ifdef USE_TOTELEM diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c index 46c5a11949c..7fdf6ec8101 100644 --- a/source/blender/blenlib/intern/storage.c +++ b/source/blender/blenlib/intern/storage.c @@ -35,11 +35,6 @@ #include <stdio.h> #include <stdlib.h> -#ifndef WIN32 -# include <dirent.h> -#endif - -#include <time.h> #include <sys/stat.h> #if defined(__NetBSD__) || defined(__DragonFly__) || defined(__sun__) || defined(__sun) @@ -79,17 +74,13 @@ /* lib includes */ #include "MEM_guardedalloc.h" -#include "DNA_listBase.h" - -#include "BLI_listbase.h" +#include "BLI_utildefines.h" #include "BLI_linklist.h" #include "BLI_string.h" #include "BLI_fileops.h" #include "BLI_fileops_types.h" #include "BLI_path_util.h" -#include "../imbuf/IMB_imbuf.h" - /** * Copies the current working directory into *dir (max size maxncpy), and * returns a pointer to same. @@ -107,42 +98,6 @@ char *BLI_current_working_dir(char *dir, const size_t maxncpy) return getcwd(dir, maxncpy); } -/* - * Ordering function for sorting lists of files/directories. Returns -1 if - * entry1 belongs before entry2, 0 if they are equal, 1 if they should be swapped. - */ -static int bli_compare(struct direntry *entry1, struct direntry *entry2) -{ - /* type is equal to stat.st_mode */ - - /* directories come before non-directories */ - if (S_ISDIR(entry1->type)) { - if (S_ISDIR(entry2->type) == 0) return (-1); - } - else { - if (S_ISDIR(entry2->type)) return (1); - } - /* non-regular files come after regular files */ - if (S_ISREG(entry1->type)) { - if (S_ISREG(entry2->type) == 0) return (-1); - } - else { - if (S_ISREG(entry2->type)) return (1); - } - /* arbitrary, but consistent, ordering of different types of non-regular files */ - if ((entry1->type & S_IFMT) < (entry2->type & S_IFMT)) return (-1); - if ((entry1->type & S_IFMT) > (entry2->type & S_IFMT)) return (1); - - /* OK, now we know their S_IFMT fields are the same, go on to a name comparison */ - /* make sure "." and ".." are always first */ - if (FILENAME_IS_CURRENT(entry1->relname)) return (-1); - if (FILENAME_IS_CURRENT(entry2->relname)) return (1); - if (FILENAME_IS_PARENT(entry1->relname)) return (-1); - if (FILENAME_IS_PARENT(entry2->relname)) return (1); - - return (BLI_natstrcmp(entry1->relname, entry2->relname)); -} - /** * Returns the number of free bytes on the volume containing the specified pathname. */ /* Not actually used anywhere. @@ -204,267 +159,6 @@ double BLI_dir_free_space(const char *dir) #endif } -struct BuildDirCtx { - struct direntry *files; /* array[nrfiles] */ - int nrfiles; -}; - -/** - * Scans the directory named *dirname and appends entries for its contents to files. - */ -static void bli_builddir(struct BuildDirCtx *dir_ctx, const char *dirname) -{ - struct ListBase dirbase = {NULL, NULL}; - int newnum = 0; - DIR *dir; - - if ((dir = opendir(dirname)) != NULL) { - const struct dirent *fname; - while ((fname = readdir(dir)) != NULL) { - struct dirlink * const dlink = (struct dirlink *)malloc(sizeof(struct dirlink)); - if (dlink != NULL) { - dlink->name = BLI_strdup(fname->d_name); - BLI_addhead(&dirbase, dlink); - newnum++; - } - } - - if (newnum) { - if (dir_ctx->files) { - void * const tmp = MEM_reallocN(dir_ctx->files, (dir_ctx->nrfiles + newnum) * sizeof(struct direntry)); - if (tmp) { - dir_ctx->files = (struct direntry *)tmp; - } - else { /* realloc fail */ - MEM_freeN(dir_ctx->files); - dir_ctx->files = NULL; - } - } - - if (dir_ctx->files == NULL) - dir_ctx->files = (struct direntry *)MEM_mallocN(newnum * sizeof(struct direntry), __func__); - - if (dir_ctx->files) { - struct dirlink * dlink = (struct dirlink *) dirbase.first; - struct direntry *file = &dir_ctx->files[dir_ctx->nrfiles]; - while (dlink) { - char fullname[PATH_MAX]; - memset(file, 0, sizeof(struct direntry)); - file->relname = dlink->name; - file->path = BLI_strdupcat(dirname, dlink->name); - BLI_join_dirfile(fullname, sizeof(fullname), dirname, dlink->name); - if (BLI_stat(fullname, &file->s) != -1) { - file->type = file->s.st_mode; - } - file->flags = 0; - dir_ctx->nrfiles++; - file++; - dlink = dlink->next; - } - } - else { - printf("Couldn't get memory for dir\n"); - exit(1); - } - - BLI_freelist(&dirbase); - if (dir_ctx->files) { - qsort(dir_ctx->files, dir_ctx->nrfiles, sizeof(struct direntry), (int (*)(const void *, const void *))bli_compare); - } - } - else { - printf("%s empty directory\n", dirname); - } - - closedir(dir); - } - else { - printf("%s non-existent directory\n", dirname); - } -} - -/** - * Fills in the "mode[123]", "size" and "string" fields in the elements of the files - * array with descriptive details about each item. "string" will have a format similar to "ls -l". - */ -static void bli_adddirstrings(struct BuildDirCtx *dir_ctx) -{ - const char *types[8] = {"---", "--x", "-w-", "-wx", "r--", "r-x", "rw-", "rwx"}; - /* symbolic display, indexed by mode field value */ - int num; -#ifdef WIN32 - __int64 st_size; -#else - off_t st_size; - int mode; -#endif - - struct direntry *file; - struct tm *tm; - time_t zero = 0; - - for (num = 0, file = dir_ctx->files; num < dir_ctx->nrfiles; num++, file++) { - - - /* Mode */ -#ifdef WIN32 - BLI_strncpy(file->mode1, types[0], sizeof(file->mode1)); - BLI_strncpy(file->mode2, types[0], sizeof(file->mode2)); - BLI_strncpy(file->mode3, types[0], sizeof(file->mode3)); -#else - mode = file->s.st_mode; - - BLI_strncpy(file->mode1, types[(mode & 0700) >> 6], sizeof(file->mode1)); - BLI_strncpy(file->mode2, types[(mode & 0070) >> 3], sizeof(file->mode2)); - BLI_strncpy(file->mode3, types[(mode & 0007)], sizeof(file->mode3)); - - if (((mode & S_ISGID) == S_ISGID) && (file->mode2[2] == '-')) file->mode2[2] = 'l'; - - if (mode & (S_ISUID | S_ISGID)) { - if (file->mode1[2] == 'x') file->mode1[2] = 's'; - else file->mode1[2] = 'S'; - - if (file->mode2[2] == 'x') file->mode2[2] = 's'; - } - - if (mode & S_ISVTX) { - if (file->mode3[2] == 'x') file->mode3[2] = 't'; - else file->mode3[2] = 'T'; - } -#endif - - - /* User */ -#ifdef WIN32 - strcpy(file->owner, "user"); -#else - { - struct passwd *pwuser; - pwuser = getpwuid(file->s.st_uid); - if (pwuser) { - BLI_strncpy(file->owner, pwuser->pw_name, sizeof(file->owner)); - } - else { - BLI_snprintf(file->owner, sizeof(file->owner), "%u", file->s.st_uid); - } - } -#endif - - - /* Time */ - tm = localtime(&file->s.st_mtime); - // prevent impossible dates in windows - if (tm == NULL) tm = localtime(&zero); - strftime(file->time, sizeof(file->time), "%H:%M", tm); - strftime(file->date, sizeof(file->date), "%d-%b-%y", tm); - - - /* Size */ - /* - * Seems st_size is signed 32-bit value in *nix and Windows. This - * will buy us some time until files get bigger than 4GB or until - * everyone starts using __USE_FILE_OFFSET64 or equivalent. - */ - st_size = file->s.st_size; - - if (st_size > 1024 * 1024 * 1024) { - BLI_snprintf(file->size, sizeof(file->size), "%.2f GiB", ((double)st_size) / (1024 * 1024 * 1024)); - } - else if (st_size > 1024 * 1024) { - BLI_snprintf(file->size, sizeof(file->size), "%.1f MiB", ((double)st_size) / (1024 * 1024)); - } - else if (st_size > 1024) { - BLI_snprintf(file->size, sizeof(file->size), "%d KiB", (int)(st_size / 1024)); - } - else { - BLI_snprintf(file->size, sizeof(file->size), "%d B", (int)st_size); - } - } -} - -/** - * Scans the contents of the directory named *dirname, and allocates and fills in an - * array of entries describing them in *filelist. - * - * \return The length of filelist array. - */ -unsigned int BLI_filelist_dir_contents(const char *dirname, struct direntry **filelist) -{ - struct BuildDirCtx dir_ctx; - - dir_ctx.nrfiles = 0; - dir_ctx.files = NULL; - - bli_builddir(&dir_ctx, dirname); - bli_adddirstrings(&dir_ctx); - - if (dir_ctx.files) { - *filelist = dir_ctx.files; - } - else { - // keep blender happy. Blender stores this in a variable - // where 0 has special meaning..... - *filelist = MEM_mallocN(sizeof(**filelist), __func__); - } - - return dir_ctx.nrfiles; -} - -/** - * Deep-duplicate of an array of direntries, including the array itself. - * - * \param dup_poin If given, called for each non-NULL direntry->poin. Otherwise, pointer is always simply copied over. - */ -void BLI_filelist_duplicate( - struct direntry **dest_filelist, struct direntry *src_filelist, unsigned int nrentries, - void *(*dup_poin)(void *)) -{ - unsigned int i; - - *dest_filelist = MEM_mallocN(sizeof(**dest_filelist) * (size_t)(nrentries), __func__); - for (i = 0; i < nrentries; ++i) { - struct direntry * const src = &src_filelist[i]; - struct direntry *dest = &(*dest_filelist)[i]; - *dest = *src; - if (dest->image) { - dest->image = IMB_dupImBuf(src->image); - } - if (dest->relname) { - dest->relname = MEM_dupallocN(src->relname); - } - if (dest->path) { - dest->path = MEM_dupallocN(src->path); - } - if (dest->poin && dup_poin) { - dest->poin = dup_poin(src->poin); - } - } -} - -/** - * frees storage for an array of direntries, including the array itself. - */ -void BLI_filelist_free(struct direntry *filelist, unsigned int nrentries, void (*free_poin)(void *)) -{ - unsigned int i; - for (i = 0; i < nrentries; ++i) { - struct direntry *entry = filelist + i; - if (entry->image) { - IMB_freeImBuf(entry->image); - } - if (entry->relname) - MEM_freeN(entry->relname); - if (entry->path) - MEM_freeN(entry->path); - if (entry->poin && free_poin) - free_poin(entry->poin); - } - - if (filelist != NULL) { - MEM_freeN(filelist); - } -} - /** * Returns the file size of an opened file descriptor. @@ -533,6 +227,7 @@ int BLI_exists(const char *name) #else struct stat st; BLI_assert(name); + BLI_assert(!BLI_path_is_rel(name)); if (stat(name, &st)) return(0); #endif return(st.st_mode); @@ -592,7 +287,7 @@ bool BLI_is_file(const char *path) LinkNode *BLI_file_read_as_lines(const char *name) { FILE *fp = BLI_fopen(name, "r"); - LinkNode *lines = NULL; + LinkNodePair lines = {NULL, NULL}; char *buf; size_t size; @@ -602,6 +297,11 @@ LinkNode *BLI_file_read_as_lines(const char *name) size = (size_t)ftell(fp); fseek(fp, 0, SEEK_SET); + if (UNLIKELY(size == (size_t)-1)) { + fclose(fp); + return NULL; + } + buf = MEM_mallocN(size, "file_as_lines"); if (buf) { size_t i, last = 0; @@ -616,7 +316,7 @@ LinkNode *BLI_file_read_as_lines(const char *name) if (i == size || buf[i] == '\n') { char *line = BLI_strdupn(&buf[last], i - last); - BLI_linklist_prepend(&lines, line); + BLI_linklist_append(&lines, line); /* faster to build singly-linked list in reverse order */ /* alternatively, could process buffer in reverse order so * list ends up right way round to start with */ @@ -629,9 +329,7 @@ LinkNode *BLI_file_read_as_lines(const char *name) fclose(fp); - /* get them the right way round */ - BLI_linklist_reverse(&lines); - return lines; + return lines.list; } /* @@ -674,4 +372,3 @@ bool BLI_file_older(const char *file1, const char *file2) #endif return (st1.st_mtime < st2.st_mtime); } - diff --git a/source/blender/blenlib/intern/string.c b/source/blender/blenlib/intern/string.c index cc5a90dbc39..3177bc659b2 100644 --- a/source/blender/blenlib/intern/string.c +++ b/source/blender/blenlib/intern/string.c @@ -231,6 +231,30 @@ size_t BLI_vsnprintf(char *__restrict buffer, size_t maxncpy, const char *__rest } /** + * A version of #BLI_vsnprintf that returns ``strlen(buffer)`` + */ +size_t BLI_vsnprintf_rlen(char *__restrict buffer, size_t maxncpy, const char *__restrict format, va_list arg) +{ + size_t n; + + BLI_assert(buffer != NULL); + BLI_assert(maxncpy > 0); + BLI_assert(format != NULL); + + n = (size_t)vsnprintf(buffer, maxncpy, format, arg); + + if (n != -1 && n < maxncpy) { + /* pass */ + } + else { + n = maxncpy - 1; + } + buffer[n] = '\0'; + + return n; +} + +/** * Portable replacement for #snprintf */ size_t BLI_snprintf(char *__restrict dst, size_t maxncpy, const char *__restrict format, ...) @@ -250,6 +274,25 @@ size_t BLI_snprintf(char *__restrict dst, size_t maxncpy, const char *__restrict } /** + * A version of #BLI_snprintf that returns ``strlen(dst)`` + */ +size_t BLI_snprintf_rlen(char *__restrict dst, size_t maxncpy, const char *__restrict format, ...) +{ + size_t n; + va_list arg; + +#ifdef DEBUG_STRSIZE + memset(dst, 0xff, sizeof(*dst) * maxncpy); +#endif + + va_start(arg, format); + n = BLI_vsnprintf_rlen(dst, maxncpy, format, arg); + va_end(arg); + + return n; +} + +/** * Print formatted string into a newly #MEM_mallocN'd string * and return it. */ @@ -811,9 +854,9 @@ bool BLI_str_endswith(const char *__restrict str, const char *end) * \param suf Return value, set to next char after the first delimiter found (or NULL if none found). * \return The length of the prefix (i.e. *sep - str). */ -size_t BLI_str_partition(const char *str, const char delim[], char **sep, char **suf) +size_t BLI_str_partition(const char *str, const char delim[], const char **sep, const char **suf) { - return BLI_str_partition_ex(str, delim, sep, suf, false); + return BLI_str_partition_ex(str, NULL, delim, sep, suf, false); } /** @@ -825,30 +868,52 @@ size_t BLI_str_partition(const char *str, const char delim[], char **sep, char * * \param suf Return value, set to next char after the first delimiter found (or NULL if none found). * \return The length of the prefix (i.e. *sep - str). */ -size_t BLI_str_rpartition(const char *str, const char delim[], char **sep, char **suf) +size_t BLI_str_rpartition(const char *str, const char delim[], const char **sep, const char **suf) { - return BLI_str_partition_ex(str, delim, sep, suf, true); + return BLI_str_partition_ex(str, NULL, delim, sep, suf, true); } /** * Find the first char matching one of the chars in \a delim, either from left or right. * * \param str The string to search within. + * \param end If non-NULL, the right delimiter of the string. * \param delim The set of delimiters to search for, as unicode values. * \param sep Return value, set to the first delimiter found (or NULL if none found). * \param suf Return value, set to next char after the first delimiter found (or NULL if none found). * \param from_right If %true, search from the right of \a str, else, search from its left. * \return The length of the prefix (i.e. *sep - str). */ -size_t BLI_str_partition_ex(const char *str, const char delim[], char **sep, char **suf, const bool from_right) +size_t BLI_str_partition_ex( + const char *str, const char *end, const char delim[], const char **sep, const char **suf, const bool from_right) { const char *d; char *(*func)(const char *str, int c) = from_right ? strrchr : strchr; + BLI_assert(end == NULL || end > str); + *sep = *suf = NULL; for (d = delim; *d != '\0'; ++d) { - char *tmp = func(str, *d); + const char *tmp; + + if (end) { + if (from_right) { + for (tmp = end - 1; (tmp >= str) && (*tmp != *d); tmp--); + if (tmp < str) { + tmp = NULL; + } + } + else { + tmp = func(str, *d); + if (tmp >= end) { + tmp = NULL; + } + } + } + else { + tmp = func(str, *d); + } if (tmp && (from_right ? (*sep < tmp) : (!*sep || *sep > tmp))) { *sep = tmp; @@ -860,7 +925,7 @@ size_t BLI_str_partition_ex(const char *str, const char delim[], char **sep, cha return (size_t)(*sep - str); } - return strlen(str); + return end ? (size_t)(end - str) : strlen(str); } /** diff --git a/source/blender/blenlib/intern/string_utf8.c b/source/blender/blenlib/intern/string_utf8.c index 67ff532cb6f..96033615cf5 100644 --- a/source/blender/blenlib/intern/string_utf8.c +++ b/source/blender/blenlib/intern/string_utf8.c @@ -329,8 +329,8 @@ size_t BLI_strnlen_utf8_ex(const char *strc, const size_t maxlen, size_t *r_len_ } /** - * \param start the string to measure the length. - * \param maxlen the string length (in bytes) + * \param strc: the string to measure the length. + * \param maxlen: the string length (in bytes) * \return the unicode length (not in bytes!) */ size_t BLI_strnlen_utf8(const char *strc, const size_t maxlen) @@ -599,14 +599,14 @@ unsigned int BLI_str_utf8_as_unicode_step(const char *__restrict p, size_t *__re /* was g_unichar_to_utf8 */ /** * BLI_str_utf8_from_unicode: - * @c a Unicode character code - * \param outbuf output buffer, must have at least 6 bytes of space. + * \param c: a Unicode character code + * \param outbuf: output buffer, must have at least 6 bytes of space. * If %NULL, the length will be computed and returned * and nothing will be written to outbuf. * * Converts a single character to UTF-8. * - * Return value: number of bytes written + * \return number of bytes written **/ size_t BLI_str_utf8_from_unicode(unsigned int c, char *outbuf) { @@ -734,28 +734,31 @@ char *BLI_str_prev_char_utf8(const char *p) } /* end glib copy */ -size_t BLI_str_partition_utf8(const char *str, const unsigned int delim[], char **sep, char **suf) +size_t BLI_str_partition_utf8(const char *str, const unsigned int delim[], const char **sep, const char **suf) { - return BLI_str_partition_ex_utf8(str, delim, sep, suf, false); + return BLI_str_partition_ex_utf8(str, NULL, delim, sep, suf, false); } -size_t BLI_str_rpartition_utf8(const char *str, const unsigned int delim[], char **sep, char **suf) +size_t BLI_str_rpartition_utf8(const char *str, const unsigned int delim[], const char **sep, const char **suf) { - return BLI_str_partition_ex_utf8(str, delim, sep, suf, true); + return BLI_str_partition_ex_utf8(str, NULL, delim, sep, suf, true); } -size_t BLI_str_partition_ex_utf8(const char *str, const unsigned int delim[], char **sep, char **suf, - const bool from_right) +size_t BLI_str_partition_ex_utf8( + const char *str, const char *end, const unsigned int delim[], const char **sep, const char **suf, const bool from_right) { const unsigned int *d; - const size_t str_len = strlen(str); + const size_t str_len = end ? (size_t)(end - str) : strlen(str); size_t index; + /* Note that here, we assume end points to a valid utf8 char! */ + BLI_assert(end == NULL || (end >= str && (BLI_str_utf8_as_unicode(end) != BLI_UTF8_ERR))); + *suf = (char *)(str + str_len); for (*sep = (char *)(from_right ? BLI_str_find_prev_char_utf8(str, str + str_len) : str), index = 0; - *sep != NULL && **sep != '\0'; - *sep = (char *)(from_right ? (char *)BLI_str_find_prev_char_utf8(str, *sep) : str + index)) + *sep >= str && (!end || *sep < end) && **sep != '\0'; + *sep = (char *)(from_right ? BLI_str_find_prev_char_utf8(str, *sep) : str + index)) { const unsigned int c = BLI_str_utf8_as_unicode_and_size(*sep, &index); diff --git a/source/blender/blenlib/intern/system.c b/source/blender/blenlib/intern/system.c index b6b0f14a4e2..5d1bdd6d978 100644 --- a/source/blender/blenlib/intern/system.c +++ b/source/blender/blenlib/intern/system.c @@ -99,8 +99,7 @@ void BLI_system_backtrace(FILE *fp) /* Windows */ #elif defined(_MSC_VER) - (void)fp; -#if defined WIN32 +#ifndef NDEBUG #define MAXSYMBOL 256 #define SIZE 100 unsigned short i; @@ -127,11 +126,12 @@ void BLI_system_backtrace(FILE *fp) MEM_freeN(symbolinfo); #undef MAXSYMBOL #undef SIZE -#endif - +#else + fprintf(fp, "Crash backtrace not supported on release builds\n"); +#endif /* NDEBUG */ +#else /* _MSC_VER */ /* ------------------ */ /* non msvc/osx/linux */ -#else (void)fp; #endif diff --git a/source/blender/blenlib/intern/task.c b/source/blender/blenlib/intern/task.c index d187a8d1968..08d40a158ca 100644 --- a/source/blender/blenlib/intern/task.c +++ b/source/blender/blenlib/intern/task.c @@ -417,6 +417,16 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) BLI_mutex_unlock(&pool->num_mutex); } +int BLI_pool_get_num_threads(TaskPool *pool) +{ + if (pool->num_threads != 0) { + return pool->num_threads; + } + else { + return BLI_task_scheduler_num_threads(pool->scheduler); + } +} + void BLI_pool_set_num_threads(TaskPool *pool, int num_threads) { /* NOTE: Don't try to modify threads while tasks are running! */ @@ -498,16 +508,14 @@ BLI_INLINE bool parallel_range_next_iter_get( int * __restrict iter, int * __restrict count) { bool result = false; + BLI_spin_lock(&state->lock); if (state->iter < state->stop) { - BLI_spin_lock(&state->lock); - if (state->iter < state->stop) { - *count = min_ii(state->chunk_size, state->stop - state->iter); - *iter = state->iter; - state->iter += *count; - result = true; - } - BLI_spin_unlock(&state->lock); + *count = min_ii(state->chunk_size, state->stop - state->iter); + *iter = state->iter; + state->iter += *count; + result = true; } + BLI_spin_unlock(&state->lock); return result; } diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index ded2fd7e06d..42f7a744b94 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -122,6 +122,7 @@ static pthread_mutex_t _nodes_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _movieclip_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _colormanage_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _fftw_lock = PTHREAD_MUTEX_INITIALIZER; +static pthread_mutex_t _view3d_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_t mainid; static int thread_levels = 0; /* threads can be invoked inside threads */ static int num_threads_override = 0; @@ -198,6 +199,7 @@ void BLI_init_threads(ListBase *threadbase, void *(*do_thread)(void *), int tot) } } + BLI_spin_lock(&_malloc_lock); if (thread_levels == 0) { MEM_set_lock_callback(BLI_lock_malloc_thread, BLI_unlock_malloc_thread); @@ -210,6 +212,7 @@ void BLI_init_threads(ListBase *threadbase, void *(*do_thread)(void *), int tot) } thread_levels++; + BLI_spin_unlock(&_malloc_lock); } /* amount of available threads */ @@ -328,9 +331,11 @@ void BLI_end_threads(ListBase *threadbase) BLI_freelistN(threadbase); } + BLI_spin_lock(&_malloc_lock); thread_levels--; if (thread_levels == 0) MEM_set_lock_callback(NULL, NULL); + BLI_spin_unlock(&_malloc_lock); } /* System Information */ @@ -338,33 +343,37 @@ void BLI_end_threads(ListBase *threadbase) /* how many threads are native on this system? */ int BLI_system_thread_count(void) { - int t; + static int t = -1; + + if (num_threads_override != 0) { + return num_threads_override; + } + else if (LIKELY(t != -1)) { + return t; + } + + { #ifdef WIN32 - SYSTEM_INFO info; - GetSystemInfo(&info); - t = (int) info.dwNumberOfProcessors; + SYSTEM_INFO info; + GetSystemInfo(&info); + t = (int) info.dwNumberOfProcessors; #else # ifdef __APPLE__ - int mib[2]; - size_t len; - - mib[0] = CTL_HW; - mib[1] = HW_NCPU; - len = sizeof(t); - sysctl(mib, 2, &t, &len, NULL, 0); + int mib[2]; + size_t len; + + mib[0] = CTL_HW; + mib[1] = HW_NCPU; + len = sizeof(t); + sysctl(mib, 2, &t, &len, NULL, 0); # else - t = (int)sysconf(_SC_NPROCESSORS_ONLN); + t = (int)sysconf(_SC_NPROCESSORS_ONLN); # endif #endif + } + + CLAMP(t, 1, RE_MAX_THREAD); - if (num_threads_override > 0) - return num_threads_override; - - if (t > RE_MAX_THREAD) - return RE_MAX_THREAD; - if (t < 1) - return 1; - return t; } @@ -402,6 +411,8 @@ void BLI_lock_thread(int type) pthread_mutex_lock(&_colormanage_lock); else if (type == LOCK_FFTW) pthread_mutex_lock(&_fftw_lock); + else if (type == LOCK_VIEW3D) + pthread_mutex_lock(&_view3d_lock); } void BLI_unlock_thread(int type) @@ -426,6 +437,8 @@ void BLI_unlock_thread(int type) pthread_mutex_unlock(&_colormanage_lock); else if (type == LOCK_FFTW) pthread_mutex_unlock(&_fftw_lock); + else if (type == LOCK_VIEW3D) + pthread_mutex_unlock(&_view3d_lock); } /* Mutex Locks */ @@ -768,6 +781,17 @@ int BLI_thread_queue_size(ThreadQueue *queue) return size; } +bool BLI_thread_queue_is_empty(ThreadQueue *queue) +{ + bool is_empty; + + pthread_mutex_lock(&queue->mutex); + is_empty = BLI_gsqueue_is_empty(queue->queue); + pthread_mutex_unlock(&queue->mutex); + + return is_empty; +} + void BLI_thread_queue_nowait(ThreadQueue *queue) { pthread_mutex_lock(&queue->mutex); @@ -797,10 +821,12 @@ void BLI_begin_threaded_malloc(void) /* Used for debug only */ /* BLI_assert(thread_levels >= 0); */ + BLI_spin_lock(&_malloc_lock); if (thread_levels == 0) { MEM_set_lock_callback(BLI_lock_malloc_thread, BLI_unlock_malloc_thread); } thread_levels++; + BLI_spin_unlock(&_malloc_lock); } void BLI_end_threaded_malloc(void) @@ -808,8 +834,10 @@ void BLI_end_threaded_malloc(void) /* Used for debug only */ /* BLI_assert(thread_levels >= 0); */ + BLI_spin_lock(&_malloc_lock); thread_levels--; if (thread_levels == 0) MEM_set_lock_callback(NULL, NULL); + BLI_spin_unlock(&_malloc_lock); } diff --git a/source/blender/blenlib/intern/timecode.c b/source/blender/blenlib/intern/timecode.c index 0c8834008b6..39ffbcd7ebe 100644 --- a/source/blender/blenlib/intern/timecode.c +++ b/source/blender/blenlib/intern/timecode.c @@ -113,22 +113,22 @@ size_t BLI_timecode_string_from_time( if (power <= 0) { /* include "frames" in display */ if (hours) { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d:%02d+%02d", neg, hours, minutes, seconds, frames); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d:%02d+%02d", neg, hours, minutes, seconds, frames); } else if (minutes) { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d+%02d", neg, minutes, seconds, frames); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d+%02d", neg, minutes, seconds, frames); } else { - rlen = BLI_snprintf(str, maxncpy, "%s%d+%02d", neg, seconds, frames); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%d+%02d", neg, seconds, frames); } } else { /* don't include 'frames' in display */ if (hours) { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d:%02d", neg, hours, minutes, seconds); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d:%02d", neg, hours, minutes, seconds); } else { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d", neg, minutes, seconds); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d", neg, minutes, seconds); } } break; @@ -137,10 +137,10 @@ size_t BLI_timecode_string_from_time( { /* reduced SMPTE format that always shows minutes, seconds, frames. Hours only shown as needed. */ if (hours) { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d:%02d:%02d", neg, hours, minutes, seconds, frames); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d:%02d:%02d", neg, hours, minutes, seconds, frames); } else { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d:%02d", neg, minutes, seconds, frames); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d:%02d", neg, minutes, seconds, frames); } break; } @@ -156,10 +156,10 @@ size_t BLI_timecode_string_from_time( const int s_pad = ms_dp + 3; if (hours) { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d:%0*.*f", neg, hours, minutes, s_pad, ms_dp, time); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d:%0*.*f", neg, hours, minutes, s_pad, ms_dp, time); } else { - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%0*.*f", neg, minutes, s_pad, ms_dp, time); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%0*.*f", neg, minutes, s_pad, ms_dp, time); } break; } @@ -168,10 +168,10 @@ size_t BLI_timecode_string_from_time( /* only show the original seconds display */ /* round to whole numbers if power is >= 1 (i.e. scale is coarse) */ if (power <= 0) { - rlen = BLI_snprintf(str, maxncpy, "%.*f", 1 - power, time_seconds); + rlen = BLI_snprintf_rlen(str, maxncpy, "%.*f", 1 - power, time_seconds); } else { - rlen = BLI_snprintf(str, maxncpy, "%d", iroundf(time_seconds)); + rlen = BLI_snprintf_rlen(str, maxncpy, "%d", iroundf(time_seconds)); } break; } @@ -179,7 +179,7 @@ size_t BLI_timecode_string_from_time( default: { /* full SMPTE format */ - rlen = BLI_snprintf(str, maxncpy, "%s%02d:%02d:%02d:%02d", neg, hours, minutes, seconds, frames); + rlen = BLI_snprintf_rlen(str, maxncpy, "%s%02d:%02d:%02d:%02d", neg, hours, minutes, seconds, frames); break; } } @@ -196,7 +196,6 @@ size_t BLI_timecode_string_from_time( * \param power special setting for #View2D grid drawing, * used to specify how detailed we need to be * \param time_seconds time total time in seconds - * \param seconds time in seconds. * \return length of \a str * * \note in some cases this is used to print non-seconds values. @@ -208,10 +207,10 @@ size_t BLI_timecode_string_from_time_simple( /* round to whole numbers if power is >= 1 (i.e. scale is coarse) */ if (power <= 0) { - rlen = BLI_snprintf(str, maxncpy, "%.*f", 1 - power, time_seconds); + rlen = BLI_snprintf_rlen(str, maxncpy, "%.*f", 1 - power, time_seconds); } else { - rlen = BLI_snprintf(str, maxncpy, "%d", iroundf(time_seconds)); + rlen = BLI_snprintf_rlen(str, maxncpy, "%d", iroundf(time_seconds)); } return rlen; diff --git a/source/blender/blenlib/intern/winstuff_dir.c b/source/blender/blenlib/intern/winstuff_dir.c index b20da9ce959..bde0734a740 100644 --- a/source/blender/blenlib/intern/winstuff_dir.c +++ b/source/blender/blenlib/intern/winstuff_dir.c @@ -44,6 +44,22 @@ #include "BLI_utildefines.h" #include "utfconv.h" +#define PATH_SUFFIX "\\*" +#define PATH_SUFFIX_LEN 2 + +/* keep local to this file */ +struct __dirstream { + HANDLE handle; + WIN32_FIND_DATAW data; + char path[MAX_PATH + PATH_SUFFIX_LEN]; + long dd_loc; + long dd_size; + char dd_buf[4096]; + void *dd_direct; + + struct dirent direntry; +}; + /* Note: MinGW (FREE_WINDOWS) has opendir() and _wopendir(), and only the * latter accepts a path name of wchar_t type. Rather than messing up with * extra #ifdef's here and there, Blender's own implementations of opendir() @@ -54,25 +70,25 @@ DIR *opendir(const char *path) { wchar_t *path_16 = alloc_utf16_from_8(path, 0); + int path_len; + DIR *newd = NULL; - if (GetFileAttributesW(path_16) & FILE_ATTRIBUTE_DIRECTORY) { - DIR *newd = MEM_mallocN(sizeof(DIR), "opendir"); - + if ((GetFileAttributesW(path_16) & FILE_ATTRIBUTE_DIRECTORY) && + ((path_len = strlen(path)) < (sizeof(newd->path) - PATH_SUFFIX_LEN))) + { + newd = MEM_mallocN(sizeof(DIR), "opendir"); newd->handle = INVALID_HANDLE_VALUE; - sprintf(newd->path, "%s\\*", path); - + memcpy(newd->path, path, path_len); + memcpy(newd->path + path_len, PATH_SUFFIX, PATH_SUFFIX_LEN + 1); + newd->direntry.d_ino = 0; newd->direntry.d_off = 0; newd->direntry.d_reclen = 0; newd->direntry.d_name = NULL; - - free(path_16); - return newd; - } - else { - free(path_16); - return NULL; } + + free(path_16); + return newd; } static char *BLI_alloc_utf_8_from_16(wchar_t *in16, size_t add) |