source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.h @ 5620

Last change on this file since 5620 was 5620, checked in by nmedfort, 19 months ago

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

File size: 6.6 KB
Line 
1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
3#include <stdint.h>
4#include <vector>
5#include <boost/iterator/iterator_facade.hpp>
6#include <util/slab_allocator.h>
7
8//
9// unicode_set.h - representing and manipulating sets of Unicode
10// characters, based on data from UCD - the Unicode Character Database
11//
12// Robert D. Cameron
13// September 18, 2014
14//
15// Licensed under Open Software License 3.0.
16//
17// Unicode Sparse Bitset Representation
18//
19// The Unicode Sparse Bitset representation is based on
20// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
21// (b) Specifying the quads using a run-length encoding, in which each run
22//     is Empty (quads contain no members), Mixed (quads contain some members and
23//     some nonmembers) or Full (all codepoints in each quad are members of the set).
24// (c) Explicitly listing all the quads of Mixed type.
25//
26
27//
28// The internal datatype for quads - bitsets of 2^k codepoints.
29// Default: 64 codepoints (k=6).
30//
31
32namespace llvm {
33class raw_ostream;
34}
35
36namespace UCD {
37
38typedef unsigned codepoint_t;
39enum : codepoint_t { UNICODE_MAX = 0x10FFFF };
40
41enum run_type_t : uint16_t {Empty, Mixed, Full};
42
43class UnicodeSet {
44public:
45
46    using bitquad_t = uint32_t;
47    using length_t = uint16_t;
48    using run_t = std::pair<run_type_t, length_t>;
49    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
50
51    using interval_t = std::pair<codepoint_t, codepoint_t>;
52
53    using RunVector = std::vector<run_t, ProxyAllocator<run_t>>;
54    using QuadVector = std::vector<bitquad_t, ProxyAllocator<bitquad_t>>;
55    using RunIterator = RunVector::const_iterator;
56    using QuadIterator = QuadVector::const_iterator;
57
58    using size_type = RunVector::size_type;
59
60    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
61        friend class UnicodeSet;
62        friend class boost::iterator_core_access;
63    protected:
64
65        iterator(const RunVector::const_iterator runIterator, const QuadVector::const_iterator quadIterator, const codepoint_t baseCodePoint)
66        : mRunIterator(runIterator), mQuadIterator(quadIterator)
67        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(baseCodePoint), mMinCodePoint(baseCodePoint), mMaxCodePoint(baseCodePoint) {
68
69        }
70
71        void advance(const unsigned n);
72
73        inline interval_t dereference() const {
74            return std::make_pair(mMinCodePoint, mMaxCodePoint);
75        }
76
77        inline void increment() {
78            advance(1);
79        }
80
81        inline bool equal(const iterator & other) const {
82            return (mMinCodePoint == other.mMinCodePoint);
83        }
84    private:
85        RunIterator         mRunIterator;
86        QuadIterator        mQuadIterator;
87        unsigned            mMixedRunIndex;
88        bitquad_t           mQuadOffset;
89        codepoint_t         mBaseCodePoint;
90        codepoint_t         mMinCodePoint;
91        codepoint_t         mMaxCodePoint;
92    };
93
94    inline iterator begin() const {
95        // note: preincrement forces the iterator to advance onto and capture the first interval.
96        return ++iterator(mRuns.cbegin(), mQuads.cbegin(), 0);
97    }
98
99    inline iterator end() const {
100        return iterator(mRuns.cend(), mQuads.cend(), 0x110000);
101    }
102
103    bool empty() const;
104
105    bool contains(const codepoint_t codepoint) const;
106
107    bool intersects(const codepoint_t lo, const codepoint_t hi) const;
108
109    void insert(const codepoint_t cp);
110
111    void insert_range(const codepoint_t lo, const codepoint_t hi);
112
113    size_type size() const;
114
115    interval_t front() const;
116
117    interval_t back() const;
118
119    void print(llvm::raw_ostream & out) const;
120
121    void dump(llvm::raw_ostream & out) const;
122
123    UnicodeSet operator~() const;
124    UnicodeSet operator&(const UnicodeSet & other) const;
125    UnicodeSet operator+(const UnicodeSet & other) const;
126    UnicodeSet operator-(const UnicodeSet & other) const;
127    UnicodeSet operator^(const UnicodeSet & other) const;
128
129    inline UnicodeSet & operator=(const UnicodeSet & other) = default;
130    inline UnicodeSet & operator=(UnicodeSet && other) = default;
131    bool operator==(const UnicodeSet & other) const;
132    bool operator<(const UnicodeSet & other) const;
133
134    UnicodeSet();
135    UnicodeSet(const codepoint_t codepoint);
136    UnicodeSet(const codepoint_t lo, const codepoint_t hi);
137    UnicodeSet(const UnicodeSet & other);
138    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q);
139    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end);
140    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end);
141
142    inline void swap(UnicodeSet & other);
143    inline void swap(UnicodeSet && other);
144
145protected:
146
147    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q);
148
149    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
150        friend class UnicodeSet;
151        friend class boost::iterator_core_access;
152    public:
153        quad_iterator(RunIterator runIterator, QuadIterator quadIterator)
154            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
155
156        void advance(unsigned n);
157
158        inline quad_iterator_return_t dereference() const {
159            return std::make_pair(std::make_pair(type(), length()), quad());
160        }
161
162        inline void increment() {
163            advance(1);
164        }
165
166        inline run_type_t type() const {
167            return mRunIterator->first;
168        }
169
170        inline length_t length() const {
171            return mRunIterator->second - mOffset;
172        }
173
174        inline bitquad_t quad() const {
175            return *mQuadIterator;
176        }
177
178        inline bool equal(const quad_iterator & other) const {
179            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
180        }
181
182    private:
183        RunIterator     mRunIterator;
184        QuadIterator    mQuadIterator;
185        unsigned        mOffset;
186    };
187
188    inline quad_iterator quad_begin() const {
189        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
190    }
191
192    inline quad_iterator quad_end() const {
193        return quad_iterator(mRuns.cend(), mQuads.cend());
194    }
195
196private:
197
198    RunVector               mRuns;
199    QuadVector              mQuads;
200    static SlabAllocator<>  mAllocator;
201};
202
203
204inline void UnicodeSet::swap(UnicodeSet & other) {
205    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
206}
207
208inline void UnicodeSet::swap(UnicodeSet && other) {
209    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
210}
211
212}
213
214#endif
215
Note: See TracBrowser for help on using the repository browser.