diff options
Diffstat (limited to 'source/blender/blenlib')
66 files changed, 2631 insertions, 852 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_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 10c0752c9a7..876d2c459c5 100644 --- a/source/blender/blenlib/BLI_compiler_compat.h +++ b/source/blender/blenlib/BLI_compiler_compat.h @@ -37,4 +37,16 @@ # include <malloc.h> #endif +#if defined(__cplusplus) && ((__cplusplus >= 201103L) || (defined(_MSC_VER) && _MSC_VER >= 1800)) +# define HAS_CPP11_FEATURES +#endif + +#if (defined(__GNUC__) || defined(__clang__)) && defined(HAS_CPP11_FEATURES) +extern "C++" { + /* Some magic to be sure we don't have reference in the type. */ + template<typename T> static inline T decltype_helper(T x) { return x; } +# define typeof(x) decltype(decltype_helper(x)) +} +#endif + #endif /* __BLI_COMPILER_COMPAT_H__ */ 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..642896ac701 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 */ @@ -107,6 +106,7 @@ int BLI_access(const char *filename, int mode) ATTR_WARN_UNUSED_RESULT ATTR_N bool BLI_file_is_writable(const char *file) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_file_touch(const char *file) ATTR_NONNULL(); +void BLI_file_size_string(off_t st_size, char *size, size_t len); #if 0 /* UNUSED */ int BLI_file_gzip(const char *from, const char *to) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); diff --git a/source/blender/blenlib/BLI_fileops_types.h b/source/blender/blenlib/BLI_fileops_types.h index 0e6eab687ad..e596fa55877 100644 --- a/source/blender/blenlib/BLI_fileops_types.h +++ b/source/blender/blenlib/BLI_fileops_types.h @@ -34,6 +34,7 @@ */ #include <sys/stat.h> +#include "BLI_listbase.h" #if defined(WIN32) && !defined(FREE_WINDOWS) typedef unsigned int mode_t; @@ -41,6 +42,19 @@ typedef unsigned int mode_t; struct ImBuf; +typedef struct CollapsedEntry { + /* list that gets populated during file open */ + ListBase list; + /* sorted array of the files for quick access of frames */ + struct direntry **darray; + off_t totalsize; + int minframe; + int maxframe; + int numdigits; + int totfiles; + int curfra; +} CollapsedEntry; + struct direntry { mode_t type; char *relname; @@ -69,6 +83,10 @@ struct direntry { int nr; struct ImBuf *image; unsigned int selflag; /* selection flag */ + off_t realsize; /* real size of file */ + int frame; /* frame of file in a movie sequence */ + + CollapsedEntry collapsed_info; }; struct dirlink { diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index bf2b4126453..a9f8d9fc268 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -44,6 +44,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) (const void *key); +typedef void *(*GHashValCopyFP) (const void *val); typedef struct GHash GHash; @@ -54,7 +56,13 @@ typedef struct GHashIterator { } GHashIterator; enum { - GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* only checked for in debug mode */ + GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* Only checked for in debug mode */ + GHASH_FLAG_ALLOW_SHRINK = (1 << 1), /* Allow to shrink buckets' size. */ + +#ifdef GHASH_INTERNAL_API + /* Internal usage only */ + GHASH_FLAG_IS_GSET = (1 << 16), /* Whether the GHash is actually used as GSet (no value storage). */ +#endif }; /* *** */ @@ -62,19 +70,24 @@ enum { GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, + GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve); void BLI_ghash_insert(GHash *gh, void *key, void *val); bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); 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); @@ -127,23 +140,38 @@ unsigned int BLI_ghashutil_strhash_n(const char *key, size_t n); CHECK_TYPE_ANY(key, char *, const char *, const char * const), \ BLI_ghashutil_strhash_p(key)) unsigned int BLI_ghashutil_strhash_p(const void *key); +unsigned int BLI_ghashutil_strhash_p_murmur(const void *key); bool BLI_ghashutil_strcmp(const void *a, const void *b); #define BLI_ghashutil_inthash(key) ( \ CHECK_TYPE_ANY(&(key), int *, const int *), \ BLI_ghashutil_uinthash((unsigned int)key)) 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); + + +unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]); #define BLI_ghashutil_inthash_v4(key) ( \ CHECK_TYPE_ANY(key, int *, const int *), \ BLI_ghashutil_uinthash_v4((const unsigned int *)key)) -unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]); #define BLI_ghashutil_inthash_v4_p \ ((GSetHashFP)BLI_ghashutil_uinthash_v4) +#define BLI_ghashutil_uinthash_v4_p \ + ((GSetHashFP)BLI_ghashutil_uinthash_v4) +unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]); +#define BLI_ghashutil_inthash_v4_murmur(key) ( \ + CHECK_TYPE_ANY(key, int *, const int *), \ + BLI_ghashutil_uinthash_v4_murmur((const unsigned int *)key)) +#define BLI_ghashutil_inthash_v4_p_murmur \ + ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur) +#define BLI_ghashutil_uinthash_v4_p_murmur \ + ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur) bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b); #define BLI_ghashutil_inthash_v4_cmp \ BLI_ghashutil_uinthash_v4_cmp -unsigned int BLI_ghashutil_inthash_p(const void *ptr); -bool BLI_ghashutil_intcmp(const void *a, const void *b); /** \} */ @@ -178,6 +206,7 @@ typedef struct GSet GSet; typedef GHashHashFP GSetHashFP; typedef GHashCmpFP GSetCmpFP; typedef GHashKeyFreeFP GSetKeyFreeFP; +typedef GHashKeyCopyFP GSetKeyCopyFP; /* so we can cast but compiler sees as different */ typedef struct GSetIterator { @@ -191,7 +220,8 @@ typedef struct GSetIterator { 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; -int BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT; +GSet *BLI_gset_copy(GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC 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); @@ -199,10 +229,10 @@ 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); +void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp); GSet *BLI_gset_ptr_new_ex(const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; @@ -229,10 +259,22 @@ BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashItera BLI_gsetIterator_done(&gs_iter_) == false; \ BLI_gsetIterator_step(&gs_iter_), i_++) -#ifdef DEBUG + +/* For testing, debugging only */ +#ifdef GHASH_INTERNAL_API +int BLI_ghash_buckets_size(GHash *gh); +int BLI_gset_buckets_size(GSet *gs); + +double BLI_ghash_calc_quality_ex( + GHash *gh, double *r_load, double *r_variance, + double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket); +double BLI_gset_calc_quality_ex( + GSet *gs, double *r_load, double *r_variance, + double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket); double BLI_ghash_calc_quality(GHash *gh); double BLI_gset_calc_quality(GSet *gs); -#endif +#endif /* GHASH_INTERNAL_API */ + #ifdef __cplusplus } diff --git a/source/blender/blenlib/BLI_hash_mm2a.h b/source/blender/blenlib/BLI_hash_mm2a.h index 007dec4f4d6..6beaf50ae8f 100644 --- a/source/blender/blenlib/BLI_hash_mm2a.h +++ b/source/blender/blenlib/BLI_hash_mm2a.h @@ -42,4 +42,6 @@ void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data); uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2); +uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed); + #endif /* __BLI_HASH_MM2A_H__ */ 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_math.h b/source/blender/blenlib/BLI_math.h index db2fed433da..62ed8045109 100644 --- a/source/blender/blenlib/BLI_math.h +++ b/source/blender/blenlib/BLI_math.h @@ -30,18 +30,30 @@ * \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 + * + * \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 +73,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..79a2d57c966 100644 --- a/source/blender/blenlib/BLI_math_base.h +++ b/source/blender/blenlib/BLI_math_base.h @@ -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 55e57b14d09..d70dfcd9e58 100644 --- a/source/blender/blenlib/BLI_math_color.h +++ b/source/blender/blenlib/BLI_math_color.h @@ -80,13 +80,6 @@ void rgb_to_xyz(float r, float g, float b, float *x, float *y, float *z); unsigned int rgb_to_cpack(float r, float g, float b); unsigned int hsv_to_cpack(float h, float s, float v); -MINLINE float rgb_to_bw(const float rgb[3]); -MINLINE float rgb_to_grayscale(const float rgb[3]); -MINLINE unsigned char rgb_to_grayscale_byte(const unsigned char rgb[3]); -MINLINE float rgb_to_luma(const float rgb[3]); -MINLINE unsigned char rgb_to_luma_byte(const unsigned char rgb[3]); -MINLINE float rgb_to_luma_y(const float rgb[3]); - /**************** Profile Transformations *****************/ float srgb_to_linearrgb(float c); @@ -136,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..91610ccfe5b 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -227,6 +227,8 @@ void fill_poly_v2i_n( /* tri or quad, d can be NULL */ void interp_weights_face_v3(float w[4], const float a[3], const float b[3], const float c[3], const float d[3], const float p[3]); +/* also returns three indices of the triangle actually used */ +void interp_weights_face_v3_index(int tri[3], float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3]); void interp_weights_poly_v3(float w[], float v[][3], const int n, const float co[3]); void interp_weights_poly_v2(float w[], float v[][2], const int n, const float co[2]); @@ -259,6 +261,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 ffd80f46725..9bc1121801e 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -146,11 +146,20 @@ MINLINE void negate_v4_v4(float r[4], const float a[3]); MINLINE void negate_v3_short(short r[3]); +MINLINE void abs_v2(float r[2]); +MINLINE void abs_v2_v2(float r[2], const float a[2]); +MINLINE void abs_v3(float r[3]); +MINLINE void abs_v3_v3(float r[3], const float a[3]); +MINLINE void abs_v4(float r[4]); +MINLINE void abs_v4_v4(float r[4], const float a[4]); + MINLINE float dot_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT; MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT; 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]); @@ -264,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]); @@ -299,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); @@ -319,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..c488856ca30 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(); +bool BLI_path_frame_strip(char *path, bool setsharp, char *ext); 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..e0a0b34ac5f 100644 --- a/source/blender/blenlib/BLI_rect.h +++ b/source/blender/blenlib/BLI_rect.h @@ -89,6 +89,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..6d41e5feb88 100644 --- a/source/blender/blenlib/BLI_stack.h +++ b/source/blender/blenlib/BLI_stack.h @@ -48,6 +48,7 @@ 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_string.h b/source/blender/blenlib/BLI_string.h index c4853e37398..e6c1cc8b4b6 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); 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..18b8feaa99c 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); diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 1e8440e55e9..8f2f906ed17 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -252,7 +252,7 @@ extern "C" { #define FTOCHAR(val) ((CHECK_TYPE_INLINE(val, float)), \ (char)(((val) <= 0.0f) ? 0 : (((val) > (1.0f - 0.5f / 255.0f)) ? 255 : ((255.0f * (val)) + 0.5f)))) #define FTOUSHORT(val) ((CHECK_TYPE_INLINE(val, float)), \ - ((val >= 1.0f - 0.5f / 65535) ? 65535 : (val <= 0.0f) ? 0 : (unsigned short)(val * 65535.0f + 0.5f))) + (unsigned short)((val >= 1.0f - 0.5f / 65535) ? 65535 : (val <= 0.0f) ? 0 : (val * 65535.0f + 0.5f))) #define USHORTTOUCHAR(val) ((unsigned char)(((val) >= 65535 - 128) ? 255 : ((val) + 128) >> 8)) #define F3TOCHAR3(v2, v1) { \ (v1)[0] = FTOCHAR((v2[0])); \ @@ -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/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index e614a2a0663..e39202d35fd 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -44,6 +44,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 @@ -74,6 +75,7 @@ set(SRC 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 +155,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 +208,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..f700a12fbca --- /dev/null +++ b/source/blender/blenlib/intern/BLI_filelist.c @@ -0,0 +1,398 @@ +/* + * ***** 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; + 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. + */ + file->realsize = file->s.st_size; + + BLI_file_size_string(file->realsize, file->size, sizeof(file->size)); + } +} + +void BLI_file_size_string(off_t st_size, char *size, size_t len) +{ + if (st_size > 1024 * 1024 * 1024) { + BLI_snprintf(size, len, "%.2f GiB", ((double)st_size) / (1024 * 1024 * 1024)); + } + else if (st_size > 1024 * 1024) { + BLI_snprintf(size, len, "%.1f MiB", ((double)st_size) / (1024 * 1024)); + } + else if (st_size > 1024) { + BLI_snprintf(size, len, "%d KiB", (int)(st_size / 1024)); + } + else { + BLI_snprintf(size, len, "%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); + } + if (dest->collapsed_info.darray) { + dest->collapsed_info.darray = NULL; + } + } +} + +/** + * 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 (entry->collapsed_info.darray) + MEM_freeN(entry->collapsed_info.darray); + } + + 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 5360ea744a1..9287d62a683 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -36,17 +36,23 @@ #include <string.h> #include <stdlib.h> +#include <stdarg.h> #include <limits.h> #include "MEM_guardedalloc.h" #include "BLI_sys_types.h" /* for intptr_t support */ #include "BLI_utildefines.h" +#include "BLI_hash_mm2a.h" #include "BLI_mempool.h" + +#define GHASH_INTERNAL_API #include "BLI_ghash.h" #include "BLI_strict_flags.h" +#define GHASH_USE_MODULO_BUCKETS +/* Also used by smallhash! */ const unsigned int hashsizes[] = { 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, @@ -54,24 +60,43 @@ const unsigned int hashsizes[] = { 268435459 }; -/* internal flag to ensure sets values aren't used */ -#ifndef NDEBUG -# define GHASH_FLAG_IS_SET (1 << 8) -# define IS_GHASH_ASSERT(gh) BLI_assert((gh->flag & GHASH_FLAG_IS_SET) == 0) -// # define IS_GSET_ASSERT(gs) BLI_assert((gs->flag & GHASH_FLAG_IS_SET) != 0) +#ifdef GHASH_USE_MODULO_BUCKETS +# define GHASH_MAX_SIZE 27 #else -# define IS_GHASH_ASSERT(gh) -// # define IS_GSET_ASSERT(eh) +# define GHASH_BUCKET_BIT_MIN 2 +# define GHASH_BUCKET_BIT_MAX 28 /* About 268M of buckets... */ #endif +/** + * \note Max load #GHASH_LIMIT_GROW used to be 3. (pre 2.74). + * Python uses 0.6666, tommyhaslib even goes down to 0.5. + * Reducing our from 3 to 0.75 gives huge speedup (about twice quicker pure GHash insertions/lookup, + * about 25% - 30% quicker 'dynamic-topology' stroke drawing e.g.). + * Min load #GHASH_LIMIT_SHRINK is a quarter of max load, to avoid resizing to quickly. + */ +#define GHASH_LIMIT_GROW(_nbkt) (((_nbkt) * 3) / 4) +#define GHASH_LIMIT_SHRINK(_nbkt) (((_nbkt) * 3) / 16) + /***/ +/* WARNING! Keep in sync with ugly _gh_Entry in header!!! */ typedef struct Entry { struct Entry *next; - void *key, *val; + void *key; } Entry; +typedef struct GHashEntry { + Entry e; + + void *val; +} GHashEntry; + +typedef Entry GSetEntry; + +#define GHASH_ENTRY_SIZE(_is_gset) \ + ((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry)) + struct GHash { GHashHashFP hashfp; GHashCmpFP cmpfp; @@ -79,11 +104,34 @@ struct GHash { Entry **buckets; struct BLI_mempool *entrypool; unsigned int nbuckets; + unsigned int limit_grow, limit_shrink; +#ifdef GHASH_USE_MODULO_BUCKETS + unsigned int cursize, size_min; +#else + unsigned int bucket_mask, bucket_bit, bucket_bit_min; +#endif + unsigned int nentries; - unsigned int cursize, flag; + unsigned int flag; }; +BLI_INLINE void ghash_entry_copy( + GHash *gh_dst, Entry *dst, GHash *gh_src, Entry *src, + GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) +{ + dst->key = (keycopyfp) ? keycopyfp(src->key) : src->key; + + if ((gh_dst->flag & GHASH_FLAG_IS_GSET) == 0) { + if ((gh_src->flag & GHASH_FLAG_IS_GSET) == 0) { + ((GHashEntry *)dst)->val = (valcopyfp) ? valcopyfp(((GHashEntry *)src)->val) : ((GHashEntry *)src)->val; + } + else { + ((GHashEntry *)dst)->val = NULL; + } + } +} + /* -------------------------------------------------------------------- */ /* GHash API */ @@ -91,25 +139,37 @@ struct GHash { * \{ */ /** - * Get the hash for a key. + * Get the full hash for a key. */ BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key) { - return gh->hashfp(key) % gh->nbuckets; + return gh->hashfp(key); } /** - * Check if the number of items in the GHash is large enough to require more buckets. + * Get the full hash for an entry. */ -BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets) +BLI_INLINE unsigned int ghash_entryhash(GHash *gh, const Entry *e) { - return (nentries > nbuckets * 3); + return gh->hashfp(e->key); } /** - * Expand buckets to the next size up. + * Get the bucket-hash for an already-computed full hash. */ -BLI_INLINE void ghash_resize_buckets(GHash *gh, const unsigned int nbuckets) +BLI_INLINE unsigned int ghash_bucket_index(GHash *gh, const unsigned int hash) +{ +#ifdef GHASH_USE_MODULO_BUCKETS + return hash % gh->nbuckets; +#else + return hash & gh->bucket_mask; +#endif +} + +/** + * Expand buckets to the next size up or down. + */ +static void ghash_buckets_resize(GHash *gh, const unsigned int nbuckets) { Entry **buckets_old = gh->buckets; Entry **buckets_new; @@ -117,49 +177,223 @@ BLI_INLINE void ghash_resize_buckets(GHash *gh, const unsigned int nbuckets) unsigned int i; Entry *e; - BLI_assert(gh->nbuckets != nbuckets); + BLI_assert((gh->nbuckets != nbuckets) || !gh->buckets); +// printf("%s: %d -> %d\n", __func__, nbuckets_old, nbuckets); gh->nbuckets = nbuckets; - buckets_new = (Entry **)MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); - - for (i = 0; i < nbuckets_old; i++) { - Entry *e_next; - for (e = buckets_old[i]; e; e = e_next) { - const unsigned hash = ghash_keyhash(gh, e->key); - e_next = e->next; - e->next = buckets_new[hash]; - buckets_new[hash] = e; +#ifdef GHASH_USE_MODULO_BUCKETS +#else + gh->bucket_mask = nbuckets - 1; +#endif + + buckets_new = (Entry **)MEM_callocN(sizeof(*gh->buckets) * gh->nbuckets, __func__); + + if (buckets_old) { + if (nbuckets > nbuckets_old) { + for (i = 0; i < nbuckets_old; i++) { + Entry *e_next; + for (e = buckets_old[i]; e; e = e_next) { + const unsigned hash = ghash_entryhash(gh, e); + const unsigned bucket_index = ghash_bucket_index(gh, hash); + e_next = e->next; + e->next = buckets_new[bucket_index]; + buckets_new[bucket_index] = e; + } + } + } + else { + for (i = 0; i < nbuckets_old; i++) { +#ifdef GHASH_USE_MODULO_BUCKETS + Entry *e_next; + for (e = buckets_old[i]; e; e = e_next) { + const unsigned hash = ghash_entryhash(gh, e); + const unsigned bucket_index = ghash_bucket_index(gh, hash); + e_next = e->next; + e->next = buckets_new[bucket_index]; + buckets_new[bucket_index] = e; + } +#else + /* No need to recompute hashes in this case, since our mask is just smaller, all items in old bucket i + * will go in same new bucket (i & new_mask)! */ + const unsigned bucket_index = ghash_bucket_index(gh, i); + BLI_assert(!buckets_old[i] || (bucket_index == ghash_bucket_index(gh, ghash_entryhash(gh, buckets_old[i])))); + for (e = buckets_old[i]; e && e->next; e = e->next); + if (e) { + e->next = buckets_new[bucket_index]; + buckets_new[bucket_index] = buckets_old[i]; + } +#endif + } } } gh->buckets = buckets_new; - MEM_freeN(buckets_old); + if (buckets_old) { + MEM_freeN(buckets_old); + } } /** - * Increase initial bucket size to match a reserved amount. + * Check if the number of items in the GHash is large enough to require more buckets, + * or small enough to require less buckets, and resize \a gh accordingly. */ -BLI_INLINE void ghash_buckets_reserve(GHash *gh, const unsigned int nentries_reserve) +static void ghash_buckets_expand( + GHash *gh, const unsigned int nentries, const bool user_defined) { - while (ghash_test_expand_buckets(nentries_reserve, gh->nbuckets)) { - gh->nbuckets = hashsizes[++gh->cursize]; + unsigned int new_nbuckets; + + if (LIKELY(gh->buckets && (nentries < gh->limit_grow))) { + return; + } + + new_nbuckets = gh->nbuckets; + +#ifdef GHASH_USE_MODULO_BUCKETS + while ((nentries > gh->limit_grow) && + (gh->cursize < GHASH_MAX_SIZE - 1)) + { + new_nbuckets = hashsizes[++gh->cursize]; + gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets); } +#else + while ((nentries > gh->limit_grow) && + (gh->bucket_bit < GHASH_BUCKET_BIT_MAX)) + { + new_nbuckets = 1u << ++gh->bucket_bit; + gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets); + } +#endif + + if (user_defined) { +#ifdef GHASH_USE_MODULO_BUCKETS + gh->size_min = gh->cursize; +#else + gh->bucket_bit_min = gh->bucket_bit; +#endif + } + + if ((new_nbuckets == gh->nbuckets) && gh->buckets) { + return; + } + + gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets); + gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets); + ghash_buckets_resize(gh, new_nbuckets); +} + +static void ghash_buckets_contract( + GHash *gh, const unsigned int nentries, const bool user_defined, const bool force_shrink) +{ + unsigned int new_nbuckets; + + if (!(force_shrink || (gh->flag & GHASH_FLAG_ALLOW_SHRINK))) { + return; + } + + if (LIKELY(gh->buckets && (nentries > gh->limit_shrink))) { + return; + } + + new_nbuckets = gh->nbuckets; + +#ifdef GHASH_USE_MODULO_BUCKETS + while ((nentries < gh->limit_shrink) && + (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)) + { + new_nbuckets = 1u << --gh->bucket_bit; + gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets); + } +#endif + + if (user_defined) { +#ifdef GHASH_USE_MODULO_BUCKETS + gh->size_min = gh->cursize; +#else + gh->bucket_bit_min = gh->bucket_bit; +#endif + } + + if ((new_nbuckets == gh->nbuckets) && gh->buckets) { + return; + } + + gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets); + gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets); + ghash_buckets_resize(gh, new_nbuckets); +} + +/** + * Clear and reset \a gh buckets, reserve again buckets for given number of entries. + */ +BLI_INLINE void ghash_buckets_reset(GHash *gh, const unsigned int nentries) +{ + MEM_SAFE_FREE(gh->buckets); + +#ifdef GHASH_USE_MODULO_BUCKETS + gh->cursize = 0; + gh->size_min = 0; + gh->nbuckets = hashsizes[gh->cursize]; +#else + gh->bucket_bit = GHASH_BUCKET_BIT_MIN; + gh->bucket_bit_min = GHASH_BUCKET_BIT_MIN; + gh->nbuckets = 1u << gh->bucket_bit; + gh->bucket_mask = gh->nbuckets - 1; +#endif + + gh->limit_grow = GHASH_LIMIT_GROW(gh->nbuckets); + gh->limit_shrink = GHASH_LIMIT_SHRINK(gh->nbuckets); + + gh->nentries = 0; + + ghash_buckets_expand(gh, nentries, (nentries != 0)); } /** * Internal lookup function. - * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index multiple times. */ -BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, - const unsigned int hash) +BLI_INLINE Entry *ghash_lookup_entry_ex( + GHash *gh, const void *key, const unsigned int bucket_index) { Entry *e; + /* If we do not store GHash, not worth computing it for each entry here! + * Typically, comparison function will be quicker, and since it's needed in the end anyway... */ + for (e = gh->buckets[bucket_index]; e; e = e->next) { + if (UNLIKELY(gh->cmpfp(key, e->key) == false)) { + return e; + } + } + + return NULL; +} + +/** + * Internal lookup function, returns previous entry of target one too. + * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index multiple times. + * Useful when modifying buckets somehow (like removing an entry...). + */ +BLI_INLINE Entry *ghash_lookup_entry_prev_ex( + GHash *gh, const void *key, Entry **r_e_prev, const unsigned int bucket_index) +{ + Entry *e, *e_prev = NULL; - for (e = gh->buckets[hash]; e; e = e->next) { + /* If we do not store GHash, not worth computing it for each entry here! + * Typically, comparison function will be quicker, and since it's needed in the end anyway... */ + for (e = gh->buckets[bucket_index]; e; e_prev = e, e = e->next) { if (UNLIKELY(gh->cmpfp(key, e->key) == false)) { + *r_e_prev = e_prev; return e; } } + + *r_e_prev = NULL; return NULL; } @@ -169,105 +403,157 @@ BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key) { const unsigned int hash = ghash_keyhash(gh, key); - return ghash_lookup_entry_ex(gh, key, hash); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + return ghash_lookup_entry_ex(gh, key, bucket_index); } static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, - const unsigned int nentries_reserve, - const unsigned int entry_size) + const unsigned int nentries_reserve, const unsigned int flag) { GHash *gh = MEM_mallocN(sizeof(*gh), info); gh->hashfp = hashfp; gh->cmpfp = cmpfp; - gh->nbuckets = hashsizes[0]; /* gh->cursize */ - gh->nentries = 0; - gh->cursize = 0; - gh->flag = 0; + gh->buckets = NULL; + gh->flag = flag; - /* if we have reserved the number of elements that this hash will contain */ - if (nentries_reserve) { - ghash_buckets_reserve(gh, nentries_reserve); - } - - gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); - gh->entrypool = BLI_mempool_create(entry_size, 64, 64, BLI_MEMPOOL_NOP); + ghash_buckets_reset(gh, nentries_reserve); + gh->entrypool = BLI_mempool_create(GHASH_ENTRY_SIZE(flag & GHASH_FLAG_IS_GSET), 64, 64, BLI_MEMPOOL_NOP); return gh; } /** * Internal insert function. - * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + * Takes hash and bucket_index arguments to avoid calling #ghash_keyhash and #ghash_bucket_index multiple times. */ -BLI_INLINE void ghash_insert_ex(GHash *gh, void *key, void *val, - unsigned int hash) +BLI_INLINE void ghash_insert_ex( + GHash *gh, void *key, void *val, const unsigned int bucket_index) { - Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool); + GHashEntry *e = BLI_mempool_alloc(gh->entrypool); + BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0)); - IS_GHASH_ASSERT(gh); + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); - e->next = gh->buckets[hash]; - e->key = key; + e->e.next = gh->buckets[bucket_index]; + e->e.key = key; e->val = val; - gh->buckets[hash] = e; + gh->buckets[bucket_index] = (Entry *)e; - if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) { - ghash_resize_buckets(gh, hashsizes[++gh->cursize]); - } + ghash_buckets_expand(gh, ++gh->nentries, false); +} + +/** + * 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, - unsigned int hash) +BLI_INLINE void ghash_insert_ex_keyonly( + GHash *gh, void *key, const unsigned int bucket_index) { - Entry *e = (Entry *)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)); - e->next = gh->buckets[hash]; + BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0); + + e->next = gh->buckets[bucket_index]; e->key = key; - /* intentionally leave value unset */ - gh->buckets[hash] = e; + gh->buckets[bucket_index] = e; - if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) { - ghash_resize_buckets(gh, hashsizes[++gh->cursize]); - } + ghash_buckets_expand(gh, ++gh->nentries, false); } BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val) { const unsigned int hash = ghash_keyhash(gh, key); - ghash_insert_ex(gh, key, val, hash); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + + ghash_insert_ex(gh, key, val, bucket_index); +} + +BLI_INLINE bool ghash_insert_safe( + GHash *gh, void *key, void *val, const bool override, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) +{ + 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); + + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); + + if (e) { + if (override) { + if (keyfreefp) keyfreefp(e->e.key); + if (valfreefp) valfreefp(e->val); + e->e.key = key; + e->val = val; + } + return false; + } + else { + ghash_insert_ex(gh, key, val, bucket_index); + return true; + } +} + +BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool override, GHashKeyFreeFP keyfreefp) +{ + const unsigned int hash = ghash_keyhash(gh, key); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + Entry *e = ghash_lookup_entry_ex(gh, key, bucket_index); + + BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0); + + if (e) { + if (override) { + if (keyfreefp) keyfreefp(e->key); + e->key = key; + } + return false; + } + else { + ghash_insert_ex_keyonly(gh, key, bucket_index); + return true; + } } /** * 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, - unsigned int hash) +static Entry *ghash_remove_ex( + GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, + const unsigned int bucket_index) { - Entry *e; - Entry *e_prev = NULL; + Entry *e_prev; + Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, bucket_index); - for (e = gh->buckets[hash]; e; e = e->next) { - if (UNLIKELY(gh->cmpfp(key, e->key) == false)) { - Entry *e_next = e->next; + BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET)); - if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); + if (e) { + if (keyfreefp) keyfreefp(e->key); + if (valfreefp) valfreefp(((GHashEntry *)e)->val); - if (e_prev) e_prev->next = e_next; - else gh->buckets[hash] = e_next; + if (e_prev) e_prev->next = e->next; + else gh->buckets[bucket_index] = e->next; - gh->nentries--; - return e; - } - e_prev = e; + ghash_buckets_contract(gh, --gh->nentries, false, false); } - return NULL; + return e; } /** @@ -277,21 +563,57 @@ static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va { unsigned int i; - BLI_assert(keyfreefp || valfreefp); + BLI_assert(keyfreefp || valfreefp); + BLI_assert(!valfreefp || !(gh->flag & GHASH_FLAG_IS_GSET)); for (i = 0; i < gh->nbuckets; i++) { Entry *e; - for (e = gh->buckets[i]; e; ) { - Entry *e_next = e->next; - + for (e = gh->buckets[i]; e; e = e->next) { if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); + if (valfreefp) valfreefp(((GHashEntry *)e)->val); + } + } +} + +/** + * Copy the GHash. + */ +static GHash *ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) +{ + GHash *gh_new; + unsigned int i; + /* This allows us to be sure to get the same number of buckets in gh_new as in ghash. */ + const unsigned int reserve_nentries_new = MAX2(GHASH_LIMIT_GROW(gh->nbuckets) - 1, gh->nentries); + + BLI_assert(!valcopyfp || !(gh->flag & GHASH_FLAG_IS_GSET)); - e = e_next; + gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, gh->flag); + ghash_buckets_expand(gh_new, reserve_nentries_new, false); + + BLI_assert(gh_new->nbuckets == gh->nbuckets); + + for (i = 0; i < gh->nbuckets; i++) { + Entry *e; + + for (e = gh->buckets[i]; e; e = e->next) { + Entry *e_new = BLI_mempool_alloc(gh_new->entrypool); + ghash_entry_copy(gh_new, e_new, gh, e, keycopyfp, valcopyfp); + + /* Warning! + * This means entries in buckets in new copy will be in reversed order! + * This shall not be an issue though, since order should never be assumed in ghash. */ + + /* Note: We can use 'i' here, since we are sure that 'gh' and 'gh_new' have the same number of buckets! */ + e_new->next = gh_new->buckets[i]; + gh_new->buckets[i] = e_new; } } + gh_new->nentries = gh->nentries; + + return gh_new; } + /** \} */ @@ -311,9 +633,7 @@ static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, const unsigned int nentries_reserve) { - return ghash_new(hashfp, cmpfp, info, - nentries_reserve, - (unsigned int)sizeof(Entry)); + return ghash_new(hashfp, cmpfp, info, nentries_reserve, 0); } /** @@ -325,11 +645,28 @@ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) } /** + * Copy given GHash. Keys and values are also copied if relevant callback is provided, else pointers remain the same. + */ +GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) +{ + return ghash_copy(gh, keycopyfp, valcopyfp); +} + +/** + * Reverve given ammount of entries (resize \a gh accordingly if needed). + */ +void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve) +{ + ghash_buckets_expand(gh, nentries_reserve, true); + ghash_buckets_contract(gh, nentries_reserve, true, false); +} + +/** * \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; } /** @@ -353,19 +690,7 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val) */ bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { - const unsigned int hash = ghash_keyhash(gh, key); - Entry *e = ghash_lookup_entry_ex(gh, key, hash); - if (e) { - if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); - e->key = key; - e->val = val; - return false; - } - else { - ghash_insert_ex(gh, key, val, hash); - return true; - } + return ghash_insert_safe(gh, key, val, true, keyfreefp, valfreefp); } /** @@ -379,8 +704,8 @@ bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreef */ void *BLI_ghash_lookup(GHash *gh, const void *key) { - Entry *e = ghash_lookup_entry(gh, key); - IS_GHASH_ASSERT(gh); + GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key); + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); return e ? e->val : NULL; } @@ -389,8 +714,8 @@ void *BLI_ghash_lookup(GHash *gh, const void *key) */ void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) { - Entry *e = ghash_lookup_entry(gh, key); - IS_GHASH_ASSERT(gh); + GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key); + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); return e ? e->val : val_default; } @@ -406,12 +731,64 @@ void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) */ void **BLI_ghash_lookup_p(GHash *gh, const void *key) { - Entry *e = ghash_lookup_entry(gh, key); - IS_GHASH_ASSERT(gh); + GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key); + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); return e ? &e->val : NULL; } /** + * 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. @@ -419,10 +796,11 @@ 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); - Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, hash); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + Entry *e = ghash_remove_ex(gh, key, keyfreefp, valfreefp, bucket_index); if (e) { BLI_mempool_free(gh->entrypool, e); return true; @@ -441,11 +819,12 @@ 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); - Entry *e = ghash_remove_ex(gh, key, keyfreefp, NULL, hash); - IS_GHASH_ASSERT(gh); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + GHashEntry *e = (GHashEntry *)ghash_remove_ex(gh, key, keyfreefp, NULL, bucket_index); + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); if (e) { void *val = e->val; BLI_mempool_free(gh->entrypool, e); @@ -477,17 +856,7 @@ void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valf if (keyfreefp || valfreefp) ghash_free_cb(gh, keyfreefp, valfreefp); - gh->nbuckets = hashsizes[0]; /* gh->cursize */ - gh->nentries = 0; - gh->cursize = 0; - - if (nentries_reserve) { - ghash_buckets_reserve(gh, nentries_reserve); - } - - MEM_freeN(gh->buckets); - gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); - + ghash_buckets_reset(gh, nentries_reserve); BLI_mempool_clear_ex(gh->entrypool, nentries_reserve ? (int)nentries_reserve : -1); } @@ -701,6 +1070,10 @@ unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]) hash += key[3]; return hash; } +unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]) +{ + 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) { @@ -733,6 +1106,18 @@ unsigned int BLI_ghashutil_inthash_p(const void *ptr) return (unsigned int)(key & 0xffffffff); } +unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr) +{ + uintptr_t key = (uintptr_t)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); @@ -769,9 +1154,15 @@ unsigned int BLI_ghashutil_strhash_p(const void *ptr) return h; } +unsigned int BLI_ghashutil_strhash_p_murmur(const void *ptr) +{ + const unsigned char *key = ptr; + + return BLI_hash_mm2(key, strlen((const char *)key) + 1, 0); +} bool BLI_ghashutil_strcmp(const void *a, const void *b) { - return (!STREQ(a, b)); + return (a == b) ? false : !STREQ(a, b); } GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second) @@ -809,44 +1200,36 @@ void BLI_ghashutil_pairfree(void *ptr) /** \name Convenience GHash Creation Functions * \{ */ -GHash *BLI_ghash_ptr_new_ex(const char *info, - const unsigned int nentries_reserve) +GHash *BLI_ghash_ptr_new_ex(const char *info, const unsigned int nentries_reserve) { - return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, - nentries_reserve); + return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve); } GHash *BLI_ghash_ptr_new(const char *info) { return BLI_ghash_ptr_new_ex(info, 0); } -GHash *BLI_ghash_str_new_ex(const char *info, - const unsigned int nentries_reserve) +GHash *BLI_ghash_str_new_ex(const char *info, const unsigned int nentries_reserve) { - return BLI_ghash_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, - nentries_reserve); + return BLI_ghash_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve); } GHash *BLI_ghash_str_new(const char *info) { return BLI_ghash_str_new_ex(info, 0); } -GHash *BLI_ghash_int_new_ex(const char *info, - const unsigned int nentries_reserve) +GHash *BLI_ghash_int_new_ex(const char *info, const unsigned int nentries_reserve) { - return BLI_ghash_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, - nentries_reserve); + return BLI_ghash_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve); } GHash *BLI_ghash_int_new(const char *info) { return BLI_ghash_int_new_ex(info, 0); } -GHash *BLI_ghash_pair_new_ex(const char *info, - const unsigned int nentries_reserve) +GHash *BLI_ghash_pair_new_ex(const char *info, const unsigned int nentries_reserve) { - return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, - nentries_reserve); + return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve); } GHash *BLI_ghash_pair_new(const char *info) { @@ -861,21 +1244,12 @@ GHash *BLI_ghash_pair_new(const char *info) /* Use ghash API to give 'set' functionality */ -/* TODO: typical set functions - * isdisjoint/issubset/issuperset/union/intersection/difference etc */ - /** \name GSet Functions * \{ */ GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, const unsigned int nentries_reserve) { - GSet *gs = (GSet *)ghash_new(hashfp, cmpfp, info, - nentries_reserve, - sizeof(Entry) - sizeof(void *)); -#ifndef NDEBUG - ((GHash *)gs)->flag |= GHASH_FLAG_IS_SET; -#endif - return gs; + return (GSet *)ghash_new(hashfp, cmpfp, info, nentries_reserve, GHASH_FLAG_IS_GSET); } GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) @@ -883,9 +1257,17 @@ GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) return BLI_gset_new_ex(hashfp, cmpfp, info, 0); } -int BLI_gset_size(GSet *gs) +/** + * Copy given GSet. Keys are also copied if callback is provided, else pointers remain the same. + */ +GSet *BLI_gset_copy(GSet *gs, GHashKeyCopyFP keycopyfp) +{ + return (GSet *)ghash_copy((GHash *)gs, keycopyfp, NULL); +} + +unsigned int BLI_gset_size(GSet *gs) { - return (int)((GHash *)gs)->nentries; + return ((GHash *)gs)->nentries; } /** @@ -895,7 +1277,8 @@ int BLI_gset_size(GSet *gs) void BLI_gset_insert(GSet *gs, void *key) { const unsigned int hash = ghash_keyhash((GHash *)gs, key); - ghash_insert_ex_keyonly((GHash *)gs, key, hash); + const unsigned int bucket_index = ghash_bucket_index((GHash *)gs, hash); + ghash_insert_ex_keyonly((GHash *)gs, key, bucket_index); } /** @@ -906,15 +1289,7 @@ void BLI_gset_insert(GSet *gs, void *key) */ bool BLI_gset_add(GSet *gs, void *key) { - const unsigned int hash = ghash_keyhash((GHash *)gs, key); - Entry *e = ghash_lookup_entry_ex((GHash *)gs, key, hash); - if (e) { - return false; - } - else { - ghash_insert_ex_keyonly((GHash *)gs, key, hash); - return true; - } + return ghash_insert_safe_keyonly((GHash *)gs, key, false, NULL); } /** @@ -925,20 +1300,10 @@ bool BLI_gset_add(GSet *gs, void *key) */ bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) { - const unsigned int hash = ghash_keyhash((GHash *)gs, key); - Entry *e = ghash_lookup_entry_ex((GHash *)gs, key, hash); - if (e) { - if (keyfreefp) keyfreefp(e->key); - e->key = key; - return false; - } - else { - ghash_insert_ex_keyonly((GHash *)gs, key, hash); - return true; - } + 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); } @@ -982,22 +1347,18 @@ void BLI_gset_flag_clear(GSet *gs, unsigned int flag) /** \name Convenience GSet Creation Functions * \{ */ -GSet *BLI_gset_ptr_new_ex(const char *info, - const unsigned int nentries_reserve) +GSet *BLI_gset_ptr_new_ex(const char *info, const unsigned int nentries_reserve) { - return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, - nentries_reserve); + return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve); } GSet *BLI_gset_ptr_new(const char *info) { return BLI_gset_ptr_new_ex(info, 0); } -GSet *BLI_gset_pair_new_ex(const char *info, - const unsigned int nentries_reserve) +GSet *BLI_gset_pair_new_ex(const char *info, const unsigned int nentries_reserve) { - return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, - nentries_reserve); + return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve); } GSet *BLI_gset_pair_new(const char *info) { @@ -1009,37 +1370,126 @@ GSet *BLI_gset_pair_new(const char *info) /** \name Debugging & Introspection * \{ */ -#ifdef DEBUG + +#include "BLI_math.h" + +/** + * \return number of buckets in the GHash. + */ +int BLI_ghash_buckets_size(GHash *gh) +{ + return (int)gh->nbuckets; +} +int BLI_gset_buckets_size(GSet *gs) +{ + return BLI_ghash_buckets_size((GHash *)gs); +} /** - * Measure how well the hash function performs - * (1.0 is approx as good as random distribution). + * Measure how well the hash function performs (1.0 is approx as good as random distribution), + * and return a few other stats like load, variance of the distribution of the entries in the buckets, etc. * * Smaller is better! */ -double BLI_ghash_calc_quality(GHash *gh) +double BLI_ghash_calc_quality_ex( + GHash *gh, double *r_load, double *r_variance, + double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket) { - uint64_t sum = 0; + double mean; unsigned int i; - if (gh->nentries == 0) - return -1.0; + if (gh->nentries == 0) { + if (r_load) { + *r_load = 0.0; + } + if (r_variance) { + *r_variance = 0.0; + } + if (r_prop_empty_buckets) { + *r_prop_empty_buckets = 1.0; + } + if (r_prop_overloaded_buckets) { + *r_prop_overloaded_buckets = 0.0; + } + if (r_biggest_bucket) { + *r_biggest_bucket = 0; + } - for (i = 0; i < gh->nbuckets; i++) { - uint64_t count = 0; - Entry *e; - for (e = gh->buckets[i]; e; e = e->next) { - count += 1; + return 0.0; + } + + mean = (double)gh->nentries / (double)gh->nbuckets; + if (r_load) { + *r_load = mean; + } + if (r_biggest_bucket) { + *r_biggest_bucket = 0; + } + + if (r_variance) { + /* We already know our mean (i.e. load factor), easy to compute variance. + * See http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Two-pass_algorithm + */ + double sum = 0.0; + for (i = 0; i < gh->nbuckets; i++) { + int count = 0; + Entry *e; + for (e = gh->buckets[i]; e; e = e->next) { + count++; + } + sum += ((double)count - mean) * ((double)count - mean); } - sum += count * (count + 1); + *r_variance = sum / (double)(gh->nbuckets - 1); } - return ((double)sum * (double)gh->nbuckets / - ((double)gh->nentries * (gh->nentries + 2 * gh->nbuckets - 1))); + + { + uint64_t sum = 0; + uint64_t overloaded_buckets_threshold = (uint64_t)max_ii(GHASH_LIMIT_GROW(1), 1); + uint64_t sum_overloaded = 0; + uint64_t sum_empty = 0; + + for (i = 0; i < gh->nbuckets; i++) { + uint64_t count = 0; + Entry *e; + for (e = gh->buckets[i]; e; e = e->next) { + count++; + } + if (r_biggest_bucket) { + *r_biggest_bucket = max_ii(*r_biggest_bucket, (int)count); + } + if (r_prop_overloaded_buckets && (count > overloaded_buckets_threshold)) { + sum_overloaded++; + } + if (r_prop_empty_buckets && !count) { + sum_empty++; + } + sum += count * (count + 1); + } + if (r_prop_overloaded_buckets) { + *r_prop_overloaded_buckets = (double)sum_overloaded / (double)gh->nbuckets; + } + if (r_prop_empty_buckets) { + *r_prop_empty_buckets = (double)sum_empty / (double)gh->nbuckets; + } + return ((double)sum * (double)gh->nbuckets / + ((double)gh->nentries * (gh->nentries + 2 * gh->nbuckets - 1))); + } +} +double BLI_gset_calc_quality_ex( + GSet *gs, double *r_load, double *r_variance, + double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket) +{ + return BLI_ghash_calc_quality_ex((GHash *)gs, r_load, r_variance, + r_prop_empty_buckets, r_prop_overloaded_buckets, r_biggest_bucket); +} + +double BLI_ghash_calc_quality(GHash *gh) +{ + return BLI_ghash_calc_quality_ex(gh, NULL, NULL, NULL, NULL, NULL); } double BLI_gset_calc_quality(GSet *gs) { - return BLI_ghash_calc_quality((GHash *)gs); + return BLI_ghash_calc_quality_ex((GHash *)gs, NULL, NULL, NULL, NULL, NULL); } -#endif /** \} */ 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..f0efe49cfdb 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -230,7 +230,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; 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..311d6dd89ae 100644 --- a/source/blender/blenlib/intern/astar.c +++ b/source/blender/blenlib/intern/astar.c @@ -229,7 +229,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/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/hash_mm2a.c b/source/blender/blenlib/intern/hash_mm2a.c index bae098ae96b..af6ef4f355f 100644 --- a/source/blender/blenlib/intern/hash_mm2a.c +++ b/source/blender/blenlib/intern/hash_mm2a.c @@ -49,6 +49,13 @@ (h) = ((h) * MM2A_M) ^ (k); \ } (void)0 +#define MM2A_MIX_FINALIZE(h) \ +{ \ + (h) ^= (h) >> 13; \ + (h) *= MM2A_M; \ + (h) ^= (h) >> 15; \ +} (void)0 + static void mm2a_mix_tail(BLI_HashMurmur2A *mm2, const unsigned char **data, size_t *len) { while (*len && ((*len < 4) || mm2->count)) { @@ -99,9 +106,40 @@ uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2) MM2A_MIX(mm2->hash, mm2->tail); MM2A_MIX(mm2->hash, mm2->size); - mm2->hash ^= mm2->hash >> 13; - mm2->hash *= MM2A_M; - mm2->hash ^= mm2->hash >> 15; + MM2A_MIX_FINALIZE(mm2->hash); return mm2->hash; } + +/* Non-incremental version, quicker for small keys. */ +uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed) +{ + /* Initialize the hash to a 'random' value */ + uint32_t h = seed ^ len; + + /* Mix 4 bytes at a time into the hash */ + for (; len >= 4; data += 4, len -= 4) { + uint32_t k = *(uint32_t *)data; + + MM2A_MIX(h, k); + } + + /* Handle the last few bytes of the input array */ + switch (len) { + case 3: + h ^= data[2] << 16; + /* fall through */ + case 2: + h ^= data[1] << 8; + /* fall through */ + case 1: + h ^= data[0]; + h *= MM2A_M; + } + + /* Do a few final mixes of the hash to ensure the last few bytes are well-incorporated. */ + MM2A_MIX_FINALIZE(h); + + return h; +} + diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c index d52c09790f9..f267cd777a5 100644 --- a/source/blender/blenlib/intern/listbase.c +++ b/source/blender/blenlib/intern/listbase.c @@ -208,7 +208,7 @@ void BLI_freelinkN(ListBase *listbase, void *vlink) /** * 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 *)) 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 dc62d04ad55..45466226e72 100644 --- a/source/blender/blenlib/intern/math_color_inline.c +++ b/source/blender/blenlib/intern/math_color_inline.c @@ -200,60 +200,46 @@ MINLINE void cpack_cpy_3ub(unsigned char r_col[3], const unsigned int pack) r_col[2] = ((pack) >> 16) & 0xFF; } -/* TODO: + +/** \name RGB/Grayscale Functions * - * regarding #rgb_to_bw vs #rgb_to_grayscale, - * it seems nobody knows why we have both functions which convert color to grays - * but with different influences, this is quite stupid, and should be resolved - * by someone who knows this stuff: see this thread - * http://lists.blender.org/pipermail/bf-committers/2012-June/037180.html + * \warning + * These are only an approximation, + * in almost _all_ cases, #IMB_colormanagement_get_luminance should be used instead. + * however for screen-only colors which don't depend on the currently loaded profile - this is preferred. + * Checking theme colors for contrast, etc. Basically anything outside the render pipeline. * - * Only conclusion is that rgb_to_grayscale is used more for compositing. - */ -MINLINE float rgb_to_bw(const float rgb[3]) -{ - return 0.35f * rgb[0] + 0.45f * rgb[1] + 0.2f * rgb[2]; -} + * \{ */ -/* 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); } -/* luma from defined by 'YCC_JFIF', see #rgb_to_ycc */ -MINLINE float rgb_to_luma(const float rgb[3]) -{ - return 0.299f * rgb[0] + 0.587f * rgb[1] + 0.114f * rgb[2]; -} +/** \} */ -MINLINE unsigned char rgb_to_luma_byte(const unsigned char rgb[3]) -{ - return (unsigned char)(((76 * (unsigned short)rgb[0]) + - (150 * (unsigned short)rgb[1]) + - (29 * (unsigned short)rgb[2])) / 255); -} -/* gamma-corrected RGB --> CIE XYZ - * for this function we only get the Y component - * see: http://software.intel.com/sites/products/documentation/hpc/ipp/ippi/ippi_ch6/ch6_color_models.html - * - * also known as: - * luminance rec. 709 */ -MINLINE float rgb_to_luma_y(const float rgb[3]) -{ - return 0.212671f * rgb[0] + 0.71516f * rgb[1] + 0.072169f * rgb[2]; -} MINLINE int compare_rgb_uchar(const unsigned char col_a[3], const unsigned char col_b[3], const int limit) { diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index ba1f4480659..32308ad1ab5 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -2425,6 +2425,71 @@ void interp_weights_face_v3(float w[4], const float v1[3], const float v2[3], co } } +void interp_weights_face_v3_index(int tri[3], float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3]) +{ + float w2[3]; + + w[0] = w[1] = w[2] = w[3] = 0.0f; + tri[0] = tri[1] = tri[2] = -1; + + /* first check for exact match */ + if (equals_v3v3(co, v1)) { + w[0] = 1.0f; + tri[0] = 0; tri[1] = 1; tri[2] = 3; + } + else if (equals_v3v3(co, v2)) { + w[1] = 1.0f; + tri[0] = 0; tri[1] = 1; tri[2] = 3; + } + else if (equals_v3v3(co, v3)) { + w[2] = 1.0f; + tri[0] = 1; tri[1] = 2; tri[2] = 3; + } + else if (v4 && equals_v3v3(co, v4)) { + w[3] = 1.0f; + tri[0] = 1; tri[1] = 2; tri[2] = 3; + } + else { + /* otherwise compute barycentric interpolation weights */ + float n1[3], n2[3], n[3]; + bool degenerate; + + sub_v3_v3v3(n1, v1, v3); + if (v4) { + sub_v3_v3v3(n2, v2, v4); + } + else { + sub_v3_v3v3(n2, v2, v3); + } + cross_v3_v3v3(n, n1, n2); + + /* OpenGL seems to split this way, so we do too */ + if (v4) { + degenerate = barycentric_weights(v1, v2, v4, co, n, w); + SWAP(float, w[2], w[3]); + tri[0] = 0; tri[1] = 1; tri[2] = 3; + + if (degenerate || (w[0] < 0.0f)) { + /* if w[1] is negative, co is on the other side of the v1-v3 edge, + * so we interpolate using the other triangle */ + degenerate = barycentric_weights(v2, v3, v4, co, n, w2); + + if (!degenerate) { + w[0] = 0.0f; + w[1] = w2[0]; + w[2] = w2[1]; + w[3] = w2[2]; + tri[0] = 1; tri[1] = 2; tri[2] = 3; + } + } + } + else { + barycentric_weights(v1, v2, v3, co, n, w); + tri[0] = 0; tri[1] = 1; tri[2] = 2; + } + } +} + /* return 1 of point is inside triangle, 2 if it's on the edge, 0 if point is outside of triangle */ int barycentric_inside_triangle_v2(const float w[3]) { @@ -3101,6 +3166,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 6b6a3113e0b..fb33fed33e4 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -611,6 +611,48 @@ MINLINE void negate_v3_short(short r[3]) r[2] = (short)-r[2]; } +MINLINE void abs_v2(float r[2]) +{ + r[0] = fabsf(r[0]); + r[1] = fabsf(r[1]); +} + +MINLINE void abs_v2_v2(float r[2], const float a[2]) +{ + r[0] = fabsf(a[0]); + r[1] = fabsf(a[1]); +} + +MINLINE void abs_v3(float r[3]) +{ + r[0] = fabsf(r[0]); + r[1] = fabsf(r[1]); + r[2] = fabsf(r[2]); +} + +MINLINE void abs_v3_v3(float r[3], const float a[3]) +{ + r[0] = fabsf(a[0]); + r[1] = fabsf(a[1]); + r[2] = fabsf(a[2]); +} + +MINLINE void abs_v4(float r[4]) +{ + r[0] = fabsf(r[0]); + r[1] = fabsf(r[1]); + r[2] = fabsf(r[2]); + r[3] = fabsf(r[3]); +} + +MINLINE void abs_v4_v4(float r[4], const float a[4]) +{ + r[0] = fabsf(a[0]); + r[1] = fabsf(a[1]); + r[2] = fabsf(a[2]); + r[3] = fabsf(a[3]); +} + MINLINE float dot_v2v2(const float a[2], const float b[2]) { return a[0] * b[0] + a[1] * b[1]; @@ -638,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..d411c2605d7 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,132 @@ 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; +} + +bool 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) { + /* logic here is a bit complex. Idea is: if ext has been provided, + * fill it with the extension part and do not keep it in filename + * if no ext has been provided, just strip the number or fill it with # + */ + if (ext) { + while (*suffix) { + *ext++ = *suffix++; + } + *ext = 0; + + if (setsharp) { + while (numdigits--) { + *c++ = '#'; + } + } + *c = 0; + } + else { + if (setsharp) { + while (numdigits--) { + *c++ = '#'; + } + } + while (*suffix) { + *c++ = *suffix++; + } + *c = 0; + } + + return true; + } + } + + return false; +} + + +/** * 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 +1147,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 +1346,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..629bed10191 100644 --- a/source/blender/blenlib/intern/polyfill2d.c +++ b/source/blender/blenlib/intern/polyfill2d.c @@ -179,7 +179,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]) { 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..1edc9002611 100644 --- a/source/blender/blenlib/intern/rct.c +++ b/source/blender/blenlib/intern/rct.c @@ -571,3 +571,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..d0420a30448 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; } diff --git a/source/blender/blenlib/intern/stack.c b/source/blender/blenlib/intern/stack.c index 2d3a2f77a3e..3c9e1a52cda 100644 --- a/source/blender/blenlib/intern/stack.c +++ b/source/blender/blenlib/intern/stack.c @@ -216,6 +216,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..6394187d40a 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. @@ -602,6 +296,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; @@ -674,4 +373,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..e41e52a7c6e 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. */ diff --git a/source/blender/blenlib/intern/string_utf8.c b/source/blender/blenlib/intern/string_utf8.c index 67ff532cb6f..22f44a38c7a 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) { 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..50295954192 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 */ @@ -402,6 +407,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 +433,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 */ @@ -797,10 +806,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 +819,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; |