source: CLRX/CLRadeonExtender/trunk/CLRX/utils/Containers.h @ 3875

Last change on this file since 3875 was 3875, checked in by matszpk, 16 months ago

CLRadeonExtender: AsmRegAlloc?: fixed subroutine cache usage. Fixed pushing ssaIds before visited subroutine. Add hasValue to VectorSet?.

File size: 12.7 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19/*! \file Containers.h
20 * \brief containers and other utils for other libraries and programs
21 */
22
23#ifndef __CLRX_CONTAINERS_H__
24#define __CLRX_CONTAINERS_H__
25
26#include <CLRX/Config.h>
27#include <cstddef>
28#include <iterator>
29#include <algorithm>
30#include <vector>
31#include <initializer_list>
32
33/// main namespace
34namespace CLRX
35{
36
37/// an array class
38template<typename T>
39class Array
40{
41public:
42    typedef T* iterator;    ///< type of iterator
43    typedef const T* const_iterator;    ///< type of constant iterator
44    typedef T element_type; ///< element type
45private:
46    T* ptr, *ptrEnd;
47public:
48    /// empty constructor
49    Array(): ptr(nullptr), ptrEnd(nullptr)
50    { }
51   
52    /// construct array of N elements
53    explicit Array(size_t N)
54    {
55        ptr = nullptr;
56        if (N != 0)
57            ptr = new T[N];
58        ptrEnd = ptr+N;
59    }
60   
61    /// construct array of elements in begin and end
62    template<typename It>
63    Array(It b, It e)
64    {
65        try
66        {
67            ptr = nullptr;
68            const size_t N = e-b;
69            if (N != 0)
70                ptr = new T[N];
71            ptrEnd = ptr+N;
72            std::copy(b, e, ptr);
73        }
74        catch(...)
75        {
76            delete[] ptr;
77            throw;
78        }
79    }
80   
81    /// copy constructor
82    Array(const Array& cp)
83    {
84        try
85        {
86            ptr = ptrEnd = nullptr;
87            const size_t N = cp.size();
88            if (N != 0)
89                ptr = new T[N];
90            ptrEnd = ptr+N;
91            std::copy(cp.ptr, cp.ptrEnd, ptr);
92        }
93        catch(...)
94        {
95            delete[] ptr;
96            throw;
97        }
98    }
99   
100    /// move constructor
101    Array(Array&& cp) noexcept
102    {
103        ptr = cp.ptr;
104        ptrEnd = cp.ptrEnd;
105        cp.ptr = cp.ptrEnd = nullptr;
106    }
107   
108    /// constructor with initializer list
109    Array(std::initializer_list<T> list)
110    {
111        try
112        {
113            ptr = nullptr;
114            const size_t N = list.size();
115            if (N != 0)
116                ptr = new T[N];
117            ptrEnd = ptr+N;
118            std::copy(list.begin(), list.end(), ptr);
119        }
120        catch(...)
121        {
122            delete[] ptr;
123            throw;
124        }
125    }
126   
127    /// destructor
128    ~Array()
129    { delete[] ptr; }
130   
131    /// copy assignment
132    Array& operator=(const Array& cp)
133    {
134        if (this == &cp)
135            return *this;
136        assign(cp.begin(), cp.end());
137        return *this;
138    }
139    /// move assignment
140    Array& operator=(Array&& cp) noexcept
141    {
142        if (this == &cp)
143            return *this;
144        delete[] ptr;
145        ptr = cp.ptr;
146        ptrEnd = cp.ptrEnd;
147        cp.ptr = cp.ptrEnd = nullptr;
148        return *this;
149    }
150   
151    /// assignment from initializer list
152    Array& operator=(std::initializer_list<T> list)
153    {
154        assign(list.begin(), list.end());
155        return *this;
156    }
157   
158    /// operator of indexing
159    const T& operator[] (size_t i) const
160    { return ptr[i]; }
161    /// operator of indexing
162    T& operator[] (size_t i)
163    { return ptr[i]; }
164   
165    /// returns true if empty
166    bool empty() const
167    { return ptrEnd==ptr; }
168   
169    /// returns number of elements
170    size_t size() const
171    { return ptrEnd-ptr; }
172   
173    /// only allocating space without keeping previous content
174    void allocate(size_t N)
175    {
176        if (N == size())
177            return;
178        delete[] ptr;
179        ptr = nullptr;
180        if (N != 0)
181            ptr = new T[N];
182        ptrEnd = ptr + N;
183    }
184   
185    /// resize space with keeping old content
186    void resize(size_t N)
187    {
188        if (N == size())
189            return;
190        T* newPtr = nullptr;
191        if (N != 0)
192            newPtr = new T[N];
193        try
194        {
195            /* move only if move constructor doesn't throw exceptions */
196            const size_t toMove = std::min(N, size());
197            for (size_t k = 0; k < toMove; k++)
198                newPtr[k] = std::move_if_noexcept(ptr[k]);
199        }
200        catch(...)
201        {
202            delete[] newPtr;
203            throw;
204        }
205        delete[] ptr;
206        ptr = newPtr;
207        ptrEnd = ptr + N;
208    }
209   
210    /// clear array
211    void clear()
212    {
213        delete[] ptr;
214        ptr = ptrEnd = nullptr;
215    }
216   
217    /// assign from range of iterators
218    template<typename It>
219    Array& assign(It b, It e)
220    {
221        const size_t N = e-b;
222        if (N != size())
223        {
224            T* newPtr = nullptr;
225            if (N != 0)
226                newPtr = new T[N];
227            try
228            { std::copy(b, e, newPtr); }
229            catch(...)
230            {
231                delete[] newPtr;
232                throw;
233            }
234            delete[] ptr;
235            ptr = newPtr;
236            ptrEnd = ptr+N;
237        }
238        else // no size changed only copy
239            std::copy(b, e, ptr);
240        return *this;
241    }
242   
243    /// get data
244    const T* data() const
245    { return ptr; }
246    /// get data
247    T* data()
248    { return ptr; }
249   
250    /// get iterator to first element
251    const T* begin() const
252    { return ptr; }
253    /// get iterator to first element
254    T* begin()
255    { return ptr; }
256   
257    /// get iterator to after last element
258    const T* end() const
259    { return ptrEnd; }
260    /// get iterator to after last element
261    T* end()
262    { return ptrEnd; }
263   
264    /// get first element
265    const T& front() const
266    { return *ptr; }
267    /// get first element
268    T& front()
269    { return *ptr; }
270    /// get last element
271    const T& back() const
272    { return ptrEnd[-1]; }
273    /// get last element
274    T& back()
275    { return ptrEnd[-1]; }
276   
277    /// swap two arrays
278    void swap(Array& array)
279    {
280        std::swap(ptr, array.ptr);
281        std::swap(ptrEnd, array.ptrEnd);
282    }
283};
284
285/// VectorSet
286template<typename T>
287class VectorSet: public std::vector<T>
288{
289public:
290    /// constructor
291    VectorSet()
292    { }
293   
294    /// constructor
295    VectorSet(size_t n) : std::vector<T>(n)
296    { }
297   
298    /// constructor
299    VectorSet(size_t n, const T& v) : std::vector<T>(n, v)
300    { }
301   
302    /// constructor
303    VectorSet(std::initializer_list<T> l): std::vector<T>(l)
304    { }
305   
306    /// insert new value if doesn't exists
307    void insertValue(const T& v)
308    {
309        auto fit = std::find(std::vector<T>::begin(), std::vector<T>::end(), v);
310        if (fit == std::vector<T>::end())
311            std::vector<T>::push_back(v);
312    }
313   
314    /// erase value if exists
315    void eraseValue(const T& v)
316    {
317        auto fit = std::find(std::vector<T>::begin(), std::vector<T>::end(), v);
318        if (fit != std::vector<T>::end())
319            std::vector<T>::erase(fit);
320    }
321   
322    bool hasValue(const T& v) const
323    {
324        return std::find(std::vector<T>::begin(), std::vector<T>::end(), v) !=
325                std::vector<T>::end();
326    }
327};
328
329
330/// binary find helper
331/**
332 * \param begin iterator to first element
333 * \param end iterator to after last element
334 * \param v value to find
335 * \return iterator to value or end
336 */
337template<typename Iter>
338Iter binaryFind(Iter begin, Iter end, const
339            typename std::iterator_traits<Iter>::value_type& v);
340
341/// binary find helper
342/**
343 * \param begin iterator to first element
344 * \param end iterator to after last element
345 * \param v value to find
346 * \param comp comparator
347 * \return iterator to value or end
348 */
349template<typename Iter, typename Comp =
350        std::less<typename std::iterator_traits<Iter>::value_type> >
351Iter binaryFind(Iter begin, Iter end, const
352        typename std::iterator_traits<Iter>::value_type& v, Comp comp);
353
354/// binary find helper for array-map
355/**
356 * \param begin iterator to first element
357 * \param end iterator to after last element
358 * \param k key to find
359 * \return iterator to value or end
360 */
361template<typename Iter>
362Iter binaryMapFind(Iter begin, Iter end, const 
363        typename std::iterator_traits<Iter>::value_type::first_type& k);
364
365/// binary find helper for array-map
366/**
367 * \param begin iterator to first element
368 * \param end iterator to after last element
369 * \param k key to find
370 * \param comp comparator
371 * \return iterator to value or end
372 */
373template<typename Iter, typename Comp =
374    std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
375Iter binaryMapFind(Iter begin, Iter end, const
376        typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp);
377
378/// map range of iterators
379/**
380 * \param begin iterator to first element
381 * \param end iterator to after last element
382 */
383template<typename Iter>
384void mapSort(Iter begin, Iter end);
385
386/// map range of iterators
387/**
388 * \param begin iterator to first element
389 * \param end iterator to after last element
390 */
391template<typename Iter, typename Comp =
392    std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
393void mapSort(Iter begin, Iter end, Comp comp);
394
395/// binary find
396/**
397 * \param begin iterator to first element
398 * \param end iterator to after last element
399 * \param v value to find
400 * \return iterator to value or end
401 */
402template<typename Iter>
403Iter binaryFind(Iter begin, Iter end,
404        const typename std::iterator_traits<Iter>::value_type& v)
405{
406    auto it = std::lower_bound(begin, end, v);
407    if (it == end || v < *it)
408        return end;
409    return it;
410}
411
412/// binary find
413/**
414 * \param begin iterator to first element
415 * \param end iterator to after last element
416 * \param v value to find
417 * \param comp comparator
418 * \return iterator to value or end
419 */
420template<typename Iter, typename Comp>
421Iter binaryFind(Iter begin, Iter end,
422        const typename std::iterator_traits<Iter>::value_type& v, Comp comp)
423{
424    auto it = std::lower_bound(begin, end, v, comp);
425    if (it == end || comp(v, *it))
426        return end;
427    return it;
428}
429
430/// binary find of map (array)
431template<typename Iter>
432Iter binaryMapFind(Iter begin, Iter end, const
433            typename std::iterator_traits<Iter>::value_type::first_type& k)
434{
435    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
436    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
437    auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
438               [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
439        return e1.first < e2.first; });
440    if (it == end || k < it->first)
441        return end;
442    return it;
443}
444
445/// binary find of map (array)
446template<typename Iter, typename Comp>
447Iter binaryMapFind(Iter begin, Iter end, const
448        typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp)
449{
450    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
451    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
452    auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
453               [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
454        return comp(e1.first, e2.first); });
455    if (it == end || comp(k, it->first))
456        return end;
457    return it;
458}
459
460/// sort map (array)
461/**
462 * \param begin iterator to first element
463 * \param end iterator to after last element
464 */
465template<typename Iter>
466void mapSort(Iter begin, Iter end)
467{
468    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
469    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
470    std::sort(begin, end, [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
471        return e1.first < e2.first; });
472}
473
474/// sort map (array)
475/**
476 * \param begin iterator to first element
477 * \param end iterator to after last element
478 * \param comp comparator
479 */
480template<typename Iter, typename Comp>
481void mapSort(Iter begin, Iter end, Comp comp)
482{
483    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
484    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
485    std::sort(begin, end, [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
486       return comp(e1.first, e2.first); });
487}
488
489};
490
491namespace std
492{
493
494/// std::swap specialization for CLRX::Array
495template<typename T>
496void swap(CLRX::Array<T>& a1, CLRX::Array<T>& a2)
497{ a1.swap(a2); }
498
499}
500
501#endif
Note: See TracBrowser for help on using the repository browser.