source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp @ 4982

Last change on this file since 4982 was 4982, checked in by cameron, 3 years ago

Eliminate legacy include files; prepare util directory

File size: 34.4 KB
Line 
1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
23#include <llvm/Support/raw_ostream.h>
24#include <llvm/Support/Format.h>
25#include <array>
26
27namespace UCD {
28
29using bitquad_t = UnicodeSet::bitquad_t;
30using run_t = UnicodeSet::run_t;
31using interval_t = UnicodeSet::interval_t;
32using codepoint_t = UnicodeSet::codepoint_t;
33
34//
35// Select the correct built-in scan function, dependent on whatever
36// bitquad_t resolves to, when scan_forwrad_zeroes<bitquad_t> is called.
37template <typename T> int scan_forward_zeroes(T x);
38template <> inline int scan_forward_zeroes<unsigned int>(unsigned int x){return __builtin_ctz(x);}
39template <> inline int scan_forward_zeroes<unsigned long>(unsigned long x){return __builtin_ctzl(x);}
40template <> inline int scan_forward_zeroes<unsigned long long>(unsigned long long x){return __builtin_ctzll(x);}
41
42
43
44UnicodeSet::Allocator UnicodeSet::mAllocator;
45
46const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
47const size_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
48const size_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
49const bitquad_t FULL_QUAD_MASK = -1;
50
51inline run_type_t typeOf(const run_t & run) {
52    return run.first;
53}
54
55inline UnicodeSet::length_t lengthOf(const run_t & run) {
56    return run.second;
57}
58
59/** ------------------------------------------------------------------------------------------------------------- *
60 * @brief append_run
61 ** ------------------------------------------------------------------------------------------------------------- */
62template <class RunVector>
63inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
64    if (LLVM_UNLIKELY(length == 0)) {
65        return;
66    } else if (!runs.empty() && typeOf(runs.back()) == type) {
67        std::get<1>(runs.back()) += length;
68        return;
69    }
70    runs.emplace_back(type, length);
71}
72
73/** ------------------------------------------------------------------------------------------------------------- *
74 * @brief append_quad
75 ** ------------------------------------------------------------------------------------------------------------- */
76template <class QuadVector, class RunVector>
77inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
78    run_type_t type = Empty;
79    if (LLVM_UNLIKELY(quad == 0)) {
80        type = Empty;
81    } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
82        type = Full;
83    } else {
84        quads.emplace_back(quad);
85        type = Mixed;
86    }
87    append_run(type, 1, runs);
88}
89
90#ifndef NDEBUG
91/** ------------------------------------------------------------------------------------------------------------- *
92 * @brief verify
93 *
94 * Sanity check for each function that constructs or modifies a UnicodeSet
95 ** ------------------------------------------------------------------------------------------------------------- */
96template <class RunVector, class QuadVector>
97inline bool verify(const RunVector & runs, const QuadVector & quads) {
98    unsigned sum = 0;
99    unsigned mixedQuads = 0;
100    for (auto run : runs) {
101        const auto l = lengthOf(run);
102        if (l == 0) {
103            throw std::runtime_error("Zero-length quad found!");
104        }
105        if (typeOf(run) == Mixed) {
106            mixedQuads += l;
107        }
108        sum += l;
109    }
110    if (sum != UNICODE_QUAD_COUNT) {
111        throw std::runtime_error("Invalid quad count: found " + std::to_string(sum) + " but expected " + std::to_string(UNICODE_QUAD_COUNT));
112    }
113    if (mixedQuads != quads.size()) {
114        throw std::runtime_error("Invalid mixed quad count: found " + std::to_string(quads.size()) + " but expected " + std::to_string(mixedQuads));
115    }
116    for (auto quad : quads) {
117        if (quad == 0) {
118            throw std::runtime_error("Empty quad found in Mixed quad array!");
119        } else if (quad == FULL_QUAD_MASK) {
120            throw std::runtime_error("Full quad found in Mixed quad array!");
121        }
122    }
123    return true;
124}
125#endif
126
127/** ------------------------------------------------------------------------------------------------------------- *
128 * @brief empty
129 ** ------------------------------------------------------------------------------------------------------------- */
130bool UnicodeSet::empty() const {
131    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
132}
133
134/** ------------------------------------------------------------------------------------------------------------- *
135 * @brief size
136 ** ------------------------------------------------------------------------------------------------------------- */
137UnicodeSet::size_type UnicodeSet::size() const {
138    return std::distance(begin(), end());
139}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief front
143 ** ------------------------------------------------------------------------------------------------------------- */
144UnicodeSet::interval_t UnicodeSet::front() const {
145    return *begin();
146}
147
148/** ------------------------------------------------------------------------------------------------------------- *
149 * @brief back
150 ** ------------------------------------------------------------------------------------------------------------- */
151UnicodeSet::interval_t UnicodeSet::back() const {
152    auto back = begin();
153    for (auto i = back; i != end(); back = i++);
154    return *back;
155}
156
157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief dump
159 ** ------------------------------------------------------------------------------------------------------------- */
160void UnicodeSet::dump(llvm::raw_ostream & out) const {
161    auto qi = mQuads.cbegin();
162    for (const run_t & run : mRuns) {
163        if (typeOf(run) == Empty) {
164            out << "Empty(" << lengthOf(run) << ")\n";
165        }
166        else if (typeOf(run) == Full) {
167            out << "Full(" << lengthOf(run) << ")\n";
168        }
169        else {
170            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
171                assert (qi != mQuads.cend());
172                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
173            }
174        }
175    }
176}
177
178/** ------------------------------------------------------------------------------------------------------------- *
179 * @brief complement
180 ** ------------------------------------------------------------------------------------------------------------- */
181UnicodeSet UnicodeSet::operator~() const {
182    std::vector<run_t> runs;
183    std::vector<bitquad_t> quads;
184    runs.reserve(mRuns.size());
185    quads.reserve(mQuads.size());
186    auto qi = quads.cbegin();
187    for (const run_t & run : mRuns) {
188        if (typeOf(run) == Empty) {
189            append_run(Full, lengthOf(run), runs);
190        }
191        else if (typeOf(run) == Full) {
192            append_run(Empty, lengthOf(run), runs);
193        }
194        else {
195            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
196                assert (qi != quads.cend());
197                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
198            }
199        }
200    }
201    return UnicodeSet(std::move(runs), std::move(quads));
202}
203
204/** ------------------------------------------------------------------------------------------------------------- *
205 * @brief intersection
206 ** ------------------------------------------------------------------------------------------------------------- */
207UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
208    std::vector<run_t> runs;
209    std::vector<bitquad_t> quads;
210    const auto e1 = quad_end();
211    const auto e2 = other.quad_end();
212    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
213        const auto n = std::min(i1.length(), i2.length());
214        if ((i1.type() == Full) && (i2.type() == Full)) {
215            append_run(Full, n, runs);
216            i1 += n;
217            i2 += n;
218        }
219        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
220            append_run(Empty, n, runs);
221            i1 += n;
222            i2 += n;
223        }
224        else if (i1.type() == Full) {
225            for (unsigned i = 0; i != n; ++i, ++i2) {
226                append_quad(i2.quad(), quads, runs);
227            }
228            i1 += n;
229        }
230        else if (i2.type() == Full) {
231            for (unsigned i = 0; i != n; ++i, ++i1) {
232                append_quad(i1.quad(), quads, runs);
233            }
234            i2 += n;
235        }
236        else { //both Mixed
237            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
238                append_quad(i1.quad() & i2.quad(), quads, runs);
239            }
240        }
241    }
242    return UnicodeSet(std::move(runs), std::move(quads));
243}
244
245/** ------------------------------------------------------------------------------------------------------------- *
246 * @brief union
247 ** ------------------------------------------------------------------------------------------------------------- */
248UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
249    std::vector<run_t> runs;
250    std::vector<bitquad_t> quads;
251    const auto e1 = quad_end();
252    const auto e2 = other.quad_end();
253    auto i1 = quad_begin(), i2 = other.quad_begin();
254    for (; i1 != e1 && i2 != e2; ) {
255        const auto n = std::min(i1.length(), i2.length());
256        if ((i1.type() == Empty) && (i2.type() == Empty)) {
257            append_run(Empty, n, runs);
258            i1 += n;
259            i2 += n;
260        } else if ((i1.type() == Full) || (i2.type() == Full)) {
261            append_run(Full, n, runs);
262            i1 += n;
263            i2 += n;
264        } else if (i1.type() == Empty) {
265            for (unsigned i = 0; i != n; ++i, ++i2) {
266                append_quad(i2.quad(), quads, runs);
267            }
268            i1 += n;
269        } else if (i2.type() == Empty) {
270            for (unsigned i = 0; i != n; ++i, ++i1) {
271                append_quad(i1.quad(), quads, runs);
272            }
273            i2 += n;
274        } else {
275            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
276                append_quad(i1.quad() | i2.quad(), quads, runs);
277            }
278        }
279    }
280    return UnicodeSet(std::move(runs), std::move(quads));
281}
282
283/** ------------------------------------------------------------------------------------------------------------- *
284 * @brief difference
285 ** ------------------------------------------------------------------------------------------------------------- */
286UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
287    std::vector<run_t> runs;
288    std::vector<bitquad_t> quads;
289    const auto e1 = quad_end();
290    const auto e2 = other.quad_end();
291    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
292        unsigned n = std::min(i1.length(), i2.length());
293        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
294            append_run(i1.type(), n, runs);
295            i1 += n;
296            i2 += n;
297        }
298        else if (i1.type() == Full) {
299            for (unsigned i = 0; i != n; ++i, ++i2) {
300                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
301            }
302            i1 += n;
303        }
304        else if (i2.type() == Empty) {
305            for (unsigned i = 0; i != n; ++i, ++i1) {
306                append_quad(i1.quad(), quads, runs);
307            }
308            i2 += n;
309        }
310        else {
311            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
312                append_quad(i1.quad() &~ i2.quad(), quads, runs);
313            }
314        }
315    }
316    return UnicodeSet(std::move(runs), std::move(quads));
317}
318
319/** ------------------------------------------------------------------------------------------------------------- *
320 * @brief symmetric difference
321 ** ------------------------------------------------------------------------------------------------------------- */
322UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
323    std::vector<run_t> runs;
324    std::vector<bitquad_t> quads;
325    const auto e1 = quad_end();
326    const auto e2 = other.quad_end();
327    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
328        unsigned n = std::min(i1.length(), i2.length());
329        if (i1.type() != Mixed && i2.type() != Mixed) {
330            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
331            i1 += n;
332            i2 += n;
333        }
334        else if (i1.type() == Empty) {
335            for (unsigned i = 0; i < n; ++i, ++i2) {
336                append_quad(i2.quad(), quads, runs);
337            }
338            i1 += n;
339        }
340        else if (i2.type() == Empty) {
341            for (unsigned i = 0; i < n; ++i, ++i1) {
342                append_quad(i1.quad(), quads, runs);
343            }
344            i2 += n;
345        }
346        else if (i1.type() == Full) {
347            for (unsigned i = 0; i < n; ++i, ++i2) {
348                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
349            }
350            i1 += n;
351        }
352        else if (i2.type() == Empty) {
353            for (unsigned i = 0; i < n; ++i, ++i1) {
354                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
355            }
356            i2 += n;
357        }
358        else {
359            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
360                append_quad(i1.quad() ^ i2.quad(), quads, runs);
361            }
362        }
363    }
364    return UnicodeSet(std::move(runs), std::move(quads));
365}
366
367/** ------------------------------------------------------------------------------------------------------------- *
368 * @brief equality
369 ** ------------------------------------------------------------------------------------------------------------- */
370bool UnicodeSet::operator==(const UnicodeSet & other) const {
371    if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
372        return false;
373    }
374    for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
375        if (*i != *j) return false;
376    }
377    for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
378        if (*i != *j) return false;
379    }
380    return true;
381}
382
383/** ------------------------------------------------------------------------------------------------------------- *
384 * @brief less operator
385 ** ------------------------------------------------------------------------------------------------------------- */
386bool UnicodeSet::operator<(const UnicodeSet & other) const {
387    if (LLVM_LIKELY(mRuns.size() != other.mRuns.size())) {
388        return mRuns.size() < other.mRuns.size();
389    } else if (LLVM_LIKELY(mQuads.size() != other.mQuads.size())) {
390        return (mQuads.size() < other.mQuads.size());
391    } else { // equal run and quad lengths; test their individual values
392        for (auto ri = mRuns.cbegin(), end = mRuns.cend(), rj = other.mRuns.cbegin(); ri != end; ++ri, ++rj) {
393            if (*ri < *rj) {
394                return true;
395            } else if (*ri > *rj) {
396                return false;
397            }
398        }
399        for (auto qi = mQuads.cbegin(), end = mQuads.cend(), qj = other.mQuads.cbegin(); qi != end; ++qi, ++qj) {
400            if (*qi < *qj) {
401                return true;
402            } else if (*qi > *qj) {
403                return false;
404            }
405        }
406        return false;
407    }
408}
409
410/** ------------------------------------------------------------------------------------------------------------- *
411 * @brief insert
412 ** ------------------------------------------------------------------------------------------------------------- */
413void UnicodeSet::insert(const codepoint_t cp) {
414
415    if (LLVM_UNLIKELY(cp >= UNICODE_MAX)) {
416        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
417    }
418
419    codepoint_t offset = cp / QUAD_BITS;
420    const bitquad_t value = static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK);
421    auto run = mRuns.begin();
422    auto quad = mQuads.begin();
423    length_t l = 0;
424    run_type_t t = Empty;
425    for (;;) {
426        std::tie(t, l) = *run;
427        if (offset < l) {
428            break;
429        }
430        if (t == Mixed) {
431            quad += l;
432        }
433        offset -= l;
434        ++run;
435    }
436    if (LLVM_LIKELY(t == Mixed)) {
437        quad += offset;
438        *quad |= value;
439        if (LLVM_LIKELY(*quad != FULL_QUAD_MASK)) {
440            assert (contains(cp));
441            return;
442        }
443        mQuads.erase(quad);
444    } else if (t == Empty) {
445        mQuads.insert(quad, value);
446    } else { // if (t == Full) {
447        assert (contains(cp));
448        return;
449    }
450    const unsigned remaining = l - (offset + 1);
451    if (offset == 0) {
452        *run = std::make_pair(t == Empty ? Mixed : Full, 1);
453        if (remaining != 0) {
454            mRuns.insert(++run, std::make_pair(t, remaining));
455        }
456    } else {
457        run->second = offset;
458        if (remaining == 0) {
459            mRuns.insert(++run, std::make_pair(t == Empty ? Mixed : Full, 1));
460        } else {
461            mRuns.insert(++run, {std::make_pair(t == Empty ? Mixed : Full, 1), std::make_pair(t, remaining)});
462        }
463    }
464
465    assert (verify(mRuns, mQuads));
466    assert (contains(cp));
467}
468
469/** ------------------------------------------------------------------------------------------------------------- *
470 * @brief insert_range
471 ** ------------------------------------------------------------------------------------------------------------- */
472void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
473
474    if (LLVM_UNLIKELY(lo > hi)) {
475        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
476    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
477        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
478    }
479
480    // Create a temporary run and quad set for the given range
481    std::vector<run_t> runs;
482    std::vector<bitquad_t> quads;
483
484    codepoint_t lo_index = lo / QUAD_BITS;
485    codepoint_t hi_index = hi / QUAD_BITS;
486
487    auto ri = mRuns.cbegin();
488    auto qi = mQuads.cbegin();
489
490    length_t length = 0;
491    run_type_t type = Empty;
492    // Advance past any full runs prior to the lo_index
493    for (;;) {
494        std::tie(type, length) = *ri;
495        if (lo_index < length) {
496            break;
497        }
498        if (type == Mixed) {
499            qi += length;
500        }
501        lo_index -= length;
502        hi_index -= length;
503        ++ri;
504    }
505
506    // Now record the runs and any quads prior to lo_index
507    runs.assign(mRuns.cbegin(), ri);
508    if (lo_index) {
509        runs.push_back(std::make_pair(type, lo_index));
510        if (type == Mixed) {
511            qi += lo_index;
512        }
513        hi_index -= lo_index;
514        length -= lo_index;
515    }
516
517    quads.assign(mQuads.cbegin(), qi);
518    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
519    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
520    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
521
522    // If our original quad is full, just append a Full run
523    if (LLVM_UNLIKELY(type == Full)) {
524        append_run(Full, 1, runs);
525    } else { // Otherwise merge the new quad value with the original one
526        if (hi_index == 0) {
527            lo_quad &= hi_quad;
528        }
529        if (type == Mixed) {
530            lo_quad |= *qi++;
531        }
532        append_quad(lo_quad, quads, runs);
533    }
534    --length;
535
536    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
537    // in the original quad to suit.
538    if (hi_index) {
539        // Add in any full runs between the lo and hi quads
540        append_run(Full, hi_index - 1, runs);
541        // Advance past original quads that were filled in
542        for (;;) {
543            if (type == Mixed) {
544                qi += length;
545            }
546            std::tie(type, length) = *++ri;
547            if (hi_index < length) {
548                break;
549            }
550            hi_index -= length;
551        }
552
553        // Write out the hi_quad value
554        if (LLVM_UNLIKELY(type == Full)) {
555            append_run(Full, 1, runs);
556        } else {
557            if (type == Mixed) {
558                qi += hi_index;
559                hi_quad |= *qi++;
560            }
561            append_quad(hi_quad, quads, runs);
562        }
563    }
564
565    // And append any remaining values from the original data
566    append_run(type, length - hi_index, runs);
567    runs.insert(runs.end(), ++ri, mRuns.cend());
568    quads.insert(quads.end(), qi, mQuads.cend());
569
570    assert (verify(runs, quads));
571
572    mRuns.assign(runs.cbegin(), runs.cend());
573    mQuads.assign(quads.cbegin(), quads.cend());
574}
575
576/** ------------------------------------------------------------------------------------------------------------- *
577 * @brief contains
578 * @param codepoint
579 *
580 * Return whether this UnicodeSet contains the specified code point
581 ** ------------------------------------------------------------------------------------------------------------- */
582bool UnicodeSet::contains(const codepoint_t cp) const {
583    codepoint_t offset = cp / QUAD_BITS;
584    auto quad = mQuads.cbegin();
585    for (const auto r : mRuns) {
586        length_t l = 0;
587        run_type_t t = Empty;
588        std::tie(t, l) = r;
589        if (offset < l) {
590            if (t == Mixed) {
591                quad += offset;
592                return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
593            }
594            return (t == Full);
595        }
596        if (t == Mixed) {
597            quad += l;
598        }       
599        offset -= l;
600    }
601    return false;
602}
603
604/** ------------------------------------------------------------------------------------------------------------- *
605 * @brief intersects
606 * @param lo_codepoint
607 * @param hi_codepoint
608 *
609 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
610 ** ------------------------------------------------------------------------------------------------------------- */
611bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
612    for (auto range : *this) {
613        if (range.second < lo) {
614            continue;
615        }
616        if (range.first > hi) {
617            break;
618        }
619        return true;
620    }
621    return false;
622}
623
624/** ------------------------------------------------------------------------------------------------------------- *
625 * @brief UnicodeSet::quad_iterator::advance
626 ** ------------------------------------------------------------------------------------------------------------- */
627void UnicodeSet::quad_iterator::advance(unsigned n) {
628    while (n > 0) {
629        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
630        if (remain > n) {
631            if (typeOf(*mRunIterator) == Mixed) {
632                mQuadIterator += n;
633            }
634            mOffset += n;
635            break;
636        }
637        if (typeOf(*mRunIterator) == Mixed) {
638            mQuadIterator += remain;
639        }
640        ++mRunIterator;
641        mOffset = 0;
642        n -= remain;
643    }
644}
645
646/** ------------------------------------------------------------------------------------------------------------- *
647 * @brief UnicodeSet::iterator::advance
648 ** ------------------------------------------------------------------------------------------------------------- */
649void UnicodeSet::iterator::advance(const unsigned n) {
650
651    assert (n == 1);
652
653    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
654        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
655    }
656
657    bool found = false;
658    // Find the start of our interval
659    while ( mBaseCodePoint < 0x110000 ) {
660        // Find the first non-empty block
661        if (typeOf(*mRunIterator) != Mixed) {           
662            // If we found a full run, this must be the start of our interval.
663            const auto baseCodePoint = mBaseCodePoint;
664            const auto type = typeOf(*mRunIterator);
665            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
666            if (type == Full) {
667                mMinCodePoint = baseCodePoint;
668                found = true;
669                break;
670            }
671        } else { // if (typeOf(t) == Mixed)
672            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
673                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
674                // If we found a marker in m, it marks the beginning of our current interval.
675                // Find it and break out of the loop.
676                if (m) {
677                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
678                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
679                    found = true;
680                    break;
681                }
682                mBaseCodePoint += QUAD_BITS;
683                ++mQuadIterator;
684                ++mMixedRunIndex;
685                mQuadOffset = 0;
686            }
687            if (found) break;
688            ++mRunIterator;
689            mQuadOffset = 0;
690            mMixedRunIndex = 0;
691        }
692    }
693
694    if (!found) {
695        assert (mBaseCodePoint == 0x110000);
696        mMinCodePoint = 0x110000;
697        return;
698    }
699
700    // at this stage, the max code point is the previous max code point (initially 0)
701    assert (mMaxCodePoint <= mMinCodePoint);
702    found = false;
703    // Find the end of our interval
704    while ( mBaseCodePoint < 0x110000 ) {
705
706        // Find the first non-Full block
707        if (typeOf(*mRunIterator) != Mixed) {
708            // If this run is Empty, the max code point is the last computed base code point - 1.
709            const auto baseCodePoint = mBaseCodePoint;
710            const auto type = typeOf(*mRunIterator);
711            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
712            if (type == Empty) {
713                mMaxCodePoint = baseCodePoint - 1;
714                found = true;
715                break;
716            }
717        } else { // if (typeOf(t) == Mixed)
718            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
719                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
720
721                // If we found a marker in m, it marks the end of our current interval.
722                // Find it and break out of the loop.
723                if (m) {
724                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
725                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
726                    found = true;
727                    break;
728                }
729                mBaseCodePoint += QUAD_BITS;
730                ++mQuadIterator;
731                ++mMixedRunIndex;
732                mQuadOffset = 0;
733            }
734            if (found) break;
735            ++mRunIterator;
736            mQuadOffset = 0;
737            mMixedRunIndex = 0;
738        }
739    }
740    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
741    if (!found) {
742        assert (mBaseCodePoint == 0x110000);
743        mMaxCodePoint = 0x10FFFF;
744    }
745
746    assert (mMinCodePoint <= mMaxCodePoint);
747}
748
749/** ------------------------------------------------------------------------------------------------------------- *
750 * @brief Empty Set Constructor
751 ** ------------------------------------------------------------------------------------------------------------- */
752UnicodeSet::UnicodeSet()
753: mRuns(reinterpret_cast<RunAllocator &>(mAllocator))
754, mQuads(reinterpret_cast<QuadAllocator &>(mAllocator))
755{
756    append_run(Empty, UNICODE_QUAD_COUNT, mRuns);
757    assert (verify(mRuns, mQuads));
758}
759
760/** ------------------------------------------------------------------------------------------------------------- *
761 * @brief Singleton Set Constructor
762 ** ------------------------------------------------------------------------------------------------------------- */
763UnicodeSet::UnicodeSet(const codepoint_t codepoint)
764: mRuns(reinterpret_cast<RunAllocator &>(mAllocator))
765, mQuads(reinterpret_cast<QuadAllocator &>(mAllocator))
766{
767    const codepoint_t quad_no = codepoint / QUAD_BITS;
768    append_run(Empty, quad_no, mRuns);
769    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
770    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
771    assert (verify(mRuns, mQuads));
772}
773
774/** ------------------------------------------------------------------------------------------------------------- *
775 * @brief Range Set Constructor
776 ** ------------------------------------------------------------------------------------------------------------- */
777UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
778: mRuns(reinterpret_cast<RunAllocator &>(mAllocator))
779, mQuads(reinterpret_cast<QuadAllocator &>(mAllocator))
780{
781    const codepoint_t lo_index = lo / QUAD_BITS;
782    const codepoint_t hi_index = hi / QUAD_BITS;
783    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
784    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
785    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
786    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
787    append_run(Empty, lo_index, mRuns);
788    bitquad_t mask = hi_quad;
789    if (lo_index == hi_index) {
790        mask &= lo_quad;
791    } else {
792        append_quad(lo_quad, mQuads, mRuns);
793        append_run(Full, hi_index - (lo_index + 1), mRuns);
794    }
795    append_quad(mask, mQuads, mRuns);
796    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
797    assert (verify(mRuns, mQuads));
798}
799
800/** ------------------------------------------------------------------------------------------------------------- *
801 * @brief Range List Set Constructor
802 ** ------------------------------------------------------------------------------------------------------------- */
803template <typename itr>
804void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
805    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
806        assert (l.first <= l.second);
807        assert (l.second < UNICODE_MAX);
808        assert (r.first <= r.second);
809        assert (r.second < UNICODE_MAX);
810        return l.second < r.first;
811    }));
812
813    std::vector<run_t> runs;
814    std::vector<bitquad_t> quads;
815
816    codepoint_t prior_index = 0;
817    bitquad_t mask = 0;
818    for (auto interval = begin; interval != end; ) {
819        codepoint_t lo, hi;
820        std::tie(lo, hi) = *interval;
821        const codepoint_t lo_index = (lo / QUAD_BITS);
822        const codepoint_t hi_index = (hi / QUAD_BITS);
823        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
824        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
825        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
826        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
827        append_run(Empty, lo_index - prior_index, runs);
828        if (lo_index == hi_index) {
829            mask |= (lo_quad & hi_quad);
830        } else {
831            append_quad(mask | lo_quad, quads, runs);
832            append_run(Full, hi_index - (lo_index + 1), runs);
833            mask = hi_quad;
834        }
835        // if the next interval is in our current quad, continue to the next range
836        prior_index = hi_index;
837        if (LLVM_LIKELY(++interval != end)) {
838            if (hi_index == (interval->first / QUAD_BITS)) {
839                continue;
840            }
841        }
842        append_quad(mask, quads, runs);
843        mask = 0;
844        ++prior_index;
845    }
846    assert (mask == 0);
847    if (prior_index < UNICODE_QUAD_COUNT) {
848        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
849    }   
850    assert (verify(runs, quads));
851    mRuns.assign(runs.begin(), runs.end());
852    mQuads.assign(quads.begin(), quads.end());
853}
854
855/** ------------------------------------------------------------------------------------------------------------- *
856 * @brief Interval Range Constructor
857 ** ------------------------------------------------------------------------------------------------------------- */
858UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
859: mRuns(0, {Empty, 0}, reinterpret_cast<RunAllocator &>(mAllocator))
860, mQuads(0, 0, reinterpret_cast<QuadAllocator &>(mAllocator))
861{
862    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
863}
864
865/** ------------------------------------------------------------------------------------------------------------- *
866 * @brief Interval Range Constructor
867 ** ------------------------------------------------------------------------------------------------------------- */
868UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
869: mRuns(0, {Empty, 0}, reinterpret_cast<RunAllocator &>(mAllocator))
870, mQuads(0, 0, reinterpret_cast<QuadAllocator &>(mAllocator))
871{
872    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
873}
874
875/** ------------------------------------------------------------------------------------------------------------- *
876 * @brief Copy Constructor
877 ** ------------------------------------------------------------------------------------------------------------- */
878UnicodeSet::UnicodeSet(const UnicodeSet & other)
879: mRuns(other.mRuns, reinterpret_cast<RunAllocator &>(mAllocator))
880, mQuads(other.mQuads, reinterpret_cast<QuadAllocator &>(mAllocator))
881{
882    assert (verify(mRuns, mQuads));
883}
884
885/** ------------------------------------------------------------------------------------------------------------- *
886 * @brief Initializer Constructor
887 ** ------------------------------------------------------------------------------------------------------------- */
888UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
889: mRuns(r.begin(), r.end(), reinterpret_cast<RunAllocator &>(mAllocator))
890, mQuads(q.begin(), q.end(), reinterpret_cast<QuadAllocator &>(mAllocator))
891{
892    assert (verify(mRuns, mQuads));
893}
894
895/** ------------------------------------------------------------------------------------------------------------- *
896 * @brief Internal Vector Constructor
897 ** ------------------------------------------------------------------------------------------------------------- */
898inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
899: mRuns(r.begin(), r.end(), reinterpret_cast<RunAllocator &>(mAllocator))
900, mQuads(q.begin(), q.end(), reinterpret_cast<QuadAllocator &>(mAllocator))
901{
902    assert (verify(mRuns, mQuads));
903}
904
905}
Note: See TracBrowser for help on using the repository browser.