algorithm revision df7611a3647a8ac956044c86178fb5ad85d89293 
1/* -*- c++ -*- */
2/*
3 * Copyright (C) 2009 The Android Open Source Project
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *  * Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 *  * Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in
13 *    the documentation and/or other materials provided with the
14 *    distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
23 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30#ifndef ANDROID_ASTL_ALGORITHM__
31#define ANDROID_ASTL_ALGORITHM__
32
33#include <cstddef>
34#include <cstring>
35#include <type_traits.h>
36#ifndef ANDROID_ASTL_TYPE_TRAITS_H__
37#error "Wrong file included!"
38#endif
39
40namespace std {
41
42// This file contains the following template functions:
43// - min
44// - max
45// - swap
46// - fill
47// - fill_n
48
49template<typename _T> inline const _T& min(const _T& left, const _T& right)
50{
51    if (left < right) return left;
52    return right;
53}
54
55template<typename _T> inline const _T& max(const _T& left, const _T& right)
56{
57    if (right < left) return left;
58    return right;
59}
60
61template<typename _T> inline void swap(_T& left, _T& right)
62{
63    _T tmp = left;
64    left = right;
65    right = tmp;
66}
67
68// fill the range [begin, end) with copies of value, return nothing.
69// fill_n the range [begin, begin + n) with copies of value, return
70// the pointer at begin + n.
71//
72// TODO: fill and fill_n should take forward and output iterators for
73// begin and end params. Fix this when iterator are defined.
74
75
76template<bool> struct __fill
77{
78    template<typename _T> static void fill(_T *begin, const _T *end,
79                                           const _T& value)
80    {
81        for (; begin < end; ++begin)
82            *begin = value;
83    }
84};
85
86template<> struct __fill<true>  // scalar version
87{
88    template<typename _T> static void fill(_T *begin, const _T *end,
89                                           const _T& value)
90    {
91        const _T tmp = value;
92
93        for (; begin < end; ++begin)
94            *begin = tmp;
95    }
96};
97
98template<typename _T> void fill(_T *begin, _T *end, const _T& value)
99{
100    const bool is_scalar = std::is_scalar<_T>::value;
101    __fill<is_scalar>::fill(begin, end, value);
102}
103
104// Specialization: for one-byte types use memset.
105inline void fill(unsigned char *begin, unsigned char *end,
106                 const unsigned char& value)
107{
108    if (begin < end)
109    {
110        const int tmp = value;
111        std::memset(begin, tmp, end - begin);
112    }
113}
114
115inline void fill(signed char *begin, signed char *end, const signed char& value)
116{
117    if (begin < end)
118    {
119        const int tmp = value;
120        std::memset(begin, tmp, end - begin);
121    }
122}
123
124inline void fill(char *begin, char *end, const char& value)
125{
126    if (begin < end)
127    {
128        const int tmp = value;
129        std::memset(begin, tmp, end - begin);
130    }
131}
132
133template<bool> struct __fill_n
134{
135    template<typename _T> static _T *fill_n(_T *begin, size_t num,
136                                            const _T& value)
137    {
138        for (size_t i = 0; i < num; ++i, ++begin)
139        {
140            *begin = value;
141        }
142        return begin;
143    }
144};
145
146template<> struct __fill_n<true>  // scalar version
147{
148    template<typename _T> static _T *fill_n(_T *begin, size_t num,
149                                            const _T& value)
150    {
151        const _T tmp = value;
152
153        for (size_t i = 0; i < num; ++i, ++begin)
154        {
155            *begin = tmp;
156        }
157        return begin;
158    }
159};
160
161template<typename _T> _T *fill_n(_T *begin, size_t n, const _T& value)
162{
163    const bool is_scalar = std::is_scalar<_T>::value;
164    return __fill_n<is_scalar>::fill_n(begin, n, value);
165}
166
167
168// Specialization: for one-byte types uses memset.
169inline unsigned char *fill_n(unsigned char *begin, size_t num,
170                             const unsigned char& value)
171{
172    const int tmp = value;
173    std::memset(begin, tmp, num);
174    return begin + num;
175}
176
177inline signed char *fill_n(signed char *begin, size_t num,
178                           const signed char& value)
179{
180    const int tmp = value;
181    std::memset(begin, tmp, num);
182    return begin + num;
183}
184
185inline char *fill_n(char *begin, size_t num, const char& value)
186{
187    const int tmp = value;
188    std::memset(begin, tmp, num);
189    return begin + num;
190}
191
192}  // namespace std
193
194
195#endif
196