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

Last change on this file since 6194 was 5935, checked in by cameron, 19 months ago

Direct CC builder work

File size: 8.4 KB
RevLine 
[4189]1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
[5748]3
4#include "UCD_Config.h"
[4189]5#include <stdint.h>
6#include <vector>
[4616]7#include <boost/iterator/iterator_facade.hpp>
[4983]8#include <util/slab_allocator.h>
[4611]9
[4189]10//
11// unicode_set.h - representing and manipulating sets of Unicode
12// characters, based on data from UCD - the Unicode Character Database
13//
14// Robert D. Cameron
15// September 18, 2014
16//
17// Licensed under Open Software License 3.0.
18//
19// Unicode Sparse Bitset Representation
20//
21// The Unicode Sparse Bitset representation is based on
22// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
23// (b) Specifying the quads using a run-length encoding, in which each run
24//     is Empty (quads contain no members), Mixed (quads contain some members and
25//     some nonmembers) or Full (all codepoints in each quad are members of the set).
26// (c) Explicitly listing all the quads of Mixed type.
27//
28
29//
30// The internal datatype for quads - bitsets of 2^k codepoints.
31// Default: 64 codepoints (k=6).
32//
[4616]33
[5748]34namespace llvm { class raw_ostream; }
35namespace re { class RE; }
[4618]36
[4621]37namespace UCD {
[4189]38
39enum run_type_t : uint16_t {Empty, Mixed, Full};
40
[4620]41class UnicodeSet {
[5748]42    friend class re::RE;
43    template<typename RunVector, typename QuadVector> friend void assign(UnicodeSet *, const RunVector &, const QuadVector &) noexcept;
[4620]44public:
45
[4621]46    using bitquad_t = uint32_t;
47    using length_t = uint16_t;
[5748]48    using size_type = size_t;
49
[4621]50    using run_t = std::pair<run_type_t, length_t>;
[4622]51    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
[4621]52
[4620]53    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
[4616]54        friend class UnicodeSet;
[4617]55        friend class boost::iterator_core_access;
[4616]56    protected:
[4627]57
[5748]58        iterator(const run_t * const runIterator, const bitquad_t * const quadIterator, const codepoint_t baseCodePoint)
[4620]59        : mRunIterator(runIterator), mQuadIterator(quadIterator)
[4627]60        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(baseCodePoint), mMinCodePoint(baseCodePoint), mMaxCodePoint(baseCodePoint) {
[4617]61
[4618]62        }
63
[4620]64        void advance(const unsigned n);
[4617]65
[4622]66        inline interval_t dereference() const {
[4618]67            return std::make_pair(mMinCodePoint, mMaxCodePoint);
68        }
[4617]69
[4616]70        inline void increment() {
71            advance(1);
72        }
[4617]73
[4622]74        inline bool equal(const iterator & other) const {
[4627]75            return (mMinCodePoint == other.mMinCodePoint);
[4616]76        }
77    private:
[5748]78        const run_t *       mRunIterator;
79        const bitquad_t *   mQuadIterator;
[4860]80        unsigned            mMixedRunIndex;
81        bitquad_t           mQuadOffset;
82        codepoint_t         mBaseCodePoint;
83        codepoint_t         mMinCodePoint;
84        codepoint_t         mMaxCodePoint;
[4616]85    };
86
[4618]87    inline iterator begin() const {
[4627]88        // note: preincrement forces the iterator to advance onto and capture the first interval.
[5748]89        return ++iterator(mRuns, mQuads, 0);
[4618]90    }
91
92    inline iterator end() const {
[5748]93        return iterator(mRuns, mQuads, UNICODE_MAX+1);
[4618]94    }
95
[5748]96    bool empty() const { // The set has no members
97        return (mRunLength == 1) && mRuns->first == Empty;
98    }
99
100    bool full() const {  // The set has the full set of possible Unicode codepoints.
101        return (mRunLength == 1) && mRuns->first == Full;
102    }
[5727]103   
[5739]104    codepoint_t at(const size_type k) const; // return the k-th codepoint (or throw an error if it doesn't exist)
105
[5748]106    bool contains(const codepoint_t codepoint) const noexcept;
[4860]107
[5748]108    bool intersects(const codepoint_t lo, const codepoint_t hi) const noexcept;
[5632]109   
[5748]110    bool intersects(const UnicodeSet & other) const noexcept;
[5742]111
[5748]112    bool subset(const UnicodeSet & other) const noexcept;
[5632]113   
[4860]114    void insert(const codepoint_t cp);
115
[5748]116    void insert(const UnicodeSet & other) noexcept;
117
118    void invert() noexcept;
119
[4860]120    void insert_range(const codepoint_t lo, const codepoint_t hi);
121
[5748]122    size_type size() const noexcept; // number of intervals in this set
[4860]123
[5748]124    size_type count() const noexcept; // number of codepoints in this set
[5739]125
[5748]126    interval_t front() const noexcept;
[4860]127
[5748]128    interval_t back() const noexcept;
[4860]129
[5748]130    void print(llvm::raw_ostream & out) const noexcept;
[5620]131
[5748]132    void dump(llvm::raw_ostream & out) const noexcept;
[4860]133
[5748]134    UnicodeSet operator~() const noexcept;
135    UnicodeSet operator&(const UnicodeSet & other) const noexcept;
136    UnicodeSet operator+(const UnicodeSet & other) const noexcept;
137    UnicodeSet operator-(const UnicodeSet & other) const noexcept;
138    UnicodeSet operator^(const UnicodeSet & other) const noexcept;
[5935]139   
140    // The subset of a UnicodeSet consisting of the isolated codepoints only, i.e.,
141    // those codepoints cp such that neither cp-1 nor cp+1 is a member of the set.
142    UnicodeSet isolates () const noexcept;
[4860]143
[5748]144    UnicodeSet & operator=(const UnicodeSet & other) noexcept;
145    UnicodeSet & operator=(const UnicodeSet && other) noexcept;
146    bool operator==(const UnicodeSet & other) const noexcept;
147    bool operator<(const UnicodeSet & other) const noexcept;
[4860]148
[5748]149    UnicodeSet() noexcept;
150    UnicodeSet(const codepoint_t codepoint) noexcept;
151    UnicodeSet(const codepoint_t lo, const codepoint_t hi) noexcept;
152    UnicodeSet(const UnicodeSet & other) noexcept;
153    UnicodeSet(const UnicodeSet && other) noexcept;
[4860]154
[5748]155    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end) noexcept;
156    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end) noexcept;
157    UnicodeSet(run_t * const runs, const uint32_t runLength, const uint32_t runCapacity, bitquad_t * const quads, const uint32_t quadLength, const uint32_t quadCapacity) noexcept;
158
159    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) noexcept;
160
[5742]161    inline static void Reset() {
162        GlobalAllocator.Reset();
163    }
164
[4860]165protected:
166
[4622]167    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
[4617]168        friend class UnicodeSet;
169        friend class boost::iterator_core_access;
[4618]170    public:
[5748]171        explicit quad_iterator(const run_t * const runIterator, const run_t * const runEnd, const bitquad_t * const quadIterator, const bitquad_t * const quadEnd, const run_type_t type, const length_t remaining)
[5740]172        : mRunIterator(runIterator)
173        , mRunEnd(runEnd)
174        , mQuadIterator(quadIterator)
175        #ifndef NDEBUG
176        , mQuadEnd(quadEnd)
177        #endif
178        , mType(type)
[5742]179        , mRemaining(remaining) {
180            assert (type == Empty || type == Mixed || type == Full);
181            assert (remaining > 0 || type == Empty);
[5759]182            assert (remaining <= ((UNICODE_MAX+1) / (sizeof(bitquad_t) * 8)));
[5742]183        }
[4617]184
185        void advance(unsigned n);
186
[4622]187        inline quad_iterator_return_t dereference() const {
[4629]188            return std::make_pair(std::make_pair(type(), length()), quad());
[4617]189        }
190
191        inline void increment() {
192            advance(1);
193        }
194
[4629]195        inline run_type_t type() const {
[5740]196            return mType;
[4618]197        }
198
[4629]199        inline length_t length() const {
[5740]200            return mRemaining;
[4629]201        }
202
[4622]203        inline bitquad_t quad() const {
[5740]204            assert (mQuadIterator != mQuadEnd);
[4620]205            return *mQuadIterator;
[4618]206        }
207
208        inline bool equal(const quad_iterator & other) const {
[5740]209            const auto r = (mRunIterator == other.mRunIterator) && (mRemaining == other.mRemaining);
210            assert (!r || (mQuadIterator == other.mQuadIterator));
211            return r;
[4617]212        }
[4618]213
[4617]214    private:
[5748]215        const run_t *           mRunIterator;
216        const run_t * const     mRunEnd;
217        const bitquad_t *       mQuadIterator;
[5740]218        #ifndef NDEBUG
[5748]219        const bitquad_t * const mQuadEnd;
[5740]220        #endif
[5748]221        run_type_t              mType;
222        length_t                mRemaining;
[4617]223    };
224
225    inline quad_iterator quad_begin() const {
[5748]226        return quad_iterator(mRuns, mRuns + mRunLength, mQuads, mQuads + mQuadLength, std::get<0>(*mRuns), std::get<1>(*mRuns));
[4617]227    }
228
[5755]229    inline quad_iterator quad_end() const {       
[5748]230        return quad_iterator(mRuns + mRunLength, mRuns + mRunLength, mQuads + mQuadLength, mQuads + mQuadLength, Empty, 0);
[4617]231    }
232
[4618]233private:
234
[5748]235    run_t *                 mRuns;
236    bitquad_t *             mQuads;
[4189]237
[5748]238    uint32_t                mRunLength;
239    uint32_t                mQuadLength;
[4812]240
[5748]241    uint32_t                mRunCapacity;
242    uint32_t                mQuadCapacity;
[4621]243
[5748]244    static SlabAllocator<>  GlobalAllocator;
245};
[4621]246
[4618]247}
[4189]248
249#endif
250
Note: See TracBrowser for help on using the repository browser.