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

Last change on this file since 5765 was 5755, checked in by nmedfort, 20 months ago

Bug fixes and simplified MultiBlockKernel? logic

File size: 58.2 KB
Line 
1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
23#include <llvm/Support/raw_ostream.h>
24#include <llvm/Support/Format.h>
25#include <llvm/ADT/SmallVector.h>
26
27namespace UCD {
28
29using bitquad_t = UnicodeSet::bitquad_t;
30using run_t = UnicodeSet::run_t;
31
32//
33// Select the correct built-in scan function, dependent on whatever
34// bitquad_t resolves to, when scan_forward_zeroes<bitquad_t> is called.
35template <typename T> int scan_forward_zeroes(const T x) noexcept;
36template <> inline int scan_forward_zeroes<unsigned int>(const unsigned int x) noexcept { return __builtin_ctz(x); }
37template <> inline int scan_forward_zeroes<unsigned long>(const unsigned long x) noexcept { return __builtin_ctzl(x); }
38template <> inline int scan_forward_zeroes<unsigned long long>(const unsigned long long x) noexcept { return __builtin_ctzll(x); }
39
40template <typename T> unsigned popcount(const T x) noexcept;
41template <> inline unsigned popcount<unsigned int>(const unsigned int x) noexcept { return __builtin_popcount(x); }
42template <> inline unsigned popcount<unsigned long>(const unsigned long x) noexcept { return __builtin_popcountl(x); }
43template <> inline unsigned popcount<unsigned long long>(const unsigned long long x) noexcept { return __builtin_popcountll(x); }
44
45
46SlabAllocator<> UnicodeSet::GlobalAllocator;
47
48const auto QUAD_BITS = (8 * sizeof(bitquad_t));
49const auto QUAD_LIMIT = (QUAD_BITS - 1);
50const auto UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
51const bitquad_t FULL_QUAD_MASK = ~static_cast<bitquad_t>(0);
52
53inline run_type_t typeOf(const run_t & run) {
54    return run.first;
55}
56
57inline UnicodeSet::length_t lengthOf(const run_t & run) {
58    return run.second;
59}
60
61template<typename T>
62T * copyOf(const T * base, const uint32_t length, SlabAllocator<> & allocator) {
63    T * const ptr = allocator.allocate<T>(length);
64    std::memcpy(ptr, base, length * sizeof(T));
65    return ptr;
66}
67
68using RunVector = llvm::SmallVector<run_t, 32>;
69using QuadVector = llvm::SmallVector<bitquad_t, 32>;
70
71template<typename RunVector, typename QuadVector>
72void assign(UnicodeSet * const self, const RunVector & runs, const QuadVector & quads) noexcept {
73    assert (verify(runs.data(), runs.size(), quads.data(), quads.size()));
74    const unsigned n = runs.size();
75    assert (n > 0 && n < UNICODE_QUAD_COUNT);
76    if (self->mRunCapacity < n) {
77        UnicodeSet::GlobalAllocator.deallocate<run_t>(self->mRuns, self->mRunCapacity);
78        self->mRuns = UnicodeSet::GlobalAllocator.allocate<run_t>(n);
79        self->mRunCapacity = n;
80    }
81    std::memcpy(self->mRuns, runs.data(), n * sizeof(run_t));
82    self->mRunLength = n;
83    const unsigned m = quads.size();
84    assert (m < UNICODE_QUAD_COUNT);
85    if (m > 0) {
86        if (self->mQuadCapacity < m) {
87            UnicodeSet::GlobalAllocator.deallocate<bitquad_t>(self->mQuads, self->mQuadCapacity);
88            self->mQuads = UnicodeSet::GlobalAllocator.allocate<bitquad_t>(m);
89            self->mQuadCapacity = m;
90        }
91        std::memcpy(self->mQuads, quads.data(), m * sizeof(bitquad_t));
92    }
93    self->mQuadLength = m;
94}
95
96using namespace llvm;
97
98/** ------------------------------------------------------------------------------------------------------------- *
99 * @brief append_run
100 ** ------------------------------------------------------------------------------------------------------------- */
101inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) noexcept {
102    if (LLVM_UNLIKELY(length == 0)) {
103        return;
104    } else if (!runs.empty() && typeOf(runs.back()) == type) {
105        std::get<1>(runs.back()) += length;
106        return;
107    }
108    runs.emplace_back(type, length);
109}
110
111/** ------------------------------------------------------------------------------------------------------------- *
112 * @brief append_quad
113 ** ------------------------------------------------------------------------------------------------------------- */
114inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) noexcept {
115    run_type_t type = Empty;
116    if (LLVM_UNLIKELY(quad == 0)) {
117        type = Empty;
118    } else if (LLVM_UNLIKELY(~quad == 0)) {
119        type = Full;
120    } else {
121        quads.emplace_back(quad);
122        type = Mixed;
123    }
124    append_run(type, 1, runs);
125}
126
127#ifndef NDEBUG
128/** ------------------------------------------------------------------------------------------------------------- *
129 * @brief verify
130 *
131 * Sanity check for each function that constructs or modifies a UnicodeSet
132 ** ------------------------------------------------------------------------------------------------------------- */
133inline bool verify(const run_t * const runs, const uint32_t runLength, const bitquad_t * const quads, const uint32_t quadLength) noexcept {
134    unsigned sum = 0;
135    unsigned mixedQuads = 0;
136    for (unsigned i = 0; i < runLength; ++i) {
137        const auto type = typeOf(runs[i]);
138        if (LLVM_UNLIKELY(type != Empty && type != Mixed && type != Full)) {
139            llvm::errs() << "illegal run type " << type << " found\n";
140            return false;
141        }
142        const auto l = lengthOf(runs[i]);
143        if (LLVM_UNLIKELY(l == 0)) {
144            llvm::errs() << "zero-length quad found\n";
145            return false;
146        }
147        if (type == Mixed) {
148            mixedQuads += l;
149        }
150        sum += l;
151    }
152    if (LLVM_UNLIKELY(sum != UNICODE_QUAD_COUNT)) {
153        llvm::errs() << "found " << sum << " quads but expected " << UNICODE_QUAD_COUNT << "\n";
154        return false;
155    }
156    if (LLVM_UNLIKELY(mixedQuads != quadLength)) {
157        llvm::errs() << "found " << quadLength << " mixed quad(s) but expected " << mixedQuads << "\n";
158        return false;
159    }
160    for (unsigned i = 0; i < quadLength; ++i) {
161        if (LLVM_UNLIKELY((quads[i] == 0) || (~quads[i] == 0))) {
162            llvm::errs() << "Empty or Full quad found in Mixed quad array\n";
163            return false;
164        }
165    }
166    return true;
167}
168#endif
169
170/** ------------------------------------------------------------------------------------------------------------- *
171 * @brief at
172 ** ------------------------------------------------------------------------------------------------------------- */
173codepoint_t UnicodeSet::at(const size_type k) const {
174
175    size_type base = 0;
176    size_type remaining = k;
177    const bitquad_t * qi = mQuads;
178
179    for (unsigned i = 0; i < mRunLength; ++i) {
180        assert ((base % QUAD_BITS) == 0);
181        const auto & r = mRuns[i];
182        if (typeOf(r) == Empty) {
183            base += lengthOf(r) * QUAD_BITS;
184        } else if (typeOf(r) == Full) {
185            const auto m = lengthOf(r) * QUAD_BITS;
186            if (LLVM_UNLIKELY(remaining < m)) {
187                return (base * QUAD_BITS) + remaining;
188            }
189            base += m;
190            remaining -= m * QUAD_BITS;
191        } else { // if (typeOf(r) == Mixed) {
192            for (auto l = lengthOf(r); l; --l, ++qi) {
193                auto q = *qi; assert (q);
194                const auto c = popcount<bitquad_t>(q);
195                if (LLVM_UNLIKELY(remaining < c)) {
196                    // iterate through the remaining bits to find the offset
197                    for (;;) {
198                        assert (q);
199                        const bitquad_t k = scan_forward_zeroes<bitquad_t>(q);
200                        if (remaining == 0) {
201                            return (base * QUAD_BITS) + k;
202                        }
203                        q ^= static_cast<bitquad_t>(1) << k;
204                        --remaining;
205                    }
206                }
207                ++base;
208                remaining -= c;
209            }
210        }
211    }
212    throw std::runtime_error("cannot retrieve codepoint " + std::to_string(k) + " from a "
213                             " set containing " + std::to_string(count()) + " codepoints");
214}
215
216/** ------------------------------------------------------------------------------------------------------------- *
217 * @brief size
218 ** ------------------------------------------------------------------------------------------------------------- */
219UnicodeSet::size_type UnicodeSet::size() const noexcept {
220    return std::distance(begin(), end());
221}
222
223/** ------------------------------------------------------------------------------------------------------------- *
224 * @brief count
225 ** ------------------------------------------------------------------------------------------------------------- */
226UnicodeSet::size_type UnicodeSet::count() const noexcept {
227    size_type count = 0;
228    for (unsigned i = 0; i < mRunLength; ++i) {
229        const auto & r = mRuns[i];
230        if (typeOf(r) == Full) {
231            assert (lengthOf(r) > 0);
232            count += lengthOf(r);
233        }
234    }
235    count *= QUAD_BITS;
236    for (unsigned i = 0; i < mQuadLength; ++i) {
237        assert (mQuads[i]);
238        count += popcount<bitquad_t>(mQuads[i]);
239    }
240    return count;
241}
242
243/** ------------------------------------------------------------------------------------------------------------- *
244 * @brief front
245 ** ------------------------------------------------------------------------------------------------------------- */
246interval_t UnicodeSet::front() const noexcept {
247    return *begin();
248}
249
250/** ------------------------------------------------------------------------------------------------------------- *
251 * @brief back
252 ** ------------------------------------------------------------------------------------------------------------- */
253interval_t UnicodeSet::back() const noexcept {
254    auto back = begin();
255    for (auto i = back; i != end(); back = i++);
256    return *back;
257}
258
259/** ------------------------------------------------------------------------------------------------------------- *
260 * @brief print
261 ** ------------------------------------------------------------------------------------------------------------- */
262void UnicodeSet::print(llvm::raw_ostream & out) const noexcept {
263    if (LLVM_UNLIKELY(empty())) {
264        out << "()";
265    } else {
266        char joiner = '(';
267        for (auto r : *this) {
268            out << joiner << std::get<0>(r);
269            if (std::get<0>(r) != std::get<1>(r)) {
270                out << '-' << std::get<1>(r);
271            }
272            joiner = ',';
273        }
274        out << ')';
275
276    }
277}
278
279/** ------------------------------------------------------------------------------------------------------------- *
280 * @brief dump
281 ** ------------------------------------------------------------------------------------------------------------- */
282void UnicodeSet::dump(llvm::raw_ostream & out) const noexcept {
283    auto qi = mQuads;
284    for (unsigned i = 0; i < mRunLength; ++i) {
285        const auto & run = mRuns[i];
286        const auto l = lengthOf(run);
287        if (typeOf(run) == Empty) {
288            out << "Empty(" << l << ")\n";
289        } else if (typeOf(run) == Full) {
290            out << "Full(" << l << ")\n";
291        } else {
292            for (const auto qi_end = qi + l; qi != qi_end; ++qi) {
293                assert (qi != (mQuads + mQuadLength));
294                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
295            }
296        }
297    }
298}
299
300/** ------------------------------------------------------------------------------------------------------------- *
301 * @brief complement
302 ** ------------------------------------------------------------------------------------------------------------- */
303UnicodeSet UnicodeSet::operator~() const noexcept {
304    run_t * const runs = GlobalAllocator.allocate<run_t>(mRunLength);
305    run_t * ri = runs;
306    for (unsigned i = 0; i < mRunLength; ++i) {
307        const auto & run = mRuns[i];
308        run_type_t type = Mixed;
309        if (typeOf(run) == Empty) {           
310            type = Full;
311        } else if (typeOf(run) == Full) {
312            type = Empty;
313        }
314        *ri++ = { type, lengthOf(run) };
315    }
316    bitquad_t * quads = nullptr;
317    if (mQuadLength > 0) {
318        quads = GlobalAllocator.allocate<bitquad_t>(mQuadLength);
319        bitquad_t * qi = quads;
320        for (unsigned i = 0; i < mQuadLength; ++i) {
321            *qi++ = ~mQuads[i];
322        }
323    }
324    return UnicodeSet(runs, mRunLength, mRunLength, quads, mQuadLength, mQuadLength);
325}
326
327/** ------------------------------------------------------------------------------------------------------------- *
328 * @brief intersection
329 ** ------------------------------------------------------------------------------------------------------------- */
330UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const noexcept {
331    RunVector runs;
332    QuadVector quads;
333    auto i1 = quad_begin(), i2 = other.quad_begin();   
334    for (;;) {
335        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
336        const auto n = std::min(i1.length(), i2.length());
337        if (LLVM_UNLIKELY(n == 0)) {
338            break;
339        }
340        if ((i1.type() == Full) && (i2.type() == Full)) {
341            append_run(Full, n, runs);
342            i1 += n;
343            i2 += n;
344        } else if ((i1.type() == Empty) || (i2.type() == Empty)) {
345            append_run(Empty, n, runs);
346            i1 += n;
347            i2 += n;
348        } else if (i1.type() == Full) {
349            for (unsigned i = 0; i != n; ++i, ++i2) {
350                append_quad(i2.quad(), quads, runs);
351            }
352            i1 += n;
353        } else if (i2.type() == Full) {
354            for (unsigned i = 0; i != n; ++i, ++i1) {
355                append_quad(i1.quad(), quads, runs);
356            }
357            i2 += n;
358        } else { // both Mixed
359            assert (i1.type() == Mixed && i2.type() == Mixed);
360            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
361                append_quad(i1.quad() & i2.quad(), quads, runs);
362            }
363        }
364    }
365    assert (i1 == quad_end() && i2 == other.quad_end());
366    const auto runsLength = runs.size();
367    const auto runsCopy = copyOf<run_t>(runs.data(), runsLength, GlobalAllocator);
368    const auto quadsLength = quads.size();
369    const auto quadsCopy = quadsLength ? copyOf<bitquad_t>(quads.data(), quadsLength, GlobalAllocator) : nullptr;
370    return UnicodeSet(runsCopy, runsLength, runsLength, quadsCopy, quadsLength, quadsLength);
371}
372
373/** ------------------------------------------------------------------------------------------------------------- *
374 * @brief union
375 ** ------------------------------------------------------------------------------------------------------------- */
376UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const noexcept {
377    RunVector runs;
378    QuadVector quads;
379    auto i1 = quad_begin(), i2 = other.quad_begin();
380    for (;;) {
381        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
382        const auto n = std::min(i1.length(), i2.length());
383        if (LLVM_UNLIKELY(n == 0)) {
384            break;
385        }
386        if ((i1.type() == Empty) && (i2.type() == Empty)) {
387            append_run(Empty, n, runs);
388            i1 += n;
389            i2 += n;
390        } else if ((i1.type() == Full) || (i2.type() == Full)) {
391            append_run(Full, n, runs);
392            i1 += n;
393            i2 += n;
394        } else if (i1.type() == Empty) {
395            assert (i2.type() == Mixed);
396            for (unsigned i = 0; i != n; ++i, ++i2) {
397                append_quad(i2.quad(), quads, runs);
398            }
399            i1 += n;
400        } else if (i2.type() == Empty) {
401            assert (i1.type() == Mixed);
402            for (unsigned i = 0; i != n; ++i, ++i1) {
403                append_quad(i1.quad(), quads, runs);
404            }
405            i2 += n;
406        } else { // both Mixed
407            assert (i1.type() == Mixed && i2.type() == Mixed);
408            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
409                append_quad(i1.quad() | i2.quad(), quads, runs);
410            }
411        }
412    }
413    assert (i1 == quad_end() && i2 == other.quad_end());
414    const auto runsLength = runs.size();
415    const auto runsCopy = copyOf<run_t>(runs.data(), runsLength, GlobalAllocator);
416    const auto quadsLength = quads.size();
417    const auto quadsCopy = quadsLength ? copyOf<bitquad_t>(quads.data(), quadsLength, GlobalAllocator) : nullptr;
418    return UnicodeSet(runsCopy, runsLength, runsLength, quadsCopy, quadsLength, quadsLength);
419}
420
421/** ------------------------------------------------------------------------------------------------------------- *
422 * @brief difference
423 ** ------------------------------------------------------------------------------------------------------------- */
424UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const noexcept {
425    RunVector runs;
426    QuadVector quads;
427    auto i1 = quad_begin(), i2 = other.quad_begin();
428    for (;;) {
429        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
430        const auto n = std::min(i1.length(), i2.length());
431        if (LLVM_UNLIKELY(n == 0)) {
432            break;
433        }
434        if ((i1.type() == Empty) || (i2.type() == Full)) {           
435            append_run(Empty, n, runs);
436            i1 += n;
437            i2 += n;
438        } else if (i1.type() == Full) {
439            if (i2.type() == Empty) {
440                append_run(Full, n, runs);
441                i2 += n;
442            } else {
443                for (unsigned i = 0; i != n; ++i, ++i2) {
444                    append_quad(~i2.quad(), quads, runs);
445                }               
446            }
447            i1 += n;
448        } else if (i2.type() == Empty) {
449            for (unsigned i = 0; i != n; ++i, ++i1) {               
450                append_quad(i1.quad(), quads, runs);
451            }
452            i2 += n;
453        } else { // both Mixed
454            assert (i1.type() == Mixed && i2.type() == Mixed);
455            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {               
456                append_quad(i1.quad() &~ i2.quad(), quads, runs);
457            }
458        }
459    }
460    assert (i1 == quad_end() && i2 == other.quad_end());
461    const auto runsLength = runs.size();
462    const auto runsCopy = copyOf<run_t>(runs.data(), runsLength, GlobalAllocator);
463    const auto quadsLength = quads.size();
464    const auto quadsCopy = quadsLength ? copyOf<bitquad_t>(quads.data(), quadsLength, GlobalAllocator) : nullptr;
465    return UnicodeSet(runsCopy, runsLength, runsLength, quadsCopy, quadsLength, quadsLength);
466}
467
468/** ------------------------------------------------------------------------------------------------------------- *
469 * @brief symmetric difference
470 ** ------------------------------------------------------------------------------------------------------------- */
471UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const noexcept {
472    RunVector runs;
473    QuadVector quads;
474    auto i1 = quad_begin(), i2 = other.quad_begin();
475    for (;;) {
476        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
477        const auto n = std::min(i1.length(), i2.length());
478        if (LLVM_UNLIKELY(n == 0)) {
479            break;
480        }
481        if (i1.type() != Mixed && i2.type() != Mixed) {
482            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
483            i1 += n;
484            i2 += n;
485        } else if (i1.type() == Empty) {
486            for (unsigned i = 0; i < n; ++i, ++i2) {
487                append_quad(i2.quad(), quads, runs);
488            }
489            i1 += n;
490        } else if (i2.type() == Empty) {
491            for (unsigned i = 0; i < n; ++i, ++i1) {
492                append_quad(i1.quad(), quads, runs);
493            }
494            i2 += n;
495        } else if (i1.type() == Full) {
496            for (unsigned i = 0; i < n; ++i, ++i2) {
497                append_quad(~i2.quad(), quads, runs);
498            }
499            i1 += n;
500        } else if (i2.type() == Full) {
501            for (unsigned i = 0; i < n; ++i, ++i1) {
502                append_quad(~i1.quad(), quads, runs);
503            }
504            i2 += n;
505        } else { // both Mixed
506            assert (i1.type() == Mixed && i2.type() == Mixed);
507            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
508                append_quad(i1.quad() ^ i2.quad(), quads, runs);
509            }
510        }
511    }
512    assert (i1 == quad_end() && i2 == other.quad_end());
513    const auto runsLength = runs.size();
514    const auto runsCopy = copyOf<run_t>(runs.data(), runsLength, GlobalAllocator);
515    const auto quadsLength = quads.size();
516    const auto quadsCopy = quadsLength ? copyOf<bitquad_t>(quads.data(), quadsLength, GlobalAllocator) : nullptr;
517    return UnicodeSet(runsCopy, runsLength, runsLength, quadsCopy, quadsLength, quadsLength);
518}
519
520/** ------------------------------------------------------------------------------------------------------------- *
521 * @brief equality
522 ** ------------------------------------------------------------------------------------------------------------- */
523bool UnicodeSet::operator==(const UnicodeSet & other) const noexcept {
524    if (LLVM_LIKELY(mRunLength != other.mRunLength || mQuadLength != other.mQuadLength)) {
525        return false;
526    }
527    for (unsigned i = 0; i < mQuadLength; ++i) {
528        if (mQuads[i] != other.mQuads[i]) {
529            return false;
530        }
531    }
532    for (unsigned i = 0; i < mRunLength; ++i) {
533        if (mRuns[i] != other.mRuns[i]) {
534            return false;
535        }
536    }
537    return true;
538}
539
540/** ------------------------------------------------------------------------------------------------------------- *
541 * @brief less operator
542 ** ------------------------------------------------------------------------------------------------------------- */
543bool UnicodeSet::operator<(const UnicodeSet & other) const noexcept {
544    if (LLVM_LIKELY(mRunLength != other.mRunLength)) {
545        return mRunLength < other.mRunLength;
546    } else if (LLVM_LIKELY(mQuadLength != other.mQuadLength)) {
547        return (mQuadLength < other.mQuadLength);
548    } else { // equal run and quad lengths; test their individual values
549        for (unsigned i = 0; i < mRunLength; ++i) {
550            if (mRuns[i] < other.mRuns[i]) {
551                return true;
552            } else if (mRuns[i] > other.mRuns[i]) {
553                return false;
554            }
555        }
556        for (unsigned i = 0; i < mQuadLength; ++i) {
557            if (mQuads[i] < other.mQuads[i]) {
558                return true;
559            } else if (mQuads[i] > other.mQuads[i]) {
560                return false;
561            }
562        }
563        return false;
564    }
565}
566
567/** ------------------------------------------------------------------------------------------------------------- *
568 * @brief insert
569 ** ------------------------------------------------------------------------------------------------------------- */
570void UnicodeSet::insert(const codepoint_t cp) {
571
572    if (LLVM_UNLIKELY(cp > UNICODE_MAX)) {
573        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
574    }
575
576    codepoint_t offset = cp / QUAD_BITS;
577    const bitquad_t value = static_cast<bitquad_t>(1) << (cp & QUAD_LIMIT);
578
579    unsigned runIndex = 0;
580    unsigned quadIndex = 0;
581
582    length_t length = 0;
583    run_type_t type = Empty;
584    for (;;) {
585        std::tie(type, length) = mRuns[runIndex];
586        if (offset < length) {
587            break;
588        }
589        if (type == Mixed) {
590            quadIndex += length;
591        }
592        offset -= length;
593        ++runIndex;
594    }
595
596    if (LLVM_LIKELY(type == Mixed)) {       
597        quadIndex += offset;
598        if (LLVM_UNLIKELY(mQuadCapacity == 0)) {
599            bitquad_t * const quads = GlobalAllocator.allocate<bitquad_t>(mQuadLength - 1);
600            std::memcpy(quads, mQuads, (quadIndex - 1) * sizeof(bitquad_t));
601            quads[quadIndex] = mQuads[quadIndex] | value;
602            const unsigned offset = (~quads[quadIndex] == 0) ? 1 : 0;
603            mQuadCapacity = mQuadLength;
604            mQuadLength -= offset;
605            ++quadIndex;
606            std::memcpy(quads + quadIndex, mQuads + quadIndex + offset, (mQuadLength - quadIndex) * sizeof(bitquad_t));
607            mQuads = quads;
608            if (LLVM_LIKELY(offset == 0)) {  // no change to runs needed
609                assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
610                assert (contains(cp));
611                return;
612            }
613
614        } else { // reuse the buffer
615            mQuads[quadIndex] |= value;
616            if (LLVM_LIKELY(~mQuads[quadIndex] != 0)) { // no change to runs needed
617                assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
618                assert (contains(cp));
619                return;
620            }
621            --mQuadLength;
622            ++quadIndex;
623            std::memmove(mQuads + quadIndex, mQuads + quadIndex + 1, (mQuadLength - quadIndex) * sizeof(bitquad_t));
624        }
625
626    } else if (type == Empty) {
627        // insert a new quad
628        const auto l = mQuadLength + 1;
629        if (l > mQuadCapacity) {
630            bitquad_t * const quads = GlobalAllocator.allocate<bitquad_t>(l);
631            std::memcpy(quads, mQuads, quadIndex * sizeof(bitquad_t));
632            quads[quadIndex] = value;
633            std::memcpy(quads + quadIndex + 1, mQuads + quadIndex, (mQuadLength - quadIndex) * sizeof(bitquad_t));
634            GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
635            mQuads = quads;
636            mQuadCapacity = l;
637        } else { // reuse the same buffer
638            std::memmove(mQuads + quadIndex + 1, mQuads + quadIndex, (mQuadLength - quadIndex) * sizeof(bitquad_t));
639            mQuads[quadIndex] = value;
640        }
641        mQuadLength = l;
642    } else { // if (t == Full) {
643        assert (contains(cp));
644        return;
645    }
646
647    if (LLVM_UNLIKELY(length == 1 && mRunCapacity != 0)) { // are we overwriting a 1-length run?
648        std::get<0>(mRuns[runIndex]) = (type == Empty) ? Mixed : Full;
649    } else {
650        const unsigned remaining = length - (offset + 1);
651        const auto m = (offset && remaining) ? 2 : 1; // splitting the run in the middle?
652        const auto l = mRunLength + m;
653        const auto k = runIndex + ((offset != 0) ? 1 : 0);
654        if (l > mRunCapacity) {
655            run_t * const newRun = GlobalAllocator.allocate<run_t>(l);
656            std::memcpy(newRun, mRuns, k * sizeof(run_t));
657            std::memcpy(newRun + k + m, mRuns + k, (mRunLength - k) * sizeof(run_t));
658            GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
659            mRuns = newRun;
660            mRunCapacity = l;
661        } else { // reuse the same buffer
662            std::memmove(mRuns + k + m, mRuns + k, (mRunLength - k) * sizeof(run_t));
663        }
664        mRuns[k] = std::make_pair(type == Empty ? Mixed : Full, 1);
665        if (offset) {
666            mRuns[k - 1] = std::make_pair(type, offset);
667        }
668        if (remaining) {
669            mRuns[k + 1] = std::make_pair(type, remaining);
670        }
671        mRunLength = l;
672    }
673    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
674    assert (contains(cp));
675}
676
677/** ------------------------------------------------------------------------------------------------------------- *
678 * @brief insert
679 ** ------------------------------------------------------------------------------------------------------------- */
680void UnicodeSet::insert(const UnicodeSet & other) noexcept {
681    RunVector runs;
682    QuadVector quads;
683    auto i1 = quad_begin(), i2 = other.quad_begin();
684    bool changed = false;
685    for (;;) {
686        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
687        const auto n = std::min(i1.length(), i2.length());
688        if (LLVM_UNLIKELY(n == 0)) {
689            break;
690        }
691        if ((i1.type() == Empty) && (i2.type() == Empty)) {
692            append_run(Empty, n, runs);
693            i1 += n;
694            i2 += n;
695        } else if ((i1.type() == Full) || (i2.type() == Full)) {
696            changed |= (i1.type() != Full);
697            append_run(Full, n, runs);
698            i1 += n;
699            i2 += n;
700        } else if (i1.type() == Empty) {
701            assert (i2.type() == Mixed);
702            changed = true;
703            for (unsigned i = 0; i != n; ++i, ++i2) {
704                append_quad(i2.quad(), quads, runs);
705            }
706            i1 += n;
707        } else if (i2.type() == Empty) {
708            assert (i1.type() == Mixed);
709            for (unsigned i = 0; i != n; ++i, ++i1) {
710                append_quad(i1.quad(), quads, runs);
711            }
712            i2 += n;
713        } else { // both Mixed
714            assert (i1.type() == Mixed && i2.type() == Mixed);
715            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
716                changed |= (i2.quad() &~ i1.quad());
717                append_quad(i1.quad() | i2.quad(), quads, runs);
718            }
719        }
720    }
721    assert (i1 == quad_end() && i2 == other.quad_end());
722    if (LLVM_LIKELY(changed)) {
723        assign(this, runs, quads);
724    }
725}
726
727/** ------------------------------------------------------------------------------------------------------------- *
728 * @brief invert
729 ** ------------------------------------------------------------------------------------------------------------- */
730void UnicodeSet::invert() noexcept {
731
732    if (LLVM_UNLIKELY(mRunCapacity == 0)) {
733        run_t * const runs = GlobalAllocator.allocate<run_t>(mRunLength);
734        for (unsigned i = 0; i < mRunLength; ++i) {
735            auto & run = mRuns[i];
736            const auto l = lengthOf(run);
737            if (typeOf(run) == Empty) {
738                runs[i] = std::make_pair(Full, l);
739            } else if (typeOf(run) == Full) {
740                runs[i] = std::make_pair(Empty, l);
741            } else {
742                runs[i] = std::make_pair(Mixed, l);
743            }
744        }
745        mRuns = runs;
746        mRunCapacity = mRunLength;
747    } else {
748        for (unsigned i = 0; i < mRunLength; ++i) {
749            auto & run = mRuns[i];
750            if (typeOf(run) == Empty) {
751                std::get<0>(run) = Full;
752            } else if (typeOf(run) == Full) {
753                std::get<0>(run) = Empty;
754            }
755        }
756    }
757
758    if (mQuadLength) {
759        if (mQuadCapacity == 0) {
760            bitquad_t * const quads = GlobalAllocator.allocate<bitquad_t>(mQuadLength);
761            for (unsigned i = 0; i != mQuadLength; ++i) {
762                quads[i] = ~mQuads[i];
763            }
764            mQuads = quads;
765            mQuadCapacity = mQuadLength;
766        } else {
767            for (unsigned i = 0; i != mQuadLength; ++i) {
768                mQuads[i] = ~mQuads[i];
769            }
770        }
771    }
772
773}
774
775/** ------------------------------------------------------------------------------------------------------------- *
776 * @brief insert_range
777 ** ------------------------------------------------------------------------------------------------------------- */
778void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi) {
779
780    if (LLVM_UNLIKELY(lo > hi)) {
781        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
782    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
783        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
784    }
785
786    // Create a temporary run and quad set for the given range
787    RunVector runs;
788    QuadVector quads;
789
790    codepoint_t lo_index = lo / QUAD_BITS;
791    codepoint_t hi_index = hi / QUAD_BITS;
792
793    const run_t * ri = mRuns;
794    const run_t * const ri_end = mRuns + mRunLength;
795
796    const bitquad_t * qi = mQuads;
797    const bitquad_t * const qi_end = mQuads + mQuadLength;
798
799    codepoint_t length = 0;
800    run_type_t type = Empty;
801
802    // Advance past any runs prior to the lo_index
803    for (;;) {
804        assert (ri < ri_end);
805        std::tie(type, length) = *ri;
806        if (lo_index < length) {
807            break;
808        }
809        if (type == Mixed) {
810            assert ((qi + length) <= qi_end);
811            qi += length;
812        }
813        lo_index -= length;
814        hi_index -= length;
815        ++ri;
816    }
817
818    // Now record the runs and any quads prior to lo_index   
819    runs.append<const run_t *>(mRuns, ri++);
820    if (lo_index) {
821        runs.emplace_back(type, lo_index);
822        if (type == Mixed) {
823            assert ((qi + lo_index) <= qi_end);
824            qi += lo_index;
825        }
826        hi_index -= lo_index;
827        assert (length >= lo_index);
828        length -= lo_index;
829    }
830
831    quads.append<const bitquad_t *>(mQuads, qi);
832    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
833    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & QUAD_LIMIT));
834    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - (hi & QUAD_LIMIT)));
835
836    // If our original quad is full, just append a Full run
837    if (LLVM_UNLIKELY(type == Full)) {
838        append_run(Full, 1, runs);
839    } else { // Otherwise merge the new quad value with the original one
840        if (hi_index == 0) {
841            lo_quad &= hi_quad;
842        }       
843        if (type == Mixed) {
844            assert (qi < qi_end);
845            lo_quad |= *qi++;
846        }
847        append_quad(lo_quad, quads, runs);
848    }
849
850    assert (length > 0);
851    --length;
852
853    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
854    // in the original quad to suit.
855    if (hi_index) {
856        // Add in any full runs between the lo and hi quads
857        append_run(Full, hi_index - 1, runs);
858        // Advance past original quads that were filled in
859        while (length < hi_index) {
860            if (type == Mixed) {
861                assert ((qi + length) <= qi_end);
862                qi += length;
863            }
864            hi_index -= length;
865            assert (ri < ri_end);
866            std::tie(type, length) = *ri++;
867        }
868        length -= hi_index;
869        // Write out the hi_quad value
870        if (LLVM_UNLIKELY(type == Full)) {
871            append_run(Full, 1, runs);
872        } else {
873            if (type == Mixed) {
874                assert ((qi + hi_index) < qi_end);
875                qi += hi_index;
876                hi_quad |= *qi++;
877            }
878            append_quad(hi_quad, quads, runs);
879        }
880    }
881    assert ("We wrote all the runs but still have remaining quads?" && (ri != ri_end || qi == qi_end));
882    append_run(type, length, runs);
883
884    // append any remaining values from the original data
885    runs.append<const run_t *>(ri, ri_end);
886    quads.append<const bitquad_t *>(qi, qi_end);
887    assign(this, runs, quads);
888}
889
890/** ------------------------------------------------------------------------------------------------------------- *
891 * @brief contains
892 * @param codepoint
893 *
894 * Return whether this UnicodeSet contains the specified code point
895 ** ------------------------------------------------------------------------------------------------------------- */
896bool UnicodeSet::contains(const codepoint_t cp) const noexcept {
897    codepoint_t offset = cp / QUAD_BITS;
898    for (unsigned runIndex = 0, quadIndex = 0; runIndex < mRunLength; ++runIndex) {
899        length_t length = 0;
900        run_type_t type = Empty;
901        std::tie(type, length) = mRuns[runIndex];
902        if (offset < length) {
903            if (type == Mixed) {
904                return (mQuads[quadIndex + offset] & (static_cast<bitquad_t>(1) << (cp & QUAD_LIMIT))) != 0;
905            }
906            return (type == Full);
907        }
908        if (type == Mixed) {
909            quadIndex += length;
910        }       
911        offset -= length;
912    }
913    return false;
914}
915
916/** ------------------------------------------------------------------------------------------------------------- *
917 * @brief intersects
918 * @param lo_codepoint
919 * @param hi_codepoint
920 *
921 * Return true if this UnicodeSet contains any code point between lo and hi (inclusive)
922 ** ------------------------------------------------------------------------------------------------------------- */
923bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const noexcept {
924    for (auto range : *this) {
925        if (range.second < lo) {
926            continue;
927        }
928        if (range.first > hi) {
929            break;
930        }
931        return true;
932    }
933    return false;
934}
935       
936/** ------------------------------------------------------------------------------------------------------------- *
937 * @brief intersects
938 * @param other
939 *
940 * Return true if this UnicodeSet has a non-empty intersection with other
941 ** ------------------------------------------------------------------------------------------------------------- */
942bool UnicodeSet::intersects(const UnicodeSet & other) const noexcept {
943    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
944        auto n = std::min(i1.length(), i2.length());
945        if (LLVM_UNLIKELY(n == 0)) {
946            assert (i1 == quad_end() && i2 == other.quad_end());
947            return false;
948        }
949        if (i1.type() == Empty || i2.type() == Empty) {
950            i1 += n;
951            i2 += n;
952        } else if (i1.type() == Full || i2.type() == Full) {
953            return true;
954        } else { //both Mixed
955            assert (i1.type() == Mixed && i2.type() == Mixed);
956            for (; n; --n, ++i1, ++i2) {
957                if ((i1.quad() & i2.quad()) != 0) return true;
958            }
959        }
960    }
961}
962
963/** ------------------------------------------------------------------------------------------------------------- *
964 * @brief isSubsetOf
965 * @param other
966 *
967 * Return true if this UnicodeSet is a subset of other
968 ** ------------------------------------------------------------------------------------------------------------- */
969bool UnicodeSet::subset(const UnicodeSet & other) const noexcept {
970    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
971        auto n = std::min(i1.length(), i2.length());
972        if (LLVM_UNLIKELY(n == 0)) {
973            assert (i1 == quad_end() && i2 == other.quad_end());
974            return true;
975        }
976        if (i1.type() == Empty || i2.type() == Full) {
977            i1 += n;
978            i2 += n;
979        } else if (i1.type() == Full || i2.type() == Empty) {
980            return false;
981        } else { //both Mixed
982            assert (i1.type() == Mixed && i2.type() == Mixed);
983            for (; n; --n, ++i1, ++i2) {
984                if (i1.quad() &~ i2.quad()) return false;
985            }
986        }
987    }
988}
989
990/** ------------------------------------------------------------------------------------------------------------- *
991 * @brief UnicodeSet::quad_iterator::advance
992 ** ------------------------------------------------------------------------------------------------------------- */
993void UnicodeSet::quad_iterator::advance(unsigned n) {
994    assert (mRemaining > 0);
995    while (n > 0) {   
996        if (mRemaining > n) {
997            if (mType == Mixed) {
998                assert (mQuadIterator <= (mQuadEnd - n));
999                mQuadIterator += n;
1000            }
1001            mRemaining -= n;
1002            break;
1003        }
1004        if (mType == Mixed) {
1005            assert (mQuadIterator <= (mQuadEnd - mRemaining));
1006            mQuadIterator += mRemaining;
1007        }
1008        n -= mRemaining;
1009        ++mRunIterator;
1010        if (LLVM_UNLIKELY(mRunIterator == mRunEnd)) {
1011            mType = Empty;
1012            mRemaining = 0;
1013            break;
1014        }
1015        mType = typeOf(*mRunIterator);
1016        mRemaining = lengthOf(*mRunIterator);
1017    }
1018    assert ("remaining length cannot be 0 unless this is the final run" && ((mRunIterator != mRunEnd) || (mRemaining == 0)));
1019    assert ("cannot be the final quad unless this is the final run" && ((mRunIterator != mRunEnd) || (mQuadIterator == mQuadEnd)));
1020}
1021
1022/** ------------------------------------------------------------------------------------------------------------- *
1023 * @brief UnicodeSet::iterator::advance
1024 ** ------------------------------------------------------------------------------------------------------------- */
1025void UnicodeSet::iterator::advance(const unsigned n) {
1026
1027    assert (n == 1);
1028
1029    if (LLVM_UNLIKELY(mMinCodePoint > UNICODE_MAX)) {
1030        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
1031    }
1032
1033    bool found = false;
1034    // Find the start of our interval
1035    while ( mBaseCodePoint <= UNICODE_MAX ) {
1036        // Find the first non-empty block
1037        if (typeOf(*mRunIterator) != Mixed) {           
1038            // If we found a full run, this must be the start of our interval.
1039            const auto baseCodePoint = mBaseCodePoint;
1040            const auto type = typeOf(*mRunIterator);
1041            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
1042            if (type == Full) {
1043                mMinCodePoint = baseCodePoint;
1044                found = true;
1045                break;
1046            }
1047        } else { // if (typeOf(t) == Mixed)
1048            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
1049                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
1050                // If we found a marker in m, it marks the beginning of our current interval.
1051                // Find it and break out of the loop.
1052                if (m) {
1053                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
1054                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
1055                    found = true;
1056                    break;
1057                }
1058                mBaseCodePoint += QUAD_BITS;
1059                ++mQuadIterator;
1060                ++mMixedRunIndex;
1061                mQuadOffset = 0;
1062            }
1063            if (found) break;
1064            ++mRunIterator;
1065            mQuadOffset = 0;
1066            mMixedRunIndex = 0;
1067        }
1068    }
1069
1070    if (!found) {
1071        assert (mBaseCodePoint == (UNICODE_MAX+1));
1072        mMinCodePoint = (UNICODE_MAX+1);
1073        return;
1074    }
1075
1076    // at this stage, the max code point is the previous max code point (initially 0)
1077    assert (mMaxCodePoint <= mMinCodePoint);
1078    found = false;
1079    // Find the end of our interval
1080    while ( mBaseCodePoint <= UNICODE_MAX ) {
1081
1082        // Find the first non-Full block
1083        if (typeOf(*mRunIterator) != Mixed) {
1084            // If this run is Empty, the max code point is the last computed base code point - 1.
1085            const auto baseCodePoint = mBaseCodePoint;
1086            const auto type = typeOf(*mRunIterator);
1087            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
1088            if (type == Empty) {
1089                mMaxCodePoint = baseCodePoint - 1;
1090                found = true;
1091                break;
1092            }
1093        } else { // if (typeOf(t) == Mixed)
1094            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
1095                const bitquad_t m = ((~*mQuadIterator)) & (FULL_QUAD_MASK << mQuadOffset);
1096                // If we found a marker in m, it marks the end of our current interval.
1097                // Find it and break out of the loop.
1098                if (m) {
1099                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
1100                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
1101                    found = true;
1102                    break;
1103                }
1104                mBaseCodePoint += QUAD_BITS;
1105                ++mQuadIterator;
1106                ++mMixedRunIndex;
1107                mQuadOffset = 0;
1108            }
1109            if (found) break;
1110            ++mRunIterator;
1111            mQuadOffset = 0;
1112            mMixedRunIndex = 0;
1113        }
1114    }
1115    // if the very last block is a mixed block and we go past it, the last code point of the range is UNICODE_MAX
1116    if (!found) {
1117        assert (mBaseCodePoint == (UNICODE_MAX+1));
1118        mMaxCodePoint = UNICODE_MAX;
1119    }
1120
1121    assert (mMinCodePoint <= mMaxCodePoint);
1122}
1123
1124/** ------------------------------------------------------------------------------------------------------------- *
1125 * @brief Empty/Full Set Constructor
1126 ** ------------------------------------------------------------------------------------------------------------- */
1127UnicodeSet::UnicodeSet() noexcept
1128: mRuns(GlobalAllocator.allocate<run_t>(1))
1129, mQuads(nullptr)
1130, mRunLength(1)
1131, mQuadLength(0)
1132, mRunCapacity(1)
1133, mQuadCapacity(0) {
1134    mRuns[0] = std::make_pair(Empty, UNICODE_QUAD_COUNT);
1135    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1136}
1137           
1138/** ------------------------------------------------------------------------------------------------------------- *
1139 * @brief Singleton Set Constructor
1140 ** ------------------------------------------------------------------------------------------------------------- */
1141UnicodeSet::UnicodeSet(const codepoint_t codepoint) noexcept
1142: mRuns(GlobalAllocator.allocate<run_t>(3))
1143, mQuads(GlobalAllocator.allocate<bitquad_t>(1))
1144, mRunLength(0)
1145, mQuadLength(1)
1146, mRunCapacity(3)
1147, mQuadCapacity(1) {
1148    assert (codepoint <= UNICODE_MAX);
1149    const codepoint_t offset = codepoint / QUAD_BITS;
1150    const codepoint_t remaining = UNICODE_QUAD_COUNT - (offset + 1);   
1151    unsigned l = 0;
1152    if (offset) {
1153        mRuns[l++] = std::make_pair(Empty, offset);
1154    }
1155    mRuns[l++] = std::make_pair(Mixed, 1);
1156    if (remaining) {
1157        mRuns[l++] = std::make_pair(Empty, remaining);
1158    }
1159    mRunLength = l;
1160    mQuads[0] = static_cast<bitquad_t>(1) << (codepoint & QUAD_LIMIT);
1161    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1162    assert (contains(codepoint));
1163    assert (codepoint == 0 || !contains(codepoint - 1));
1164    assert (codepoint == UNICODE_MAX || !contains(codepoint + 1));
1165}
1166
1167/** ------------------------------------------------------------------------------------------------------------- *
1168 * @brief Range Set Constructor
1169 ** ------------------------------------------------------------------------------------------------------------- */
1170UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi) noexcept
1171: mRuns(GlobalAllocator.allocate<run_t>(5))
1172, mQuads(GlobalAllocator.allocate<bitquad_t>(2))
1173, mRunLength(0)
1174, mQuadLength(0)
1175, mRunCapacity(5)
1176, mQuadCapacity(2) {
1177
1178    const codepoint_t lo_index = lo / QUAD_BITS;
1179    const codepoint_t hi_index = hi / QUAD_BITS;
1180    const codepoint_t lo_offset = lo & QUAD_LIMIT;
1181    const codepoint_t hi_offset = hi & QUAD_LIMIT;
1182
1183    assert (lo <= hi);
1184    assert (hi <= UNICODE_MAX);
1185
1186    // Assuming that Empty and Full quads can be of 0 length and Mixed are
1187    // length 1, we have the following cases:
1188
1189    // LO_INDEX == HI_INDEX && LO_OFFSET == 0 && HI_OFFSET == QUAD_BITS
1190
1191    //             Empty           Full            Empty
1192    //      |                 |############|                 |
1193
1194    // LO_INDEX == HI_INDEX && (LO_OFFSET != 0 || HI_OFFSET != QUAD_BITS)
1195
1196    //             Empty          Mixed             Empty
1197    //      |                 |  #######   |                 |
1198
1199    // LO_INDEX != HI_INDEX && LO_OFFSET != 0 && HI_OFFSET == QUAD_BITS
1200
1201    //          Empty    Mixed     Full            Empty
1202    //      |           |  ###|############|                 |
1203
1204    // LO_INDEX != HI_INDEX && LO_OFFSET == 0 && HI_OFFSET != QUAD_BITS
1205
1206    //             Empty           Full     Mixed    Empty
1207    //      |                 |############|###  |           |
1208
1209    // LO_INDEX != HI_INDEX && LO_OFFSET != 0 && HI_OFFSET != QUAD_BITS
1210
1211    //          Empty    Mixed     Full     Mixed    Empty
1212    //      |           |  ###|############|###  |           |
1213
1214    if (LLVM_LIKELY(lo_index != 0)) {
1215        mRuns[0] = std::make_pair(Empty, lo_index);
1216        mRunLength = 1;
1217    }
1218    if (lo_index == hi_index) {
1219        if ((lo_offset == 0) && (hi_offset == QUAD_LIMIT)) {
1220            mRuns[mRunLength++] = std::make_pair(Full, 1);
1221        } else {
1222            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
1223            const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
1224            const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
1225            mQuads[0] = lo_quad & hi_quad;
1226            mQuadLength = 1;
1227        }
1228
1229    } else {
1230        const auto lm = ((lo_offset != 0) ? 1U : 0U);
1231        const auto rm = ((hi_offset != QUAD_LIMIT) ? 1U : 0U);
1232        const auto d = (hi_index - lo_index) - (lm + rm) + 1;
1233        if (lo_offset != 0) {
1234            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
1235            mQuads[0] = (FULL_QUAD_MASK << lo_offset);
1236            mQuadLength = 1;
1237        }
1238        if (d != 0) {
1239            mRuns[mRunLength++] = std::make_pair(Full, d);
1240        }
1241        if (hi_offset != QUAD_LIMIT) {
1242            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
1243            const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
1244            mQuads[mQuadLength++] = hi_quad;
1245        }
1246    }
1247    const auto remaining = UNICODE_QUAD_COUNT - (hi_index + 1);
1248    if (LLVM_LIKELY(remaining != 0)) {
1249        mRuns[mRunLength++] = std::make_pair(Empty, remaining);
1250    }
1251    assert (mRunLength <= mRunCapacity);
1252    assert (mQuadLength <= mQuadCapacity);
1253    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1254    assert (contains(lo) && contains(hi));
1255    assert (lo == 0 || !contains(lo - 1));
1256    assert (hi == UNICODE_MAX || !contains(hi + 1));
1257}
1258
1259/** ------------------------------------------------------------------------------------------------------------- *
1260 * @brief Range List Set Constructor
1261 ** ------------------------------------------------------------------------------------------------------------- */
1262template <typename iterator>
1263inline void convertIntervalsToUnicodeSet(const iterator begin, const iterator end, RunVector & runs, QuadVector & quads) noexcept {
1264
1265    assert ("interval list must be totally ordered" && std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
1266        if (l.first > l.second) return false;
1267        if (l.second > UNICODE_MAX) return false;
1268        if (r.first > r.second) return false;
1269        if (r.second > UNICODE_MAX) return false;
1270        return l.second < r.first;
1271    }));
1272   
1273    codepoint_t prior_index = 0;
1274    bitquad_t mask = 0;
1275    for (auto interval = begin; interval != end; ) {
1276        codepoint_t lo, hi;
1277        std::tie(lo, hi) = *interval;
1278        const codepoint_t lo_index = (lo / QUAD_BITS);
1279        const codepoint_t hi_index = (hi / QUAD_BITS);
1280        const codepoint_t lo_offset = lo & QUAD_LIMIT;
1281        const codepoint_t hi_offset = hi & QUAD_LIMIT;
1282        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
1283        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
1284        append_run(Empty, lo_index - prior_index, runs);
1285        if (lo_index == hi_index) {
1286            mask |= (lo_quad & hi_quad);
1287        } else {
1288            append_quad(mask | lo_quad, quads, runs);
1289            append_run(Full, hi_index - (lo_index + 1), runs);
1290            mask = hi_quad;
1291        }
1292        // if the next interval is in our current quad, continue to the next range
1293        prior_index = hi_index;
1294        if (LLVM_LIKELY(++interval != end)) {
1295            if (hi_index == (interval->first / QUAD_BITS)) {
1296                continue;
1297            }
1298        }
1299        append_quad(mask, quads, runs);
1300        mask = 0;
1301        ++prior_index;
1302    }
1303    assert (mask == 0);
1304    if (prior_index < UNICODE_QUAD_COUNT) {
1305        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
1306    }
1307}
1308
1309/** ------------------------------------------------------------------------------------------------------------- *
1310 * @brief Interval Range Constructor
1311 ** ------------------------------------------------------------------------------------------------------------- */
1312UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end) noexcept
1313: mRuns(nullptr)
1314, mQuads(nullptr)
1315, mRunLength(0)
1316, mQuadLength(0)
1317, mRunCapacity(0)
1318, mQuadCapacity(0) {
1319    RunVector runs;
1320    QuadVector quads;
1321
1322    convertIntervalsToUnicodeSet(begin, end, runs, quads);
1323
1324    const auto n = runs.size();
1325    assert (n > 0 && n < UNICODE_QUAD_COUNT);
1326    mRuns = GlobalAllocator.allocate<run_t>(n);
1327    mRunCapacity = n;
1328    mRunLength = n;
1329    std::memcpy(mRuns, runs.data(), n * sizeof(run_t));
1330
1331    const auto m = quads.size();
1332    assert (m < UNICODE_QUAD_COUNT);
1333    if (m) {
1334        mQuads = GlobalAllocator.allocate<bitquad_t>(m);
1335        mQuadCapacity = m;
1336        mQuadLength = m;
1337        std::memcpy(mQuads, quads.data(), m * sizeof(bitquad_t));
1338    }
1339
1340    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1341}
1342
1343/** ------------------------------------------------------------------------------------------------------------- *
1344 * @brief Interval Range Constructor
1345 ** ------------------------------------------------------------------------------------------------------------- */
1346UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end) noexcept
1347: mRuns(nullptr)
1348, mQuads(nullptr)
1349, mRunLength(0)
1350, mQuadLength(0)
1351, mRunCapacity(0)
1352, mQuadCapacity(0) {
1353    RunVector runs;
1354    QuadVector quads;
1355
1356    convertIntervalsToUnicodeSet(begin, end, runs, quads);
1357
1358    const auto n = runs.size();
1359    assert (n > 0 && n < UNICODE_QUAD_COUNT);
1360    mRuns = GlobalAllocator.allocate<run_t>(n);
1361    mRunCapacity = n;
1362    mRunLength = n;
1363    std::memcpy(mRuns, runs.data(), n * sizeof(run_t));
1364
1365    const auto m = quads.size();
1366    assert (m < UNICODE_QUAD_COUNT);
1367    if (m) {
1368        mQuads = GlobalAllocator.allocate<bitquad_t>(m);
1369        mQuadCapacity = m;
1370        mQuadLength = m;
1371        std::memcpy(mQuads, quads.data(), m * sizeof(bitquad_t));
1372    }
1373
1374    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1375}
1376
1377/** ------------------------------------------------------------------------------------------------------------- *
1378 * @brief Move Constructor
1379 ** ------------------------------------------------------------------------------------------------------------- */
1380UnicodeSet::UnicodeSet(const UnicodeSet && other) noexcept
1381: mRuns(other.mRuns)
1382, mQuads(other.mQuads)
1383, mRunLength(other.mRunLength)
1384, mQuadLength(other.mQuadLength)
1385, mRunCapacity(other.mRunLength)
1386, mQuadCapacity(other.mQuadLength) {
1387    assert (verify(mRuns, other.mRunLength, mQuads, other.mQuadLength));
1388}
1389
1390/** ------------------------------------------------------------------------------------------------------------- *
1391 * @brief Move Assignment Constructor
1392 ** ------------------------------------------------------------------------------------------------------------- */
1393UnicodeSet & UnicodeSet::operator=(const UnicodeSet && other) noexcept {
1394    if (mRunCapacity) {
1395        GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
1396    }
1397    if (mQuadCapacity) {
1398        GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
1399    }
1400    mRuns = other.mRuns;
1401    mQuads = other.mQuads;
1402    mRunLength = other.mRunLength;
1403    mQuadLength = other.mQuadLength;
1404    mRunCapacity = other.mRunCapacity;
1405    mQuadCapacity = other.mQuadCapacity;
1406    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1407    return *this;
1408}
1409
1410/** ------------------------------------------------------------------------------------------------------------- *
1411 * @brief Copy Constructor
1412 ** ------------------------------------------------------------------------------------------------------------- */
1413UnicodeSet::UnicodeSet(const UnicodeSet & other) noexcept
1414: mRuns(nullptr)
1415, mQuads(nullptr)
1416, mRunLength(0)
1417, mQuadLength(0)
1418, mRunCapacity(0)
1419, mQuadCapacity(0) {
1420    // lazily ensure reallocation on modification if and only if the source cannot modify it
1421    if (other.mRunCapacity == 0) {
1422        mRuns = other.mRuns;
1423        mRunCapacity = 0;
1424    } else {
1425        mRuns = copyOf<run_t>(other.mRuns, other.mRunLength, GlobalAllocator);
1426        mRunCapacity = other.mRunLength;
1427    }
1428    mRunLength = other.mRunLength;
1429    if (other.mQuadCapacity == 0) {
1430        mQuads = other.mQuads;
1431        mQuadCapacity = 0;
1432    } else {
1433        mQuads = copyOf<bitquad_t>(other.mQuads, other.mQuadCapacity, GlobalAllocator);
1434        mQuadCapacity = other.mQuadLength;
1435    }
1436    mQuadLength = other.mQuadLength;
1437    assert (verify(mRuns, other.mRunLength, mQuads, other.mQuadLength));
1438}
1439
1440/** ------------------------------------------------------------------------------------------------------------- *
1441 * @brief Copy Assignment Constructor
1442 ** ------------------------------------------------------------------------------------------------------------- */
1443UnicodeSet & UnicodeSet::operator=(const UnicodeSet & other) noexcept {
1444    if (mRunCapacity) {
1445        GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
1446    }
1447    if (mQuadCapacity) {
1448        GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
1449    }
1450    // lazily ensure reallocation on modification if and only if the source cannot modify it
1451    if (other.mRunCapacity == 0) {
1452        mRuns = other.mRuns;
1453        mRunCapacity = 0;
1454    } else {
1455        mRuns = copyOf<run_t>(other.mRuns, other.mRunLength, GlobalAllocator);
1456        mRunCapacity = other.mRunLength;
1457    }
1458    mRunLength = other.mRunLength;
1459    if (other.mQuadCapacity == 0) {
1460        mQuads = other.mQuads;
1461        mQuadCapacity = 0;
1462    } else {
1463        mQuads = copyOf<bitquad_t>(other.mQuads, other.mQuadCapacity, GlobalAllocator);
1464        mQuadCapacity = other.mQuadLength;
1465    }
1466    mQuadLength = other.mQuadLength;
1467    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1468    return *this;
1469}
1470
1471/** ------------------------------------------------------------------------------------------------------------- *
1472 * @brief Internal / Predefined Constructor
1473 ** ------------------------------------------------------------------------------------------------------------- */
1474UnicodeSet::UnicodeSet(run_t * const runs, const uint32_t runLength, const uint32_t runCapacity,
1475                       bitquad_t * const quads, const uint32_t quadLength, const uint32_t quadCapacity) noexcept
1476: mRuns(runs)
1477, mQuads(quads)
1478, mRunLength(runLength)
1479, mQuadLength(quadLength)
1480, mRunCapacity(runCapacity)
1481, mQuadCapacity(quadCapacity) {
1482    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1483}
1484
1485/** ------------------------------------------------------------------------------------------------------------- *
1486 * @brief Deprecated Constructor
1487 ** ------------------------------------------------------------------------------------------------------------- */
1488UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) noexcept
1489: mRuns(GlobalAllocator.allocate<run_t>(r.size()))
1490, mQuads(q.size() == 0 ? nullptr : GlobalAllocator.allocate<bitquad_t>(q.size()))
1491, mRunLength(r.size())
1492, mQuadLength(q.size())
1493, mRunCapacity(r.size())
1494, mQuadCapacity(q.size()) {
1495    std::copy(r.begin(), r.end(), mRuns);
1496    std::copy(q.begin(), q.end(), mQuads);
1497    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1498}
1499
1500}
Note: See TracBrowser for help on using the repository browser.