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

Last change on this file since 3997 was 3997, checked in by matszpk, 15 months ago

CLRadeonExtender: AsmRegAlloc?: First testcase for AsmRegAlloc::applySSAReplaces routine. Add new constructor to AsmRegAllocator? (to simplify testing).
Add new constructor to VectoSet?.

File size: 16.5 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 <utility>
32#include <unordered_map>
33#include <initializer_list>
34
35/// main namespace
36namespace CLRX
37{
38
39/// an array class
40template<typename T>
41class Array
42{
43public:
44    typedef T* iterator;    ///< type of iterator
45    typedef const T* const_iterator;    ///< type of constant iterator
46    typedef T element_type; ///< element type
47private:
48    T* ptr, *ptrEnd;
49public:
50    /// empty constructor
51    Array(): ptr(nullptr), ptrEnd(nullptr)
52    { }
53   
54    /// construct array of N elements
55    explicit Array(size_t N)
56    {
57        ptr = nullptr;
58        if (N != 0)
59            ptr = new T[N];
60        ptrEnd = ptr+N;
61    }
62   
63    /// construct array of elements in begin and end
64    template<typename It>
65    Array(It b, It e)
66    {
67        try
68        {
69            ptr = nullptr;
70            const size_t N = e-b;
71            if (N != 0)
72                ptr = new T[N];
73            ptrEnd = ptr+N;
74            std::copy(b, e, ptr);
75        }
76        catch(...)
77        {
78            delete[] ptr;
79            throw;
80        }
81    }
82   
83    /// copy constructor
84    Array(const Array& cp)
85    {
86        try
87        {
88            ptr = ptrEnd = nullptr;
89            const size_t N = cp.size();
90            if (N != 0)
91                ptr = new T[N];
92            ptrEnd = ptr+N;
93            std::copy(cp.ptr, cp.ptrEnd, ptr);
94        }
95        catch(...)
96        {
97            delete[] ptr;
98            throw;
99        }
100    }
101   
102    /// move constructor
103    Array(Array&& cp) noexcept
104    {
105        ptr = cp.ptr;
106        ptrEnd = cp.ptrEnd;
107        cp.ptr = cp.ptrEnd = nullptr;
108    }
109   
110    /// constructor with initializer list
111    Array(std::initializer_list<T> list)
112    {
113        try
114        {
115            ptr = nullptr;
116            const size_t N = list.size();
117            if (N != 0)
118                ptr = new T[N];
119            ptrEnd = ptr+N;
120            std::copy(list.begin(), list.end(), ptr);
121        }
122        catch(...)
123        {
124            delete[] ptr;
125            throw;
126        }
127    }
128   
129    /// destructor
130    ~Array()
131    { delete[] ptr; }
132   
133    /// copy assignment
134    Array& operator=(const Array& cp)
135    {
136        if (this == &cp)
137            return *this;
138        assign(cp.begin(), cp.end());
139        return *this;
140    }
141    /// move assignment
142    Array& operator=(Array&& cp) noexcept
143    {
144        if (this == &cp)
145            return *this;
146        delete[] ptr;
147        ptr = cp.ptr;
148        ptrEnd = cp.ptrEnd;
149        cp.ptr = cp.ptrEnd = nullptr;
150        return *this;
151    }
152   
153    /// assignment from initializer list
154    Array& operator=(std::initializer_list<T> list)
155    {
156        assign(list.begin(), list.end());
157        return *this;
158    }
159   
160    /// operator of indexing
161    const T& operator[] (size_t i) const
162    { return ptr[i]; }
163    /// operator of indexing
164    T& operator[] (size_t i)
165    { return ptr[i]; }
166   
167    /// returns true if empty
168    bool empty() const
169    { return ptrEnd==ptr; }
170   
171    /// returns number of elements
172    size_t size() const
173    { return ptrEnd-ptr; }
174   
175    /// only allocating space without keeping previous content
176    void allocate(size_t N)
177    {
178        if (N == size())
179            return;
180        delete[] ptr;
181        ptr = nullptr;
182        if (N != 0)
183            ptr = new T[N];
184        ptrEnd = ptr + N;
185    }
186   
187    /// resize space with keeping old content
188    void resize(size_t N)
189    {
190        if (N == size())
191            return;
192        T* newPtr = nullptr;
193        if (N != 0)
194            newPtr = new T[N];
195        try
196        {
197            /* move only if move constructor doesn't throw exceptions */
198            const size_t toMove = std::min(N, size());
199            for (size_t k = 0; k < toMove; k++)
200                newPtr[k] = std::move_if_noexcept(ptr[k]);
201        }
202        catch(...)
203        {
204            delete[] newPtr;
205            throw;
206        }
207        delete[] ptr;
208        ptr = newPtr;
209        ptrEnd = ptr + N;
210    }
211   
212    /// clear array
213    void clear()
214    {
215        delete[] ptr;
216        ptr = ptrEnd = nullptr;
217    }
218   
219    /// assign from range of iterators
220    template<typename It>
221    Array& assign(It b, It e)
222    {
223        const size_t N = e-b;
224        if (N != size())
225        {
226            T* newPtr = nullptr;
227            if (N != 0)
228                newPtr = new T[N];
229            try
230            { std::copy(b, e, newPtr); }
231            catch(...)
232            {
233                delete[] newPtr;
234                throw;
235            }
236            delete[] ptr;
237            ptr = newPtr;
238            ptrEnd = ptr+N;
239        }
240        else // no size changed only copy
241            std::copy(b, e, ptr);
242        return *this;
243    }
244   
245    /// get data
246    const T* data() const
247    { return ptr; }
248    /// get data
249    T* data()
250    { return ptr; }
251   
252    /// get iterator to first element
253    const T* begin() const
254    { return ptr; }
255    /// get iterator to first element
256    T* begin()
257    { return ptr; }
258   
259    /// get iterator to after last element
260    const T* end() const
261    { return ptrEnd; }
262    /// get iterator to after last element
263    T* end()
264    { return ptrEnd; }
265   
266    /// get first element
267    const T& front() const
268    { return *ptr; }
269    /// get first element
270    T& front()
271    { return *ptr; }
272    /// get last element
273    const T& back() const
274    { return ptrEnd[-1]; }
275    /// get last element
276    T& back()
277    { return ptrEnd[-1]; }
278   
279    /// swap two arrays
280    void swap(Array& array)
281    {
282        std::swap(ptr, array.ptr);
283        std::swap(ptrEnd, array.ptrEnd);
284    }
285};
286
287/// VectorSet
288template<typename T>
289class VectorSet: public std::vector<T>
290{
291public:
292    /// constructor
293    VectorSet()
294    { }
295   
296    /// constructor
297    VectorSet(size_t n) : std::vector<T>(n)
298    { }
299   
300    /// constructor
301    VectorSet(size_t n, const T& v) : std::vector<T>(n, v)
302    { }
303   
304    /// constructor
305    template<typename It>
306    VectorSet(It first, It last) : std::vector<T>(first, last)
307    { }
308   
309    /// constructor
310    VectorSet(std::initializer_list<T> l): std::vector<T>(l)
311    { }
312   
313    /// insert new value if doesn't exists
314    void insertValue(const T& v)
315    {
316        auto fit = std::find(std::vector<T>::begin(), std::vector<T>::end(), v);
317        if (fit == std::vector<T>::end())
318            std::vector<T>::push_back(v);
319    }
320   
321    /// erase value if exists
322    void eraseValue(const T& v)
323    {
324        auto fit = std::find(std::vector<T>::begin(), std::vector<T>::end(), v);
325        if (fit != std::vector<T>::end())
326            std::vector<T>::erase(fit);
327    }
328   
329    /// return true if value present in vector set
330    bool hasValue(const T& v) const
331    {
332        return std::find(std::vector<T>::begin(), std::vector<T>::end(), v) !=
333                std::vector<T>::end();
334    }
335};
336
337
338/// binary find helper
339/**
340 * \param begin iterator to first element
341 * \param end iterator to after last element
342 * \param v value to find
343 * \return iterator to value or end
344 */
345template<typename Iter>
346Iter binaryFind(Iter begin, Iter end, const
347            typename std::iterator_traits<Iter>::value_type& v);
348
349/// binary find helper
350/**
351 * \param begin iterator to first element
352 * \param end iterator to after last element
353 * \param v value to find
354 * \param comp comparator
355 * \return iterator to value or end
356 */
357template<typename Iter, typename Comp =
358        std::less<typename std::iterator_traits<Iter>::value_type> >
359Iter binaryFind(Iter begin, Iter end, const
360        typename std::iterator_traits<Iter>::value_type& v, Comp comp);
361
362/// binary find helper for array-map
363/**
364 * \param begin iterator to first element
365 * \param end iterator to after last element
366 * \param k key to find
367 * \return iterator to value or end
368 */
369template<typename Iter>
370Iter binaryMapFind(Iter begin, Iter end, const 
371        typename std::iterator_traits<Iter>::value_type::first_type& k);
372
373/// binary find helper for array-map
374/**
375 * \param begin iterator to first element
376 * \param end iterator to after last element
377 * \param k key to find
378 * \param comp comparator
379 * \return iterator to value or end
380 */
381template<typename Iter, typename Comp =
382    std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
383Iter binaryMapFind(Iter begin, Iter end, const
384        typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp);
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>
392void mapSort(Iter begin, Iter end);
393
394/// map range of iterators
395/**
396 * \param begin iterator to first element
397 * \param end iterator to after last element
398 */
399template<typename Iter, typename Comp =
400    std::less<typename std::iterator_traits<Iter>::value_type::first_type> >
401void mapSort(Iter begin, Iter end, Comp comp);
402
403/// binary find
404/**
405 * \param begin iterator to first element
406 * \param end iterator to after last element
407 * \param v value to find
408 * \return iterator to value or end
409 */
410template<typename Iter>
411Iter binaryFind(Iter begin, Iter end,
412        const typename std::iterator_traits<Iter>::value_type& v)
413{
414    auto it = std::lower_bound(begin, end, v);
415    if (it == end || v < *it)
416        return end;
417    return it;
418}
419
420/// binary find
421/**
422 * \param begin iterator to first element
423 * \param end iterator to after last element
424 * \param v value to find
425 * \param comp comparator
426 * \return iterator to value or end
427 */
428template<typename Iter, typename Comp>
429Iter binaryFind(Iter begin, Iter end,
430        const typename std::iterator_traits<Iter>::value_type& v, Comp comp)
431{
432    auto it = std::lower_bound(begin, end, v, comp);
433    if (it == end || comp(v, *it))
434        return end;
435    return it;
436}
437
438/// binary find of map (array)
439template<typename Iter>
440Iter binaryMapFind(Iter begin, Iter end, const
441            typename std::iterator_traits<Iter>::value_type::first_type& k)
442{
443    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
444    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
445    auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
446               [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
447        return e1.first < e2.first; });
448    if (it == end || k < it->first)
449        return end;
450    return it;
451}
452
453/// binary find of map (array)
454template<typename Iter, typename Comp>
455Iter binaryMapFind(Iter begin, Iter end, const
456        typename std::iterator_traits<Iter>::value_type::first_type& k, Comp comp)
457{
458    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
459    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
460    auto it = std::lower_bound(begin, end, std::make_pair(k, V()),
461               [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
462        return comp(e1.first, e2.first); });
463    if (it == end || comp(k, it->first))
464        return end;
465    return it;
466}
467
468/// sort map (array)
469/**
470 * \param begin iterator to first element
471 * \param end iterator to after last element
472 */
473template<typename Iter>
474void mapSort(Iter begin, Iter end)
475{
476    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
477    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
478    std::sort(begin, end, [](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
479        return e1.first < e2.first; });
480}
481
482/// sort map (array)
483/**
484 * \param begin iterator to first element
485 * \param end iterator to after last element
486 * \param comp comparator
487 */
488template<typename Iter, typename Comp>
489void mapSort(Iter begin, Iter end, Comp comp)
490{
491    typedef typename std::iterator_traits<Iter>::value_type::first_type K;
492    typedef typename std::iterator_traits<Iter>::value_type::second_type V;
493    std::sort(begin, end, [&comp](const std::pair<K,V>& e1, const std::pair<K,V>& e2) {
494       return comp(e1.first, e2.first); });
495}
496
497};
498
499namespace std
500{
501
502/// std::swap specialization for CLRX::Array
503template<typename T>
504void swap(CLRX::Array<T>& a1, CLRX::Array<T>& a2)
505{ a1.swap(a2); }
506
507}
508
509/** Simple cache **/
510
511/// Simple cache for object. object class should have a weight method
512template<typename K, typename V>
513class CLRX_INTERNAL SimpleCache
514{
515private:
516    struct Entry
517    {
518        size_t sortedPos;
519        size_t usage;
520        V value;
521    };
522   
523    size_t totalWeight;
524    size_t maxWeight;
525   
526    typedef typename std::unordered_map<K, Entry>::iterator EntryMapIt;
527    // sorted entries - sorted by usage
528    std::vector<EntryMapIt> sortedEntries;
529    std::unordered_map<K, Entry> entryMap;
530   
531    void updateInSortedEntries(EntryMapIt it)
532    {
533        const size_t curPos = it->second.sortedPos;
534        if (curPos == 0)
535            return; // first position
536        if (sortedEntries[curPos-1]->second.usage < it->second.usage &&
537            (curPos==1 || sortedEntries[curPos-2]->second.usage >= it->second.usage))
538        {
539            //std::cout << "fast path" << std::endl;
540            std::swap(sortedEntries[curPos-1]->second.sortedPos, it->second.sortedPos);
541            std::swap(sortedEntries[curPos-1], sortedEntries[curPos]);
542            return;
543        }
544        //std::cout << "slow path" << std::endl;
545        auto fit = std::upper_bound(sortedEntries.begin(),
546            sortedEntries.begin()+it->second.sortedPos, it,
547            [](EntryMapIt it1, EntryMapIt it2)
548            { return it1->second.usage > it2->second.usage; });
549        if (fit != sortedEntries.begin()+it->second.sortedPos)
550        {
551            const size_t curPos = it->second.sortedPos;
552            std::swap((*fit)->second.sortedPos, it->second.sortedPos);
553            std::swap(*fit, sortedEntries[curPos]);
554        }
555    }
556   
557    void insertToSortedEntries(EntryMapIt it)
558    {
559        it->second.sortedPos = sortedEntries.size();
560        sortedEntries.push_back(it);
561    }
562   
563    void removeFromSortedEntries(size_t pos)
564    {
565        // update later element positioning
566        for (size_t i = pos+1; i < sortedEntries.size(); i++)
567            (sortedEntries[i]->second.sortedPos)--;
568        sortedEntries.erase(sortedEntries.begin() + pos);
569    }
570   
571public:
572    /// constructor
573    explicit SimpleCache(size_t _maxWeight) : totalWeight(0), maxWeight(_maxWeight)
574    { }
575   
576    /// use key - get value
577    V* use(const K& key)
578    {
579        auto it = entryMap.find(key);
580        if (it != entryMap.end())
581        {
582            it->second.usage++;
583            updateInSortedEntries(it);
584            return &(it->second.value);
585        }
586        return nullptr;
587    }
588   
589    /// return true if key exists
590    bool hasKey(const K& key)
591    { return entryMap.find(key) != entryMap.end(); }
592   
593    /// put value
594    void put(const K& key, const V& value)
595    {
596        auto res = entryMap.insert({ key, Entry{ 0, 0, value } });
597        if (!res.second)
598        {
599            removeFromSortedEntries(res.first->second.sortedPos); // remove old value
600            // update value
601            totalWeight -= res.first->second.value.weight();
602            res.first->second = Entry{ 0, 0, value };
603        }
604        const size_t elemWeight = value.weight();
605       
606        // correct max weight if element have greater weight
607        if (elemWeight > maxWeight)
608            maxWeight = elemWeight<<1;
609       
610        while (totalWeight+elemWeight > maxWeight)
611        {
612            // remove min usage element
613            auto minUsageIt = sortedEntries.back();
614            sortedEntries.pop_back();
615            totalWeight -= minUsageIt->second.value.weight();
616            entryMap.erase(minUsageIt);
617        }
618       
619        insertToSortedEntries(res.first); // new entry in sorted entries
620       
621        totalWeight += elemWeight;
622    }
623};
624
625#endif
Note: See TracBrowser for help on using the repository browser.