Revision: 75707
http://sourceforge.net/p/brlcad/code/75707
Author: starseeker
Date: 2020-05-06 18:01:22 +0000 (Wed, 06 May 2020)
Log Message:
-----------
cleanup, use bu_sort
Modified Paths:
--------------
brlcad/trunk/doc/legal/embedded/OpenNURBS.txt
brlcad/trunk/src/libbrep/CMakeLists.txt
brlcad/trunk/src/libbrep/openNURBS/opennurbs_lookup.cpp
brlcad/trunk/src/libbrep/openNURBS/opennurbs_mesh.cpp
brlcad/trunk/src/libbrep/openNURBS/opennurbs_sort.cpp
Removed Paths:
-------------
brlcad/trunk/src/libbrep/openNURBS/CMakeLists.txt
brlcad/trunk/src/libbrep/openNURBS/opennurbs_qsort_template.h
Modified: brlcad/trunk/doc/legal/embedded/OpenNURBS.txt
===================================================================
--- brlcad/trunk/doc/legal/embedded/OpenNURBS.txt 2020-05-06 17:14:34 UTC
(rev 75706)
+++ brlcad/trunk/doc/legal/embedded/OpenNURBS.txt 2020-05-06 18:01:22 UTC
(rev 75707)
@@ -198,7 +198,6 @@
file:src/libbrep/openNURBS/opennurbs_polylinecurve.cpp
file:src/libbrep/openNURBS/opennurbs_polylinecurve.h
file:src/libbrep/openNURBS/opennurbs_precompiledheader.cpp
-file:src/libbrep/openNURBS/opennurbs_qsort_template.h
file:src/libbrep/openNURBS/opennurbs_rand.cpp
file:src/libbrep/openNURBS/opennurbs_rand.h
file:src/libbrep/openNURBS/opennurbs_rendering.h
Modified: brlcad/trunk/src/libbrep/CMakeLists.txt
===================================================================
--- brlcad/trunk/src/libbrep/CMakeLists.txt 2020-05-06 17:14:34 UTC (rev
75706)
+++ brlcad/trunk/src/libbrep/CMakeLists.txt 2020-05-06 18:01:22 UTC (rev
75707)
@@ -333,7 +333,6 @@
openNURBS/opennurbs_polyedgecurve.h
openNURBS/opennurbs_polyline.h
openNURBS/opennurbs_polylinecurve.h
- openNURBS/opennurbs_qsort_template.h
openNURBS/opennurbs_rand.h
openNURBS/opennurbs_rendering.h
openNURBS/opennurbs_revsurface.h
Deleted: brlcad/trunk/src/libbrep/openNURBS/CMakeLists.txt
===================================================================
--- brlcad/trunk/src/libbrep/openNURBS/CMakeLists.txt 2020-05-06 17:14:34 UTC
(rev 75706)
+++ brlcad/trunk/src/libbrep/openNURBS/CMakeLists.txt 2020-05-06 18:01:22 UTC
(rev 75707)
@@ -1,409 +0,0 @@
-# Note: License below is for CMake build logic of openNURBS. For license of
-# primary openNURBS source code, see license.txt file
-#
-# Copyright (c) 2010-2016 United States Government as represented by the U.S.
-# Army Research Laboratory.
-#
-# Redistribution and use in source and binary forms, with or without
-# modification, are permitted provided that the following conditions are met:
-#
-# 1. Redistributions of source code must retain the above copyright notice,
-# this list of conditions and the following disclaimer.
-#
-# 2. Redistributions in binary form must reproduce the above copyright notice,
-# this list of conditions and the following disclaimer in the documentation
-# and/or other materials provided with the distribution.
-#
-# 3. The name of the author may not be used to endorse or promote products
-# derived from this software without specific prior written permission.
-#
-# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
-# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
-# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
-# EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
-# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
-# OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
-# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
-# OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
-# ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-# Minimum required version of CMake
-cmake_minimum_required(VERSION 3.1.3)
-
-project(OPENNURBS)
-
-# Generate position independent code by default (i.e. -fPIC)
-set(CMAKE_POSITION_INDEPENDENT_CODE TRUE)
-
-# If we can, use OBJECT libraries to build both shared and static
-# libraries from the same .o files, saving double compilation
-include(CMakeDependentOption)
-cmake_dependent_option(USE_OBJECT_LIBS "Use OBJECT libraries" ON "NOT
CPP_DLL_DEFINES" OFF)
-
-if(BRLCAD_FLAGS_DEBUG)
- add_definitions(${DEBUG_CXX_FLAGS})
-endif(BRLCAD_FLAGS_DEBUG)
-
-# build shared libs by default
-if(NOT DEFINED BUILD_SHARED_LIBS)
- set(BUILD_SHARED_LIBS ON)
-endif(NOT DEFINED BUILD_SHARED_LIBS)
-
-# build static libs by default
-if(NOT DEFINED BUILD_STATIC_LIBS)
- set(BUILD_STATIC_LIBS ON)
-endif(NOT DEFINED BUILD_STATIC_LIBS)
-
-# Define destinations if not already set
-if(NOT DEFINED BIN_DIR)
- set(BIN_DIR bin)
-endif(NOT DEFINED BIN_DIR)
-if(NOT DEFINED LIB_DIR)
- set(LIB_DIR lib)
-endif(NOT DEFINED LIB_DIR)
-
-# Passed to OpenNURBS build to turn on/off any extentions/modifications to the
base code
-# specific to BRLCAD. Initially used for unwrapping UV points in a closed
surface to
-# allowing for trims that extend over a closed seam.
-# It's an expert's setting at the moment.
-option(BRLCAD_ENABLE_OPENNURBS_EXTENSIONS "Enables BRLCAD related extensions
to OpenNURBS" ON)
-mark_as_advanced(BRLCAD_ENABLE_OPENNURBS_EXTENSIONS)
-
-# these are files no longer in upstream openNURBS but retained for reference
-set(OPENNURBS_REF
- opennurbs_basic.cpp
- opennurbs_brep_changesrf.cpp
- opennurbs_brep_kinky.cpp
- opennurbs_x.cpp
- )
-
-# these are files we turn off because we don't use them and they incur some
-# cost to enable (e.g., they require OpenGL)
-set(OPENNURBS_OFF
- opennurbs_gl.cpp
- opennurbs_gl.h
- opennurbs_precompiledheader.cpp
- opennurbs_zlib_memory.cpp
- opennurbs_x.h
- )
-
-set(OPENNURBS_SOURCES
- ${OPENNURBS_REF}
- opennurbs_3dm_attributes.cpp
- opennurbs_3dm_properties.cpp
- opennurbs_3dm_settings.cpp
- opennurbs_annotation.cpp
- opennurbs_annotation2.cpp
- opennurbs_arc.cpp
- opennurbs_arccurve.cpp
- opennurbs_archive.cpp
- opennurbs_array.cpp
- opennurbs_base32.cpp
- opennurbs_base64.cpp
- opennurbs_beam.cpp
- opennurbs_bezier.cpp
- opennurbs_beziervolume.cpp
- opennurbs_bitmap.cpp
- opennurbs_bounding_box.cpp
- opennurbs_box.cpp
- opennurbs_brep.cpp
- opennurbs_brep_extrude.cpp
- opennurbs_brep_io.cpp
- opennurbs_brep_isvalid.cpp
- opennurbs_brep_region.cpp
- opennurbs_brep_tools.cpp
- opennurbs_brep_v2valid.cpp
- opennurbs_circle.cpp
- opennurbs_color.cpp
- opennurbs_compress.cpp
- opennurbs_cone.cpp
- opennurbs_crc.cpp
- opennurbs_curve.cpp
- opennurbs_curveonsurface.cpp
- opennurbs_curveproxy.cpp
- opennurbs_cylinder.cpp
- opennurbs_defines.cpp
- opennurbs_detail.cpp
- opennurbs_dimstyle.cpp
- opennurbs_dll.cpp
- opennurbs_ellipse.cpp
- opennurbs_embedded_file.cpp
- opennurbs_error.cpp
- opennurbs_error_message.cpp
- opennurbs_evaluate_nurbs.cpp
- opennurbs_extensions.cpp
- opennurbs_font.cpp
- opennurbs_fsp.cpp
- opennurbs_geometry.cpp
- opennurbs_group.cpp
- opennurbs_hatch.cpp
- opennurbs_instance.cpp
- opennurbs_intersect.cpp
- opennurbs_knot.cpp
- opennurbs_layer.cpp
- opennurbs_light.cpp
- opennurbs_line.cpp
- opennurbs_linecurve.cpp
- opennurbs_linetype.cpp
- opennurbs_lookup.cpp
- opennurbs_material.cpp
- opennurbs_math.cpp
- opennurbs_massprop.cpp
- opennurbs_matrix.cpp
- opennurbs_memory.c
- opennurbs_memory_util.c
- opennurbs_mesh.cpp
- opennurbs_mesh_ngon.cpp
- opennurbs_mesh_tools.cpp
- opennurbs_morph.cpp
- opennurbs_nurbscurve.cpp
- opennurbs_nurbssurface.cpp
- opennurbs_nurbsvolume.cpp
- opennurbs_object.cpp
- opennurbs_object_history.cpp
- opennurbs_objref.cpp
- opennurbs_offsetsurface.cpp
- opennurbs_optimize.cpp
- opennurbs_plane.cpp
- opennurbs_planesurface.cpp
- opennurbs_pluginlist.cpp
- opennurbs_point.cpp
- opennurbs_pointcloud.cpp
- opennurbs_pointgeometry.cpp
- opennurbs_pointgrid.cpp
- opennurbs_polycurve.cpp
- opennurbs_polyedgecurve.cpp
- opennurbs_polyline.cpp
- opennurbs_polylinecurve.cpp
- opennurbs_rand.cpp
- opennurbs_revsurface.cpp
- opennurbs_rtree.cpp
- opennurbs_sort.cpp
- opennurbs_sphere.cpp
- opennurbs_string.cpp
- opennurbs_sum.cpp
- opennurbs_sumsurface.cpp
- opennurbs_surface.cpp
- opennurbs_surfaceproxy.cpp
- opennurbs_textlog.cpp
- opennurbs_torus.cpp
- opennurbs_unicode.cpp
- opennurbs_userdata.cpp
- opennurbs_uuid.cpp
- opennurbs_viewport.cpp
- opennurbs_workspace.cpp
- opennurbs_wstring.cpp
- opennurbs_xform.cpp
- opennurbs_zlib.cpp
- )
-
-SET(OPENNURBS_HEADERS
- opennurbs.h
- opennurbs_3dm.h
- opennurbs_3dm_attributes.h
- opennurbs_3dm_properties.h
- opennurbs_3dm_settings.h
- opennurbs_annotation.h
- opennurbs_annotation2.h
- opennurbs_arc.h
- opennurbs_arccurve.h
- opennurbs_archive.h
- opennurbs_array.h
- opennurbs_array_defs.h
- opennurbs_base32.h
- opennurbs_base64.h
- opennurbs_beam.h
- opennurbs_bezier.h
- opennurbs_bitmap.h
- opennurbs_bounding_box.h
- opennurbs_box.h
- opennurbs_brep.h
- opennurbs_circle.h
- opennurbs_color.h
- opennurbs_compress.h
- opennurbs_cone.h
- opennurbs_crc.h
- opennurbs_curve.h
- opennurbs_curveonsurface.h
- opennurbs_curveproxy.h
- opennurbs_cylinder.h
- opennurbs_defines.h
- opennurbs_detail.h
- opennurbs_dimstyle.h
- opennurbs_dll_resource.h
- opennurbs_ellipse.h
- opennurbs_error.h
- opennurbs_evaluate_nurbs.h
- opennurbs_extensions.h
- opennurbs_font.h
- opennurbs_fpoint.h
- opennurbs_fsp.h
- opennurbs_fsp_defs.h
- opennurbs_geometry.h
- opennurbs_group.h
- opennurbs_hatch.h
- opennurbs_hsort_template.h
- opennurbs_instance.h
- opennurbs_intersect.h
- opennurbs_knot.h
- opennurbs_layer.h
- opennurbs_light.h
- opennurbs_line.h
- opennurbs_linecurve.h
- opennurbs_linestyle.h
- opennurbs_linetype.h
- opennurbs_lookup.h
- opennurbs_mapchan.h
- opennurbs_massprop.h
- opennurbs_material.h
- opennurbs_math.h
- opennurbs_matrix.h
- opennurbs_memory.h
- opennurbs_mesh.h
- opennurbs_nurbscurve.h
- opennurbs_nurbssurface.h
- opennurbs_object.h
- opennurbs_object_history.h
- opennurbs_objref.h
- opennurbs_offsetsurface.h
- opennurbs_optimize.h
- opennurbs_plane.h
- opennurbs_planesurface.h
- opennurbs_pluginlist.h
- opennurbs_point.h
- opennurbs_pointcloud.h
- opennurbs_pointgeometry.h
- opennurbs_pointgrid.h
- opennurbs_polycurve.h
- opennurbs_polyedgecurve.h
- opennurbs_polyline.h
- opennurbs_polylinecurve.h
- opennurbs_qsort_template.h
- opennurbs_rand.h
- opennurbs_rendering.h
- opennurbs_revsurface.h
- opennurbs_rtree.h
- opennurbs_sphere.h
- opennurbs_string.h
- opennurbs_sumsurface.h
- opennurbs_surface.h
- opennurbs_surfaceproxy.h
- opennurbs_system.h
- opennurbs_textlog.h
- opennurbs_texture.h
- opennurbs_texture_mapping.h
- opennurbs_torus.h
- opennurbs_unicode.h
- opennurbs_userdata.h
- opennurbs_uuid.h
- opennurbs_version.h
- opennurbs_viewport.h
- opennurbs_workspace.h
- opennurbs_x.h
- opennurbs_xform.h
- opennurbs_zlib.h
- )
-
-include(CheckIncludeFiles)
-check_include_files(emmintrin.h HAVE_EMMINTRIN_H)
-check_include_files(ieeefp.h HAVE_IEEEFP_H)
-check_include_files(sys/stat.h HAVE_SYS_STAT_H)
-if(HAVE_EMMINTRIN_H)
- add_definitions(-DHAVE_EMMINTRIN_H)
-endif(HAVE_EMMINTRIN_H)
-if(HAVE_IEEEFP_H)
- add_definitions(-DHAVE_IEEEFP_H)
-endif(HAVE_IEEEFP_H)
-if(HAVE_SYS_STAT_H)
- add_definitions(-DHAVE_SYS_STAT_H)
-endif(HAVE_SYS_STAT_H)
-
-if(BRLCAD_ENABLE_OPENNURBS_EXTENSIONS)
- add_definitions(-DBRLCAD_FEATURE_EXTEND_UV_OVER_CLOSED_SEAMS)
-endif(BRLCAD_ENABLE_OPENNURBS_EXTENSIONS)
-
-find_package(ZLIB REQUIRED)
-
-set(OPENNURBS_LINKLIBRARIES ${ZLIB_LIBRARIES})
-
-# Ideally, we should only need ZLIB here
-include_directories(
- ${${CMAKE_PROJECT_NAME}_SOURCE_DIR}/include
- ${ZLIB_INCLUDE_DIRS}
- )
-
-add_definitions(-DON_COMPILING_OPENNURBS)
-if (MSVC)
- add_definitions(-DUNICODE)
- set(OPENNURBS_LINKLIBRARIES ${OPENNURBS_LINKLIBRARIES} Rpcrt4)
-endif(MSVC)
-
-if("${CMAKE_BUILD_TYPE}" STREQUAL "Release")
- include(CheckCXXCompilerFlag)
- check_cxx_compiler_flag(-O3 HAVE_O3)
- if(HAVE_O3)
- set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3")
- endif(HAVE_O3)
-endif("${CMAKE_BUILD_TYPE}" STREQUAL "Release")
-
-# Based on the options, define libraries as either stand-alone builds
-# or dependencies on OBJECT library builds
-if(NOT USE_OBJECT_LIBS)
- if(BUILD_SHARED_LIBS)
- add_library(openNURBS SHARED ${OPENNURBS_SOURCES})
- if(MSVC)
- set_property(TARGET openNURBS APPEND PROPERTY COMPILE_DEFINITIONS
"ON_DLL_EXPORTS")
- endif(MSVC)
- endif(BUILD_SHARED_LIBS)
- if(BUILD_STATIC_LIBS)
- add_library(openNURBS-static STATIC ${OPENNURBS_SOURCES})
- endif(BUILD_STATIC_LIBS)
-else(NOT USE_OBJECT_LIBS)
- add_library(openNURBS-obj OBJECT ${OPENNURBS_SOURCES})
- if(BUILD_SHARED_LIBS)
- add_library(openNURBS SHARED $<TARGET_OBJECTS:openNURBS-obj>)
- if(MSVC)
- set_property(TARGET openNURBS APPEND PROPERTY COMPILE_DEFINITIONS
"ON_DLL_EXPORTS")
- endif(MSVC)
- endif(BUILD_SHARED_LIBS)
- if(BUILD_STATIC_LIBS)
- add_library(openNURBS-static STATIC $<TARGET_OBJECTS:openNURBS-obj>)
- endif(BUILD_STATIC_LIBS)
-endif(NOT USE_OBJECT_LIBS)
-
-
-if(BUILD_SHARED_LIBS)
- if(OPENNURBS_LINKLIBRARIES)
- target_link_libraries(openNURBS ${OPENNURBS_LINKLIBRARIES})
- endif(OPENNURBS_LINKLIBRARIES)
- set_target_properties(openNURBS PROPERTIES VERSION "2012.10.245")
- install(TARGETS openNURBS
- RUNTIME DESTINATION ${BIN_DIR}
- LIBRARY DESTINATION ${LIB_DIR}
- ARCHIVE DESTINATION ${LIB_DIR})
-endif(BUILD_SHARED_LIBS)
-
-if(BUILD_STATIC_LIBS)
- target_link_libraries(openNURBS-static ${OPENNURBS_LINKLIBRARIES})
- if(MSVC)
- # msvc does not append 'lib' - do it here to have consistent name
- set_target_properties(openNURBS-static PROPERTIES PREFIX "lib")
- else(MSVC)
- set_target_properties(openNURBS-static PROPERTIES OUTPUT_NAME "openNURBS")
- endif(MSVC)
- install(TARGETS openNURBS-static
- RUNTIME DESTINATION ${BIN_DIR}
- LIBRARY DESTINATION ${LIB_DIR}
- ARCHIVE DESTINATION ${LIB_DIR})
-endif(BUILD_STATIC_LIBS)
-
-install(FILES ${OPENNURBS_HEADERS} DESTINATION include/openNURBS)
-
-# Local Variables:
-# tab-width: 8
-# mode: cmake
-# indent-tabs-mode: t
-# End:
-# ex: shiftwidth=2 tabstop=8
-
Modified: brlcad/trunk/src/libbrep/openNURBS/opennurbs_lookup.cpp
===================================================================
--- brlcad/trunk/src/libbrep/openNURBS/opennurbs_lookup.cpp 2020-05-06
17:14:34 UTC (rev 75706)
+++ brlcad/trunk/src/libbrep/openNURBS/opennurbs_lookup.cpp 2020-05-06
18:01:22 UTC (rev 75707)
@@ -14,6 +14,8 @@
////////////////////////////////////////////////////////////////
*/
+#include "common.h"
+#include "bu/sort.h"
#include "opennurbs.h"
static bool IdIsNotZero(const ON_UUID* id)
@@ -216,34 +218,15 @@
}
}
-
-
-/*
-The defines and #include generates a fast sorting function
-static void ON_qsort_SN_ELEMENT( struct ON_SerialNumberMap::SN_ELEMENT* base,
size_t nel );
-*/
-
-#define ON_SORT_TEMPLATE_COMPARE compare_SN_ELEMENT_sn
-#define ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS
-#define ON_SORT_TEMPLATE_STATIC_FUNCTION
-#define ON_SORT_TEMPLATE_TYPE struct ON_SerialNumberMap::SN_ELEMENT
-#define ON_QSORT_FNAME ON_qsort_SN_ELEMENT
-
-static int ON_SORT_TEMPLATE_COMPARE(const struct
ON_SerialNumberMap::SN_ELEMENT * a, const struct ON_SerialNumberMap::SN_ELEMENT
* b)
+static int
+snm_cmp(const void *p1, const void *p2, void *UNUSED(arg))
{
- unsigned int asn, bsn;
- return ( ( (asn = a->m_sn) < (bsn = b->m_sn) ) ? -1 : (asn > bsn) ? 1 : 0 );
+ const struct ON_SerialNumberMap::SN_ELEMENT *a = (const struct
ON_SerialNumberMap::SN_ELEMENT *) p1;
+ const struct ON_SerialNumberMap::SN_ELEMENT *b = (const struct
ON_SerialNumberMap::SN_ELEMENT *) p2;
+ unsigned int asn, bsn;
+ return ( ( (asn = a->m_sn) < (bsn = b->m_sn) ) ? -1 : (asn > bsn) ? 1 : 0
);
}
-#include "opennurbs_qsort_template.h"
-
-#undef ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS
-#undef ON_SORT_TEMPLATE_STATIC_FUNCTION
-#undef ON_SORT_TEMPLATE_TYPE
-#undef ON_QSORT_FNAME
-#undef ON_SORT_TEMPLATE_COMPARE
-
-
void ON_SerialNumberMap::SN_BLOCK::SortBlockHelper()
{
// Sort m_sn[] by serial number.
@@ -263,55 +246,8 @@
if ( m_count > 1 )
{
-#if 1
// Quick sort
- ON_qsort_SN_ELEMENT(m_sn, m_count);
-#else
- // Heap sort
- size_t i, j, k, i_end;
- struct SN_ELEMENT e_tmp;
- struct SN_ELEMENT* e;
-
- e = m_sn;
-
- k = m_count >> 1;
- i_end = m_count-1;
- for (;;)
- {
- if (k)
- {
- --k;
- e_tmp = e[k];
- }
- else
- {
- e_tmp = e[i_end];
- e[i_end] = e[0];
- if (!(--i_end))
- {
- e[0] = e_tmp;
- break;
- }
- }
-
- i = k;
- j = (k<<1) + 1;
- while (j <= i_end)
- {
- if (j < i_end && e[j].m_sn < e[j + 1].m_sn)
- j++;
- if (e_tmp.m_sn < e[j].m_sn)
- {
- e[i] = e[j];
- i = j;
- j = (j<<1) + 1;
- }
- else
- j = i_end + 1;
- }
- e[i] = e_tmp;
- }
-#endif
+ bu_sort(m_sn, m_count, sizeof(const struct
ON_SerialNumberMap::SN_ELEMENT), snm_cmp, NULL);
m_sn0 = m_sn[0].m_sn;
m_sn1 = m_sn[m_count-1].m_sn;
}
Modified: brlcad/trunk/src/libbrep/openNURBS/opennurbs_mesh.cpp
===================================================================
--- brlcad/trunk/src/libbrep/openNURBS/opennurbs_mesh.cpp 2020-05-06
17:14:34 UTC (rev 75706)
+++ brlcad/trunk/src/libbrep/openNURBS/opennurbs_mesh.cpp 2020-05-06
18:01:22 UTC (rev 75707)
@@ -14,6 +14,10 @@
////////////////////////////////////////////////////////////////
*/
+#include "common.h"
+
+#include "bu/sort.h"
+
#include "opennurbs.h"
@@ -10209,16 +10213,11 @@
return sides_count;
}
-#define ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS
-#define ON_SORT_TEMPLATE_STATIC_FUNCTION
-#define ON_SORT_TEMPLATE_TYPE struct ON_MeshFaceSide
-
-#define ON_SORT_TEMPLATE_COMPARE ON_qsort_MeshFaceSide_compare
-static int ON_SORT_TEMPLATE_COMPARE(
- ON_SORT_TEMPLATE_TYPE const * side1,
- ON_SORT_TEMPLATE_TYPE const * side2
- )
+static int
+mfs_cmp(const void *p1, const void *p2, void *UNUSED(arg))
{
+ const ON_MeshFaceSide *side1 = (const ON_MeshFaceSide *)p1;
+ const ON_MeshFaceSide *side2 = (const ON_MeshFaceSide *)p2;
if ( side1->vi[0] < side2->vi[0] )
return -1;
if ( side1->vi[0] > side2->vi[0] )
@@ -10238,16 +10237,9 @@
return 0;
}
-#define ON_QSORT_FNAME ON_qsort_MeshFaceSide
-#include "opennurbs_qsort_template.h"
-
void ON_SortMeshFaceSidesByVertexIndex( int sides_count, struct
ON_MeshFaceSide* sides )
{
if ( sides_count >= 2 && 0 != sides )
- ON_QSORT_FNAME( sides, sides_count );
+ bu_sort(sides, sides_count, sizeof(ON_MeshFaceSide), mfs_cmp, NULL);
}
-#undef ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS
-#undef ON_SORT_TEMPLATE_STATIC_FUNCTION
-#undef ON_SORT_TEMPLATE_TYPE
-#undef ON_QSORT_FNAME
Deleted: brlcad/trunk/src/libbrep/openNURBS/opennurbs_qsort_template.h
===================================================================
--- brlcad/trunk/src/libbrep/openNURBS/opennurbs_qsort_template.h
2020-05-06 17:14:34 UTC (rev 75706)
+++ brlcad/trunk/src/libbrep/openNURBS/opennurbs_qsort_template.h
2020-05-06 18:01:22 UTC (rev 75707)
@@ -1,312 +0,0 @@
-/* $NoKeywords: $ */
-/*
-//
-// Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
-// OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
-// McNeel & Associates.
-//
-// THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
-// ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
-// MERCHANTABILITY ARE HEREBY DISCLAIMED.
-//
-// For complete openNURBS copyright information see <http://www.opennurbs.org>.
-//
-////////////////////////////////////////////////////////////////
-*/
-// NOTE: 14 April 2011 Dale Lear:
-// Replace this code with Mikko's "quacksort", once "quacksort" is fully
debugged
-// This code is based ont the VC 2010 crt qsort.c file and must not be
released
-// with public opennurbs.
-
-#if !defined(ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS)
-/*
-See opennurbs_sort.cpp for examples of using openurbs_qsort_template.c
-to define type specific quick sort functions.
-*/
-#error Do not compile openurbs_qsort_template.c directly.
-#endif
-
-#define ON_QSORT_CUTOFF 8 /* testing shows that this is good value
*/
-
-/* Note: the theoretical number of stack entries required is
- no more than 1 + log2(num). But we switch to insertion
- sort for CUTOFF elements or less, so we really only need
- 1 + log2(num) - log2(CUTOFF) stack entries. For a CUTOFF
- of 8, that means we need no more than 30 stack entries for
- 32 bit platforms, and 62 for 64-bit platforms. */
-#define ON_QSORT_STKSIZ (8*sizeof(void*) - 2)
-
-
-// ON_SORT_TEMPLATE_TYPE -> double, int, ....
-#if !defined(ON_SORT_TEMPLATE_TYPE)
-#error Define ON_SORT_TEMPLATE_TYPE macro before including
opennurbs_qsort_template.c
-#endif
-
-#if !defined(ON_QSORT_FNAME)
-#error Define ON_QSORT_FNAME macro before including opennurbs_qsort_template.c
-#endif
-
-#if defined(ON_SORT_TEMPLATE_COMPARE)
-// use a compare function like strcmp for char* strings
-#define ON_QSORT_GT(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) > 0
-#define ON_QSORT_LE(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) <= 0
-#define ON_QSORT_EQ(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) == 0
-#else
-// use type compares
-#define ON_QSORT_GT(A,B) *A > *B
-#define ON_QSORT_LE(A,B) *A <= *B
-#define ON_QSORT_EQ(A,B) *A == *B
-#endif
-
-#if defined(ON_SORT_TEMPLATE_USE_MEMCPY)
-#define ON_QSORT_SWAP(A,B)
memcpy(&tmp,A,sizeof(tmp));memcpy(A,B,sizeof(tmp));memcpy(B,&tmp,sizeof(tmp))
-#else
-#define ON_QSORT_SWAP(A,B) tmp = *A; *A = *B; *B = tmp
-#endif
-
-static void ON_shortsort(ON_SORT_TEMPLATE_TYPE *, ON_SORT_TEMPLATE_TYPE *);
-static void ON_shortsort(ON_SORT_TEMPLATE_TYPE *lo, ON_SORT_TEMPLATE_TYPE *hi)
-{
- ON_SORT_TEMPLATE_TYPE *p;
- ON_SORT_TEMPLATE_TYPE *max;
- ON_SORT_TEMPLATE_TYPE tmp;
-
- /* Note: in assertions below, i and j are alway inside original bound of
- array to sort. */
-
- while (hi > lo)
- {
- /* A[i] <= A[j] for i <= j, j > hi */
- max = lo;
- for (p = lo+1; p <= hi; p++)
- {
- /* A[i] <= A[max] for lo <= i < p */
- if ( ON_QSORT_GT(p,max) )
- {
- max = p;
- }
- /* A[i] <= A[max] for lo <= i <= p */
- }
-
- /* A[i] <= A[max] for lo <= i <= hi */
-
- ON_QSORT_SWAP(max,hi);
-
- /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
-
- hi--;
-
- /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
- }
- /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
- so array is sorted */
-}
-
-/* this parameter defines the cutoff between using quick sort and
- insertion sort for arrays; arrays with lengths shorter or equal to the
- below value use insertion sort */
-
-#if defined(ON_SORT_TEMPLATE_STATIC_FUNCTION)
-static
-#endif
-void
-ON_QSORT_FNAME (
- ON_SORT_TEMPLATE_TYPE *base,
- size_t num
- )
-{
- ON_SORT_TEMPLATE_TYPE *lo; /* start of sub-array currently
sorting */
- ON_SORT_TEMPLATE_TYPE *hi; /* end of sub-array currently
sorting */
- ON_SORT_TEMPLATE_TYPE *mid; /* points to middle of subarray
*/
- ON_SORT_TEMPLATE_TYPE *loguy; /* traveling pointers for
partition step */
- ON_SORT_TEMPLATE_TYPE *higuy; /* traveling pointers for
partition step */
- ON_SORT_TEMPLATE_TYPE *lostk[ON_QSORT_STKSIZ];
- ON_SORT_TEMPLATE_TYPE *histk[ON_QSORT_STKSIZ];
- size_t size; /* size of the sub-array */
- int stkptr; /* stack for saving sub-array to be processed */
- ON_SORT_TEMPLATE_TYPE tmp;
-
- if ( 0 == base || num < 2 )
- return;
-
- stkptr = 0; /* initialize stack */
-
- lo = base;
- hi = base + (num-1); /* initialize limits */
-
- /* this entry point is for pseudo-recursion calling: setting
- lo and hi and jumping to here is like recursion, but stkptr is
- preserved, locals aren't, so we preserve stuff on the stack */
-recurse:
-
- size = (hi - lo) + 1; /* number of el's to sort */
-
- /* below a certain size, it is faster to use a O(n^2) sorting method */
- if (size <= ON_QSORT_CUTOFF)
- {
- ON_shortsort(lo, hi);
- }
- else {
- /* First we pick a partitioning element. The efficiency of the
- algorithm demands that we find one that is approximately the median
- of the values, but also that we select one fast. We choose the
- median of the first, middle, and last elements, to avoid bad
- performance in the face of already sorted data, or data that is made
- up of multiple sorted runs appended together. Testing shows that a
- median-of-three algorithm provides better performance than simply
- picking the middle element for the latter case. */
-
- mid = lo + (size / 2); /* find middle element */
-
- /* Sort the first, middle, last elements into order */
- if ( ON_QSORT_GT(lo,mid) ) {ON_QSORT_SWAP(lo,mid);}
- if ( ON_QSORT_GT(lo,hi) ) {ON_QSORT_SWAP(lo,hi);}
- if ( ON_QSORT_GT(mid,hi) ) {ON_QSORT_SWAP(mid,hi);}
-
- /* We now wish to partition the array into three pieces, one consisting
- of elements <= partition element, one of elements equal to the
- partition element, and one of elements > than it. This is done
- below; comments indicate conditions established at every step. */
-
- loguy = lo;
- higuy = hi;
-
- /* Note that higuy decreases and loguy increases on every iteration,
- so loop must terminate. */
- for (;;)
- {
- /* lo <= loguy < hi, lo < higuy <= hi,
- A[i] <= A[mid] for lo <= i <= loguy,
- A[i] > A[mid] for higuy <= i < hi,
- A[hi] >= A[mid] */
-
- /* The doubled loop is to avoid calling comp(mid,mid), since some
- existing comparison funcs don't work when passed the same
- value for both pointers. */
-
- if (mid > loguy)
- {
- do {
- loguy++;
- } while (loguy < mid && ON_QSORT_LE(loguy,mid));
- }
- if (mid <= loguy)
- {
- do {
- loguy++;
- } while (loguy <= hi && ON_QSORT_LE(loguy,mid));
- }
-
- /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
- either loguy > hi or A[loguy] > A[mid] */
-
- do {
- higuy--;
- } while (higuy > mid && ON_QSORT_GT(higuy,mid));
-
- /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,
- either higuy == lo or A[higuy] <= A[mid] */
-
- if (higuy < loguy)
- break;
-
- /* if loguy > hi or higuy == lo, then we would have exited, so
- A[loguy] > A[mid], A[higuy] <= A[mid],
- loguy <= hi, higuy > lo */
-
- ON_QSORT_SWAP(loguy,higuy);
-
- /* If the partition element was moved, follow it. Only need
- to check for mid == higuy, since before the swap,
- A[loguy] > A[mid] implies loguy != mid. */
-
- if (mid == higuy)
- mid = loguy;
-
- /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top
- of loop is re-established */
- }
-
- /* A[i] <= A[mid] for lo <= i < loguy,
- A[i] > A[mid] for higuy < i < hi,
- A[hi] >= A[mid]
- higuy < loguy
- implying:
- higuy == loguy-1
- or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */
-
- /* Find adjacent elements equal to the partition element. The
- doubled loop is to avoid calling comp(mid,mid), since some
- existing comparison funcs don't work when passed the same value
- for both pointers. */
-
- higuy++;
- if (mid < higuy) {
- do {
- higuy--;
- } while (higuy > mid && ON_QSORT_EQ(higuy,mid));
- }
- if (mid >= higuy) {
- do {
- higuy--;
- } while (higuy > lo && ON_QSORT_EQ(higuy,mid));
- }
-
- /* OK, now we have the following:
- higuy < loguy
- lo <= higuy <= hi
- A[i] <= A[mid] for lo <= i <= higuy
- A[i] == A[mid] for higuy < i < loguy
- A[i] > A[mid] for loguy <= i < hi
- A[hi] >= A[mid] */
-
- /* We've finished the partition, now we want to sort the subarrays
- [lo, higuy] and [loguy, hi].
- We do the smaller one first to minimize stack usage.
- We only sort arrays of length 2 or more.*/
-
- if ( higuy - lo >= hi - loguy ) {
- if (lo < higuy) {
- lostk[stkptr] = lo;
- histk[stkptr] = higuy;
- ++stkptr;
- } /* save big recursion for later */
-
- if (loguy < hi) {
- lo = loguy;
- goto recurse; /* do small recursion */
- }
- }
- else {
- if (loguy < hi) {
- lostk[stkptr] = loguy;
- histk[stkptr] = hi;
- ++stkptr; /* save big recursion for later */
- }
-
- if (lo < higuy) {
- hi = higuy;
- goto recurse; /* do small recursion */
- }
- }
- }
-
- /* We have sorted the array, except for any pending sorts on the stack.
- Check if there are any, and do them. */
-
- --stkptr;
- if (stkptr >= 0) {
- lo = lostk[stkptr];
- hi = histk[stkptr];
- goto recurse; /* pop subarray from stack */
- }
- else
- return; /* all subarrays done */
-}
-
-#undef ON_QSORT_GT
-#undef ON_QSORT_LE
-#undef ON_QSORT_EQ
-#undef ON_QSORT_SWAP
-#undef ON_QSORT_CUTOFF
-#undef ON_QSORT_STKSIZ
Modified: brlcad/trunk/src/libbrep/openNURBS/opennurbs_sort.cpp
===================================================================
--- brlcad/trunk/src/libbrep/openNURBS/opennurbs_sort.cpp 2020-05-06
17:14:34 UTC (rev 75706)
+++ brlcad/trunk/src/libbrep/openNURBS/opennurbs_sort.cpp 2020-05-06
18:01:22 UTC (rev 75707)
@@ -14,6 +14,10 @@
////////////////////////////////////////////////////////////////
*/
+#include "common.h"
+
+#include "bu/sort.h"
+
#include "opennurbs.h"
/*
@@ -188,19 +192,25 @@
#undef work_size
-#define ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS
#define ON_COMPILING_OPENNURBS_HSORT_FUNCTIONS
#define ON_SORT_TEMPLATE_STATIC_FUNCTION
#define ON_SORT_TEMPLATE_TYPE double
-#define ON_QSORT_FNAME ON_qsort_double
#define ON_HSORT_FNAME ON_hsort_double
-#include "opennurbs_qsort_template.h"
#include "opennurbs_hsort_template.h"
#undef ON_SORT_TEMPLATE_TYPE
-#undef ON_QSORT_FNAME
#undef ON_HSORT_FNAME
+static int
+dbl_cmp(const void *p1, const void *p2, void *UNUSED(arg))
+{
+ double *a = (double *)p1;
+ double *b = (double *)p2;
+ if (*a > *b) return 1;
+ if (*a < *b) return -1;
+ return 0;
+}
+
void ON_SortDoubleArray(
ON::sort_algorithm sort_algorithm,
double* a,
@@ -210,18 +220,25 @@
if ( ON::heap_sort == sort_algorithm )
ON_hsort_double(a,nel);
else
- ON_qsort_double(a,nel);
+ bu_sort(a,nel, sizeof(double), dbl_cmp, NULL);
}
#define ON_SORT_TEMPLATE_TYPE float
-#define ON_QSORT_FNAME ON_qsort_float
#define ON_HSORT_FNAME ON_hsort_float
-#include "opennurbs_qsort_template.h"
#include "opennurbs_hsort_template.h"
#undef ON_SORT_TEMPLATE_TYPE
-#undef ON_QSORT_FNAME
#undef ON_HSORT_FNAME
+static int
+float_cmp(const void *p1, const void *p2, void *UNUSED(arg))
+{
+ float *a = (float *)p1;
+ float *b = (float *)p2;
+ if (*a > *b) return 1;
+ if (*a < *b) return -1;
+ return 0;
+}
+
void ON_SortFloatArray(
ON::sort_algorithm sort_algorithm,
float* a,
@@ -231,19 +248,26 @@
if ( ON::heap_sort == sort_algorithm )
ON_hsort_float(a,nel);
else
- ON_qsort_float(a,nel);
+ bu_sort(a,nel, sizeof(float), float_cmp, NULL);
}
#define ON_SORT_TEMPLATE_TYPE int
-#define ON_QSORT_FNAME ON_qsort_int
#define ON_HSORT_FNAME ON_hsort_int
-#include "opennurbs_qsort_template.h"
#include "opennurbs_hsort_template.h"
#undef ON_SORT_TEMPLATE_TYPE
-#undef ON_QSORT_FNAME
#undef ON_HSORT_FNAME
+static int
+int_cmp(const void *p1, const void *p2, void *UNUSED(arg))
+{
+ int *a = (int *)p1;
+ int *b = (int *)b;
+ if (*a > *b) return 1;
+ if (*a < *b) return -1;
+ return 0;
+}
+
void ON_SortIntArray(
ON::sort_algorithm sort_algorithm,
int* a,
@@ -253,19 +277,26 @@
if ( ON::heap_sort == sort_algorithm )
ON_hsort_int(a,nel);
else
- ON_qsort_int(a,nel);
+ bu_sort(a,nel, sizeof(int), int_cmp, NULL);
}
#define ON_SORT_TEMPLATE_TYPE unsigned int
-#define ON_QSORT_FNAME ON_qsort_uint
#define ON_HSORT_FNAME ON_hsort_uint
-#include "opennurbs_qsort_template.h"
#include "opennurbs_hsort_template.h"
#undef ON_SORT_TEMPLATE_TYPE
-#undef ON_QSORT_FNAME
#undef ON_HSORT_FNAME
+static int
+uint_cmp(const void *p1, const void *p2, void *UNUSED(arg))
+{
+ unsigned int *a = (unsigned int *)p1;
+ unsigned int *b = (unsigned int *)p2;
+ if (*a > *b) return 1;
+ if (*a < *b) return -1;
+ return 0;
+}
+
void ON_SortUnsignedIntArray(
ON::sort_algorithm sort_algorithm,
unsigned int* a,
@@ -275,6 +306,6 @@
if ( ON::heap_sort == sort_algorithm )
ON_hsort_uint(a,nel);
else
- ON_qsort_uint(a,nel);
+ bu_sort(a,nel, sizeof(unsigned int), uint_cmp, NULL);
}
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
