1// This file is part of the ustl library, an STL implementation. 2// 3// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> 4// This file is free software, distributed under the MIT License. 5// 6// ualgobase.h 7// 8// Implementation of STL algorithms. 9// 10// The function prototypes are copied 11// exactly from the SGI version of STL documentation along with comments about 12// their use. The code is NOT the same, though the functionality usually is. 13// 14 15#ifndef UALGOBASE_H_683A0BE77546133C4CE0E3622CFAA2EB 16#define UALGOBASE_H_683A0BE77546133C4CE0E3622CFAA2EB 17 18#include "uutility.h" 19#include <string.h> 20 21#if PLATFORM_ANDROID 22#include <stdio.h> 23#undef CPU_HAS_MMX 24#endif 25 26namespace ustl { 27 28/// Assigns the contents of a to b and the contents of b to a. 29/// This is used as a primitive operation by many other algorithms. 30/// \ingroup SwapAlgorithms 31/// 32template <typename Assignable> 33inline void swap (Assignable& a, Assignable& b) 34{ 35 Assignable tmp = a; 36 a = b; 37 b = tmp; 38} 39 40/// Equivalent to swap (*a, *b) 41/// \ingroup SwapAlgorithms 42/// 43template <typename Iterator> 44inline void iter_swap (Iterator a, Iterator b) 45{ 46 swap (*a, *b); 47} 48 49/// Copy copies elements from the range [first, last) to the range 50/// [result, result + (last - first)). That is, it performs the assignments 51/// *result = *first, *(result + 1) = *(first + 1), and so on. [1] Generally, 52/// for every integer n from 0 to last - first, copy performs the assignment 53/// *(result + n) = *(first + n). Assignments are performed in forward order, 54/// i.e. in order of increasing n. 55/// \ingroup MutatingAlgorithms 56/// 57template <typename InputIterator, typename OutputIterator> 58inline OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result) 59{ 60 for (; first != last; ++result, ++first) 61 *result = *first; 62 return (result); 63} 64 65/// Copy_n copies elements from the range [first, first + n) to the range 66/// [result, result + n). That is, it performs the assignments 67/// *result = *first, *(result + 1) = *(first + 1), and so on. Generally, 68/// for every integer i from 0 up to (but not including) n, copy_n performs 69/// the assignment *(result + i) = *(first + i). Assignments are performed 70/// in forward order, i.e. in order of increasing n. 71/// \ingroup MutatingAlgorithms 72/// 73template <typename InputIterator, typename OutputIterator> 74inline OutputIterator copy_n (InputIterator first, size_t count, OutputIterator result) 75{ 76 for (; count; --count, ++result, ++first) 77 *result = *first; 78 return (result); 79} 80 81/// \brief Copy copies elements from the range (last, first] to result. 82/// \ingroup MutatingAlgorithms 83/// Copies elements starting at last, decrementing both last and result. 84/// 85template <typename InputIterator, typename OutputIterator> 86inline OutputIterator copy_backward (InputIterator first, InputIterator last, OutputIterator result) 87{ 88 while (first != last) 89 *--result = *--last; 90 return (result); 91} 92 93/// For_each applies the function object f to each element in the range 94/// [first, last); f's return value, if any, is ignored. Applications are 95/// performed in forward order, i.e. from first to last. For_each returns 96/// the function object after it has been applied to each element. 97/// \ingroup MutatingAlgorithms 98/// 99template <typename InputIterator, typename UnaryFunction> 100inline UnaryFunction for_each (InputIterator first, InputIterator last, UnaryFunction f) 101{ 102 for (; first != last; ++first) 103 f (*first); 104 return (f); 105} 106 107/// Fill assigns the value value to every element in the range [first, last). 108/// That is, for every iterator i in [first, last), 109/// it performs the assignment *i = value. 110/// \ingroup GeneratorAlgorithms 111/// 112template <typename ForwardIterator, typename T> 113inline void fill (ForwardIterator first, ForwardIterator last, const T& value) 114{ 115 for (; first != last; ++first) 116 *first = value; 117} 118 119/// Fill_n assigns the value value to every element in the range 120/// [first, first+count). That is, for every iterator i in [first, first+count), 121/// it performs the assignment *i = value. The return value is first + count. 122/// \ingroup GeneratorAlgorithms 123/// 124template <typename OutputIterator, typename T> 125inline OutputIterator fill_n (OutputIterator first, size_t count, const T& value) 126{ 127 for (; count; --count, ++first) 128 *first = value; 129 return (first); 130} 131 132#if CPU_HAS_MMX 133extern "C" void copy_n_fast (const void* src, size_t count, void* dest); 134#else 135inline void copy_n_fast (const void* src, size_t count, void* dest) 136{ memcpy (dest, src, count); } 137#endif 138#if __i386__ || __x86_64__ 139extern "C" void copy_backward_fast (const void* first, const void* last, void* result); 140#else 141inline void copy_backward_fast (const void* first, const void* last, void* result) 142{ 143 const size_t nBytes (distance (first, last)); 144 memmove (advance (result, -nBytes), first, nBytes); 145} 146#endif 147extern "C" void fill_n8_fast (uint8_t* dest, size_t count, uint8_t v); 148extern "C" void fill_n16_fast (uint16_t* dest, size_t count, uint16_t v); 149extern "C" void fill_n32_fast (uint32_t* dest, size_t count, uint32_t v); 150extern "C" void rotate_fast (void* first, void* middle, void* last); 151 152#if __GNUC__ >= 4 153/// \brief Computes the number of 1 bits in a number. 154/// \ingroup ConditionAlgorithms 155inline size_t popcount (uint32_t v) { return (__builtin_popcount (v)); } 156#if HAVE_INT64_T 157inline size_t popcount (uint64_t v) { return (__builtin_popcountll (v)); } 158#endif 159#else 160size_t popcount (uint32_t v); 161#if HAVE_INT64_T 162size_t popcount (uint64_t v); 163#endif // HAVE_INT64_T 164#endif // __GNUC__ 165 166//---------------------------------------------------------------------- 167// Optimized versions for standard types 168//---------------------------------------------------------------------- 169 170#if WANT_UNROLLED_COPY 171 172template <typename T> 173inline T* unrolled_copy (const T* first, size_t count, T* result) 174{ 175 copy_n_fast (first, count * sizeof(T), result); 176 return (advance (result, count)); 177} 178 179template <> 180inline uint8_t* copy_backward (const uint8_t* first, const uint8_t* last, uint8_t* result) 181{ 182 copy_backward_fast (first, last, result); 183 return (result); 184} 185 186template <typename T> 187inline T* unrolled_fill (T* result, size_t count, T value) 188{ 189 for (; count; --count, ++result) 190 *result = value; 191 return (result); 192} 193template <> inline uint8_t* unrolled_fill (uint8_t* result, size_t count, uint8_t value) 194 { fill_n8_fast (result, count, value); return (advance (result, count)); } 195template <> inline uint16_t* unrolled_fill (uint16_t* result, size_t count, uint16_t value) 196 { fill_n16_fast (result, count, value); return (advance (result, count)); } 197template <> inline uint32_t* unrolled_fill (uint32_t* result, size_t count, uint32_t value) 198 { fill_n32_fast (result, count, value); return (advance (result, count)); } 199template <> inline float* unrolled_fill (float* result, size_t count, float value) 200 { fill_n32_fast ((uint32_t*) result, count, noalias(uint32_t(),&value)); return (advance (result, count)); } 201 202#if CPU_HAS_MMX 203#define UNROLLED_COPY_SPECIALIZATION(type) \ 204template <> inline type* copy (const type* first, const type* last, type* result) \ 205{ return (unrolled_copy (first, distance (first, last), result)); } \ 206template <> inline type* copy_n (const type* first, size_t count, type* result) \ 207{ return (unrolled_copy (first, count, result)); } 208#define UNROLLED_FILL_SPECIALIZATION(type) \ 209template <> inline void fill (type* first, type* last, const type& value) \ 210{ unrolled_fill (first, distance (first, last), value); } \ 211template <> inline type* fill_n (type* first, size_t count, const type& value) \ 212{ return (unrolled_fill (first, count, value)); } 213UNROLLED_COPY_SPECIALIZATION(uint8_t) 214UNROLLED_FILL_SPECIALIZATION(uint8_t) 215UNROLLED_COPY_SPECIALIZATION(uint16_t) 216UNROLLED_FILL_SPECIALIZATION(uint16_t) 217UNROLLED_COPY_SPECIALIZATION(uint32_t) 218UNROLLED_FILL_SPECIALIZATION(uint32_t) 219UNROLLED_COPY_SPECIALIZATION(float) 220UNROLLED_FILL_SPECIALIZATION(float) 221#undef UNROLLED_FILL_SPECIALIZATION 222#undef UNROLLED_COPY_SPECIALIZATION 223#endif // WANT_UNROLLED_COPY 224#endif // CPU_HAS_MMX 225 226// Specializations for void* and char*, aliasing the above optimized versions. 227// 228// All these need duplication with const and non-const arguments, since 229// otherwise the compiler will default to the unoptimized version for 230// pointers not const in the caller's context, such as local variables. 231// These are all inline, but they sure slow down compilation... :( 232// 233#define COPY_ALIAS_FUNC(ctype, type, alias_type) \ 234template <> inline type* copy (ctype* first, ctype* last, type* result) \ 235{ return ((type*) copy ((const alias_type*) first, (const alias_type*) last, (alias_type*) result)); } 236#if WANT_UNROLLED_COPY 237#if HAVE_THREE_CHAR_TYPES 238COPY_ALIAS_FUNC(const char, char, uint8_t) 239COPY_ALIAS_FUNC(char, char, uint8_t) 240#endif 241COPY_ALIAS_FUNC(const int8_t, int8_t, uint8_t) 242COPY_ALIAS_FUNC(int8_t, int8_t, uint8_t) 243COPY_ALIAS_FUNC(uint8_t, uint8_t, uint8_t) 244COPY_ALIAS_FUNC(const int16_t, int16_t, uint16_t) 245COPY_ALIAS_FUNC(int16_t, int16_t, uint16_t) 246COPY_ALIAS_FUNC(uint16_t, uint16_t, uint16_t) 247#if CPU_HAS_MMX || (SIZE_OF_LONG > 4) 248COPY_ALIAS_FUNC(const int32_t, int32_t, uint32_t) 249COPY_ALIAS_FUNC(int32_t, int32_t, uint32_t) 250COPY_ALIAS_FUNC(uint32_t, uint32_t, uint32_t) 251#endif 252#endif 253COPY_ALIAS_FUNC(const void, void, uint8_t) 254COPY_ALIAS_FUNC(void, void, uint8_t) 255#undef COPY_ALIAS_FUNC 256#define COPY_BACKWARD_ALIAS_FUNC(ctype, type, alias_type) \ 257template <> inline type* copy_backward (ctype* first, ctype* last, type* result) \ 258{ return ((type*) copy_backward ((const alias_type*) first, (const alias_type*) last, (alias_type*) result)); } 259#if WANT_UNROLLED_COPY 260#if HAVE_THREE_CHAR_TYPES 261COPY_BACKWARD_ALIAS_FUNC(char, char, uint8_t) 262#endif 263COPY_BACKWARD_ALIAS_FUNC(uint8_t, uint8_t, uint8_t) 264COPY_BACKWARD_ALIAS_FUNC(int8_t, int8_t, uint8_t) 265COPY_BACKWARD_ALIAS_FUNC(uint16_t, uint16_t, uint8_t) 266COPY_BACKWARD_ALIAS_FUNC(const uint16_t, uint16_t, uint8_t) 267COPY_BACKWARD_ALIAS_FUNC(int16_t, int16_t, uint8_t) 268COPY_BACKWARD_ALIAS_FUNC(const int16_t, int16_t, uint8_t) 269#endif 270COPY_BACKWARD_ALIAS_FUNC(void, void, uint8_t) 271COPY_BACKWARD_ALIAS_FUNC(const void, void, uint8_t) 272#undef COPY_BACKWARD_ALIAS_FUNC 273#define FILL_ALIAS_FUNC(type, alias_type, v_type) \ 274template <> inline void fill (type* first, type* last, const v_type& value) \ 275{ fill ((alias_type*) first, (alias_type*) last, (const alias_type&) value); } 276FILL_ALIAS_FUNC(void, uint8_t, char) 277FILL_ALIAS_FUNC(void, uint8_t, uint8_t) 278#if WANT_UNROLLED_COPY 279#if HAVE_THREE_CHAR_TYPES 280FILL_ALIAS_FUNC(char, uint8_t, char) 281FILL_ALIAS_FUNC(char, uint8_t, uint8_t) 282#endif 283FILL_ALIAS_FUNC(int8_t, uint8_t, int8_t) 284FILL_ALIAS_FUNC(int16_t, uint16_t, int16_t) 285#if CPU_HAS_MMX || (SIZE_OF_LONG > 4) 286FILL_ALIAS_FUNC(int32_t, uint32_t, int32_t) 287#endif 288#endif 289#undef FILL_ALIAS_FUNC 290#define COPY_N_ALIAS_FUNC(ctype, type, alias_type) \ 291template <> inline type* copy_n (ctype* first, size_t count, type* result) \ 292{ return ((type*) copy_n ((const alias_type*) first, count, (alias_type*) result)); } 293COPY_N_ALIAS_FUNC(const void, void, uint8_t) 294COPY_N_ALIAS_FUNC(void, void, uint8_t) 295#if WANT_UNROLLED_COPY 296#if HAVE_THREE_CHAR_TYPES 297COPY_N_ALIAS_FUNC(const char, char, uint8_t) 298COPY_N_ALIAS_FUNC(char, char, uint8_t) 299#endif 300COPY_N_ALIAS_FUNC(int8_t, int8_t, uint8_t) 301COPY_N_ALIAS_FUNC(uint8_t, uint8_t, uint8_t) 302COPY_N_ALIAS_FUNC(const int8_t, int8_t, uint8_t) 303COPY_N_ALIAS_FUNC(int16_t, int16_t, uint16_t) 304COPY_N_ALIAS_FUNC(uint16_t, uint16_t, uint16_t) 305COPY_N_ALIAS_FUNC(const int16_t, int16_t, uint16_t) 306#if CPU_HAS_MMX || (SIZE_OF_LONG > 4) 307COPY_N_ALIAS_FUNC(int32_t, int32_t, uint32_t) 308COPY_N_ALIAS_FUNC(uint32_t, uint32_t, uint32_t) 309COPY_N_ALIAS_FUNC(const int32_t, int32_t, uint32_t) 310#endif 311#endif 312#undef COPY_N_ALIAS_FUNC 313#define FILL_N_ALIAS_FUNC(type, alias_type, v_type) \ 314template <> inline type* fill_n (type* first, size_t n, const v_type& value) \ 315{ return ((type*) fill_n ((alias_type*) first, n, (const alias_type&) value)); } 316FILL_N_ALIAS_FUNC(void, uint8_t, char) 317FILL_N_ALIAS_FUNC(void, uint8_t, uint8_t) 318#if WANT_UNROLLED_COPY 319#if HAVE_THREE_CHAR_TYPES 320FILL_N_ALIAS_FUNC(char, uint8_t, char) 321FILL_N_ALIAS_FUNC(char, uint8_t, uint8_t) 322#endif 323FILL_N_ALIAS_FUNC(int8_t, uint8_t, int8_t) 324FILL_N_ALIAS_FUNC(int16_t, uint16_t, int16_t) 325#if CPU_HAS_MMX || (SIZE_OF_LONG > 4) 326FILL_N_ALIAS_FUNC(int32_t, uint32_t, int32_t) 327#endif 328#endif 329#undef FILL_N_ALIAS_FUNC 330 331} // namespace ustl 332 333#endif 334 335