EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:45
0001 //---------------------------------------------------------------------------- 0002 /// @file algorithm.hpp 0003 /// @brief low level functions of create, destroy, move and merge functions 0004 /// 0005 /// @author Copyright (c) 2017 Francisco Jose Tapia (fjtapia@gmail.com )\n 0006 /// Distributed under the Boost Software License, Version 1.0.\n 0007 /// ( See accompanying file LICENSE_1_0.txt or copy at 0008 /// http://www.boost.org/LICENSE_1_0.txt ) 0009 /// @version 0.1 0010 /// 0011 /// @remarks 0012 //----------------------------------------------------------------------------- 0013 #ifndef __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP 0014 #define __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP 0015 0016 #include <ciso646> 0017 #include <algorithm> 0018 #include <functional> 0019 #include <iterator> 0020 #include <memory> 0021 #include <type_traits> 0022 #include <vector> 0023 #include <boost/sort/common/util/traits.hpp> 0024 0025 namespace boost 0026 { 0027 namespace sort 0028 { 0029 namespace common 0030 { 0031 namespace util 0032 { 0033 // 0034 //########################################################################### 0035 // 0036 // I M P O R T A N T 0037 // 0038 // The functions of this file are for internal use only 0039 // All the operations are done with move operations, because the copy 0040 // operations are unnecesary 0041 // 0042 //########################################################################### 0043 // 0044 //---------------------------------------------------------------------------- 0045 // 0046 // F U N C T I O N S I N T H E F I L E 0047 // 0048 //---------------------------------------------------------------------------- 0049 // 0050 // static inline uint32_t nbits32 (uint32_t num) noexcept 0051 // 0052 // static inline uint32_t nbits64 (uint64_t num) 0053 // 0054 // template < class Value_t, class... Args > 0055 // inline void construct_object (Value_t *ptr, Args &&... args) 0056 // 0057 // template < class Value_t > 0058 // inline void destroy_object (Value_t *ptr) 0059 // 0060 // template < class Iter_t, class Value_t = value_iter<Iter_t> > 0061 // void initialize (Iter_t first, Iter_t last, Value_t && val) 0062 // 0063 // template < class Iter1_t, class Iter2_t > 0064 // Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last) 0065 // 0066 // template < class Iter1_t, class Iter2_t > 0067 // Iter2_t move_backward (Iter2_t it_dest, Iter1_t first, Iter1_t last) 0068 // 0069 // template < class Iter_t, class Value_t = value_iter< Iter_t > > 0070 // Value_t * move_construct (Value_t *ptr, Iter_t first, Iter_t last) 0071 // 0072 // template < class Iter_t > 0073 // void destroy (Iter_t first, const Iter_t last) 0074 // 0075 // template < class Iter_t > 0076 // void reverse (Iter_t first, const Iter_t last) 0077 // 0078 //---------------------------------------------------------------------------- 0079 // 0080 //-------------------------------------------------------------------------- 0081 // 0082 // G L O B A L V A R I B L E S 0083 // 0084 //-------------------------------------------------------------------------- 0085 // 0086 // this array represent the number of bits needed for to represent the 0087 // first 256 numbers 0088 static constexpr const uint32_t tmsb[256] = 0089 { 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0090 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0091 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 0092 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0093 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0094 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 0095 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0096 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0097 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0098 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0099 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0100 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 }; 0101 // 0102 //--------------------------------------------------------------------------- 0103 // 0104 // F U N C T I O N S 0105 // 0106 //--------------------------------------------------------------------------- 0107 // 0108 //--------------------------------------------------------------------------- 0109 // function : nbits32 0110 /// @brief Obtain the number of bits of a number equal or greater than num 0111 /// @param num : Number to examine 0112 /// @return Number of bits 0113 //--------------------------------------------------------------------------- 0114 static inline uint32_t nbits32 (uint32_t num) noexcept 0115 { 0116 int Pos = (num & 0xffff0000U) ? 16 : 0; 0117 if ((num >> Pos) & 0xff00U) Pos += 8; 0118 return (tmsb[num >> Pos] + Pos); 0119 } 0120 // 0121 //--------------------------------------------------------------------------- 0122 // function : nbits64 0123 /// @brief Obtain the number of bits of a number equal or greater than num 0124 /// @param num : Number to examine 0125 /// @exception none 0126 /// @return Number of bits 0127 //--------------------------------------------------------------------------- 0128 static inline uint32_t nbits64(uint64_t num)noexcept 0129 { 0130 uint32_t Pos = (num & 0xffffffff00000000ULL) ? 32 : 0; 0131 if ((num >> Pos) & 0xffff0000ULL) Pos += 16; 0132 if ((num >> Pos) & 0xff00ULL) Pos += 8; 0133 return (tmsb[num >> Pos] + Pos); 0134 } 0135 // 0136 //----------------------------------------------------------------------------- 0137 // function : construct_object 0138 /// @brief create an object in the memory specified by ptr 0139 /// 0140 /// @param ptr : pointer to the memory where to create the object 0141 /// @param args : arguments to the constructor 0142 //----------------------------------------------------------------------------- 0143 template <class Value_t, class ... Args> 0144 inline void construct_object (Value_t *ptr, Args &&... args) 0145 { 0146 (::new (static_cast<void *>(ptr)) Value_t(std::forward< Args > (args)...)); 0147 }; 0148 // 0149 //----------------------------------------------------------------------------- 0150 // function : destroy_object 0151 /// @brief destroy an object in the memory specified by ptr 0152 /// @param ptr : pointer to the object to destroy 0153 //----------------------------------------------------------------------------- 0154 template<class Value_t> 0155 inline void destroy_object(Value_t *ptr) 0156 { 0157 ptr->~Value_t(); 0158 }; 0159 // 0160 //----------------------------------------------------------------------------- 0161 // function : initialize 0162 /// @brief initialize a range of objects with the object val moving across them 0163 /// 0164 /// @param first : itertor to the first element to initialize 0165 /// @param last : iterator to the last element to initialize 0166 /// @param val : object used for the initialization 0167 //----------------------------------------------------------------------------- 0168 template <class Iter_t, class Value_t = value_iter<Iter_t> > 0169 inline void initialize (Iter_t first, Iter_t last, Value_t & val) 0170 { 0171 //------------------------------------------------------------------------ 0172 // Metaprogramming 0173 //------------------------------------------------------------------------ 0174 typedef value_iter<Iter_t> value_t; 0175 static_assert (std::is_same< Value_t, value_t >::value, 0176 "Incompatible iterators\n"); 0177 0178 //------------------------------------------------------------------------ 0179 // Code 0180 //------------------------------------------------------------------------ 0181 if (first == last) return; 0182 construct_object(&(*first), std::move(val)); 0183 0184 Iter_t it1 = first, it2 = first + 1; 0185 while (it2 != last) 0186 { 0187 construct_object(&(*(it2++)), std::move(*(it1++))); 0188 }; 0189 val = std::move(*(last - 1)); 0190 }; 0191 // 0192 //----------------------------------------------------------------------------- 0193 // function : move_forward 0194 /// @brief Move initialized objets 0195 /// @param it_dest : iterator to the final place of the objects 0196 /// @param first : iterator to the first element to move 0197 /// @param last : iterator to the last element to move 0198 /// @return Output iterator to the element past the last element 0199 /// moved (it_dest + (last - first)) 0200 //----------------------------------------------------------------------------- 0201 template <class Iter1_t, class Iter2_t> 0202 inline Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last) 0203 { 0204 //------------------------------------------------------------------------ 0205 // Metaprogramming 0206 //------------------------------------------------------------------------ 0207 typedef value_iter<Iter1_t> value1_t; 0208 typedef value_iter<Iter2_t> value2_t; 0209 static_assert (std::is_same< value1_t, value2_t >::value, 0210 "Incompatible iterators\n"); 0211 0212 //------------------------------------------------------------------------ 0213 // Code 0214 //------------------------------------------------------------------------ 0215 while (first != last) 0216 { *it_dest++ = std::move(*first++); 0217 } 0218 return it_dest; 0219 0220 }; 0221 // 0222 //----------------------------------------------------------------------------- 0223 // function : move_backard 0224 /// @brief Move initialized objets in reverse order 0225 /// @param it_dest : last iterator to the final place of the objects 0226 /// @param first : iterator to the first element to move 0227 /// @param last : iterator to the last element to move 0228 //----------------------------------------------------------------------------- 0229 template<class Iter1_t, class Iter2_t> 0230 inline Iter2_t move_backward(Iter2_t it_dest, Iter1_t first, Iter1_t last) 0231 { 0232 //------------------------------------------------------------------------ 0233 // Metaprogramming 0234 //------------------------------------------------------------------------ 0235 typedef value_iter<Iter1_t> value1_t; 0236 typedef value_iter<Iter2_t> value2_t; 0237 static_assert (std::is_same< value1_t, value2_t >::value, 0238 "Incompatible iterators\n"); 0239 0240 //------------------------------------------------------------------------ 0241 // Code 0242 //------------------------------------------------------------------------ 0243 while (first != last) 0244 { *(--it_dest) = std::move (*(--last)); 0245 } 0246 return it_dest; 0247 }; 0248 0249 // 0250 //----------------------------------------------------------------------------- 0251 // function : move_construct 0252 /// @brief Move objets to uninitialized memory 0253 /// 0254 /// @param ptr : pointer to the memory where to create the objects 0255 /// @param first : iterator to the first element to move 0256 /// @param last : iterator to the last element to move 0257 //----------------------------------------------------------------------------- 0258 template<class Iter_t, class Value_t = value_iter<Iter_t> > 0259 inline Value_t * move_construct(Value_t *ptr, Iter_t first, Iter_t last) 0260 { 0261 //------------------------------------------------------------------------ 0262 // Metaprogramming 0263 //------------------------------------------------------------------------ 0264 typedef typename iterator_traits<Iter_t>::value_type value2_t; 0265 static_assert (std::is_same< Value_t, value2_t >::value, 0266 "Incompatible iterators\n"); 0267 0268 //------------------------------------------------------------------------ 0269 // Code 0270 //------------------------------------------------------------------------ 0271 while (first != last) 0272 { 0273 ::new (static_cast<void *>(ptr++)) Value_t(std::move(*(first++))); 0274 }; 0275 return ptr; 0276 }; 0277 // 0278 //----------------------------------------------------------------------------- 0279 // function : destroy 0280 /// @brief destroy the elements between first and last 0281 /// @param first : iterator to the first element to destroy 0282 /// @param last : iterator to the last element to destroy 0283 //----------------------------------------------------------------------------- 0284 template<class Iter_t> 0285 inline void destroy(Iter_t first, const Iter_t last) 0286 { 0287 while (first != last) 0288 destroy_object(&(*(first++))); 0289 }; 0290 // 0291 //----------------------------------------------------------------------------- 0292 // function : reverse 0293 /// @brief destroy the elements between first and last 0294 /// @param first : iterator to the first element to destroy 0295 /// @param last : iterator to the last element to destroy 0296 //----------------------------------------------------------------------------- 0297 template<class Iter_t> 0298 inline void reverse(Iter_t first, Iter_t last) 0299 { 0300 std::reverse ( first, last); 0301 }; 0302 // 0303 //**************************************************************************** 0304 };// End namespace util 0305 };// End namespace common 0306 };// End namespace sort 0307 };// End namespace boost 0308 //**************************************************************************** 0309 // 0310 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|