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

Last change on this file since 5037 was 5037, checked in by nmedfort, 3 years ago

UnicodeSet? bug fix and compile warning clean-up.

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