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

Last change on this file since 5909 was 5909, checked in by nmedfort, 13 months ago

Bug fix

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