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
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 dump
155 ** ------------------------------------------------------------------------------------------------------------- */
156void UnicodeSet::dump(llvm::raw_ostream & out) const {
157    auto qi = mQuads.cbegin();
158    for (const run_t & run : mRuns) {
159        if (typeOf(run) == Empty) {
160            out << "Empty(" << lengthOf(run) << ")\n";
161        }
162        else if (typeOf(run) == Full) {
163            out << "Full(" << lengthOf(run) << ")\n";
164        }
165        else {
166            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
167                assert (qi != mQuads.cend());
168                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
169            }
170        }
171    }
172}
173
174/** ------------------------------------------------------------------------------------------------------------- *
175 * @brief complement
176 ** ------------------------------------------------------------------------------------------------------------- */
177UnicodeSet UnicodeSet::operator~() const {
178    std::vector<run_t> runs;
179    std::vector<bitquad_t> quads;
180    runs.reserve(mRuns.size());
181    quads.reserve(mQuads.size());
182    auto qi = quads.cbegin();
183    for (const run_t & run : mRuns) {
184        if (typeOf(run) == Empty) {
185            append_run(Full, lengthOf(run), runs);
186        }
187        else if (typeOf(run) == Full) {
188            append_run(Empty, lengthOf(run), runs);
189        }
190        else {
191            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
192                assert (qi != quads.cend());
193                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
194            }
195        }
196    }
197    return UnicodeSet(std::move(runs), std::move(quads));
198}
199
200/** ------------------------------------------------------------------------------------------------------------- *
201 * @brief intersection
202 ** ------------------------------------------------------------------------------------------------------------- */
203UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
204    std::vector<run_t> runs;
205    std::vector<bitquad_t> quads;
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; ) {
209        const auto n = std::min(i1.length(), i2.length());
210        if ((i1.type() == Full) && (i2.type() == Full)) {
211            append_run(Full, n, runs);
212            i1 += n;
213            i2 += n;
214        }
215        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
216            append_run(Empty, n, runs);
217            i1 += n;
218            i2 += n;
219        }
220        else if (i1.type() == Full) {
221            for (unsigned i = 0; i != n; ++i, ++i2) {
222                append_quad(i2.quad(), quads, runs);
223            }
224            i1 += n;
225        }
226        else if (i2.type() == Full) {
227            for (unsigned i = 0; i != n; ++i, ++i1) {
228                append_quad(i1.quad(), quads, runs);
229            }
230            i2 += n;
231        }
232        else { //both Mixed
233            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
234                append_quad(i1.quad() & i2.quad(), quads, runs);
235            }
236        }
237    }
238    return UnicodeSet(std::move(runs), std::move(quads));
239}
240
241/** ------------------------------------------------------------------------------------------------------------- *
242 * @brief union
243 ** ------------------------------------------------------------------------------------------------------------- */
244UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
245    std::vector<run_t> runs;
246    std::vector<bitquad_t> quads;
247    const auto e1 = quad_end();
248    const auto e2 = other.quad_end();
249    auto i1 = quad_begin(), i2 = other.quad_begin();
250    for (; i1 != e1 && i2 != e2; ) {
251        const auto n = std::min(i1.length(), i2.length());
252        if ((i1.type() == Empty) && (i2.type() == Empty)) {
253            append_run(Empty, n, runs);
254            i1 += n;
255            i2 += n;
256        } else if ((i1.type() == Full) || (i2.type() == Full)) {
257            append_run(Full, n, runs);
258            i1 += n;
259            i2 += n;
260        } else if (i1.type() == Empty) {
261            for (unsigned i = 0; i != n; ++i, ++i2) {
262                append_quad(i2.quad(), quads, runs);
263            }
264            i1 += n;
265        } else if (i2.type() == Empty) {
266            for (unsigned i = 0; i != n; ++i, ++i1) {
267                append_quad(i1.quad(), quads, runs);
268            }
269            i2 += n;
270        } else {
271            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
272                append_quad(i1.quad() | i2.quad(), quads, runs);
273            }
274        }
275    }
276    return UnicodeSet(std::move(runs), std::move(quads));
277}
278
279/** ------------------------------------------------------------------------------------------------------------- *
280 * @brief difference
281 ** ------------------------------------------------------------------------------------------------------------- */
282UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
283    std::vector<run_t> runs;
284    std::vector<bitquad_t> quads;
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; ) {
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);
291            i1 += n;
292            i2 += n;
293        }
294        else if (i1.type() == Full) {
295            for (unsigned i = 0; i != n; ++i, ++i2) {
296                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
297            }
298            i1 += n;
299        }
300        else if (i2.type() == Empty) {
301            for (unsigned i = 0; i != n; ++i, ++i1) {
302                append_quad(i1.quad(), quads, runs);
303            }
304            i2 += n;
305        }
306        else {
307            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
308                append_quad(i1.quad() &~ i2.quad(), quads, runs);
309            }
310        }
311    }
312    return UnicodeSet(std::move(runs), std::move(quads));
313}
314
315/** ------------------------------------------------------------------------------------------------------------- *
316 * @brief symmetric difference
317 ** ------------------------------------------------------------------------------------------------------------- */
318UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
319    std::vector<run_t> runs;
320    std::vector<bitquad_t> quads;
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; ) {
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);
327            i1 += n;
328            i2 += n;
329        }
330        else if (i1.type() == Empty) {
331            for (unsigned i = 0; i < n; ++i, ++i2) {
332                append_quad(i2.quad(), quads, runs);
333            }
334            i1 += n;
335        }
336        else if (i2.type() == Empty) {
337            for (unsigned i = 0; i < n; ++i, ++i1) {
338                append_quad(i1.quad(), quads, runs);
339            }
340            i2 += n;
341        }
342        else if (i1.type() == Full) {
343            for (unsigned i = 0; i < n; ++i, ++i2) {
344                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
345            }
346            i1 += n;
347        }
348        else if (i2.type() == Empty) {
349            for (unsigned i = 0; i < n; ++i, ++i1) {
350                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
351            }
352            i2 += n;
353        }
354        else {
355            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
356                append_quad(i1.quad() ^ i2.quad(), quads, runs);
357            }
358        }
359    }
360    return UnicodeSet(std::move(runs), std::move(quads));
361}
362
363/** ------------------------------------------------------------------------------------------------------------- *
364 * @brief equality
365 ** ------------------------------------------------------------------------------------------------------------- */
366bool UnicodeSet::operator==(const UnicodeSet & other) const {
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
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
406/** ------------------------------------------------------------------------------------------------------------- *
407 * @brief insert
408 ** ------------------------------------------------------------------------------------------------------------- */
409void UnicodeSet::insert(const codepoint_t cp) {
410
411    if (LLVM_UNLIKELY(cp >= UNICODE_MAX)) {
412        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
413    }
414
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    }
460
461    assert (verify(mRuns, mQuads));
462    assert (contains(cp));
463}
464
465/** ------------------------------------------------------------------------------------------------------------- *
466 * @brief insert_range
467 ** ------------------------------------------------------------------------------------------------------------- */
468void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
469
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    }
475
476    //this->dump(llvm::errs()); llvm::errs() << " + [" << lo << ',' << hi << "]\n"; llvm::errs().flush();
477
478    // Create a temporary run and quad set for the given range
479    std::vector<run_t> runs;
480    std::vector<bitquad_t> quads;
481
482    codepoint_t lo_index = lo / QUAD_BITS;
483    codepoint_t hi_index = hi / QUAD_BITS;
484
485    auto ri = mRuns.cbegin();
486    auto qi = mQuads.cbegin();
487
488    length_t length = 0;
489    run_type_t type = Empty;
490
491    // Advance past any full runs prior to the lo_index
492    for (;;) {
493        assert (ri != mRuns.cend());
494        std::tie(type, length) = *ri;
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();
496        if (lo_index < length) {
497            break;
498        }
499        if (type == Mixed) {
500            assert (std::distance(qi, mQuads.cend()) >= length);
501            qi += length;
502        }
503        lo_index -= length;
504        hi_index -= length;
505        ++ri;
506    }
507
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
510    // Now record the runs and any quads prior to lo_index
511    runs.assign(mRuns.cbegin(), ri++);
512    if (lo_index) {
513        runs.push_back(std::make_pair(type, lo_index));
514        if (type == Mixed) {
515            assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) >= lo_index);
516            qi += lo_index;
517        }
518        hi_index -= lo_index;
519        length -= lo_index;
520    }
521
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)));
526
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) {
535            assert (std::distance(qi, mQuads.cend()) > 0);
536            lo_quad |= *qi++;
537        }
538        append_quad(lo_quad, quads, runs);
539    }
540    --length;
541
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
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
550        while (ri != mRuns.cend()) {
551            if (type == Mixed) {
552                assert (std::distance(qi, mQuads.cend()) >= length);
553                qi += length;
554            }
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();
557            if (hi_index < length) {
558                break;
559            }
560            hi_index -= length;
561        }
562
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) {
568                assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) > hi_index);
569                qi += hi_index;
570                hi_quad |= *qi++;
571            }
572            append_quad(hi_quad, quads, runs);
573        }
574    }
575
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
582    // And append any remaining values from the original data
583    append_run(type, length - hi_index, runs);
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());
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
593/** ------------------------------------------------------------------------------------------------------------- *
594 * @brief contains
595 * @param codepoint
596 *
597 * Return whether this UnicodeSet contains the specified code point
598 ** ------------------------------------------------------------------------------------------------------------- */
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;
610            }
611            return (t == Full);
612        }
613        if (t == Mixed) {
614            quad += l;
615        }       
616        offset -= l;
617    }
618    return false;
619}
620
621/** ------------------------------------------------------------------------------------------------------------- *
622 * @brief intersects
623 * @param lo_codepoint
624 * @param hi_codepoint
625 *
626 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
627 ** ------------------------------------------------------------------------------------------------------------- */
628bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
629    for (auto range : *this) {
630        if (range.second < lo) {
631            continue;
632        }
633        if (range.first > hi) {
634            break;
635        }
636        return true;
637    }
638    return false;
639}
640
641/** ------------------------------------------------------------------------------------------------------------- *
642 * @brief UnicodeSet::quad_iterator::advance
643 ** ------------------------------------------------------------------------------------------------------------- */
644void UnicodeSet::quad_iterator::advance(unsigned n) {
645    while (n > 0) {
646        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
647        if (remain > n) {
648            if (typeOf(*mRunIterator) == Mixed) {
649                mQuadIterator += n;
650            }
651            mOffset += n;
652            break;
653        }
654        if (typeOf(*mRunIterator) == Mixed) {
655            mQuadIterator += remain;
656        }
657        ++mRunIterator;
658        mOffset = 0;
659        n -= remain;
660    }
661}
662
663/** ------------------------------------------------------------------------------------------------------------- *
664 * @brief UnicodeSet::iterator::advance
665 ** ------------------------------------------------------------------------------------------------------------- */
666void UnicodeSet::iterator::advance(const unsigned n) {
667
668    assert (n == 1);
669
670    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
671        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
672    }
673
674    bool found = false;
675    // Find the start of our interval
676    while ( mBaseCodePoint < 0x110000 ) {
677        // Find the first non-empty block
678        if (typeOf(*mRunIterator) != Mixed) {           
679            // If we found a full run, this must be the start of our interval.
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;
686                break;
687            }
688        } else { // if (typeOf(t) == Mixed)
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) {
694                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
695                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
696                    found = true;
697                    break;
698                }
699                mBaseCodePoint += QUAD_BITS;
700                ++mQuadIterator;
701                ++mMixedRunIndex;
702                mQuadOffset = 0;
703            }
704            if (found) break;
705            ++mRunIterator;
706            mQuadOffset = 0;
707            mMixedRunIndex = 0;
708        }
709    }
710
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;
720    // Find the end of our interval
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            }
734        } else { // if (typeOf(t) == Mixed)
735            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
736                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
737
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) {
741                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
742                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
743                    found = true;
744                    break;
745                }
746                mBaseCodePoint += QUAD_BITS;
747                ++mQuadIterator;
748                ++mMixedRunIndex;
749                mQuadOffset = 0;
750            }
751            if (found) break;
752            ++mRunIterator;
753            mQuadOffset = 0;
754            mMixedRunIndex = 0;
755        }
756    }
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    }
762
763    assert (mMinCodePoint <= mMaxCodePoint);
764}
765
766/** ------------------------------------------------------------------------------------------------------------- *
767 * @brief Empty Set Constructor
768 ** ------------------------------------------------------------------------------------------------------------- */
769UnicodeSet::UnicodeSet()
770: mRuns(mAllocator)
771, mQuads(mAllocator)
772{
773    append_run(Empty, UNICODE_QUAD_COUNT, mRuns);
774    assert (verify(mRuns, mQuads));
775}
776
777/** ------------------------------------------------------------------------------------------------------------- *
778 * @brief Singleton Set Constructor
779 ** ------------------------------------------------------------------------------------------------------------- */
780UnicodeSet::UnicodeSet(const codepoint_t codepoint)
781: mRuns(mAllocator)
782, mQuads(mAllocator)
783{
784    const codepoint_t quad_no = codepoint / QUAD_BITS;
785    append_run(Empty, quad_no, mRuns);
786    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
787    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
788    assert (verify(mRuns, mQuads));
789}
790
791/** ------------------------------------------------------------------------------------------------------------- *
792 * @brief Range Set Constructor
793 ** ------------------------------------------------------------------------------------------------------------- */
794UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
795: mRuns(mAllocator)
796, mQuads(mAllocator)
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;
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));
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 {
809        append_quad(lo_quad, mQuads, mRuns);
810        append_run(Full, hi_index - (lo_index + 1), mRuns);
811    }
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;
862    }
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());
870}
871
872/** ------------------------------------------------------------------------------------------------------------- *
873 * @brief Interval Range Constructor
874 ** ------------------------------------------------------------------------------------------------------------- */
875UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
876: mRuns(0, {Empty, 0}, mAllocator)
877, mQuads(0, 0, mAllocator) {
878    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
879}
880
881/** ------------------------------------------------------------------------------------------------------------- *
882 * @brief Interval Range Constructor
883 ** ------------------------------------------------------------------------------------------------------------- */
884UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
885: mRuns(0, {Empty, 0}, mAllocator)
886, mQuads(0, 0, mAllocator) {
887    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
888}
889
890/** ------------------------------------------------------------------------------------------------------------- *
891 * @brief Copy Constructor
892 ** ------------------------------------------------------------------------------------------------------------- */
893UnicodeSet::UnicodeSet(const UnicodeSet & other)
894: mRuns(other.mRuns, mAllocator)
895, mQuads(other.mQuads, mAllocator) {
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)
903: mRuns(r.begin(), r.end(), mAllocator)
904, mQuads(q.begin(), q.end(), mAllocator) {
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)
912: mRuns(r.begin(), r.end(), mAllocator)
913, mQuads(q.begin(), q.end(), mAllocator) {
914    assert (verify(mRuns, mQuads));
915}
916
917}
Note: See TracBrowser for help on using the repository browser.