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

Last change on this file since 5904 was 5904, checked in by nmedfort, 11 months ago

minor bug fix

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