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

Last change on this file since 5670 was 5646, checked in by nmedfort, 22 months ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

File size: 36.2 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    // Create a temporary run and quad set for the given range
492    std::vector<run_t> runs;
493    std::vector<bitquad_t> quads;
494
495    codepoint_t lo_index = lo / QUAD_BITS;
496    codepoint_t hi_index = hi / QUAD_BITS;
497
498    auto ri = mRuns.cbegin();
499    auto qi = mQuads.cbegin();
500
501    codepoint_t length = 0;
502    run_type_t type = Empty;
503
504    // Advance past any runs prior to the lo_index
505    for (;;) {
506        assert (ri != mRuns.cend());
507        std::tie(type, length) = *ri;       
508        if (lo_index < length) {
509            break;
510        }
511        if (type == Mixed) {
512            assert (std::distance(qi, mQuads.cend()) >= length);
513            qi += length;
514        }
515        lo_index -= length;
516        hi_index -= length;
517        ++ri;
518    }
519
520    // Now record the runs and any quads prior to lo_index
521    runs.assign(mRuns.cbegin(), ri++);
522    if (lo_index) {
523        runs.emplace_back(type, lo_index);
524        if (type == Mixed) {
525            assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) >= lo_index);
526            qi += lo_index;
527        }
528        hi_index -= lo_index;
529        length -= lo_index;
530    }
531
532    quads.assign(mQuads.cbegin(), qi);
533    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
534    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
535    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
536
537    // If our original quad is full, just append a Full run
538    if (LLVM_UNLIKELY(type == Full)) {
539        append_run(Full, 1, runs);
540    } else { // Otherwise merge the new quad value with the original one
541        if (hi_index == 0) {
542            lo_quad &= hi_quad;
543        }
544        if (type == Mixed) {
545            assert (std::distance(qi, mQuads.cend()) > 0);
546            lo_quad |= *qi++;
547        }
548        append_quad(lo_quad, quads, runs);
549    }
550    --length;
551
552    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
553    // in the original quad to suit.
554    if (hi_index) {
555        // Add in any full runs between the lo and hi quads
556        append_run(Full, hi_index - 1, runs);
557        // Advance past original quads that were filled in
558        while (ri != mRuns.cend()) {
559            if (type == Mixed) {
560                assert (std::distance(qi, mQuads.cend()) >= length);
561                qi += length;
562            }
563            std::tie(type, length) = *ri++;
564            if (hi_index < length) {
565                break;
566            }
567            hi_index -= length;
568            length = 0;
569        }       
570        // Write out the hi_quad value
571        if (LLVM_UNLIKELY(type == Full)) {
572            append_run(Full, 1, runs);
573        } else {
574            if (type == Mixed) {
575                assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) > hi_index);
576                qi += hi_index;
577                hi_quad |= *qi++;
578            }
579            append_quad(hi_quad, quads, runs);
580        }
581    }
582
583    // And append any remaining values from the original data
584    assert (length >= hi_index);
585    append_run(type, length - hi_index, runs);
586    assert ("We wrote all the runs but still have remaining quads?" && (ri != mRuns.cend() || qi == mQuads.cend()));
587    runs.insert(runs.end(), ri, mRuns.cend());
588    quads.insert(quads.end(), qi, mQuads.cend());
589    assert (verify(runs, quads));
590    mRuns.assign(runs.cbegin(), runs.cend());
591    mQuads.assign(quads.cbegin(), quads.cend());   
592}
593
594/** ------------------------------------------------------------------------------------------------------------- *
595 * @brief contains
596 * @param codepoint
597 *
598 * Return whether this UnicodeSet contains the specified code point
599 ** ------------------------------------------------------------------------------------------------------------- */
600bool UnicodeSet::contains(const codepoint_t cp) const {
601    codepoint_t offset = cp / QUAD_BITS;
602    auto quad = mQuads.cbegin();
603    for (const auto r : mRuns) {
604        length_t l = 0;
605        run_type_t t = Empty;
606        std::tie(t, l) = r;
607        if (offset < l) {
608            if (t == Mixed) {
609                quad += offset;
610                return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
611            }
612            return (t == Full);
613        }
614        if (t == Mixed) {
615            quad += l;
616        }       
617        offset -= l;
618    }
619    return false;
620}
621
622/** ------------------------------------------------------------------------------------------------------------- *
623 * @brief intersects
624 * @param lo_codepoint
625 * @param hi_codepoint
626 *
627 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
628 ** ------------------------------------------------------------------------------------------------------------- */
629bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
630    for (auto range : *this) {
631        if (range.second < lo) {
632            continue;
633        }
634        if (range.first > hi) {
635            break;
636        }
637        return true;
638    }
639    return false;
640}
641   
642   
643/** ------------------------------------------------------------------------------------------------------------- *
644 * @brief intersects
645 * @param other_set
646 *
647 * Return true if this UnicodeSet has a non-empty intersection with other_set
648 ** ------------------------------------------------------------------------------------------------------------- */
649bool UnicodeSet::intersects(const UnicodeSet & other) const {
650    const auto e1 = quad_end();
651    const auto e2 = other.quad_end();
652    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
653        const auto n = std::min(i1.length(), i2.length());
654        if (i1.type() == Empty) {
655            i1 += i1.length();
656            i2 += i1.length();
657        }
658        else if (i2.type() == Empty) {
659            i1 += i2.length();
660            i2 += i2.length();
661        }
662        else if (i1.type() == Full) {
663            return false;
664        }
665        else if (i2.type() == Full) {
666            return false;
667        }
668        else { //both Mixed
669            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
670                if ((i1.quad() & i2.quad()) != 0) return false;
671            }
672        }
673    }
674    return true;
675}
676
677
678/** ------------------------------------------------------------------------------------------------------------- *
679 * @brief UnicodeSet::quad_iterator::advance
680 ** ------------------------------------------------------------------------------------------------------------- */
681void UnicodeSet::quad_iterator::advance(unsigned n) {
682    while (n > 0) {
683        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
684        if (remain > n) {
685            if (typeOf(*mRunIterator) == Mixed) {
686                mQuadIterator += n;
687            }
688            mOffset += n;
689            break;
690        }
691        if (typeOf(*mRunIterator) == Mixed) {
692            mQuadIterator += remain;
693        }
694        ++mRunIterator;
695        mOffset = 0;
696        n -= remain;
697    }
698}
699
700/** ------------------------------------------------------------------------------------------------------------- *
701 * @brief UnicodeSet::iterator::advance
702 ** ------------------------------------------------------------------------------------------------------------- */
703void UnicodeSet::iterator::advance(const unsigned n) {
704
705    assert (n == 1);
706
707    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
708        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
709    }
710
711    bool found = false;
712    // Find the start of our interval
713    while ( mBaseCodePoint < 0x110000 ) {
714        // Find the first non-empty block
715        if (typeOf(*mRunIterator) != Mixed) {           
716            // If we found a full run, this must be the start of our interval.
717            const auto baseCodePoint = mBaseCodePoint;
718            const auto type = typeOf(*mRunIterator);
719            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
720            if (type == Full) {
721                mMinCodePoint = baseCodePoint;
722                found = true;
723                break;
724            }
725        } else { // if (typeOf(t) == Mixed)
726            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
727                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
728                // If we found a marker in m, it marks the beginning of our current interval.
729                // Find it and break out of the loop.
730                if (m) {
731                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
732                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
733                    found = true;
734                    break;
735                }
736                mBaseCodePoint += QUAD_BITS;
737                ++mQuadIterator;
738                ++mMixedRunIndex;
739                mQuadOffset = 0;
740            }
741            if (found) break;
742            ++mRunIterator;
743            mQuadOffset = 0;
744            mMixedRunIndex = 0;
745        }
746    }
747
748    if (!found) {
749        assert (mBaseCodePoint == 0x110000);
750        mMinCodePoint = 0x110000;
751        return;
752    }
753
754    // at this stage, the max code point is the previous max code point (initially 0)
755    assert (mMaxCodePoint <= mMinCodePoint);
756    found = false;
757    // Find the end of our interval
758    while ( mBaseCodePoint < 0x110000 ) {
759
760        // Find the first non-Full block
761        if (typeOf(*mRunIterator) != Mixed) {
762            // If this run is Empty, the max code point is the last computed base code point - 1.
763            const auto baseCodePoint = mBaseCodePoint;
764            const auto type = typeOf(*mRunIterator);
765            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
766            if (type == Empty) {
767                mMaxCodePoint = baseCodePoint - 1;
768                found = true;
769                break;
770            }
771        } else { // if (typeOf(t) == Mixed)
772            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
773                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
774
775                // If we found a marker in m, it marks the end of our current interval.
776                // Find it and break out of the loop.
777                if (m) {
778                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
779                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
780                    found = true;
781                    break;
782                }
783                mBaseCodePoint += QUAD_BITS;
784                ++mQuadIterator;
785                ++mMixedRunIndex;
786                mQuadOffset = 0;
787            }
788            if (found) break;
789            ++mRunIterator;
790            mQuadOffset = 0;
791            mMixedRunIndex = 0;
792        }
793    }
794    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
795    if (!found) {
796        assert (mBaseCodePoint == 0x110000);
797        mMaxCodePoint = 0x10FFFF;
798    }
799
800    assert (mMinCodePoint <= mMaxCodePoint);
801}
802
803/** ------------------------------------------------------------------------------------------------------------- *
804 * @brief Empty Set Constructor
805 ** ------------------------------------------------------------------------------------------------------------- */
806UnicodeSet::UnicodeSet()
807: mRuns(mAllocator)
808, mQuads(mAllocator)
809{
810    append_run(Empty, UNICODE_QUAD_COUNT, mRuns);
811    assert (verify(mRuns, mQuads));
812}
813
814/** ------------------------------------------------------------------------------------------------------------- *
815 * @brief Singleton Set Constructor
816 ** ------------------------------------------------------------------------------------------------------------- */
817UnicodeSet::UnicodeSet(const codepoint_t codepoint)
818: mRuns(mAllocator)
819, mQuads(mAllocator)
820{
821    const codepoint_t quad_no = codepoint / QUAD_BITS;
822    append_run(Empty, quad_no, mRuns);
823    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
824    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
825    assert (verify(mRuns, mQuads));
826}
827
828/** ------------------------------------------------------------------------------------------------------------- *
829 * @brief Range Set Constructor
830 ** ------------------------------------------------------------------------------------------------------------- */
831UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
832: mRuns(mAllocator)
833, mQuads(mAllocator)
834{
835    const codepoint_t lo_index = lo / QUAD_BITS;
836    const codepoint_t hi_index = hi / QUAD_BITS;
837    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
838    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
839    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
840    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
841    append_run(Empty, lo_index, mRuns);
842    bitquad_t mask = hi_quad;
843    if (lo_index == hi_index) {
844        mask &= lo_quad;
845    } else {
846        append_quad(lo_quad, mQuads, mRuns);
847        append_run(Full, hi_index - (lo_index + 1), mRuns);
848    }
849    append_quad(mask, mQuads, mRuns);
850    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
851    assert (verify(mRuns, mQuads));
852}
853
854/** ------------------------------------------------------------------------------------------------------------- *
855 * @brief Range List Set Constructor
856 ** ------------------------------------------------------------------------------------------------------------- */
857template <typename itr>
858void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
859    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
860        assert (l.first <= l.second);
861        assert (l.second < UNICODE_MAX);
862        assert (r.first <= r.second);
863        assert (r.second < UNICODE_MAX);
864        return l.second < r.first;
865    }));
866
867    std::vector<run_t> runs;
868    std::vector<bitquad_t> quads;
869
870    codepoint_t prior_index = 0;
871    bitquad_t mask = 0;
872    for (auto interval = begin; interval != end; ) {
873        codepoint_t lo, hi;
874        std::tie(lo, hi) = *interval;
875        const codepoint_t lo_index = (lo / QUAD_BITS);
876        const codepoint_t hi_index = (hi / QUAD_BITS);
877        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
878        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
879        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
880        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
881        append_run(Empty, lo_index - prior_index, runs);
882        if (lo_index == hi_index) {
883            mask |= (lo_quad & hi_quad);
884        } else {
885            append_quad(mask | lo_quad, quads, runs);
886            append_run(Full, hi_index - (lo_index + 1), runs);
887            mask = hi_quad;
888        }
889        // if the next interval is in our current quad, continue to the next range
890        prior_index = hi_index;
891        if (LLVM_LIKELY(++interval != end)) {
892            if (hi_index == (interval->first / QUAD_BITS)) {
893                continue;
894            }
895        }
896        append_quad(mask, quads, runs);
897        mask = 0;
898        ++prior_index;
899    }
900    assert (mask == 0);
901    if (prior_index < UNICODE_QUAD_COUNT) {
902        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
903    }   
904    assert (verify(runs, quads));
905    mRuns.assign(runs.begin(), runs.end());
906    mQuads.assign(quads.begin(), quads.end());
907}
908
909/** ------------------------------------------------------------------------------------------------------------- *
910 * @brief Interval Range Constructor
911 ** ------------------------------------------------------------------------------------------------------------- */
912UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
913: mRuns(0, {Empty, 0}, mAllocator)
914, mQuads(0, 0, mAllocator) {
915    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
916}
917
918/** ------------------------------------------------------------------------------------------------------------- *
919 * @brief Interval Range Constructor
920 ** ------------------------------------------------------------------------------------------------------------- */
921UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
922: mRuns(0, {Empty, 0}, mAllocator)
923, mQuads(0, 0, mAllocator) {
924    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
925}
926
927/** ------------------------------------------------------------------------------------------------------------- *
928 * @brief Copy Constructor
929 ** ------------------------------------------------------------------------------------------------------------- */
930UnicodeSet::UnicodeSet(const UnicodeSet & other)
931: mRuns(other.mRuns, mAllocator)
932, mQuads(other.mQuads, mAllocator) {
933    assert (verify(mRuns, mQuads));
934}
935
936/** ------------------------------------------------------------------------------------------------------------- *
937 * @brief Initializer Constructor
938 ** ------------------------------------------------------------------------------------------------------------- */
939UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
940: mRuns(r.begin(), r.end(), mAllocator)
941, mQuads(q.begin(), q.end(), mAllocator) {
942    assert (verify(mRuns, mQuads));
943}
944
945/** ------------------------------------------------------------------------------------------------------------- *
946 * @brief Internal Vector Constructor
947 ** ------------------------------------------------------------------------------------------------------------- */
948inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
949: mRuns(r.begin(), r.end(), mAllocator)
950, mQuads(q.begin(), q.end(), mAllocator) {
951    assert (verify(mRuns, mQuads));
952}
953
954}
Note: See TracBrowser for help on using the repository browser.