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

Last change on this file since 6173 was 6173, checked in by nmedfort, 7 months ago

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

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