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

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

Code clean-up. Removed Pablo Call, SetIthBit? and Prototype.

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