diff options
Diffstat (limited to 'libdimension/internal')
| -rw-r--r-- | libdimension/internal/bvh.h | 79 | ||||
| -rw-r--r-- | libdimension/internal/compiler.h | 71 | ||||
| -rw-r--r-- | libdimension/internal/concurrency.h | 236 | ||||
| -rw-r--r-- | libdimension/internal/future.h | 61 | ||||
| -rw-r--r-- | libdimension/internal/platform.h | 67 | ||||
| -rw-r--r-- | libdimension/internal/polynomial.h | 85 | ||||
| -rw-r--r-- | libdimension/internal/profile.h | 68 | ||||
| -rw-r--r-- | libdimension/internal/prtree.h | 38 | ||||
| -rw-r--r-- | libdimension/internal/rgba.h | 55 |
9 files changed, 760 insertions, 0 deletions
diff --git a/libdimension/internal/bvh.h b/libdimension/internal/bvh.h new file mode 100644 index 0000000..c97e2ba --- /dev/null +++ b/libdimension/internal/bvh.h @@ -0,0 +1,79 @@ +/************************************************************************* + * Copyright (C) 2012-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file. + * Bounding volume hierarchy. This generic interface allows different data + * structures to be represented in the same way, thus sharing code for their + * traversal algorithm. + */ + +#ifndef DMNSN_INTERNAL_BVH_H +#define DMNSN_INTERNAL_BVH_H + +#include "internal.h" +#include "dimension/math.h" +#include "dimension/model.h" +#include <stdbool.h> + +/// A bounding volume hierarchy. +typedef struct dmnsn_bvh dmnsn_bvh; + +/// Available BVH implementations. +typedef enum dmnsn_bvh_kind { + DMNSN_BVH_NONE, + DMNSN_BVH_PRTREE, +} dmnsn_bvh_kind; + +/// Create a BVH. +DMNSN_INTERNAL dmnsn_bvh *dmnsn_new_bvh(const dmnsn_array *objects, + dmnsn_bvh_kind kind); +/// Delete a BVH. +DMNSN_INTERNAL void dmnsn_delete_bvh(dmnsn_bvh *bvh); + +/// Find the closest ray-object intersection in the tree. +DMNSN_INTERNAL bool dmnsn_bvh_intersection(const dmnsn_bvh *bvh, dmnsn_ray ray, dmnsn_intersection *intersection, bool reset); +/// Determine whether a point is inside any object in the tree. +DMNSN_INTERNAL bool dmnsn_bvh_inside(const dmnsn_bvh *bvh, dmnsn_vector point); +/// Return the bounding box of the whole hierarchy. +DMNSN_INTERNAL dmnsn_aabb dmnsn_bvh_aabb(const dmnsn_bvh *bvh); + +/// A non-flat BVH representation, used by BVH implementations. +typedef struct dmnsn_bvh_node { + dmnsn_aabb aabb; ///< The bounding box of this node. + dmnsn_object *object; ///< The object, for leaf nodes. + unsigned int nchildren; ///< How many children this node has. + unsigned int max_children; ///< Maximum number of children. + struct dmnsn_bvh_node *children[]; ///< Flexible array of children. +} dmnsn_bvh_node; + +/// Create a BVH node. +DMNSN_INTERNAL dmnsn_bvh_node *dmnsn_new_bvh_node(unsigned int max_children); + +/// Create a BVH leaf node. +DMNSN_INTERNAL dmnsn_bvh_node *dmnsn_new_bvh_leaf_node(dmnsn_object *object); + +/// Delete a BVH node. +DMNSN_INTERNAL void dmnsn_delete_bvh_node(dmnsn_bvh_node *node); + +/// Add a child to a BVH node. +DMNSN_INTERNAL void dmnsn_bvh_node_add(dmnsn_bvh_node *parent, dmnsn_bvh_node *child); + +#endif // DMNSN_INTERNAL_BVH_H diff --git a/libdimension/internal/compiler.h b/libdimension/internal/compiler.h new file mode 100644 index 0000000..e3555a4 --- /dev/null +++ b/libdimension/internal/compiler.h @@ -0,0 +1,71 @@ +/************************************************************************* + * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Internally-used compiler abstractions. + */ + +#ifndef DMNSN_INTERNAL_H +#error "Please include \"internal.h\" instead of this header directly." +#endif + +#include <stdalign.h> + +/** + * @def DMNSN_HOT + * Mark a function as a hot path. + */ +/** + * @def DMNSN_INTERNAL + * Mark a function as internal linkage. + */ +/** + * @def DMNSN_DESTRUCTOR + * Queue a function to run at program termination. + */ +/** + * @def DMNSN_LATE_DESTRUCTOR + * Queue a function to run at program termination, after those labeled + * DMNSN_DESTRUCTOR. + */ +#if DMNSN_GNUC + #define DMNSN_HOT __attribute__((hot)) + #define DMNSN_INTERNAL __attribute__((visibility("hidden"))) + #define DMNSN_DESTRUCTOR __attribute__((destructor(102))) + #define DMNSN_LATE_DESTRUCTOR __attribute__((destructor(101))) +#else + #define DMNSN_HOT + #define DMNSN_INTERNAL + #define DMNSN_DESTRUCTOR + #define DMNSN_LATE_DESTRUCTOR +#endif + +/// Synonym for _Atomic that stdatomic.h doesn't define for some reason +#define atomic _Atomic + +/// Nearly-compliant alloca variant +#define DMNSN_ALLOCA(var, size) DMNSN_ALLOCA_IMPL(var, size, __LINE__) + +#define DMNSN_ALLOCA_IMPL(var, size, ctr) DMNSN_ALLOCA_IMPL2(var, size, ctr) + +#define DMNSN_ALLOCA_IMPL2(var, size, ctr) \ + alignas(max_align_t) char dmnsn_alloca##ctr[size]; \ + var = (void *)dmnsn_alloca##ctr diff --git a/libdimension/internal/concurrency.h b/libdimension/internal/concurrency.h new file mode 100644 index 0000000..e9c024a --- /dev/null +++ b/libdimension/internal/concurrency.h @@ -0,0 +1,236 @@ +/************************************************************************* + * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Internal threading abstraction. + */ + +#ifndef DMNSN_INTERNAL_CONCURRENCY_H +#define DMNSN_INTERNAL_CONCURRENCY_H + +#include "internal.h" +#include "dimension/concurrency.h" +#include <pthread.h> + +/// Allocate a new future object. +DMNSN_INTERNAL dmnsn_future *dmnsn_new_future(void); + +/// Set the total number of loop iterations. +DMNSN_INTERNAL void dmnsn_future_set_total(dmnsn_future *future, size_t total); +/// Increment the progress of a background task. +DMNSN_INTERNAL void dmnsn_future_increment(dmnsn_future *future); +/// Instantly complete the background teask. +DMNSN_INTERNAL void dmnsn_future_finish(dmnsn_future *future); +/// Set the number of worker threads. +DMNSN_INTERNAL void dmnsn_future_set_nthreads(dmnsn_future *future, unsigned int nthreads); +/// Notify completion of a worker thread. +DMNSN_INTERNAL void dmnsn_future_finish_thread(dmnsn_future *future); + +/** + * Thread callback type. + * @param[in,out] ptr An arbitrary pointer. + * @return 0 on success, non-zero on failure. + */ +typedef int dmnsn_thread_fn(void *ptr); + +/** + * Create a thread that cleans up after itself on errors. + * @param[in,out] future The future object to associate with the thread. + * @param[in] thread_fn The thread callback. + * @param[in,out] arg The pointer to pass to the thread callback. + */ +DMNSN_INTERNAL void dmnsn_new_thread(dmnsn_future *future, + dmnsn_thread_fn *thread_fn, void *arg); + +/** + * Thread callback type for parallel tasks. + * @param[in,out] ptr An arbitrary pointer. + * @param[in] thread An ID for this thread, in [0, \p nthreads). + * @param[in] nthreads The number of concurrent threads. + * @return 0 on success, non-zero on failure. + */ +typedef int dmnsn_ccthread_fn(void *ptr, unsigned int thread, + unsigned int nthreads); + +/** + * Run \p nthreads threads in parallel. + * @param[in,out] future The future object to associate with the threads, + * possibly NULL. + * @param[in] ccthread_fn The routine to run in each concurrent thread. + * @param[in,out] arg The pointer to pass to the thread callbacks. + * @param[in] nthreads The number of concurrent threads to run. + * @return 0 if all threads were successful, and an error code otherwise. + */ +DMNSN_INTERNAL int dmnsn_execute_concurrently(dmnsn_future *future, + dmnsn_ccthread_fn *ccthread_fn, + void *arg, unsigned int nthreads); + +/** + * Initialize a mutex, bailing out on failure. + * @param[out] mutex The mutex to initialize. + */ +DMNSN_INTERNAL void dmnsn_initialize_mutex(pthread_mutex_t *mutex); + +/// dmnsn_lock_mutex() implementation. +DMNSN_INTERNAL void dmnsn_lock_mutex_impl(pthread_mutex_t *mutex); +/// dmnsn_unlock_mutex() implementation. +DMNSN_INTERNAL void dmnsn_unlock_mutex_impl(void *mutex); + +/** + * Lock a mutex, bailing out on failure. + * Contains a {, so must be used in the same block as dmnsn_unlock_mutex(). + * @param[in,out] mutex The mutex to lock. + */ +#define dmnsn_lock_mutex(mutex) do { dmnsn_lock_mutex_impl((mutex)) + +/** + * Unlock a mutex, bailing out on failure. + * Contains a }, so must be used in the same block as dmnsn_lock_mutex(). + * @param[in,out] mutex The mutex to unlock. + */ +#define dmnsn_unlock_mutex(mutex) dmnsn_unlock_mutex_impl((mutex)); } while (0) + +/** + * Destroy a mutex, warning on failure. + * @param[in,out] mutex The mutex to destroy. + */ +DMNSN_INTERNAL void dmnsn_destroy_mutex(pthread_mutex_t *mutex); + +/** + * Initialize a read-write lock, bailing out on failure. + * @param[out] rwlock The read-write lock to initialize. + */ +DMNSN_INTERNAL void dmnsn_initialize_rwlock(pthread_rwlock_t *rwlock); + +/// dmnsn_read_lock() implementation. +DMNSN_INTERNAL void dmnsn_read_lock_impl(pthread_rwlock_t *rwlock); +/// dmnsn_write_lock() implementation. +DMNSN_INTERNAL void dmnsn_write_lock_impl(pthread_rwlock_t *rwlock); +/// dmnsn_unlock_rwlock() implementation. +DMNSN_INTERNAL void dmnsn_unlock_rwlock_impl(pthread_rwlock_t *rwlock); + +/** + * Read-lock a read-write lock, bailing out on failure. + * Contains a {, so must be used in the same block as dmnsn_unlock_rwlock(). + * @param[in,out] rwlock The read-write lock to lock. + */ +#define dmnsn_read_lock(rwlock) do { dmnsn_read_lock_impl((rwlock)) + +/** + * Write-lock a read-write lock, bailing out on failure. + * Contains a {, so must be used in the same block as dmnsn_unlock_rwlock(). + * @param[in,out] rwlock The read-write lock to lock. + */ +#define dmnsn_write_lock(rwlock) do { dmnsn_write_lock_impl((rwlock)) + +/** + * Unlock a read-write lock, bailing out on failure. + * Contains a }, so must be used in the same block as dmnsn_read_lock() or + * dmnsn_write_lock(). + * @param[in,out] rwlock The read-write lock to lock. + */ +#define dmnsn_unlock_rwlock(rwlock) \ + dmnsn_unlock_rwlock_impl((rwlock)); } while (0) + +/** + * Destroy a read-write lock, warning on failure. + * @param[in,out] rwlock The read-write lock to destroy. + */ +DMNSN_INTERNAL void dmnsn_destroy_rwlock(pthread_rwlock_t *rwlock); + +/** + * Initialize a condition variable, bailing out on failure. + * @param[out] cond The condition variable to initialize. + */ +DMNSN_INTERNAL void dmnsn_initialize_cond(pthread_cond_t *cond); + +/** + * Wait on a condition variable, bailing out on error. + * @param[in] cond The condition variable to wait on. + * @param[in] mutex The associated mutex. + */ +DMNSN_INTERNAL void dmnsn_cond_wait(pthread_cond_t *cond, + pthread_mutex_t *mutex); + +/** + * Wait on a condition variable, bailing out on error, and unlock the mutex if + * cancelled. + * @param[in] cond The condition variable to wait on. + * @param[in] mutex The associated mutex. + */ +#define dmnsn_cond_wait_safely(cond, mutex) \ + do { \ + pthread_cleanup_push(dmnsn_unlock_mutex_impl, (mutex)); \ + dmnsn_cond_wait((cond), (mutex)); \ + pthread_cleanup_pop(false); \ + } while (0) + +/** + * Signal a condition variable, bailing out on error. + * @param[in] cond The condition variable to signal. + */ +DMNSN_INTERNAL void dmnsn_cond_broadcast(pthread_cond_t *cond); + +/** + * Destroy a condition variable, warning on failure. + * @param[in,out] cond The condition variable to destroy. + */ +DMNSN_INTERNAL void dmnsn_destroy_cond(pthread_cond_t *cond); + +/** + * Once-called callback type. + */ +typedef void dmnsn_once_fn(void); + +/** + * Call a function exactly once, bailing out on failure. + * @param[in,out] once The once control. + * @param[in] once_fn The function to call. + */ +DMNSN_INTERNAL void dmnsn_once(pthread_once_t *once, dmnsn_once_fn *once_fn); + +/** + * Initialize a thread-local storage key, bailing out on failure. + * @param[out] key The key to initialize. + * @param[in] destructor An optional destructor callback. + */ +DMNSN_INTERNAL void dmnsn_key_create(pthread_key_t *key, dmnsn_callback_fn *destructor); + +/** + * Set a thread-specific pointer, bailing out on failure. + * @param[in] key The thread-local storage key. + * @param[in] value The value to set. + */ +DMNSN_INTERNAL void dmnsn_setspecific(pthread_key_t key, const void *value); + +/** + * Destroy a thread-local storage key, warning on failure. + * @param[out] key The key to destroy. + */ +DMNSN_INTERNAL void dmnsn_key_delete(pthread_key_t key); + +/** + * Join a thread, bailing out on failure. + * @param[in,out] thread The thread to join. + */ +DMNSN_INTERNAL void dmnsn_join_thread(pthread_t thread, void **retval); + +#endif // DMNSN_INTERNAL_CONCURRENCY_H diff --git a/libdimension/internal/future.h b/libdimension/internal/future.h new file mode 100644 index 0000000..047523e --- /dev/null +++ b/libdimension/internal/future.h @@ -0,0 +1,61 @@ +/************************************************************************* + * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Future object implementation. + */ + +#ifndef DMNSN_INTERNAL_FUTURE_H +#define DMNSN_INTERNAL_FUTURE_H + +#include <pthread.h> + +struct dmnsn_future { + size_t progress; ///< Completed loop iterations. + size_t total; ///< Total expected loop iterations. + + /// The worker thread. + pthread_t thread; + + /// Mutex to guard progress and total. + pthread_mutex_t mutex; + + /// Condition variable for waiting for a particular amount of progress. + pthread_cond_t cond; + + /// Minimum waited-on value. + double min_wait; + + /// Number of threads working on the future's background task. + unsigned int nthreads; + /// Number of threads not yet paused. + unsigned int nrunning; + /// Count of threads holding the future paused. + unsigned int npaused; + /// Condition variable for waiting for nrunning == 0. + pthread_cond_t none_running_cond; + /// Condition variable for waiting for nrunning == nthreads. + pthread_cond_t all_running_cond; + /// Condition variable for waiting for npaused == 0. + pthread_cond_t resume_cond; +}; + +#endif // DMNSN_INTERNAL_FUTURE_H diff --git a/libdimension/internal/platform.h b/libdimension/internal/platform.h new file mode 100644 index 0000000..e037d21 --- /dev/null +++ b/libdimension/internal/platform.h @@ -0,0 +1,67 @@ +/************************************************************************* + * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Internal platform abstractions. + */ + +#ifndef DMNSN_INTERNAL_PLATFORM_H +#define DMNSN_INTERNAL_PLATFORM_H + +#include "internal.h" +#include "dimension/platform.h" +#include <stdbool.h> +#include <stddef.h> +#include <stdio.h> + +/** + * Print a stack trace, if implemented for the current platform. + * @param[in,out] file The file to which to write the stack trace. + */ +DMNSN_INTERNAL void dmnsn_backtrace(FILE *file); + +/** + * Is the calling thread the main thread? + * @return Whether this is the main execution thread, or \c true if we can't + * tell. + */ +DMNSN_INTERNAL bool dmnsn_is_main_thread(void); + +/** + * Are we running on a little-endian computer? + * @return Whether the current architecture is little-endian. + */ +DMNSN_INTERNAL bool dmnsn_is_little_endian(void); + +/** + * How many CPUs are available? + * @return The number of CPUs available to dimension. + */ +DMNSN_INTERNAL size_t dmnsn_ncpus(void); + +/** + * Calculate process times. + * @param[out] timer The timer in which to store the current total process + * times. + */ +DMNSN_INTERNAL void dmnsn_get_times(dmnsn_timer *timer); + +#endif // DMNSN_INTERNAL_PLATFORM_H diff --git a/libdimension/internal/polynomial.h b/libdimension/internal/polynomial.h new file mode 100644 index 0000000..7af3e5a --- /dev/null +++ b/libdimension/internal/polynomial.h @@ -0,0 +1,85 @@ +/************************************************************************* + * Copyright (C) 2009-2011 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Utility functions for working with and numerically solving polynomials. + * Polynomials are represented as simple arrays where the ith element is the + * coefficient on x^i. In general, we are only interested in positive roots. + */ + +#include "internal.h" +#include <stddef.h> +#include <stdio.h> + +/** + * Evaluate a polynomial at \p x. + * @param[in] poly The coefficients of the polynomial to evaluate, in order + * from lowest degree to highest degree. The array should + * have dimension <tt>degree + 1</tt>. + * @param[in] degree The degree of the polynomial. + * @param[in] x The value of the variable at which to evaluate. + */ +DMNSN_INTERNAL DMNSN_INLINE double +dmnsn_polynomial_evaluate(const double poly[], size_t degree, double x) +{ + double ret = poly[degree]; + size_t i; + for (i = degree; i-- > 0;) { + ret = ret*x + poly[i]; + } + return ret; +} + +/** + * Evaluate the derivative of a polynomial at \p x. + * @param[in] poly The coefficients of the polynomial to evaluate. + * @param[in] degree The degree of the polynomial. + * @param[in] x The value of the variable at which to evaluate. + */ +DMNSN_INTERNAL DMNSN_INLINE double +dmnsn_polynomial_evaluate_derivative(const double poly[], size_t degree, double x) +{ + double ret = poly[degree]*degree; + size_t i; + for (i = degree - 1; i >= 1; --i) { + ret = ret*x + poly[i]*i; + } + return ret; +} + +/** + * Find the positive roots of a polynomial. + * @param[in] poly The coefficients of the polynomial to solve. + * @param[in] degree The degree of the polynomial. + * @param[out] x An array in which to store the roots. It should have + * dimension \p degree. + * @return The number of positive roots stored in \c x[]. + */ +DMNSN_INTERNAL size_t dmnsn_polynomial_solve(const double poly[], size_t degree, double x[]); + +/** + * Output a polynomial. The polynomial is printed as a function of x suitable + * for input into a CAS, and without a trailing newline. + * @param[in,out] file The file to write to. + * @param[in] poly The coefficients of the polynomial to print. + * @param[in] degree The degree of the polynomial. + */ +DMNSN_INTERNAL void dmnsn_polynomial_print(FILE *file, const double poly[], size_t degree); diff --git a/libdimension/internal/profile.h b/libdimension/internal/profile.h new file mode 100644 index 0000000..0f59b8f --- /dev/null +++ b/libdimension/internal/profile.h @@ -0,0 +1,68 @@ +/************************************************************************* + * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Built-in branch profiler. + */ + +#ifndef DMNSN_INTERNAL_H +#error "Please include \"internal.h\" instead of this header directly." +#endif + +#include <stdbool.h> + +/** + * @def dmnsn_likely + * Indicate that a test is likely to succeed. + * @param test The test to perform. + * @return The truth value of \p test. + */ +/** + * @def dmnsn_unlikely + * Indicate that a test is unlikely to succeed. + * @param test The test to perform. + * @return The truth value of \p test. + */ +#ifdef DMNSN_PROFILE + #define dmnsn_likely(test) \ + dmnsn_expect(!!(test), true, DMNSN_FUNC, __FILE__, __LINE__) + #define dmnsn_unlikely(test) \ + dmnsn_expect(!!(test), false, DMNSN_FUNC, __FILE__, __LINE__) +#elif DMNSN_GNUC + #define dmnsn_likely(test) __builtin_expect(!!(test), true) + #define dmnsn_unlikely(test) __builtin_expect(!!(test), false) +#else + #define dmnsn_likely(test) (!!(test)) + #define dmnsn_unlikely(test) (!!(test)) +#endif + +/** + * Record a test and its expected result. Called by dmnsn_[un]likely(); + * don't call directly. + * @param[in] result The result of the test. + * @param[in] expected The expected result of the test. + * @param[in] func The name of the function the test occurs in. + * @param[in] file The name of the file the test occurs in. + * @param[in] line The line number on which the test occurs. + * @return \p result. + */ +DMNSN_INTERNAL bool dmnsn_expect(bool result, bool expected, const char *func, + const char *file, unsigned int line); diff --git a/libdimension/internal/prtree.h b/libdimension/internal/prtree.h new file mode 100644 index 0000000..7d85f44 --- /dev/null +++ b/libdimension/internal/prtree.h @@ -0,0 +1,38 @@ +/************************************************************************* + * Copyright (C) 2010-2012 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file. + * Priority R-trees. PR-trees are a data structure introduced by Arge, de Berg, + * Haverkort, and Yi, which provides asymptotically optimal worst-case lookup, + * while remaining efficient with real-world data. Their structure is derived + * from B-trees. + */ + +#ifndef DMNSN_INTERNAL_PRTREE_H +#define DMNSN_INTERNAL_PRTREE_H + +#include "internal.h" +#include "internal/bvh.h" + +/// Create a PR-tree. +DMNSN_INTERNAL dmnsn_bvh_node *dmnsn_new_prtree(const dmnsn_array *objects); + +#endif // DMNSN_INTERNAL_PRTREE_H diff --git a/libdimension/internal/rgba.h b/libdimension/internal/rgba.h new file mode 100644 index 0000000..964d622 --- /dev/null +++ b/libdimension/internal/rgba.h @@ -0,0 +1,55 @@ +/************************************************************************* + * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * RGBA canvas optimizer interface, used by image optimizers. + */ + +#ifndef DMNSN_INTERNAL_RGBA_H +#define DMNSN_INTERNAL_RGBA_H + +#include "internal.h" +#include "dimension/canvas.h" +#include <stdint.h> + +/// RGBA8 optimizer type. +typedef struct dmnsn_rgba8_optimizer { + dmnsn_canvas_optimizer optimizer; + uint8_t data[]; +} dmnsn_rgba8_optimizer; + +/// RGBA16 optimizer type. +typedef struct dmnsn_rgba16_optimizer { + dmnsn_canvas_optimizer optimizer; + uint16_t data[]; +} dmnsn_rgba16_optimizer; + +/// Apply the RGBA8 optimizer to a canvas. +DMNSN_INTERNAL void dmnsn_rgba8_optimize_canvas(dmnsn_pool *pool, dmnsn_canvas *canvas); +/// Apply the RGBA16 optimizer to a canvas. +DMNSN_INTERNAL void dmnsn_rgba16_optimize_canvas(dmnsn_pool *pool, dmnsn_canvas *canvas); + +/// RGBA8 optimizer callback. +DMNSN_INTERNAL void dmnsn_rgba8_optimizer_fn(dmnsn_canvas_optimizer *optimizer, const dmnsn_canvas *canvas, size_t x, size_t y); +/// RGBA16 optimizer callback. +DMNSN_INTERNAL void dmnsn_rgba16_optimizer_fn(dmnsn_canvas_optimizer *optimizer, const dmnsn_canvas *canvas, size_t x, size_t y); + +#endif // DMNSN_INTERNAL_RGBA_H |