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

Last change on this file since 5656 was 5632, checked in by cameron, 2 years ago

Optimizations for re_local

File size: 6.6 KB
RevLine 
[4189]1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
3#include <stdint.h>
4#include <vector>
[4616]5#include <boost/iterator/iterator_facade.hpp>
[4983]6#include <util/slab_allocator.h>
[4611]7
[4189]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//
[4616]31
[4618]32namespace llvm {
33class raw_ostream;
34}
35
[4621]36namespace UCD {
[4189]37
[5278]38typedef unsigned codepoint_t;
39enum : codepoint_t { UNICODE_MAX = 0x10FFFF };
40
[4189]41enum run_type_t : uint16_t {Empty, Mixed, Full};
42
[4620]43class UnicodeSet {
44public:
45
[4621]46    using bitquad_t = uint32_t;
47    using length_t = uint16_t;
48    using run_t = std::pair<run_type_t, length_t>;
[4622]49    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
[4621]50
[4812]51    using interval_t = std::pair<codepoint_t, codepoint_t>;
52
[5240]53    using RunVector = std::vector<run_t, ProxyAllocator<run_t>>;
54    using QuadVector = std::vector<bitquad_t, ProxyAllocator<bitquad_t>>;
[4860]55    using RunIterator = RunVector::const_iterator;
56    using QuadIterator = QuadVector::const_iterator;
57
[4812]58    using size_type = RunVector::size_type;
59
[4620]60    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
[4616]61        friend class UnicodeSet;
[4617]62        friend class boost::iterator_core_access;
[4616]63    protected:
[4627]64
65        iterator(const RunVector::const_iterator runIterator, const QuadVector::const_iterator quadIterator, const codepoint_t baseCodePoint)
[4620]66        : mRunIterator(runIterator), mQuadIterator(quadIterator)
[4627]67        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(baseCodePoint), mMinCodePoint(baseCodePoint), mMaxCodePoint(baseCodePoint) {
[4617]68
[4618]69        }
70
[4620]71        void advance(const unsigned n);
[4617]72
[4622]73        inline interval_t dereference() const {
[4618]74            return std::make_pair(mMinCodePoint, mMaxCodePoint);
75        }
[4617]76
[4616]77        inline void increment() {
78            advance(1);
79        }
[4617]80
[4622]81        inline bool equal(const iterator & other) const {
[4627]82            return (mMinCodePoint == other.mMinCodePoint);
[4616]83        }
84    private:
[4860]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;
[4616]92    };
93
[4618]94    inline iterator begin() const {
[4627]95        // note: preincrement forces the iterator to advance onto and capture the first interval.
96        return ++iterator(mRuns.cbegin(), mQuads.cbegin(), 0);
[4618]97    }
98
99    inline iterator end() const {
[4627]100        return iterator(mRuns.cend(), mQuads.cend(), 0x110000);
[4618]101    }
102
[5620]103    bool empty() const;
104
[4860]105    bool contains(const codepoint_t codepoint) const;
106
107    bool intersects(const codepoint_t lo, const codepoint_t hi) const;
[5632]108   
109    bool intersects(const UnicodeSet & other) const;
110   
[4860]111    void insert(const codepoint_t cp);
112
113    void insert_range(const codepoint_t lo, const codepoint_t hi);
114
115    size_type size() const;
116
117    interval_t front() const;
118
119    interval_t back() const;
120
[5620]121    void print(llvm::raw_ostream & out) const;
122
[4860]123    void dump(llvm::raw_ostream & out) const;
124
125    UnicodeSet operator~() const;
126    UnicodeSet operator&(const UnicodeSet & other) const;
127    UnicodeSet operator+(const UnicodeSet & other) const;
128    UnicodeSet operator-(const UnicodeSet & other) const;
129    UnicodeSet operator^(const UnicodeSet & other) const;
130
131    inline UnicodeSet & operator=(const UnicodeSet & other) = default;
132    inline UnicodeSet & operator=(UnicodeSet && other) = default;
133    bool operator==(const UnicodeSet & other) const;
134    bool operator<(const UnicodeSet & other) const;
135
136    UnicodeSet();
137    UnicodeSet(const codepoint_t codepoint);
138    UnicodeSet(const codepoint_t lo, const codepoint_t hi);
139    UnicodeSet(const UnicodeSet & other);
140    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q);
141    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end);
142    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end);
143
144    inline void swap(UnicodeSet & other);
145    inline void swap(UnicodeSet && other);
146
147protected:
148
149    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q);
150
[4622]151    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
[4617]152        friend class UnicodeSet;
153        friend class boost::iterator_core_access;
[4618]154    public:
[4860]155        quad_iterator(RunIterator runIterator, QuadIterator quadIterator)
[4620]156            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
[4617]157
158        void advance(unsigned n);
159
[4622]160        inline quad_iterator_return_t dereference() const {
[4629]161            return std::make_pair(std::make_pair(type(), length()), quad());
[4617]162        }
163
164        inline void increment() {
165            advance(1);
166        }
167
[4629]168        inline run_type_t type() const {
[4812]169            return mRunIterator->first;
[4618]170        }
171
[4629]172        inline length_t length() const {
[4812]173            return mRunIterator->second - mOffset;
[4629]174        }
175
[4622]176        inline bitquad_t quad() const {
[4620]177            return *mQuadIterator;
[4618]178        }
179
180        inline bool equal(const quad_iterator & other) const {
[4620]181            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
[4617]182        }
[4618]183
[4617]184    private:
[4860]185        RunIterator     mRunIterator;
186        QuadIterator    mQuadIterator;
187        unsigned        mOffset;
[4617]188    };
189
190    inline quad_iterator quad_begin() const {
[4620]191        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
[4617]192    }
193
194    inline quad_iterator quad_end() const {
[4620]195        return quad_iterator(mRuns.cend(), mQuads.cend());
[4617]196    }
197
[4618]198private:
199
[5037]200    RunVector               mRuns;
201    QuadVector              mQuads;
[5240]202    static SlabAllocator<>  mAllocator;
[4189]203};
204
[4812]205
[4621]206inline void UnicodeSet::swap(UnicodeSet & other) {
[4622]207    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
[4621]208}
209
210inline void UnicodeSet::swap(UnicodeSet && other) {
[4622]211    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
[4621]212}
213
[4618]214}
[4189]215
216#endif
217
Note: See TracBrowser for help on using the repository browser.