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

Last change on this file since 5386 was 5386, checked in by nmedfort, 2 years ago

Replaced stdin input stream with mmap'ed buffer and aligned each read call to the page size.

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