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

Last change on this file since 5620 was 5620, checked in by nmedfort, 19 months ago

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

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    //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 * @brief UnicodeSet::quad_iterator::advance
658 ** ------------------------------------------------------------------------------------------------------------- */
659void UnicodeSet::quad_iterator::advance(unsigned n) {
660    while (n > 0) {
661        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
662        if (remain > n) {
663            if (typeOf(*mRunIterator) == Mixed) {
664                mQuadIterator += n;
665            }
666            mOffset += n;
667            break;
668        }
669        if (typeOf(*mRunIterator) == Mixed) {
670            mQuadIterator += remain;
671        }
672        ++mRunIterator;
673        mOffset = 0;
674        n -= remain;
675    }
676}
677
678/** ------------------------------------------------------------------------------------------------------------- *
679 * @brief UnicodeSet::iterator::advance
680 ** ------------------------------------------------------------------------------------------------------------- */
681void UnicodeSet::iterator::advance(const unsigned n) {
682
683    assert (n == 1);
684
685    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
686        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
687    }
688
689    bool found = false;
690    // Find the start of our interval
691    while ( mBaseCodePoint < 0x110000 ) {
692        // Find the first non-empty block
693        if (typeOf(*mRunIterator) != Mixed) {           
694            // If we found a full run, this must be the start of our interval.
695            const auto baseCodePoint = mBaseCodePoint;
696            const auto type = typeOf(*mRunIterator);
697            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
698            if (type == Full) {
699                mMinCodePoint = baseCodePoint;
700                found = true;
701                break;
702            }
703        } else { // if (typeOf(t) == Mixed)
704            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
705                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
706                // If we found a marker in m, it marks the beginning of our current interval.
707                // Find it and break out of the loop.
708                if (m) {
709                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
710                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
711                    found = true;
712                    break;
713                }
714                mBaseCodePoint += QUAD_BITS;
715                ++mQuadIterator;
716                ++mMixedRunIndex;
717                mQuadOffset = 0;
718            }
719            if (found) break;
720            ++mRunIterator;
721            mQuadOffset = 0;
722            mMixedRunIndex = 0;
723        }
724    }
725
726    if (!found) {
727        assert (mBaseCodePoint == 0x110000);
728        mMinCodePoint = 0x110000;
729        return;
730    }
731
732    // at this stage, the max code point is the previous max code point (initially 0)
733    assert (mMaxCodePoint <= mMinCodePoint);
734    found = false;
735    // Find the end of our interval
736    while ( mBaseCodePoint < 0x110000 ) {
737
738        // Find the first non-Full block
739        if (typeOf(*mRunIterator) != Mixed) {
740            // If this run is Empty, the max code point is the last computed base code point - 1.
741            const auto baseCodePoint = mBaseCodePoint;
742            const auto type = typeOf(*mRunIterator);
743            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
744            if (type == Empty) {
745                mMaxCodePoint = baseCodePoint - 1;
746                found = true;
747                break;
748            }
749        } else { // if (typeOf(t) == Mixed)
750            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
751                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
752
753                // If we found a marker in m, it marks the end of our current interval.
754                // Find it and break out of the loop.
755                if (m) {
756                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
757                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
758                    found = true;
759                    break;
760                }
761                mBaseCodePoint += QUAD_BITS;
762                ++mQuadIterator;
763                ++mMixedRunIndex;
764                mQuadOffset = 0;
765            }
766            if (found) break;
767            ++mRunIterator;
768            mQuadOffset = 0;
769            mMixedRunIndex = 0;
770        }
771    }
772    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
773    if (!found) {
774        assert (mBaseCodePoint == 0x110000);
775        mMaxCodePoint = 0x10FFFF;
776    }
777
778    assert (mMinCodePoint <= mMaxCodePoint);
779}
780
781/** ------------------------------------------------------------------------------------------------------------- *
782 * @brief Empty Set Constructor
783 ** ------------------------------------------------------------------------------------------------------------- */
784UnicodeSet::UnicodeSet()
785: mRuns(mAllocator)
786, mQuads(mAllocator)
787{
788    append_run(Empty, UNICODE_QUAD_COUNT, mRuns);
789    assert (verify(mRuns, mQuads));
790}
791
792/** ------------------------------------------------------------------------------------------------------------- *
793 * @brief Singleton Set Constructor
794 ** ------------------------------------------------------------------------------------------------------------- */
795UnicodeSet::UnicodeSet(const codepoint_t codepoint)
796: mRuns(mAllocator)
797, mQuads(mAllocator)
798{
799    const codepoint_t quad_no = codepoint / QUAD_BITS;
800    append_run(Empty, quad_no, mRuns);
801    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
802    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
803    assert (verify(mRuns, mQuads));
804}
805
806/** ------------------------------------------------------------------------------------------------------------- *
807 * @brief Range Set Constructor
808 ** ------------------------------------------------------------------------------------------------------------- */
809UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
810: mRuns(mAllocator)
811, mQuads(mAllocator)
812{
813    const codepoint_t lo_index = lo / QUAD_BITS;
814    const codepoint_t hi_index = hi / QUAD_BITS;
815    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
816    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
817    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
818    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
819    append_run(Empty, lo_index, mRuns);
820    bitquad_t mask = hi_quad;
821    if (lo_index == hi_index) {
822        mask &= lo_quad;
823    } else {
824        append_quad(lo_quad, mQuads, mRuns);
825        append_run(Full, hi_index - (lo_index + 1), mRuns);
826    }
827    append_quad(mask, mQuads, mRuns);
828    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
829    assert (verify(mRuns, mQuads));
830}
831
832/** ------------------------------------------------------------------------------------------------------------- *
833 * @brief Range List Set Constructor
834 ** ------------------------------------------------------------------------------------------------------------- */
835template <typename itr>
836void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
837    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
838        assert (l.first <= l.second);
839        assert (l.second < UNICODE_MAX);
840        assert (r.first <= r.second);
841        assert (r.second < UNICODE_MAX);
842        return l.second < r.first;
843    }));
844
845    std::vector<run_t> runs;
846    std::vector<bitquad_t> quads;
847
848    codepoint_t prior_index = 0;
849    bitquad_t mask = 0;
850    for (auto interval = begin; interval != end; ) {
851        codepoint_t lo, hi;
852        std::tie(lo, hi) = *interval;
853        const codepoint_t lo_index = (lo / QUAD_BITS);
854        const codepoint_t hi_index = (hi / QUAD_BITS);
855        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
856        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
857        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
858        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
859        append_run(Empty, lo_index - prior_index, runs);
860        if (lo_index == hi_index) {
861            mask |= (lo_quad & hi_quad);
862        } else {
863            append_quad(mask | lo_quad, quads, runs);
864            append_run(Full, hi_index - (lo_index + 1), runs);
865            mask = hi_quad;
866        }
867        // if the next interval is in our current quad, continue to the next range
868        prior_index = hi_index;
869        if (LLVM_LIKELY(++interval != end)) {
870            if (hi_index == (interval->first / QUAD_BITS)) {
871                continue;
872            }
873        }
874        append_quad(mask, quads, runs);
875        mask = 0;
876        ++prior_index;
877    }
878    assert (mask == 0);
879    if (prior_index < UNICODE_QUAD_COUNT) {
880        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
881    }   
882    assert (verify(runs, quads));
883    mRuns.assign(runs.begin(), runs.end());
884    mQuads.assign(quads.begin(), quads.end());
885}
886
887/** ------------------------------------------------------------------------------------------------------------- *
888 * @brief Interval Range Constructor
889 ** ------------------------------------------------------------------------------------------------------------- */
890UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
891: mRuns(0, {Empty, 0}, mAllocator)
892, mQuads(0, 0, mAllocator) {
893    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
894}
895
896/** ------------------------------------------------------------------------------------------------------------- *
897 * @brief Interval Range Constructor
898 ** ------------------------------------------------------------------------------------------------------------- */
899UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
900: mRuns(0, {Empty, 0}, mAllocator)
901, mQuads(0, 0, mAllocator) {
902    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
903}
904
905/** ------------------------------------------------------------------------------------------------------------- *
906 * @brief Copy Constructor
907 ** ------------------------------------------------------------------------------------------------------------- */
908UnicodeSet::UnicodeSet(const UnicodeSet & other)
909: mRuns(other.mRuns, mAllocator)
910, mQuads(other.mQuads, mAllocator) {
911    assert (verify(mRuns, mQuads));
912}
913
914/** ------------------------------------------------------------------------------------------------------------- *
915 * @brief Initializer Constructor
916 ** ------------------------------------------------------------------------------------------------------------- */
917UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
918: mRuns(r.begin(), r.end(), mAllocator)
919, mQuads(q.begin(), q.end(), mAllocator) {
920    assert (verify(mRuns, mQuads));
921}
922
923/** ------------------------------------------------------------------------------------------------------------- *
924 * @brief Internal Vector Constructor
925 ** ------------------------------------------------------------------------------------------------------------- */
926inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
927: mRuns(r.begin(), r.end(), mAllocator)
928, mQuads(q.begin(), q.end(), mAllocator) {
929    assert (verify(mRuns, mQuads));
930}
931
932}
Note: See TracBrowser for help on using the repository browser.