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

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

Bug fix for segment pipeline parallel mode + memory management improvements.

File size: 57.3 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 + remaining;
188            }
189            base += m;
190            remaining -= m;
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 + k;
202                        }
203                        q ^= static_cast<bitquad_t>(1) << k;
204                        --remaining;
205                    }
206                }
207                base += QUAD_BITS;
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
675//    print(llvm::errs());
676//    llvm::errs() << "\n\n";
677
678    assert (contains(cp));
679}
680
681/** ------------------------------------------------------------------------------------------------------------- *
682 * @brief insert
683 ** ------------------------------------------------------------------------------------------------------------- */
684void UnicodeSet::insert(const UnicodeSet & other) noexcept {
685    RunVector runs;
686    QuadVector quads;
687    auto i1 = quad_begin(), i2 = other.quad_begin();
688    bool changed = false;
689    for (;;) {
690        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
691        const auto n = std::min(i1.length(), i2.length());
692        if (LLVM_UNLIKELY(n == 0)) {
693            break;
694        }
695        if ((i1.type() == Empty) && (i2.type() == Empty)) {
696            append_run(Empty, n, runs);
697            i1 += n;
698            i2 += n;
699        } else if ((i1.type() == Full) || (i2.type() == Full)) {
700            changed |= (i1.type() != Full);
701            append_run(Full, n, runs);
702            i1 += n;
703            i2 += n;
704        } else if (i1.type() == Empty) {
705            assert (i2.type() == Mixed);
706            changed = true;
707            for (unsigned i = 0; i != n; ++i, ++i2) {
708                append_quad(i2.quad(), quads, runs);
709            }
710            i1 += n;
711        } else if (i2.type() == Empty) {
712            assert (i1.type() == Mixed);
713            for (unsigned i = 0; i != n; ++i, ++i1) {
714                append_quad(i1.quad(), quads, runs);
715            }
716            i2 += n;
717        } else { // both Mixed
718            assert (i1.type() == Mixed && i2.type() == Mixed);
719            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
720                changed |= (i2.quad() &~ i1.quad());
721                append_quad(i1.quad() | i2.quad(), quads, runs);
722            }
723        }
724    }
725    assert (i1 == quad_end() && i2 == other.quad_end());
726    if (LLVM_LIKELY(changed)) {
727        assign(this, runs, quads);
728    }
729}
730
731/** ------------------------------------------------------------------------------------------------------------- *
732 * @brief invert
733 ** ------------------------------------------------------------------------------------------------------------- */
734void UnicodeSet::invert() noexcept {
735
736    if (LLVM_UNLIKELY(mRunCapacity == 0)) {
737        run_t * const runs = GlobalAllocator.allocate<run_t>(mRunLength);
738        for (unsigned i = 0; i < mRunLength; ++i) {
739            auto & run = mRuns[i];
740            const auto l = lengthOf(run);
741            if (typeOf(run) == Empty) {
742                runs[i] = std::make_pair(Full, l);
743            } else if (typeOf(run) == Full) {
744                runs[i] = std::make_pair(Empty, l);
745            } else {
746                runs[i] = std::make_pair(Mixed, l);
747            }
748        }
749        mRuns = runs;
750        mRunCapacity = mRunLength;
751    } else {
752        for (unsigned i = 0; i < mRunLength; ++i) {
753            auto & run = mRuns[i];
754            if (typeOf(run) == Empty) {
755                std::get<0>(run) = Full;
756            } else if (typeOf(run) == Full) {
757                std::get<0>(run) = Empty;
758            }
759        }
760    }
761
762    if (mQuadLength) {
763        if (mQuadCapacity == 0) {
764            bitquad_t * const quads = GlobalAllocator.allocate<bitquad_t>(mQuadLength);
765            for (unsigned i = 0; i != mQuadLength; ++i) {
766                quads[i] = ~mQuads[i];
767            }
768            mQuads = quads;
769            mQuadCapacity = mQuadLength;
770        } else {
771            for (unsigned i = 0; i != mQuadLength; ++i) {
772                mQuads[i] = ~mQuads[i];
773            }
774        }
775    }
776
777}
778
779/** ------------------------------------------------------------------------------------------------------------- *
780 * @brief insert_range
781 ** ------------------------------------------------------------------------------------------------------------- */
782void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi) {
783
784    if (LLVM_UNLIKELY(lo > hi)) {
785        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
786    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
787        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
788    }
789
790    // Create a temporary run and quad set for the given range
791    RunVector runs;
792    QuadVector quads;
793
794    codepoint_t lo_index = lo / QUAD_BITS;
795    codepoint_t hi_index = hi / QUAD_BITS;
796
797    const run_t * ri = mRuns;
798    const run_t * const ri_end = mRuns + mRunLength;
799
800    const bitquad_t * qi = mQuads;
801    const bitquad_t * const qi_end = mQuads + mQuadLength;
802
803    codepoint_t length = 0;
804    run_type_t type = Empty;
805
806    // Advance past any runs prior to the lo_index
807    for (;;) {
808        assert (ri < ri_end);
809        std::tie(type, length) = *ri;
810        if (lo_index < length) {
811            break;
812        }
813        if (type == Mixed) {
814            assert ((qi + length) <= qi_end);
815            qi += length;
816        }
817        lo_index -= length;
818        hi_index -= length;
819        ++ri;
820    }
821
822    // Now record the runs and any quads prior to lo_index   
823    runs.append<const run_t *>(mRuns, ri++);
824    if (lo_index) {
825        runs.emplace_back(type, lo_index);
826        if (type == Mixed) {
827            assert ((qi + lo_index) <= qi_end);
828            qi += lo_index;
829        }
830        hi_index -= lo_index;
831        assert (length >= lo_index);
832        length -= lo_index;
833    }
834
835    quads.append<const bitquad_t *>(mQuads, qi);
836    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
837    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & QUAD_LIMIT));
838    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - (hi & QUAD_LIMIT)));
839
840    // If our original quad is full, just append a Full run
841    if (LLVM_UNLIKELY(type == Full)) {
842        append_run(Full, 1, runs);
843    } else { // Otherwise merge the new quad value with the original one
844        if (hi_index == 0) {
845            lo_quad &= hi_quad;
846        }       
847        if (type == Mixed) {
848            assert (qi < qi_end);
849            lo_quad |= *qi++;
850        }
851        append_quad(lo_quad, quads, runs);
852    }
853
854    assert (length > 0);
855    --length;
856
857    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
858    // in the original quad to suit.
859    if (hi_index) {
860        // Add in any full runs between the lo and hi quads
861        append_run(Full, hi_index - 1, runs);
862        // Advance past original quads that were filled in
863        while (length < hi_index) {
864            if (type == Mixed) {
865                assert ((qi + length) <= qi_end);
866                qi += length;
867            }
868            hi_index -= length;
869            assert (ri < ri_end);
870            std::tie(type, length) = *ri++;
871        }
872        length -= hi_index;
873        // Write out the hi_quad value
874        if (LLVM_UNLIKELY(type == Full)) {
875            append_run(Full, 1, runs);
876        } else {
877            if (type == Mixed) {
878                assert ((qi + hi_index) < qi_end);
879                qi += hi_index;
880                hi_quad |= *qi++;
881            }
882            append_quad(hi_quad, quads, runs);
883        }
884    }
885    assert ("We wrote all the runs but still have remaining quads?" && (ri != ri_end || qi == qi_end));
886    append_run(type, length, runs);
887
888    // append any remaining values from the original data
889    runs.append<const run_t *>(ri, ri_end);
890    quads.append<const bitquad_t *>(qi, qi_end);
891    assign(this, runs, quads);
892}
893
894/** ------------------------------------------------------------------------------------------------------------- *
895 * @brief contains
896 * @param codepoint
897 *
898 * Return whether this UnicodeSet contains the specified code point
899 ** ------------------------------------------------------------------------------------------------------------- */
900bool UnicodeSet::contains(const codepoint_t cp) const noexcept {
901    codepoint_t offset = cp / QUAD_BITS;
902    for (unsigned runIndex = 0, quadIndex = 0; runIndex < mRunLength; ++runIndex) {
903        length_t length = 0;
904        run_type_t type = Empty;
905        std::tie(type, length) = mRuns[runIndex];
906        if (offset < length) {
907            if (type == Mixed) {
908                return (mQuads[quadIndex + offset] & (static_cast<bitquad_t>(1) << (cp & QUAD_LIMIT))) != 0;
909            }
910            return (type == Full);
911        }
912        if (type == Mixed) {
913            quadIndex += length;
914        }       
915        offset -= length;
916    }
917    return false;
918}
919
920/** ------------------------------------------------------------------------------------------------------------- *
921 * @brief intersects
922 * @param lo_codepoint
923 * @param hi_codepoint
924 *
925 * Return true if this UnicodeSet contains any code point between lo and hi (inclusive)
926 ** ------------------------------------------------------------------------------------------------------------- */
927bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const noexcept {
928    for (auto range : *this) {
929        if (range.second < lo) {
930            continue;
931        }
932        if (range.first > hi) {
933            break;
934        }
935        return true;
936    }
937    return false;
938}
939       
940/** ------------------------------------------------------------------------------------------------------------- *
941 * @brief intersects
942 * @param other
943 *
944 * Return true if this UnicodeSet has a non-empty intersection with other
945 ** ------------------------------------------------------------------------------------------------------------- */
946bool UnicodeSet::intersects(const UnicodeSet & other) const noexcept {
947    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
948        auto n = std::min(i1.length(), i2.length());
949        if (LLVM_UNLIKELY(n == 0)) {
950            assert (i1 == quad_end() && i2 == other.quad_end());
951            return false;
952        }
953        if (i1.type() == Empty || i2.type() == Empty) {
954            i1 += n;
955            i2 += n;
956        } else if (i1.type() == Full || i2.type() == Full) {
957            return true;
958        } else { //both Mixed
959            assert (i1.type() == Mixed && i2.type() == Mixed);
960            for (; n; --n, ++i1, ++i2) {
961                if ((i1.quad() & i2.quad()) != 0) return true;
962            }
963        }
964    }
965}
966
967/** ------------------------------------------------------------------------------------------------------------- *
968 * @brief isSubsetOf
969 * @param other
970 *
971 * Return true if this UnicodeSet is a subset of other
972 ** ------------------------------------------------------------------------------------------------------------- */
973bool UnicodeSet::subset(const UnicodeSet & other) const noexcept {
974    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
975        auto n = std::min(i1.length(), i2.length());
976        if (LLVM_UNLIKELY(n == 0)) {
977            assert (i1 == quad_end() && i2 == other.quad_end());
978            return true;
979        }
980        if (i1.type() == Empty || i2.type() == Full) {
981            i1 += n;
982            i2 += n;
983        } else if (i1.type() == Full || i2.type() == Empty) {
984            return false;
985        } else { //both Mixed
986            assert (i1.type() == Mixed && i2.type() == Mixed);
987            for (; n; --n, ++i1, ++i2) {
988                if (i1.quad() &~ i2.quad()) return false;
989            }
990        }
991    }
992}
993
994/** ------------------------------------------------------------------------------------------------------------- *
995 * @brief UnicodeSet::quad_iterator::advance
996 ** ------------------------------------------------------------------------------------------------------------- */
997void UnicodeSet::quad_iterator::advance(unsigned n) {
998    assert (mRemaining > 0);
999    while (n > 0) {   
1000        if (mRemaining > n) {
1001            if (mType == Mixed) {
1002                assert (mQuadIterator <= (mQuadEnd - n));
1003                mQuadIterator += n;
1004            }
1005            mRemaining -= n;
1006            break;
1007        }
1008        if (mType == Mixed) {
1009            assert (mQuadIterator <= (mQuadEnd - mRemaining));
1010            mQuadIterator += mRemaining;
1011        }
1012        n -= mRemaining;
1013        ++mRunIterator;
1014        if (LLVM_UNLIKELY(mRunIterator == mRunEnd)) {
1015            mType = Empty;
1016            mRemaining = 0;
1017            break;
1018        }
1019        mType = typeOf(*mRunIterator);
1020        mRemaining = lengthOf(*mRunIterator);
1021    }
1022    assert ("remaining length cannot be 0 unless this is the final run" && ((mRunIterator != mRunEnd) || (mRemaining == 0)));
1023    assert ("cannot be the final quad unless this is the final run" && ((mRunIterator != mRunEnd) || (mQuadIterator == mQuadEnd)));
1024}
1025
1026/** ------------------------------------------------------------------------------------------------------------- *
1027 * @brief UnicodeSet::iterator::advance
1028 ** ------------------------------------------------------------------------------------------------------------- */
1029void UnicodeSet::iterator::advance(const unsigned n) {
1030
1031    assert (n == 1);
1032
1033    if (LLVM_UNLIKELY(mMinCodePoint > UNICODE_MAX)) {
1034        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
1035    }
1036
1037    bool found = false;
1038    // Find the start of our interval
1039    while ( mBaseCodePoint <= UNICODE_MAX ) {
1040        // Find the first non-empty block
1041        if (typeOf(*mRunIterator) != Mixed) {           
1042            // If we found a full run, this must be the start of our interval.
1043            const auto baseCodePoint = mBaseCodePoint;
1044            const auto type = typeOf(*mRunIterator);
1045            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
1046            if (type == Full) {
1047                mMinCodePoint = baseCodePoint;
1048                found = true;
1049                break;
1050            }
1051        } else { // if (typeOf(t) == Mixed)
1052            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
1053                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
1054                // If we found a marker in m, it marks the beginning of our current interval.
1055                // Find it and break out of the loop.
1056                if (m) {
1057                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
1058                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
1059                    found = true;
1060                    break;
1061                }
1062                mBaseCodePoint += QUAD_BITS;
1063                ++mQuadIterator;
1064                ++mMixedRunIndex;
1065                mQuadOffset = 0;
1066            }
1067            if (found) break;
1068            ++mRunIterator;
1069            mQuadOffset = 0;
1070            mMixedRunIndex = 0;
1071        }
1072    }
1073
1074    if (!found) {
1075        assert (mBaseCodePoint == (UNICODE_MAX+1));
1076        mMinCodePoint = (UNICODE_MAX+1);
1077        return;
1078    }
1079
1080    // at this stage, the max code point is the previous max code point (initially 0)
1081    assert (mMaxCodePoint <= mMinCodePoint);
1082    found = false;
1083    // Find the end of our interval
1084    while ( mBaseCodePoint <= UNICODE_MAX ) {
1085
1086        // Find the first non-Full block
1087        if (typeOf(*mRunIterator) != Mixed) {
1088            // If this run is Empty, the max code point is the last computed base code point - 1.
1089            const auto baseCodePoint = mBaseCodePoint;
1090            const auto type = typeOf(*mRunIterator);
1091            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
1092            if (type == Empty) {
1093                mMaxCodePoint = baseCodePoint - 1;
1094                found = true;
1095                break;
1096            }
1097        } else { // if (typeOf(t) == Mixed)
1098            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
1099                const bitquad_t m = ((~*mQuadIterator)) & (FULL_QUAD_MASK << mQuadOffset);
1100                // If we found a marker in m, it marks the end of our current interval.
1101                // Find it and break out of the loop.
1102                if (m) {
1103                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
1104                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
1105                    found = true;
1106                    break;
1107                }
1108                mBaseCodePoint += QUAD_BITS;
1109                ++mQuadIterator;
1110                ++mMixedRunIndex;
1111                mQuadOffset = 0;
1112            }
1113            if (found) break;
1114            ++mRunIterator;
1115            mQuadOffset = 0;
1116            mMixedRunIndex = 0;
1117        }
1118    }
1119    // if the very last block is a mixed block and we go past it, the last code point of the range is UNICODE_MAX
1120    if (!found) {
1121        assert (mBaseCodePoint == (UNICODE_MAX+1));
1122        mMaxCodePoint = UNICODE_MAX;
1123    }
1124
1125    assert (mMinCodePoint <= mMaxCodePoint);
1126}
1127
1128/** ------------------------------------------------------------------------------------------------------------- *
1129 * @brief Empty/Full Set Constructor
1130 ** ------------------------------------------------------------------------------------------------------------- */
1131UnicodeSet::UnicodeSet() noexcept
1132: mRuns(GlobalAllocator.allocate<run_t>(1))
1133, mQuads(nullptr)
1134, mRunLength(1)
1135, mQuadLength(0)
1136, mRunCapacity(1)
1137, mQuadCapacity(0) {
1138    mRuns[0] = std::make_pair(Empty, UNICODE_QUAD_COUNT);
1139    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1140}
1141           
1142/** ------------------------------------------------------------------------------------------------------------- *
1143 * @brief Singleton Set Constructor
1144 ** ------------------------------------------------------------------------------------------------------------- */
1145UnicodeSet::UnicodeSet(const codepoint_t codepoint) noexcept
1146: mRuns(GlobalAllocator.allocate<run_t>(3))
1147, mQuads(GlobalAllocator.allocate<bitquad_t>(1))
1148, mRunLength(0)
1149, mQuadLength(1)
1150, mRunCapacity(3)
1151, mQuadCapacity(1) {
1152    assert (codepoint <= UNICODE_MAX);
1153    const codepoint_t offset = codepoint / QUAD_BITS;
1154    const codepoint_t remaining = UNICODE_QUAD_COUNT - (offset + 1);   
1155    unsigned l = 0;
1156    if (offset) {
1157        mRuns[l++] = std::make_pair(Empty, offset);
1158    }
1159    mRuns[l++] = std::make_pair(Mixed, 1);
1160    if (remaining) {
1161        mRuns[l++] = std::make_pair(Empty, remaining);
1162    }
1163    mRunLength = l;
1164    mQuads[0] = static_cast<bitquad_t>(1) << (codepoint & QUAD_LIMIT);
1165    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1166    assert (contains(codepoint));
1167    assert (codepoint == 0 || !contains(codepoint - 1));
1168    assert (codepoint == UNICODE_MAX || !contains(codepoint + 1));
1169}
1170
1171/** ------------------------------------------------------------------------------------------------------------- *
1172 * @brief Range Set Constructor
1173 ** ------------------------------------------------------------------------------------------------------------- */
1174UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi) noexcept
1175: mRuns(GlobalAllocator.allocate<run_t>(5))
1176, mQuads(GlobalAllocator.allocate<bitquad_t>(2))
1177, mRunLength(0)
1178, mQuadLength(0)
1179, mRunCapacity(5)
1180, mQuadCapacity(2) {
1181
1182    const codepoint_t lo_index = lo / QUAD_BITS;
1183    const codepoint_t hi_index = hi / QUAD_BITS;
1184    const codepoint_t lo_offset = lo & QUAD_LIMIT;
1185    const codepoint_t hi_offset = hi & QUAD_LIMIT;
1186
1187    assert (lo <= hi);
1188    assert (hi <= UNICODE_MAX);
1189
1190    // Assuming that Empty and Full quads can be of 0 length and Mixed are
1191    // length 1, we have the following cases:
1192
1193    // LO_INDEX == HI_INDEX && LO_OFFSET == 0 && HI_OFFSET == QUAD_BITS
1194
1195    //             Empty           Full            Empty
1196    //      |                 |############|                 |
1197
1198    // LO_INDEX == HI_INDEX && (LO_OFFSET != 0 || HI_OFFSET != QUAD_BITS)
1199
1200    //             Empty          Mixed             Empty
1201    //      |                 |  #######   |                 |
1202
1203    // LO_INDEX != HI_INDEX && LO_OFFSET != 0 && HI_OFFSET == QUAD_BITS
1204
1205    //          Empty    Mixed     Full            Empty
1206    //      |           |  ###|############|                 |
1207
1208    // LO_INDEX != HI_INDEX && LO_OFFSET == 0 && HI_OFFSET != QUAD_BITS
1209
1210    //             Empty           Full     Mixed    Empty
1211    //      |                 |############|###  |           |
1212
1213    // LO_INDEX != HI_INDEX && LO_OFFSET != 0 && HI_OFFSET != QUAD_BITS
1214
1215    //          Empty    Mixed     Full     Mixed    Empty
1216    //      |           |  ###|############|###  |           |
1217
1218    if (LLVM_LIKELY(lo_index != 0)) {
1219        mRuns[0] = std::make_pair(Empty, lo_index);
1220        mRunLength = 1;
1221    }
1222    if (lo_index == hi_index) {
1223        if ((lo_offset == 0) && (hi_offset == QUAD_LIMIT)) {
1224            mRuns[mRunLength++] = std::make_pair(Full, 1);
1225        } else {
1226            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
1227            const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
1228            const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
1229            mQuads[0] = lo_quad & hi_quad;
1230            mQuadLength = 1;
1231        }
1232
1233    } else {
1234        const auto lm = ((lo_offset != 0) ? 1U : 0U);
1235        const auto rm = ((hi_offset != QUAD_LIMIT) ? 1U : 0U);
1236        const auto d = (hi_index - lo_index) - (lm + rm) + 1;
1237        if (lo_offset != 0) {
1238            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
1239            mQuads[0] = (FULL_QUAD_MASK << lo_offset);
1240            mQuadLength = 1;
1241        }
1242        if (d != 0) {
1243            mRuns[mRunLength++] = std::make_pair(Full, d);
1244        }
1245        if (hi_offset != QUAD_LIMIT) {
1246            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
1247            const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
1248            mQuads[mQuadLength++] = hi_quad;
1249        }
1250    }
1251    const auto remaining = UNICODE_QUAD_COUNT - (hi_index + 1);
1252    if (LLVM_LIKELY(remaining != 0)) {
1253        mRuns[mRunLength++] = std::make_pair(Empty, remaining);
1254    }
1255    assert (mRunLength <= mRunCapacity);
1256    assert (mQuadLength <= mQuadCapacity);
1257    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1258    assert (contains(lo) && contains(hi));
1259    assert (lo == 0 || !contains(lo - 1));
1260    assert (hi == UNICODE_MAX || !contains(hi + 1));
1261}
1262
1263/** ------------------------------------------------------------------------------------------------------------- *
1264 * @brief Range List Set Constructor
1265 ** ------------------------------------------------------------------------------------------------------------- */
1266template <typename iterator>
1267inline void convertIntervalsToUnicodeSet(const iterator begin, const iterator end, RunVector & runs, QuadVector & quads) noexcept {
1268
1269    assert ("interval list must be totally ordered" && std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
1270        if (l.first > l.second) return false;
1271        if (l.second > UNICODE_MAX) return false;
1272        if (r.first > r.second) return false;
1273        if (r.second > UNICODE_MAX) return false;
1274        return l.second < r.first;
1275    }));
1276   
1277    codepoint_t prior_index = 0;
1278    bitquad_t mask = 0;
1279    for (auto interval = begin; interval != end; ) {
1280        codepoint_t lo, hi;
1281        std::tie(lo, hi) = *interval;
1282        const codepoint_t lo_index = (lo / QUAD_BITS);
1283        const codepoint_t hi_index = (hi / QUAD_BITS);
1284        const codepoint_t lo_offset = lo & QUAD_LIMIT;
1285        const codepoint_t hi_offset = hi & QUAD_LIMIT;
1286        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
1287        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
1288        append_run(Empty, lo_index - prior_index, runs);
1289        if (lo_index == hi_index) {
1290            mask |= (lo_quad & hi_quad);
1291        } else {
1292            append_quad(mask | lo_quad, quads, runs);
1293            append_run(Full, hi_index - (lo_index + 1), runs);
1294            mask = hi_quad;
1295        }
1296        // if the next interval is in our current quad, continue to the next range
1297        prior_index = hi_index;
1298        if (LLVM_LIKELY(++interval != end)) {
1299            if (hi_index == (interval->first / QUAD_BITS)) {
1300                continue;
1301            }
1302        }
1303        append_quad(mask, quads, runs);
1304        mask = 0;
1305        ++prior_index;
1306    }
1307    assert (mask == 0);
1308    if (prior_index < UNICODE_QUAD_COUNT) {
1309        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
1310    }
1311}
1312
1313/** ------------------------------------------------------------------------------------------------------------- *
1314 * @brief Interval Range Constructor
1315 ** ------------------------------------------------------------------------------------------------------------- */
1316UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end) noexcept
1317: mRuns(nullptr)
1318, mQuads(nullptr)
1319, mRunLength(0)
1320, mQuadLength(0)
1321, mRunCapacity(0)
1322, mQuadCapacity(0) {
1323    RunVector runs;
1324    QuadVector quads;
1325
1326    convertIntervalsToUnicodeSet(begin, end, runs, quads);
1327
1328    const auto n = runs.size();
1329    assert (n > 0 && n < UNICODE_QUAD_COUNT);
1330    mRuns = GlobalAllocator.allocate<run_t>(n);
1331    mRunCapacity = n;
1332    mRunLength = n;
1333    std::memcpy(mRuns, runs.data(), n * sizeof(run_t));
1334
1335    const auto m = quads.size();
1336    assert (m < UNICODE_QUAD_COUNT);
1337    if (m) {
1338        mQuads = GlobalAllocator.allocate<bitquad_t>(m);
1339        mQuadCapacity = m;
1340        mQuadLength = m;
1341        std::memcpy(mQuads, quads.data(), m * sizeof(bitquad_t));
1342    }
1343
1344    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1345}
1346
1347/** ------------------------------------------------------------------------------------------------------------- *
1348 * @brief Interval Range Constructor
1349 ** ------------------------------------------------------------------------------------------------------------- */
1350UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end) noexcept
1351: mRuns(nullptr)
1352, mQuads(nullptr)
1353, mRunLength(0)
1354, mQuadLength(0)
1355, mRunCapacity(0)
1356, mQuadCapacity(0) {
1357    RunVector runs;
1358    QuadVector quads;
1359
1360    convertIntervalsToUnicodeSet(begin, end, runs, quads);
1361
1362    const auto n = runs.size();
1363    assert (n > 0 && n < UNICODE_QUAD_COUNT);
1364    mRuns = GlobalAllocator.allocate<run_t>(n);
1365    mRunCapacity = n;
1366    mRunLength = n;
1367    std::memcpy(mRuns, runs.data(), n * sizeof(run_t));
1368
1369    const auto m = quads.size();
1370    assert (m < UNICODE_QUAD_COUNT);
1371    if (m) {
1372        mQuads = GlobalAllocator.allocate<bitquad_t>(m);
1373        mQuadCapacity = m;
1374        mQuadLength = m;
1375        std::memcpy(mQuads, quads.data(), m * sizeof(bitquad_t));
1376    }
1377
1378    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1379}
1380
1381/** ------------------------------------------------------------------------------------------------------------- *
1382 * @brief Move Constructor
1383 ** ------------------------------------------------------------------------------------------------------------- */
1384UnicodeSet::UnicodeSet(const UnicodeSet && other) noexcept
1385: mRuns(other.mRuns)
1386, mQuads(other.mQuads)
1387, mRunLength(other.mRunLength)
1388, mQuadLength(other.mQuadLength)
1389, mRunCapacity(other.mRunLength)
1390, mQuadCapacity(other.mQuadLength) {
1391    assert (verify(mRuns, other.mRunLength, mQuads, other.mQuadLength));
1392}
1393
1394/** ------------------------------------------------------------------------------------------------------------- *
1395 * @brief Move Assignment Constructor
1396 ** ------------------------------------------------------------------------------------------------------------- */
1397UnicodeSet & UnicodeSet::operator=(const UnicodeSet && other) noexcept {
1398    if (mRunCapacity) {
1399        GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
1400    }
1401    if (mQuadCapacity) {
1402        GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
1403    }
1404    mRuns = other.mRuns;
1405    mQuads = other.mQuads;
1406    mRunLength = other.mRunLength;
1407    mQuadLength = other.mQuadLength;
1408    mRunCapacity = other.mRunCapacity;
1409    mQuadCapacity = other.mQuadCapacity;
1410    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1411    return *this;
1412}
1413
1414/** ------------------------------------------------------------------------------------------------------------- *
1415 * @brief Copy Constructor
1416 ** ------------------------------------------------------------------------------------------------------------- */
1417UnicodeSet::UnicodeSet(const UnicodeSet & other) noexcept
1418: mRuns(other.mRuns)
1419, mQuads(other.mQuads)
1420, mRunLength(other.mRunLength)
1421, mQuadLength(other.mQuadLength)
1422, mRunCapacity(0) // lazily ensure reallocation on modification
1423, mQuadCapacity(0) {
1424    assert (verify(mRuns, other.mRunLength, mQuads, other.mQuadLength));
1425}
1426
1427/** ------------------------------------------------------------------------------------------------------------- *
1428 * @brief Copy Assignment Constructor
1429 ** ------------------------------------------------------------------------------------------------------------- */
1430UnicodeSet & UnicodeSet::operator=(const UnicodeSet & other) noexcept {
1431    if (mRunCapacity) {
1432        GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
1433    }
1434    if (mQuadCapacity) {
1435        GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
1436    }
1437    mRuns = other.mRuns;
1438    mQuads = other.mQuads;
1439    mRunLength = other.mRunLength;
1440    mQuadLength = other.mQuadLength;
1441    mRunCapacity = 0; // lazily ensure reallocation on modification
1442    mQuadCapacity = 0;
1443    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1444    return *this;
1445}
1446
1447/** ------------------------------------------------------------------------------------------------------------- *
1448 * @brief Internal / Predefined Constructor
1449 ** ------------------------------------------------------------------------------------------------------------- */
1450UnicodeSet::UnicodeSet(run_t * const runs, const uint32_t runLength, const uint32_t runCapacity,
1451                       bitquad_t * const quads, const uint32_t quadLength, const uint32_t quadCapacity) noexcept
1452: mRuns(runs)
1453, mQuads(quads)
1454, mRunLength(runLength)
1455, mQuadLength(quadLength)
1456, mRunCapacity(runCapacity)
1457, mQuadCapacity(quadCapacity) {
1458    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1459}
1460
1461/** ------------------------------------------------------------------------------------------------------------- *
1462 * @brief Deprecated Constructor
1463 ** ------------------------------------------------------------------------------------------------------------- */
1464UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) noexcept
1465: mRuns(GlobalAllocator.allocate<run_t>(r.size()))
1466, mQuads(q.size() == 0 ? nullptr : GlobalAllocator.allocate<bitquad_t>(q.size()))
1467, mRunLength(r.size())
1468, mQuadLength(q.size())
1469, mRunCapacity(r.size())
1470, mQuadCapacity(q.size()) {
1471    std::copy(r.begin(), r.end(), mRuns);
1472    std::copy(q.begin(), q.end(), mQuads);
1473    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
1474}
1475
1476}
Note: See TracBrowser for help on using the repository browser.