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

Last change on this file since 5821 was 5821, checked in by nmedfort, 16 months ago

Bug fixes

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