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

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

Optimizations for re_local

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